Асимптотики комбинаторных чисел

Apr 2, 2014Download as PPTX, PDF2 likes1,071 views

Alex Dainiak

Дискретные
структуры
МФТИ, осень 2013
Александр Дайняк
www.dainiak.com

Не всегда нужно знать точное
значение
Сравним:
• «Мой алгоритм проработает 5 дней»
• Алгоритм проработал 6 дней
и
• «Мой алгоритм проработает 1000 дней»
• Алгоритм проработал 1001 день

Оценки для чисел Стирлинга и Белла (без
доказательства)

Обсуждаем два определения k-связности. Доказываем теорему Менгера об их эквавалентности (через теорему Форда—Фалкерсона). Доказываем теоремы о построении 2-связных и 3-связных графов. Вводим деревья блоков и точек сочленения. Доказываем теорему Мадера о существовании k-связного подграфа. [Слайды курса, прочитанного в МФТИ в 2013 году.]

Теорема о 5 красках. Теорема Холла.Alex Dainiak

��

Основы теории графов 05: критерии планарности графовAlex Dainiak

��

Основы теории графов 08: раскраски и списочные раскраскиAlex Dainiak

��

Вводим понятие списочной раскраски. Демонстрируем различие между обчным и списочным хроматическим числом. Доказываем теоремы Брукса и Визинга. Доказываем теорему Алона об оценки списочного хроматического числа через минимальную степень вершин. Доказываем верхнюю оценку на списочное хроматическое число через обычное. [Слайды курса, прочитанного в МФТИ в 2013 году.]

Раскраски и укладки графовAlex Dainiak

��

Основы теории графов 01: напоминание определений, теорема Форда—ФалкерсонаAlex Dainiak

��

Основы теории графов 06: триангуляции и трёхсвязные планарные графыAlex Dainiak

��

Вводим понятие триангуляций. Доказываем, что триангуляции трёхсвязны. Доказываем критерий Татта о том, когда множество образует границу грани в трёхсвязном планарном графе. Доказываем теорему Вагнера—Фари о том, что у любого планарного графа существует укладка, в которой рёбра — отрезки прямых линий. [Слайды курса, прочитанного в МФТИ в 2013 году.]

Основы теории графов 02: факторизация графов (разложение на простые подграфы)Alex Dainiak

��

Доказываем теоремы о разложении полных графов на полные двудольные: Грэхема—Поллака и Анселя. Доказываем теорему Татта о критерии существования совершенного паросочетания в произвольном графе. [Слайды курса, прочитанного в МФТИ в 2013 году.]

Основы теории графов 09: раскраски планарных графов, совершенные графыAlex Dainiak

��

Рассматриваем раскраски планарных графов и другие темы, связанные с раскрасками. Доказываем теорему Томассена о том, что списочное хроматическое число любого планарного графа не превышает пяти. Доказываем теорему Эрдёша о том, что существуют графы с большим хроматическим числом и одновременно большим обхватом. Рассматриваем совершенные графы и доказываем слабую гипотезу Бержа. [Слайды курса, прочитанного в МФТИ в 2013 году.]

Основы теории графов 10: экстремальная теория графовAlex Dainiak

��

Доказываем теорему Турана, а затем теорему Эрдёша—Стоуна—Симоновица(Шимоновича) о связи хроматического числа подграфа с максимальным числом рёбер в графе, его не содержащего. [Слайды курса, прочитанного в МФТИ в 2013 году.]

Основы теории графов 11: гамильтоновы циклыAlex Dainiak

��

Доказываем достаточные условия существования в графе гамильтоновых циклов: условия Эрдёша—Хватала, Асратяна—Хачатряна, Хватала. Доказываем необходимые условия существования гамильтонова цикла в планарном графе (теорема Гринберга). [Слайды курса, прочитанного в МФТИ в 2013 году.]

Основы теории графов 04: метрики на деревьяхAlex Dainiak

��

Конспект лекций по теории кодированияAlex Dainiak

��

Графовая модель канала связи. Шенноновская ёмкостьAlex Dainiak

��

Приложения теории кодированияAlex Dainiak

��

Приложения кодов, исправляющих ошибки. Рандомизированный протокол в коммуникационной сложности. Криптосхема МакЭлиса. Однородные (псевдослучайные) множества на основе кодов, их приложения к дерандомизации задачи выполнимости и к задаче разделения секрета.

