URSS.ru Магазин научной книги
Перейти на канал URSS
Обложка Босс В. Лекции по математике: Перебор и эффективные алгоритмы Обложка Босс В. Лекции по математике: Перебор и эффективные алгоритмы
Id: 185773
13.9 EUR

Лекции по математике:
Перебор и эффективные алгоритмы. Т.10. Изд. стереотип.

URSS. 2014. 216 с. ISBN 978-5-382-01544-6. Уценка. Состояние: 5-. Блок текста: 5. Обложка: 5-.
Белая офсетная бумага

Аннотация

Настоящий том лекций посвящен теории сложности алгоритмов в той ее части, где речь идет о противостоянии P- и NP-задач. В резонанс с проблемой «P против NP» входит обширная тематика: комбинаторные задачи на графах, неразрешимые проблемы теории алгоритмов, криптография, целочисленное программирование, вероятностные методы, квантовые вычисления, алгоритмы Хачияна и Кармаркара для линейного программирования, а также полиномиальный ...(Подробнее)алгоритм AKS для выяснения простоты числа. Особое внимание уделяется геометрическому взгляду на проблему, который в привычном уже пейзаже обнаруживает свежие ракурсы.

Книга отличается краткостью и прозрачностью изложения. Объяснения даются "человеческим языком" --- лаконично и доходчиво, благодаря чему книга легко читается.

Для студентов, преподавателей, инженеров и научных работников.


Оглавление
top
Предисловие к "Лекциям"
Предисловие к десятому тому
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. Квантовые вычисления
Сокращения и обозначения
Литература
Предметный указатель

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

Том планировалось назвать "Труднорешаемые задачи", но помешала двусмысленность толкования. Одни начинают думать о математических олимпиадах, другие – "где бы найти что-нибудь полегче". А речь-то идет о противоборстве перебора и целенаправленного поиска. Иначе говоря, содержание вращается вокруг знаменитой проблемы "P против NP", и вовлекает в круговорот многое за пределами. Можно ли кардинально избавиться от сложности решения при компактном описании исходных данных? Не вообще избавиться, а там, где перечисление организовано экономно. Ибо почему бы не найти ответ быстро, если данных много, но описание коротко? Проблема на вид проста, но ускользает, и аукается в таких закоулках, что мысль о "неисповедимых путях" обретает дополнительную опору.


Предисловие к "Лекциям"
top
Лучше изредка спотыкаться на деталях,
чем утопить общую картину в формальностях.

Для нормального изучения любого математического предмета необходимы, по крайней мере, 4 ингредиента:

1) живой учитель;

2) обыкновенный подробный учебник;

3) рядовой задачник;

4) учебник, освобожденный от рутины, но дающий общую картину, мотивы, связи, "что зачем".

До четвертого пункта у системы образования руки не доходили. Конечно, подобная задача иногда ставилась и решалась, но в большинстве случаев – при параллельном исполнении функций обыкновенного учебника. Акценты изНза перегрузки менялись, и намерения со второй-третьей главы начинали дрейфовать, не достигая результата. В виртуальном пространстве так бывает. Аналог объединения гантели с теннисной ракеткой перестает решать обе задачи, хотя это не сразу бросается в глаза.

"Лекции" ставят 4Нй пункт своей главной целью. Сопутствующая идея – экономия слов и средств. Правда, на фоне деклараций о краткости и ясности изложения предполагаемое издание около 20 томов может показаться тяжеловесным, но это связано с обширностью математики, а не с перегрузкой деталями.

Необходимо сказать, на кого рассчитано. Ответ "на всех" выглядит наивно, но он в какой-то мере отражает суть дела. Обозримый вид, обнаженные конструкции доказательств, – такого сорта книги удобно иметь под рукой. Не секрет, что специалисты самой высокой категории тратят массу сил и времени на освоение математических секторов, лежащих за рамками собственной специализации. Здесь же ко многим проблемам предлагается короткая дорога, позволяющая быстро освоить новые области и освежить старые. Для начинающих "короткие дороги" тем более полезны, поскольку облегчают движение любыми другими путями.

В вопросе "на кого рассчитано", – есть и другой аспект. На сильных или слабых? На средний вуз или физтех? Опять-таки выходит "на всех". Звучит странно, но речь не идет о регламентации кругозора. Простым языком, коротко и прозрачно описывается предмет. Из этого каждый извлечет свое и двинется дальше.

Наконец, последнее. В условиях информационного наводнения инструменты вчерашнего дня перестают работать. Не потому, что изучаемые дисциплины чересчур разрослись, а потому, что новых секторов жизни стало слишком много. И в этих условиях мало кто готов уделять много времени чему-то одному. Поэтому учить всему – надо как-то иначе. "Лекции" дают пример. Плохой ли, хороший – покажет время. Но в любом случае, это продукт нового поколения. Те же "колеса", тот же "руль", та же математическая суть, – но по-другому.


