Навыки, которые вы приобретете

SPL
В чем особенность этой книги
Эта книга предназначена только для одного: постараться научить основам алгоритмизации максимально доступным способом. Воспринимайте ее как конспект лекций, которые опытный наставник по алгоритмам будет давать вам на протяжении серии индивидуальных уроков.
Существует ряд прекрасных, гораздо более традиционных и энциклопедически выверенных учебников по алгоритмам. Любой из них с пользой украсит эту серию книг дополнительными деталями, задачами и темами. Хотелось бы, чтобы вы поискали и нашли что-то полезное среди этих книг для себя. Кроме того, есть книги, которые ориентируются на программистов, ищущих готовые реализации алгоритмов на конкретном языке программирования. Множество соответствующих примеров также находятся в свободном доступе в интернете.
19.2. Возможные уровни профессиональной компетенции
Одни вычислительные задачи проще, чем другие. Суть теории NP-трудности состоит в классификации задач — выделении легкорешаемых (подобных задаче о минимальном остовном дереве) и труднорешаемых (подобных задаче коммивояжера). Эта книга нацелена как на читателей, ищущих пособие начального уровня по этой теме, так и на тех, кто стремится к компетенции профессионального уровня. В этом разделе даются рекомендации, как подойти к остальной части книги в зависимости от ваших целей и ограни­чений.
Каковы ваши текущие и желаемые уровни профессиональной компетенции в распознавании и решении NP-трудных задач?
Уровень 0: «Что такое NP-трудная задача?»
Это полное невежество — вы никогда не слышали об NP-трудности и не знаете, что многие практически релевантные вычислительные задачи считаются не поддающимися решению быстрым алгоритмом. Если я все сделал правильно, то эта книга будет доступной даже читателям уровня 0.
Уровень 1: «О, задача-то NP-трудная? Думаю, что мы должны либо переформулировать задачу (снизить поставленные нами цели), либо вложить больше ресурсов в ее решение».
Это осведомленность на уровне коктейльной вечеринки и, по меньшей мере, владение слухами об NP-трудности. Например, управляя своим софтверным проектом, используете ли вы алгоритмическую либо оптимизационную компоненты? Если да, то вам следует приобрести знания уровня 1 на случай, если один из членов вашей команды столкнется с NP-трудной задачей и захочет обсудить с вами возможные дальнейшие шаги. Для этого изучите разделы 19.3, 19.4 и 19.6.
Уровень 2: «О, задача-то NP-трудная? Дайте мне шанс применить мой алгоритмический опыт и посмотрим, насколько далеко я смогу зайти».
Разработчики ПО при достижении уровня 2 приобретают уверенность и богатый инструментарий для разработки практически полезных алгоритмов решения или аппроксимации NP-трудных задач. Серьезные программисты должны быть нацелены на этот уровень (или выше). К счастью, все алгоритмические парадигмы, которые мы развернули в предыдущих частях серии, также полезны для продвижения к NP-трудным задачам. Главы 20 и 21 приведут вас к уровню 2, в разделе 19.4 вы найдете обзор, а в главе 24 — исследование инструментария уровня 2 и его применение.
Уровень 3: «Расскажите поподробнее о задаче. [...внимательно слушает.. .] Мои соболезнования, она — NP-трудная».
Вы можете быстро распознавать NP-трудность: знаете несколько известных NP-трудных задач и можете доказать NP-трудность дополнительных задач. Эти навыки позволяют вам консультировать по алгоритмическим вопросам коллег, студентов или инженеров в промышленности. Глава 22 содержит курс молодого бойца для повышения вашего уровня до 3, а раздел 19.5 — обзор.
Уровень 4: «Давайте я вам объясню вот тут на доске предположение, что P ≠ NP».
Самый продвинутый уровень предназначен для начинающих теоретиков и тех, кто ищет строгого математического понимания NP-трудности и рассмотрения вопроса «P против NP». Если этот уровень вас не отпугивает, прочтите дополнительную главу 23.
19.3. «Легкие» и «трудные» задачи
Противопоставление «легкой» и «трудной» задач в теории NP-трудности простыми словами звучит так:

Это краткое изложение NP-трудности упускает из виду несколько важных тонкостей (см. раздел 19.3.9). Но если через десять лет о смысле NP-трудности вы вспомните только эти несколько слов, то они будут самыми точными.
19.3.1. Полиномиально-временные алгоритмы
Чтобы перейти к определению «легкой» задачи, давайте вспомним время выполнения некоторых известных алгоритмов (из предыдущих частей серии):

