Золотой билет

Золотой билет

«Золотой билет» – великолепное введение в P/NP-проблему, в котором описаны история этой задачи и ее влияние на нашу жизнь. В этой информативной и занимательной книге Лэнс Фортноу прослеживает работу, которая велась над задачей во времена холодной войны по обе стороны «железного занавеса», и приводит примеры ее возникновения во множестве дисциплин, включая экономику, физику и биологию.

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

В формате pdf A4 сохранен издательский дизайн.

Жанры: Научная литература, Компьютерная литература, Научпоп, Технические науки
Серии: -
Всего страниц: 59
ISBN: 978-5-00101-424-9
Год издания: 2016
Формат: Фрагмент

Золотой билет читать онлайн бесплатно

Шрифт
Интервал

Посвящается Марси, Энни и Молли.

Теперь они, может быть, поймут, чем я занимаюсь и почему.

Copyright © 2013 by Princeton University Press Все права защищены. Никакая часть этой книги не может быть воспроизведена или передана в любой форме или любыми средствами, электронными или механическими, включая фотокопирование, запись или использование средств хранения и поиска информации, без письменного разрешения Издателя.

© Лаборатория знаний, 2016

Предисловие

В Америке почти у каждого второго есть смартфон. Этот маленький компьютер давно обогнал своих более крупных собратьев, которые еще каких-то двадцать лет назад считались очень мощными. Компьютеры снабжают нас информацией о мире и не дают в ней потеряться; позволяют выходить на связь почти из любой точки планеты; справляются с неимоверно сложными вычислительными задачами, будь то составление расписаний для загруженных аэропортов или моделирование космических явлений. Компьютеры распознают наши лица и голоса, регистрируют перемещения, определяют предпочтения и советуют книги, музыку и фильмы… не за горами то время, когда они будут сами управлять автомобилем. Похоже, для них в этом мире нет ничего невозможного?

На самом деле пока они могут не все. Из этой книги вы узнаете о вычислительных задачах, которые мы, вероятно, никогда не научимся быстро решать. Виной тому труднейшая математическая проблема с загадочным названием «P против NP» – главный вопрос теории алгоритмов, а, может, и всей математики или даже всей науки в целом.

Математический институт Клэя присвоил ей статус задачи тысячелетия. Всего таких задач семь, и за решение каждой из них институт предлагает приз в миллион долларов. Однако за вопросом «P против NP» стоит нечто большее.

P – это класс задач, которые на компьютере решаются относительно быстро. NP – задачи, для которых мы хотим найти оптимальное решение. Равенство P и NP означает, что любую поставленную задачу можно быстро решить. В этом случае наша жизнь сразу перейдет на совершенно новый уровень; медицина, наука, индустрия развлечений шагнут далеко вперед, и почти любой процесс можно будет автоматизировать.

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

В 2008 году главный редактор журнала Communications of the ACM Моше Варди предложил мне написать о проблеме статью. Ассоциация вычислительной техники, или ACM, – это крупнейшая международная организация, объединяющая специалистов в области компьютерных наук, а ее главный научный журнал Communications of the ACM публикует статьи на интересующие компьютерное сообщество темы.

Поначалу я пытался «сбагрить» работу кому-то еще, но потом все же сдался. «Вон физики же издают популярные статьи про теорию струн, – убеждал меня Моше. – И не только статьи, а целые книги! Так что, я думаю, у нас тоже получится объяснить всем теорию сложности и ее достижения». Я писал, ориентируясь на читательскую аудиторию журнала; речь в работе шла не столько о текущем статусе проблемы, который можно было бы описать одним словом – «открыта», сколько о методах борьбы с трудоемкими задачами. Статья The Status of the P versus NP Problem вышла в сентябре 2009 года и быстро побила все рекорды по скачиванию за всю историю существования сайта журнала.

Полная версия приключений P и NP осталась за кадром, однако популярность статьи говорила о том, что момент выбран верный и настало время познакомить с подробностями не только специалистов, но и широкую публику.

Статья послужила для книги каркасом; каждый параграф в итоге разросся в целую главу. Вдохновение я черпал в Краткой истории времени Стивена Хокинга, объясняющей физику на простых примерах и занимательных историях. Хокинг обошелся без формул и терминов; я попытался сделать то же, и, надеюсь, мне удалось в доступной форме изложить суть проблемы и показать ее важность.

Формальных определений вы здесь не найдете: хороших учебников и сайтов, излагающих математическое описание проблемы и связанные с ней результаты, сейчас и так довольно много. Цель книги – дать представление о том, что могут и чего не могут дать нам вычисления в век, когда мир уже невозможно представить без компьютеров.

