AE 2010: 1. Vorlesung (13. April)
Eine gute Einführung zu Algorithm Engineering findet man im Antrag zum aktuell laufenden DFG-Schwerpunktprogramm Algorithm Engineering
Geschichte der Algorithmik
Von Donald Knuth stammt das berühmte Buch The Art of Computer Programming
Frank Wilczek, von dem das Zitat “If you don't make mistakes, you're not working on hard enough problems. And that's a big mistake.” stammt, erhielt 2004 den Nobelpreis für Physik.
70er- und 80er-Jahre: Die Papier- und Bleistiftjahre
- Algorithmen zur planaren Einbettung: Hopcroft & Tarjan (1974), Mehlhorn (1982)
korrigiert in Mehlhorn & Mutzel (1996)
- maximaler planarer Untergraph: Jayakumar et al. (1986, 1989), Kant (1992)
korrigiert in Jünger et al. (1997)
- Fredman & Tarjan (1987): Algorithmus für MST mit Fibonacci-Heaps
- Robertson & Seymour Papers über Graphminoren, siehe Graph Minor Theory
80er-Jahre: Erste experimentelle Vergleiche
- Bentley (1983): Programming Pearls
- Jones (1986): Experimenteller Vergleich von Priority-Queues
- Stasko & Vitter (1987): Pairing-Heaps
90er-Jahre: Beginn des Algorithm Engineering
Seit Beginn der 90er-Jahre finden in unregelmäßigen Abständen die DIMACS Implementation Challenges statt.
- Moret & Shapiro (1991): Algorithms from P to NP (Chapter 8), Addison Wesley
Moret & Shapiro (1994): in DIMACS: Computational Support for Discrete Mathematics
- Cherkassky, Goldberg, Radzig (1996): Kürzeste Wege
Die LEDA-Bibliothek wird inzwischen von Algorithmic Solutions vertrieben.
Die letzte Version des Artikels Emerging Opportunities for Theoretical Computer Science von Aho, Johnson, Karp, Kosaraju, McGeoch, Papadimitriou, Pevzner (1997) erschien in ACM SIGACT News.
Ende der 90er-Jahre: Rechnerarchitektur
- LaMarca & Ladner (1996): Optimierung von Algorithmen bzgl. Caches
- Vitter (2001): Externspeicheralgorithmen