TU Wien:Approximationsalgorithmen VU (Pferschy)

Aus VoWi
Wechseln zu: Navigation, Suche
Diese LVA wird nicht mehr von dieser Person angeboten, ist ausgelaufen, oder läuft aus und befindet sich daher nur noch zu historischen Zwecken im VoWi. Eventuell findest du über dieser Meldung noch andere Vortragende, oder Links für dieselbe LVA.


Daten[Bearbeiten]

Inhalt[Bearbeiten]

Wichtige Definitionen aus dem Bereich Algorithmik sowie approximative Algorithmen zu folgenden Problemen:

  • Scheduling
  • Bin-Packing
  • Rucksackproblem
  • Travalling-Salesman
  • Maximum Clique

Ablauf[Bearbeiten]

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[Bearbeiten]

Vortrag[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

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[Bearbeiten]

im SS 2009 nach der letzten Prüfung im Juni, wenn man das Zeugnis früher braucht, ist das aber auch kein Problem

Zeitaufwand[Bearbeiten]

entspricht ziemlich genau dem Aufwand, der anhand der ECTS errechenbar ist

Unterlagen[Bearbeiten]

  • 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[Bearbeiten]

  • 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[Bearbeiten]

noch offen