Uni-Logo Institut für Informatik

Algorithmen WS 2010/11
Dozent Prof. Dr. Oliver Vornberger
Übungsleiter Nicolas Neubauer, M.Sc., Mathias Menninghaus
Tutoren Sebastian Brockmeyer, Christian Flothmann, Nils Haldenwang, Julian Kniephoff, Daniel Künne, B.Sc., Jana Lehnfeld, Jirka Lewandowski, Nico Marniok, Niels Meyering, Philipp Middendorf, Ilja Muhl, Philip Münch, Manuel Schwarz
Vorlesung montags und dienstags, 14:15 - 15:45 Uhr, Raum 32/102
Übung

Pfeil zur Übungsseite

Mathias Menninghaus: donnerstags, 08:30 - 10:00 Uhr, Raum 31/449a
donnerstags, 10:15 - 11:45 Uhr, Raum 31/449a
Nicolas Neubauer: donnerstags, 12:30 - 14:00 Uhr, Raum 66/E34
donnerstags, 14:15 - 15:45 Uhr, Raum 66/E34
erste Übung: 28.10.2010, alle vier Übungen haben den gleichen Inhalt
1. Klausur Dienstag, 15.02.2011, 13:30 - 15:30 Uhr
Raum 01/E01+02 und 01/B01+02 (HVZ, Kolpingstraße)
2. Klausur Donnerstag, 31.03.2011, 10:30 - 12:30 Uhr
Raum 01/E01+02 und 01/B01+02 (HVZ, Kolpingstraße)
Evaluation der Veranstaltung durch interne Hörer,     der Veranstaltung durch externe Hörer,     der Tutoren durch die Studenten
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 (mit Markierungen)
Foto in Vollauflösung
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.
Ablauf
Datum Kapitel Thema Video Video Audio
Mo, 18.10. 1 Einführung: Organisation, Informatik, Algorithmus, Anweisungen, Collatz-Funktion FLV MP4 MP3
Di,  19.10. - Vorkurs: Organisation, Übungsbetrieb, Systemadministration, Installation, Algotools FLV MP4 MP3
Mo, 25.10. 2 Java - Sprachmerkmale, Variablen, Bedingungen, Fallunterscheidungen FLV MP4 MP3
Di,  26.10. 2 Schleifen: while, do-while, for, Berechnung der Fakultät, Berechnung des GGT FLV MP4 MP3
Mo, 01.11. 2 Java-Datentypen: Ganze Zahlen, Gleitkommazahlen FLV MP4 MP3
Di,  02.11. 2 Java-Datentypen: Gleitkommazahlen (Fortsetzung), Boolean, Character, Typumwandlung, Konstanten FLV MP4 MP3
Mo, 08.11. 3 Felder: Feld von Ziffern, Feld von Daten, Feld von Zeichen, Feld von Wahrheitswerten FLV MP4 MP3
Di,  09.11. 3 Felder: Feld von Indizes (Abzählreim), Feld von Zuständen (Endlicher Automat), Lineare Suche FLV MP4 MP3
Mo, 15.11. 3, 4 Binäre Suche, Methoden: aktuelle + formale Parameter, Übergabe von arrays, Sichtbarkeit FLV MP4 MP3
Di,  16.11. 4, 5 Fehlerbehandlung, Rekursion, Fakultät, Potenzieren, Fibonacci, ggT, Türme von Hanoi FLV MP4 MP3
Mo, 22.11. 6 Komplexität, O-Notation, Analyse von Schleifen, Analyse eines rekursiven Programms FLV MP4 MP3
Di,  23.11. 6 Verifikation, partielle Korrektheit, Terminierung, Halteproblem (Algorithmen-Fee) FLV MP4 MP3
Mo, 29.11. 7 Greedy, Divide-&-Conquer, SelectionSort, BubbleSort, MergeSort rekursiv, MergeSort iterativ FLV MP4 MP3
Di,  30.11. 7 Quicksort, Median FLV MP4 MP3
Mo, 06.12. 7 Baum, Heap, HeapSort FLV MP4 MP3
Di,  07.12. 7 Sortieren: Laufzeit und Platzbedarf, Untere Schranke für Sortieren durch Vergleichen, Bucket Sort FLV MP4 MP3
Mo, 13.12. 8 Objektorientierte Programmierung, Class Person, Vererbung, Class Student, Binden, Kinderabzählreim FLV MP4 MP3
Di,  14.12. 8 ADT, Interface, ADT Liste FLV MP4 MP3
Mo, 03.01. 9 ADT Keller, Reverse, Klammerung, CharKeller, Infix-Postfix FLV MP4 MP3
Di, 04.01. 9 Schlange, Baum, VerweisBaum FLV MP4 MP3
Mo, 10.01. 9 Traverse, TiefenSuche, BreitenSuche, PostfixBaumBau, Interface Enumeration, PreorderTraverse FLV MP4 MP3
Di, 11.01. 9 SuchBaum, Comparable, Interface Menge, Insert, Delete, Lookup FLV MP4 MP3
Mo,  17.01. 9 SuchBaumTest, Klassendiagramm, ausgeglichen, Balance, AVLBaum FLV MP4 MP3
Di,  18.01. 10 Hashfunktion, Kollision, Sondieren, offenes + geschlossenes Hashing, HashSet, HashMap FLV MP4 MP3
Mo, 24.01. 11 Graphen: Modellierung, Probleme, Implementation, All-Pairs-Shortest Path FLV MP4 MP3
Di,  25.01. 11 Graphen: Vertex, Edge, Single-Source-Shortest-Path, Topologisches Sortieren, Hamiltonkreis FLV MP4 MP3
Mo, 31.01. 11 Graphen: Maximaler Fluss, Implementation von ungerichteten Graphen FLV MP4 MP3
Di,  01.02. 11 Graphen: Spannbaum, Matching, Chinese Postman FLV MP4 MP3
Mo,  07.02. - Wanderung
Di,  15.02. - Klausur
Literatur