Точный смысл n и m зависит от конкретной задачи, но во всех случаях они связаны с размером входных данных. Согласно таблице, хотя время выполнения алгоритмов варьируется, все они зависят от размера входных данных в рамках полиномиальной функции. В общем случае:

Все шесть алгоритмов являются полиномиально-временными (с достаточно малыми экспонентами d).13 Все ли естественные алгоритмы выполняются за полиномиальное время? Нет. Например, для многих задач исчерпывающий поиск выполняется за время, экспоненциально зависящее от размера входных данных (как указано во второй сноске к задаче о минимальном остовном дереве). В полиномиально-временных алгоритмах, которые мы ранее изучили, есть кое-что особенное.
19.3.2. Полиномиальное время против экспоненциального
Не забывайте, что любая экспоненциальная функция в конечном счете растет намного быстрее любой полиномиальной функции. Между типичным полиномиальным и экспоненциальным временем выполнения существует огромная разница, даже для очень малых экземпляров. Рассмотрите график, на котором изображены полиномиальная функция 100 n2 и экспоненциальная функция 2n.
Закон Мура утверждает, что вычислительная мощность, доступная по данной цене, удваивается каждые 1–2 года. Означает ли это, что разница между полиномиально- и экспоненциально-временными алгоритмами со временем исчезнет? На самом деле наоборот! Вычислительные амбиции растут вместе с вычислительной мощностью, и с течением времени мы видим все более крупные размеры входных данных и страдаем от все более огромной пропасти между полиномиальным и экспоненциальным периодами выполнения.
Представьте фиксированный бюджет времени, например час или день. Как масштабируется поддающийся решению размер входных данных вместе с добавочной вычислительной мощностью? С полиномиально-временным алгоритмом он увеличивается на постоянный коэффициент (например, с 1 000 000 до 1 414 213) с каждым удвоением вычислительной мощности.14 С алгоритмом, который работает со временем, пропорциональным 2n, где n — это размер входных данных, каждое удвоение вычислительной мощности увеличивает поддающийся решению размер входных данных только на единицу (например, с 1 000 000 до 1 000 001)!

19.3.3. Легкорешаемые задачи
Теория NP-трудности определяет, что «легкие» задачи поддаются решению полиномиально-временным алгоритмом или, что эквивалентно, алгоритмом, для которого поддающийся решению размер входных данных (для фиксированного бюджета времени) масштабируется мультипликативно вместе с увеличением вычислительной мощности:

Например, все шесть перечисленных задач поддаются решению за полиномиальное время.
Технически алгоритм (бесполезный на практике), который выполняется за время
Технически алгоритм (бесполезный на практике), который выполняется за время O (n100) на n-размерных входных данных, считается полиномиально-временным, и задача, решенная таким алгоритмом, квалифицируется как поддающаяся решению за полиномиальное время. Если перевернуть это утверждение, окажется, что если задача, такая как задача коммивояжера, не поддается решению за полиномиальное время, то не существует даже O (n100)-временного или O (n10 000)-временного алгоритма, который ее решит (!).

19.3.4. Относительная труднорешаемость
Предположим, вы заподозрили, что задача, такая как задача коммивояжера, «не является легкой», имея в виду, что она не поддается решению любым полиномиально-временным алгоритмом (независимо от того, насколько крупным является полином). Как это доказать? Самым убедительным аргументом, конечно, будет герметичное математическое доказательство. Но статус задачи коммивояжера остается в подвешенном состоянии: никто не нашел полиномиально-временного алгоритма, который ее решает, или доказательства, что такого алгоритма не существует.
Как развить теорию, которая с пользой дифференцирует «легкие» и «трудные» задачи при нашем недостаточном понимании всех возможностей алгоритмов? Блестящая идея теории NP-трудности состоит в классификации задач на основе их относительной (а не абсолютной) трудности и объявления задачи «трудной», если она «по меньшей мере так же трудна, как» подавляющее число других нерешенных задач.
19.3.5. Трудные задачи
Безуспешные попытки решить задачу коммивояжера (раздел 19.1.3) дают косвенные свидетельства, что эта задача, возможно, не решается за полиномиальное время.

Есть ли более убедительный аргумент? Основная идея NP-трудности состоит в том, чтобы показать, что такая задача, как задача коммивояжера, по меньшей мере так же трудна, как и огромное количество нерешенных задач из множества различных научных областей. По сути, в этих задачах легко распознаются решения, стоит только вам понять задачу. А значит, гипотетический полиномиально-временной алгоритм для задачи коммивояжера автоматически будет решать и остальные нерешенные задачи!

