|
Christian Viergutz |
Programmierpraktikum |
|
| Letzte Änderung: 15.12.2011 |
Inhalt:
Zu den wichtigsten Modellen der Informatik zählen Graphen, die zahlreiche praktische Anwendungen haben, z.B. im Verkehrs- und Telekommunikations-Bereich, der Produktionsplanung etc. Zu Beginn sollen die Teilnehmer die freie Java-Graphenbibliothek JGraphT kennenlernen und anhand einiger Beispiele die allgemeine Funktionsweise des Frameworks erkunden. Darauf aufbauend sollen in kleinen Gruppen eigene Lösungsalgorithmen für graphbasierte Problemstellungen implementiert und getestet werden. Größere Vorkenntnisse aus dem Bereich der Graphenalgorithmen werden dabei nicht vorausgesetzt. Ziele des Praktikums:
|
Termine:
|
Material
| Eingestellt am | Datei | Inhalt |
|---|---|---|
| 26.02.2010 |
|
Folien aus der Vorbesprechung |
| 26.02.2010 |
|
Übersicht zu den Themengebieten der Kurzvorträge |
| 08.03.2010 |
|
Aufgabenblatt 1 (JGraphT, Hypercubes, Graphentraversierungen) |
| 08.03.2010 |
|
Library-Paket zu JGraphT (blatt1.tar.gz) |
| 09.03.2010 |
|
Grundlagen zur Benutzung von Eclipse (A. Kamenew, A. Lorenz) |
| 09.03.2010 |
|
Einführung der Tiefensuche |
| 09.03.2010 |
|
Aufgabenblatt 2 (De Bruijn-Netzwerke, DFS mit Kantenklassifikation, Test auf Zyklen) |
| 11.03.2010 |
|
Aufgabenblatt 3 (Visualisierung, Topologische Sortierung) |
| 11.03.2010 |
|
Java-Klasse GraphPresenter.java |
| 12.03.2010 |
|
Beispielgraph zum topologischen Sortieren |
| 15.03.2010 |
|
Aufgabenblatt 4 (Einlesen von Graphen, Minimale Spannbäume) |
| 15.03.2010 |
|
Testinstanzen für MST |
| 17.03.2010 |
|
Aufgabenblatt 5 (Kürzeste Wege, Dijkstra, Routensuche) |
| 17.03.2010 |
|
Testinstanzen für das Routingproblem |
| 17.03.2010 |
|
Versionskontrolle mit Subversion (J. Helmsmüller) |
| 19.03.2010 |
|
Bipartite Matchings (A. Hammer) |
| 19.03.2010 |
|
Aufgabenblatt 6 (Matchings in bipartiten Graphen) |
| 19.03.2010 |
|
Testinstanzen: Bipartite Graphen |
| 22.03.2010 |
|
Aufgabenblatt 7 (Projekt Robomaze), korr. am 23.3. |
| 26.03.2010 |
|
Folien Abschlussbesprechung |
Teilnahme
Teilnehmen können alle interessierten Bachelor-Studierende aus den Studiengängen Informatik, Mathematik, Angewandte Systemwissenschaft und Cognitive Science. Die Veranstaltung zählt als Programmierpraktikum (P4 / 6 LP).
Vorkenntnisse
Von den Teilnehmern werden erwartet:
- Programmierkenntnisse in Java (wie sie z.B. durch Informatik A und B vermittelt werden)
- Grundlagen von Algorithmen und Datenstrukturen
Kenntnisse aus dem Bereich der Graphenalgorithmen sind nützlich, aber auf keinen Fall Voraussetzung für eine Teilnahme.
Scheinerwerb
Voraussetzung für den Erwerb eines Scheins zur Veranstaltung ist die regelmäßige aktive Teilnahme am Praktikum sowie die Präsentation eines Kurzvortrags im Rahmen des Praktikums.
Referenzen und Literatur
Software
- JGraphT
- B. Collins-Sussman, B.W. Fitzpatrick, C.M. Pilato (2009)
- Versionskontrolle mit Subversion, 2. Auflage, auch online verfügbar
Graphenalgorithmen
- R.K. Ahuja, T.L. Magnanti, J.B. Orlin (1993)
- Network Flows, Prentice Hall
- J.M. Aldous, R.J. Wilson (2003)
- Graphs and applications, Springer
- T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein (2009)
- Introduction to Algorithms, 3rd ed., MIT Press
- J. Gross, J. Yellen (2004)
- Handbook of graph theory, CRC Press
- T. Grünert, S. Irnich (2005)
- Optimierung im Transport, Bände I und II, Shaker Verlag, Aachen.
- R. Sedgewick (2003)
- Algorithms in Java, Pearson Studium, 3. Auflage
- V. Turau (2004)
- Algorithmische Graphentheorie, Oldenbourg
Programmieren in Java
- G. Krüger, T. Stark (2009)
- Handbuch der Java-Programmierung (online verfügbar), Addison Wesley, München, 6. Auflage
- C. Ullenboom (2009)
- Java ist auch eine Insel (online verfügbar), Galileo Press, 8. Auflage