Лэнс Фотноу - Золотой билет. P, NP и границы возможного

Тут можно читать онлайн Лэнс Фотноу - Золотой билет. P, NP и границы возможного - бесплатно ознакомительный отрывок. Жанр: Прочая научная литература, издательство Литагент БИНОМ. Лаборатория знаний, год 2016. Здесь Вы можете читать ознакомительный отрывок из книги онлайн без регистрации и SMS на сайте лучшей интернет библиотеки ЛибКинг или прочесть краткое содержание (суть), предисловие и аннотацию. Так же сможете купить и скачать торрент в электронном формате fb2, найти и слушать аудиокнигу на русском языке или узнать сколько частей в серии и всего страниц в публикации. Читателям доступно смотреть обложку, картинки, описание и отзывы (комментарии) о произведении.

Лэнс Фотноу - Золотой билет. P, NP и границы возможного краткое содержание

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

Золотой билет. P, NP и границы возможного - читать онлайн бесплатно ознакомительный отрывок

Золотой билет. P, NP и границы возможного - читать книгу онлайн бесплатно (ознакомительный отрывок), автор Лэнс Фотноу
Тёмная тема
Сбросить

Интервал:

Закладка:

Сделать

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

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

«Пути, деревья и цветы» дали нам не только эффективный способ решения задачи о паросочетаниях для случая произвольной схемы. В группе из 100 человек алгоритм Эдмондса находит максимальное паросочетание примерно за 100 4, т. е. 100000000 (сто миллионов) шагов, что для современного компьютера сущий пустяк. Методичный перебор всех возможных сочетаний вылился бы примерно в два квинвигинтиллиона шагов, а один квинвигинтиллион – это, между прочим, единица и 78 нулей! В работе Эдмондса есть довольно длинное отступление на тему эффективных алгоритмов. Понимая, что для такого, в сущности, интуитивного понятия, как эффективность, подобрать полноценное формальное определение очень сложно, Эдмондс все-таки предлагает некий критерий. Он называет алгоритм эффективным, если тот находит решение за «алгебраическое» время, т. е. время, «алгебраически» зависящее от размера входных данных. Для 100 человек это может быть, к примеру, 100 4, 100 2или 100 12. В дальнейшем класс задач, для которых существуют такие алгоритмы, получил обозначение «P» – от слова «полиномиальный», заменившего эдмондсовское понятие «алгебраический». Таким образом, класс P представляет собой все многообразие задач, которые можно решить относительно быстро. Ну что ж – в споре «P против NP» мы выслушали мнение первой стороны.

Конец ознакомительного фрагмента.

Текст предоставлен ООО «ЛитРес».

Прочитайте эту книгу целиком, на ЛитРес.

Безопасно оплатить книгу можно банковской картой Visa, MasterCard, Maestro, со счета мобильного телефона, с платежного терминала, в салоне МТС или Связной, через PayPal, WebMoney, Яндекс.Деньги, QIWI Кошелек, бонусными картами или другим удобным Вам способом.

Примечания

1

Перевод: М. Барон, Е. Барон.

2

Мое число Эрдёша равно двум, поскольку у меня имеются совместные публикации с тремя его соавторами. В единицу оно уже вряд ли когда-нибудь превратится: Пал Эрдёш умер в 1996 году. Актерский опыт у меня отсутствует (талант, впрочем, тоже), так что мое число Бэйкона не определено.

Тёмная тема
Сбросить

Интервал:

Закладка:

Сделать


Лэнс Фотноу читать все книги автора по порядку

Лэнс Фотноу - все книги автора в одном месте читать по порядку полные версии на сайте онлайн библиотеки LibKing.




Золотой билет. P, NP и границы возможного отзывы


Отзывы читателей о книге Золотой билет. P, NP и границы возможного, автор: Лэнс Фотноу. Читайте комментарии и мнения людей о произведении.


Понравилась книга? Поделитесь впечатлениями - оставьте Ваш отзыв или расскажите друзьям

Напишите свой комментарий
x