TU Wien:Effiziente Algorithmen VU (Leitner)

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]

Perlen der Programmierkunst, Zufällige Auswahl, Mischen, Suffix Bäume und Suffix Arrays, Sequenzalignment, Phylogenetische Bäume, Kryptographie (RSA, elliptische Kurven)

Ablauf[Bearbeiten]

WS2010: ganz normale VU, 2 Übungstermine mit je 15 Beispielen

Empfehlenswerte Vorkenntnisse[Bearbeiten]

Algorithmen und Datenstrukturen 1

Vortrag[Bearbeiten]

  • Ruthmaier: Sehr lockerer Vortragsstil, regt zur Mitarbeit an, motiviert und kurzweilig
  • Leitner: etwas monoton
  • Schauer: Sehr lockerer Vortragsstil, motiviert und kurzweilig

Übungen[Bearbeiten]

2 Übungstermine, Mitte November und Ende Jänner, Zeitaufwand pro Übungstermin liegt zwischen einem halben Tag und zwei Tagen (je nach dem, wieviele Beispiele man ankreuzen möchte). Plus gibt es für freiwillige Meldungen (es wird nicht herausgerufen) und für Ergänzungen zu den Beispielen anderer.

Prüfung[Bearbeiten]

mündlich; man wird von mindestens 2 Vortragenden geprüft; über welche Themengebiete man geprüft wird, hängt davon ab, bei wem man die Prüfung ablegt. Die Fragen sind zum Großteil eher überblicksartig gestellt (zB: "Wozu braucht man einen Suffix Tree/ein Suffix Array"), die Prüfung sollte man dennoch nicht unterschätzen, da auch Detailfragen kommen.

Beispiele für Prüfungsfragen[Bearbeiten]

  • Textsuche: Wofür braucht man Suffix Array bzw. Trees, wie funktionieren sie, Unterschiede, Gemeinsamkeiten, Laufzeit- und Speicherkomplexität.
  • Textsuche: Algorithmus von Ukkonen (Grundstruktur beschreiben, Idee der 3 Effizienzsteigerungen und Laufzeitauswirkungen grob beschreiben)
  • Kurze Beschreibung der Algorithmen für Mischen oder Auswahl, diese vergleichen.
  • Effizienten Algorithmus für zufällige Auswahl
  • Effizienten Algoritmus für Zahlensortierung unter gewissen Constraints
  • Anagramme finden - wie macht man das effizient?
  • Bioinformatik: Alignment Überblick (was, wozu, welche gap funktionen, 2 sequenzen, multiples alignment, ...)

Zeitaufwand[Bearbeiten]

Für die Übungstermine einen halben Tag bis zwei Tage, für die Prüfung sich alles noch einmal ansehen, ohne Vorlesungsbesuch zwei Tage, evtl. etwas mehr, wenn die Übung lange zurückliegt.

Verbesserungsvorschläge / Kritik[Bearbeiten]

noch offen