Список канонических проблем

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

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

Мне не известны какие-либо хорошие онлайн-ресурсы, но основополагающая статья Карпа Сводимость среди комбинаторных задач (1972) о сокращениях и сложности, вероятно, является «каноническим» справочником по трудным задачам.

Вы смотрели страницы Википедии Категория: Вычислительные задачи и Категория: NP Завершенные задачи? Возможно, он не завершен, но выглядит хорошей отправной точкой. Википедия, похоже, неплохо разбирается в темах CS.

@rcreswick, это звучит как хорошие ссылки, но я немного стесняюсь того, о чем я думаю. (Однако, насколько я знаю, это лучшее, что есть на свете)

Я не собираюсь отмечать что-либо как принятые в надежде, что люди найдут лучшую ссылку.

А пока я собираюсь перечислить здесь несколько проблем, смело добавляю еще

Проблема сортировки Найдите порядок для набора, который является монотонным определенным образом

Проблема с упаковкой бункера разбивает набор на минимальное количество наборов, где каждое подмножество «меньше» некоторого предела

Проблема коммивояжера Найдите гамильтонов цикл во взвешенном графе с минимальным общим весом

Не думаю, что вы найдете ответы на все эти проблемы в одной книге. Я никогда не видел приличных, всеобъемлющих веб-сайтов, посвященных алгоритмам, поэтому я рекомендую вам придерживаться книг. Тем не менее, вы всегда можете получить вводный материал по текстам канонических алгоритмов (я всегда рекомендую три: CLRS, Manber, Ахо, Хопкрофт и Ульман (этот немного устарел по некоторым ключевым темам, но он настолько формален и хорошо написан) что это необходимо прочитать). Все они содержат важные комбинаторные проблемы, которые в некотором смысле являются каноническими проблемами в информатике. Изучив некоторые основы теории графов, вы сможете перейти к Сетевым потокам и линейному программированию. содержат набор методов, которые в конечном итоге решат большинство проблем, с которыми вы столкнетесь (линейное программирование с переменными, ограниченными целыми значениями, является NP-трудным). Сетевые потоки имеют дело с проблемами, определенными на графах (с взвешенными / емкостными ребрами) с очень интересными приложениями в областях, которые, казалось бы, не имеют никакого отношения к теории графов. Учебник по этому вопросу - Ахуджа, Маньянти и Орлин. Линейное программирование - это своего рода надмножество сетевых потоков и занимается оптимизацией линейного фу действия на переменные с ограничениями в виде линейной системы уравнений. Книга, в которой подчеркивается связь с сетевыми потоками, называется Базараа. Затем вы можете перейти к целочисленному программированию, очень ценному инструменту, который представляет множество естественных методов моделирования таких проблем, как упаковка контейнеров, планирование задач, задача о рюкзаке и т. д. Хорошей ссылкой будет книга Л. Уолси.

Вы, определенно, хотите посмотреть на Словарь алгоритмов и структур данных NIST. У него есть задача коммивояжера, Византийская проблема генералов, проблема обедающих философов, проблема с рюкзаком (= ваша "проблема с упаковкой бункера", я думаю), проблема с режущим материалом, проблема восьми ферзей, задача рыцарского тура, проблема занятого бобра, проблема остановки и т. д.

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

Интересно, что на codinghorror.com есть блог, в котором о некоторых из них рассказывается в виде головоломки. (Я не могу вспомнить, читал ли я книгу Смулляна, цитируемую в блоге, но он хороший составитель головоломок и философских размышлений. Мартин Гарднер, Дуглас Хофштадтер и ОН. Dudeney - другие.)

Также, возможно, посмотрите Репозиторий алгоритмов Stony Brook.

(Или поищите «комбинаторные задачи» в Google, или поищите «проблему» в Вольфрам Mathworld, или посмотрите Проблемы Гильберта, но во всех этих ссылках многие из них больше относятся к чистой математике, чем к информатике.)