Uni Wien:Algorithmen und Datenstrukturen VO (Schikuta)

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.

Daten

• LV-Kürzel: PI.ADS.AD.VO
• im Modul enthalten: Algorithen und Datenstrukturen UE
• Vortragender Dipl.-Ing. Dr. Erich Schikuta
• ECTS: 4 (SWS: 3 )
• Institut: Institut für Knowledge and Business Engineering
• Empfohlenes Semester: 2
• Vorlage:521

Inhalt

Ziele gemäß Studienplan

Die Studierenden erlangen Kenntnisse über Aufwandsabschätzungen, Komplexitätsmaße, grundlegende Datenstrukturen, Such- und Sortierverfahren und grundlegende Graph- und Optimierungsalgorithmen.

Themen

• 0. Einführung:
  • Eigenschaften von Algorithmen
  • Algorithmen-Paradigmen
  • Programmstrukturen: Schleifen, Rekursionen, Verzweigungen,...

• 1. Algorithmen:
  • Algorithmenparadigmen: Greedy, Divide-and-Conquer, Dynamic Programming
  • Analyse und Bewertung von Algorithmen:
    • Effektivität, Korrektheit, Termination
    • Komplexitätsanalysen (nach Struktur oder Laufzeit)
    • Ordnungsnotationen: Big O-, Omega-, Theta-Notationen
    • Rekurrenzgleichungen: für Laufzeitanalyse von Rekursionen
    • Master-Theorem zur Laufzeitabschätzung
  • Begriff der 'Algorithmischen Lücke'

• 2. Datenstrukturen:
  • Motivation
  • Listen (Verkettete Listen und Spezialfälle)
  • Bäume:
    • Traversierung (Preorder, Postorder, Inorder)
    • Binärer Suchbaum (Funktion u. Eigenschaften)
    • AVL-Baum (Funktion u. Eigenschaften)
    • 2-3-4-Baum (Funktion u. Eigenschaften)
    • B+-Baum (Funktion u. Eigenschaften)
  • Trie
    • Patricia Trie, de la Briandais Trie
  • Priority Queue, Heap
  • Vektoren
    • Dictionaries, Aufwand: O(1)
    • Hashing mit Kollisionsbehandlungen
      • Separate Chaining, Double Hashing
    • Dynamisches Hashing: Linear Hashing, Extendible Hashing

• 3. Sortierverfahren:
  • Kennwerte
  • Klassische Verfahren
    • Selection Sort (Funktion u. Eigenschaften)
    • Bubble Sort (Funktion u. Eigenschaften)
    • Quick Sort (Funktion u. Eigenschaften)
    • Merge Sort (Funktion u. Eigenschaften)
    • Heap Sort (Funktion u. Eigenschaften)
  • Sortieren in linearer Zeit (nicht-vergleichende Verfahren)
    • Counting Sort (Funktion u. Eigenschaften)
    • Radix Sort (Funktion u. Eigenschaften)
    • Bucket Sort (Funktion u. Eigenschaften)
  • Externes Sortieren
    • Balanced Multiway Merging (Funktion u. Eigenschaften)
    • Replacement Selection (Funktion u. Eigenschaften)
    • Polyphase Merging (Funktion u. Eigenschaften)

• 4. Graphen
  • Motivation
  • Adjazenzliste, Adjazenzmatrix
  • Topologisches Sortieren
  • Traversieren eines Graphen
    • dfs
    • bfs
  • Dijkstra's Algorithmus

Vorkenntnisse

• Voraussetzung laut Studienplan ist das Modul: PI.PRG, also: EPROG
• Grundlegende Programmierkenntnisse sind vom Vorteil, da in der Vorlesung hin und wieder Pseudo- oder C++-Code vorkommen.

Vortrag

Prof. Schikuta

• Wenn Prof. Schikuta die Vorlesung persönlich hält, muss man sich darauf gefasst machen, statt (oder manchmal zwischen) dem Stoff Geschichten aus seinen Erlebnissen in der IT-Branche zu hören, die sicher interessant sind, bei AlgoDat selbst aber eher nicht weiterhelfen. Für die Motivation kann es dem einen oder anderen hilfreich sein. Nur nach Hören der Vorlesung von Prof. Schikuta die Prüfung zu machen, würde ich demnach nicht empfehlen. Man sollte aber trotzdem nicht davor zurückschrecken, Fragen den Stoff betreffend zu stellen, da Prof. Schikuta neben seinem Talent zum Geschichtenerzählen ein kompetenter Mann ist. Darüber hinaus merkt man bei ihm in der Vorlesung überhaupt nicht, wie schnell die Zeit vergeht. Ihm zuzuhören ist ein Genuss.

