Handbuch fortgeschrittener Algorithmen

11

Ich suche nach Ressourcen (vorzugsweise einem Handbuch) zu fortgeschrittenen Themen in Algorithmen (Themen, die über das hinausgehen, was in Algorithmenlehrbüchern wie CLRS und DPV behandelt wird).

Die Art von Material, das zum Unterrichten von Themen im Algorithmuskurs wie Erik Demaine und David Kargers Kurs für fortgeschrittene Algorithmen verwendet werden kann .

Ressourcen, die einen Überblick über das Gebiet geben würden (wie ein Handbuch), sind vorzuziehen, aber auch fokussiertere Ressourcen wie Vijay Vaziranis Buch "Approximation Algorithms" sind in Ordnung.

Kaveh
quelle
Dies ähnelt meiner vorherigen Frage zu Datenstrukturen: Handbuch für fortgeschrittene Datenstrukturen . Ich möchte sie als Zeiger für meine Schüler verwenden, um mehr über fortgeschrittene Themen in Algorithmen zu erfahren. Ressourcen, die online für Studenten verfügbar sind, sind vorzuziehen.
Kaveh
Durchsuchen Sie die MIT-Archive .
Tommy
1
Johan Håstad hat (auch) Vorlesungsunterlagen zu fortgeschrittenen Algorithmen: nada.kth.se/~johanh/algnotes.pdf
Huck Bennett

Antworten:

6

Das Design von Approximationsalgorithmen von Williamson & Shmoys ( http://www.designofapproxalgs.com/ ) ist ein großartiges Buch für viele Approximationsmethoden wie gierige Algorithmen, semidefinite Programmierung usw. Außerdem werden einige Themen innerhalb der Komplexität behandelt, die eng miteinander verbunden sind im Zusammenhang mit Approximationsalgorithmen (Inapproximierbarkeit, Unique Games-basierte Härte von MAX-CUT).

rahulmehta95
quelle
5

Die folgenden aktuellen Handbücher sind möglicherweise von Interesse. Das Themenspektrum geht weit über CLRS hinaus und das Material eignet sich gut für Absolventen und Doktoranden. Studenten, obwohl Sie einige ausgewählte Themen für fortgeschrittene Studenten auswählen können.

Handbuch zu Algorithmen und Theorie der Berechnung Zweite Ausgabe (Spezielle Themen und Techniken)

Handbuch angewandter Algorithmen zur Lösung wissenschaftlicher, technischer und praktischer Probleme

Handbuch der Approximationsalgorithmen und Metaheuristik 

Massimo Cafaro
quelle
Rückblick & Inhaltsverzeichnis des 1. Ref. Atallah / Blanton
vzn
4

Ich mochte "Algorithmics for Hard Problems" von Juraj Hromkovic

n00b
quelle
4

Schauen Sie sich die Encyclopedia of Algorithms von Kao (Herausgeber) an. Es enthält über 500 Einträge und viele von ihnen enthalten erweiterte Algorithmen.

Mohammad Al-Turkistany
quelle
4

Computergeometrie: Mark de Berg, Marc van Kreveld, Mark Overmars und Otfried Cheong. Computergeometrie: Algorithmen und Anwendungen; Kursnotizen von David Mount .

Randomisierte Algorithmen: Motwani und Raghavan. Randomisierte Algorithmen; Ausgezeichnete Noten von James Aspnes ; Mitzenmacher und Upfal. Wahrscheinlichkeit und Berechnung.

Netzwerkflüsse: Ahuja, Magnanti und Orlin. Netzwerkflüsse.

Approximationsalgorithmen: Dorit Hochbaum. Approximationsalgorithmen für NP-harte Probleme. 

Verhexen
quelle
1
Da es möglicherweise kein einziges "Handbuch für fortgeschrittene Algorithmen" gibt, wäre eine Community-Wiki-Antwort in dieser Richtung (nach dem Thema für fortgeschrittene Algorithmen) hilfreich.
Huck Bennett
O(mn)
0

Betrachten Sie CS G399: Gems of Theoretical Computer Science. Vorlesungsnotizen Frühjahr 16 von Viola. Es ist eher eine beweiszentrierte Perspektive, aber die meisten sind im Wesentlichen fortschrittliche Algorithmen in wichtigen Grenzforschungsbereichen. (Beachten Sie auch, dass Beweise für untere Grenzen als Komprimierungsalgorithmen angesehen werden können.)

Dieser Kurs behandelt einige der aufregendsten und jüngsten Fortschritte in der theoretischen Informatik. Es präsentiert aktuelle Ergebnisse zu aktiven Forschungsbereichen und vermittelt verwandte Proof-Techniken. Eine vorläufige Liste von Themen enthält:

  • Untergrenzen für Schaltungen mit konstanter Tiefe.
  • Der Nisan-Wigderson-Pseudozufallsgenerator.
  • Kryptographie in konstanter Parallelzeit.
  • Die Komplexität der Nash-Gleichgewichte.
  • Ungerichtete Konnektivität im logarithmischen Raum (SL = L).
  • Kommunikationskomplexität.
  • Primes ist in P.
  • Schnelle Matrixmultiplikation.
vzn
quelle
2
schöner Kurs, aber viel breiter als das, was das OP verlangte
Alessandro Cosentino