Лекции 34 часов Экзамен 11 семестр семинары нет Зачет нет лабораторные занятия нет
|
Скачать 36.1 Kb.
|
министерство образования и науки российской федерации Московский физико-технический институт (государственный университет) УТВЕРЖДАЮ Проректор по учебной работе Ю.А. Самарский 8 июня 2011 г. П Р О Г Р А М М Апо курсу ЭФФЕКТИВНЫЕ АЛГОРИТМЫ по направлению 010900 факультет ФУПМ кафедра математических основ управления курс VI семестр 11лекции – 34 часов Экзамен – 11 семестр семинары – нет Зачет – нет лабораторные занятия – нетсамостоятельная работа – 2 часа в неделю ВСЕГО ЧАСОВ – 34Программу составил: д.ф.-м.н. Н.Н. КузюринПрограмма обсуждена на заседании кафедрыматематических основ управления17 мая 2011 годаЗаведующий кафедрой С.А. Гуз 1. Методы построения и анализа эффективных приближенных алгоритмов с гарантированными оценками точности 1.1. Приближенные алгоритмы с гарантированными оценками точности. Анализ точности жадного алгоритма в задачах о покрытии, вершинном покрытии и k-покрытии. 1.2. Приближенные алгоритмы с константной мультипликативной точностью. Модифицированный жадный алгоритм для задачи о рюкзаке и его анализ. Метрическая задача коммивояжера. Приближенные алгоритмы с мультипликативной точностью 2 и 3/2. 1.3. Приближенные алгоритмы максимизации субмодулярных функций на множествах и их приложение в задачах анализа социальных сетей. 1.4. Полностью полиномиальные приближенные схемы для задачи о рюкзаке. 2. Элементы теории сложности 2.1. Различные модели вычислений и сложностные классы по времени и памяти. 2.2. Недетерминированные вычисления и класс NP. 2.3. Лас-Вегас и Монте-Карло вероятностные алгоритмы. Вероятностные сложностные классы RP, BPP, PP. 2.4. РСР теорема и ее применение для оценок порогов неаппроксимируемости. Плохо приближаемые задачи. Несуществование PTAS для задачи MAX-SAT (максимальной выполнимости КНФ). 3. Анализ сложности в среднем 3.1. Полиномиальные в среднем алгоритмы. Полиномиальный в среднем алгоритм для задачи об упаковке. 3.2. Полиномиальный в среднем алгоритм проверки выполнимости КНФ. 3.3. Полиномиальный в среднем алгоритм для задачи о рюкзаке. 3.4. Вычислительно трудные в среднем задачи. 4. Вероятностные методы в построении эффективных алгоритмов 4.1. Модели параллельных вычислений: EREW PRAM, CREW PRAM, CRCW PRAM. Вероятностные методы в построении эффективных параллельных алгоритмов. Вероятностный параллельный алгоритм Луби нахождения максимального по включению независимого множества в графе. 4.2. Вероятностные методы в построении эффективных распределенных алгоритмов. Коммуникационная сложность проверки идентичности двух битовых строк. 4.3. Задача целочисленного программирования и ее линейные релаксации. Вероятностное округление нецелочисленного решения до целочисленного. Приближенные вероятностные алгоритмы для задачи MAX-SAT. 4.4. Вероятностный 0.878-приближенный алгоритм для задачи о максимальном разрезе. Полуопределенное программирование. 4.5. Вероятностный приближенный алгоритм подсчета числа решений некоторых булевых уравнений. 4. Методы дерандомизации 4.1. Метод условных вероятностей, его применение для задачи MAX-SAT. 4.2. Метод малых вероятностных пространств. Литература
Подписано в печать 08.06.11. Формат 60 84  Бумага офсетная.Печать офсетная. Усл. печ. л. 0.25. Уч.-изд. л. 0.25. Тираж 370 экз. Заказ №33 Государственное образовательное учреждение высшего профессионального образования «Московский физико-технический институт (государственный университет)» Отдел оперативной полиграфии Московская обл., г. Долгопрудный, Институтский пер., 9 |
Похожие:
 | Лекции 32 часа Экзамен 8 семестр семинары -нет Зачет с оценкой нет лабораторные занятия нет Некоторые задачи, приводящие к стохастическим аналогам обыкновенных дифференциальных уравнений (стохастические модели, возникающие... | | Лекции 50 часов Экзамен 8 семестр семинары 50 часов Зачет нет лабораторные занятия нет Основная задача оптимального управления. Понятие слабого и сильного минимума. Задача Лагранжа и задача вариационного исчисления.... |
| Лекции 34 часа Экзамен нет семинары 34 часа Зачет с оценкой 3 семестр лабораторные занятия нет Программа обсуждена на заседании кафедры математических основ управления 15 мая 2011 г | | Лекции 64 часа Экзамен 5,6 семестр семинары 64 часа Зачет нет лабораторные занятия нет Постановка задач оптимизации. Локальный и глобальный экстремумы. Классификация экстремальных задач. Примеры |
| Лекции 32 часа Экзамен нет семинары 32 часа Зачет с оценкой 8 семестр лабораторные занятия нет Охватывает более простые, главным образом «одномерные» методы; третье задание относится к анализу существенно многомерных данных | | Лекции 34 часа Экзамен нет семинары 17 часов Зачет с оценкой 7 семестр лабораторные занятия нет Алфавиты, конструктивные объекты, их примеры. Понятие алгоритма, вычислимые функции. Формализация понятия алгоритма: частично-рекурсивные... |
| Лекции 32 часа Экзамен нет семинары нет Зачёт с оценкой 4 семестр лабораторные занятия 32 часа Понятия базы данных, системы баз данных и субд. Требования к субд. Характеристики, функции субд |  | Семинары нет Зачёт нет лабораторные занятия 16 часов самостоятельная работа 2 часа в неделю Программа утверждена на заседании кафедры математических основ управления 18 марта 2005 г |
| Лекции 66 часов Экзамен 5,6 семестр практические занятия 66 часа Диф зачет нет самостоятельная работа 20 часов Постановка задач оптимизации. Локальный и глобальный экстремумы. Классификация экстремальных задач. Примеры | | Лекции 50 часов Экзамен 8 семестр практические занятия 50 часов Диф зачет нет самостоятельная работа 20 часов Основная задача оптимального управления. Понятие слабого и сильного минимума. Задача Лагранжа и задача вариационного исчисления.... |