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

Question

Кто-нибудь знает хороший справочник по каноническим проблемам CS?

Я думаю о таких вещах, как «проблема сортировки», «проблема упаковки в мусорное ведро», «серьезная проблема продавца» и тому подобное.

редактировать: веб-сайты предпочтительнее

Answer 1

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

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

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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

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

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

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

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

Answer 6

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

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

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

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

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

Трудная задача продавца Найти гамильтонов цикл в весовом графике с минимальным общим весом