Table of Contents

Proseminar Algorithms Unplugged (WiSe 2016/17)

Veranstalterin Prof. Dr. Petra Mutzel
Modul Bachelor, INF-BSc-110 (Informatik, Angewandte Informatik)
Veranstaltungsart Proseminar
Veranstaltungsnummer 040607
Forschungsbereich Algorithmen und Komplexität
SWS 3
Max. Teilnehmer 20

Inhalt und Themen

In dem Proseminar halten wir uns an die Kapitel des Buches “Algorithms Unplugged” (s.u.). Dieses Buch entstand ursprünglich aus dem Jahr der Informatik. Damals war die Idee, jede Woche einen neuen Algorithmus so darzustellen, dass er auch für die Öffentlichkeit (z.B. Schülerinnen und Schüler, ohne Vorkenntnisse) verständlich ist.

Jedes Kapitel widmet sich einem Thema, insgesamt umfasst das Buch sehr viele Themen der Informatik in großer Breite. Da sind sicherlich für alle Teilnehmer interessante Kapitel dabei. Alle Teilnehmer/innen sollen über je ein Kapitel vortragen. Zur Auswahl suchen Sie sich bitte jeweils genau 5 mögliche Kapitel (mit Prioritäten) aus (s. unten). Die Einteilung findet am Termin der Vorbesprechung statt. Natürlich scheiden Kapitel, die bereits in DAP2 behandelt wurden (wie z.B. Insertion Sort oder Binärsuche) aus.

Die einzelnen Kapitel (zumindest die Titel) des Buches finden Sie hier.

Ablauf des Seminars

Diese Veranstaltung ist ein Proseminar für Studierende im Grundstudium. Sie umfasst 3SWS. Dies beinhaltet einen Präsentationskurs (1SWS), der extern (zentral veranstaltet) angeboten wird. Hierzu müssen Sie sich über das LSF anmelden. Dieser Kurs ist für BachelorstudentInnen verpfichtend.

Die Themenverteilung erfolgt während der Vorbesprechung zu Beginn des Wintersemesters. Im weiteren Verlauf des Semesters haben die Teilnehmer Zeit die Ausarbeitung zu schreiben und den Vortrag vorzubereiten.

Voraussetzung für den Hauptvortrag ist die vorherige Abgabe einer schriftlichen Ausarbeitung zu dem fest vorgegebenen Termin (s. unten), welche 6-10 Seiten umfasst und mit LaTeX erstellt wird. Mangelhafte Ausarbeitungen sowie 1:1 Übersetzungen bzw. Kopieren führen zum Nicht-Bestehen des Seminars.

Es wird dringend empfohlen, sich rechtzeitig vor der Abgabe der schriftlichen Ausarbeitung dem/r BetreuerIn ein kurzes Konzeptpapier vorzulegen, in dem der Inhalt und Aufbau des Vortrags stichpunktartig erläutert wird. Denn eine Aufgabe der Teilnehmer/innen besteht auch darin, den zu präsentierenden Stoff aus der Literaturquelle sorgsam auszuwählen. Es geht nicht darum, den ganzen Inhalt zu präsentieren, sondern die interessanten Aspekte. Hierbei ist eine Rückmeldung von der/m Betreuer/in oft hilfreich. Der Inhalt der Ausarbeitung stimmt i.A. mit dem Inhalt der Präsentation überein.

Jede Ausarbeitung wird dann von zwei Teilnehmer/innen korrigiert. Die zu beachtenden Kriterien werden rechtzeitig bekannt gegeben. Die Teilnehmer/innen senden die korrigierten Versionen zu einem festgelegten Zeitpunkt an die Betreuer/in. Die Betreuer/innen besprechen diese Versionen dann mit den Teilnehmern. Daraufhin haben die Teilnehmer/innen die Gelegenheit, ihre Ausarbeitung noch einmal zu überarbeiteten und endgültig abzugeben.

Zur Mitte des Semesters halten alle Teilnehmer/innen einen 5-minütigen Vortrag zur Vorstellung ihres Themas sowie dem geplanten Inhalt. Dieser dient dazu, immer wieder gemachte Fehler bei den Abschlussvorträgen zu vermeiden.

Um die vorbereiteten Abschlussvorträge zu perfektionieren, treffen sich die Teilnehmer/innen in kleineren Gruppen um sich gegenseitig zu unterstützen. Dies passiert zu einem festgelegten Termin. Die Betreuer schauen hierbei nur kurz vorbei um Unklarheiten zu klären. Auch diese Teilnahme ist Pflicht.

