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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Схемы из функциональных элементов)
 
(не показано 11 промежуточных версий 5 участников)
Строка 3: Строка 3:
  
 
Символом <tex> \star </tex> помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.
 
Символом <tex> \star </tex> помечены дополнительные темы (возможно, сложные), которые не были подробно рассмотрены (или вообще рассмотрены) в рамках курса.
 +
 +
[https://youtube.com/andrewzta видеолекции Андрея Станкевича]
  
 
== Отношения ==
 
== Отношения ==
Строка 31: Строка 33:
 
*[[Полные системы функций. Теорема Поста о полной системе функций]]
 
*[[Полные системы функций. Теорема Поста о полной системе функций]]
 
*[[Представление функции класса DM с помощью медианы]]
 
*[[Представление функции класса DM с помощью медианы]]
 +
*[[Выражение функции XOR через медианы]]
 
*[[Пороговая функция]]
 
*[[Пороговая функция]]
 
*[[Троичная логика]]<tex>^\star</tex>
 
*[[Троичная логика]]<tex>^\star</tex>
Строка 37: Строка 40:
 
*[[Реализация булевой функции схемой из функциональных элементов]]
 
*[[Реализация булевой функции схемой из функциональных элементов]]
 
*[[Простейшие методы синтеза схем из функциональных элементов]]
 
*[[Простейшие методы синтеза схем из функциональных элементов]]
*[[Мультиплексор и демультиплексор]]<tex>^\star</tex>
+
*[[Шифратор и дешифратор]]
 +
*[[Мультиплексор и демультиплексор]]
 
*[[Метод Лупанова синтеза схем]]
 
*[[Метод Лупанова синтеза схем]]
 +
*[[Представление булевых функций линейными программами]]
 +
*[[Нижняя оценка размера схем из функциональных элементов]]
 
*[[Cумматор]]
 
*[[Cумматор]]
 
*[[Каскадный сумматор]]
 
*[[Каскадный сумматор]]
Строка 75: Строка 81:
 
* [[Избыточное кодирование, код Хэмминга]]
 
* [[Избыточное кодирование, код Хэмминга]]
 
* [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex>
 
* [[Гамма-, дельта- и омега-код Элиаса]]<tex>^\star</tex>
 +
* [[Арифметическое кодирование]]
 +
* [[Контекстное моделирование]]
  
 
== Комбинаторика ==
 
== Комбинаторика ==
Строка 109: Строка 117:
 
* [[Числа Каталана]]
 
* [[Числа Каталана]]
 
* [[Конструирование комбинаторных объектов и их подсчет]]
 
* [[Конструирование комбинаторных объектов и их подсчет]]
 +
* [[Подсчет деревьев]]
 +
* [[Метод производящих функций]]
  
 
=== Свойства комбинаторных объектов ===
 
=== Свойства комбинаторных объектов ===
Строка 119: Строка 129:
 
* [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]
 
* [[Задача о монотонных подпоследовательностях, теорема о связи длины НВП и НУП]]
  
== [[Производящая функция]] ==
+
=== Производящие функции  ===
 +
* [[Производящая функция]]
 
* [[Арифметические действия с формальными степенными рядами]]
 
* [[Арифметические действия с формальными степенными рядами]]
 
* [[Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности]]
 
* [[Теорема о связи между рациональностью производящей функции и линейной рекуррентностью задаваемой ей последовательности]]
Строка 134: Строка 145:
 
* [[Уравнение Лагранжа и теорема Лагранжа]]
 
* [[Уравнение Лагранжа и теорема Лагранжа]]
 
*[[Асимптотика коэффициентов функций, связанных между собой уравнением Лагранжа]]
 
*[[Асимптотика коэффициентов функций, связанных между собой уравнением Лагранжа]]
 +
* [[Обращение Лагранжа]]

Текущая версия на 19:55, 13 октября 2020

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

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

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

Отношения[править]

Булевы функции[править]

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

Представление информации[править]

Алгоритмы сжатия[править]

Комбинаторика[править]

Комбинаторные объекты[править]

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

Подсчёт числа объектов[править]

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

Производящие функции[править]