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

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

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


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

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


Лечение

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


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

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


На траверзе — Дакар

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


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

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


Интеллигенция в поисках идентичности. Достоевский – Толстой

Монография посвящена проблеме самоидентификации русской интеллигенции, рассмотренной в историко-философском и историко-культурном срезах. Логически текст состоит из двух частей. В первой рассмотрено становление интеллигенции, начиная с XVIII века и по сегодняшний день, дана проблематизация важнейших тем и идей; вторая раскрывает своеобразную интеллектуальную, духовную, жизненную оппозицию Ф. М. Достоевского и Л. Н. Толстого по отношению к истории, статусу и судьбе русской интеллигенции. Оба писателя, будучи людьми диаметрально противоположных мировоззренческих взглядов, оказались “versus” интеллигентских приемов мышления, идеологии, базовых ценностей и моделей поведения.


Князь Евгений Николаевич Трубецкой – философ, богослов, христианин

Монография протоиерея Георгия Митрофанова, известного историка, доктора богословия, кандидата философских наук, заведующего кафедрой церковной истории Санкт-Петербургской духовной академии, написана на основе кандидатской диссертации автора «Творчество Е. Н. Трубецкого как опыт философского обоснования религиозного мировоззрения» (2008) и посвящена творчеству в области религиозной философии выдающегося отечественного мыслителя князя Евгения Николаевича Трубецкого (1863-1920). В монографии показано, что Е.


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

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


Лес. Как устроена лесная экосистема

Что такое, в сущности, лес, откуда у людей с ним такая тесная связь? Для человека это не просто источник сырья или зеленый фитнес-центр – лес может стать местом духовных исканий, служить исцелению и просвещению. Биолог, эколог и журналист Адриане Лохнер рассматривает лес с культурно-исторической и с научной точек зрения. Вы узнаете, как устроена лесная экосистема, познакомитесь с различными типами леса, характеризующимися по составу видов деревьев и по условиям окружающей среды, а также с видами лесопользования и с некоторыми аспектами охраны лесов. «Когда видишь зеленые вершины холмов, которые волнами катятся до горизонта, вдруг охватывает оптимизм.