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

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

«Золотой билет» – великолепное введение в 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 год, война с террористическим движением подошла к концу, однако очаги сражений продолжают вспыхивать в странах Ближнего Востока. Получив задание вычислить и обезвредить вражескую группу, отряд специального назначния направляется в Мертвую Зону, охватывающую северное побережье Черного моря. Преследование длится не больше дня и фактически подходит к завершению, однако к ночи становится понятно, что "игра на выживание" только начинается.


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

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


Лечение

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


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

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


Россия и Дон. История донского казачества 1549—1917

Предлагаем вашему вниманию адаптированную на современный язык уникальную монографию российского историка Сергея Григорьевича Сватикова. Книга посвящена донскому казачеству и является интересным исследованием гражданской и социально-политической истории Дона. В работе было использовано издание 1924 года, выпущенное Донской Исторической комиссией. Сватиков изучил колоссальное количество монографий, общих трудов, статей и различных материалов, которые до него в отношении Дона не были проработаны. История казачества представляет громадный интерес как ценный опыт разрешения самим народом вековых задач построения жизни на началах свободы и равенства.


Император Алексей Ι Комнин и его стратегия

Монография доктора исторических наук Андрея Юрьевича Митрофанова рассматривает военно-политическую обстановку, сложившуюся вокруг византийской империи накануне захвата власти Алексеем Комнином в 1081 году, и исследует основные военные кампании этого императора, тактику и вооружение его армии. выводы относительно характера военно-политической стратегии Алексея Комнина автор делает, опираясь на известный памятник византийской исторической литературы – «Алексиаду» Анны Комниной, а также «Анналы» Иоанна Зонары, «Стратегикон» Катакалона Кекавмена, латинские и сельджукские исторические сочинения. В работе приводятся новые доказательства монгольского происхождения династии великих Сельджукидов и новые аргументы в пользу радикального изменения тактики варяжской гвардии в эпоху Алексея Комнина, рассматриваются процессы вестернизации византийской армии накануне Первого Крестового похода.


Продолжим наши игры+Кандибобер

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


Краткая история насекомых. Шестиногие хозяева планеты

«Любая история, в том числе история развития жизни на Земле, – это замысловатое переплетение причин и следствий. Убери что-то одно, и все остальное изменится до неузнаваемости» – с этих слов и знаменитого примера с бабочкой из рассказа Рэя Брэдбери палеоэнтомолог Александр Храмов начинает свой удивительный рассказ о шестиногих хозяевах планеты. Мы отмахиваемся от мух и комаров, сражаемся с тараканами, обходим стороной муравейники, что уж говорить о вшах! Только не будь вшей, человек остался бы волосатым, как шимпанзе.


Историческое образование, наука и историки сибирской периферии в годы сталинизма

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


Технологии против Человека. Как мы будем жить, любить и думать в следующие 50 лет?

Эксперты пророчат, что следующие 50 лет будут определяться взаимоотношениями людей и технологий. Грядущие изобретения, несомненно, изменят нашу жизнь, вопрос состоит в том, до какой степени? Чего мы ждем от новых технологий и что хотим получить с их помощью? Как они изменят сферу медиа, экономику, здравоохранение, образование и нашу повседневную жизнь в целом? Ричард Уотсон призывает задуматься о современном обществе и представить, какой мир мы хотим создать в будущем. Он доступно и интересно исследует возможное влияние технологий на все сферы нашей жизни.