Informationen zur Vorlesung

Einführung in
»Algorithmen und Komplexität«

Sommersemester 2004

Inhalt

• Klassen P und NP, Zeitkomplexität
• NP-Vollständigkeit
• Satz von Cook
• Reduktionen
• Heuristiken, Backtracking, Branch and Bound
• Approximationsalgorithmen

Termine

Vorlesung

von: Friedhelm Meyer auf der Heide
Mo. 11-13, Raum C1, wöchentlich

Zentralübung

von: Friedhelm Meyer auf der Heide
Mo. 13-14, Raum C1, zweiwöchentlich und bei Bedarf

Übungen

von: wiss. Mitarbeitern und studentischen Hilfskräften Annika Bölte, Matthias Fischer, Martin Meeser, Norbert Sondag, Tim Süß, Klaus Volbert

Die Übungen (Präsenzübung) finden zweiwöchentlich statt, und zwar die Übungsgruppen g: Ü1, Ü3, Ü5, Ü7, Ü9, Ü11, Ü13, Ü15 in ungeraden Kalenderwochen und die Übungsgruppen u: Ü2, Ü4, Ü6, Ü8, Ü10, Ü12, Ü14, Ü16 geraden Kalenderwochen. Die Vorlesung und die ersten Präsenzübungen (Ü1, Ü3) beginnen am Montag, 19.4.04. Das erste Hausaufgabenblatt erscheint am 19.4.04. Die erste Zentralübung findet am 10.5.04 statt.

Prüfungstermine

Erste Klausur

Die erste gemeinsame Klausur über den Stoff dieser Vorlesung und den der vorhergehenden Veranstaltung "Berechenbarkeit und Formale Sprachen" (WS 03/04) findet am 10.08.04 statt (Zeit: 13:00 - 15:00 Uhr, ggfs. bis 15:30, Räume: Sporthalle, AudiMax). Lehramtsstudierende und Austauschstudierende schreiben diese Klausur nicht mit! Die Klausureinsicht findet am 1.9.04 im Raum F1.110 / F1.310 ab 11.00 Uhr statt. Ihre vorläufigen Ergebnisse können Sie ab Donnerstag, 19.8.04 in Ihrem StudInfo{flex} Account einsehen.

Zweite Klausur

Die zweite Klausur (Wiederholertermin) findet am 02.10.04 statt (Zeit: 9:00 - 11:00 Uhr, Räume: AudiMax, C1, C2). Die Anmeldung zur zweiten Klausur erfolgt über ihren StudInfo{flex} Account und ist freigeschaltet. Wenn Sie sich in StudInfo{flex} angemeldet haben, können Sie dort unter Prüfungsart ein Formular runterladen, das Sie unterschreiben und uns zukommen lassen müssen (Post, Fax, oder Abgabe bei uns, siehe Hinweis auf dem Formular).

Mündliche Prüfung für Lehramtsstudierende

Die mündlichen Prüfungstermine für Lehramtsstudierende und Austauschstudierende über diese  Vorlesung stehen fest: 3.8.04, 4.8.04, 5.10.04 und 6.10.04. Die Anmeldung (ggfs. mit Terminwunsch) erfolgt bis zum 29.7.04 durch E-Mail an Matthias Fischer (mafi@upb.de). Die Prüfungen sind mündliche Einzelprüfungen. Die genauen Zeiten legen wir nach dem 29.7.04 fest und teilen Sie Ihnen dann per E-Mail mit.

Dritte Klausur

