Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
 

Graphentheorie

BSc Seminar - Winter 2017/18

Beschreibung

Das Wort diskret beschreibt in der Mathematik Mengen, die endlich oder höchstens abzählbar viele Elemente besitzen. Folglich sind diskrete Strukturen überall um uns herum. Interessanterweise gab es noch vor 60 Jahren kein Konzept der diskreten Mathematik. Das Aufflammen des Interesses an der Studie diskreter Strukturen im letzten halben Jahrhundert ist mit dem Aufstieg des Computers leicht zu erklären. Nicht mehr das Universum, die Natur oder der eigene Geist war die Grenze, sondern harte Zahlen. So wächst mit jedem Jahr das Forschungskalkül der diskreten Mathematik gerade als Grundlage für größere Teile der theoretischen Informatik beständig.

Dieses Seminar dient als Einführung und Vertiefung der Studie diskreter Strukturen mit der Graphentheorie als Schwerpunkt. Es baut auf der Vorlesung Mathematik 1 auf. Exemplarische Themen sind Eulertouren, aufspannende Bäume und Graphenfärbungen. Hierfür erhalten die Teilnehmer Unterstützung beim Erstellen und der Durchführung eines ersten mathematischen Vortrags.

Teilnehmer

Das Seminar ist ausgelegt für Studenten im Bachelorstudiengang. Auf Grund des Aufbaus (s.u.) ist die Anzahl an Teilnehmern auf maximal 12 beschränkt.

Voraussetzungen

Es gibt keine formellen Voraussetzungen. Der behandelte Stoff aus Mathematik 1 und 2 wird erwartet.

Teilnehmer sollten eine Freude an abstraktem Denken und Knobeln mitbringen. Zusätzlich sind Teile der Literatur in englisch geschrieben und müssen verstanden werden.

Literatur

Die Literatur bestehend aus Ausschnitten verschiedener Lehrbücher wird im Algorithm Engineering Moodle bekannt gegeben. Die Anmeldeinformationen sind identisch zu denen vom HPI. Aktuelle Forschungsartikel sind als Literatur nicht vorgesehen.

Aufbau

Am ersten Termin findet ein informatives Treffen statt. Hier werden die Vortragsthemen vorgestellt, die Modalitäten des Seminars erläutert und aufkommende Fragen geklärt. Wünschenswert ist ebenso die Vergabe der Themen zu diesem Termin.

Jeder Teilnehmer wählt ein eigenes Thema und erarbeitet einen 45-minütigen Vortrag, auf den eine maximal 30-minütige Übung geleitet vom Vortragenden folgt. Zusätzlich wird zu diesem Termin ein erweitertes Handout (Ausarbeitung) erwartet. Dieses soll alle Hauptinhalte des Vortrages sowie stichpunktartig Erklärungen wiedergeben. Ebenso sollen die entsprechenden stellen mit Referenzen aus der Literatur versehen werden.

Für die Übung werden dem Vortragenden einige Übungsaufgaben zur Verfügung gestellt, die dieser für sich selber lösen soll. Nach dem Vortrag sollen die Aufgaben dem Auditorium vorgestellt und die Überlegungen des Auditorium vom Vortragenden geleitet werden, um gemeinsam zu einer Lösung zu gelangen.

Zwei Wochen vor dem jeweiligen Vortragstermin wird ein persönliches Treffen mit dem Betreuer veranschlagt, das zur Vorstellung der Vortragsgliederung und der Klärung von Fragen dienen soll. In einem weiteren Treffen eine Woche vor dem jeweiligen Vortragstermin sollen der Vortrag und das Handout dem Betreuer vorgestellt werden.

Leistungserfassung

Grundlage der Benotung ist der Vortrag und die geleitete Übung. Ein herausragend gutes/schlechtes Handout (Ausarbeitung) kann die Note beeinflussen.

Termine

  • Zeit: Dienstag, 11:00 Uhr
  • Ort: Raum A-1.2

Weitere Informationen werden im Algorithm Engineering Moodle bekannt gegeben.