Bachelor-Seminar Algorithmik

• Google Scholar
• ACM Digital Library
• Citeseer (Research Index) Citation Index
• DBLP
• Universitätsbibliothek der TU-Braunschweig

• Tipps+Tricks zu (La)TeX
• Templates

• 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

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 30 Minuten (reine Vortragszeit) dauern. Anschließend wird es eine kurze Diskussionsrunde mit Fragen geben. 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.

Themen für Bachelorstudenten

Üblicherweise werden einige Themen aus dem Buch der Beweise vorgeschlagen. Falls spezielle Themen aus eigenem Interesse gewünscht sind, ist dies sicherlich möglich.

Die Themen dieses Semesters sind:

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.

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.

Searching for Empty Convex Polygons

Ein Problem in der algorithmischen Geometrie ist die Identifikation von Teilmengen einer Punktmenge, die bestimmte Eigenschaften erfüllen. Die gewünschten Eigenschaften in diesem Thema sind Leere und Konvexität. Es existieren Beziehungen zwischen diesen Eigenschaften. Diese und ein Algorithmus für das Finden von leere, konvexen Polygonen ist der grobe Inhalt dieses Themas.

Maximum Degree of Bipartite Embeddings of Trees in the Plane

Ein bipartiter Graph ist ein Graph bei dem die Knotenmenge in zwei disjunkte Teilmengen aufgeteilt werden kann, so dass Kanten nur zwischen Knoten aus verschiedenen Mengen existieren. Das Problem dieses Themas betrachtet einen vollständig bipartiten Graphen mit gleichgroßen Bipartitionen, bei dem außerdem, wird er in der Ebene dargestellt, keine drei Punkte kollinear sind. Für solche Graphen kann gezeigt werden, dass sie einen planaren, aufspannenden, bipartiten Baum T beinhalten, so dass der Maximalgrad von T maximal drei ist.