WS 2017/18: Seminar "Graphen in der Informatik: Algorithmen und Modellierung"

Inhalt

Graphen, bestehend aus Knoten und Kanten, kommen in der Informatik in vielen Zusammenhängen vor. Beispielsweise können Rechner- und Straßennetze, das Internet, Nachbarschaftsbeziehungen, endliche Automaten, Transitionssysteme und semantische Beziehungen geeignet durch Graphen beschrieben werden. Es ist daher wichtig, Verfahren und Methoden zu besitzen, die die Struktur von Graphen untersuchen und auch Graphen transformieren können, wenn sich die Topologie des zu untersuchenden Systems ändern sollte. Insbesondere geht es in diesem Seminar um folgende Themen:

  • Graphentheorie: Welche Typen von Graphen gibt es? Welche Strukturen treten in Graphen auf? Welche bekannten Sätze über Graphen gibt es? (z.B. Vierfarbentheorem)
  • Graphalgorithmen: Wie kann man Graphen am besten algorithmisch verarbeiten? Welche Verfahren gibt es, um Graphen zu untersuchen (z.B. Chinese Postman Problem, Max Flow)? Wie lassen sich Graphen zeichnen/visualisieren?
  • Graphtransformation: Wie kann man Graphen mit Hilfe von Regeln transformieren? Wie funktionieren Graphgrammatiken? Wie kann man nebenläufige Systeme mit Hilfe von Graphtransformationsregeln modellieren?
  • Soziale Netzwerke als Graphen: Besonders mit dem verstärkten Aufkommen von Sozialen Medien und Sozialen Netwerk Seiten (Facebook, LinkedIn, ...) hat das Interesse an der Modellierung von sozialen Netzwerken durch Graphen stark zugenommen. Interessante Fragen sind zum Beispiel: Wer sind die wichtigen Akteure in einem sozialen Netzwerk? Lassen sich Individuen anhand der Graphenstruktur zu logischen Gruppen zusammenfassen? Wie erzeugen Facebook und Co Vorschläge für Personen die ich kennen könnte?

Themen und Literatur

Die Themen und dazugehörigen Literatur werden im Einführungstreffen am Montag, den 16.10.2017 bekanntgegeben. Die Themen befinden sich in den Bereichen "Klassische Graphentheorie", "Algorithmen auf Graphen", "Graphtransformationssysteme" und "Analyse sozialer Netzwerke".

Betreuung

Jeder Teilnehmer und jede Teilnehmerin wird von einem Dozenten oder einer Dozentin betreut. Der Betreuer oder die Betreuerin steht zur Verfügung für inhaltliche und Verständnisfragen, sowie für Hilfe bei der Bearbeitung der Vortragsfolien, dem Schreiben der Ausarbeitung und der Vorbereitung des Vortrags.

© Universität Duisburg-Essen, Lehrstuhl Theoretische InformatikLogin