| Titel | Proseminar - Perlen der Informatik |
| Semester | Sommersemester 2016 |
| Module | IN0013 |
| Voraussetzungen | Vorlesung "Perlen der Informatik" (IN2148) |
| SWS | 2 |
| ECTS | 4 |
| Organisation | Ondřej Kunčar, Tobias Nipkow |
Jeder Teilnehmer erhält ein Thema, zu welchem er oder sie eine schriftliche Ausarbeitung anfertigt und einen Vortrag vor den anderen Teilnehmern hält. Außerdem gibt jeder Teilnehmer kurze schriftliche Rezensionen zu den Ausarbeitungen zweier anderer Teilnehmer ab. Der genaue zeitliche Ablauf kann dem Abschnitt 'Termine' entnommen werden.
Die Rezensionen, der Vortrag und die Ausarbeitung können sowohl auf Deutsch als auch auf Englisch angefertigt bzw. abgehalten werden.
Sämtliche Abgaben sind bei Ondřej Kunčar einzureichen.
Die Platzvergabe erfolgt durch das Matchingsystem. Es wird keine Vorbesprechung geben.
Die Themenvergabe erfolgt auf Basis von durch die Teilnehmer angegebenen Präferenzen.
| Teilnehmer | Titel |
|---|---|
| Erik Kynast | 1. Fast Multiplication Algorithms and the Master Theorem |
| Thomas Tangl | 3. Closest Pair of Points Problem |
| Sabine Rieder | 5. Dynamische Programmierung: Edit Distance |
Datum: 12.05.2016 (Themen 1, 3)
Datum: 19.05.2016 (Themen 5)
Datum: 02.06.2016 (Themen 1, 3)
Datum: 09.06.2016 (Themen 5)
Datum: 16.06.2016 (Themen 1, 3)
Datum: 30.06.2016 (Themen 5)
Uhrzeit: 14:00 - 16:00
Ort: MI 00.09.038 (Turing)
Description: This talk should explain and analyse two Divide & Conquer algorithms: The Karatsuba algorithm integers multiplication and the Schönhage–Strassen algorithm for matrix multiplication. The complexity analysis is an application of the Master theorem, which should also be presented (but not proven).
References: [1] Knuth, Donald E. The Art of Computer Programming, Volume 2, p. 294 ff. (How Fast Can We Multiply?)
[2] Knuth, Donald E. The Art of Computer Programming, Volume 2, p. 499 ff. (Special Multivariate Polynomials/Matrix multiplication)
[3] Nguyen, Phuong. Strassen's algorithm for matrix multiplication (lecture notes).
[4] Cormen et al. Introduction to Algorithms, Second Edition, p. 73 ff. (The Master method)
Advisor: Manuel Eberl
Description: The Deterministic Selection algorithm finds the k-th smallest number in a list in worst-case linear time. Its recursion structure is somewhat unusual and its analysis is a classic use case of the Akra–Bazzi theorem, a powerful generalisation of the Master theorem. For this topic, the deterministic selection algorithm should be explained in detail and the Akra–Bazzi theorem presented and applied to it (but not proven).
References: [1] Cormen et al. Introduction to Algorithms, Second Edition, p. 189 ff. (Selection in worst-case linear time)
[2] Leighton, Tom. Notes on Better Master Theorems for Divide-and-Conquer Recurrences.
Advisor: Manuel Eberl
Description: The closest pair of points problem is as follows: Given n points in two-dimensional euclidean space, find the pair of points with the smallest distance between them. A naïve algorithm solves this problem in O(n²) time by comparing the distances of all pairs of points. However, there is a better algorithm that solves the problem in O(n log n) time. It is also possible to generalize this algorithm to an arbitrary number of dimensions as well as to metrics other than the Euclidean metric.
References: [1] Jon Kleinberg and Éva Tardos. "Algorithm Design".
[2] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. "Introduction to Algorithms".
[3] http://www.cs.ucsb.edu/~suri/cs235/ClosestPair.pdf
[4] https://en.wikipedia.org/wiki/Closest_pair_of_points_problem
Advisor: Julian Brunner
Description: Für NP-schwere Probleme muss man oftmals auf die Berechnung einer exakten Lösung verzichten, sondern nähert stattdessen die Lösung mit Hilfe sogenannter Approximationsalgorithmen an. Dieser Vortrag soll anhand zweier Beispiele, einem Load-Balancing Problem und einem geometrischen Problem, das beispielsweise in der Stadtplanung auftreten könnte, eine Einführung in das Thema geben. Wir werden dabei sehen, dass scheinbar simple Beobachtungen manchmal bereits einen effizienten Algorithmus mit vertretbarem Fehler liefern können.
References: [1] Abschnitte 11.0, 11.1 und 11.2 aus Algorithm Design
[2] https://en.wikipedia.org/wiki/Approximation_algorithm
Advisor: Simon Wimmer
Description:
Eine der mächtigsten Techniken zum Design von effizienten Algorithmen ist das Prinzip der sogenannten dynamischen Programmierung. Kern des Ansatzes ist es ähnlich wie bei Divide-and-Conquer-Algorithmen durch das geschickte Zusammensetzen von Lösungen kleinerer Teilprobleme eine Lösung für das Gesamtproblem zu erhalten. Wir wollen die Technik an einem ihrer wohl bekanntesten Beispiele, der Berechnung der Edit-Distance zweier Strings, einführen. Die Berechnung der Edit-Distance hat beispielsweise Anwendungen in der automatischen Korrektur von Texteingaben, aber auch für den Vergleich von RNA-Sequenzen in der Bioinformatik. Der Vortrag soll zunächst aufzeigen, wie die Edit-Distance mit quadratischem Platz- und Zeitverbrauch berechnet werden kann, und anschließend, wie man den Platzverbrauch durch Kombination mit der Divide-and-Conquer-Technik linear beschränken kann.
References: [1] Abschnitte 6.0, 6.6 und 6.7 aus Algorithm Design
[2] https://en.wikipedia.org/wiki/Edit_distance
Advisor: Simon Wimmer
Description:
Unification is the process of finding a most general substitution that unifies two terms, i.e., makes them syntactically equal. In this talk, a simple unification algorithm will be discussed and proved correct.
References: [1] Baader and Nipkow. Term Rewriting and All That.
Advisor: Tobias Nipkow
Description:
In computational geometry, different algorithms are proposed for computing the convex hull of a finite set of points.
Basic algorithms like Graham scan and Jarvis march [1] shall be studied and compared with an optimal (output-sensitive) algorithm like Chan's [3]. Thinking and reasoning abstractly about convex hull algorithms can give valuable insights [2].
References: [1] Introduction to algorithms, Thomas H. Cormen, MIT press, 2009 (Chapter 33: Computational Geometry)
[2] Donald E. Knuth. Axioms and Hulls, Springer, 1992
[3] http://link.springer.com/article/10.1007/BF02712873
Advisor: Fabian Immler
Description: Markov chains a the central concept in computer science to
model and analyse programs with random choice (e.g. a random number
generator). The student should give a overview of the behaviour of
Markov chains and the basic algorithms to compute reachability on
them.
References: [1] https://en.wikipedia.org/wiki/Markov_chain
Advisor: Johannes Hölzl
Description: Datalog is a subset of Prolog, designed for database applications.
It restricts syntax in numerous ways to avoid common problems in
Prolog (e.g. when using negation and recursion) [1,2]. Datalog itself
can be extended with constraints to make it more expressive while
maintaining nice computational properties. This topic is concerned
with some of these extensions and how to compile them away.
References: [1] Kemper, "Datenbanksystem: Eine Einführung", Abschnitt Deduktive Datenbanken
[2] Lam, Datalog
[3] Revesz, Safe Datalog Queries with Linear Constraints
Advisor: Lars Hupel
Description: Reliable computer systems must handle malfunctioning components that give conflicting information to different parts of the system. This situation can be expressed abstractly in terms of a group of generals of the Byzantine army camped with their troops around an enemy city. Communicating only by messenger, the generals must agree upon a common battle plan. However, one or more of them may be traitors who will try to confuse the others. The problem is to find an algorithm to ensure that the loyal generals will reach agreement.
References: [1] Lamport, Leslie, Robert Shostak, and Marshall Pease. The Byzantine generals problem. ACM Transactions on Programming Languages and Systems (TOPLAS) 4.3 (1982): 382-401.
Advisor: Ondřej Kunčar
Unabhängig von der Themenvergabe werden jedem Teilnehmer zwei Rezensionsthemen zugeordnet. Diese Zuordnung wird nur den Rezensoren per E-Mail mitgeteilt, sodass diese die Möglichkeit haben, anonym zu bleiben.
Jeder Teilnehmer reicht 4 Wochen vor dem Vortrag einen Entwurf seiner Ausarbeitung ein. Ein Entwurf ist eine ausformulierte und inhaltlich vollständige Version der Ausarbeitung, auf deren Basis die Rezensionen angefertigt werden.
Die Rezensoren erhalten die Entwürfe, sobald sie von den jeweiligen Autoren eingereicht werden und haben 2 Wochen für das Anfertigen der Rezension. Eine Rezension sollte etwa 1 Seite umfassen. Diese Rezensionen werden anschließend den Autoren zugänglich gemacht. Die Autoren haben dann noch 2 Wochen, die Kritik einzuarbeiten, bevor der Vortrag gehalten und die endgültige Version der Ausarbeitung eingereicht wird.
Die Rezensionen sollten sich hauptsächlich auf den Inhalt konzentrieren, wobei nicht erwartet wird, dass vom Rezensor weitere Recherche an den Quellen betrieben wird. Wichtig sind z.B. gute Strukturierung des Themas, schlüssige Argumentation und leicht verständliche Darstellung von Sachverhalten, die der Leser auch dann nachvollziehen kann, wenn er oder sie die Quelle dazu nicht gelesen hat. Rechtschreibung und Grammatik sind weniger wichtig, es macht aber natürlich Sinn, auch solche Fehler in der Rezension zu erwähnen. Eine Zusammenfassung des Themas ist nicht nötig. Die äußere Form der Rezensionen ist den Teilnehmern überlassen. Sowohl Stichpunkte als auch Fließtext sind in Ordnung.
Eine Vorversion der Präsentationsfolien wird 2 Wochen vor dem Vortrag eingereicht.
Die Länge eines Vortrags sollte ca. 45 Minuten betragen. Die Vorträge werden in Sitzungen zu je 2-3 Vorträgen abgehalten.
Die endgültige Version der Ausarbeitung wird am Tag des Vortrags eingereicht. Der Umfang sollte sich auf ca. 10 Seiten belaufen. Die äußere Form der Ausarbeitung ist im Rahmen des Üblichen den Teilnehmern überlassen. Es gibt keine Vorlage.
Die Endfassung der Präsentationsfolien wird am Tag des Vortrags im PDF Format eingereicht.
Die Note setzt sich wie folgt zusammen: 20% Rezensionen + 40% Vortrag + 40% Ausarbeitung
Bei der Recherchearbeit können Dienste wie Google Scholar dabei helfen, wissenschaftliche Veröffentlichungen zu finden. Anschließend kann mit Hilfe von eAccess darauf zugegriffen werden. Dieser Schritt ist meist notwendig, da die Verlage oft hohe Kosten für den Download dieser Veröffentlichungen veranschlagen.