Город: Тест Санкт-Петербург Новосибирск Казань Язык: Русский English

Алгоритмы для NP-трудных задач
Казань / осень 2016, посмотреть все семестры

Запишитесь на курс, чтобы получать уведомления и иметь возможность сдавать домашние задания. Для записи требуется регистрация на сайте.
Перейти к регистрации Войти

Алгоритмы для NP-трудных задач

Одним из центральных открытых вопросов компьютерных наук является вопрос о равенстве классов P и NP. Неформально его можно сформулировать так: «Верно ли, что для каждой алгоритмической задачи, решение которой можно быстро проверить, можно быстро найти решение?» Ответа мы до сих пор не знаем. NP-трудные задачи — в некотором смысле самые сложные из алгоритмических задач. Классический пример — задача 3-раскраски графа, в которой вершины данного неориентированного графа нужно покрасить так, чтобы концы всех рёбер были разного цвета. Действительно, проверить, является ли заданная раскраска правильной, легко. В то же время мы не знаем алгоритмов, которые бы за полиномиальное время проверяли, есть ли у данного графа такая раскраска. Таких задач очень много, они часто возникают на практике. Мы дадим обзор алгоритмов для таких задач. Более конкретно,

  • узнаем, на основании чего некоторые задачи из класса NP считаются самыми трудными;
  • узнаем формальную постановку вопроса о равенстве классов P и NP — вопроса, за решение которого положен приз в один миллион долларов;
  • рассмотрим несколько техник решения NP-трудных задач на практике;
  • воспользуемся SAT-солвером для того, чтобы очень быстро решить какую-нибудь комбинаторную задачу;
  • увидим несколько примеров приближённых алгоритмов, которые быстро находят решение для трудной оптимизационной задачи, гарантированно не сильно отличающееся от оптимального;
  • узнаем несколько красивых идей (как классических, так и совсем недавних), позволяющих избегать полного перебора в решении NP-трудных задач.

Отдельное внимание будет уделено открытым задачам данной области.

Курс предполагает знакомство слушателей лишь с базовыми алгоритмическими идеями (О-нотация, сортировки, базовые алгоритмы на графах, динамическое программирование). Проверить и освежить свои знания базовых алгоритмов можно в данном бесплатном онлайн-курсе.

Дата и время Занятие Место Материалы
13 сентября
10:10–11:30
Задачи поиска, Лекция 2-й учебный корпус К(П)ФУ, ауд. 1011 слайды
13 сентября
11:40–13:00
Сведения, Лекция 2-й учебный корпус К(П)ФУ, ауд. 209 слайды
14 сентября
11:50–13:05
Частные случаи, Лекция 2-й учебный корпус К(П)ФУ, ауд. 209 слайды
14 сентября
13:20–14:40
Точные алгоритмы, Лекция 2-й учебный корпус К(П)ФУ, ауд. 209 слайды
15 сентября
08:30–11:40
Приближенные алгоритмы, Лекция 2-й учебный корпус К(П)ФУ, ауд. 209 Нет