Национальный цифровой ресурс Руконт - межотраслевая электронная библиотека (ЭБС) на базе технологии Контекстум (всего произведений: 508640)
Консорциум Контекстум Информационная технология сбора цифрового контента
Уважаемые СТУДЕНТЫ и СОТРУДНИКИ ВУЗов, использующие нашу ЭБС. Рекомендуем использовать новую версию сайта.

Золотой билет. P, PN и границы возможного (451,00 руб.)

0   0
Первый авторФортноу Лэнс
АвторыЛожкина Зинаида
ИздательствоМ.: Лаборатория знаний
Страниц221
ID474211
Аннотация«Золотой билет»—великолепное введение в P/NP-проблему, в котором описаны история этой задачи и ее влияние на нашу жизнь. В этой информативной и занимательной книге Лэнс Фортноу прослеживает работу, которая велась над задачей во времена холодной войны по обе стороны «железного занавеса», и приводит примеры ее возникновения во множестве дисциплин, включая экономику, физику и биологию.
Кому рекомендованоДля студентов и специалистов в области теории вычислений, всех, интересующихся современными проблемами в математике.
ISBN978-5-00101-424-9
УДК51
ББК22.1
Фортноу, Л. Золотой билет. P, PN и границы возможного = The Golden Ticket: P, NP, and the Search for the Impossible [Электронный ресурс] / пер.: З. Ложкина, Л. Фортноу .— эл. изд. — М. : Лаборатория знаний, 2016 .— 221 с. : ил. — Пер. с англ.; Деривативное эл. изд. на основе печ. аналога (М.: Лаборатория знаний, 2016); Электрон. текстовые дан. (1 файл pdf : 221 с.); Систем. требования: Adobe Reader XI; экран 10" .— ISBN 978-5-00101-424-9 .— Режим доступа: https://rucont.ru/efd/474211

Предпросмотр (выдержки из произведения)

ISBN 978-5-00101-424-9 «Золотой билет»—великолепное введение в P/NP-проблему, в котором описаны история этой задачи и ее влияние на нашу жизнь. <...> Для студентов и специалистов в области теории вычислений, всех, интересующихся современными проблемами в математике. <...> Математический институт Клэя присвоил ей статус задачи тысячелетия. <...> NP—задачи, для которых мы хотим найти оптимальное решение. <...> Так что, я думаю, у нас тоже получится объяснить всем теорию сложности и ее достижения». <...> Задача коммивояжера З о л о то й б и л е т 12 Однако транспортный отдел попросил ее подумать еще и постараться уложиться в 17000 километров. <...> Вопрос о равенстве классов P и NP самым непосредственным образом связан с задачей быстрого поиска кратчайшего маршрута коммивояжера (и не только с ней). <...> Класс NP—это множество задач, которые мы хотим решить; класс P—задачи, которые мы умеем решать быстро. <...> Представьте, что у нас есть хороший алгоритм, который быстро разбивает заданное множество чисел на две группы с равной суммой (когда это разбиение вообще существует). <...> Вот почему проблема равенства P и NP так будоражит умы. <...> Насколько быстро можно перебрать огромное число потенциальных вариантов? <...> Впервые проблема равенства классов упоминается еще в 1956 году—в письме, которое один величайший математик XX века, Курт Гёдель, отправил другому величайшему математику XX века, Джону фон Нейману. <...> Авторы—Стивен Кук и Леонид Левин—независимо друг от друга пришли к одному и тому же вопросу, находясь по разные стороны «железного занавеса». <...> Сейчас проблема равенства классов уже стала основополагающей—причем не только в информатике, но также в биологии, медицине, экономике, физике и многих других областях. <...> Шумиха вокруг доказательства Великой теоремы Ферма, предложенного в 1994 году Эндрю Уайлсом, побудила Математический институт Клэя организовать нечто вроде конкурса по решению сложнейших открытых математических проблем. <...> В 2000 году институт опубликовал список из семи <...>
Золотой_билет._P,_PN_и_границы_возможного.—Эл._изд..pdf
УДК 51 ББК 22.1 Ф80 Фортноу Л. Ф80 Золотой билет. P, NP и границы возможного [Электронный ресурс] / Л. Фортноу ; пер. с англ. З. Ложкиной.—Эл. изд.— Электрон. текстовые дан. (1 файл pdf : 221 с.).—М. : Лаборатория знаний, 2016.—Систем. требования: Adobe Reader XI ; экран 10". ISBN 978-5-00101-424-9 «Золотой билет»—великолепное введение в P/NP-проблему, в котором описаны история этой задачи и ее влияние на нашу жизнь. В этой информативной и занимательной книге Лэнс Фортноу прослеживает работу, которая велась над задачей во времена холодной войны по обе стороны «железного занавеса», и приводит примеры ее возникновения во множестве дисциплин, включая экономику, физику и биологию. Для студентов и специалистов в области теории вычислений, всех, интересующихся современными проблемами в математике. УДК 51 ББК 22.1 Деривативное электронное издание на основе печатного аналога: Золотой билет. P, NP и границы возможного / Л. Фортноу ; пер. с англ. З. Ложкиной.—М. : Лаборатория знаний, 2016.—218 с. : ил.—ISBN 978-5-906828-68-2. В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений, установленных техническими средствами защиты авторских прав, правообладатель вправе требовать от нарушителя возмещения убытков или выплаты компенсации Copyright 2013 by Princeton University Press Все права защищены. Никакая часть этой книги не может быть воспроизведена или передана в любой форме или любыми средствами, электронными или механическими, включая фотокопирование, запись или использование средств хранения и поиска информации, без письменного разрешения Издателя. ○ c ISBN 978-5-00101-424-9 ○ Лаборатория знаний, 2016 c
Стр.5
ОГЛАВЛЕНИЕ Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Глава 1. Золотой билет . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 9 Глава 2. Совершенный мир . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 Глава 3. Классы P и NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Глава 4. Самые трудные задачи класса NP . . . . . . . . . . . 69 Глава 5. Хроника предшествующих событий . . . . . . . . . . 93 Глава 6. Преодолевая трудности . . . . . . . . . . . . . . . . . . . . . . . 114 Глава 7. Как доказать, что P = NP . . . . . . . . . . . . . . . . . . . . 138 Глава 8. Совершенно секретно . . . . . . . . . . . . . . . . . . . . . . . . . 155 Глава 9. Его величество квант . . . . . . . . . . . . . . . . . . . . . . . . . 178 Глава10. Будущее вычислений . . . . . . . . . . . . . . . . . . . . . . . . . 193 Благодарности . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 Примечания и список литературы . . . . . . . . . . . . . . . . . . . . . 205 Предметный указатель . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
Стр.219