Uni-Logo Institut für Informatik

Algorithmen WS 2016/17

Dozent Prof. Dr. Oliver Vornberger
Übungsleiter Nils Haldenwang, M.Sc., Lukas Kalbertodt, B.Sc.
Tutoren Dennis Altenhoff, Johan von Behren, Franziska Becker, Miriam Beutel, Malte Bo├čert, Jan-Niklas Brandes, Lena Dorfschmidt, Alejandro Dinkelberg, Christoph Eichler, Till Grenzdörffer, Laura Hembrock, Katrin Ihler, Famke Lamberti, Hannah Lewerentz, Matthias Jansen, Moritz Nipshagen, Svantje Jung, Timo Osterkamp, Ann-Kathrin Schalkamp, Lena Scholz, Andreas Schröder, Kevin Trebing, Rene Warnking, Philipp Wicke, Joshua Wiebe, Sven Wilke
Vorlesung montags und dienstags, 14:15 - 15:45 Uhr, Raum 32/102 und per Videostream in 32/109 und 32/110
Übung
Lukas Kalbertodt: donnerstags, 08:30 - 10:00 Uhr, Raum 31/E06
donnerstags, 10:15 - 11:45 Uhr, Raum 31/E06
Nils Haldenwang: donnerstags, 12:15 - 13:45 Uhr, Raum 93/E31
donnerstags, 14:15 - 15:45 Uhr, Raum 93/E31

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.
Literatur Vorlesungsskript (HTML),     Vorlesungsskript (PDF)     (Das Skript kann in der ersten Vorlesungsstunde für 5 € erworben werden.)

Die Veranstaltung behandelt (naturgemäß) nur einen Teil der Programmiersprache Java und auch nur exemplarisch einige wichtige Datenstrukturen. Der prüfungsrelevante Stoff ist vollständig in diesem Skript dokumentiert. Wer sich darüberhinaus noch umfassender informieren möchte, sei auf folgende Bücher verwiesen:

  • Christian Ullenboom:
    "Java ist auch eine Insel", 10. Auflage, Galileo Computing, 2011
    Onlinefassung: http://openbook.galileocomputing.de/javainsel/
  • Robert Sedgewick, Kevin Wayne:
    "Einführung in die Programmierung mit Java", Pearson, 2011
Evaluation über stud.ip-Fragebogen (PDF)
Foto Die Teilnehmer der Veranstaltung
Die Teilnehmer der Veranstaltung (mit Markierungen)
Vorlesungsmitschnitte und Podcast Von der Vorlesung werden Film- und Tonaufzeichnungen erstellt und als HTML5-Video, mp4-Video und mp3-Audio angeboten. 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.
Ablauf
Datum Kapitel Thema Video Video Audio
Mo, 24.10. 1 Einführung: Organisation, Informatik, Algorithmus, Anweisungen, Collatz-Funktion FLV mp4 mp3
Di,  25.10. - Organisation: Übungsbetrieb, Systemadministration, Installation, Algotools FLV mp4 mp3
Mo, 31.10. 2 Java: Sprachmerkmale, Variablen, Bedingungen, Fallunterscheidungen FLV mp4 mp3
Di,  01.11. 2 Schleifen: while, do-while, for, Berechnung der Fakultät, Berechnung des GGT FLV mp4 mp3
Mo, 07.11. 2 Datentypen: Ganze Zahlen (byte, short, int, long), Gleitkommazahlen (float) FLV mp4 mp3
Di,  08.11. 2 Datentypen: Gleitkommazahlen (double), Boolean, Character, Typumwandlung, Konstanten FLV mp4 mp3
Mo, 14.11. 3 Felder: Feld von Ziffern, Feld von Daten, Feld von Zeichen, Feld von Wahrheitswerten FLV mp4 mp3
Di,  15.11. 3 Felder: Feld von Indizes (Abzählreim), Feld von Zuständen (Endlicher Automat), Lineare Suche FLV mp4 mp3
Mo, 21.11. 3, 4 Binäre Suche, Methoden: aktuelle + formale Parameter, Übergabe von arrays, Sichtbarkeit FLV mp4 mp3
Di,  22.11. 4, 5 Rekursion: Fakultät, Potenzieren, Fibonacci, ggT, Türme von Hanoi FLV mp4 mp3
Mo, 28.11. 6 Komplexität: O-Notation, Analyse von Schleifen, Analyse eines rekursiven Programms FLV mp4 mp3
Di,  29.11. 6 Verifikation: partielle Korrektheit, Terminierung, Halteproblem (Algorithmen-Fee) FLV mp4 mp3
Mo, 05.12. 7 Sortieren: Greedy, SelectionSort, BubbleSort, MergeSort rekursiv, MergeSort iterativ FLV mp4 mp3
Di,  06.12. 7 Sortieren: Quicksort, Median FLV mp4 mp3
Mo,   12.12. 7 Sortieren: Baum, Heap, HeapSort FLV mp4 mp3
Di,  13.12. 7 Sortieren: Laufzeit und Platzbedarf, Untere Schranke, Bucket Sort, Objektorientierung FLV mp4 mp3
Mo,  02.01. 8 Objektorientierte Programmierung: Class Person, Vererbung, Class Student, Binden, Abzählreim FLV mp4 mp3
Di,  03.01. 8 ADT: Interface, ADT Liste FLV mp4 mp3
Mo, 09.01. 9 ADT: Keller, Reverse, Klammerung, CharKeller, Infix-Postfix FLV mp4 mp3
Di, 10.01. 9 ADT: Schlange, Baum, VerweisBaum FLV mp4 mp3
Mo, 16.01. 9 ADT: Traverse, TiefenSuche, BreitenSuche, PostfixBaumBau, Enumeration, PreorderTraverse FLV mp4 mp3
Di, 17.01. 9 SuchBaum: Comparable, Interface Menge, Insert, Delete, Lookup FLV mp4 mp3
Mo,  23.01. 9 Suchbaum: Implementation von Lookup, Insert, SuchBaumTest, ausgeglichen, AVLBaum FLV mp4 mp3
Di,  24.01. 10,11 Hashing: Kollision, Sondieren, offenes + geschlossenes Hashing, HashSet, HashMap FLV mp4 mp3
Mo, 30.01. 12 Graphen: Modellierung, Fragestellungen, Implementation, All-Pairs-Shortest Path FLV mp4 mp3
Di,  31.01. 12 Graphen: Vertex, Edge, Single-Source-Shortest-Path, Topologisches Sortieren, Hamiltonkreis FLV mp4 mp3
Mo, 06.02. 12 Graphen: Maximaler Fluss, Minimaler Cut, erweiternder Weg, Ford Fulkerson FLV mp4 mp3
Di,  07.02. 12 Graphen: Spannbaum, Matching, Chinese Postman FLV mp4 mp3
Mo,  13.02. - Wanderung
Do,  23.02. - Klausur