|
|
 |
LS 2 Home
Lehre Service Anreise Mitarbeiter Kontakt Interna
Externe Links Universität DortmundFakultät für InformatikSFB 531SFB 475DFG-Schwerp. Nr. 1126Studieninformation
|
WahlpflichtvorlesungEffiziente Algorithmen und KomplexitätstheorieSommersemester 2007Thomas Jansen
[Termine] [Zusammenfassung] [Übungen] [Folien] [Skript] [Diskussionsforum]
Termine
ZusammenfassungEs 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. Zur Vorlesung wird ein Skript erscheinen, das allerdings nicht als Grundlage zum eigenständigen Studium und Ersatz für die Vorlesung gedacht ist. Es enthält kaum Beispiele, Bilder und anschauliche Erklärungen, diese werden in der Vorlesung präsentiert, man findet sie in den Folien, die vorlesungsbegleitend verfügbar gemacht werden. Zusammen mit diesen Folien erlaubt es das konzentrierte Zuhören, ohne mitschreiben zu müssen.
ÜbungenVorlesungsbegleitend finden Übungen statt, die regelmäße aktive Teilnahme an einer Übungsgruppe wird dringend empfohlen. In den Übungen können Fragen zur Vorlesung diskutiert werden, außerdem gibt es regelmäßig Übungsaufgaben, die zu Hause gelöst und deren Lösungen in den Übungsgruppen präsentiert werden sollen. Informationen zur Organisation und dem Ablauf der Übungen sowie der Ausgabe der Übungsblätter findet man auf dem ersten Übungsblatt.
FolienHier gibt es die 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, das Datum der letzten Aktualisierung ist vermerkt. Auf besonderen Wunsch gibt es die Folien auch noch jeweils in zwei "kleineren" Versionen, nämlich mit zwei bzw. vier logischen Seiten auf einer physikalischen Seite. Die Dateien werden mit einem kleinen Script erstellt, das hoffentlich meistens funktioniert. Ihr findet sie direkt im Folienverzeichnis, die Dateinamen sind hoffentlich selbsterklärend.
SkriptEin Skript zur Vorlesung entstand vorlesungsbegleitend. Es gibt hier jetzt nur noch die Gesamtfassung, die alle aktuellen Fassungen enthält, sie datiert auf dem 6.11.2007.
oben
last change: 6.11.2007 |