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
Registration via LPIS
Notes to the course
Subject(s) Bachelor Programs
Subject(s) Diploma Programs
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) |
- 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)
Verständnis grundlegender Datenstrukturen und der zugehörigen Algorithmen
Fähigkeit zur Umsetzung in der Systementwicklung
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
"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