Seminare

Inhalt

Entwurf und Analyse von Algorithmen ist ein Kerngebiet der Informatik. In den ersten Semestern wurden bereits eine Reihe von Algorithmen, z.B. Graphalgorithmen und Sortieralgorithmen, und Paradigmen für Algorithmenentwurf vorgestellt und analysiert.

In diesem Seminar werden darauf aufbauend Algorithmen behandelt, die typischer Weise nicht in den Curricula behandelt werden, aber interessante Ideen aufweisen und von Interesse für die Anwendung sind. Wir behandeln Themen wie Mustererkennung in Texten, Boyer-Moore- und Knuth-Morris-Pratt-Algorithmen, Präfix-Bäume, Goldberg/Tarjans Netzwerkflussalgorithmus mit Anwendungen, Stable Marriage Problem, Weighted Popular Matchings, Student/Projekt-Zuweisungsproblem, Boston School Choice Problem, Top Trading Cycle Verfahren, Nierenvergabe für Transplantation mit TTCC, Cake Cutting and Lone Chooser Protokoll, Divide and conquer cake cutting Protokoll.

Ablauf

1. Zu Beginn des Semesters gibt es eine Einführungsveranstaltung, bei der die Themen verteilt werden.

2. Nach der Zuteilung der Themen haben Sie Zeit sich Ihr Thema näher anzusehen und eine Literaturrecherche zum Beispiel zu historischen Hintergründen und insbesondere zu Anwendungen Ihrer Algorithmen in der Praxis oder Erweiterungen/Varianten der Problemstellung durchzuführen.

3. Beim zweiten Seminartermin hält jeder Studierende einen kurzen Vortrag, ca. 5-10 Minuten, in dem das Thema und eine provisorische Gliederung des geplanten Vortrags vorgestellt wird.

4. Sie haben danach einige Wochen Zeit die Folien Ihres Vortrags zu erstellen, der ca. 50 Minuten inklusive Diskussion dauern soll. Diese senden Sie mir 1 Woche vor Ihrem Vortrag zur Korrektur per Email zu.

5. Die Vorträge finden statt.

6. Es soll eine Ausarbeitung von 10 (±10%) Seiten (Deckblatt und Inhaltsverzeichnis zählen nicht) an mich gesandt werden. Im Gegensatz zu den Folien, die eher stichpunktartig organisiert sind, ist die Ausarbeitung eine ausführliche Behandlung Ihres Themas.

7. Am Ende des Semesters findet ein Reviewing durch die Teilnehmenden statt.

Sprache

Vortrag und Ausarbeitung können auf deutsch oder englisch sein. Vortrag und Ausarbeitung sollen in der gleichen Sprache erfolgen und selbstständig formuliert werden.

Bewertungskriterien

Hier werden Hinweise zur Bearbeitung der Themen gegeben. Die Nichteinhaltung wird in der Note berücksichtigt.

1. Alle vorkommenden Begriffe sollen gut erklärt werden, z.B. an einem eigenen Beispiel / Gegenbeispiel. Ebenso sollen die Algorithmen/Protokolle sowie komplexere Definitionen illustriert werden und an einem eigenen Beispiel erläutert werden. Die Aussagen zu den Algorithmen/Protokollen sollen präsentiert und erläutert werden. Beweise erfolgen in der Regel in der Ausarbeitung.

2. Sie sollen Kosten von Algorithmen angeben und begründen.

3. Beweise dürfen nicht einfach nur abgeschrieben oder übersetzt werden.

4. Quellen müssen klar und umfassend genannt werden.

5. Copy und Paste aus Texten oder Darstellungen im Internet oder deren wortwörtliche Übersetzung sind nicht zulässig (Ausnahme: Zitate). Insbesondere Erläuterungen und Beweise müssen mit eigenen Worten formuliert werden.
   Beachten Sie auch die Hinweise zum Umgang mit Plagiaten und Täuschungsversuchen.

6. Es ist Vorsicht geboten, Veranschaulichungen aus dem Internet zu übernehmen. Diese sind nicht notwendig konform mit der von uns gewählten Literatur und auch nicht immer an Informatiker gerichtet und manchmal ziemlich salopp, insbesondere ohne Begründung der Korrektheit dessen, was da getan wird. In unseren Seminaren geht es aber um wissenschaftliches Arbeiten, z.B. auch um das Verstehen komplexerer formaler Konstrukte und Zusammenhänge. Veranschaulichen ist gut, ersetzt aber nicht das exakte Formale. Eine bloße Veranschaulichung, wie sie häufig im Internet zu finden ist, entspricht nicht dem, was in einem Seminarvortrag erwartet wird.

7. Sie müssen eine Literaturrecherche durchführen und die Literatur korrekt zitieren.

8. Auch bei der Verwendung zusätzlicher Literatur muss man darauf achten, das die verwendeten Begriffe übereinstimmen, selbst kleine Veränderungen in einer Definition/einem Algorithmus können weitreichende Konsequenzen haben.

Vortrag

Der Vortrag soll ca. 50 Minuten inklusive Diskussion dauern.

• Inhalt: Motivation und Einführung, Gliederung, Argumentationskette, Abstraktionsniveau, Vollständigkeit
• Form: Form der Folien (Schriftgröße, Diagramme, Folien nicht überladen), freie Rede, sprachliche Verständlichkeit (deutliche Sprechweise, Wortwahl), Einhalten der Zeit
• Bereiten Sie eine kleine Aufgabe für oder Frage an die Kommiliton:innen vor. Die Mitarbeit der jeweils Zuhörenden wird erwartet.

Ausarbeitung

• Darstellung: Klarheit des Textes, sprachliche Gewandtheit, äußere Form, Rechtschreibung, Quellenangaben, sinnvolle Darstellung von Abbildungen
• Deckblatt: Titel des Vortrags, Name des Vortragenden, Titel des Seminars, Datum, Angabe des Instituts und des Betreuers
  
• Hinführung: Abstract, Einleitung und Motivation
• Hauptteil: Argumentationskette, Darstellung der Hauptresultate
• Abschluss: Schlussbewertung und Zusammenfassung, Ausblick

This seminar discusses techniques for regression testing, which aim to run (a subset of) the previously developed tests on the modified software to detect deviations from previous behavior efficiently. We in particular look into techniques that apply test suite reduction (i.e., removal of redundant tests), test selection (i.e., selection of a relevant subset of the tests), and test prioritization (i.e., ordering the tests with the goal that deviations are likely detected early).

Under the guidance of your supervisor you will