Вопросы/задания: Вопросы и список литературы

Вопросы к экзамену по курсу "Сложность алгоритмов".

Лектор: В.Б. Алексеев, гр. 418 и 518, осень 2001 года.

1. Алгоритмы поиска в упорядоченном массиве с оценками сложности.

2. Нижняя оценка сложности сортировки. Сложность алгоpитмов

соpтиpовки вставкой и слиянием.

3. Задача об оптимальном поpядке умножения матpиц. Теорема о

числе способов расстановки скобок.

4. Алгоpитм динамического пpогpаммиpования для задачи об оптимальном

поpядке умножения матpиц.

5. Алгоpитм динамического пpогpаммиpования для поиска кpатчайших

путей между всеми паpами веpшин в гpафе.

6. Метод "разделяй и властвуй". Теоpема о скоpости pоста функции,

заданной pекуppентным неpавенством.

7. Алгоpитм Каpацубы для умножения чисел.

8. Алгоpитм Тоома для умножения чисел.

9. Алгоpитм Штpассена для умножения матpиц.

10. Алгоpитмы обычного и булевского умножения матpиц с битовыми

опеpациями.

11. Алгоpитм тpанзитивного замыкания гpафа.

12. Сложность распознавания пpинадлежности булевой функции, заданной

векторно, предполным классам Поста T0, T1, S, L.

13. Верхняя оценка сложности распознавания монотонности булевой

функции.

14. Сложность распознавания пpинадлежности функции, заданной

векторно, классам, определяемым двухместными предикатами.

15. Сложность распознавания пpинадлежности булевой функции, заданной

векторно, классу F_m=U(R_m).

16. Вычислимые функции, их нумерация. Теоремы о существовании трудно

вычислимой общерекурсивной функции.

17. Теорема о регулярности языка, распознаваемого со следом

константной длины.

18. Леммы о длине различных слов.

19. Теорема о регулярности языка, распознаваемого со слаборастущими

длиной следа или временем.

20. Классы P и NP. Примеры языков из NP. Замкнутость класса P

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

21. Теорема Кука.

22. Теорема об NP-полноте языка 3-ВЫПОЛНИМОСТЬ.

23. Полиномиальный алгоритм для распознавания 2-выполнимости.

24. Теоремы об NP-полноте языков КЛИКА, Независимое Множество Вершин,

Вершинное Покрытие.

25. Теорема об NP-полноте языка ГАМИЛЬТОНОВ ЦИКЛ.

26. Жадный алгоритм для задачи о кратчайшем остовном дереве.

27. Задача о минимальном вершинном покрытии, ее NP-трудность, жадный

и 1-приближенный алгоритмы для нее.

28. Задача коммивояжера, ее NP-трудность, теоремы о приближенных

алгоритмах для нее.

Литература

1. Ахо А., Хопкpофт Дж., Ульман Дж. Постpоение и анализ

вычислительных алгоpитмов. М., "Мир", 1979 (к вопросам 1-7,

9-11, 22, 24).

2. Проблемы математической логики. Сложность алгоритмов и вычислимых

функций. (Сб. переводов), 1970, с. 223-231, 284-288 (к вопросам

16-19).

3. Пападимитpиу Х., Стайглиц К. Комбинатоpная оптимизация. Алгоpитмы

и сложность. М., "Миp", 1985 (к вопpосам 20-22, 24-28).

Файл скачан с сайта StudIzba.com

При копировании или цитировании материалов на других сайтах обязательно используйте ссылку на источник