- •3. Алгоритм Дейкстры.
- •4. Метод Форда-Беллмана решения задачи о кратчайшем пути в графе.
- •5. Математическая постановка задачи коммивояжера
- •6. Метод ветвей и границ решения задачи коммивояжера
- •7. Математическая постановка транспортной задачи.
- •9. Модифицированный распределительный метод транспортной задачи
- •8. Распределительный метод.
- •10. Цикломатическое число графа
- •14. Устойчивость, покрытия, паросочетания в графе.
- •15. Продолжение.
- •13. Операции над графами.
- •15. Планарные и плоские графы.
- •16. Эйлеров путь в графе.
- •17. Потоки в сетях. Теорема Форда-Фалкерсона
- •18. Связность графов. Теорема Менгера.
- •19. Раскраска вершин и ребер графа
- •20. Гиперкубы
- •21. Логика высказываний. Логические функции от двух переменных.
- •22. Минимизация булевых функций в классе днф.
- •23. Минимизация булевых функций с помощью карты карно.
- •24. Метод Квайна-Мак-Класки
- •25. Полнота логических функций.
- •26. Минимизация слабоопределнных булевых функций.
- •27. Схемы из функциональных элементов
- •28.Синтез логических схем в произвольном базисе
- •32. Продолжение.
- •29. Разложение Шеннона. Дифференц-ие булевых ф-ий
- •31 Алгоритмический этап проект-я цифрового автомата
- •33. Структурное проектирование автоматов с минимальным объемом внутренней памяти.
- •34. Структурное проектирование автоматов с максимальным объемом внутренней памяти
- •26. Минимизация слабоопределнных булевых функций.
31 Алгоритмический этап проект-я цифрового автомата
П
роизводится
построение системных выходных ф-ий
Y=f(X,
Z+)
и сис-мы ф-ий возбуждения
На этом
этапе заданный автоматный оператор A
оформляется в виде алгоритма, исходя
из уст треб-ий. Поиск опт алг-ма по A
можно представить в виде дерева, каждый
лист которого соответствует опредленному
алг-му, а кол-во таких листов заранее
не известно. Проектирование автоматного
опер-ра заключается в построении
автоматного отображения по словесному
описанию(цель проектирования, назначение
автомата, свойства поведения упр-го
объекта)
Автоматное отображение обычно задается графом переходов (каждая вершина взаимно однозначно соответствует внутр состоянию автомата, если из gi переходит в gj то соотв вершины ui uj соед-ся дугой (ui uj) взвешенной парой векторов (X,Y) по к-м переход и осуществляется При преобразовании неформальной инф-ции в формальную сис-му используется принцип аналогий. Формально мб основан на прим-ии грамматик, в к-х правила подстановки формализуют данные св-ва упр-го объекта. В рез-те применения грамматик порождаются композиции графов переходов, соотв описанию. Часто двухуровневые: 1 ур – графы пер-в, реакция к-х – воздействие на объект, 2 ур – граф пер-в, реакция к-го – возбуждение инициальных вершин графов 1-го уровня Зная опер авт-т и алгоритм, можно составить временную диаграмму функционирования управляющего автомата – алгоритм выполнения операций в терминах управляющих точек – микроопераций. Но вр диаграмма еще не дает апп. отображения , тк 1 знач вх вектора(опр-т вып-ую опер-ию) соотв-т нексколько значений вых вектора(микрокоманд). Необходимо ввести в автомат память, при этом задать заведомо достаточный объем памяти. Тогда совокупность вх вектора и сост-ия памяти однозначно опр-т микрокоманду.
32. Абстрактное проект-ие автоматов. Математической моделью устройства с памятью является абстрактный автомат, который представляет собой совокупность пяти конечных множеств:
где A={a0, a1, .aM} - множество состояний автомата;={Z1, Z2, .ZF} - множество входных сигналов;={W1, W2, .WC} - множество выходных сигналов; сигма- функция переходов, обеспечивающая выработку последующего состояния as автомата в зависимости от существующего состояния aM и входного воздействия Zf; лямбда - функция выходов, обеспечивающая выработку выходного сигнала автомата в зависимости от его состояния aM и входного сигнала Zf. Абстрактный автомат имеет один входной и один выходной каналы, и каждой букве входного алфавита Z ставит в соответствие букву или слово выходного алфавита W. Автомат называется синхронным, если он описывается a(t) и W(t) как автомат Мили. Автомат называется асинхронным, если его функция переходов описывается как у автомата Мура. В синхронном автомате осуществляется синхронизация внешних и внутренних сигналов, в то время как в асинхронном этого нет, и для представления последовательности одинаковых букв вводится какая-либо разделяющая их буква, не несущая информации.
