Wir beschäftigen uns mit shared- und distributed memory parallelen Algorithmen für fundamentale algorithmische Probleme wie Suchen, Sortieren, Hashing etc.

Bitte beachten Sie neben den in der Vorbesprechung bekanntgegebenen Informationen auch dieses Informationsblatt (neu!).

• 1. Maschinenmodelle: McCool et al. Kap. 2.4-2.6 OHNE 2.5
• 2. Performanzmessung: McCool et al. Kap. 2.5 und Dietzfelbinger et al. Kap. 2.10 und McCool et al. 2.5.6
• 3. PRAM: Dietzfelbinger et al. Kap. 2.4.1, Cormen et al. Kap. 27.1
• 4. BSP/Distributed Memory: Dietzfelbinger et al. Kap. 2.4.2-2.4.3 und 3.1

• 5. Präfixsumme: Blelloch 1.1-1.2
• 6. List-Ranking: Dietzfelbinger et al. Kap. 3.3
• 7. Hashing: Dietzfelbinger et al. Kap. 4.6
• 8. Selection: Dietzfelbinger et al. Kap. 5.8-5.9
• 9. Queues und Prioritätswarteschlangen: Dietzfelbinger et al. Kap. 3.7 und 6.4

• 10. Quicksort: Dietzfelbinger et al. Kap. 5.7
• 11. Mergesort: Cormen et al. Kap. 27.3 und Dietzfelbinger et al. Kap. 5.14
• 12. Sample Sort: Dietzfelbinger et al. Kap. 5.13 und McCool et al. Kap. 14

• 13. Breitensuche: Dietzfelbinger et al. Kap. 9.2
• 14. DAG-Traversal: Dietzfelbinger et al. Kap. 9.4
• 15. Minimum Spanning Trees: Dietzfelbinger et al. Kap. 11.6

• 16. Dietzfelbinger et al. Kap. 13.1-13.3
• 17. Dietzfelbinger et al. Kap. 13.4-13.6

• 18. Dietzfelbinger et al. Kap. 14.1-14.3
• 19. Dietzfelbinger et al. Kap. 14.4-14.5

Sie sollten Spaß an algorithmischen Problem und der Analyse von Algorithmen haben. Die Vorlesung DAP2 sollte nicht zu Ihren schlechtesten Fächern gehört haben. Im Idealfall haben Sie bereits andere Veranstaltungen aus diesem Bereich gehört (Effiziente Algorithmen, Algorithmen auf Sequenzen, etc.) bzw. haben vor, dies noch zu tun.

Das Proseminar ist geeignet für Informatikstud. in den Bachelor-Studiengängen oder für Informatik-Lehramtsstud. (als “Seminar” im Modul INF-ML-101). Es eignet sich gut als Vorbereitung zur Erstellung von Studien- oder Abschlussarbeiten in der Arbeitsgruppe von Johannes Fischer.

• 25.1.2019, 15:30: Vorbesprechung in OH12, 3.030
• Präsentationskurs: Freitag, 5.4.2019, 9-17 Uhr.
• Proseminar: 3 Blocktage am 5.-7.6.2019, jeweils 9-17 Uhr