Босс Валерий
Лекции по математике. Перебор и эффективные алгоритмы, том 10

Lib.ru/Современная литература: [Регистрация] [Найти] [Рейтинги] [Обсуждения] [Новинки] [Помощь]
  • Комментарии: 1, последний от 31/12/2019.
  • © Copyright Босс Валерий
  • Размещен: 26/03/2008, изменен: 10/07/2009. 6k. Статистика.
  • Учебник: Естеств.науки
  • Учебные пособия

    •    Содержание
       1. Комбинаторные задачи
       1.1. Экспоненциальный кошмар
       1.2. P- и NP-задачи
       1.3. Центральный вопрос и окружение
       1.4. Задачи на графах
       1.5. Целочисленное программирование
       1.6. Логические задачи
       1.7. (0,1)-матрицы
       1.8. Простые и составные числа
       1.9. Комбинаторные механизмы
      
       2. Инструменты и декорации
       2.1. Вычислимые функции
       2.2. Перечислимые множества
       2.3. Неразрешимые проблемы
       2.4. Машины Тьюринга
       2.5. Полиномиальные алгоритмы
       2.6. Вычислительная сложность
       2.7. Задачи верхнего уровня
      
       3. Проблема "P=NP?"
       3.1. Класс P
       3.2. Класс NP
       3.3. Сводимость и NP-полнота
       3.4. Универсальная переборная задача
       3.5. Теорема Кука
       3.6. Класс NPC
       3.7. Подход Левина
       3.8. Полиномиальное раздутие
       3.9.Будет ли решена проблема  "P=NP?"
      
       4. Анатомия переборных задач
       4.1.Проблема "co-NP=NP?"
       4.2. Сильная NP-полнота
       4.3. Кратчайший путь
       4.4. Максимальный поток и минимальный разрез
       4.5. Теория матроидов и жадный алгоритм
       4.6. Вариации МОД
       4.7. PSPACE-задачи
       4.8. Схемная сложность
       4.9. Интерактивные протоколы
       4.10. Релятивизация и оракулы
       4.11. Рамсеевские задачи
      
       5. Линейное программирование
       5.1. Постановка задачи
       5.2. Предыстория комбинаторного варианта
       5.3. Эффекты ограниченной точности
       5.4. Алгоритм эллипсоидов
       5.5. Природа алгоритма
       5.6. Методы внутренней точки
       5.7. Феномен целочисленных вершин
      
       6. Арифметика и криптография
       6.1. О причинах исключительности
       6.2. Тесты на простоту
       6.3. Полиномиальный тест AKS
       6.4. Алгоритмы факторизации
       6.5. Система RSA
       6.6. Вариант распознавания
       6.7. Дискретный логарифм
       6.8. Системы с нулевым разглашением
       6.9. Другие задачи
       6.10. Технические дополнения
      
       7. Геометрический подход
       7.1. Общая картина
       7.2. Выпуклые многогранники
       7.3. Циклические многогранники
       7.4. Линейные разделяющие деревья
       7.5. Алгоритмы прямого типа
       7.6. Релаксационные многогранники
       7.7. Аффинная сводимость
       7.8. Комментарии и дополнения
      
       8. Вероятностные алгоритмы
       8.1. Напоминание о смешанных стратегиях
       8.2. Интерактивные доказательства
       8.3. PCP-проблематика
       8.4. Рутинная колея
       8.5. Простые числа
      
       9. Прагматика и эвристика
       9.1. Сетевое программирование как обобщение динамического
       9.2. Ареал жадного алгоритма
       9.3. Приближенные алгоритмы
       9.4. Метод ветвей и границ
       9.5. О задаче ЦЛП
      
       10. Квантовые вычисления
       10.1. В чем идея и каковы препятствия
       10.2. Основные понятия
       10.3. Вычисление и феномен измерения
       10.4. Квантовые вентили
       10.5. Алгоритм ускоренного поиска
       10.6. Квантовое преобразование Фурье
       10.7. Алгоритм факторизации Шора
       10.8. Антипод здравого смысла
       10.9. ЭПР-парадокс и скрытые параметры
       10.10. О перетягивании каната
       10.11. Комментарии и дополнения
      
       11. Сводка основных определений и результатов
       Литература
       Предметный указатель
      

    Предисловие

      

    Чего, собственно, ожидать на краю?
    На грани, где возможное переходит в невозможное, жизнь     - в смерть,
    теорема -- в парадокс. По сути     - ожидать нечего.
    Однако, как и в поиске смысла жизни,
    основную роль здесь играют побочные эффекты.

       Том планировалось назвать "Труднорешаемые задачи", но помешала двусмысленность толкования. Одни начинают думать о математических олимпиадах, другие - "где бы найти что-нибудь полегче". А речь-то идет о противоборстве перебора и целенаправленного поиска. Иначе говоря, содержание вращается вокруг знаменитой проблемы "P против NP", и вовлекает в круговорот многое за пределами. Можно ли кардинально избавиться от сложности решения при компактном описании исходных данных? Не вообще избавиться, а там, где перечисление организовано экономно. Ибо почему бы не найти ответ быстро, если данных много, но описание коротко? Проблема на вид проста, но ускользает, и аукается в таких закоулках, что мысль о "неисповедимых путях" обретает дополнительную опору.
  • Комментарии: 1, последний от 31/12/2019.
  • © Copyright Босс Валерий
  • Обновлено: 10/07/2009. 6k. Статистика.
  • Учебник: Естеств.науки
    • Связаться с программистом сайта.