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

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

Авторы:

Жанры: Научная литература, Компьютерная литература, Научпоп, Технические науки

Циклы: не входит в цикл

Формат: Фрагмент

Всего в книге 59 страниц. Год издания книги - 2016.

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

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

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

Читать онлайн Золотой билет


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

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

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!

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

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

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

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


С этой книгой читают
Социальное общение и демократия. Ассоциации и гражданское общество в транснациональной перспективе, 1750-1914

Что значат для демократии добровольные общественные объединения? Этот вопрос стал предметом оживленных дискуссий после краха государственного социализма и постепенного отказа от западной модели государства всеобщего благосостояния, – дискуссий, сфокусированных вокруг понятия «гражданское общество». Ответ может дать обращение к прошлому, а именно – к «золотому веку» общественных объединений между Просвещением и Первой мировой войной. Политические теоретики от Алексиса де Токвиля до Макса Вебера, равно как и не столь известные практики от Бостона до Санкт-Петербурга, полагали, что общество без добровольных объединений неминуемо скатится к деспотизму.


Поляки в Западной Сибири в конце XIX – первой четверти XX века

Книга посвящена истории польской диаспоры в Западной Сибири в один из переломных периодов истории страны. Автором проанализированы основные подходы к изучению польской диаспоры в Сибири. Работа представляет собой комплексное исследование истории польской диаспоры в Западной Сибири, основанное на материалах большого числа источников. Исследуются история миграций поляков в Сибирь, состав польской диаспоры и вклад поляков в развитие края. Особое внимание уделено вкладу поляков в развитие предпринимательства.


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

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


История инженерного дела. Важнейшие технические достижения с древних времен до ХХ столетия

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


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

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


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

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


Авиация и космонавтика 2010 10

Авиационно-исторический журнал, техническое обозрение.


Техника и оружие 1997 01

Научно-популярный журнал (согласно титульным данным). Историческое и военно-техническое обозрение.


Воробьи на Мэдисон-сквере
Автор: О Генри

Один из самых известных юмористов в мировой литературе, О. Генри создал уникальную панораму американской жизни на рубеже XIX–XX веков, в гротескных ситуациях передал контрасты и парадоксы своей эпохи, открывшей простор для людей с деловой хваткой, которых игра случая то возносит на вершину успеха, то низвергает на самое дно жизни.«Молодому человеку в стесненных обстоятельствах, если он приехал в Нью-Йорк, чтобы стать писателем, и притом заранее тщательно изучил поле боя, требуется сделать только одно.


День воскресения
Автор: О Генри

Один из самых известных юмористов в мировой литературе, О. Генри создал уникальную панораму американской жизни на рубеже XIX–XX веков, в гротескных ситуациях передал контрасты и парадоксы своей эпохи, открывшей простор для людей с деловой хваткой, которых игра случая то возносит на вершину успеха, то низвергает на самое дно жизни.«Ясно вижу, как хмурит лоб художник и грызет карандаш, когда речь заходит о том, чтобы изобразить пасхальный сюжет, – оно и понятно, ибо его профессиональные представления о тех, кто может быть причастен к этому празднику, вполне законно сводятся всего к четырем персонажам…».