- •1. Основные понятия теории графов, удаленность вершины, центр, радиус и диаметр графа.
- •2. Способы задания графов, свойства матриц смежности и инциденций, теорема о рукопожатиях.
- •3. Основные операции над графами, неравенства для числа вершин, ребер и компонент связности графа.
- •4. Типы графов, дополнительные графы, двудольные графы, критерий двудольности.
- •5. Обходы графов: эйлеровы цепи и циклы, необходимые и достаточные условия их существования, алгоритм Флери.
- •6. Обходы графов: гамильтоновы цепи и циклы, достаточные условия их существования.
- •7. Деревья, их свойства, кодирование деревьев, остовные деревья.
- •8. Экстремальные задачи теории графов: минимальное остовное дерево, алгоритмы Прима и Краскала.
- •9. Экстремальные задачи теории графов: задача коммивояжера, «жадный» алгоритм
- •10. Экстремальные задачи теории графов: задача о кратчайшем пути, алгоритм Дейкстры.
- •11. Изоморфизм и гомеоморфизм графов, методы доказательства изоморфности и неизоморфности графов.
- •12. Плоские укладки графов, планарные графы, критерий Понтрягина-Куратовского.
- •13. Необходимые условия планарности, формула Эйлера для планарных графов.
- •14. Правильные вершинные раскраски графов, хроматическое число, неравенства для хроматического числа.
- •15. Теорема о пяти красках, гипотеза четырех красок, «жадный» алгоритм.
- •16. Хроматический многочлен, его нахождение и свойства.
- •17. Задача о поиске выхода из лабиринта, реберная раскраска графа.
- •18. Ориентированные графы, источники и стоки, топологическая сортировка, алгоритм Демукрона.
- •19. Составление расписания выполнения комплекса работ в кратчайшие сроки методами теории графов.
- •20. Элементарные булевы функции и способы их задания (табличный, векторный, формульный, графический, карта Карно).
- •21. Существенные и фиктивные переменные булевых функций, основные тождества, эквивалентные преобразования формул.
- •22. Линейные и нелинейные полиномы Жегалкина, разложение булевых функций в полином Жегалкина методом неопределенных коэффициентов.
- •23. Линейные и нелинейные полиномы Жегалкина, разложение булевых функций в полином Жегалкина методом эквивалентных преобразований.
- •24. Разложение булевых функций в сднф и скнф.
- •25. Минимизация днф и кнф методом эквивалентных преобразований.
- •26. Минимизация днф и кнф с помощью карт Карно.
- •27. Замкнутые классы булевых функций т0, т1, l, лемма о нелинейной функции.
- •28. Замкнутые классы булевых функций s и м, леммы о несамодвойственной и немонотонной функции.
- •29. Полная система функций, теорема о двух системах булевых функций.
- •30. Теорема Поста о полноте системы булевых функций, алгоритм проверки системы на полноту, базис.
- •31. Схемы из функциональных элементов, правила построения и функционирования, метод синтеза сфэ, основанный на сднф и скнф.
- •32. Метод синтеза сфэ, основанный на компактной реализации всех конъюнкций с помощью универсального многополюсника, сложность получаемых схем.
- •33. Основные комбинаторные операции, сочетания и размещения (с возвращением и без возвращения элементов).
- •34. Комбинаторные принципы сложения, умножения, дополнения, включения-исключения.
- •35. Биномиальные коэффициенты, их свойства, бином Ньютона.
- •36. Треугольник Паскаля, полиномиальная формула.
- •37. Алфавитное кодирование: необходимое и достаточные условия однозначности декодирования.
- •38. Алфавитное кодирование: теорема Маркова, алгоритм Маркова.
- •39. Коды с минимальной избыточностью (коды Хаффмана), метод построения.
- •40. Линейные коды, порождающая матрица, двойственный код.
- •41. Самокорректирующиеся коды (коды Хэмминга), метод построения.
- •42. Определение, схема и функционирование абстрактного автомата, способы задания автоматов.
- •43. Типы конечных автоматов, автоматы Мили и Мура, автоматы-генераторы.
- •44. Слова и языки, операции над ними, их свойства.
- •45. Регулярные выражения и регулярные языки, теорема Клини.
- •46. Задача анализа автоматов-распознавателей.
- •47. Задача синтеза автоматов-распознавателей.
- •48. Эквивалентные состояния автомата-распознавателя, эквивалентные автоматы-распознаватели, минимизация автоматов-распознавателей, алгоритм Мили.
- •49. Эквивалентные состояния автомата-преобразователя, эквивалентные автоматы- преобразователи, минимизация автоматов- преобразователей, алгоритм Мили.
- •50. Детерминированные и недетерминированные функции, примеры, способы задания.
- •51. Ограниченно-детерминированные (автоматные) функции, способы их задания.
- •52. Логические автоматы, способы их задания, синтез двоичного сумматора.
- •53. Операции над логическими автоматами: суперпозиция и введение обратной связи.
44. Слова и языки, операции над ними, их свойства.
Определение.Входное слово – произвольная строка конечной длины, составленная из символов входного алфавита А. У таких автоматов одно или несколько состояний заранее объявляются заключительными. Считается, что автомат распознал слово, поданное ему на вход, тогда и только тогда, когда он завершил работу над этим словом в одном из своих заключительных состояний.
Определение.Язык – множество всех слов, распознаваемых автоматом. Сам язык может быть как конечным, так и бесконечным, но в любом случае он состоит только из слов, распознаваемых соответствующим автоматом.
Определение.Суммой языковLиL´называется язык, который обозначаетсяL+L´и получается объединением множествLиL´, т.е.L+L´ =.
Определение.Произведением языковLиL´называется язык, который обозначаетсяL·L´ и получается в результате конкатенации всех возможных словwиw´, гдеwпринадлежит языкуL, аw´– языкуL´, т.е.L·L´ =.
Заметим, что язык L·L´, как правило, отличается от языкаL´·L, хотя некоторые слова могут принадлежать обоим произведениям.
Определение.Итерацией языкаLназывается язык, который обозначаетсяL* и получается в результате сложения бесконечного числа языков {Λ} +L+L2+L3+ … +Lk+ …, т.е.L* =
Итерация выражается через операции сложения и умножения языков. Из всех введенных операций над языками она единственная, которая позволяет из конечного языка получить бесконечный.
Таким образом, с помощью введенных операций сложения, умножения и итерации некоторые языки можно выражать в виде формул через более простые языки. Причем результатом сложения или умножения двух конечных языков всегда будет конечный язык, и лишь итерация позволяет из конечного языка получить бесконечный. Некоторые важные свойства операций над языками:
1. L1· (L2+L3) =L1·L2+L1·L3; |
5. L·Λ=L; |
2. (L1+L2) ·L3=L1·L3+L2·L3; |
6. L·L* =L*·L; |
3. L+L=L; |
7. Λ+L·L* =L*; |
4. L+L* =L*; |
8. ((L1)*· (L2)*)* = (L1+L2)*. |
Пустое подмножество множества А*, как и всякое другое его подмножество, тоже считается языком. Этот язык мы будем называть пустым языком и обозначать символом пустого множества . Очевидно, что для любого языкаLверны равенстваL+=LиL·=. Значит, при всех натуральных значенияхnвыполняетсяn=. Тогда из определения операции итерации получаем* =Λ++2+3+ … +n+ … =Λ.
Заметим также, что Λ* = Λ, поскольку Λn = Λ и Λ + Λ = Λ.
Определение.Пусть имеется алфавит А = {а1, а2, …, аs}. Одноэлементные языки а1, а2, …, аs, а также язык, содержащий только пустое словоΛ- элементарные языки.
45. Регулярные выражения и регулярные языки, теорема Клини.
Определение.Регулярным языком называется такой язык, который можно получить из элементарных языков с помощью конечного числа операций сложения, умножения и итерации.
Чтобы доказать регулярность какого-либо языка, надо записать его в виде так называемого регулярного выражения, т.е. формулы, в которой конечное число раз используются элементарные языки и знаки операций сложения, умножения и итерации. Поскольку количество регулярных выражений счетно, то число различных регулярных языков не более, чем счетно. Всего же имеется континуум языков над фиксированным конечным алфавитом А, т.к. язык – это любое подмножество счетного множества А*. Следовательно, существуют и нерегулярные языки.
Пример.Рассмотрим несколько языков.
Конечный язык L1 = {a, ab, abc} является регулярным языком, т.к. его можно задать равенством L1 = a + ab + abc = a + a·b + a·b·c = a·(Λ + b·(Λ + c)). Последнее полученное выражение является регулярным, поскольку оно содержит только простейшие языки a, b, c и Λ и конечное число знаков операций сложения и умножения. Этот пример показывает, что любое конечное множество слов образует регулярный язык.
Бесконечный язык L2 = {с, cabc, cabcabc, cabcabcabc, …}, порождаемый автоматом из примера 4 §3, является регулярным, т.к. его можно задать разными регулярными выражениями: с·(a·b·с)*, либо (с·a·b)*·с. Этот пример свидетельствует о том, что один и тот же язык можно представить через различные регулярные выражения.
Бесконечный язык L3, состоящий из всех слов конечной длины в алфавите А = {a, b, c}, включая и пустое слово, является регулярным языком, поскольку выполняется равенство L3 = (a + b + с)*.
Бесконечный язык L4 над алфавитом А = {a, b, c}, образованный словами, которые содержат хотя бы одну букву с, регулярен, т.к. он может быть задан равенством L4 = (a + b + с)*· с· (a + b + с)*.
Бесконечный язык L5 над алфавитом А = {0,1}, образованный всеми словами, кроме слов 0 и 11, регулярен, т.к. его можно задать регулярным выражением Λ + 1 + 00 + 01 + 10 + (0 + 1)3 · (0 + 1)*.
Бесконечный язык L6 = {1, 10, 101, 1010, 10100, …}, состоящий из всех начальных отрезков {а1, а1а2, а1а2а3, …} бесконечной последовательности (10100100010…), не является регулярным.
Определение.Пересечением языковLиL´называется язык, который обозначаетсяL∩L´ и состоит из всех слов, принадлежащих одновременно обоим языкамLиL´. Поскольку всякий язык является подмножеством множества А* всех слов конечной длины в некотором фиксированном алфавите А, то пересечение языков – это обычная операция пересечения множеств слов.
Определение.Дополнением языкаLв алфавите А называется язык, который обозначаетсяи состоит из слов множества А*, не принадлежащих языкуL. ЯзыкLи его дополнениене имеют общих слов, а их сумма совпадает с множеством А*. Операция пересечения языков не относится к числу основных, поскольку она может быть выражена через операции сложения и дополнения. Действительно, из закона де Моргана следует, что.
Пример.Пусть исходный языкLсостоит из всех таких слов в алфавите А = {0,1}, которые начинаются с нуля, а оканчиваются двумя единицами. Нетрудно проверить, что этот язык можно задать регулярным выражением 0· (0 + 1)*· 11. Тогда дополнительный к нему языксостоит из всех таких слов в алфавите А, которые начинаются с единицы или оканчиваются любой из трех комбинаций – 00, 01 или 10. Языкможно задать регулярным выражением 1· (0 + 1)* + (0 + 1)*· (0· 0+ 0· 1 + 1· 0).
При фиксированном алфавите А класс регулярных языков над А замкнут относительно всех перечисленных выше операций – сложения, умножения, итерации, пересечения и дополнения. Это означает, что язык, получаемый в результате применения данных операций к регулярным языкам, тоже является регулярным.
Существует тесная связь между регулярными языками и конечными автоматами. Дело в том, что, с одной стороны, любой регулярный язык обязательно распознается некоторым конечным детерминированным автоматом (автоматом Мили). А с другой стороны, автоматы Мили способны распознавать только регулярные языки. Оба эти утверждения сформулированы в основной теореме теории автоматов (теореме Клини).
Теорема Клини.ЯзыкLраспознается конечным детерминированным автоматом тогда и только тогда, когдаL– регулярный язык.