English version of this page
На главную страницу
Официальный сайт кафедры Математической теории интеллектуальных систем и лабораторий Проблем теоретической кибернетики и Математичеких проблем искусственного интеллекта механико-математического факультета МГУ им. М. В. Ломоносова
На первую страницу сервера Новости Кафедра Сотрудники Учеба Наука Исследования Журнал Культура Канал кафедры МаТИС в Телеграм
 ТДФ Теория дискретных функций – лекции и семинары для студентов 1 курса (II поток)
 Ташкентский филиал Ташкентский филиал МГУ им. М.В. Ломоносова
 Семинары расписание специальных семинаров кафедры МаТИС
 Курсы расписание специальных курсов кафедры, программа курсов
 Практикум cпециальный математический практикум кафедры МаТИС, III курс
 Студенты список студентов кафедры по курсам и группам, расписание занятий, выпускники
 Магистратура информация для поступающих в магистратуру
 Аспирантура информация для аспирантов и поступающих в аспирантуру; списки аспирантов

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

Программа спецкурса "Оптимизация и сложность алгоритмов" (гр. 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 Метод решения задачи о рюкзаке разбиением на подзадачи.

Наверх

   © 2001- г. Кафедра Математической теории интеллектуальных систем, лаборатория ПТК, лаборатория МПИИ Написать вебмастеру   
Последние новости - в телеграм-канале кафедры МаТИС: Канал кафедры МаТИС в Телеграм Rambler's Top100 Рейтинг@Mail.ru