Предисловие к "Лекциям" |
Предисловие к десятому тому |
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. Сводка основных определений и результатов |
| 11.1. Список NP-полных задач |
| 11.2. Алгоритмы и вычислимость |
| 11.3.Проблема P=NP |
| 11.4. Вокруг "P или NP" |
| 11.5. Линейное программирование |
| 11.6. Арифметика и криптография |
| 11.7. Геометрический подход |
| 11.8. Вероятностные алгоритмы |
| 11.9. Квантовые вычисления |
Сокращения и обозначения |
Литература |
Предметный указатель |
Предисловие к десятому тому
Чего, собственно, ожидать на краю?
На грани, где возможное переходит
в невозможное, жизнь -- в смерть,
теорема -- в парадокс. По сути -- ожидать
нечего.
Однако, как и в поиске смысла жизни,
основную роль здесь играют
побочные эффекты.
Том планировалось назвать "Труднорешаемые задачи", но помешала двусмысленность
толкования. Одни начинают думать о математических олимпиадах, другие -- "где бы найти что-нибудь полегче". А речь-то идет о противоборстве перебора
и целенаправленного поиска. Иначе говоря, содержание вращается вокруг знаменитой
проблемы "P против NP", и вовлекает в круговорот многое за пределами. Можно ли
кардинально избавиться от сложности решения при компактном описании исходных
данных? Не вообще избавиться, а там, где перечисление организовано экономно.
Ибо почему бы не найти ответ быстро, если данных много, но описание коротко?
Проблема на вид проста, но ускользает, и аукается в таких закоулках, что мысль
о "неисповедимых путях" обретает дополнительную опору.
Лучше изредка спотыкаться на деталях,
чем утопить общую картину
в формальностях.
Для нормального изучения любого математического предмета необходимы, по крайней
мере, 4 ингредиента:
1) живой учитель;
2) обыкновенный подробный учебник;
3) рядовой задачник;
4) учебник, освобожденный от рутины, но дающий общую картину, мотивы,
связи, "что зачем".
До четвертого пункта у системы образования руки не доходили. Конечно, подобная
задача иногда ставилась и решалась, но в большинстве случаев -- при
параллельном исполнении функций обыкновенного учебника. Акценты изНза
перегрузки менялись, и намерения со второй-третьей главы начинали дрейфовать,
не достигая результата. В виртуальном пространстве так бывает. Аналог
объединения гантели с теннисной ракеткой перестает решать обе задачи, хотя это
не сразу бросается в глаза.
"Лекции" ставят 4Нй пункт своей главной целью. Сопутствующая идея -- экономия слов и средств. Правда, на фоне деклараций о краткости и ясности
изложения предполагаемое издание около 20 томов может показаться тяжеловесным,
но это связано с обширностью математики, а не с перегрузкой деталями.
Необходимо сказать, на кого рассчитано. Ответ "на всех" выглядит наивно,
но он в какой-то мере отражает суть дела. Обозримый вид, обнаженные конструкции
доказательств, -- такого сорта книги удобно иметь под рукой. Не секрет, что
специалисты самой высокой категории тратят массу сил и времени на освоение
математических секторов, лежащих за рамками собственной специализации. Здесь же
ко многим проблемам предлагается короткая дорога, позволяющая быстро освоить
новые области и освежить старые. Для начинающих "короткие дороги" тем более
полезны, поскольку облегчают движение любыми другими путями.
В вопросе "на кого рассчитано", -- есть и другой аспект. На сильных или
слабых? На средний вуз или физтех? Опять-таки выходит "на всех". Звучит
странно, но речь не идет о регламентации кругозора. Простым языком, коротко
и прозрачно описывается предмет. Из этого каждый извлечет свое и двинется дальше.
Наконец, последнее. В условиях информационного наводнения инструменты
вчерашнего дня перестают работать. Не потому, что изучаемые дисциплины чересчур
разрослись, а потому, что новых секторов жизни стало слишком много. И в этих
условиях мало кто готов уделять много времени чему-то одному. Поэтому учить
всему -- надо как-то иначе. "Лекции" дают пример. Плохой ли, хороший -- покажет время. Но в любом случае, это продукт нового
поколения. Те же "колеса", тот же "руль", та же математическая суть, -- но по-другому.
О загадке бестселлеров В.Босса
Книгу В.Босса "Интуиция и математика" я перечитал три раза! Потом
еще раз, чтобы разобраться,
в чем дело, но скрытых пружин так
и не нашел. Конечно, великолепный
подбор миниатюр, точный язык,
мягкий юмор, располагающая интонация, -- но все это вместе взятое
не объясняет результат даже наполовину.
Сын моего приятеля -- парню
14 лет -- выучил "Интуицию" почти
наизусть. Измучил родителей вопросами,
прочел гору дополнительной
литературы. Понятно -- особый
случай, но показательный! В целом
ситуация, безусловно, мягче. Однако
отзывы все положительные,
а процент восторженных -- удивителен
и необъясним.
"Лекции по математике" того же автора -- другое дело. Кое-кто
из моих коллег принял их в штыки,
поскольку система образования,
естественно, противится нововведениям.
Лишняя головная боль для
преподавателя. Тем не менее, в результате
итогового обсуждения -- первые
два тома "Лекций" пришли
к нам на отзыв -- В.Босс получил
высший бал.
Лично мне "Лекции" нравятся даже
больше, чем "Интуиция". Ясное
и продуманное изложение предмета.
Лаконичное до неправдоподобия,
но без ущерба для содержания.
Вот что по этому поводу пишет сам
автор: "Первая часть книги -- сжатый
курс матанализа. Чушь более
сотни страниц, но "все есть". Некоторые
детали, конечно, опускаются,
но это не потери, а приобретения.
Сбросив десяток лишних
килограмм, человек выглядит лучше,
живет интереснее. Так и здесь.
Многие подробности мешают видеть
суть. И освобождение от балласта,
как ни странно, позволяет
обсуждать принципиальные вопросы,
на которые в толстых учебниках
не хватает места".
Первый опыт показывает, что студенты -- и сильные, и слабые -- благосклонно
принимают "Лекции".
В этом еще одна удивительная, хотя
и понятная особенность изложения.
Короткий и ясный взгляд на предмет,
обсуждение мотивов, общая
картина, -- нужны всем.
Наконец, я бы не писал в газету,
если бы речь шла просто о хороших
и даже очень хороших книгах.
"Лекции" В.Босса, на мой взгляд,
явление неординарное. Дело в том,
что информационная лавина сейчас
многое меняет. В результате,
сложившаяся система образования
подходит к критической точке. Конечно,
как в доме накапливаются
ненужные вещи, так и в образовании
со временем укореняется масса
атавизмов. Но хуже другое. То,
без чего вроде бы нельзя обойтись,
перестает помещаться в рамки. Поэтому
необходимы новые подходы
и принципы. "Лекции" обеспечивают
прорыв в этом направлении.
Профессор МФТИ А.П.Афанасьев
-- Нельзя ли в двух словах о главной особенности "Лекций"?
-- Диалектика обучения -- во взаимодействии сторон. Понимание -- умение.
Суть -- детали. "Лекции" добиваются понимания.
-- Как?
-- Правдами и неправдами (улыбается). Очень важно, например, поместить проблему
"целиком в кадр". Чтобы видно было "сразу все".
-- Объяснениями на пальцах?
-- Когда как, только "коротко и ясно". Упрощения, недомолвки. Но главное -- обнажение сути.
-- А что посоветуете, если завтра экзамен, а в голове пусто?
-- Таблетку димедрола.
В условиях информационного наводнения инструменты вчерашнего дня перестают
работать. Поэтому учить надо как-то иначе. "Лекции" дают пример. Плохой
ли, хороший -- покажет время. Но в любом случае, это продукт нового
поколения. Те же "колеса", тот же "руль", та же математическая суть, -- но
по-другому.
В.Босс
Из отзывов читателей:
Чтобы усвоить предмет, надо освободить
его от деталей, обнажить центральные
конструкции, понять, как до теорем
можно было додуматься. Это тяжелая
работа, на которую не всегда
хватает сил и времени. В "Лекциях"
такая работа проделывается автором.
Популярность книг В.Босса легко
объяснима. Дается то, чего недостает:
общая картина, мотивация,
взаимосвязи. И самое главное --
легкость вхождения в любую тему.
Содержание продумано и хорошо
увязано. Громоздкие доказательства
ужаты до нескольких строчек.
Виртуозное владение языком.
Босс В.
Российский ученый, просветитель и популяризатор науки, заведующий сектором Института проблем управления Российской академии наук (ИПУ РАН); доктор физико-математических наук, профессор кафедры проблем управления Московского физико-технического института (МФТИ). Создатель и автор крупного Интернет-проекта «Школа Опойцева».
Практически вся его научная деятельность связана с работой в Институте проблем управления, где в качестве ведущего специалиста в области управления социальными и экономическими системами, статики и динамики сложных систем, он принимал участие во многих научно-прикладных программах и разработках. Руководил прикладными исследованиями для Госплана и Министерства связи СССР, а также крупной научно-исследовательской работой по расчету и оптимизации структуры бортовых вычислительных систем.
Талантливый лектор, Валерий Иванович всегда был увлечен просветительской деятельностью, часто разъезжал по стране, буквально — от Балтики до Камчатки, в качестве активного члена Общества «Знание» — «академии миллионов».
За время работы в Австралии (1998–2001) опубликовал множество статей по математике на английском языке и читал лекции для профессоров в Квинслендском университете.
Последние годы Валерий Иванович посвятил проекту «Школа Опойцева» — это книги, видеолекции и учебные материалы по математике и физике для высшего и школьного образования.
Он был убежден, что: «В условиях информационного наводнения инструменты вчерашнего дня перестают работать. Поэтому учить надо как-то иначе. „Лекции“ дают пример. Плохой ли, хороший — покажет время. Но в любом случае это продукт нового поколения. Те же „колеса“, тот же „руль“, та же математическая суть — но по-другому».