Uni-Logo Institut für Informatik

Algorithmen WS 2012/13
Dozent Prof. Dr. Oliver Vornberger
Übungsleiter Sebastian Büscher, M.Sc., Dipl.-Math. Jana Lehnfeld, Nicolas Neubauer, M.Sc.
Tutoren Patrizia Barkey, Maike Braukmüller, Sebastian Brockmeyer, Patrick Faion, Benjamin Graf, Kathrin Grosse, Nils Haldenwang, B.Sc., Christian Heiden, Julian Kniephoff, B.Sc., Nico Marniok, B.Sc., Niels Meyering, Sebastian Pütz, Manuel Schwarz, B.Sc., Andrea Suckro, Corinna Vatterodt
Vorlesung montags und dienstags, 14:15 - 15:45 Uhr, Raum 32/102
Übung

Pfeil zur Übungsseite

Sebastian Büscher: donnerstags, 10:15 - 11:45 Uhr, Raum 31/449a
Nicolas Neubauer: donnerstags, 12:30 - 14:00 Uhr, Raum 31/147
donnerstags, 14:15 - 15:45 Uhr, Raum 31/449a
Jana Lehnfeld: freitags, 10:15 - 11:45 Uhr, Raum 32/107
freitags, 12:30 - 14:00 Uhr, Raum 69/125

Erste Übung: 18.10.2012, alle fünf Übungen haben den gleichen Inhalt.
1. Klausur Montag, 04.02.2013, 08:30 - 10:30 Uhr
(Räume und Verteilung in Gebäude 01 wird noch bekannt gegeben)
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)     (Das Skript kann in der ersten Vorlesungsstunde für 6 Euro erworben werden)
Foto Die Teilnehmer der Veranstaltung
Die Teilnehmer der Veranstaltung (mit Markierungen)
Evaluation durch Papier-Fragebogen   durch Online-Fragebogen
Vorlesungsmitschnitte und Podcast Von der Vorlesung werden Videoaufzeichnungen erstellt und als Flash-Video, mp3-Audio und mp4-Podcast angeboten. Das Zentrum virtUOS hat hierzu ein Informationsblatt verfasst. Zusätzlich zu stud.ip finden Sie die Links auf die jeweiligen Folgen in der untenstehenden Ablauf-Tabelle. Sie werden eingefügt, sobald die jeweiligen Aufzeichnungen verfügbar sind. Zur Vorlesungszeit gibt es auch eine Liveübertragung. Wenn Sie Apple iTunes installiert haben, können Sie die Veranstaltung als Podcast abonnieren. Wenn Sie ein Apple iPad besitzen, können Sie die Veranstaltung auch als Apple Course besuchen.
Ablauf
Datum Kapitel Thema Video Video Audio
Mo, 08.10. 1 Einführung: Organisation, Informatik, Algorithmus, Anweisungen, Collatz-Funktion FLV mp4 mp3
Mo, 15.10. 2 Java - Sprachmerkmale, Variablen, Bedingungen, Fallunterscheidungen FLV mp4 mp3
Di,  16.10. 2 Schleifen: while, do-while, for, Berechnung der Fakultät, Berechnung des GGT FLV mp4 mp3
Mo, 22.10. 2 Java-Datentypen: Ganze Zahlen (byte, short, int, long), Gleitkommazahlen (float) FLV mp4 mp3
Di,  23.10. 2 Java-Datentypen: Gleitkommazahlen (Fortsetzung), Boolean, Character, Typumwandlung, Konstanten FLV mp4 mp3
Mo, 29.10. 3 Felder: Feld von Ziffern, Feld von Daten, Feld von Zeichen, Feld von Wahrheitswerten FLV mp4 mp3
Di,  30.10. 3 Felder: Feld von Indizes (Abzählreim), Feld von Zuständen (Endlicher Automat), Lineare Suche FLV mp4 mp3
Mo, 05.11. 3, 4 Binäre Suche, Methoden: aktuelle + formale Parameter, Übergabe von arrays, Sichtbarkeit FLV mp4 mp3
Di,  06.11. 4, 5 Fehlerbehandlung, Rekursion, Fakultät, Potenzieren, Fibonacci, ggT, Türme von Hanoi FLV mp4 mp3
Mo, 12.11. 6 Komplexität, O-Notation, Analyse von Schleifen, Analyse eines rekursiven Programms FLV mp4 mp3
Di,  13.11. 6 Verifikation, partielle Korrektheit, Terminierung, Halteproblem (Algorithmen-Fee) FLV mp4 mp3
Mo, 19.11. 7 Greedy, Divide-&-Conquer, SelectionSort, BubbleSort, MergeSort rekursiv, MergeSort iterativ FLV mp4 mp3
Di,  20.11. 7 Quicksort, Median FLV mp4 mp3
Mo, 26.11. 7 Baum, Heap, HeapSort FLV mp4 mp3
Di,  27.11. 7 Sortieren: Laufzeit und Platzbedarf, Untere Schranke für Sortieren durch Vergleichen, Bucket Sort FLV mp4 mp3
Mo, 03.12. 8 Objektorientierte Programmierung, Class Person, Vererbung, Class Student, Binden, Kinderabzählreim FLV mp4 mp3
Di,  04.12. 8 ADT, Interface, ADT Liste FLV mp4 mp3
Mo, 10.12. 9 ADT Keller, Reverse, Klammerung, CharKeller, Infix-Postfix FLV mp4 mp3
Di, 11.12. 9 Schlange, Baum, VerweisBaum FLV mp4 mp3
Mo, 17.12. 9 Traverse, TiefenSuche, BreitenSuche, PostfixBaumBau, Interface Enumeration, PreorderTraverse FLV mp4 mp3
Di, 18.12. 9 SuchBaum, Comparable, Interface Menge, Insert, Delete, Lookup FLV mp4 mp3
Mo,  07.01. 9 Implementation von Lookup, Insert, SuchBaumTest, ausgeglichen, AVLBaum FLV mp4 mp3
Di,  8.01. 10,11 Hashfunktion, Kollision, Sondieren, offenes + geschlossenes Hashing, HashSet, HashMap FLV mp4 mp3
Mo, 14.01. 12 Graphen: Modellierung, Fragestellungen, Implementation, All-Pairs-Shortest Path FLV mp4 mp3
Di,  15.01. 12 Graphen: Vertex, Edge, Single-Source-Shortest-Path, Topologisches Sortieren, Hamiltonkreis FLV mp4 mp3
Mo, 21.01. 12 Graphen: Maximaler Fluss, Minimaler Cut, erweiternder Weg, Ford Fulkerson FLV mp4 mp3
Di,  22.01. 12 Graphen: Spannbaum, Matching, Chinese Postman FLV mp4 mp3
Mo,  28.01. - Wanderung
Mo,  04.02. - Klausur
Literatur