Uni-Logo Institut für Informatik

Algorithmen WS 2009/10

Dozent Prof. Dr. Oliver Vornberger
Übungsleiter Dipl.-Math. Patrick Fox, Dipl.-Inform. Christian Viergutz
Tutoren Sebastian Büscher, Daniel Künne, Elisa Klose, Julian Kniephoff, Jana Lehnfeld, Katharina Lorenz, Mathias Menninghaus, Philipp Middendorf, Philip Münch, Nicolas Neubauer, Sabine Seyffarth, Dirk Stürzekarn
Vorlesung montags und dienstags, 14:15 - 15:45 Uhr, Raum 32/102
Übung
Christian Viergutz: donnerstags, 08:20 - 09:50 Uhr, Raum 31/E05
donnerstags, 14:15 - 15:45 Uhr, Raum 31/E06
Patrick Fox: donnerstags, 10:15 - 11:45 Uhr, Raum 66/E33
donnerstags, 12:15 - 13:45 Uhr, Raum 66/E33
erste Übung: 22.10.2009, alle vier Übungen haben den gleichen Inhalt
Inhalt Es werden anhand der Programmiersprache Java Algorithmen zum Suchen und Sortieren vorgestellt und die dazu benötigten Datenstrukturen wie Keller, Schlange, Liste, Baum und Graph eingeführt. Programme werden auf Eigenschaften wie Korrektheit, Terminierung und Effizienz untersucht.
Material Vorlesungsskript (HTML),     Vorlesungsskript (PDF)
Evaluation interne Hörer Papier (PDF)     interne Hörer Online (PDF)     externe Hörer Online (PDF)
Foto Die Teilnehmer der Veranstaltung als sensitives Foto
Liveübertragung Montags und dienstags von 14:15 - 15:45 Uhr wird die Vorlesung auf dieser Seite live übertragen.
Vorlesungsmitschnitte und Podcast Es werden Vorlesungsmitschnitte als Flash-Video, mp3-Audio und mp4-Podcast angeboten. Zum Betrachten des Flash-Video wird der FlashPlayer benötigt. Zum Hören der mp3-Dateien benötigen Sie einen mp3-Player. Die Links auf die jeweiligen Folgen finden Sie in der Ablauf-Tabelle. Sie werden eingefügt, sobald die jeweiligen Aufzeichnungen verfügbar sind.

Wenn Sie Apple iTunes installiert haben, können Sie den Podcast im Apple Store finden und abonnieren. Suchen Sie hierzu im Store nach "Algorithmen" oder folgen Sie von hier aus dem Link zum iTunes Store.

Die Vorlesungsaufzeichnungen sind als Applikation mit vielen sozialen Funktionen in Facebook verfügbar. Der social virtPresenter setzt einen Facebook-Account voraus. Zum Installieren rufen Sie folgende URL auf: http://fb.socialvirtpresenter.de
Ablauf
Datum Kapitel Thema Video Video Audio
Mo, 19.10. 1 Einführung: Organisation, Informatik, Algorithmus, Anweisungen, Collatz-Funktion FLV MP4 MP3
Di,  20.10. - Vorkurs: Organisation, Übungsbetrieb, Systemadministration, Installation, Algotools FLV MP4 MP3
Mo, 26.10. 2 Java - Sprachmerkmale, Variablen, Bedingungen, Fallunterscheidungen FLV MP4 MP3
Di,  27.10. 2 Schleifen: while, do-while, for, Berechnung der Fakultät, Berechnung des GGT FLV MP4 MP3
Mo, 02.11. 2 Java-Datentypen: Ganze Zahlen, Gleitkommazahlen FLV MP4 MP3
Di,  03.11. 2 Java-Datentypen: Gleitkommazahlen (Fortsetzung), Boolean, Character, Typumwandlung, Konstanten FLV MP4 MP3
Mo, 09.11. 3 Felder: Feld von Ziffern, Feld von Daten, Feld von Zeichen, Feld von Wahrheitswerten FLV MP4 MP3
Di,  10.11. 3 Felder: Feld von Indizes, Feld von Zuständen (Endlicher Automat), Lineare Suche, Binäre Suche FLV MP4 MP3
Mo, 16.11. 3, 4 Methoden: aktuelle + formale Parameter, Sichtbarkeit FLV MP4 MP3
Di,  17.11. 4, 5 Fehlerbehandlung, Rekursion, Fakultät, Potenzieren, Fibonacci, ggT, Türme von Hanoi FLV MP4 MP3
Mo, 23.11. 6 Komplexität, O-Notation, Analyse von Schleifen, Analyse eines rekursiven Programms FLV MP4 MP3
Di,  24.11. 6 Verifikation, Halteproblem FLV MP4 MP3
Mo, 30.11. 7 Greedy, Divide-&-Conquer, SelectionSort, BubbleSort, MergeSort rekursiv, MergeSort iterativ FLV MP4 MP3
Di,  01.12. 7 Quicksort, Median FLV MP4 MP3
Mo, 07.12. 7 Baum, Heap, HeapSort FLV MP4 MP3
Di,  08.12. 7 Sortieren: Laufzeit und Platzbedarf, Untere Schranke für Sortieren durch Vergleichen, Bucket Sort FLV MP4 MP3
Mo, 14.12. 8 Objektorientierte Programmierung, Class Person, Vererbung, Class Student, Binden, Kinderabzählreim FLV MP4 MP3
Di,  15.12. 8 ADT, Interface, ADT Liste FLV MP4 MP3
Mo,  04.01. 9 ADT Keller, Reverse, Klammerung, CharKeller, Infix-Postfix FLV MP4 MP3
Di, 05.01. 9 Schlange, Baum, VerweisBaum FLV MP4 MP3
Mo,  11.01. 9 Traverse, TiefenSuche, BreitenSuche, PostfixBaumBau, Interface Enumeration, PreorderTraverse FLV MP4 MP3
Di, 12.01. 9 SuchBaum, Comparable, Interface Menge, Insert, Delete, Lookup FLV MP4 MP3
Mo,  18.01. 9 SuchBaumTest, Klassendiagramm, ausgeglichen, Balance, AVLBaum FLV MP4 MP3
Di,  19.01. 10 Hashfunktion, Kollision, Sondieren, offenes + geschlossenes Hashing, HashSet, HashMap FLV MP4 MP3
Mo, 25.01. 11 Graphen: Modellierung, Probleme, Implementation, All-Pairs-Shortest Path FLV MP4 MP3
Di,  26.01. 11 Graphen: Vertex, Edge, Single-Source-Shortest-Path, Topologisches Sortieren, Hamiltonkreis FLV MP4 MP3
Mo, 01.02. 11 Graphen: Maximaler Fluss, Implementation von ungerichteten Graphen FLV MP4 MP3
Di,  02.02. 11 Graphen: Spannbaum, Matching, Chinese Postman FLV MP4 MP3
Mo,  08.02. - Wanderung
Mo,  15.02. - Klausur
Literatur