kanonische Probleme Liste

Question

Kennt jemand eine gute Referenz für kanonische CS Probleme?

Ich denke an Dinge wie "das Sortierproblem", "das Fach Verpackung Problem", "die travailing Verkäufer Problem" und was nicht.

edit: Websites

bevorzugt

Answer 1

Sie können wahrscheinlich die beste in einem Algorithmen Lehrbuch finden wie Introduction to Algorithms. Obwohl ich dieses Buch nie gelesen habe, ist es sehr bekannt dafür, gründlich zu sein und würde wahrscheinlich die meisten der Probleme enthalten, denen Sie wahrscheinlich begegnen werden.

Answer 2

"Computers and Intractability: A guide to the theory of NP-Completeness" von Garey und Johnson ist eine gute Referenz für diese Art von Sache, obwohl die "gelösten" Probleme (in P) offensichtlich nicht viel Aufmerksamkeit in dem Buch gegeben.

Mir sind keine guten Online-Ressourcen bekannt, aber Karps grundlegende Arbeit Reducibility among Combinatorial Problems (1972) über Reduktionen und Komplexität ist wahrscheinlich die "kanonische" Referenz für harte Probleme.

Answer 3

Haben Sie sich die Seiten Category:Computational problems und Category:NP Complete Problems von Wikipedia angesehen? Es ist wahrscheinlich nicht vollständig, aber sie sehen wie gute Startpunkte aus. Wikipedia scheint in CS-Themen ziemlich gut zu sein.

Answer 4

@rcreswick die klingen wie gute Referenzen, fallen aber ein bisschen schüchtern von dem, woran ich denke. (Ich weiß jedoch, es ist das Beste, was es gibt)

Ich werde nichts als akzeptiert in der Hoffnung, dass die Menschen eine bessere Referenz finden könnte markieren.

Inzwischen werde ich hier ein paar Probleme verzeichnen, fiel auf mehr

Das Sortierproblem hinzufügen einen Auftrag für einen Satz finden, die in einer bestimmten Art und Weise

Die monotone ist bin packing Problem Partition ein Satz in eine minimale Anzahl von Sätzen, wobei jede Teilmenge ist „kleiner“ als irgendeine Grenze

Das travailing Verkäufer Problem, einen Hamilton-Zyklus in einem weig finden hted graph mit dem minimalen Gesamtgewicht

Answer 5

Ich glaube nicht, dass Sie die Antworten auf all diese Probleme in nur einem Buch finden werden. Ich habe noch nie eine anständige, umfassende Website zu Algorithmen gesehen, daher würde ich Ihnen empfehlen, sich an die Bücher zu halten. Das heißt, Sie können immer einleitendes Material über kanonische Algorithmustexte bekommen (es gibt immer drei, die ich normalerweise empfehle: CLRS, Manber, Aho, Hopcroft and Ullman (dieses ist in einigen Schlüsselthemen ein bisschen veraltet, aber es ist so formell und gut geschrieben (Es ist ein Pflichtlektüre.) Alle von ihnen enthalten wichtige kombinatorische Probleme, die in gewisser Hinsicht kanonische Probleme in der Informatik sind.Nachdem Sie einige Grundlagen in der Graphentheorie gelernt haben, können Sie zu Netzwerkflüssen und linearer Programmierung wechseln Sie umfassen eine Reihe von Techniken, die letztendlich die meisten Probleme lösen werden (lineares Programmieren mit den auf ganzzahlige Werte beschränkten Variablen ist NP-schwer.) Netzwerkflüsse behandeln Probleme, die auf Graphen (mit gewichteten/kapazitierten Kanten) mit sehr interessanten Anwendungen definiert sind in Bereichen, die scheinbar keine Beziehung zur Graphentheorie haben, das Lehrbuch dazu ist Ahuja, Magnanti and Orlin's. Lineare Programmierung ist eine Art Obermenge von Netzwerkflüssen und befasst sich mit der Optimierung einer linearen Funktion auf Variablen, die Beschränkungen in Form eines linearen Gleichungssystems unterliegen.Ein Buch, das die Beziehung zu Netzwerkflüssen hervorhebt, ist Bazaraa's. Dann können Sie mit der Integer-Programmierung fortfahren, einem sehr nützlichen Werkzeug, das viele natürliche Techniken für die Modellierung von Problemen wie Müllbeutel, Aufgabenplanung, Rucksackproblem usw. bietet. Eine gute Referenz wäre L. Wolsey's Buch.

Answer 6

Sie definitiv wollen NIST sehen Dictionary of Algorithms and Data Structures. Es hat die traveling salesman problem, die Byzantine generals problem, die dining philosophers' problem, die knapsack problem (= Ihre "Bin Packing Problem", glaube ich), die cutting stock problem, die eight queens problem, die knight's tour problem, die busy beaver problem, die halting problem, etc. etc.

Es hat nicht die firing squad synchronization problem (ich bin überrascht über diese Unterlassung) oder die Jeep problem (mehr Logistik als Informatik).

Interessanterweise gibt es einen Blog auf codinghorror.com, der über einige davon in Puzzleform spricht. (Ich kann mich nicht erinnern, ob ich Smullyan Buch im Blog zitiert gelesen haben, aber er ist ein guter Compiler Rätsel & philosophischen Überlegungen. Martin Gardner und Douglas Hofstadter und H.E. Dudeney sind andere.)

vielleicht Überprüfen Sie auch die Stony Brook Algorithm Repository.

(oder „kombinatorische Probleme“ auf Google nachschlagen oder bei Hilbert's problems für „Problem“ in Wolfram Mathworld oder suchen Sie suchen, aber in all diesen Links viele von ihnen sind reine Mathematik als Informatik.)