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

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. Параллельный алгоритм, находящий максимальное по включению независимое множество.