Вопросы/задания: вопросы TXT

Введение в теорию графов.

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. [Представление конечного автомата сетью Петри.]