Лекции 34 часов Экзамен 11 семестр семинары нет Зачет нет лабораторные занятия нет



Дата15.01.2013
Размер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. Метод малых вероятностных пространств.


Литература



  1. Гэри М, Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М.: Мир, 1982. (Тема 1).

  2. Motwani R., Raghavan P. Randomized algorithms, Cambrige University Press, 1995.(Тема 3).

  3. Mayr E., Promel H., Steger A. (eds), Lectures on proof verification and approximation algorithms, Springer, 1998.

  4. Кузюрин Н.Н., Фомин С.А. Эффективные алгоритмы, М., МФТИ, 2007, 313 с.


Подписано в печать 08.06.11. Формат 60  84 Бумага офсетная.

Печать офсетная. Усл. печ. л. 0.25. Уч.-изд. л. 0.25. Тираж 370 экз. Заказ №33
Государственное образовательное учреждение

высшего профессионального образования

«Московский физико-технический институт

(государственный университет)»

Отдел оперативной полиграфии

Московская обл., г. Долгопрудный, Институтский пер., 9



Похожие:

Лекции 34 часов Экзамен 11 семестр семинары нет Зачет нет лабораторные занятия нет iconЛекции 32 часа Экзамен 8 семестр семинары -нет Зачет с оценкой нет лабораторные занятия нет
Некоторые задачи, приводящие к стохастическим аналогам обыкновенных дифференциальных уравнений (стохастические модели, возникающие...
Лекции 34 часов Экзамен 11 семестр семинары нет Зачет нет лабораторные занятия нет iconЛекции 50 часов Экзамен 8 семестр семинары 50 часов Зачет нет лабораторные занятия нет
Основная задача оптимального управления. Понятие слабого и сильного минимума. Задача Лагранжа и задача вариационного исчисления....
Лекции 34 часов Экзамен 11 семестр семинары нет Зачет нет лабораторные занятия нет iconЛекции 34 часа Экзамен нет семинары 34 часа Зачет с оценкой 3 семестр лабораторные занятия нет
Программа обсуждена на заседании кафедры математических основ управления 15 мая 2011 г
Лекции 34 часов Экзамен 11 семестр семинары нет Зачет нет лабораторные занятия нет iconЛекции 64 часа Экзамен 5,6 семестр семинары 64 часа Зачет нет лабораторные занятия нет
Постановка задач оптимизации. Локальный и глобальный экстремумы. Классификация экстремальных задач. Примеры
Лекции 34 часов Экзамен 11 семестр семинары нет Зачет нет лабораторные занятия нет iconЛекции 32 часа Экзамен нет семинары 32 часа Зачет с оценкой 8 семестр лабораторные занятия нет
Охватывает более простые, главным образом «одномерные» методы; третье задание относится к анализу существенно многомерных данных
Лекции 34 часов Экзамен 11 семестр семинары нет Зачет нет лабораторные занятия нет iconЛекции 34 часа Экзамен нет семинары 17 часов Зачет с оценкой 7 семестр лабораторные занятия нет
Алфавиты, конструктивные объекты, их примеры. Понятие алгоритма, вычислимые функции. Формализация понятия алгоритма: частично-рекурсивные...
Лекции 34 часов Экзамен 11 семестр семинары нет Зачет нет лабораторные занятия нет iconЛекции 32 часа Экзамен нет семинары нет Зачёт с оценкой 4 семестр лабораторные занятия 32 часа
Понятия базы данных, системы баз данных и субд. Требования к субд. Характеристики, функции субд
Лекции 34 часов Экзамен 11 семестр семинары нет Зачет нет лабораторные занятия нет iconСеминары нет Зачёт нет лабораторные занятия 16 часов самостоятельная работа 2 часа в неделю
Программа утверждена на заседании кафедры математических основ управления 18 марта 2005 г
Лекции 34 часов Экзамен 11 семестр семинары нет Зачет нет лабораторные занятия нет iconЛекции 66 часов Экзамен 5,6 семестр практические занятия 66 часа Диф зачет нет самостоятельная работа 20 часов
Постановка задач оптимизации. Локальный и глобальный экстремумы. Классификация экстремальных задач. Примеры
Лекции 34 часов Экзамен 11 семестр семинары нет Зачет нет лабораторные занятия нет iconЛекции 50 часов Экзамен 8 семестр практические занятия 50 часов Диф зачет нет самостоятельная работа 20 часов
Основная задача оптимального управления. Понятие слабого и сильного минимума. Задача Лагранжа и задача вариационного исчисления....
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org