Alle Teilnehmer halten nach Ende des Semesters einen 30-minütigen Abschlussvortrag über das festgelegte Thema; im Anschluss folgt eine ca. 15-minütige Diskussion über Thema und Vortrag. Bitte beachten Sie auch die Hinweise zur Foliengestaltung!

Termine

Die Vorbesprechung findet am Mittwoch, dem 19. Oktober 2016 um 12:00 Uhr in OH14 R.202 statt.

Die schriftliche Abgabe der Ausarbeitungen muss bis zum 5. Dezember 2016 um 23:59 Uhr (pdf per email oder gedruckt im Sekretariat) an Petra Mutzel erfolgen. Verspätete Abgaben werden nicht akzeptiert. Eine nicht rechtzeitige Abgabe führt zum Nicht-Bestehen des Proseminars. Dasselbe gilt für Ausarbeitungen, die ganz oder teilweise von anderen Arbeiten plagiiert sind (dies inkludiert auch Übersetzungen englischsprachiger Texte).

Diese schriftliche Abgabe wird ab 6. Dezember an jeweils zwei Teilnehmer/innen zur Korrektur gesendet. Diese haben dann 2 Wochen Zeit dazu. Wir treffen uns wieder alle am Mittwoch, dem 21. Dezember 2016 von 14-16 Uhr in OH14 R.202 zur (dezentralen) Korrekturbesprechung. Das heisst, die Dreiergruppen besprechen hier ihre gegenseitigen Korrekturen. Die Betreuer sind bei Fragen vor Ort.

Danach bleibt Zeit bis zum 6. Januar 2017 um die endgültigen schriftlichen Versionen abzugeben. Diese sind an Petra Mutzel mit cc an Ihren Betreuer per Email einzureichen.

Die 5-minütigen Vorträge erfolgen am Mittwoch, dem 18. Januar 2017 von 13:00 Uhr bis 16:00 Uhr in OH14 R.202. In diesem Vortrag sollen Sie das behandelte Problem vorstellen und einen Überblick über Ihren Vortrag geben. Die dabei genutzten Folien müssen danach für den Endvortrag nur noch erweitert werden.

Die Treffen in den Kleingruppen erfolgen am Mittwoch, dem 1. Februar 2017 von 14:00 Uhr bis 16:00 Uhr in OH14 R.202.

Die Folien für die jeweiligen Vorträge sind bis zum 6. Februar 2017 per Email bei Petra Mutzel mit cc an Ihren Betreuer einzureichen.

Die Vorträge finden am 13. und 14. Februar 2017 in OH14 R. 202 statt. Die Zeiten sind: Mo 13.02. um 13:30 - 16:45 Uhr (4 Vorträge) und Di 14.02. um 10:00-12:30 (3 Vorträge) und 13:30 - 16:00 Uhr (3 Vorträge). Die Reihenfolge ist entsprechend der Kapitelnummern (s. unten).

Kapitel Thema Teilnehmer Betreuer/in
16 Public-Key Cryptography Robin Rieger Bernd Zey
17 Secret Sharing Mohammad Tehrani Till Schäfer
19 Fingerprinting Marc Strotkamp Denis Kurz
23 Converting Numbers to Words Tim Prothmann Petra Mutzel
24 Majority Voting Steffen Enders Petra Mutzel
25 Random Numbers Johannes May Christopher Morris
26 Winning Strategies Mariam Tayyem Nils Kriege
27 Tournament Scheduling Jens Köcke Andre Droschinsky
28D Alpha-Beta für Spielbäume Max Brämer Adalat Jabrayilov
37 Online Algorithms Marvin Wehrmaker Fritz Bökler

Kriterien der schriftlichen Ausarbeitung:

Kriterien des Vortrags:

Anmeldung

Die Anmeldung erfolgt über das zentrale Verfahren und ist bereits abgelaufen.

Literatur

  1. Vöcking, B., Alt, H., Dietzfelbinger, M., Reischuk, R., Scheideler, C., Vollmer, H., Wagner, D. (Eds.): Algorithms Unplugged, Springer 2011

Ansprechpartner

Bei Fragen zu dieser Veranstaltung wenden Sie sich bitte an Petra Mutzel.