Дискретная математика
52 билета + 20 задач · кафедра МК ВМК0/72
★ — на экзамене по этим билетам можно пользоваться письменными материалами при подготовке к ответу.
Алгебра логики
1
Функции алгебры логики. Существенность переменных. Суперпозиция. Тождества.
2
Функции алгебры логики. Разложение функции алгебры логики по переменным.
3
Дизъюнктивная нормальная форма (ДНФ). Выразимость функции алгебры логики совершенной ДНФ.
4
Конъюнктивная нормальная форма (КНФ). Выразимость функции алгебры логики совершенной КНФ.
5
Полином Жегалкина. Теорема Жегалкина о выразимости функции алгебры логики полиномом Жегалкина.
6
★Полиномы Жегалкина. Вычисление коэффициентов полинома Жегалкина функции алгебры логики. Быстрый алгоритм построения полинома Жегалкина.
7
Функции алгебры логики. Полные системы. Примеры полных систем (с доказательством полноты).
8
Функции алгебры логики. Замыкание. Свойства замыкания. Замкнутый класс. Замкнутые классы функций, сохраняющих константу, и линейных функций.
9
Функции алгебры логики. Двойственность. Самодвойственные функции. Замкнутый класс самодвойственных функций.
10
Функции алгебры логики. Монотонные функции. Замкнутый класс монотонных функций.
11
Функции алгебры логики. Самодвойственные функции. Лемма о несамодвойственной функции.
12
Функции алгебры логики. Монотонные функции. Лемма о немонотонной функции.
13
Функции алгебры логики. Линейные функции. Лемма о нелинейной функции.
14
Функции алгебры логики. Полнота. Теорема Поста о полноте в алгебре логики.
15
Функции алгебры логики. Базис. Теорема о числе функций в базисе алгебры логики.
16
★Функции алгебры логики. Предполные классы. Замкнутость предполного класса. Теорема о предполных классах.
Графы
17
Графы (псевдографы, мультиграфы, простые графы). Изоморфизм графов. Степень вершины, формула Эйлера для степеней вершин.
18
Графы. Пути, цепи, простые цепи. Замкнутые пути, циклы, простые циклы. Свойства путей и циклов в графе.
19
Графы. Связность. Два свойства связных графов. Компоненты связности графа. Теорема о соотношении между числом вершин, ребер и компонент связности в графе.
20
Деревья. Теорема о равносильных определениях дерева.
21
Деревья. Обход дерева в глубину из заданной вершины. Верхняя оценка числа неизоморфных деревьев с заданным числом ребер.
22
Остовные деревья. Существование остовного дерева в связном графе: три алгоритма построения остовного дерева (с обоснованием).
23
★Кратчайшие остовные деревья. Алгоритм построения кратчайшего остовного дерева в связном графе (с обоснованием).
24
Геометрическое представление графов в n-мерном пространстве. Теорема о геометрическом представлении графов в трехмерном пространстве.
25
Планарные графы. Укладка планарного графа на плоскости. Грань планарного графа при его укладке на плоскости. Формула Эйлера для планарных графов.
26
Планарные графы. Свойства планарных графов (верхняя оценка числа ребер, существование вершины ограниченной степени).
27
Планарные графы. Графы K5 и K3,3. Непланарность графов K5 и K3,3.
28
Планарные графы. Гомеоморфизм графов. Теорема Понтрягина-Куратовского (доказательство в одну сторону).
29
Раскраски вершин графов. Теорема о раскраске вершин графа в 2 цвета (теорема Кенига).
30
Раскраски вершин графов. Теорема о раскраске вершин планарных графов в 5 цветов.
Кодирование
31
Кодирование, однозначность (разделимость) кодирования. Алфавитное кодирование, алфавитные коды. Однозначность (разделимость) алфавитного кода. Некоторые однозначные алфавитные коды (равномерные, префиксные, суффиксные).
32
★Алфавитные коды. Граф однозначности алфавитного кода. Алгоритм Маркова распознавания однозначности алфавитного кода (с обоснованием).
33
★Алфавитные коды. Теорема Маркова об алфавитных кодах.
34
★Алфавитные коды. Неравенство Макмиллана.
35
Алфавитные коды. Префиксные коды. Существование префиксного кода с заданными длинами кодовых слов.
36
Коды с минимальной избыточностью (оптимальные коды). Три леммы о свойствах кодов с минимальной избыточностью.
37
★Коды с минимальной избыточностью (оптимальные коды). Теорема редукции.
38
Коды с минимальной избыточностью (оптимальные коды). Алгоритм Хаффмана построения кода с минимальной избыточностью.
39
Равномерные двоичные коды. Ошибки замещения. Коды, обнаруживающие и исправляющие ошибки. Критерии кодов, обнаруживающих и исправляющих t ошибок.
40
★Коды, исправляющие t ошибок. Оценки максимальной мощности кода, исправляющего t ошибок.
41
Коды, исправляющие одну ошибку. Коды Хэмминга. Оценки мощности кода, исправляющего одну ошибку.
42
Код Хэмминга. Алгоритмы кодирования, исправления ошибки и декодирования в коде Хэмминга.
43
Линейные двоичные коды. Теорема о кодовом расстоянии линейных кодов.
Автоматы
44
Конечные автоматы. Функционирование конечного автомата. Конечно-автоматные функции. Канонические уравнения и диаграмма Мура конечного автомата. Единичная задержка, ее конечно-автоматность.
45
★Конечные автоматы. Отличимость состояний конечного автомата. Теорема Мура. Достижимость оценки теоремы Мура.
Схемы из функциональных элементов
46
Дискретные преобразователи без памяти. Схемы из функциональных элементов (СФЭ). Выразимость функции алгебры логики схемой из функциональных элементов в базисе из конъюнкции, дизъюнкции и отрицания.
47
★Дискретные преобразователи с конечной памятью. Схемы из функциональных элементов и элементов задержки (СФЭЗ). Автоматность осуществляемых ими отображений.
48
★Дискретные преобразователи с конечной памятью. Выразимость автоматной функции схемой из функциональных элементов и элементов задержки (при подходящем кодировании).
49
Сумматор порядка n. Верхняя оценка сложности СФЭ n-разрядного сумматора.
50
Вычитатель порядка n. Верхняя оценка сложности СФЭ n-разрядного вычитателя.
51
Умножитель порядка n. Порядок сложности СФЭ n-разрядного умножителя по алгоритму «в столбик». Оценки сложности СФЭ умножения n-разрядного числа на степень двойки и на разряд и умножения (n+1)-разрядных чисел.
52
★Метод Карацубы построения умножителя. Оценка сложности СФЭ умножения 2n-разрядных чисел. Верхняя оценка сложности СФЭ n-разрядного умножителя по методу Карацубы.
Задачи
53
Найти существенные и фиктивные переменные заданной функции алгебры логики.
54
Найти совершенную ДНФ, совершенную КНФ или полином Жегалкина заданной функции алгебры логики.
55
Подсчитать число функций алгебры логики, зависящих от n переменных, в заданном множестве.
56
Исследовать на полноту заданной системы функций алгебры логики (конечной или бесконечной).
57
Выяснить, является ли данная система функций алгебры логики базисом, или выделить из заданной системы функций алгебры логики все базисы.
58
Найти число неизоморфных графов с заданными свойствами и изобразить эти графы.
59
Найти код упорядоченного корневого дерева или восстановить упорядоченное корневое дерево по коду.
60
Найти в заданном графе подграф, гомеоморфный графу K_5 или графу K_3,3.
61
Выяснить, является ли заданный граф планарным.
62
Выяснить, найдется ли планарный граф с заданными свойствами.
63
Найти хроматическое число или хроматический индекс заданного графа.
64
Исследовать разделимость заданного алфавитного кода (по алгоритму Маркова).
65
Исследовать разделимость заданного алфавитного кода по неравенству Макмиллана или построить префиксный код с заданными длинами кодовых слов.
66
Найти оптимальный алфавитный двоичный код по заданному набору частот.
67
Установить, сколько ошибок замещения обнаруживает или исправляет заданный равномерный код.
68
Кодировать или исправить ошибку и декодировать сообщение в коде Хэмминга.
69
Найти кодовое расстояние заданного линейного кода.
70
Найти диаграмму Мура автоматной функции, заданной описанием.
71
Найти диаграмму Мура, каноническую таблицу, канонические уравнения или СФЭ с задержками автоматной функции, заданной одним из перечисленных способов.
72
Построить диаграмму Мура, не содержащую недостижимых и неотличимых состояний, для заданной автоматной функции.