Разное




РазДЕЛЫ САЙТА

Боевики, детективы
Документалка
Драмы, триллеры
Исторические
Комедии
Мелодрамы
Мультяшки
Обучающее, познание
Приключения
Сказки, фэнтези
Старое, доброе
Ужасы
Фантастика
х х х х х х х х х
Блюз, джаз, соул
Инструментальная
Классическая
Клипы
Минусовки
Музыка игр и кино
Поп
Разная
Ретро
Рок, метал
Рэп, хип-хоп
Шансон
х х х х х х х х х
Автософт и навигация
Аудиокниги
Книги и журналы
Фото и видео, приколы



СЛучайные материалы

Melting Pot Music (2012)
Melting Pot Music (2012)

Глеб Напреенко - Введение в психоанализ: от Фрейда к Лакану и далее (2023) WEBRip
Глеб Напреенко - Введение в психоанализ: от Фрейда к Лакану и далее (2023) WEBRip

Сапфир Олег, Ковтунов Алексей - Идеальный мир для Лекаря. Книга 6 (Аудиокнига)
Сапфир Олег, Ковтунов Алексей - Идеальный мир для Лекаря. Книга 6 (Аудиокнига)

Кораблев Родион - Другая сторона. Том 2. Проводник Часть 1 (Аудиокнига)
Кораблев Родион - Другая сторона. Том 2. Проводник Часть 1 (Аудиокнига)

Happy Beats (2024)
Happy Beats (2024)
Главная » 2019 » Январь » 16 » Кузюрин Н.Н., Фомин С.А. - Сложность комбинаторных алгоритмов. Курс лекций

Кузюрин Н.Н., Фомин С.А. - Сложность комбинаторных алгоритмов. Курс лекций

13:47

Понятие алгоритма в математике используется давно, но различные его формализации были предложены только в середине 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 с.
Размер: 64 mb

Скачать Кузюрин Н.Н., Фомин С.А. - Сложность комбинаторных алгоритмов. Курс лекций


Скачать: Книги и журналы | Теги: литература, Сложность комбинаторных алгоритмов, электронная книга, Книга

Похожие материалы скачать бесплатно и без регистрации


К "Кузюрин Н.Н., Фомин С.А. - Сложность комбинаторных алгоритмов. Курс лекций"
пока нет комментариев, но Вы можете стать первым, кто его оставит!

Всего мнений: 0
Войдите:
avatar
Ищу на сайте

Случайный анекдот
- Доктор, спасибо, боль в спине прошла. Что это было - радикулит?
- Нет, просто подтяжки были перекручены!

Новое на сайте
Пока, к сожалению, ничего нет

Наша статистика
Присутствуют: 4
Неизвестных: 4
Знакомых: 0
Copyright by Anonimus © 2024