x, y, z

Теория алгоритмов

Валерий Опойцев

Комментарии: 0
1. Полиномиальные и экспоненциальные алгоритмы
Исходные понятия. Длина описания задачи. Кодирование описания. Число бит информации, необходимых для формулировки задачи. Время решения, или число арифметических операций, требуемых для решения задачи. Водораздел между полиномиальными и переборными алгоритмами.

2. Задачи распознавания и оптимизации
Роль задач распознавания в теории алгоритмов. Сводимость оптимизации к распознаванию — почти всегда. Задача о простоте числа. О труднорешаемости задачи разложения на множители составного числа.

3. P- и NP-задачи
Определение классов P и NP. Совпадает ли P с NP или не совпадает — вопрос на миллион долларов. Феноменальный прорыв в изучении труднорешаемых задач в связи с открытием NP-класса.

4. Машины Тьюринга
Машина Тьюринга как универсальный вычислительный прибор. Контраст примитивности устройства с фантастическими возможностями. Тезис Тьюринга. Задача Тьюринга как универсальная переборная (NP-полная) задача.

5. Опорные комбинаторные задачи
Джентльменский набор комбинаторных задач. Минимальное остовное дерево (МОД). Задача коммивояжера. Задачи: клика, изоморфизм графов, паросочетание, рюкзак, целочисленное линейное программирование (ЦЛП), транспортная задача. В двух словах о непрерывной задаче линейного программирования. Логические задача ВЫПОЛНИМОСТЬ.

6. Теорема Кука
Теорема Кука устанавливает NP-полноту задачи ВЫПОЛНИМОСТЬ, трансформируя проблематику в область задач, которые можно «пощупать».

Лекции читает Опойцев Валерий Иванович, доктор физико-математических наук, профессор МФТИ, гл. н. с. ИПУ РАН.

Дополнительные материалы: oschool.ru
Комментарии: 0