Блог независимых постеров
Суббота, 27.04.2024, 06:27
Приветствую Вас Гость | RSS
 
Главная РегистрацияВход
Меню сайта
  • Главная
  • Наши правила
  • Добавить новость
  • Как оформить?
  • Наш форум
  • Контакты
    • Категории раздела
    Софт
    Видео
    Музыка
    Игры
    Графика
    Чтиво
    Другое
    Кулинария
    Наш опрос
    Самая интересная категория?
    [ Результаты · Архив опросов ]
    Всего ответов: 305
    Статистика
    Главная » 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

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

    Категория: Чтиво | Просмотров: 134 | Добавил: zyzy | Теги: книга, Сложность комбинаторных алгоритмов, литература, электронная книга | Рейтинг: 0.0/0
    Похожие материалы:
    Всего коментариев: 0
    Добавлять коментарии могут только зарегистрированные пользователи.
    [ Регистрация | Вход ]
    Онлайн
    Онлайн всего: 1
    Гостей: 1
    Пользователей: 0
    Мини-чат
    Поиск
    Календарь
    Друзья сайта
    Copyright by blogz © 2024
    Хостинг от uCoz