О загадке бестселлеров В.Босса
top

Книгу В.Босса "Интуиция и математика" я перечитал три раза! Потом еще раз, чтобы разобраться, в чем дело, но скрытых пружин так и не нашел. Конечно, великолепный подбор миниатюр, точный язык, мягкий юмор, располагающая интонация, – но все это вместе взятое не объясняет результат даже наполовину. Сын моего приятеля – парню 14 лет – выучил "Интуицию" почти наизусть. Измучил родителей вопросами, прочел гору дополнительной литературы. Понятно – особый случай, но показательный! В целом ситуация, безусловно, мягче. Однако отзывы все положительные, а процент восторженных – удивителен и необъясним.

"Лекции по математике" того же автора – другое дело. Кое-кто из моих коллег принял их в штыки, поскольку система образования, естественно, противится нововведениям. Лишняя головная боль для преподавателя. Тем не менее, в результате итогового обсуждения – первые два тома "Лекций" пришли к нам на отзыв – В.Босс получил высший бал.

Лично мне "Лекции" нравятся даже больше, чем "Интуиция". Ясное и продуманное изложение предмета. Лаконичное до неправдоподобия, но без ущерба для содержания. Вот что по этому поводу пишет сам автор: "Первая часть книги – сжатый курс матанализа. Чушь более сотни страниц, но "все есть". Некоторые детали, конечно, опускаются, но это не потери, а приобретения. Сбросив десяток лишних килограмм, человек выглядит лучше, живет интереснее. Так и здесь. Многие подробности мешают видеть суть. И освобождение от балласта, как ни странно, позволяет обсуждать принципиальные вопросы, на которые в толстых учебниках не хватает места".

Первый опыт показывает, что студенты – и сильные, и слабые – благосклонно принимают "Лекции". В этом еще одна удивительная, хотя и понятная особенность изложения. Короткий и ясный взгляд на предмет, обсуждение мотивов, общая картина, – нужны всем.

Наконец, я бы не писал в газету, если бы речь шла просто о хороших и даже очень хороших книгах. "Лекции" В.Босса, на мой взгляд, явление неординарное. Дело в том, что информационная лавина сейчас многое меняет. В результате, сложившаяся система образования подходит к критической точке. Конечно, как в доме накапливаются ненужные вещи, так и в образовании со временем укореняется масса атавизмов. Но хуже другое. То, без чего вроде бы нельзя обойтись, перестает помещаться в рамки. Поэтому необходимы новые подходы и принципы. "Лекции" обеспечивают прорыв в этом направлении.

Профессор МФТИ А.П.Афанасьев

Из интервью с В.Боссом
top

Нельзя ли в двух словах о главной особенности "Лекций"?

– Диалектика обучения – во взаимодействии сторон. Понимание – умение. Суть – детали. "Лекции" добиваются понимания.

Как?

– Правдами и неправдами (улыбается). Очень важно, например, поместить проблему "целиком в кадр". Чтобы видно было "сразу все".

Объяснениями на пальцах?

– Когда как, только "коротко и ясно". Упрощения, недомолвки. Но главное – обнажение сути.

А что посоветуете, если завтра экзамен, а в голове пусто?

– Таблетку димедрола.


В условиях информационного наводнения инструменты вчерашнего дня перестают работать. Поэтому учить надо как-то иначе. "Лекции" дают пример. Плохой ли, хороший – покажет время. Но в любом случае, это продукт нового поколения. Те же "колеса", тот же "руль", та же математическая суть, – но по-другому.

В.Босс

Из отзывов читателей:

Чтобы усвоить предмет, надо освободить его от деталей, обнажить центральные конструкции, понять, как до теорем можно было додуматься. Это тяжелая работа, на которую не всегда хватает сил и времени. В "Лекциях" такая работа проделывается автором.

Популярность книг В.Босса легко объяснима. Дается то, чего недостает: общая картина, мотивация, взаимосвязи. И самое главное – легкость вхождения в любую тему.

Содержание продумано и хорошо увязано. Громоздкие доказательства ужаты до нескольких строчек. Виртуозное владение языком.


Об авторе
top
photoБосс В.
Российский ученый, просветитель и популяризатор науки, заведующий сектором Института проблем управления Российской академии наук (ИПУ РАН); доктор физико-математических наук, профессор кафедры проблем управления Московского физико-технического института (МФТИ). Создатель и автор крупного Интернет-проекта «Школа Опойцева».

Практически вся его научная деятельность связана с работой в Институте проблем управления, где в качестве ведущего специалиста в области управления социальными и экономическими системами, статики и динамики сложных систем, он принимал участие во многих научно-прикладных программах и разработках. Руководил прикладными исследованиями для Госплана и Министерства связи СССР, а также крупной научно-исследовательской работой по расчету и оптимизации структуры бортовых вычислительных систем.

