|
|
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 |
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 |
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 |
- O. Vornberger:
"Algorithmen",
Vorlesungsskript Heft 152, WS 2010/11
- K. Arnold, J. Gosling:
"Die Programmiersprache Java",
Addison-Wesley, 1. Auflage, Juni 2001
- D. Flanagan:
"Java In A Nutshell (engl. Edition für Java 1.5)",
O'Reilly, 5. Auflage, März 2005, ca. 42 €
- R. Sedgewick:
"Algorithms in Java, Teil 1-4",
Pearson Studium, 3. Auflage, Juli 2003, ca. 50 €
- G. Krüger, T. Stark:
"Handbuch der Java-Programmierung (online lesbar)",
Addison Wesley, München, 5. Auflage, Dezember 2008, ca. 40 €
- C. Ullenboom:
"Java ist auch eine Insel (online lesbar)",
Gallileo Press, 8. aktualisierte Auflage, Januar 2009, ca. 50 €
- R. Sedgewick: "Einführung in die Programmierung mit Java",
Pearson, 2011
|