В сущности, теория NP-трудности показывает, что тысячи вычислительных задач являются замаскированными вариантами одной и той же задачи, и полиномиально-временной алгоритм для одной из NP-трудных задач решит все остальные.
Мы называем задачу NP-трудной, если есть веские свидетельства труднорешаемости в указанном выше смысле:

Эта идея будет полностью подтверждена в разделе 23.3.4. А пока мы поработаем с предварительным определением NP-трудности в терминах широко известного математического предположения, что P ≠ NP.
19.3.6. Предположение, что P ≠ NP
Возможно, вы слышали о предположении, что P ≠ NP. Что оно собой представляет? Раздел 23.4 содержит его точную математическую формулировку, но на данный момент мы остановимся на неформальной версии, которая звучит как девиз при проверке домашнего задания:

Здесь P и NP относятся соответственно к задачам, которые могут быть решены с нуля за полиномиальное время, и к тем задачам, решения которых могут быть проверены за полиномиальное время (формальные определения P и NP в главе 23).
Конечно, проверка предложенного кем-то решения судоку или кенкен выглядит проще самостоятельного разбора головоломки. Как и легко проверить, что предложенный кем-то тур коммивояжера является хорошим (с суммарной стоимостью, скажем, не более 1000), просуммировав стоимости его ребер. Не ясно, как быстро можно придумать такой тур с нуля. Поэтому пояснение ниже настаивает: предположение, что P ≠ NP, является истинным.
Более подробно с книгой можно ознакомиться на сайте издательства
» Оглавление
» Отрывок
Для Хаброжителей скидка 25% по купону — Алгоритмы
По факту оплаты бумажной версии книги на e-mail высылается электронная книга.
===========
Источник:
habr.com
===========
Похожие новости:

• [Алгоритмы, Машинное обучение, Исследования и прогнозы в IT, Искусственный интеллект] Исследователи изучают, как GPT-3 разбирает входящую почту
  
• [Программирование, Алгоритмы, Go] Algorithms in Go: Dutch National Flag
  
• [Алгоритмы, Сжатие данных, Мониторы и ТВ, Электроника для начинающих] Что такое HDR10+? Разбор
  
• [Алгоритмы, Машинное обучение, История IT] Рекомендательный движок за 2 строчки кода
  
• [Программирование, C++, Алгоритмы, Математика] Пишем свой парсер математических выражений и калькулятор командной строки (перевод)
  
• [Алгоритмы, Математика, Научно-популярное] Математик-пенсионер, «хакнувший» лотерею
  
• [Программирование, Проектирование и рефакторинг, API, Google API] Проектирование API: почему для представления отношений в API лучше использовать ссылки, а не ключи (перевод)
  
• [Python, Профессиональная литература] Книга «Секреты Python Pro»
  
• [Программирование, Алгоритмы, Программирование микроконтроллеров, Бизнес-модели, Визуальное программирование] Умеет ли человечество писать алгоритмы? Безошибочные алгоритмы и язык ДРАКОН. Сенатор: они находились в летающих гробах
  
• [Python, Программирование, Алгоритмы, Машинное обучение, Искусственный интеллект] Собираем нейросети. Классификатор животных из мультфильмов. Без данных и за 5 минут. CLIP: Обучение без Обучения + код

Теги для поиска: #_algoritmy (Алгоритмы), #_professionalnaja_literatura (Профессиональная литература), #_kniga (книга), [url=https://torrents-local.xyz/search.php?nm=%23_blog_kompanii_izdatelskij_dom_«piter»&to=0&allw=0&o=1&s=0&f%5B%5D=820&f%5B%5D=959&f%5B%5D=958&f%5B%5D=872&f%5B%5D=967&f%5B%5D=954&f%5B%5D=885&f%5B%5D=882&f%5B%5D=863&f%5B%5D=881&f%5B%5D=860&f%5B%5D=884&f%5B%5D=865&f%5B%5D=873&f%5B%5D=861&f%5B%5D=864&f%5B%5D=883&f%5B%5D=957&f%5B%5D=859&f%5B%5D=966&f%5B%5D=956&f%5B%5D=955]#_blog_kompanii_izdatelskij_dom_«piter» (
Блог компании Издательский дом «Питер»
)[/url], #_algoritmy (
Алгоритмы
), #_professionalnaja_literatura (
Профессиональная литература
)