TU Wien:Approximationsalgorithmen VU (Pferschy)
Daten[edit | edit source]
| Lecturers | Ulrich Pferschy |
|---|---|
| ECTS | 3 |
| Department | Forschungsbereich Algorithms and Complexity |
| When | summer semester |
| Language | English |
| Links | Homepage |
| Master Logic and Computation | Pflichtmodul Unbekannt oder "Prä-Modul-Ära" - EDIT ME |
| Master Software Engineering & Internet Computing | Wahlmodul Unbekannt oder "Prä-Modul-Ära" - EDIT ME |
Inhalt[edit | edit source]
Wichtige Definitionen aus dem Bereich Algorithmik sowie approximative Algorithmen zu folgenden Problemen:
- Scheduling
- Bin-Packing
- Rucksackproblem
- Travalling-Salesman
- Maximum Clique
Ablauf[edit | edit source]
Das LVA wird im Sommersemester geblockt abgehalten. Es gibt 3 mal 3 Termine (Mittwoch abends, Donnerstag und Freitag Vormittag), wovon 2 Übungstermine sind.
Benötigte/Empfehlenswerte Vorkenntnisse[edit | edit source]
- Solide Kenntnisse aus der Algorithmik, vor allem Algorithmen und Datenstrukturen 1
- Mathematik-Kenntnisse (Inhalt aus Mathematik 1: Induktionsbeweise, mathematische Formeln lesen und schreiben können)
Vortrag[edit | edit source]
Der Vortrag ist sehr gut strukturiert, langsam und detailliert. Prof. Pferschy verwendet Folien und schreibt nebenbei vieles an die Tafel (mitschreiben!), vor allem Beweise und Worst-Case-Beispiele.
Er geht auf Fragen ein und bemüht sich, die Inhalte durch Skizzen zu verdeutlichen.
Übungen[edit | edit source]
2 Übungsblätter mit je 10 Beispielen, die in 2 Übungsstunden durchgemacht werden. Es werden Teilnehmer zur Tafel gerufen (meistens keine freiwilligen Meldungen).
Das 3. Übungsblatt mit etwa 5 Beispielen muss per E-Mail abgegeben werden (entfällt aber für diejenigen, die die Prüfung sofort nach der letzten VO ablegen).
Prüfung, Benotung[edit | edit source]
Die Prüfung ist mündlich. Sie kann gleich am letzten oder vorletzten Tag der VO (Donnerstag oder Freitag Nachmittag) abgelegt werden. Danach müssen individuell Termine mit ihm vereinbart werden, da er aus Graz kommt. Entweder man erreicht ihn wenn er gerade in Wien ist, oder man besucht ihn in Graz.
Prof. Pferschy prüft sehr auf Verständnis. Beweise müssen nicht im Detail auswendig gelernt werden, wichtig ist ihm aber, dass die Beweisidee verstanden wird (vor allem bei konstruktiven Beweisen und welchen die sich gut grafisch veranschaulichen lassen).
Wer sich ernsthaft mit dem Stoff auseinandergesetzt hat sollte bei der Prüfung kein Problem haben. Er berücksichtigt es auch positiv, wenn die Antworten bei der Prüfung nicht nur "irgendwie" passen, sondern wenn man sie mathematisch exakt formuliert.
Dauer der Zeugnisausstellung[edit | edit source]
im SS 2009 nach der letzten Prüfung im Juni, wenn man das Zeugnis früher braucht, ist das aber auch kein Problem
Zeitaufwand[edit | edit source]
entspricht ziemlich genau dem Aufwand, der anhand der ECTS errechenbar ist
Unterlagen[edit | edit source]
- Folien. Diese reichen für die Prüfung nicht aus, was er auch ganz offiziell ankündigt. Wenn man nicht in der VO war, sind sie auch wenig hilfreich.
- Eigene Mitschrift aus der VO.
Tipps[edit | edit source]
- mitschreiben
- Übungen in Teams ausarbeiten (nicht nur abschreiben!)
- Prüfung gleich nach der letzten VO machen (Stoff des letzten Freitagstermins fällt weg, 3. Übungsblatt fällt weg)
Verbesserungsvorschläge / Kritik[edit | edit source]
noch offen