Uni-Logo Institut für Informatik

Algorithmen WS 2013/14
Dozent Prof. Dr. Oliver Vornberger
Übungsleiter Nils Haldenwang, M.Sc., Nicolas Neubauer, M.Sc.
Tutoren Patrizia Barkey, Sebastian Blum, Joris Clement, Christoph Eichler, Malte Gegner, Matthias Harte, Christian Heiden, Maike Hille, Lukas Kalbertodt, Julian Kniephoff, B.Sc., Nico Marniok, B.Sc., Niels Meyering, B.Sc., Andrea Olberding, B.Sc., Sargini Rasathurai, Lena Scholz, Manuel Schwarz, B.Sc., Kai Standvoß
Vorlesung montags und dienstags, 14:15 - 15:45 Uhr, Raum 32/102
Übung

Pfeil zur Übungsseite

Nils Haldenwang: donnerstags, 10:15 - 11:45 Uhr, Raum 31/E06
freitags, 10:15 - 11:45 Uhr, Raum 35/E22
Nicolas Neubauer: donnerstags, 12:30 - 14:00 Uhr, Raum 31/E05
donnerstags, 14:15 - 15:45 Uhr, Raum 31/E06

Erste Übung: 31.10.2012, alle Ü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)     (Das Skript kann in der ersten Vorlesungsstunde erworben werden. Man kann ein Skript für 3,50 Euro oder drei Skripte für 10 Euro bekommen.)
Evaluation interne Hörer Online (PDF)
Foto Die Teilnehmer der Veranstaltung
Die Teilnehmer der Veranstaltung (mit Markierungen)
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. 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, 21.10. 1 Einführung: Organisation, Informatik, Algorithmus, Anweisungen, Collatz-Funktion FLV mp4
Di,  22.10. - Vorkurs: Organisation, Übungsbetrieb, Systemadministration, Installation, Algotools FLV mp4
Mo, 28.10. 2 Java: Sprachmerkmale, Variablen, Bedingungen, Fallunterscheidungen FLV mp4 mp3
Di,  29.10. 2 Schleifen: while, do-while, for, Berechnung der Fakultät, Berechnung des GGT FLV mp4 mp3
Mo, 04.11. 2 Datentypen: Ganze Zahlen (byte, short, int, long), Gleitkommazahlen (float) FLV mp4 mp3
Di,  05.11. 2 Datentypen: Gleitkommazahlen (double), Boolean, Character, Typumwandlung, Konstanten FLV mp4 mp3
Mo, 11.11. 3 Felder: Feld von Ziffern, Feld von Daten, Feld von Zeichen, Feld von Wahrheitswerten FLV mp4 mp3
Di,  12.11. 3 Felder: Feld von Indizes (Abzählreim), Feld von Zuständen (Endlicher Automat), Lineare Suche FLV mp4 mp3
Mo, 18.11. 3, 4 Binäre Suche, Methoden: aktuelle + formale Parameter, Übergabe von arrays, Sichtbarkeit FLV mp4 mp3
Di,  19.11. 4, 5 Rekursion: Fakultät, Potenzieren, Fibonacci, ggT, Türme von Hanoi FLV mp4 mp3
Mo, 25.11. 6 Komplexität: O-Notation, Analyse von Schleifen, Analyse eines rekursiven Programms FLV mp4 mp3
Di,  26.11. 6 Verifikation: partielle Korrektheit, Terminierung, Halteproblem (Algorithmen-Fee) FLV mp4 mp3
Mo, 02.12. 7 Sortieren: Greedy, SelectionSort, BubbleSort, MergeSort rekursiv, MergeSort iterativ FLV mp4 mp3
Di,  03.12. 7 Sortieren: Quicksort, Median FLV mp4 mp3
Mo, 09.12. 7 Sortieren: Baum, Heap, HeapSort FLV mp4 mp3
Di,  10.12. 7 Sortieren: Laufzeit und Platzbedarf, Untere Schranke für Sortieren durch Vergleichen, Bucket Sort FLV mp4 mp3
Mo, 16.12. 8 Objektorientierte Programmierung: Class Person, Vererbung, Class Student, Binden, Abzählreim FLV mp4 mp3
Di,  17.12. 8 ADT: Interface, ADT Liste FLV mp4 mp3
Mo, 06.01. 9 ADT: Keller, Reverse, Klammerung, CharKeller, Infix-Postfix FLV mp4 mp3
Di, 07.01. 9 ADT: Schlange, Baum, VerweisBaum FLV mp4 mp3
Mo, 13.01. 9 ADT: Traverse, TiefenSuche, BreitenSuche, PostfixBaumBau, Interface Enumeration, PreorderTraverse FLV mp4 mp3
Di, 14.01. 9 SuchBaum: Comparable, Interface Menge, Insert, Delete, Lookup FLV mp4 mp3
Mo,  20.01. 9 Suchbaum: Implementation von Lookup, Insert, SuchBaumTest, ausgeglichen, AVLBaum FLV mp4 mp3
Di,  21.01. 10,11 Hashing: Kollision, Sondieren, offenes + geschlossenes Hashing, HashSet, HashMap FLV mp4 mp3
Mo, 27.01. 12 Graphen: Modellierung, Fragestellungen, Implementation, All-Pairs-Shortest Path FLV mp4 mp3
Di,  28.01. 12 Graphen: Vertex, Edge, Single-Source-Shortest-Path, Topologisches Sortieren, Hamiltonkreis FLV mp4 mp3
Mo, 03.02. 12 Graphen: Maximaler Fluss, Minimaler Cut, erweiternder Weg, Ford Fulkerson FLV mp4 mp3
Di,  04.02. 12 Graphen: Spannbaum, Matching, Chinese Postman FLV mp4 mp3
Di,  11.02. - Wanderung
Mo,  17.02. - Klausur
Literatur