Дискретная математика (прошлые годы)
39 билетов · прошлая программа0/39
Алгебра логики
1
В20Функции алгебры логики. Равенство функций. Тождества для элементарных функций.
2
В21Теорема о разложении функции алгебры логики по переменным. Теорема о совершенной дизъюнктивной нормальной форме.
3
В22Полные системы. Примеры полных систем с доказательством полноты.
4
В23Теорема Жегалкина о представимости функции алгебры логики полиномом.
5
А1Алгоритм построения вектора коэффициентов полинома Жегалкина с обоснованием.
6
В24Понятие замкнутого класса. Замкнутость классов T₀, T₁, L.
7
А2Двойственность. Класс самодвойственных функций, его замкнутость.
8
В25Класс монотонных функций, его замкнутость.
9
В26Лемма о несамодвойственной функции.
10
В27Лемма о немонотонной функции.
11
А3Лемма о нелинейной функции.
12
А4Теорема Поста о полноте системы функций алгебры логики.
13
В28Теорема о максимальном числе функций в базисе в алгебре логики.
14
А5Теорема о предполных классах.
Графы
15
В29Основные понятия теории графов. Изоморфизм графов. Связность.
16
А6Деревья. Свойства деревьев.
17
В30Корневые деревья. Верхняя оценка их числа.
18
А7Алгоритм построения кратчайшего остовного дерева с обоснованием.
19
В31Геометрическая реализация графов. Теорема о реализации графов в трёхмерном пространстве.
20
В32Планарные, или плоские, графы. Формула Эйлера.
21
В33Доказательство непланарности графов K₅ и K₃,₃. Теорема Понтрягина–Куратовского с доказательством в одну сторону.
22
В34Теорема о раскраске вершин графа в 2 цвета, или теорема Кёнига.
23
А8Теорема о раскраске планарных графов в 5 цветов.
Кодирование
24
А9Алгоритм распознавания взаимной однозначности алфавитного кодирования с обоснованием.
25
А10Теорема Маркова.
26
А11Неравенство Макмиллана.
27
А12Существование префиксного кода с заданными длинами кодовых слов.
28
В35Оптимальные коды, их свойства.
29
А13Теорема редукции.
30
А14Коды с исправлением r ошибок. Оценка функции Mᵣ(n).
31
А15Коды Хэмминга. Оценка функции M₁(n).
32
В36Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов.
Схемы и сложность
33
В37Схемы из функциональных элементов. Реализация функций алгебры логики схемами.
34
В38Сумматор. Верхняя оценка сложности сумматора. Вычитатель.
35
А19Метод Карацубы построения схемы для умножения, верхняя оценка её сложности.
Автоматы
36
В39Понятие автоматных функций, их представление диаграммой Мура. Единичная задержка.
37
А16Схемы из функциональных элементов и элементов задержки. Автоматность осуществляемых ими отображений.
38
А17Моделирование автоматной функции схемой из функциональных элементов и элементов задержки.
39
А18Теорема Мура.