• Der Veranstaltungsbeginn muss leider im Normalfall aufgrund eines Konfliktes bei 14:45 Uhr bleiben. Wir werden aber an ausgewählten Terminen bereits um 14 Uhr beginnen, das nächste Mal am 15. Mai.
  Also: Nächste Vorlesung: 15. Mai, 14 Uhr!

Graphen gehören zu den wichtigsten abstrakten Datenstrukturen in der Informatik. Sie haben sich als mächtiges Werkzeug zur Modellierung komplexer Probleme erwiesen. Daher sind Graphen nicht nur ein Kerngebiet der theoretischen Informatik, sondern auch allgegenwärtig in täglichen Anwendungen. Die zunehmende Komplexität von Graphen und Netzwerken in realen Anwendungen hat bewirkt, dass eine Bearbeitung immer häufiger auf Parallelrechnern erfolgt. Dabei ergeben sich einige Herausforderungen, etwa die Implementierung paralleler Graphenalgorithmen mit guter paralleler Performanz. In dieser Veranstaltung werden diese Herausforderungen angegangen, indem man die Dualität zwischen Graphen und Matrizen ausnutzt. Es wird gezeigt, wie man parallele Matrixberechnungen zur Implementierung von skalierbaren parallelen Graphenalgorithmen benutzen kann.

• Folien vom 15. Mai
• Übungsblatt 4


• Folien vom 8. Mai
• Übungsblatt 3


• Folien vom 24. April
• Code für MIS (ersetzt am 8. Mai)
• Übungsblatt 2


• Folien vom 17. April
• Codebeispiel vom 17. April
• Übungsblatt 1

• Nächstes Treffen: 1. Juni, 11.30 - 13.30 Uhr. Raum wird noch bekanntgegeben.
• Hauptvorträge: 25. bzw. 26. Juli, Details werden noch besprochen.
• Folien vom 10. Mai: Vortrag Präsentationsmethodik, Fachvortrag

Die Seminarthemen behandeln das Feld der Optimierung mit Metaheuristiken und Approximationsalgorithmen. Beides sind Lösungstechniken für schwierige Optimierungsprobleme, für die keine effizienten Lösungsverfahren bekannt sind. Der Vorteil der Approximationsalgorithmen ist, dass sie eine gewisse Güte der berechneten Lösung garantieren. Dies gilt bei Metaheuristiken (normalerweise) nicht. Allerdings sind letztere meistens einfacher zu implementieren und haben oft eine geringere Laufzeit.

Wir werden in diesem Seminar mehrere Vertreter dieser beiden Algorithmenklassen kennenlernen. Zusätzlich wird sich mindestens ein Thema mit parallelen Aspekten von Metaheuristiken beschäftigen.

Jeder Teilnehmer muss zur erfolgreichen Teilnahme folgende Leistungen erbringen:

• Teilnahme an den Seminarveranstaltungen
• Gelungener Seminarvortrag (45 Minuten inkl. Diskussion, entspricht knapp 40 Minuten Vortrag), der nachweist, dass das zugewiesene Thema selbstständig erarbeitet und verstanden wurde.
• Eine eigene Ausarbeitung, die das Thema im Vergleich zum Vortrag breiter und tiefer beleuchtet. Hierbei genügt es natürlich nicht, den/die Original-Artikel zu übersetzen.
• Formale Anforderungen: 14-17 Seiten reiner Text (plus Deckblatt, Inhaltsverzeichnis, Literaturverzeichnis), Schriftgröße 11pt, 1.1facher Zeilenabstand, außen etwas breiterer Korrekturrand.
• Abgabeformat: pdf. Die Anfertigung mit LaTeX wird empfohlen, ist aber keine Bedingung (den Unerfahrenen bzgl. LaTeX sei der leichtere Einstieg mit dem Frontend LyX ans Herz gelegt).

• Vorlesung und Übung fallen am 21. Dezember aus. Die Zeiten werden durch Verlängerung späterer Termine nachgeholt. Vorlesung und Übung am 11. Januar und 1. Februar finden aus dienstlichen Gründen von 14.00-16.00 Uhr statt! Außerdem beginnen wir am 18.1., 25.1. und 8.2. auch bereits um 14.00 Uhr (bei normalem Ende).
• Diese Veranstaltung ist auch im Diplomstudiengang prüfbar. Als Vertiefungsgebiete sind Theoretische Grundlagen und Algorithmentechnik möglich.

Netzwerke in physischer Form oder als Modellierungsgegenstand sind heutzutage allgegenwärtig. Physisch realisierte Netzwerke treten beispielsweise in technischen Bereichen (Strom, Telefon) oder dem Transportwesen auf. Neuerdings gewinnen abstrakte Netzwerke, etwa zur Modellierung der Verbindungsstruktur des World Wide Web oder von sozialen Kontakten, eine große Bedeutung. Bedingt durch die Vielzahl der Anwendungen und resultierenden Fragestellungen, kommt dabei ein reicher Methodenkatalog zur Anwendung. Es werden unter anderem Techniken aus der Graphentheorie und der linearen Algebra angewendet. Außerdem werden interessante Zusammenhänge zu probabilistischen Methoden deutlich.

In dieser Veranstaltung sollen einige der eingesetzten Methoden und deren Grundlagen systematisch behandelt werden. Fragestellungen werden exemplarisch an Anwendungsbeispielen motiviert, der Schwerpunkt wird auf den zur Lösung verwendeten algorithmischen Vorgehensweisen sowie deren Voraussetzungen und Eigenschaften liegen.

• Folien zur Vorlesung am 19.10.2011
• Übungsblatt 1
• Folien zur Vorlesung am 26.10.2011 (aktualisiert am 03.11.)
• Übungsblatt 2
• Folien zur Vorlesung am 02.11.2011
• Übungsblatt 3
• DFS-Beispiel, 2 Seiten pro Blatt
• Folien zur Vorlesung am 09.11.2011
• Header fürs Parsen, Quelldatei fürs Parsen
• Übungsblatt 4
• Folien zur Vorlesung am 16.11.2011
• Übungsblatt 5 (aktualisiert am 21.11.)
• Folien (Satz 1) zur Vorlesung am 23.11.2011
• Folien (Satz 2) zur Vorlesung am 23.11.2011
• Übungsblatt 6
• Folien zur Vorlesung am 30.11.2011
• Übungsblatt 7
• Folien zur Vorlesung am 07.12.2011
• Übungsblatt 8
• Vorlesung am 14.12.2011: Cluster-Koeffizienten, Bloom-Filter
• Übungsblatt 9
• Folien zur Vorlesung am 11.01.2012
• Übungsblatt 10
• Folien zur Vorlesung am 18.01.2012
• Übungsblatt 11
• Folien zur Vorlesung am 25.01.2012
• Übungsblatt 12
• Folien zur Vorlesung am 01.02.2012
• Folien zur Vorlesung am 08.02.2012

• M. E. J. Newman: Networks. An Introduction. Oxford University Press, 2010.
• Network Analysis