Контрольная работа

Контрольная работа состоит из двух заданий (вопросов). Номера вопросов для заданий определяются по таблице:

Ответы на вопросы заданий должны быть развернутыми. Обязательно указание на источники информации.

Вопросы для контрольной работы

1. Формальные языки и грамматики. Основные понятия.
2. Порождающая грамматика. Классификация по Хомскому.
3. Контекстно-свободная грамматика. Основные понятия и определения.
4. Нормальные формы Хомского.
5. Конечные автоматы. Основные определения, форма представления.
6. Нисходящие методы обработки языков. S - грамматики.
7. Нисходящие методы обработки языков. Q - грамматики.
8. Восходящие методы обработки языков.
9. Вычислимые функции, разрешимые и перечислимые множества.
10. Определение машины Тьюринга – Поста.
11. Вычислимые по Тьюрингу функции.
12. Алгоритмически разрешимые и неразрешимые проблемы.
13. Нормальные алгоритмы Маркова.
14. Рекурсивные функции. Тезис Чёрча.
15. Эквивалентность моделей алгоритмов.
16. Частично рекурсивные функции.
17. Рекурсивно перечислимые отношения.
18. Языки. Иерархия языков по Хомскому.
19. Основные меры сложности вычисления.
20. Определение и связь основных характеристик сложности алгоритма.