| Modul: | Algorithmik Algorithmics |
| Belegnummern: | 41.4964 [PVL 41.4965] |
| Sprache: | deutsch |
| Zuordnung: | CNAM - Masterzyklus
CNAM Master - Masterzyklus
Dualer Master 2021 - Katalog T: Theorieorientierte Module
Master 2021 - Katalog T: Theorieorientierte Module
Dualer Master 2013 - Katalog T: Theorieorientierte Module
JIM 2013 - Elective Catalogue T
Master 2013 - Katalog T: Theorieorientierte Module
Master 2006 - Katalog T: Theorieorientierte Module
Master 2006 - Vertiefung CG: Computer Graphik
Master 2006 - Vertiefung TS: Technische Systeme
MN Data Science 2016 - Katalog DS-I: Data Science - Informatik |
| Lehrform: | V+Ü = Vorlesung+Übung |
| SWS: | 3+1 |
| CP: | 6 |
| Prüfung: | Klausur |
| Anmeldung zur Prüfung: | explizit und unabhängig von der Belegung |
| PVL (z.B. Praktikum): | unbenotet (Erfolgreiche Teilnahme an den Übungen: Die Prüfungsvorleistung ist erbracht worden, wenn 50% der Übungsaufgaben bearbeitet wurden, korrekte Lösungen für zwei Übungsaufgaben im Rahmen der Übung vorgestellt wurden und eine korrekte Musterlösung für eine Übungsaufgabe ausgearbeitet und abgegeben wurde.) |
| Häufigkeit des Angebots: | jährlich |
| Lernziele: | Im Mittelpunkt stehen folgende Lernziele:
- Verständnis ausgewählter Prinzipien zum Entwurf effizienter Algorithmen
- Kenntnis von der Umsetzung dieser Prinzipien im Anwendungsgebiet algorithmische Geometrie
- Fähigkeit, komplizierte Algorithmen in Bezug auf deren Laufzeit zu analysieren
- Kenntnis grundlegender Ansätze zum Umgang mit schwierigen algorithmischen Problemen und von den Möglichkeiten und Grenzen solcher Ansätze
|
| Lehrinhalte: | - Grundlegende Konzepte
- Laufzeit von Algorithmen
- Komplexitätsmaße, Abschätzungen
- Prinzipien des Entwurfs effizienter Algorithmen
- dynamisches Programmieren
- Greedy Algorithmen
- Divide & Conquer Algorithmen
- Anwendungsgebiet algorithmische Geometrie
- effiziente Algorithmen für ausgewählte Probleme (inklusive der zugrunde liegenden algorithmischen Prinzipien und geeigneter Datenstrukturen; u.a. Scan-line Prinzip, geometrisches Divide & Conquer Algorithmen)
- Umgang mit schwierigen Problemen
- P=NP? Problematik
- Heuristiken (lokale Suche, Branch & Bound)
- Approximationsschemata
Parallel zu Vorlesung und Übung arbeiten sich die Studierenden selbständig in das Thema randomisierte Algorithmen ein (mit Verständnisabfrage in einer Klausuraufgabe). |
| Literatur: | - Cormen, Th.H., Leiserson, Ch.E., Rivest, R., Stein, C.: Algorithmen - Eine Einführung, 2. Auflage, Oldenbourg Verlag, 2007.
- Hromkovic. J.: Algorithmics for Hard Problems, 2nd Edition, Springer, 2003.
- Klein, R.: Algorithmische Geometrie, Springer 2005.
- Schöning, U.: Algorithmen, Spektrum-Akademischer Verlag, 2001.
|
| Arbeitsformen / Hilfsmittel: | Vorlesung, Übung zur Diskussion von Übungsaufgaben, die zu Hause zu bearbeiten sind; Hilfsmittel: Folien, Übungsblätter |
| Modulverantwortung: | Steffen Lange |
| Freigabe ab: | SS 2015 |
| Fachliche Kompetenzen: | - Formale, algorithmische, mathematische Kompetenzen: hoch
- Analyse-, Design- und Realisierungskompetenzen: schwach
- Befähigung zum Wissenschaftlichen Arbeiten: mittel
|
| Überfachliche Kompetenzen: | - Fachübergreifende Sachkompetenzen: Mathematische und naturwissenschaftliche Grundkompetenz
|