Талантливый лектор, Валерий Иванович всегда был увлечен просветительской деятельностью, часто разъезжал по стране, буквально — от Балтики до Камчатки, в качестве активного члена Общества «Знание» — «академии миллионов».

За время работы в Австралии (1998–2001) опубликовал множество статей по математике на английском языке и читал лекции для профессоров в Квинслендском университете.

Последние годы Валерий Иванович посвятил проекту «Школа Опойцева» — это книги, видеолекции и учебные материалы по математике и физике для высшего и школьного образования.

Он был убежден, что: «В условиях информационного наводнения инструменты вчерашнего дня перестают работать. Поэтому учить надо как-то иначе. „Лекции“ дают пример. Плохой ли, хороший — покажет время. Но в любом случае это продукт нового поколения. Те же „колеса“, тот же „руль“, та же математическая суть — но по-другому».

Информация / Заказ
2024. 288 с. Мягкая обложка. 15.9 EUR Новинка недели!

Особенности 20-го выпуска:

- исправили предыдущие ошибки

- Добавлены разновидности в раздел разновидностей юбилейных монет СССР

- В раздел 50 копеек 2006-2015 добавлены немагнитные 50 копеек

10 копеек 2005 М (ввел доп. разворот)

- Добавлена информация о 1 рубле 2010 СПМД немагнитный... (Подробнее)


Информация / Заказ
Зиновьев А.А. ЗИЯЮЩИЕ ВЫСОТЫ
2024. 720 с. Твердый переплет. 19.9 EUR

Книга «Зияющие высоты» – первый, главный, социологический роман, созданный интеллектуальной легендой нашего времени – Александром Александровичем Зиновьевым (1922-2006), единственным российским лауреатом Премии Алексиса де Токвиля, членом многочисленных международных академий, автором десятков логических... (Подробнее)


Информация / Заказ
2022. 1656 с. Твердый переплет. 169.9 EUR

Впервые в свет выходит весь комплекс черновиков романа М. А. Булгакова «Мастер и Маргарита», хранящихся в научно-исследовательском отделе рукописей Российской государственной библиотеки. Текст черновиков передаётся методом динамической транскрипции и сопровождается подробным текстологическим... (Подробнее)


Информация / Заказ
2023. 274 с. Мягкая обложка. 14.9 EUR

Арабо-израильский конфликт, в частности палестино-израильский, на протяжении многих десятилетий определял политическую ситуацию на Ближнем Востоке. На современном этапе наблюдается падение значимости палестинской проблемы в системе международных приоритетов основных акторов. В монографии... (Подробнее)


Информация / Заказ
URSS. 2024. 136 с. Мягкая обложка. В печати

В настоящей книге, написанной выдающимся тренером А.Н.Мишиным, описывается техника фигурного катания, даются практические советы по овладению этим видом спорта. В книге рассматриваются основы техники элементов фигурного катания и то, как эти элементы соединяются в спортивные программы, излагаются... (Подробнее)


Информация / Заказ
2024. 400 с. Твердый переплет. 16.9 EUR

Как реализовать проект в срок, уложиться в бюджет и не наступить на все грабли? Книга Павла Алферова — подробное практическое руководство для всех, кто занимается разработкой и реализацией проектов. Его цель — «переупаковать» проектное управление, сделать метод более применимым к российским... (Подробнее)


Информация / Заказ
URSS. 2024. 344 с. Мягкая обложка. 18.9 EUR

Мы очень часто сталкиваемся с чудом самоорганизации. Оно воспринимается как само собой разумеющееся, не требующее внимания, радости и удивления. Из случайно брошенного замечания на семинаре странным образом возникает новая задача. Размышления над ней вовлекают коллег, появляются новые идеи, надежды,... (Подробнее)


Информация / Заказ
URSS. 2023. 272 с. Мягкая обложка. 15.9 EUR

Настоящая книга посвящена рассмотрению базовых понятий и техник психологического консультирования. В ней детально представлены структура процесса консультирования, описаны основные его этапы, содержание деятельности психолога и приемы, которые могут быть использованы на каждом из них. В книге... (Подробнее)


Информация / Заказ
URSS. 2024. 704 с. Твердый переплет. 26.9 EUR

В новой книге профессора В.Н.Лексина подведены итоги многолетних исследований одной из фундаментальных проблем бытия — дихотомии естественной неминуемости и широчайшего присутствия смерти в пространстве жизни и инстинктивного неприятия всего связанного со смертью в обыденном сознании. Впервые... (Подробнее)


Информация / Заказ
URSS. 2024. 576 с. Мягкая обложка. 23.9 EUR

Эта книга — самоучитель по военной стратегии. Прочитав её, вы получите представление о принципах военной стратегии и сможете применять их на практике — в стратегических компьютерных играх и реальном мире.

Книга состоит из пяти частей. Первая вводит читателя в мир игр: что в играх... (Подробнее)