Prof. Wanek

• Falls Prof. Schikuta zufällig keine Zeit hat, kommt ihr in den Genuss, Prof. Wanek und seine C++-Kenntnisse kennenzulernen. Er versucht im Gegensatz zu Prof. Schikuta, sich an die Folien im Skriptum zu halten, wobei er besonderen Wert auf die Folien mit Source-Code legt. Im Übrigen wird auch er die Prüfung zusammenstellen.
• Prof. Wanek erklärt den Stoff verständlich und fragt auch bei den Studenten nach, ob sie alles verstanden haben. Wie immer: Fragen erwünscht.
• Bei Forumeinträgen hat man das Gefühl, als würde Prof. Wanek jedesmal eine SMS erhalten, wenn was neues da ist. Egal ob man um 0 Uhr, 3 Uhr oder gar um 06:20 postet, die durchschnittliche Reaktionszeit beträgt etwa eine halbe Stunde. Fast verdächtigt für einen Menschen.

Übungen

• Im selben Modul befindet sich eine Übung, die man am Besten gleichzeitig mit der Vorlesung besuchen sollte, zwingend notwendig ist es aber nicht. Man bekommt durch das Implementieren eines Sortieralgorithmus und einer Datenstruktur (das wird in der UE gefordert) ein bisschen ein Gefühl, was die Aufwandsabschätzungen zu bedeuten haben und wie man das Lösen einer solchen Aufgabe am Besten angeht.

Prüfung, Benotung

• Modus: Theoriefragen sowie Funktionsweisen von Algorithmen anhand kl. Beispiele erklären.
• Hilfsmittel: Keine.
• Zeit: soweit ich weiß 2 Stunden (ausreichend, wenn man gelernt hat)
• Benotung: In Ordnung

• Die hier unter Materialien hochgeladenen Prüfungsbeispiele sind leicht veraltet, inzwischen werden 4 Fragen pro Prüfung gestellt. Die Themen sind weitgehend dieselben, zusätzlich wird oft der B+ Baum gefragt.
• Prinzipiell sollte man die alten Prüfungsbeispiele ausdrucken und entsprechend dem Stoff, der im aktuellen Semester vorgetragen wurde, durcharbeiten. Versteht man die Prüfungsbeispiele (nicht trivial!) und kann sie lösen (auch nicht trivial!), kann man getrost zur Prüfung antreten.

Zeitaufwand

• Man braucht schon eine Woche, um den Stoff durchzuarbeiten, nicht weil er so umfangreich ist, sondern weil es eine Weile braucht, um alle Details zu verinnerlichen. Gewappnet mit alten Prüfungsbeispielen, Skriptum u. evt. einigen Internetrecheren (z.B. JavaApplets für B+-Bäume, etc.) kann man mit intensiven Lerneinheiten in 5 Tagen durchkommen. Gemütliche Lerner sollten 1,5 Wochen einplanen. Zur Prüfung selbst kommen meist Themen, die in ähnlicher Form bereits in älteren Prüfungen vorgekommen sind (daher unbedingt die älteren Angaben durchsehen), auf alle Fälle sollte man damit rechnen, das Master-Theorem anwenden zu müssen (zB in Form von Pseudo-Code), Graphen zu traversieren (Dijkstra-Algorithmus) und Hashtabellen anzulegen.

Literatur

• AlgoDat-Skriptum, gebunden: Selbkostenpreis (ca. 8 EUR) im Student Service Centre (SCC)

In der Lehrbuchsammlung

• Robert Sedgewick. Algorithms in C++. Addison-Wesley Longman. 3. Auflage (1998) ISBN 0-201-35088-2
• Thomas H. Cormen. Algorithmen - eine Einführung. Oldenbourg. 2. Auflage (2007) ISBN 978-3-486-58262-8

Online

• NIST Dictionary of Algorithms and Data Structures

Materialien

Neues Material hinzufügen

4

• 4DF0098Cd01.pdf (details)

A

• ADS Skriptum.pdf (details)

P

• Pruefung17-12-2010.pdf (details)
• Pruefung19-11-2009.pdf (details)
• Pruefung27-09-2010.pdf (details)

S

• Skriptum.pdf (details)

Z

• Zusammenfassung zur Prüfungsvorbereitung.pdf (details)