53. Операции над логическими автоматами: суперпозиция и введение обратной связи.
Пусть имеется два автомата, один из которых вычисляет автоматную функцию f1, а другой – функциюf2. Если выход первого автомата подключить ко входу второго, то полученный автомат будет вычислятьсуперпозициюf2(f1). Очевидно,суперпозиция автоматных функцийсама является автоматной функцией. Её каноническую систему можно получить из канонических систем исходных функций.
Пример 1.Автоматные функцииf1иf2заданы соответственно каноническими системами
Требуется получить каноническую систему и нарисовать схему из функциональных элементов и элементов единичной задержки для автомата, вычисляющего суперпозицию f2( f1).
Схемы автоматов, вычисляющих функции f1иf2, приведены на рисунке. В первой схеме используется функциональные элементы инвертор и конъюнктор, а во второй – дизъюнктор. Кроме того, прямоугольником на схемах обозначены элементы единичной задержки. Надписи около их входов и выходов указывают, что в началеt-го такта им на вход поступает сигналq(t), «выталкивая» при этом на выход сигналq(t – 1).
На нижнем рисунке представлена схема автомата, вычисляющего суперпозицию f2(f1). Он имеет два входа и один выход и получается в результате последовательного соединения исходных автоматов.
Каноническая система полученного автомата имеет вид
Она получается в результате объединения двух исходных систем. При этом из первой системы удалено первое уравнение, aего правая часть подставлена вместо х(t) во вторуюcистему. Кроме того, полученная каноническая система содержит две функции переходов.
Определение.Говорят, что автоматная функцияfзависит с запаздыванием от аргумента х1, если для любого набора изnвходных последовательностейи любого момента времениtэлементy(t) выходной последовательности= fне зависит от элементаx1(t) входной последовательности.
Если имеется автомат, вычисляющий сразу т автоматных функций f1,f2,…,fт, каждая из которых зависит от п аргументов х1, х2,…, хn, и при этомfjзависит от хkс запаздыванием, то в этом автомате можноввести обратную связьпо паре переменных (fj, хk). Операция введения обратной в данном случае заключается в том, что сигнал сj-го выхода направляется наk-й вход. В результате получается автомат, вычисляющий (m– 1) автоматных функций от (n– 1) аргументов.
Пример.Рассмотрим автомат, схема которого изображена на рисунке. Он вычисляет две функцииf1иf2от двух аргументов х1и х2. Убедившись, чтоf2зависит от х1с запаздыванием, требуется ввести обратную связь по паре переменных (f2, х1) и написать каноническую систему полученного автомата.
Прежде всего запишем каноническую систему исходного автомата. Она имеет вид
Поскольку переменная х1(t) является фиктивной для булевой функции у2(t), то автоматная функция f2 зависит от х1 с запаздыванием. Следовательно, можно ввести обратную связь по паре переменных ( f2, х1). В итоге получим автомат с одним входом и одним выходом. Поскольку в ней присутствуют два элемента единичной задержки, то полученный автомат имеет не более четырех состояний. Его каноническая система имеет вид
Она получается из исходной канонической системы, если в ней всюду х1(t) заменить правой частью уравнения для у2(t), а само это уравнение удалить из системы.
- 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. Операции над логическими автоматами: суперпозиция и введение обратной связи.