Вопросы к зачету по курсу �Информатика�

110–113 гр., весенний семестр 2003 г.

1. Праволинейные грамматики; теорема о приведении к нормальной форме.

2. Теорема об эквивалентности детерминированных и недетерминированных конечных автоматов.

3. Конечные автоматы, регулярные выражения и праволинейные грамматики: теорема об эквивалентности.

4. Лемма о разрастании для регулярных языков; языки, не являющиеся регулярными.

5. Замкнутость класса регулярных языков относительно теоретико-множественных операций. Разрешимые проблемы, связанные с регулярными языками.

6. Бесконтекстные грамматики; теорема о приведении к нормальной форме.

7. Автоматы с магазинной памятью; построение автомата, принимающего данный бесконтекстый язык.

8. Лемма о разрастании для бесконтекстных языков. Разрешимые алгоритмические проблемы, связанные с бесконтекстными языками.

9. Контекстно-зависимые языки.

10. Рекурсивно-перечислимые языки. Существование рекурсивно-перечислимого, но не рекурсивного языка.

11. Классы P и NP. Сводимости и полнота.

12. Алгоритмы, использующие случайные числа. Вероятностный алгоритм, распознающий составные числа.

13. Приближенный алгоритм для задачи о рюкзаке.

14. Приближенные алгоритмы для задачи о коммивояжере.

15. Приближенный алгоритм для задачи о покрытии множествами.

16. Приближенный алгоритм для задачи о кратчайшей общей надпоследовательности.

17. Алгоритм для задачи о поиске подстроки.

18. Дискретное преобразование Фурье (ДПФ). Теорема об отрицательно обернутой свертке. Вычисление ДПФ.

19. Алгоритм Шёнхаге-Штрассенa (без вычисления ДПФ, но с “простым” рекурсивным алгоритмом).

20. Параллельный алгоритм для задачи о достижимости в графе.

21. Параллельный алгоритм, находящий максимальное по включению независимое множество.