===== AE 2010: 1. Vorlesung (13. April) =====

Eine gute Einführung zu Algorithm Engineering findet man im [[http://www.algorithm-engineering.de/beschreibung.pdf|Antrag]] zum aktuell laufenden DFG-Schwerpunktprogramm //[[http://www.algorithm-engineering.de/index.php?page=aktuelles&language=de|Algorithm Engineering]]//
==== Geschichte der Algorithmik ====

Von [[http://de.wikipedia.org/wiki/Donald_Ervin_Knuth|Donald Knuth]] stammt das berühmte Buch //[[http://www-cs-faculty.stanford.edu/~knuth/taocp.html|The Art of Computer Programming]]//

[[http://de.wikipedia.org/wiki/Frank_Wilczek|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: [[http://doi.acm.org/10.1145/321850.321852|Hopcroft & Tarjan (1974)]], Mehlhorn (1982)\\ korrigiert in [[http://dx.doi.org/10.1007/BF01940648|Mehlhorn & Mutzel (1996)]]

  * 3-Zusammenhangszerlegung: [[http://dx.doi.org/10.1137/0202012|Hopcroft & Tarjan (1973)]]\\ korrigiert in [[http://dx.doi.org/10.1007/3-540-44541-2_8|Gutwenger & Mutzel (2000)]]

  * maximaler planarer Untergraph: Jayakumar et al. ([[http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=1085997|1986]], [[http://dx.doi.org/10.1109/43.21845 |1989]]), [[http://www.cs.uu.nl/research/techreps/repo/CS-1992/1992-03.pdf|Kant (1992)]]\\ korrigiert in Jünger et al. ([[http://dx.doi.org/10.1007/3-540-63938-1_62|1997]])

  * [[http://doi.acm.org/10.1145/28869.28874|Fredman & Tarjan (1987)]]: Algorithmus für MST mit Fibonacci-Heaps

  * Robertson & Seymour Papers über Graphminoren, siehe //[[http://www.ams.org/journals/bull/2006-43-01/S0273-0979-05-01088-8/S0273-0979-05-01088-8.pdf|Graph Minor Theory]]//

=== 80er-Jahre: Erste experimentelle Vergleiche ===

  * Bentley (1983): //[[http://www.cs.bell-labs.com/cm/cs/pearls/|Programming Pearls]]//

  * [[http://doi.acm.org/10.1145/63238.63249|Jones (1986)]]: Experimenteller Vergleich von Priority-Queues

  * [[http://doi.acm.org/10.1145/214748.214759|Stasko & Vitter (1987)]]: Pairing-Heaps

=== 90er-Jahre: Beginn des Algorithm Engineering ===

Seit Beginn der 90er-Jahre finden in unregelmäßigen Abständen die //[[http://dimacs.rutgers.edu/Challenges/|DIMACS Implementation Challenges]]// statt.

  * Moret & Shapiro (1991): Algorithms from P to NP (Chapter 8), Addison Wesley\\ Moret & Shapiro (1994): in DIMACS: //[[http://dimacs.rutgers.edu/Volumes/Vol15.html|Computational Support for Discrete Mathematics]]//

  * [[http://dx.doi.org/10.1007/BF02592101|Cherkassky, Goldberg, Radzig (1996)]]: Kürzeste Wege

Die [[http://www.algorithmic-solutions.com/leda/|LEDA-Bibliothek]] wird inzwischen von Algorithmic Solutions vertrieben.

Die letzte Version des Artikels //[[http://doi.acm.org/10.1145/262301.262309|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 ===

  * [[http://doi.acm.org/10.1145/235141.235145|LaMarca & Ladner (1996)]]: Optimierung von Algorithmen bzgl. Caches

  * [[http://doi.acm.org/10.1145/384192.384193|Vitter (2001)]]: Externspeicheralgorithmen

\\ 
----

~~NOCACHE~~

{{page>ae-2010-footer}}