• In Zukunft wird die Vorlesung "Berechenbarkeit und Formale Sprachen" und diese Veranstaltung, "Algorithmen und Komplexität", in einer einzigen einsemstrigen Veranstaltung "Einführung in Berechenbarkeit, Komplexität und formale Sprachen" stattfinden. Es wird im Anschluß an die Vorlesung zu der neuen Veranstaltung zwei Klausuren mit jeweils 3h Dauer geben.
• Wir bieten Ihnen zu dieser Veranstaltung eine dritte Klausur im Umfang von 2 Stunden an. Die zu dieser Vorlesung erworbenen Bonuspunkte werden Ihnen angerechnet. Die Anmeldung zur dritten Klausur erfolgt über Ihren Account zu dieser Veranstaltung. Dort melden Sie sich unter "3. Klausur" an, d.h. Sie benötigen keinen neuen account in der Nachfolgeveranstaltung (außer Sie wollen die neue Veranstaltung hören und am Übungsbetrieb teilnehmen).
• Die dritte Klausur wird zeitgleich mit der ersten Klausur der neuen Veranstaltung stattfinden. Da die Dauer der beiden Klausuren unterschiedlich ist (2h/3h), handelt es sich bei den beiden Klausuren um unterschiedliche Klausuren.
• Studierende, die an BFS/AuK (03/04) teilgenommen haben und auch an der neuen Veranstaltung teilnehmen, haben die Möglichkeit entweder die dritte Klausur (2-stündig) zu BFS/AuK oder die erste Klausur (3-stündig) zur neuen Veranstaltung zu schreiben. Es werden Ihnen jedoch die Bonuspunkte zu der Veranstaltung angerechnet, deren Klausur Sie schreiben. Die dritte Klausur zu BFS/AuK wird sich am Stoff und den Übungen der zugehörigen BFS/AuK-Vorlesung orientieren. Die Klausur zur neuen Vorlesung wird sich am Stoff und den Übungen der neuen Vorlesung orientieren.
• Zeit und Ort dritte Klausur: Mittwoch, 23. Februar 2005, 12.00 - 14.00 Uhr im Hörsaal C1
• Ihre Ergebnisse können Sie in Ihrem StudInfo{flex} Account einsehen.
• Die 1. Klausureinsicht findet am Montag, 21.3.2005 ab 13.00 Uhr im Raum F0.530 statt. Zu diesem Termin sollten nur Studierende kommen, die nicht bestanden haben und vorhaben an der 2. Klausur der Vorlesung "Einführung in Berechenbarkeit, Komplexität und formale Sprachen" am 4.4.2005 teilzunehmen.
• Die 2. Klausureinsicht findet am Mittwoch, 6.4.2005 ab 13.00 Uhr im Raum F0.530 statt.

Übungen

Hausaufgaben

Es wird zweiwöchentlich Montags ein Übungsblatt mit jeweils vier Aufgaben auf dieser Website herausgegeben, das von Ihnen zu bearbeiten ist. Die Lösung wird bis Donnerstag nach der Ausgabe des nächsten Blattes (2,5 Wochen Bearbeitungszeit) in den Kästen auf Ebene D3 abgegeben und von den Betreuern der Übungsgruppe korrigiert und bewertet. Die Aufgaben können handschriftlich oder elektronisch erstellt werden; die Abgabe erfolgt aber immer in Papierform. Auf jedem Blatt können 20 Punkte erreicht werden. Es werden sechs Hausaufgabenblätter erscheinen; ein siebtes Blatt enthält eine Probeklausur, das in der letzten Zentralübung vorgerechnet wird. Überprüfen Sie immer auf Ihrem Punktekonto, ob Sie genau die Punkte bekommen haben, mit denen Ihre Lösung bewertet wurde.

Übungszettel Präsenzübung

Für jede Präsenzübung wird ein Übungsblatt mit zwei Aufgaben herausgegeben, das als Handzettel in der Präsenzübung ausgeteilt wird. Die beiden Aufgaben werden in der Übung durch Sie in Gruppenarbeit bearbeitet und eine Lösung von Ihnen an der Tafel präsentiert.

Gruppenarbeit

