[Termine] [Zusammenfassung] [Übungen] [Folien] [Skript] [Forum]
| Vorlesungsbeginn | 07.04.2008 |
| Übungsbeginn | 14.04.2008 |
| Wann? | Wo? | Wer? | |
| Vorlesungen: | Mo 10:15 - 11:45 | OH14, E23 | Ingo Wegener |
| Do 12:15 - 13:45 | OH14, E23 | Ingo Wegener | |
| Übungen: | Mo 14:15 - 15:45 | OH16, Raum 205 | Wim Martens |
| Di 10:15 - 11:45 | OH16, Raum E07 | Robin Nunkesser | |
| Mi 10:15 - 11:45 | OH16, Raum 205 | Alexander Munteanu | |
| Mi 12:15 - 13:45 | OH14, Raum 304 | Alexander Munteanu | |
| Fragegruppen: | Mo 16:15 - 17:45 | OH16, Raum 212 | Wim Martens |
| Mi 16:15 - 17:45 | OH14, Raum 305 | Robin Nunkesser |
Es gibt kaum einen Bereich der Informatik, der ohne Algorithmen auskommt. Auch im Grundstudium der Informatik sind sie fest verankert: in DAP 2 werden viele grundlegende Algorithmen vorgestellt, davon viele effiziente Algorithmen. In GTI bzw. TIfAI werden Grenzen der Möglichkeit, solche effizienten Algorithmen zu entwickeln, ausgelotet. Obwohl das Thema schon seit vielen Jahren intensiv behandelt wird, ist es immer noch sehr aktuell.
Es gibt viele Gründe, sich für diese Vorlesung zu interessieren. Neben den offensichtlichen Vorteilen, welche die Kenntnis effizienter Algorithmen und vor allem Entwurfstechniken für effiziente Algorithmen mit sich bringt, kann man anführen, dass die Algorithmik, ein Teilgebiet der theoretischen Informatik, wegen ihrer immensen praktischen Bedeutung mit gutem Recht als eines der praktischsten Teilgebiete der theoretischen Informatik bezeichnet werden kann. Sie darum das Potenzial, manchem, der Theorie eher skeptisch begegnet, einen gelungenen Einstieg in ein großes und spannendes Forschungsgebiet zu bieten.
Man kann Algorithmen auf verschiedene Arten systematisieren und darstellen. Wir werden hier eine Dreiteilung vornehmen. Im ersten Teil der Vorlesung werden wir uns mit effizienten Algorithmen im engeren Sinn beschäftigen und diskutieren Probleme, für die es deterministische Algorithmen gibt, die auch im Worst Case eine optimale Lösung in Polynomialzeit berechnen. Lässt sich ein Problem nicht so lösen, findet man häufig trotzdem im Worst Case in polynomieller Zeit Lösungen, die zwar nicht optimal sind, die aber eine optimale Lösung mit garantierter Mindestgüte approximieren. Solche Approximationsalgorithmen, sowohl deterministische als auch randomisierte, sind Gegenstand des zweitens Teils der Vorlesung. Findet man weder optimale Lösungen noch gute Approximationen in zufriedenstellender Zeit, kann man versuchen, heuristische Algorithmen zur Problemlösung einzusetzen. Vor allem mit randomisierten Suchheuristiken werden wir uns darum im dritten Teil der Vorlesung auseinandersetzen. In diesem Teil besprechen wir auch das Simplex-Verfahren, dass trotz exponentieller Worst-Case-Rechenzeit das Problem der linearen Programmierung in der Praxis oft schnell optimal löst. In der restlichen Zeit nehmen wir uns die Freiheit, ausgewählte Themen zu betrachten, die spannend und praktisch relevant sind, die zur Allgemeinbildung in der Informatik gehören und in anderen Vorlesungen vielleicht keine Erwähnung gefunden haben.
Hier gibt es nach den Vorlesungen die in der Vorlesung verwendeten Folien zum Nachschlagen. Sie sind als Skriptergänzung zu verstehen und sollen dazu einladen, in der Vorlesung weniger zu schreiben und mehr zu hören. Die großen Fassungen enthalten alle schrittweisen Einblendungen, die anderen Fassungen sind zum Ausdruck geeignet. Korrigierte Fassungen gibt es immer nach den Vorlesungen.