Перейти к полному списку специальных курсов кафедры

Введение в теорию интеллектуальных систем (обязательный курс гр. 431, 432)

Учебное пособие по этому курсу в формате pdf доступно по этой ссылке

1. Функции сложности алгоритмов и их свойства.

2. Модели вычислений, используемые для оценки сложности алгоритмов и вычислений.

3. Нумерация алгоритмов и существование сложно решаемых задач.

4. Классы P и NP и их свойства.

5. Полиномиальная сводимость задач. NP-полные задачи.

6. NP-полнота задачи КЛИКА.

7. NP-полнота задачи 3-ВЫП.

8. Задача о рюкзаке. Сильная NP-полнота.

9. Сложность выполнимости биюнктивных формул.

10. Метод рекурсии. Типы полиномиальных оценок сложности рекурсивных алгоритмов.

11. Рекурсивный алгоритм для задач сортировки массивов чисел.

12. Рекурсивный алгоритм умножения чисел.

13. Рекурсивный алгоритм умножения матриц.

14. Быстрое преобразование Фурье и его применения. Сложность умножения многочленов.

15. Задачи о назначениях и о системах различных представителей и их связь.

16. Перманенты и их свойства.

17. Условия равенства нулю перманента.

18. Перебор элементов множеств с использованием разбиений на классы эквивалентности. Числа Белла. Числа Стирлинга-2.

19. Перебор элементов множеств с использованием отношения частичной упорядоченности.

20. Разложение частично упорядоченного множества на цепи. Теорема Дилуорса.

21. Лемма Анселя для единичного куба.

22. Сложность оптимального алгоритма выделения монотонной функции.

23. Минимизация среднего числа опробований с учетом вероятности истинного варианта и сложности его опробования.

24. Конечные автоматы со свойством БПИ. Критерий выполнимости БПИ для автомата.

25. Метод согласования для перебора множеств состояний в суперпозиции автоматов со свойством БПИ.

26. Приближенные алгоритмы и меры их точности. Задача об упаковке в контейнеры.

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

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

29. Доказательства не существования приближенных алгоритмов с некоторыми мерами уклонения.(задача о рюкзаке, о максимальном независимом множестве).

30. Определение матроида. Характеризация случаев оптимальности жадных алгоритмов. (Теорема Радо- Эдмонса.)

Литература

1. Пападимитриу Х., Стайглиц Х. Комбинаторная оптимизация. М 1985

2. Ахо А., Хопкрофт Д. Ульман Д. Построение и анализ вычислительных алгоритмов. М 1979

3. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.1982

4. Носов В.А. Основы теории алгоритмов и анализа их сложности. М.1992

5. Конспект лекций 2004 года.

Экзаменационные билеты 2008-2009 года
Составил В.А.Носов
 

Билет №1
1 Функции сложности алгоритмов и их свойства.
2 Теорема Дилуорса и ее применения.

Билет №2
1 Машинные модели алгоритмов. Тезис Тьюринга
2 Задача от рюкзаке и ее применения.

Билет №3
1 Нумерация алгоритмов. Универсальная функция.
2 Задача классификации. Числа Белла и Стирлинга-2 и их вычисление.

Билет №4
1 Алгоритмически неразрешимые задачи. Проблема останова.
2 Задача о назначении. Критерий существования назначения

Билет №5
1 Задача о назначении. Подсчет числа допустимых назначений.
2 Оценки сложности в алгоритмах, использующих рекурсию.

Билет №6
1 Условие равенства нулю перманента.
2 Существование сложно вычислимых функций.

Билет №7
1 Представление булевских функций рядом Фурье.
2 Лемма Бернсайда и ее применение.

Билет №8
1 Быстрое преобразование Фурье для булевских функций.
2 Жадный алгоритм для задачи об упаковке в контейнеры.

Билет №9
1 Классы Р и NР и их взаимосвязь.
2 Задача о расписании работ. Алгоритм Джонсона для двух станков.

Билет №10
1 NP-полные задачи. Задача F–выполнимости.
2 Задача о разложении единичного куба на цепи.

Билет №11
1 Рекурсивный алгоритм сортировки и его сложность
2 Задача о рюкзаке и ее решение методом разбиения.

Билет №12
1 Рекурсивный алгоритм умножения битовых чисел.
2 Приближенные алгоритмы для NP-полных задач.

Билет №13
1 Типы полиномиальных оценок в рекурсивных алгоритмах.
2 Перманенты матриц и их вычисление.

Билет №14
1 Рекурсивный алгоритм умножения матриц.
2 Перебор элементов множества с использованием частичного порядка.

Билет №15
1 Вычислимые функции и их представление.
2 Алгоритмически неразрешимые задачи. Проблема останова.

Билет №16
1 Системы различных представителей семейств множеств. Теорема Холла.
2 Нумерация вычислимых функций. Универсальная функция.

Билет №17
1 Задача 2-выполнимости и 3-выполнимости КНФ.
2 Теорема Шеннона о числе классов эквивалентности булевских функций.

Билет №18
1 Существование сложно разрешимых задач.
2 Задача о назначении и число допустимых назначений.

Билет №19
1 Метод резолюций для булевских формул.
2 Матроиды и их свойства. Теорема об оптимальности жадного алгоритма.

Билет №20
1 Сильная NP-полнота. Задача о целочисленном рюкзаке
2 Теорема Дилуорса и ее применение.

Билет №21
1 Приближенные алгоритмы и их оценивание. Задача об упаковке в контейнеры.
2 Вычислимые функции и их представление. Тезис Черча.

Билет №22
1 Политика жадности. Задача о минимальном остовном дереве.
2 Метод разбиения решения задачи о рюкзаке.

Билет №23
1 Приближенный алгоритма для задачи о коммивояжере.
2 Быстрое преобразование Фурье для многочленов.

Билет №24
1 Функции сложности алгоритмов и их свойства.
2 Задача о назначении.

Билет №25
1 Автоматы без потери информации.
2 Коэффициенты Фурье булевских функций и их вычисление.

Билет №26
1 Политика жадности в задаче коммивояжера.
2 Типы полиномиальных оценок в рекурсивных алгоритмах.

 

Наверх