Algorithmentechnik

• Dozentin: Prof. Dr. Dorothea Wagner
• Termine: Wöchentlich: Dienstags 15:45–17:15 Uhr (HS Neue Chemie) und donnerstags 15:45–17:15 Uhr (Tulla HS)
  Achtung: Donnerstag, 12.11.2009 fällt aus. Donnerstag, 26.11.2009 Verlegung in Gaede Hörsaal.
• Betreuung: Tanja Hartmann, Thomas Pajor
• Forum zur Vorlesung

Die Vorlesung Algorithmentechnik vertieft die wichtigsten Teilgebiete der Algorithmik. Dazu gehören Graphenalgorithmen, Algorithmische Geometrie, Algebraische Algorithmen, Kombinatorische Optimierung sowie fortgeschrittene Datenstrukturen. Es werden verschiedene methodische Richtungen vertieft, z.B. randomisierte Algorithmen, Approximationsalgorithmen, parallele Algorithmen, Online-Algorithmen und Algorithm Engineering.

• Die Nachklausur fand statt am Freitag, 16. April 2010 um 16:00 Uhr.

• Vorläufige Ergebnisse der Nachklausur (UPDATE: 7. Mai 2010)
• Klausur ohne Lösung
• Klausur mit Lösung

Falls Sie einen Termin für eine mündliche Nachprüfung benötigen, setzen Sie sich bitte mit Thomas Pajor in Verbindung.

• Die Hauptklausur fand statt am 1. März 2010 um 9:00 Uhr.

• Vorläufige Ergebnisse der Hauptklausur.
• Klausur ohne Lösung.
• Klausur mit Lösung.

7. Mai:
Die Noten der Nachklausur haben sich aufgrund der Klausureinsicht geändert (betrifft auch Studierende, die nicht in der Klausureinsicht waren). Eine upgedatete Fassung der Notenliste wurde unter Nachklausur veröffentlicht.

12. April:
Anmeldeliste für die Nachklausur online. Bitte überprüfen Sie wiederrum, ob Sie auf der Anmeldeliste stehen. Eine Teilnahme an der Klausur für Studierende, die nicht auf der Anmeldeliste verzeichnet sind, ist ausgeschlossen.

24. März:
Die Hauptklausur sowohl mit alsauch ohne Lösung sind jetzt zum Download verfügbar.

23. Februar:
Anmeldeliste und Hinweise zum Ablauf der Hauptklausur sind online. Bitte überprüfen Sie unbedingt, ob Sie auf der Anmeldeliste verzeichnet sind. Eine Teilnahme an der Klausur für Studierende, die nicht auf der Anmeldeliste stehen, ist ausgeschlossen.

18. Februar:
Anmerkung zum Skript, S.153 ff: Die Existenz eines Suchbaums für VERTEX COVER in O(nk + (1.342^k) k^2) setzt einen zusammenhängenden Graphen voraus, da sonst nicht ausgeschlossen werden kann, dass eine Verzweigung (1,4) mehrfach pro Pfad auftritt.

16. Februar:
Lösungsvorschläge zu Blatt 8 sind jetzt online.

12. Februar:
Diplom-Mathe-Studenten, die die Algorithmentechnik im Vordiplom als Nebenfach-Prüfung schreiben möchten, müssen sich bei Herrn Stefan Kühnlein (Mathefakultät) anmelden.
Diplom-Mathe-Studenten, die die Algorithmentechnik im Hauptdiplom als Nebenfach-Prüfung schreiben möchten, brauchen eine Zulassung (gelber DINA4-Zettel), der bei uns im Infobau abgegeben werden kann.

In letzterem Fall gab es etwas Verwirrung, die dazu führte, dass wir nicht wussten, ob wir jene Zulassungszettel annehmen dürfen. Daher nahmen manche von Euch einen unnötigen Weg zu Herrn Kühnlein auf sich. Dafür bitten wir um Entschuldigung!

09. Februar:
Weitere Informationen zu den in der Übung vorgestellten Hiwi-Stellen gibt's hier.

08. Jänner:
Vorlesungsfolien zur Vorlesung über Lineares Programmieren vom 7. Jänner 2010 sind online.

14. Dezember:
In den letzten beiden Zeichnungen des Gegenbeispiels zu Aufgabe 2, Blatt 3, befanden sich bis eben Vorzeichenfehler in den Flussangaben zwischen den Knoten 1,2,3 und 4. Diese sind nun korrigiert. Bitte entschuldigen Sie diese Unachtsamkeit!

29. Oktober:
Der Vorlesungstermin am 12.11.2009 fällt aus. Es wird empfohlen an der Eröffnungsfeier des KIT-Schwerpunkt COMMputation teilzunehmen.

26. Oktober:
Diskussionsforum aktiviert. Falls ihr also Fragen habt, könnt ihr diese dort gerne an uns stellen.

16. Oktober:
Vorläufige Version des Vorlesungsskripts online (basierend auf WS 08/09). Möglicherweise werden neue Revisionen des Skripts im Verlauf des Semesters veröffentlicht die Verbesserungen und Korrekturen enthalten.

6. Oktober:
Vorläufige Vorlesungs- und Übungstermine online. Bitte beachten Sie außerdem, dass an den Terminen 12.11.2009 und 26.11.2009 die jeweilige Veranstaltung im Gaede Hörsaal stattfindet.

• Vorläufiges Skript zur Vorlesung WS 09/10
• Kurzskripte zur Wiederholung wichtiger Begriffe
  • Algorithmen und ihre Laufzeit
  • Begriffe zu Graphen
  • Die Komplexitätsklassen P, NP und NPC
• Periodische Fahrpläne und Kreise in Graphen
  Vorlesungsfolien vom 22.12.2009
• Lineares Programmieren und
  Lineares Programmieren (Klickminimal/Handout)
  Vorlesungsfolien vom 07.01.2010

Übung:

Hinweise zu den Blättern:

• Allgemein:
  Sollten Sie Fragen zur Korrektur der Übungsblätter haben, wenden Sie sich an die Übungsleiter oder direkt an den Korrektor (Jonathan Rollin) unter algotech@n-ten.de
• Blatt 2:
  Sie können bei Aufgabe 2d) davon ausgehen, dass sich ein minimaler Spannbaum in Zeit O(|V|²) berechnen lässt (zum Beispiel über den Algorithmus von Prim mit Fibonacci-Heaps), bzw. einen minimalen Spannbaum als gegeben voraussetzen.
• Blatt 3:
  Ein Gegenbeispiel zur in der Übung vorgeschlagenen (vermeintlich alternativen) Vorgehensweise zur Bestimmung eines minimalen Schnitts auf Basis eines Max-Flows (berechnet mit Preflow-Push-Algo) (Problem 2), steht hier (korrigiert) bereit. (Alte Version mit Vorzeichenfehler: Achtung: Vorzeichenfehler!)

Vergangene Algorithmentechnik-Vorlesungen:

• Vorlesungsseite Algorithmentechnik, WS 2008/2009 (ITI Wagner)
• Vorlesungsseite Algorithmentechnik, WS 2007/2008 (ITI Sanders)
• Vorlesungsseite Algorithmentechnik, WS 2006/2007 (ITI Wagner)
• Vorlesungsseite Algorithmentechnik, WS 2005/2006 (ITI Wagner)

Voraussichtliche Klausurtermine:

• Hauptklausur: 1. März 2010
• Nachklausur: 16. April 2010

Verbindlich sind die Termine auf der offiziellen Klausurseite.

Änderungen vorbehalten!

Die Journalveröffentlichungen [Hor87] und [Kav04] sind aus dem Netz der Universität zugänglich.