Aktuelle Themen der Theoretischen Informatik - Algorithmen (SS 2017)

Seminarbetreuung

Alex Schickedanz

Inhalt

Gegenstand dieses Seminars sind parallele Modelle, Entwurfsmethoden und Algorithmen sowie deren Analyse.

Termine

Das Seminar findet ab dem 01.06.2017 wöchentlich Donnerstags von 16 bis 19 Uhr in SR 11 statt.

Organisation

Während jedes regulären Termins werden zwei oder drei Vorträge mit je 20min Votragszeit (zzgl. Diskussionszeit) stattfinden. Die Themen sollen von allen Studenten vorbereitet werden. Zusätzlich werden wöchentlich Aufgaben gestellt und zum nächsten Termin vorgerechnet.

Bitte schicken Sie Ihren Foliensatz spätestens am Montag der Woche Ihres Vortrag an Ihren Betreuer.

Das Seminar gilt als bestanden, wenn der Vortrag bestanden wurde, mindestens 70% der Aufgaben vorbereitet sowie einmal vorgerechnet wurde. Aufgaben

• Zum 01.06.: Aufgaben 1.4, 1.8 und 1.14
• Zum 08.06.: Aufgaben 2.7, 2.13 und 2.24
• Zum 22.06.: Aufgaben 3.4, 3.9 und 3.11
• Zum 06.07.: Aufgaben 3.20, 4.1 und 4.6
• Zum 13.07.: Aufgaben 6.4 und 6.16

Themen

Wir orientieren uns am Buch J. JáJá An Introduction to Parallel Algorithms, das in der Bibliothek und in Raum 312 vorhanden ist. Sie haben während der Vorbesprechung die Möglichkeit Präferenzen für Vorträge anzugeben.

1. Termin (01.06.)
   • Andreas Bienert & Hendrik Wiechula (gemeinsam)
     Thema: Kapitel 1.1 - 1.7 Basics of Parallel Algorithms
     Betreuer: Schickedanz
2. Termin (08.06.)
   • Andreas Herzog
     Thema: Kapitel 2.1, 2.3 Balanced Trees and Divide and Conquer
     Betreuer: Behdju
   • Jonathan Boll
     Thema: Kapitel 2.2, 2.4, 2.5 Pointer Jumping, Partitioning and Pipelining
     Betreuer: Behdju
3. Termin (22.06.)
   • Ionut Petre Urs
     Thema: Kapitel 3.1 List Ranking
     Betreuer: Behdju
   • Elizaveta Kovalevskaya
     Thema: Kapitel 3.2 The Euler-Tour Technique
     Betreuer: Meyer
4. Termin (29.6.)
   • Walaa Karakich
     Thema: Kapitel 3.3 Tree Contraction
     Betreuer: Penschuck
   • Jakob Schröber
     Thema: Kapitel 4.1, 4.2 Searching and Merging
     Betreuer: Penschuck
   • Michael Czaja
     Thema: Kapitel 4.4 Sorting Networks sowie eine Übersicht über AKS Netze
     Betreuer: Schickedanz
5. Termin (06.07)
   • Mehrnoosh Shariati Najafabadi
     Thema: Kapitel 6.1 The Convex-Hull Problem Revisited
     Betreuer: Penschuck
   • Alexander Janzen
     Thema: Kapitel 6.3 Plane Sweeping
     Betreuer: Schickedanz
6. Termin (13.07.)
   • Matthias Kühnel
     Thema: Kapitel 9.1 Performance Measures of Randomized Parallel Algorithms
     Betreuer: Meyer
   • Lea Berty
     Thema: Kapitel 10.1 Simulation Between PRAM Models
     Betreuer: Meyer