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

Материал из Викиконспекты
Перейти к: навигация, поиск
(→‎Производящая функция)
м (rollbackEdits.php mass rollback)
 
(не показано 36 промежуточных версий 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] помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.

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

Отношения

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

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

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

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

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

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

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

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

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

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Дискретная_математика&oldid=85782»