Syllabus

Title
2133 Algorithmen und Datenstrukturen
Instructors
Univ.Prof.i.R. Dipl.-Ing.Dr. Wolfgang Panny
Type
PI
Weekly hours
2
Language of instruction
Deutsch
Registration
09/01/11 to 10/09/11
Registration via LPIS
Notes to the course
Dates
Day Date Time Room
Monday 10/10/11 01:00 PM - 02:30 PM 2H363 (Mendling,Panny)
Monday 10/17/11 01:00 PM - 02:30 PM 2H363 (Mendling,Panny)
Monday 10/24/11 01:00 PM - 02:30 PM 2H363 (Mendling,Panny)
Monday 10/31/11 01:00 PM - 02:30 PM 2H363 (Mendling,Panny)
Monday 11/07/11 01:00 PM - 02:30 PM H 0.6 (B)
Monday 11/14/11 01:00 PM - 02:30 PM 2H363 (Mendling,Panny)
Monday 11/21/11 01:00 PM - 02:30 PM 2H363 (Mendling,Panny)
Monday 11/28/11 01:00 PM - 02:30 PM H 2.28 (C)
Monday 12/05/11 01:00 PM - 02:30 PM 2H363 (Mendling,Panny)
Monday 12/12/11 01:00 PM - 02:30 PM 2H363 (Mendling,Panny)
Monday 12/19/11 01:00 PM - 02:30 PM H DE03 (UZA 4)
Monday 01/09/12 01:00 PM - 02:30 PM 2H363 (Mendling,Panny)
Monday 01/16/12 01:00 PM - 02:30 PM SR XI (Kolpinghaus)
Monday 01/23/12 01:00 PM - 02:30 PM H 3.35 (C)
Contents
- Einführung und Grundlagen (Dualität: Algorithmus – Datenstruktur, funktionale Abstraktion und Datenabstraktion, formaler Algorithmusbegriff (berechenbare Funktionen, Turingmaschine,Turing-Church-These), Algorithmenanalyse (Zeit- und Speicherplatz-Komplexität, Worst-, Best- und Average-Case Analyse) - Elementare Sortier- und Suchverfahren (Sortieren durch Einfügen, Auswahl, Vertauschen, lineare Suche) - Höhere Sortier- und Suchverfahren (Quicksort, Heapsort, Mergesort, binäre Suche) - Bäume (Binärbäume, sortierte Binärbäume (binary search trees), geordnete Bäume, Traversierung von Bäumen, balancierte Bäume, AVL-Bäume) - Priority queues (Prioritätswarteschlangen) (Kellerspeicher und Warteschlangen als Spezialfälle von Prioritätswarteschlangen, Heapbäume und Heaps, abstrakte Datentypen) - Fallweise Ergänzungen aus den Bereichen: * Suchen in Zeichenketten (Knuth-Morris-Pratt Algorithmus, Boyer-Moore Algorithmus, Robin-Karp Algorithmus) * Information Retrieval (Tries, Digitale Suchbäume, Patricia) * Randomisierung anhand von SBBs (randomisierte binäre Suchbäume, random Treaps) * Optimale Suchbäume * Externes Suchen (indexsequentieller Zugriff, B-Bäume, Hashing) * Alternative Ansätze zur Balancierung (2-2-, 2-3-4-, rot-schwarz-Bäume) * Weitere Sortierverfahren (Batcher’s Method, Shellsort, Radixsort)
Learning outcomes
Verständnis grundlegender Datenstrukturen und der zugehörigen Algorithmen Fähigkeit zur Umsetzung in der Systementwicklung
Teaching/learning method(s)
Offener, fragend-entwickelter Unterricht Stundenwiederholungen
Assessment
Es werden vier Test abgehalten, von denen die drei besten Ergebnisse zur Beurteilung herangezogen werden. Für eine positive Note sind zumindest drei positive Tests notwendig. Mitarbeit, Hausübungen
Readings
1 Author: Panny Wolfgang
Title: Algorithmen und Datenstrukturen

Year: 2002
Content relevant for class examination: Yes
Content relevant for diploma examination: Yes
Recommendation: Essential reading for all students
Type: Script
2 Author: Sedgewick, R.
Title: Algorithmen

Publisher: Addison Wesley
Year: 1992
Content relevant for class examination: No
Content relevant for diploma examination: No
Recommendation: Reference literature
3 Author: Sedgewick, R.
Title: Algorithmen in C

Publisher: Addison Wesley
Year: 1992
Content relevant for class examination: No
Content relevant for diploma examination: No
Recommendation: Reference literature
4 Author: Wirth, N.
Title: Algorithmen und Datenstrukturen

Publisher: Teubner
Edition: 5. Auflage
Year: 1999
5 Author: Sedgewick, R.
Title: Algorithms in C

Publisher: Addison Wesley
Edition: 3rd ed.
Year: 1998
6 Author: Sedgewick, R.
Title: Algorithms in C++

Publisher: Addison Wesley
Edition: 3rd ed.
Year: 1999
7 Author: Gonnet, G.H.; Baeza-Yates, R.
Title: Handbook of Algorithms and Data Structures in Pascal and C

Publisher: Addison Wesley
Edition: 2nd ed.
Year: 1991
8 Author: Knuth, D.E.
Title: The Art of Computer Programming, Vol. 1: Fundamental Algorithms

Publisher: Addison Wesley
Edition: 3rd ed.
Year: 1997
9 Author: Knuth, D.E.
Title: The Art of Computer Programming, Vol. 2: Seminumerical Algorithms

Publisher: Addison Wesley
Edition: 3rd ed.
Year: 1997
10 Author: Knuth, D.E.
Title: The Art of Computer Programming, Vol. 3: Sorting and Searching

Publisher: Addison Wesley
Edition: 2nd ed.
Year: 1998
Availability of lecturer(s)
Per Mail: wolfgang.panny@wu-wien.ac.at
Other
"MitbelegerInnen" können nur dann in die Lehrveranstaltung aufgenommen werden, wenn es noch freie Plätze gibt! Handouts und weitere Unterlagen zur LV finden sie unter: http://www.ai.wu.ac.at/~panny/algdat/
Last edited: 2011-07-13



Back