Кузюрин Н.Н., Фомин С.А. - Сложность комбинаторных алгоритмов. Курс лекций
Категория: Программирование | автор: 19Anton98 | Просмотров: +286
Понятие алгоритма в математике используется давно, но различные его формализации были предложены только в середине 30-х годов прошлого столетия, когда и стала складываться теория алгоритмов. Классическая теория алгоритмов вообще не интересуется сложностными аспектами (временем решения задач на реальных вычислителях). В рамках классической теории алгоритмов, ставятся и решаются задачи о разрешимости различных задач, однако вычислительная сложность полученных решений принципиально не исследуется. Однако с практической точки зрения, может не быть никакой разницы между неразрешимой задачей и задачей, решаемой за время ?(exp(n)), где n — длина входа. Таким образом реализации алгоритмов на реальных вычислитель- ных машинах обязательно требуют анализа сложности их выполнения. Анализом задач с точки зрения вычислительной сложности занимается раздел теории алгоритмов — теория сложности вычислений, активно развивающийся с 50х годов — с момента создания вычислительной техники. Теория сложности вычислений занимает промежуточное положение между строгой математикой и реальным программированием. Для математика это в первую очередь математическая теория, строящаяся на основе фундаментальных понятий полиномиальной вычислимости и полиномиальной сводимости. Для программиста-практика — это набор общих методов, парадигм и конструкций, позволяющий в ряде случаев существенно минимизировать прямолинейный перебор вариантов, а в ряде случаев — показать, что эта задача в рассматриваемой постановке скорее всего неразрешима (и, следовательно, следует искать более реалистичные постановки).
Содержание
Оглавление
1 Элементы теории сложности 4
1.1 Несложно о сложности. Примеры алгоритмов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.1 Примеры задач на натуральных числах. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.2 Приближенные алгоритмы. Многопроцессорные расписания . . . . . . . . . . . . . . . . . . . . . 8
1.1.3 Примеры задач на графах. Кратчайшие пути и задача коммивояжера. . . . . . . . . . . . . . . . . 8
1.1.4 Сортировка слиянием . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.1.5 Быстрая сортировка. Анализ в среднем и вероятностная версия. . . . . . . . . . . . . . . . . . . . 17
1.2 Формально об алгоритмах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.2.1 Машины с произвольным доступом (RAM) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.2.2 Машины Тьюринга и вычислимость . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.3 Сложность алгоритмов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
1.3.1 Сложность в худшем случае (Worst Case Complexity) . . . . . . . . . . . . . . . . . . . . . . . . . 36
1.3.2 Полиномиальные алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
1.3.3 Полиномиальность и эффективность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
1.3.4 Эффективность и классы DTIME, DSPACE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
1.3.5 Полиномиальные сводимости и NP-полнота . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
1.3.6 Сводимость по Куку . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
1.3.7 Недетерминированные алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
1.3.8 Сводимость по Карпу . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
1.4 Вероятностные вычисления . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
1.4.1 Классы RP и coRP. Распознавание с односторонней ошибкой. . . . . . . . . . . . . . . . . . . . . 49
1.4.2 Класс BPP. Эффективное распознавание с двухсторонней ошибкой. . . . . . . . . . . . . . . . . . 51
1.4.3 Класс PP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
1.4.4 Класс ZPP. Вероятностное распознавание без ошибок. . . . . . . . . . . . . . . . . . . . . . . . . 54
1.5 Вероятностно проверяемые доказательства . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
1.5.1 PCP и неаппроксимируемость . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
1.6 Схемы и схемная сложность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
1.7 Коммуникационная сложность. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
1.8 Диаграмма классов сложности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
2 Приближенные алгоритмы с гарантированными оценками точности 67
2.1 Приближенные алгоритмы с фиксированными оценками точности . . . . . . . . . . . . . . . . . . . . . . 67
2.1.1 Жадный алгоритм в задаче о покрытии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
2.1.2 Приближенные алгоритмы для задачи покрытия с минимальной суммой . . . . . . . . . . . . . . 69
2.1.3 Жадный алгоритм для задачи о рюкзаке . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
2.1.4 Алгоритм Кристофидеса для метрической задачи коммивояжера . . . . . . . . . . . . . . . . . . . 73
2.2 Приближенные алгоритмы с выбираемыми оценками точности . . . . . . . . . . . . . . . . . . . . . . . . 79
2.2.1 Динамическое программирование для задачи о рюкзаке . . . . . . . . . . . . . . . . . . . . . . . . 79
2.2.2 Полностью полиномиальная приближенная схема для задачи о рюкзаке . . . . . . . . . . . . . . 82
3 Вероятностные алгоритмы и вероятностный анализ. 88
3.1 Вероятностный анализ детерминированных алгоритмов . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
3.1.1 Задача упаковки. Анализ сложности в среднем. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
3.1.2 Точность жадного алгоритма для почти всех исходных данных . . . . . . . . . . . . . . . . . . . . 92
3.1.3 Полиномиальный в среднем алгоритм для задачи о рюкзаке . . . . . . . . . . . . . . . . . . . . . 94
3.2 Вероятностные алгоритмы. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
3.2.1 Алгоритм Фрейвалда . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
2
3.2.2 Вероятностные методы в перечислительных алгоритмах. Подсчет числа выполняющих наборов
для ДНФ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
3.2.3 Вероятностный алгоритм Луби нахождения максимального по включению независимого множе-
ства в графе . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
3.3 Вероятностные методы в распределенных вычислениях . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
3.3.1 Протокол византийского соглашения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
3.4 Вероятностное округление и дерандомизация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
3.4.1 Вероятностное округление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
3.4.2 Приближенный алгоритм для задачи о максимальном сечении . . . . . . . . . . . . . . . . . . . . 107
3.4.3 Дерандомизация и метод условных вероятностей. . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
3.4.4 Дерандомизация вероятностного алгоритма Луби нахождения максимального по включению неза-
висимого множества в графе . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
4 Криптография 115
4.1 Генераторы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
4.1.1 Псевдослучайные генераторы. Генератор Нисана-Вигдерсона . . . . . . . . . . . . . . . . . . . . 115
4.1.2 Полиномиальный алгоритм распознавания простоты числа . . . . . . . . . . . . . . . . . . . . . . 116
4.2 Элементы криптографии с открытым ключом . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
4.2.1 Односторонние функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
4.2.2 Дискретный логарифм. Обмен ключами. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
4.2.3 Система RSA и ее анализ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
5 Приложения 124
5.1 Глоссарий . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
5.2 Введение в Python . . . . . . . . . . . . .
Название: Сложность комбинаторных алгоритмов. Курс лекций
Автор: Кузюрин Н.Н., Фомин С.А.
Язык: Русский
Издательство: М.: Московский физико-технический институт
Жанр: Информатика и вычислительная техника,Теория алгоритмов
Год выхода: 2007
Формат: pdf
Страниц: 135 с.
Понятие алгоритма в математике используется давно, но различные его формализации были предложены только в середине 30-х годов прошлого столетия, когда и стала складываться теория алгоритмов. Классическая теория алгоритмов вообще не интересуется сложностными аспектами (временем решения задач на реальных вычислителях). В рамках классической теории алгоритмов, ставятся и решаются задачи о разрешимости различных задач, однако вычислительная сложность полученных решений принципиально не исследуется. Однако с практической точки зрения, может не быть никакой разницы между неразрешимой задачей и задачей, решаемой за время ?(exp(n)), где n — длина входа. Таким образом реализации алгоритмов на реальных вычислитель- ных машинах обязательно требуют анализа сложности их выполнения. Анализом задач с точки зрения вычислительной сложности занимается раздел теории алгоритмов — теория сложности вычислений, активно развивающийся с 50х годов — с момента создания вычислительной техники. Теория сложности вычислений занимает промежуточное положение между строгой математикой и реальным программированием. Для математика это в первую очередь математическая теория, строящаяся на основе фундаментальных понятий полиномиальной вычислимости и полиномиальной сводимости. Для программиста-практика — это набор общих методов, парадигм и конструкций, позволяющий в ряде случаев существенно минимизировать прямолинейный перебор вариантов, а в ряде случаев — показать, что эта задача в рассматриваемой постановке скорее всего неразрешима (и, следовательно, следует искать более реалистичные постановки).
Содержание
Оглавление
1 Элементы теории сложности 4
1.1 Несложно о сложности. Примеры алгоритмов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.1 Примеры задач на натуральных числах. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.2 Приближенные алгоритмы. Многопроцессорные расписания . . . . . . . . . . . . . . . . . . . . . 8
1.1.3 Примеры задач на графах. Кратчайшие пути и задача коммивояжера. . . . . . . . . . . . . . . . . 8
1.1.4 Сортировка слиянием . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.1.5 Быстрая сортировка. Анализ в среднем и вероятностная версия. . . . . . . . . . . . . . . . . . . . 17
1.2 Формально об алгоритмах . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.2.1 Машины с произвольным доступом (RAM) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.2.2 Машины Тьюринга и вычислимость . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1.3 Сложность алгоритмов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
1.3.1 Сложность в худшем случае (Worst Case Complexity) . . . . . . . . . . . . . . . . . . . . . . . . . 36
1.3.2 Полиномиальные алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
1.3.3 Полиномиальность и эффективность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
1.3.4 Эффективность и классы DTIME, DSPACE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
1.3.5 Полиномиальные сводимости и NP-полнота . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
1.3.6 Сводимость по Куку . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
1.3.7 Недетерминированные алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
1.3.8 Сводимость по Карпу . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
1.4 Вероятностные вычисления . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
1.4.1 Классы RP и coRP. Распознавание с односторонней ошибкой. . . . . . . . . . . . . . . . . . . . . 49
1.4.2 Класс BPP. Эффективное распознавание с двухсторонней ошибкой. . . . . . . . . . . . . . . . . . 51
1.4.3 Класс PP. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
1.4.4 Класс ZPP. Вероятностное распознавание без ошибок. . . . . . . . . . . . . . . . . . . . . . . . . 54
1.5 Вероятностно проверяемые доказательства . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
1.5.1 PCP и неаппроксимируемость . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
1.6 Схемы и схемная сложность . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
1.7 Коммуникационная сложность. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
1.8 Диаграмма классов сложности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
2 Приближенные алгоритмы с гарантированными оценками точности 67
2.1 Приближенные алгоритмы с фиксированными оценками точности . . . . . . . . . . . . . . . . . . . . . . 67
2.1.1 Жадный алгоритм в задаче о покрытии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
2.1.2 Приближенные алгоритмы для задачи покрытия с минимальной суммой . . . . . . . . . . . . . . 69
2.1.3 Жадный алгоритм для задачи о рюкзаке . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
2.1.4 Алгоритм Кристофидеса для метрической задачи коммивояжера . . . . . . . . . . . . . . . . . . . 73
2.2 Приближенные алгоритмы с выбираемыми оценками точности . . . . . . . . . . . . . . . . . . . . . . . . 79
2.2.1 Динамическое программирование для задачи о рюкзаке . . . . . . . . . . . . . . . . . . . . . . . . 79
2.2.2 Полностью полиномиальная приближенная схема для задачи о рюкзаке . . . . . . . . . . . . . . 82
3 Вероятностные алгоритмы и вероятностный анализ. 88
3.1 Вероятностный анализ детерминированных алгоритмов . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
3.1.1 Задача упаковки. Анализ сложности в среднем. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
3.1.2 Точность жадного алгоритма для почти всех исходных данных . . . . . . . . . . . . . . . . . . . . 92
3.1.3 Полиномиальный в среднем алгоритм для задачи о рюкзаке . . . . . . . . . . . . . . . . . . . . . 94
3.2 Вероятностные алгоритмы. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
3.2.1 Алгоритм Фрейвалда . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
2
3.2.2 Вероятностные методы в перечислительных алгоритмах. Подсчет числа выполняющих наборов
для ДНФ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
3.2.3 Вероятностный алгоритм Луби нахождения максимального по включению независимого множе-
ства в графе . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
3.3 Вероятностные методы в распределенных вычислениях . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
3.3.1 Протокол византийского соглашения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
3.4 Вероятностное округление и дерандомизация . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
3.4.1 Вероятностное округление . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
3.4.2 Приближенный алгоритм для задачи о максимальном сечении . . . . . . . . . . . . . . . . . . . . 107
3.4.3 Дерандомизация и метод условных вероятностей. . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
3.4.4 Дерандомизация вероятностного алгоритма Луби нахождения максимального по включению неза-
висимого множества в графе . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
4 Криптография 115
4.1 Генераторы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
4.1.1 Псевдослучайные генераторы. Генератор Нисана-Вигдерсона . . . . . . . . . . . . . . . . . . . . 115
4.1.2 Полиномиальный алгоритм распознавания простоты числа . . . . . . . . . . . . . . . . . . . . . . 116
4.2 Элементы криптографии с открытым ключом . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
4.2.1 Односторонние функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
4.2.2 Дискретный логарифм. Обмен ключами. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
4.2.3 Система RSA и ее анализ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
5 Приложения 124
5.1 Глоссарий . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
5.2 Введение в Python . . . . . . . . . . . . .
Название: Сложность комбинаторных алгоритмов. Курс лекций
Автор: Кузюрин Н.Н., Фомин С.А.
Язык: Русский
Издательство: М.: Московский физико-технический институт
Жанр: Информатика и вычислительная техника,Теория алгоритмов
Год выхода: 2007
Формат: pdf
Страниц: 135 с.
Смотрите также:
