Seminar ``Graphen in der Informatik: Algorithmen und … · 2013-04-04 · Algebraic approaches to graph transformation, part I: Basic concepts and double pushout approach. Handbook

Graphen in der Informatik Allgemeine Hinweise Themen und Zeitplan Tipps zum Halten eines Vortrags Verschiedenes

Seminar “Graphen in der Informatik:Algorithmen und Modellierung”

Organisatorisches &Tipps zum Halten eines Vortrags

Prof. Dr. Barbara Konig, Dr. Sander Bruggink,Christoph Blume, Jan Stuckrath,

Henning Kerstan, Sebastian Kupper

13. Marz 2013

Konig, Bruggink, Blume, Stuckrath, Kerstan, Kupper Seminar “Graphen in der Informatik” 1


Graphen in der Informatik

Graphen dienen der Darstellung und Modellierung

Rechnernetze, Internet

Straßennetze

Nachbarschaftsbeziehungen

endliche Automaten, Transitionssysteme

semantische Beziehungen



Graphen in der Informatik

Wir beschaftigen uns in diesem Seminar mit:

Graphentheorie: Welche Typen von Graphen gibt es? WelcheStrukturen treten in Graphen auf? Welche bekannten Satzeuber Graphen gibt es? (z.B. Vierfarbentheorem)

Graphalgorithmen: Wie kann man Graphen am bestenalgorithmisch verarbeiten? Welche Verfahren gibt es, umGraphen zu untersuchen? (z.B. Chinese Postman Problem,Max Flow)

Graph Drawing: Wie lassen sich Graphen am bestenvisualisieren? Welche Algorithmen gibt es, um Graphen zuzeichnen?

Graphtransformation: Wie kann man Graphen mit Hilfe vonRegeln transformieren? Wie funktionieren Graphgrammatiken?Wie kann man nebenlaufige Systeme mit Hilfe vonGraphtransformationsregeln modellieren?



Seminar

Seminartreffen

Das Seminar beginnt am 22. April 2013 und findet dann jeweilsmontags in Raum LK 052 statt!

Teilnahme an dem Seminar besteht aus drei Teilen:

der schriftliche Ausarbeitung,

dem Vortrag selbst und

der Teilnahme an den Diskussionen nach den Vortagen.



Literatur

(Englischsprachige) Literatur zum Thema wird von denjeweiligen Betreuern zur Verfugung gestellt.

Ansonsten: Eigene Literaturrecherche

BibliothekVerfolgen von ReferenzenInternet

Literaturverzeichnis in der Ausarbeitung nicht vergessen!



Ausarbeitung

Formale Kriterien

ca. 5-10 Seiten

Deutsch oder Englisch

Ausarbeitung 6= Folien

Muss am Vortragstermin ausgeteilt werden

Als Datei (PDF, kein Word) an den jeweiligen Betreuerschicken

Hinweise fur die Ausarbeitung

Zusammenfassung des Themas in eigenen Worten

Weniger wichtige Details weglassen

Am besten erst nach dem Vortrag austeilen

Wir empfehlen LATEX zur Erstellung der Ausarbeitung



Ausarbeitung

Formale Kriterien

ca. 5-10 Seiten

Deutsch oder Englisch

Ausarbeitung 6= Folien

Muss am Vortragstermin ausgeteilt werden

Als Datei (PDF, kein Word) an den jeweiligen Betreuerschicken

Hinweise fur die Ausarbeitung

Zusammenfassung des Themas in eigenen Worten

Weniger wichtige Details weglassen

Am besten erst nach dem Vortrag austeilen

Wir empfehlen LATEX zur Erstellung der Ausarbeitung



Vortrag

Vortrag

Reine Vortragszeit: ca. 45 Minuten

Mit Zwischenfragen: maximal 1 Stunde

Sprache: Deutsch oder Englisch

Voraussetzung: Jeder Vortrag muss mindestens ein interaktivesElement enthalten (Vorfuhrung eines Algorithmus’, . . . , usw.)

Diskussion:

ca. 15 MinutenWir bitten um rege Teilnahme!



Vortrag

Vortrag

Reine Vortragszeit: ca. 45 Minuten

Mit Zwischenfragen: maximal 1 Stunde

Sprache: Deutsch oder Englisch

Voraussetzung: Jeder Vortrag muss mindestens ein interaktivesElement enthalten (Vorfuhrung eines Algorithmus’, . . . , usw.)

Diskussion:

ca. 15 MinutenWir bitten um rege Teilnahme!



Benotung

Die Note setzt sich aus vier Teilen zusammen:

1 Erarbeitung und Verstandnis des Themas

2 Aufbau und Halten des Vortrags

3 Ausarbeitung

4 Anwesenheit bei und aktive Beteiligung an den Vortragen deranderen



Themenliste mit Betreuern

15.04.2013 Kurzeste Wege und Spannbaume in Graphen [13, 17] ?Betreut durch: Sander Bruggink

29.04.2013 Max-Flow/Min-Cut [20] ?Betreut durch: Henning Kerstan

06.05.2013 Small Worlds: Modelle fur soziale Netzwerkeund das Internet [14, 15, 16] ??Betreut durch: Henning Kerstan

13.05.2013 Das Problem des chinesischen Postboten [11] ?Betreut durch: Barbara Konig

20.05.2013 Planare Graphen und Graphminoren [1, 18] ??Betreut durch: Jan Stuckrath

27.05.2013 Der Vier-Farben-Satz [19] ??Betreut durch: Sebastian Kupper

03.06.2013 Algorithmen zum Zeichnen von Graphen [5] ?Betreut durch: Sander Bruggink



Themenliste mit Betreuern

10.06.2013 Binary Decision Diagrams [7, 8] ??Betreut durch: Christoph Blume

17.06.2013 Pfad- und Baumweite: Beschreibung,Berechnung und Anwendung [3, 4] ??Betreut durch: Christoph Blume

24.06.2013 Routing basierend auf Baumzerlegungen undSmall Worlds [12] ? ? ?Betreut durch: Barbara Konig

01.07.2013 Graphtransformation durch Kantenersetzung [10] ? ? ?Betreut durch: Sebastian Kupper

08.07.2013 Algebraischer Ansatz zur Graphersetzung [9] ? ? ?Betreut durch: Jan Stuckrath

15.07.2013 Erkennbare Graphsprachen [6, 2] ? ? ?Betreut durch: Christoph Blume



Zeitplan

Termine

−4 Wochen erstes Treffen mit dem Betreuer und Beschaffungder Literatur

−3 Wochen Vorlage eines groben Konzepts bzw. Gliederung−2 Wochen Vorlage eines Entwurfs der Ausarbeitung−1 Wochen Vorlage eines Entwurfs der Vortragsfolien

Man darf sich naturlich auch außerhalb der Fristen bei denBetreuern melden!



Kontakt

Kontaktdaten

Barbara Konig (barbara [email protected])

Sander Bruggink ([email protected])

Christoph Blume ([email protected])

Jan Stuckrath ([email protected])

Henning Kerstan ([email protected])

Sebastian Kupper ([email protected])

Weitere Kontaktinformationen finden sich auf unserer Webseite

Web-Seite des Seminars:http://www.ti.inf.uni-due.de/teaching/ss2013/seminar/



Warum halte ich einen Vortrag?




Antwort 1: Um die Zuhorer zu beeindrucken!

Taktik:

Viele Fremdworter

Schnelles Tempo

Wenig hilfreiche Erklarungen

Wenige Beispiele

Voraussetzen von erheblichen Vorkenntnissen




Antwort 2: Um den Zuhorern eine Idee zu vermitteln

Vortragende(r) Zuhorer(in)



Zielsetzung

Daher:

Stoff so aufbereiten (und evtl. einschranken), dass er gutvermittelbar ist

Vortrag gut strukturieren

Zentrale Ideen hervorheben

Das Publikum nicht uberschatzen

Redundanz

Geeignete graphische Darstellungen finden

Gute Beispiele suchen



Umgang mit dem Publikum

Zuhorer ansehen, Blickkontakt aufnehmen

Aktivierung der Zuhorer durch Fragen, kleine Aufgaben, etc.

Und ein Appell ans Publikum:

Stellen Sie Fragen, wenn Sie etwas nicht verstanden haben undwenn Sie etwas interessiert!



Medien

Zur Verfugung stehen:

Beamer (Overhead-Projektor) Tafel

Folien:

mit großer Schrift, Bildern, Farbe, etc.

nicht zu viel auf eine Folie quetschen

nicht zu viele Folien vorbereiten

Uberblicksfolien (Inhaltsverzeichnis, etc.) erstellen

Richtwert: ca. 25 Folien fur 45 Minuten

Randbemerkung: Diese Folien wurden mit latex-beamer erstellt.



Medien

Medienwechsel:

auch die Tafel nutzen, beispielsweise um schwierige Sachverhaltezu erklaren

Vorsicht:

Aufmerksamkeit der Zuhorer richtet sich gerne auf dieProjektionsflache, vorbei am Sprecher.

Daher . . .



Uben des Vortrags

Vortrag vorher uben, evtl. vor Probepublikum

Zeit messen (Dauer: ca. 45 Minuten)

Vortrag nicht auswendiglernen!

Schlussworte ausdenken

Kurze Zusammenfassung des VortragsAbschließende Bewertung

”Danke. Gibt es Fragen?“

Nur keine Panik! Ein bisschen Lampenfieber gehort aber dazu.



”Allein der Vortrag macht des Redners Gluck.“

Johann Wolfgang von Goethe, aus Faust



Dan Bienstock and Michael A. Langston.Algorithmic Implications of the Graph Minor Theorem.University of Tennessee, Computer Science Department, 1994.

Christoph Blume, H.J. Sander Bruggink, Dominik Engelke,and Barbara Konig.Efficient symbolic implementation of graph automata withapplications to invariant checking.In Proceedings of ICGT 2012, 2012.

Hans L. Bodlaender and Arie M. C. A. Koster.Combinatorial optimization on graphs of bounded treewidth.The Computer Journal, 51(3):255–269, 2008.

Hans L. Bodlaender and Arie M. C. A. Koster.Treewidth computations I. Upper bounds.Information and Computation, 208(3):259–275, 2010.



Ulrik Brandes.Drawing on physical analogies.Drawing Graphs, pages 71–86, 2001.

H. J. Sander Bruggink and Barbara Konig.On the recognizability of arrow and graph languages.In Proceedings of ICGT ’08. Springer, 2008.

Randal E. Bryant.Graph-based algorithms for boolean function manipulation.IEEE Transactions on Computers, 100(8):677–691, 1986.

Randal E. Bryant.Symbolic boolean manipulation with ordered binary-decisiondiagrams.ACM Computing Surveys (CSUR), 24(3):293–318, 1992.



Andrea Corradini, Ugo Montanari, Francesca Rossi, HartmutEhrig, Reiko Heckel, and Michael Lowe.Algebraic approaches to graph transformation, part I: Basicconcepts and double pushout approach.Handbook of graph grammars and computing by graphtransformation, 1:163–245, 1997.

Frank Drewes, Annegret Habel, and Hans-Jorg Kreowski.Hyperedge replacement graph grammars.Handbook of Graph Grammars and Computing by GraphTransformation, 1:95–162, 1997.

Horst A. Eiselt, Michel Gendreau, and Gilbert Laporte.Arc routing problems, Part I: The chinese postman problem.Operations Research, 43(2):231–242, 1995.



Pierre Fraigniaud.A new perspective on the small-world phenomenon: Greedyrouting in tree-decomposed graphs.In Proceedings of the 13th Annual European Symposium onAlgorithms (ESA), pages 791–802, 2005.

Peter E. Hart, Nils J. Nilsson, and Bertram Raphael.A formal basis for the heuristic determination of minimum costpaths.Systems Science and Cybernetics, IEEE Transactions on,4(2):100–107, 1968.

Jon M. Kleinberg.Navigation in a small world.Nature, 406(6798):845–845, 2000.



Jon M. Kleinberg.The small-world phenomenon and decentralized search.SIAM News, 37(3):1–2, 2004.

Jon M. Kleinberg.Complex networks and decentralized search algorithms.In Proceedings of the International Congress ofMathematicians, pages 1019–1044, 2006.

Joseph B. Kruskal.On the shortest spanning subtree of a graph and the travelingsalesman problem.Proceedings of the American Mathematical Society,7(1):48–50, 1956.



Laszlo Lovasz.Graph minor theory.Bulletin of the American Mathematical Society, 43(1):75–86,2006.

Neil Robertson, Daniel P. Sanders, Paul Seymour, and RobinThomas.A new proof of the four-colour theorem.Electronic Research Announcements of the AmericanMathematical Society, 2(1):17–25, 1996.

Vince Vatter.Graphs, flows, and the ford-fulkerson algorithm, 2004.


Documents

Seminar ``Graphen in der Informatik: Algorithmen und … · 2013-04-04 · Algebraic approaches to graph transformation, part I: Basic concepts and double pushout approach. Handbook