Wir fordern Sie ausdrücklich auf, in kleinen Gruppen (ca. 2-4 Personen) gemeinsam die Vorlesung nachzuarbeiten und die Übungen zu bearbeiten. Für den Lernerfolg und den Spaß am Studieren ist das sehr förderlich. Sie dürfen Ihre Übungen auch in solchen Gruppen abgeben.

Musterlösungen

Musterlösungen für die Hausaufgaben werden durch Sie erstellt. Dazu werden eine oder mehrere Ihrer Lösungen ausgewählt, zusammen mit den Betreuern ggfs. überarbeitet und im Netz zur Verfügung gestellt. Entweder werden wir Sie gezielt ansprechen und ermuntern eine Aufgabe als Musterlösung abzugeben, oder Sie sprechen uns darauf an, wenn sie den Wunsch haben eine Aufgabe als Musterlösung abzugeben. In Frage kommen Aufgaben, die mit 4-5 Punkten bewertet wurden. Die Abgabe von Musterlösungen erfolgt immer elektronisch. Möglich sind vorzugsweise PDF, oder Formate von LaTeX, OpenOffice, MSOffice oder Framemaker, die wir in PDF umwandeln können und als PDF im Netz zur Verfügung stellen.

Aufgabenblätter

Anmeldung

Die Anmeldung zu den Übungen erfolgt über StudInfo{flex}. Jede Gruppe ist auf 20 Teilnehmer begrenzt. Sie können Ihre persönlichen Informationen, sowie die Zugehörigkeit zu einer Übungsgruppe und Ihre Punkte aus den Hausaufgaben einsehen. Später finden Sie hier die Klausuranmeldung und erfahren Ihr Klausurergebnis. Bitte beachten Sie: Für jede Veranstaltung, die Sie besuchen und die zur Anmeldung StudInfo{flex} verwendet, müssen Sie sich erneut anmelden, jedes Teilnehmerkonto ist für genau eine Vorlesung gültig. Das gilt auch für alle Studenten, die "Berechenbarkeit und Formale Sprachen" im WS 03/04 gehört haben. Anmelden können Sie sich ab Mi., 14.04.04, 12.00 Uhr. Hier geht es zu Ihrem Teilnehmerkonto:

Prüfung

Im Anschluss an die Vorlesung erfolgt eine Prüfung über den Stoff dieser Veranstaltung und der Vorlesung "Berechenbarkeit und Formale Sprachen" (WS 03/04) durch eine gemeinsame Klausur. Als Hilfsmittel zur Klausur ist ein zweiseitig, handschriftlich, selbstgeschriebenes DIN-A4-Blatt zugelassen, d.h. keine Kopien und keine elektronischen Ausdrucke. Für Lehramtsstudierende und Austauschstudierende findet eine mündliche Prüfung über diese Veranstaltung statt, sie schreiben daher die gemeinsame Klausur über "Berechenbarkeit und Formale Sprachen" und "Algorithmen und Komplexität" nicht mit.

Wenn Sie aktiv in den Übungen mitarbeiten, können Sie Ihre Note wie folgt verbessern (Bonus):

• Erreichen Sie mindestens 50% der Punkte der Hausaufgaben, so verbessert sich die Note um 1/3.
• Erreichen Sie mindestens 75% der Punkte der Hausaufgaben, so verbessert sich die Note um 2/3.
• Erstellen Sie für eine Hausaufgabe Musterlösungen, die im Netz zur Verfügung gestellt werden, so verdoppelt sich die Punktezahl für die Aufgabe. Wenn Sie zu einer Aufgabe Musterlösungen erstellen wollen, dann melden Sie sich bei uns. Oder wir werden Sie auffordern Musterlösungen zu erstellen.

