| Carl Friedrich Gauß Faculty | Department of Computer Science

Institute of Operating Systems
and Computer Networks

Informatikzentrum

Bachelor-Seminar Algorithmik

Semester	Summer 2016 Summer 2021 Winter 2020/2021 Summer 2020 Winter 2019/2020 Summer 2019 Winter 2018/2019 Summer 2018 Winter 2017/2018 Summer 2017 Winter 2016/2017 Winter 2015/2016 Summer 2015 Winter 2013/2014 Summer 2013 Winter 2012/2013 Summer 2012 Winter 2011/2012 Summer 2011 Winter 2010/2011 Winter 2009/2010 Summer 2009 Winter 2008/2009
Module #	INF-STD-18, INF-STD-20
Event #	INF-ALG-019, INF-ALG-029
Programmes	Bachelor Informations-Systemtechnik, Bachelor Elektrotechnik, Bachelor Informatik
IBR Group	ALG (Prof. Fekete)
Type	Seminar
Lecturer	Prof. Dr. Sándor P. Fekete Abteilungsleiter s.fekete[[at]]tu-bs.de +49 531 3913111 Room 335
Assistants	Dr. Victor Alvarez Ehemaliger Wissenschaftlicher Mitarbeiter Dr. Phillip Keldenich Wissenschaftlicher Mitarbeiter keldenich[[at]]ibr.cs.tu-bs.de +49 531 3913112 Room 318 Dr. Frank Quedenfeld Ehemaliger Wissenschaftlicher Mitarbeiter PD Dr. Christian Scheffer Ehemaliger Wissenschaftlicher Mitarbeiter scheffer[[at]]ibr.cs.tu-bs.de
Credits	5
Hours	0+2
Prerequisites	Voraussetzungen für die Bearbeitung der einzelnen Themen sind jeweils individuell aufgeführt. Sind diese in Klammern gesetzt, sind sie zwar hilfreich, aber keine Voraussetzung.
Certificates	Schriftliche Ausarbeitung und erfolgreicher Seminarvortrag. Die Note wird abhängig von der aktiven Teilnahme am Seminar sowie der Qualität des Vortrages und der Ausarbeitung bestimmt.
Registration	Anmeldung zentral (über StudIP). Die Vorbesprechung für das Seminar erfolgt in der ersten Semesterwoche im Besprechungsraum der Abteilung Algorithmik (IZ313), der genaue Termin wird noch bekannt gegeben.
Content	Das Seminar Algorithmik beschäftigt sich dieses Semester mit einer Reihe von Buchkapiteln aus dem "Buch der Beweise" (Bachelor), sowie einer Reihe von aktuellen Artikeln sowie Ausschnitten aus Büchern (Master).
References	Literaturrecherche: Google Scholar ACM Digital Library Citeseer (Research Index) Citation Index DBLP Universitätsbibliothek der TU-Braunschweig Ausarbeitung und Vortrag: Tipps+Tricks zu (La)TeX slidetemplates Literatur: Martin Aigner and Günter M. Ziegler: Proofs from THE BOOK, Springer-Verlag Berlin Heidelberg, 2010 (az-pftb-10, BibTeX) Martin Aigner and Günter M. Ziegler: Das BUCH der Beweise, Springer, 2010 (az-dbdb-10, BibTeX)
Hinweise Teilnehmerzahl Es werden je 5 Plätze für Studierende auf Bachelor- und auf Masterniveau angeboten. Ausarbeitung Die Ausarbeitung soll etwa 6-8 Seiten lang sein. Generell interessiert uns, dass Sie da eine selbstverfasste Zusammenfassung eines selbst verstandenen Artikels abgeben. Wesentlich mehr als die genannte Seitenzahl sollte es nicht werden, immerhin geht es hier um die Kunst des Zusammenfassens. Wir erwarten, dass Sie selbstständig zusätzliche Quellen recherchieren. Vortrag Ihr Vortrag soll etwa 35-40 Minuten (reine Vortragszeit) dauern. Das Medium ist frei, Sie können also Whiteboard, Overhead-Projektor, Beamer mit PowerPoint, Beamer mit PDF, oder was auch immer Sie für sinnvoll erachten, einsetzen. Natürlich sollten Sie bei exotischen Wünschen diese erstmal mit dem Betreuer klären, und unbedingt auch Programm-, Programmversions- und sonstige Kompatibilitätsfragen besprechen. Beispiele für Themen für Bachelorstudenten Thema 1: Drei Anwendungen der Eulerschen Polyederformel Die Eulersche Polyederformel setzt für zusammenhängende ebene Graphen die Anzahl von Ecken, Kanten und Gebieten in Beziehung. Dieser Satz wird vorgestellt und auf drei Probleme angewendet. Thema 2: Das Dinitz-Problem Das folgende Problem wird betrachtet: Angenommen, wir haben für jedes der n² Felder eines (nxn)-Quadrats eine Menge von n Farben zur Verfügung. Ist es dann immer möglich, so jedem Feld eine seiner n Farben zuzuweisen, dass keine zwei Felder in derselben Zeile oder Spalte dieselbe Farbe erhalten? Thema 3: Der Fünffarbensatz Ein berühmter Satz über planare Graphen besagt, dass sich jeder planare Graph mit nur 4 Farben so färben lässt, dass benachbarte Knoten unterschiedliche Farben haben. Der Beweis dieses Satzes kann derzeit nur per Computer geführt werden. Wesentlich einfacher ist es zu zeigen, dass höchstens 5 Farben immer ausreichen. Dies soll hier vorgestellt werden.

last changed 2016-05-18, 17:32 by Dr. Phillip Keldenich