Дискретная математика — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Производящая функция)
м (rollbackEdits.php mass rollback)
 
(не показано 39 промежуточных версий 22 участников)
Строка 3: Строка 3:
  
 
Символом <tex> \star </tex> помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.
 
Символом <tex> \star </tex> помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.
 +
 +
[https://youtube.com/andrewzta видеолекции Андрея Станкевича]
  
 
== Отношения ==
 
== Отношения ==
 +
*[[Множества]]
 
*[[Определение отношения]]
 
*[[Определение отношения]]
 
*[[Композиция отношений|Композиция отношений, степень отношения, обратное отношение]]
 
*[[Композиция отношений|Композиция отношений, степень отношения, обратное отношение]]
Строка 31: Строка 34:
 
*[[Полные системы функций. Теорема Поста о полной системе функций]]
 
*[[Полные системы функций. Теорема Поста о полной системе функций]]
 
*[[Представление функции класса DM с помощью медианы]]
 
*[[Представление функции класса DM с помощью медианы]]
 +
*[[Выражение функции XOR через медианы]]
 
*[[Пороговая функция]]
 
*[[Пороговая функция]]
 
*[[Троичная логика]]<tex>^\star</tex>
 
*[[Троичная логика]]<tex>^\star</tex>
Строка 37: Строка 41:
 
*[[Реализация булевой функции схемой из функциональных элементов]]
 
*[[Реализация булевой функции схемой из функциональных элементов]]
 
*[[Простейшие методы синтеза схем из функциональных элементов]]
 
*[[Простейшие методы синтеза схем из функциональных элементов]]
 +
*[[Шифратор и дешифратор]]
 +
*[[Мультиплексор и демультиплексор]]
 
*[[Метод Лупанова синтеза схем]]
 
*[[Метод Лупанова синтеза схем]]
 +
*[[Представление булевых функций линейными программами]]
 +
*[[Нижняя оценка размера схем из функциональных элементов]]
 
*[[Cумматор]]
 
*[[Cумматор]]
 
*[[Каскадный сумматор]]
 
*[[Каскадный сумматор]]
Строка 48: Строка 56:
 
*[[Триггеры]]<tex>^\star</tex>
 
*[[Триггеры]]<tex>^\star</tex>
 
*[[Квантовые гейты]]<tex>^\star</tex>
 
*[[Квантовые гейты]]<tex>^\star</tex>
 +
*[[Квантовые алгоритмы]]<tex>^\star</tex>
  
 
== Представление информации ==
 
== Представление информации ==
Строка 57: Строка 66:
 
== Алгоритмы сжатия ==
 
== Алгоритмы сжатия ==
 
* [[Алгоритм Хаффмана]]
 
* [[Алгоритм Хаффмана]]
* [[Оптимальное хранение словаря в алгоритме Хаффмана]]
 
 
* [[Алгоритм Хаффмана за O(n)]]
 
* [[Алгоритм Хаффмана за O(n)]]
 
* [[Алгоритм Ху-Таккера]]<tex>^\star</tex>
 
* [[Алгоритм Ху-Таккера]]<tex>^\star</tex>
Строка 72: Строка 80:
 
* [[Расстояние Хэмминга]]
 
* [[Расстояние Хэмминга]]
 
* [[Избыточное кодирование, код Хэмминга]]
 
* [[Избыточное кодирование, код Хэмминга]]
 +
* [[Обнаружение и исправление ошибок кодирования]]
 
* [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex>
 
* [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex>
 +
* [[Арифметическое кодирование]]
 +
* [[Контекстное моделирование]]
  
 
== Комбинаторика ==
 
== Комбинаторика ==
Строка 93: Строка 104:
 
* [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
 
* [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
 
* [[Методы генерации случайного сочетания]]<tex>^\star</tex>
 
* [[Методы генерации случайного сочетания]]<tex>^\star</tex>
 +
* [[Методы получения случайных комбинаторных объектов]]
  
 
=== Подсчёт числа объектов ===
 
=== Подсчёт числа объектов ===
Строка 101: Строка 113:
 
* [[Числа Стирлинга первого рода]]
 
* [[Числа Стирлинга первого рода]]
 
* [[Числа Стирлинга второго рода]]
 
* [[Числа Стирлинга второго рода]]
 +
* [[Символ Похгаммера]]
 +
* [[Числа Белла]]
 
* [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]]<tex>^\star</tex>
 
* [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]]<tex>^\star</tex>
 
* [[Числа Каталана]]
 
* [[Числа Каталана]]
 +
* [[Конструирование комбинаторных объектов и их подсчет]]
 +
* [[Подсчет деревьев]]
 +
* [[Метод производящих функций]]
  
 
=== Свойства комбинаторных объектов ===
 
=== Свойства комбинаторных объектов ===
Строка 113: Строка 130:
 
* [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]
 
* [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]
  
== [[Производящая функция]] ==
+
=== Производящие функции  ===
 +
* [[Производящая функция]]
 
* [[Арифметические действия с формальными степенными рядами]]
 
* [[Арифметические действия с формальными степенными рядами]]
 +
* [[Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности]]
 +
* [[Асимптотическое поведение последовательности, заданной рекуррентным соотношением]]
 +
* [[Использование производящих функций для доказательства тождеств]]
 
* [[Производящие функции нескольких переменных]]
 
* [[Производящие функции нескольких переменных]]
 
* [[Разложение рациональной функции в ряд]]
 
* [[Разложение рациональной функции в ряд]]
 +
* [[Представление производящей функций в виде непрерывных дробей]]
 
* [[Задача о счастливых билетах]]
 
* [[Задача о счастливых билетах]]
<!--* [[Интегрирование/дифференцирование формальных степенных рядов]]-->
+
* [[Произведение Адамара рациональных производящих функций|Произведение Адамара]]
 
+
* [[Интегрирование/дифференцирование производящих функций]]
== [[Динамическое программирование]] ==
+
* [[Производящая функция Дирихле]]
=== Классические задачи динамического программирования ===
+
* [[Решение рекуррентных соотношений]]
*[[Кратчайший путь в ациклическом графе]]
+
* [[Язык Дика]]
*[[Задача о числе путей в ациклическом графе]]
+
* [[Уравнение Лагранжа и теорема Лагранжа]]
*[[Задача о расстановке знаков в выражении]]
+
*[[Асимптотика коэффициентов функций, связанных между собой уравнением Лагранжа]]
*[[Задача о порядке перемножения матриц]]
+
* [[Обращение Лагранжа]]
*[[Задача о наибольшей общей подпоследовательности]]
+
* [[Автокорреляционный многочлен]]
*[[Задача о наибольшей возрастающей подпоследовательности]]
 
*[[Быстрый поиск наибольшей возрастающей подпоследовательности]]*
 
*[[Задача коммивояжера, ДП по подмножествам]]
 
*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
 
*[[Задача о рюкзаке]]
 
 
 
=== Способы оптимизации методов динамического программирования ===
 
*[[Метод четырех русских для умножения матриц]]
 
*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]<tex>^\star</tex>
 
*[[Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза]]
 
*[[Meet-in-the-middle]]<tex>^\star</tex>
 
*[[Convex hull trick]]
 
 
 
=== Другие задачи ===
 
*[[Задача о расстоянии Дамерау-Левенштейна]]<tex>^\star</tex>
 
*[[Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами]]
 
*[[Задача о наибольшей подпоследовательности-палиндроме]]
 
*[[Задача о наибольшей общей возрастающей последовательности]]<tex>^\star</tex>
 
*[[Задача о наибольшей общей палиндромной подпоследовательности]]<tex>^\star</tex>
 
*[[Динамическое программирование по профилю]]<tex>^\star</tex>
 
*[[Динамика по поддеревьям]]
 

Текущая версия на 19:40, 4 сентября 2022

Убедительная просьба читать правила оформления вики-конспектов.

Символом [math] \star [/math] помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.

видеолекции Андрея Станкевича

Отношения

Булевы функции

Схемы из функциональных элементов

Представление информации

Алгоритмы сжатия

Комбинаторика

Комбинаторные объекты

Генерация комбинаторных объектов

Подсчёт числа объектов

Свойства комбинаторных объектов

Производящие функции