Текущий раздел » » » Сложность комбинаторных алгоритмов. Курс лекций
Лучшие книги по лучшим ценам здесь!

Сложность комбинаторных алгоритмов. Курс лекций

  • Заявить о правах (Abuse)
Автор: strok10 от 2019-01-16, 14:10:20
Сложность комбинаторных алгоритмов. Курс лекций Автор: Кузюрин Н.Н., Фомин С.А.
Язык: Русский
Издательство: М.: Московский физико-технический институт
Жанр: Информатика и вычислительная техника,Теория алгоритмов
Год: 2007
Формат: pdf
Размер: 64 mb

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

Скачать Сложность комбинаторных алгоритмов. Курс лекций




Ad Litteram. Купить и скачать книги в fb2 на любом устройстве, читать онлайн

Акция С заботой о здоровье и безопасности

Самые ожидаемые книги мая 2022 года

Больше книг - больше выгода! Скидки до 30%




My-shop.ru: самый большой выбор детских игрушек в Рунете My-shop.ru - книжный Интернет-магазин My-shop.ru - Интернет-магазин для учителей My-shop.ru - Интернет-магазин учебной литературы
Интернет-магазин детских игрушек Книжный интернет-магазин Интернет-магазин для учителей Интернет-магазин учебной литературы
       

My-shop.ru - Ваш Интернет-магазин My-shop.ru - детский Интернет-магазин My-shop.ru - Интернет-магазин товаров для рукоделия My-shop.ru - Интернет-магазин товаров для образования
Интернет-магазин с более 700000 товаров Интернет-магазин товаров для детей Интернет-магазин товаров для рукоделия Интернет-магазин товаров для образования
       


 


BooksKeeper - электронная библиотека, ежедневно пополняемая нашими авторами.
Все материалы, представленные на нашем сайте, Вы сможете скачать по ссылкам различных бесплатных файлообменников совершенно бесплатно!
Инструкции, поясняющие, как надо качать бесплатно с файлообменников смотреть тут
Регистрация на нашем сайте позволит Вам добавлять свои книги, а также комментировать опубликованные книги, общаться с нашими авторами.
Для этого мы рекомендуем Вам зарегистрироваться либо войти на сайт под своим именем.

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


Информация
Посетители, находящиеся в группе Гости, не могут оставлять комментарии к данной публикации.

Размещение Вашего баннера на книжном сайте BEGET - первые 30 дней хостинга БЕСПЛАТНО! HostLife - лучший платный хостинг
Баннер или тизер? Выбирай! BEGET - первые 30 дней хостинга БЕСПЛАТНО! HostLife - лучший платный хостинг!
Размещение Вашего баннера на нашем сайте - это дешевая реклама Ваших сайтов или партнерских программ! Стабильный, профессиональный и ОЧЕНЬ выгодный хостинг на сегодняший день! Бонусы, акции - все для Вас! Отличный хостинг по цене от 1.87$/месяц! Рекомендация от сайта Bookskeeper.ru!


Бесплатная электронная библиотека. Скачать книги бесплатно!
Текущий раздел » » » Сложность комбинаторных алгоритмов. Курс лекций

Наша электронная библиотека Bookskeeper.ru - это интернет-витрина, где любой посетитель может публиковать электронные варианты книг, журналов, газет, комиксов, в общем, любой литературы со ссылками для медленного, но бесплатного скачивания с файлообменников.

В нашем книжном хранилище Вы всегда найдете литературу на любой вкус человека любого возраста - от детских комиксов и расскрасок до серьезной научной литературы.
 
 

Реклама


Садовые печи-барбекю от компании Династия


Возврат инвестиций scamconsulting.com


Фотоаппарат моментальной печати купить c БЕСПЛАТНОЙ ДОСТАВКОЙ!



Labirint.ru - ваш проводник по лабиринту книг



Book24.ru - книжный интернет магазин



BEGET - первые 30 дней хостинга БЕСПЛАТНО!



Turbobit - Получите турбо-доступ и скачивайте безлимитно и без рекламы!



Ad Litteram. Купить и скачать книги в fb2 на любом устройстве, читать онлайн



Kwork.ru - услуги фрилансеров от 500 руб.


Интернет-магазин ШОПС. Нужные товары для Вашего дома, сада, автомобиля
 
 

Топ публикаций

 
  • Щепетнов Евгений - Сборник "Бандит" (5 книг)
  • Глебов Макс - Сборник "Блюстители хаоса" (2 книги)
  • Французские гастроли
  • Выбор. Долгие каникулы в Одессе
  • Заюшкина избушка (сборник)
  • История на просеке
  • Сборник произведений в 324 книгах (Дружба народов. Харвест и др.) 1983-2022
  • Домашняя лаборатория №2-3 (февраль-март 2022)
  • Полари. Цикл из 15 книг
  • Автоматика и программная инженерия №4 (2021)
  • Ионов Павел - Сборник "Пача" (2 книги)
  • Комсомольская правда (Толстушка) Россия №19т 2022
  • Ловушка для людей (аудиокнига)
  • Pitstop №4 2022
  • S-T-I-K-S. Первый ангел
  • Титан. Цикл из 3 книг
  • Каменев А. - Сборник "Алхимик" (4 книги)
  • Уникум (В. Поселягин). Цикл из 3 книг
  • Арчи. Цикл из 7 книг
  • Целитель (В. Большаков). Цикл из 7 книг
  • Громыко О. - Сборник "Космоолухи. Карма" (2 тома)
  • Последний реанорец. Том I
  • Титан. Цикл из 2 книг
  • Сын ведьмы. Цикл из 3 книг
  • Рави Ивар - Сборник произведений (12 книг)
  • Сибирский целитель
  • Беличенко Константин - Сборник "Контрабандист Сталина" (8 книг)
  • Самая тёмная ночь. Цикл из 2 книг
  • А.Смолин, ведьмак. Цикл из 7 книг
  • Псы Нинеи. Стаф. Цикл из 4 книг
  •