Вопросык экзаменам. Вопросы по теории алгоритмов.

1. Машина Тьюринга, теорема Кука. NP-полные задачи. КлассNPи классP.

2. Задача коммивояжёра. Приложение метода ветвей и границ.

3. Динамическое программирование и метод сетевого планирования. Ранние и поздние времена, запасы времени на работу.

4. Алгоритм Карацубы. Сложность алгоритма Карацубы. Масштабное соотношение. (Можно блок алгоритмов Тома).

5. Алгоритм сортировки слиянием и быстрое преобразование Фурье.

6. Схема Горнера, быстрое преобразование Фурье, битовое преобразование Фурье, обратные матрицы преобразований Фурье для этих случаев. Арифметика комплексных чисел, их умножение и деление, матричное представление.

7. Модулярная арифметика, Быстрое возведение в степень. Алгоритм Масси-Омуры, алгоритм RSA.

8. Алгоритм Квадратичного решета для факторизации чисел и взлома RSA.

9. Алгоритм Цермело-Куна.

10. Алгоритм Евклида обращения чисел по заданному модулю.

11. Алгоритм Дейкстры.

12. Алгоритм Форда-Фалкерсона поиска максимального потока в сети..

13. Алгоритм быстрого перемножения матриц Штрассена.

14. Основные идеи перемножения полиномов с помощью преобразования Фурье.

15. Жадные алгоритмы построения минимального остовного дерева.

16. Алгоритм транзитивного замыкания графа (алгоритм Уоршалла).

17. Нечёткая логика. Формулы для нечёткой коньюнкции (и), дизьюнкции (или) и отрицания. Анализ иерархий элементы теории нейронных сетей. Сеть Кохонена, сеть Хопфилда, Персептрон (выразимость).

18. Логические функции не более чем двух переменных, существенность переменных, упрощение релейно-контактных схем,

19. Дизьюнктивная, коньюнктивная и полиномиальная формы, Теорема Поста, классы Поста, число функций (мощность) классов Поста, (часто встречающиеся) полные системы функций, Шефферовы функции.

20. Задача о раскрасках. Вычисление хроматического полинома.