Циклические коды БЧХ, Хемминга. Восстановление синхронизацииAlex Dainiak

��

Циклические коды. Граница БЧХAlex Dainiak

��

Циклические коды. Проверочный и порождающий многочлены, критерий существования кода с заданным порождающим многочленом. Вид порождающей и проверочной матриц. Систематическое кодирование. Граница Боуза—Чоудхури—Хоквингема.

Коды на основе многочленов и алгоритмы их декодированияAlex Dainiak

��

Коды Рида—Соломона. Алгоритм декодирования Берлекэмпа—Велча. Коды Рида—Маллера: кодовое расстояние, алгоритм мажоритарного декодирования. Варианты обобщений конструкции Рида—Маллера. Лемма Липтона—ДеМилло—Шварца—Зиппеля. Понятие об алгеброгеометрических кодах.

Задача о ближайшем кодовом слове. Коды Галлагера—Сипсера—ШпильманаAlex Dainiak

��

Сложность задачи декодирования линейных кодов: задача NCP (задачи о ближайшем кодовом слове). Графы-расширители. Вероятностное доказательство существования расширителей. Коды на основе двудольных графов. Кодовое расстояние кодов на основе расширителей. Алгоритм декодирования Сипсера—Шпильмана.

Линейные кодыAlex Dainiak

��

Линейные коды. Определения. Порождающая и проверочная матрицы. Связь кодового расстояния с проверочной матрицей. Граница Варшамова—Гилберта. Систематическое кодирование. Декодирование по синдрому. Коды Хемминга. Остаточный код. Граница Грайсмера—Соломона—Штиффлера.

Границы Плоткина и Элайеса—БассалыгоAlex Dainiak

��

Коды, исправляющие ошибки. Простейшие границы. Коды Варшамова—Тененгольца.Alex Dainiak

��

Задача исправления и обнаружения ошибок. Геометрическая интерпретация. Типы ошибок. Метрики Хемминга и Левенштейна. Кодовое расстояние. Основные задачи теории кодов, исправляющих ошибки. Коды Варшамова—Тененгольца, алгоритмы исправления одиночных ошибок выпадения и вставки символов. Простейшие границы для параметров кодов, исправляющих ошибки замещения: границы сферической упаковки, Синглтона.

More Related Content

Viewers also liked (12)

Основы теории графов 03: связностьAlex Dainiak

��

Теорема о 5 красках. Теорема Холла.Alex Dainiak

��

Основы теории графов 05: критерии планарности графовAlex Dainiak

��

Основы теории графов 08: раскраски и списочные раскраскиAlex Dainiak

��

Раскраски и укладки графовAlex Dainiak

��

Основы теории графов 01: напоминание определений, теорема Форда—ФалкерсонаAlex Dainiak

��

Основы теории графов 06: триангуляции и трёхсвязные планарные графыAlex Dainiak

��

Основы теории графов 02: факторизация графов (разложение на простые подграфы)Alex Dainiak

��

Основы теории графов 09: раскраски планарных графов, совершенные графыAlex Dainiak

��

Основы теории графов 10: экстремальная теория графовAlex Dainiak

��

Основы теории графов 11: гамильтоновы циклыAlex Dainiak

��

Основы теории графов 04: метрики на деревьяхAlex Dainiak

��

Основы теории графов 03: связностьAlex Dainiak

��

Теорема о 5 красках. Теорема Холла.Alex Dainiak

��

Основы теории графов 05: критерии планарности графовAlex Dainiak

��

Основы теории графов 08: раскраски и списочные раскраскиAlex Dainiak

��

Раскраски и укладки графовAlex Dainiak

��

Основы теории графов 01: напоминание определений, теорема Форда—ФалкерсонаAlex Dainiak

��

Основы теории графов 06: триангуляции и трёхсвязные планарные графыAlex Dainiak

��

Основы теории графов 02: факторизация графов (разложение на простые подграфы)Alex Dainiak

��

Основы теории графов 09: раскраски планарных графов, совершенные графыAlex Dainiak

��

Основы теории графов 10: экстремальная теория графовAlex Dainiak

��

Основы теории графов 11: гамильтоновы циклыAlex Dainiak

��

Основы теории графов 04: метрики на деревьяхAlex Dainiak

