/Materials Пн, 24.07.2017, 19:39

Сайт методики довузовского обучения программированию
и проектной деятельности в информатике


Главная страница, Контакты, RSS
 
> Меню сайта

> Разделы новостей
Семинар [37]
Семинар по системному и прикладному программированию
Etc [14]
Разное
Конференция [16]
Открытая конференция исследовательских и проектных работ

> Архив новостей

> Партнеры

> Поиск

> Статистика

Главная » 2009 » Апрель » 14 » Введение в теорию алгоритмической сложности (3 семинара)
Введение в теорию алгоритмической сложности (3 семинара)
Евгений Молчанов
Московский физико-технический институт (Физтех), 6 курс

Лекция "P"
вторник, 14 апреля, 15:40, каб. 25

Алгоритм сортировки пузырьком имеет сложность O(n2).

На лекции будут рассмотрены:
  • Понятие длины входных и выходных данных алгоритма.
  • Понятие сложности алгоритма.
  • Символы O, W.
  • Класс P-алгоритмов, время работы которых не превосходит полинома от длины входных данных.
  • Будет описано преимущество алгоритмов из этого класса перед остальными алгоритмами.


Лекция "NP"
вторник, 21 апреля, 15:40, каб. 25

Число (232 + 1) является составным, так как оно делится на 641.

На лекции будут рассмотрены:
  • Понятие свидетелей решения - "подсказок", с помощью которых можно значительно ускорить время решения задачи.
  • Класс NP-задач, в которых с помощью "подсказок" можно решить задачу за время, не превосходящее полинома от длины входных данных (т.е. "проверить ответ" за полиномиальное время).
  • Неразрешенная проблема равенства классов P и NP.
  • Последствия решения проблемы как в случае P != NP, так и в случае P = NP.

Лекция "NPC"
вторник, 28 апреля, 15:40, каб. 25

Если какую-то НП-полную задачу можно решить за полиномиальное время, то любую задачу из класса НП также можно решить за полиномиальное время.

На лекции будут рассмотрены:
  • Понятие полиномиальной сводимости задач.
  • Класс NPС (NP-полные) - задачи, к которым можно свести любую задачу из класса NP.
  • Примеры NP-полных задач (задача о выполнимости булевых формул, задача коммивояжера, задача нахождения кратчайшего пути в игре "15", задачи возникшие из игр "сапер", "тетрис").

Также на лекциях будет кратко рассказано про:

  • Приближенные алгоритмы
  • Вероятностные алгоритмы


В настоящее время семинары с участием сотруднков МФТИ не проводятся из-за регулярных срывов их организации администрацией лицея "Вторая школа".

Категория: Семинар | Просмотров: 2270 | Добавил: ded32
> Инструменты

Orphus


> О рекламе на сайте

Сайт рас­по­ло­жен на бес­плат­ном хос­тин­ге, пра­ви­ла ко­то­ро­го за­пре­ща­ют вы­ре­зать ре­к­ла­му, встав­ляе­мую авто­ма­ти­чес­ки. Сайт не име­ет ни­ка­ко­го отно­ше­ния к этой ре­кла­ме.


> Загрузить

> Основные материалы

> Примеры проектов



Copyright (c) И.Р. Дединский, 2006-2017
Никакая часть материалов данного сайта или его подразделов не может быть прямо или косвенно процитирована или упомянута без действующей активной ссылки на данный сайт
...

Хостинг от uCoz

MasterHost Orphus