Итак, вперед, к классам P и NP!

Лэнс Фортноу
Иванстон, штат Иллинойс

Золотой билет

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

Как найти эти билеты? Ну, наверно, накупить как можно больше шоколадок. А потом использовать магнит. Хотя нет: ведь золото не магнитится. Тогда можно нанять пару тысяч человек, раздать им шоколадки и заставить снимать обертки. По-вашему, это глупо? Только не для Веруки Солт, которой до смерти хочется найти билет и поглядеть на шоколадную фабрику Вилли Вонка!


Рекомендуем почитать
Жженые карты

2089 год, война с террористическим движением подошла к концу, однако очаги сражений продолжают вспыхивать в странах Ближнего Востока. Получив задание вычислить и обезвредить вражескую группу, отряд специального назначния направляется в Мертвую Зону, охватывающую северное побережье Черного моря. Преследование длится не больше дня и фактически подходит к завершению, однако к ночи становится понятно, что "игра на выживание" только начинается.


Красная звездочка — храброе сердце

Витя — октябрёнок, у него на груди красная звёздочка. Но сама сказка волшебная. В ней рассказывается о необыкновенном приключении Вити, который летит на волшебном глобусе спасать негритёнка Самбо. Эта сказка и об октябрятской звёздочке: кто её носит — становится сильным и смелым.


Лечение

Космический полет был фатален для супружеской пары, Фреда и Маргарет. Их корабль разлетелся в клочья от столкновения с астероидом. Однако Маргарет обнаружила, что не умерла, хотя не может пошевелить ни одной частью тела. Голос во тьме сообщил ей, что их подобрали представители внеземной цивилизации и теперь будет проведено уникальное лечение — им восстановят утраченные части тела. Больше всего Маргарет волнует, как будет выглядеть ее лицо, потому что она боится потерять любимого Фреда.


Да не оскудеет рука дающего

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


Ум первобытного человека

Книга известного американского антрополога, лингвиста и естествоиспытателя Франца Боаса содержит его взгляды на историю развития человеческой культуры и умственных способностей человека. Автор опровергает утверждение о существовании даровитых и менее одаренных рас; он показывает, что успехи и достижения различных рас, равно как и различия в их анатомических признаках, не являются доказательством различия их умственных дарований. Боас рассматривает вопрос об устойчивости человеческих типов, исследует влияние окружающей среды и наследственности на анатомическое строение и склад ума человека.


Капиталистическое отчуждение труда и кризис современной цивилизации

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


Тайны продуктов питания

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


Социально-культурные проекты Юргена Хабермаса

В работе проанализированы малоисследованные в нашей литературе социально-культурные концепции выдающегося немецкого философа, получившие названия «радикализации критического самосознания индивида», «просвещенной общественности», «коммуникативной радициональности», а также «теоретиколингвистическая» и «психоаналитическая» модели. Автором показано, что основной смысл социокультурных концепций Ю. Хабермаса состоит не только в критико-рефлексивном, но и конструктивном отношении к социальной реальности, развивающем просветительские традиции незавершенного проекта модерна.


Вторжение: Взгляд из России. Чехословакия, август 1968

Пражская весна – процесс демократизации общественной и политической жизни в Чехословакии – был с энтузиазмом поддержан большинством населения Чехословацкой социалистической республики. 21 августа этот процесс был прерван вторжением в ЧССР войск пяти стран Варшавского договора – СССР, ГДР, Польши, Румынии и Венгрии. В советских средствах массовой информации вторжение преподносилось как акт «братской помощи» народам Чехословакии, единодушно одобряемый всем советским народом. Чешский журналист Йозеф Паздерка поставил своей целью выяснить, как в действительности воспринимались в СССР события августа 1968-го.


Сандинистская революция в Никарагуа. Предыстория и последствия

Книга посвящена первой успешной вооруженной революции в Латинской Америке после кубинской – Сандинистской революции в Никарагуа, победившей в июле 1979 года.В книге дан краткий очерк истории Никарагуа, подробно описана борьба генерала Аугусто Сандино против американской оккупации в 1927–1933 годах. Анализируется военная и экономическая политика диктатуры клана Сомосы (1936–1979 годы), позволившая ей так долго и эффективно подавлять народное недовольство. Особое внимание уделяется роли США в укреплении режима Сомосы, а также истории Сандинистского фронта национального освобождения (СФНО) – той силы, которая в итоге смогла победоносно завершить революцию.