|
|
| Dozent |
Prof. Dr. Oliver Vornberger |
| Übungsleiter |
Nils Haldenwang, M.Sc., Ann-Katrin Häuser, M.Sc. |
| Tutoren |
Dennis Altenhoff,
Miriam Beutel,
Christoph Eichler,
Till Grenzdörffer,
Steffen Hartmeyer,
Svantje Jung,
Valentin Koch,
Hendrik Langebrake,
Christoph Stenkam,
Alexander Tessmer,
Kevin Trebing,
Johan von Behren,
Timo Bourdon,
Christian Heiden,
Lukas Kalbertodt,
Julian Kniephoff, B.Sc.,
Niels Meyering, B.Sc.,
Lena Scholz,
Manuel Schwarz, B.Sc.
|
|
| Vorlesung |
montags und dienstags, 14:15 - 15:45 Uhr, Raum 32/102
|
| Übung |
| Ann-Katrin Häuser: |
donnerstags, 08:30 - 10:00 Uhr, Raum 31/E06
donnerstags, 10:15 - 11:45 Uhr, Raum 31/E06 |
| Nils Haldenwang: |
donnerstags, 12:30 - 14:00 Uhr, Raum 31/E05
donnerstags, 14:15 - 15:45 Uhr, Raum 31/E05 |
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 2,50 € 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 |
Hörer der Vorlesung über Online-Fragebogen (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.
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 |
| Mo, 13.10. |
1 |
Einführung: Organisation, Informatik, Algorithmus, Anweisungen, Collatz-Funktion |
FLV |
mp4 |
| Di, 14.10. |
- |
Vorkurs: Organisation, Übungsbetrieb, Systemadministration, Installation, Algotools |
FLV |
mp4 |
| Mo, 20.10. |
2 |
Java: Sprachmerkmale, Variablen, Bedingungen, Fallunterscheidungen |
FLV |
mp4 |
| Di, 21.10. |
2 |
Schleifen: while, do-while, for, Berechnung der Fakultät, Berechnung des GGT |
FLV |
mp4 |
| Mo, 27.10. |
2 |
Datentypen: Ganze Zahlen (byte, short, int, long), Gleitkommazahlen (float) |
FLV |
mp4 |
mp3 |
| Di, 28.10. |
2 |
Datentypen: Gleitkommazahlen (double), Boolean, Character, Typumwandlung, Konstanten |
FLV |
mp4 |
mp3 |
| Mo, 03.11. |
3 |
Felder: Feld von Ziffern, Feld von Daten, Feld von Zeichen, Feld von Wahrheitswerten |
FLV |
mp4 |
mp3 |
| Di, 04.11. |
3 |
Felder: Feld von Indizes (Abzählreim), Feld von Zuständen (Endlicher Automat), Lineare Suche |
FLV |
mp4 |
mp3 |
| Mo, 10.11. |
3, 4 |
Binäre Suche, Methoden: aktuelle + formale Parameter, Übergabe von arrays, Sichtbarkeit |
FLV |
mp4 |
mp3 |
| Di, 11.11. |
4, 5 |
Rekursion: Fakultät, Potenzieren, Fibonacci, ggT, Türme von Hanoi |
FLV |
mp4 |
mp3 |
| Mo, 17.11. |
6 |
Komplexität: O-Notation, Analyse von Schleifen, Analyse eines rekursiven Programms |
FLV |
mp4 |
mp3 |
| Di, 18.11. |
6 |
Verifikation: partielle Korrektheit, Terminierung, Halteproblem (Algorithmen-Fee) |
FLV |
mp4 |
mp3 |
| Mo, 24.11. |
7 |
Sortieren: Greedy, SelectionSort, BubbleSort, MergeSort rekursiv, MergeSort iterativ |
FLV |
mp4 |
mp3 |
| Di, 25.11. |
7 |
Sortieren: Quicksort, Median |
FLV |
mp4 |
mp3 |
| Mo, 01.12. |
7 |
Sortieren: Baum, Heap, HeapSort |
FLV |
mp4 |
mp3 |
| Di, 02.12. |
7 |
Sortieren: Laufzeit und Platzbedarf, Untere Schranke, Bucket Sort, Objektorientierung |
FLV |
mp4 |
mp3 |
| Mo, 08.12. |
8 |
Objektorientierte Programmierung: Class Person, Vererbung, Class Student, Binden, Abzählreim |
FLV |
mp4 |
mp3 |
| Di, 09.12. |
8 |
ADT: Interface, ADT Liste |
FLV |
mp4 |
mp3 |
| Mo, 15.12. |
9 |
ADT: Keller, Reverse, Klammerung, CharKeller, Infix-Postfix |
FLV |
mp4 |
mp3 |
| Di, 16.12. |
9 |
ADT: Schlange, Baum, VerweisBaum |
FLV |
mp4 |
mp3 |
| Mo, 05.01. |
9 |
ADT: Traverse, TiefenSuche, BreitenSuche, PostfixBaumBau, Interface Enumeration, PreorderTraverse |
FLV |
mp4 |
mp3 |
| Di, 06.01. |
9 |
SuchBaum: Comparable, Interface Menge, Insert, Delete, Lookup |
FLV |
mp4 |
mp3 |
| Mo, 12.01. |
9 |
Suchbaum: Implementation von Lookup, Insert, SuchBaumTest, ausgeglichen, AVLBaum |
FLV |
mp4 |
mp3 |
| Di, 13.01. |
10,11 |
Hashing: Kollision, Sondieren, offenes + geschlossenes Hashing, HashSet, HashMap |
FLV |
mp4 |
mp3 |
| Mo, 19.01. |
12 |
Graphen: Modellierung, Fragestellungen, Implementation, All-Pairs-Shortest Path |
FLV |
mp4 |
mp3 |
| Di, 20.01. |
12 |
Graphen: Vertex, Edge, Single-Source-Shortest-Path, Topologisches Sortieren, Hamiltonkreis |
FLV |
mp4 |
mp3 |
| Mo, 26.01. |
12 |
Graphen: Maximaler Fluss, Minimaler Cut, erweiternder Weg, Ford Fulkerson |
FLV |
mp4 |
mp3 |
| Di, 27.01. |
12 |
Graphen: Spannbaum, Matching, Chinese Postman |
FLV |
mp4 |
mp3 |
| Mo, 02.02. |
- |
Wanderung |
| Fr, 13.02. |
- |
Klausur |
|
zur Übungsseite