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

Программа спецкурса "Оптимизация и сложность алгоритмов" (гр. 431, 432, осенний семестр)

1 Постановка основных математических задач в теории сложности алгоритмов и их значение для обработки экономической информации.

Роль оптимизации и сложности алгоритмов в разработке программных продуктов искусственного интеллекта.

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

2.1 Машины произвольного доступа к памяти, машины Тьюринга и их модификации.

2.2 Взаимное моделирование моделей вычислений.

3 Меры сложности алгоритмов.

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

3.2 Существование сложных задач.

3.3 Теорема Блюма об ускорении.

4 Труднорешаемость задач.

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

4.2 Полиномиальная сводимость задач.

4.3 NP-полные задачи. Теорема Кука о NP-полноте проблемы выполнимости формул алгебры высказываний.

4.4 Основные NP-полные задачи.

4.5 Задачи с числовыми параметрами. Задача о рюкзаке. Сильная NP-полнота.

4.6 Бесконечная серия NP-полных задач Шиффера.

5 Методы построения быстрых алгоритмов.

5.1 Структуры данных.

5.2 Рекурсия. Типы полиномиальных оценок сложности рекурсивных алгоритмов.

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

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

5.5 Быстрые алгоритмы на графах. Поиск в глубину и в ширину. Кратчайшие пути. Минимальные остовные деревья. Алгоритмы для задачи о паросочетании.

Потоки в сетях и алгоритмы нахождения максимального потока.

6 Методы решения труднорешаемых задач.

6.1 Метод ограничения параметров.

6.2 Метод приближенных алгоритмов. Существование приближенных алгоритмов с различными мерами уклонений от точных алгоритмов.

6.3 Доказательства не существования приближенных алгоритмов с некоторыми мерами уклонения.

6.4 Политика жадности. Примеры оптимальности жадных алгоритмов. Приближенные алгоритмы для задач об упаковке, о коммивояжере, о вершинном покрытии. Матроиды. Характеризация случаев оптимальности жадных алгоритмов. Теорема Радо- Эдмонса.

7 Оптимизация алгоритмов перебора.

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

7.2 Метод согласования координат при переборе.

8 Методы получения нижних оценок сложности

8.1 Нижние оценки сложности в наследственных алгоритмах, использующих отношение частичной упорядоченности. Теорема Дилуорса. Лемма Анселя для единичного куба..

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

8.2 Нижние оценки вычисления на машине Тьюринга. Проблема симметрии слов. Теорема Барздинь и доказательство оптимальности.

9 Заключение. Основные направления исследований в области оценок сложности алгоритмов. Приложения к проблемам защиты банковской информации и электронной коммерции.

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

Билет ?1 1 Принципы комбинаторики. Числа инъекций, сюръекций и биекций конечных множеств.
2 Системы различных представителей. Теорема Холла.

Билет ?2
1 Числа Стирлинга-2.
2 Ортогональные латинские квадраты. Теорема Манна.

Билет ?3
1 Числа Белла.
2 Конечные проективные плоскости и их существование.

Билет ?4
1 Числа Стирлинга-1.
2 Число систем различных представителей семейства множеств.

Билет ?5
1 Числа Каталана
2 Матроиды и их свойства.

Билет ?6
1 Числа Дилуорса
2 Теорема Радо-Эдмонса о матроидах.

Билет ?7
1 Быстрое преобразование Фурье
2 Перманенты и их свойства.

Билет ?8
1 Подстановки булевского куба. Критерий Хаффмана.
2 Метод включения-исключения. Формула Райзера для перманентов

Билет ?9
1 Числа Гаусса
2 Сложность умножения матриц

Билет ?10
1 Числа Шпернера.
2 Сложность сортировки чисел

Билет ?11
1 Число булевских функций без фиктивных переменных.
2 Сложность умножения битовых чисел

Билет ?12
1 Число подстановок без единичных циклов.
2 Сложность умножения многочленов

Билет ?13
1 Число булевских функций с заданным значением коэффициента Фурье
2 Формула Райзера для перманентов.

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

Билет ?15
1 Лемма Бернсайда.
2 Цикловая структура прямого произведения подстановок.

Билет ?16
1 Теорема Шеннона о числе классов эквивалентности булевских функций
2 Матрицы Адамара и их существование.

Билет ?17
1 Циклы прямого произведения подстановок.
2 Коды Адамара и их корректирующие свойства.

Билет ?18
1 Типы полиномиальных оценок сложности для рекурсивных алгоритмов.
2 Метод склейки-расклейки циклов для подстановок регистров сдвига.

Билет ?19
1 Классы сложности Р и NP и их связь.
2 Разностные характеристики подстановок. Теорема Холла.

Билет ?20
1 Класс сложности NPH. Теорема Кука.
2 Критерий БПИ для автоматов.

Билет ?21
1 Задача Клика и ее NP-полнота.
2 Критерий регулярности для автоматов.

Билет ?22
1 Задача о рюкзаке и ее NP-полнота
2 Латинские квадраты над булевским кубом.

Билет ? 23
1 Графы де Брейна. Теорема де Брейна о числе эйлеровых циклов.
2 Число типов булевских функций в группе отрицаний переменных.

Билет ? 24
1 Метод рекуррентных соотношений. Решения линейных соотношений
2 Декомпозиция дважды стохастических матриц. Теорема Биркгофа.

Билет ?25
1 Метод производящих функций. Числа Каталана.
2 Задача выполнимости F-формул. Классы Шиффера. Теорема Шеффера.

Билет ?26
1 Разностные характеристики подстановок регистров сдвига.
2 Метод решения задачи о рюкзаке разбиением на подзадачи.

Наверх