Eine Verbesserung der Note 5 (nicht bestanden) ist nicht möglich. Als Bonusleistung zählen die Hausaufgaben von dieser Veranstaltung (Auk) und der vorhergehenden Veranstaltung "Berechenbarkeit und Formale Sprachen" (BFS) im Wintersemester 2003/04. Für BFS erkennen wir auch die Übungsleistungen aus noch älteren Veranstaltungen an (z.B. die BFS Vorlesungen bei Johannes Blömer). Sie können bei BFS wählen, aus welcher Veranstaltung die Punkte anerkannt werden sollen. Falls Sie sich nicht melden, zählt automatisch die dieser Veranstaltung unmittelbar vorhergehende Veranstaltung "Berechenbarkeit und Formale Sprachen" im Wintersemester 2003/04. Die Termine für die Klausur finden Sie unter Prüfungstermine.

Skript

Die Vorlesung wird sich an der Vorlesung "Algorithmen und Komplexität" (SS 03) von Johannes Blömer orientieren. Dieses Skript kann jedoch das Lesen von Lehrbüchern nicht ersetzen. Ein Auswahl an Büchern haben wir in der Literatur angegeben. Falls erforderlich, werden Sie im Laufe des Semesters hier zusätzliche Ergänzungen zu dem Skript finden. Sie finden Skript und Folien hier:

Aktuelle Informationen

Literatur

Bücher über Berechenbarkeit und Komplexität

• Introduction to Automata Theory, Languages, and Computation, von: John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Addsion Wesley, 2001
  (auch übersetzt: Einführung in die Automatentheorie, Formale Sprachen und Komplexität, ... , Pearson Studium, 2002)
• Computers and Intractability - A Guide to the Theory of NP-Completeness, von: Michael R. Garey, David S. Johnson, W.H. Freeman & Company, 1997
• Theoretische Informatik, von: Christel Baier, Alexander Asteroth, Pearson Studium, 2002
• Theoretische Informatik - Eine algorithmenorientierte Einführung, von: Ingo Wegener, Teubner, 1993
• The Theory of Computation, von Bernard M. Moret, Pearson Education, 1998
• Computational Complexity, von: Christos H. Papadimitriou, Addison-Wesley, 1994
• Theoretische Informatk - kurzgefaßt, von: Uwe Schöning, Spektrum, akad. Verlag, Heidelberg, 1997
• Elements of the Theory of Computation, von: Harry R. Lewis, Christos H. Papadimitriou, Prentice Hall, 1998
• Introduction to the Theory of Computation, von: Michael Sipser, PWS, 1997
• Theory of Computing - A Gentle Introduction, von: Efim Kinber, Carl Smith, Prentice Hall, 2001

Bücher über Algorithmen

• Introduction to Algorithms, von: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, The MIT Press, 2001
• Algorithmen, von: Robert Sedgewick, Pearson Studium, 2002
  (übersetzt aus dem Englischen, gibt es in verschiedenen Ausgaben mit Schwerpunkten in Java, C, C++)
• Algorithmen, von: Ellis Horowitz, Sartaj Sahni, Springer, 1981
• The Design and Analysis of Computer Algorithms, von: Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman Addison Wesley, 1974
• Data Structures and Algorithms, von: Alfred V. Aho, J. D. Ullman, J. E. Hopcroft, Addison Wesley, 1983
• Algorithmik - Theorie und Praxis, von: Gilles Brassard, Paul Bratley, Prentice Hall, 1993
  
• Approximation Algorithms for NP-Hard Problems, von: Dorit S. Hochbaum, Wadsworth Publishing Company, 1997
• Randomized Algorithms, von: Rajeev Motwani, Prabhakar Raghavan, Cambridge University Press, 1995

Bücher über mathematische Hilfsmittel

Es geht bei diesen Büchern nicht direkt um Algorithmen und Komplexität. Die Bücher stellen aber gezielt alle mathematischen Mittel bereit, wie Informatiker sie für ihre Analysen und Berechnungen dabei benötigen: Asymptotic, Folgen, Reihen, Rekurrenz,...

• Concrete Mathematics, von: Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Addison-Wesley, 1994
• Diskrete Mathematik für Informatiker, von: Rod Haggarty, Pearson Studium, 2004