Uni-Logo Institut für Informatik

Algorithmen WS 2011/12
-->
Dozent Prof. Dr. Oliver Vornberger
Übungsleiter Sebastian Büscher, M.Sc., Nicolas Neubauer, M.Sc.
Tutoren Peter Biermanski, Sven Boge, Sebastian Brockmeyer, Christian Flothmann, Benjamin Graf, Kathrin Grosse, Nils Haldenwang, Julian Kniephoff, Jana Lehnfeld, Nico Marniok, B.Sc., Niels Meyering, Philipp Middendorf, Philip Münch, Francesca Panter, Sebastian Pütz, Manuel Schwarz, Sabine Seyffahrt, Alexandre Witte
Vorlesung montags und dienstags, 14:15 - 15:45 Uhr, Raum 32/102
Übung

Pfeil zur Übungsseite

Sebastian Büscher: donnerstags, 08:15 - 09:45 Uhr, Raum 69/117
donnerstags, 10:15 - 11:45 Uhr, Raum 31/E06
Nicolas Neubauer: donnerstags, 12:30 - 14:00 Uhr, Raum 66/E33
donnerstags, 14:15 - 15:45 Uhr, Raum 31/E06
erste Übung: 27.10.2011, alle vier Übungen haben den gleichen Inhalt
1. Klausur Freitag, 10.02.2012, 14:30 - 16:30 Uhr
(Räume und Verteilung wird noch bekannt gegeben)
2. Klausur Donnerstag, 12.04.2012, 09:30 - 11:30 Uhr
(Räume und Verteilung wird noch bekannt gegeben)
Evaluation der Veranstaltung durch interne Hörer
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 5 Euro erworben werden)
Foto Die Teilnehmer der Veranstaltung (mit Markierungen)
Foto in Vollauflösung
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 den Podcast im Apple Store finden und abonnieren.
Ablauf
Datum Kapitel Thema Video Video Audio
Mo, 17.10. 1 Einführung: Organisation, Informatik, Algorithmus, Anweisungen, Collatz-Funktion FLV mp4 mp3
Di,  18.10. - Vorkurs: Organisation, Übungsbetrieb, Systemadministration, Installation, Algotools FLV mp4 mp3
Mo, 24.10. 2 Java - Sprachmerkmale, Variablen, Bedingungen, Fallunterscheidungen FLV mp4 mp3
Di,  25.10. 2 Schleifen: while, do-while, for, Berechnung der Fakultät, Berechnung des GGT FLV mp4 mp3
Mo, 31.10. 2 Java-Datentypen: Ganze Zahlen (byte, short, int, long), Gleitkommazahlen (float) FLV mp4 mp3
Di,  01.11. 2 Java-Datentypen: Gleitkommazahlen (Fortsetzung), Boolean, Character, Typumwandlung, Konstanten FLV mp4 mp3
Mo, 07.11. 3 Felder: Feld von Ziffern, Feld von Daten, Feld von Zeichen, Feld von Wahrheitswerten FLV mp4 mp3
Di,  08.11. 3 Felder: Feld von Indizes (Abzählreim), Feld von Zuständen (Endlicher Automat), Lineare Suche FLV mp4 mp3
Mo, 14.11. 3, 4 Binäre Suche, Methoden: aktuelle + formale Parameter, Übergabe von arrays, Sichtbarkeit FLV mp4 mp3
Di,  15.11. 4, 5 Fehlerbehandlung, Rekursion, Fakultät, Potenzieren, Fibonacci, ggT, Türme von Hanoi FLV mp4 mp3
Mo, 21.11. 6 Komplexität, O-Notation, Analyse von Schleifen, Analyse eines rekursiven Programms FLV mp4 mp3
Di,  22.11. 6 Verifikation, partielle Korrektheit, Terminierung, Halteproblem (Algorithmen-Fee) FLV mp4 mp3
Mo, 28.11. 7 Greedy, Divide-&-Conquer, SelectionSort, BubbleSort, MergeSort rekursiv, MergeSort iterativ FLV mp4 mp3
Di,  29.11. 7 Quicksort, Median FLV mp4 mp3
Mo, 05.12. 7 Baum, Heap, HeapSort FLV mp4 mp3
Di,  06.12. 7 Sortieren: Laufzeit und Platzbedarf, Untere Schranke für Sortieren durch Vergleichen, Bucket Sort FLV mp4 mp3
Mo, 12.12. 8 Objektorientierte Programmierung, Class Person, Vererbung, Class Student, Binden, Kinderabzählreim FLV mp4 mp3
Di,  13.12. 8 ADT, Interface, ADT Liste FLV mp4 mp3
Mo, 02.01. 9 ADT Keller, Reverse, Klammerung, CharKeller, Infix-Postfix FLV mp4 mp3
Di, 03.01. 9 Schlange, Baum, VerweisBaum FLV mp4 mp3
Mo, 09.01. 9 Traverse, TiefenSuche, BreitenSuche, PostfixBaumBau, Interface Enumeration, PreorderTraverse FLV mp4 mp3
Di, 10.01. 9 SuchBaum, Comparable, Interface Menge, Insert, Delete, Lookup FLV mp4 mp3
Mo,  16.01. 9 SuchBaumTest, Klassendiagramm, ausgeglichen, Balance, AVLBaum FLV mp4 mp3
Di,  17.01. 10 Hashfunktion, Kollision, Sondieren, offenes + geschlossenes Hashing, HashSet, HashMap FLV mp4 mp3
Mo, 23.01. 11 Graphen: Modellierung, Probleme, Implementation, All-Pairs-Shortest Path FLV mp4 mp3
Di,  24.01. 11 Graphen: Vertex, Edge, Single-Source-Shortest-Path, Topologisches Sortieren, Hamiltonkreis FLV mp4 mp3
Mo, 30.01. 11 Graphen: Maximaler Fluss, Implementation von ungerichteten Graphen FLV mp4 mp3
Di,  31.01. 11 Graphen: Spannbaum, Matching, Chinese Postman FLV mp4 mp3
Di,  07.02. - Wanderung
Fr,  10.02. - Klausur
Literatur