Экзаменационная программа по дисциплине

Экзаменационная программа по дисциплине

“Теория автоматов”

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. Гонки в комбинационных логических схемах.

28. Понятие гонок в автоматах. Способы борьбы с гонками.

29. Аппаратные способы борьбы с гонками. Введение синхронизации.

30. Аппаратные способы борьбы с гонками. Введение дополнительной памяти.

31. Логические способы борьбы с гонками. Соседнее кодирование.

32. Способы борьбы с гонками. Метод развязывания пар.

33. Определение формального языка.

34. Определение автомата-распознавателя.

35. Эквивалентность автоматов-распознавателей.

36. Минимизация автоматов-распознавателей.

37. Определение недетерминированного автомата-распознавателя.

38. Переход от недетерминированного автомата-распознавателя к детерминированному автомату распознавателю.

Программу составил

доцент., к.т.н. К.И. Свириденков