Редактирование: Дискретная математика

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 31: Строка 31:
 
*[[Полные системы функций. Теорема Поста о полной системе функций]]
 
*[[Полные системы функций. Теорема Поста о полной системе функций]]
 
*[[Представление функции класса DM с помощью медианы]]
 
*[[Представление функции класса DM с помощью медианы]]
*[[Выражение функции XOR через медианы]]
 
 
*[[Пороговая функция]]
 
*[[Пороговая функция]]
 
*[[Троичная логика]]<tex>^\star</tex>
 
*[[Троичная логика]]<tex>^\star</tex>
Строка 38: Строка 37:
 
*[[Реализация булевой функции схемой из функциональных элементов]]
 
*[[Реализация булевой функции схемой из функциональных элементов]]
 
*[[Простейшие методы синтеза схем из функциональных элементов]]
 
*[[Простейшие методы синтеза схем из функциональных элементов]]
*[[Шифратор и дешифратор]]
 
*[[Мультиплексор и демультиплексор]]
 
 
*[[Метод Лупанова синтеза схем]]
 
*[[Метод Лупанова синтеза схем]]
 
*[[Cумматор]]
 
*[[Cумматор]]
Строка 51: Строка 48:
 
*[[Триггеры]]<tex>^\star</tex>
 
*[[Триггеры]]<tex>^\star</tex>
 
*[[Квантовые гейты]]<tex>^\star</tex>
 
*[[Квантовые гейты]]<tex>^\star</tex>
*[[Квантовые алгоритмы]]<tex>^\star</tex>
 
  
 
== Представление информации ==
 
== Представление информации ==
Строка 77: Строка 73:
 
* [[Избыточное кодирование, код Хэмминга]]
 
* [[Избыточное кодирование, код Хэмминга]]
 
* [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex>
 
* [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex>
* [[Арифметическое кодирование]]
 
* [[Контекстное моделирование]]
 
  
 
== Комбинаторика ==
 
== Комбинаторика ==
Строка 99: Строка 93:
 
* [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
 
* [[Метод генерации случайной перестановки, алгоритм Фишера-Йетса]]
 
* [[Методы генерации случайного сочетания]]<tex>^\star</tex>
 
* [[Методы генерации случайного сочетания]]<tex>^\star</tex>
* [[Методы получения случайных комбинаторных объектов]]
 
  
 
=== Подсчёт числа объектов ===
 
=== Подсчёт числа объектов ===
 
* [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]]
 
* [[Формула включения-исключения | Формула включения-исключения, подсчет числа беспорядков]]
 
* [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
 
* [[Нахождение количества разбиений числа на слагаемые | Нахождение количества разбиений числа на слагаемые. Пентагональная теорема Эйлера]]
 +
* [[Производящая функция]]
 
* [[Лемма Бёрнсайда и Теорема Пойа]]
 
* [[Лемма Бёрнсайда и Теорема Пойа]]
 
* [[Задача об ожерельях]]
 
* [[Задача об ожерельях]]
 
* [[Числа Стирлинга первого рода]]
 
* [[Числа Стирлинга первого рода]]
 
* [[Числа Стирлинга второго рода]]
 
* [[Числа Стирлинга второго рода]]
* [[Символ Похгаммера]]
 
* [[Числа Белла]]
 
 
* [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]]<tex>^\star</tex>
 
* [[Числа Эйлера I и II рода | Числа Эйлера первого и второго рода. Подъемы в перестановках]]<tex>^\star</tex>
 
* [[Числа Каталана]]
 
* [[Числа Каталана]]
* [[Конструирование комбинаторных объектов и их подсчет]]
 
  
 
=== Свойства комбинаторных объектов ===
 
=== Свойства комбинаторных объектов ===
Строка 123: Строка 114:
 
* [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]
 
* [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]
  
== [[Производящая функция]] ==
+
== [[Динамическое программирование]] ==
* [[Арифметические действия с формальными степенными рядами]]
+
=== Классические задачи динамического программирования ===
* [[Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности]]
+
*[[Кратчайший путь в ациклическом графе]]
* [[Использование производящих функций для доказательства тождеств]]
+
*[[Задача о числе путей в ациклическом графе]]
* [[Производящие функции нескольких переменных]]
+
*[[Задача о расстановке знаков в выражении]]
* [[Разложение рациональной функции в ряд]]
+
*[[Задача о порядке перемножения матриц]]
* [[Представление производящей функций в виде непрерывных дробей]]
+
*[[Задача о наибольшей общей подпоследовательности]]
* [[Задача о счастливых билетах]]
+
*[[Задача о наибольшей возрастающей подпоследовательности]]
* [[Произведение Адамара рациональных производящих функций|Произведение Адамара]]
+
*[[Быстрый поиск наибольшей возрастающей подпоследовательности]]*
* [[Интегрирование/дифференцирование производящих функций]]
+
*[[Задача коммивояжера, ДП по подмножествам]]
* [[Производящая функция Дирихле]]
+
*[[Задача о редакционном расстоянии, алгоритм Вагнера-Фишера]]
* [[Решение рекуррентных соотношений]]
+
*[[Задача о рюкзаке]]
* [[Язык Дика]]
+
 
* [[Уравнение Лагранжа и теорема Лагранжа]]
+
=== Способы оптимизации методов динамического программирования ===
*[[Асимптотика коэффициентов функций, связанных между собой уравнением Лагранжа]]
+
*[[Метод четырех русских для умножения матриц]]
 +
*[[Применение метода четырех русских в задачах ДП на примере задачи о НОП]]<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>
 +
*[[Динамика по поддеревьям]]

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)