��

More from Alex Dainiak (19)

Конспект лекций по теории кодированияAlex Dainiak

��

Графовая модель канала связи. Шенноновская ёмкостьAlex Dainiak

��

Приложения теории кодированияAlex Dainiak

��

Циклические коды БЧХ, Хемминга. Восстановление синхронизацииAlex Dainiak

��

Циклические коды. Граница БЧХAlex Dainiak

��

Коды на основе многочленов и алгоритмы их декодированияAlex Dainiak

��

Задача о ближайшем кодовом слове. Коды Галлагера—Сипсера—ШпильманаAlex Dainiak

��

Линейные кодыAlex Dainiak

��

Границы Плоткина и Элайеса—БассалыгоAlex Dainiak

��

Коды, исправляющие ошибки. Простейшие границы. Коды Варшамова—Тененгольца.Alex Dainiak

��

Алфавитное кодирование. Коды с минимальной избыточностью. Теорема Макмиллана.Alex Dainiak

��

Алфавитное кодирование. Достаточные условия однозначности декодирования: равномерность, префиксность, суффиксность. Распознавание однозначности: критерий Маркова. Оценка длины неоднозначно декодируемого слова. Неравенство Крафта—Макмиллана; существование префиксного кода с заданным набором длин слов; следствие об универсальности префиксных кодов. Коды с минимальной избыточностью: постановка задачи, теорема Хаффмана о редукции.

Коды Адамара. Каскадные коды Форни.Alex Dainiak

��

Визуализация графов: left-right алгоритм распознавания планарностиAlex Dainiak

��

Визуализация графов: укладки деревьевAlex Dainiak

��

Визуализация графов: теорема Татта о барицентрической укладкеAlex Dainiak

��

Визуализация графов: историяAlex Dainiak

��

Визуализация графов: нижние оценки и NP-трудностьAlex Dainiak

��

Размерность Вапника—ЧервоненкисаAlex Dainiak

��

Теорема Алона о нулях и её примененияAlex Dainiak

��

Конспект лекций по теории кодированияAlex Dainiak

��

Графовая модель канала связи. Шенноновская ёмкостьAlex Dainiak

��

Приложения теории кодированияAlex Dainiak

��

Циклические коды БЧХ, Хемминга. Восстановление синхронизацииAlex Dainiak

��

Циклические коды. Граница БЧХAlex Dainiak

��

Коды на основе многочленов и алгоритмы их декодированияAlex Dainiak

��

Задача о ближайшем кодовом слове. Коды Галлагера—Сипсера—ШпильманаAlex Dainiak

��

Линейные кодыAlex Dainiak

��

Границы Плоткина и Элайеса—БассалыгоAlex Dainiak

��

Коды, исправляющие ошибки. Простейшие границы. Коды Варшамова—Тененгольца.Alex Dainiak

��

Алфавитное кодирование. Коды с минимальной избыточностью. Теорема Макмиллана.Alex Dainiak

��

Коды Адамара. Каскадные коды Форни.Alex Dainiak

��

Визуализация графов: left-right алгоритм распознавания планарностиAlex Dainiak

��

Визуализация графов: укладки деревьевAlex Dainiak

��

Визуализация графов: теорема Татта о барицентрической укладкеAlex Dainiak

��

Визуализация графов: историяAlex Dainiak

��

Визуализация графов: нижние оценки и NP-трудностьAlex Dainiak

��

Размерность Вапника—ЧервоненкисаAlex Dainiak

��

Теорема Алона о нулях и её примененияAlex Dainiak

��

Асимптотики комбинаторных чисел

1. Дискретные структуры МФТИ, осень 2013 Александр Дайняк www.dainiak.com

2. Комбинаторные числа

3. Не всегда нужно знать точное значение Сравним: • «Мой алгоритм проработает 5 дней» • Алгоритм проработал 6 дней и • «Мой алгоритм проработает 1000 дней» • Алгоритм проработал 1001 день

4. Часто точное значение трудно вычислить

5. Нужно формализовать понятие «примерно»

6. Примеры

7. Скорости роста величин

8. Сравнение скоростей роста

9. Сравнение скоростей роста

10. Примеры

11. Сравнение скоростей роста

12. Примеры

13. Сравнение скоростей роста

14. Примеры

15. Сравнение скоростей роста