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