Modul CS4501-KP12, CS4501
Algorithmik, Logik und Komplexität (ALK14)
Dauer
2 Semester
Angebotsturnus
Jedes Sommersemester
Leistungspunkte
12
Studiengang, Fachgebiet und Fachsemester:
- Master Entrepreneurship in digitalen Technologien 2020, Vertiefungsmodul, fachspezifisch, Beliebiges Fachsemester
- Master Informatik 2019, Wahlpflicht, Vertiefungsmodule, Beliebiges Fachsemester
- Master IT-Sicherheit 2019, Vertiefungsmodul, Vertiefung Informatik, 1. oder 2. Fachsemester
- Master Entrepreneurship in digitalen Technologien 2014, Vertiefungsmodul, fachspezifisch, 2. und/oder 3. Fachsemester
- Master Informatik 2014, Vertiefungsmodul, Vertiefung, 2. und/oder 3. Fachsemester
Lehrveranstaltungen:
- CS4501-S: Seminar Algorithmik, Logik und Komplexität (Seminar, 2 SWS)
- CS4501-Ü: Algorithmik, Logik und Komplexität (Übung, 2 SWS)
- CS4501-V: Algorithmik, Logik und Komplexität (Vorlesung, 4 SWS)
Workload:
- 120 Stunden Präsenzstudium
- 160 Stunden Selbststudium und Aufgabenbearbeitung
- 40 Stunden Prüfungsvorbereitung
- 40 Stunden Bearbeitung eines individuellen Themas inkl. Vortrag und schriftl. Ausarbeitung
Lehrinhalte:
- neue Ergebnisse im Bereich Algorithmen- und Komplexitätstheorie
- Schaltkreiskomplexität, Kommunikationskomplexität
- Strukturelle und deskriptive Komplexitätstheorie
- Algorithmische Spieltheorie
- Nichtstandardberechnungsmodelle
- Ausdrucksstarke von Logiken verstehen und anwenden können
Qualifikationsziele/Kompetenzen:
- Die Studierenden können ein tiefes Verständnis der Konzepte und Methoden des Algorithmenentwurfs und der Komplexitätsanalyse demonstrieren.
- Sie können komplexe algorithmische Probleme bezüglich ihrer Komplexität einordnen und daraus Lösungsmethoden ableiten.
- Sie können komplexe Problemstellungen adäquat formal modellieren.
- Sie können die Bedeutung von unteren Komplexitätsschranken für reale Probleme einschätzen und erläutern.
Vergabe von Leistungspunkten und Benotung durch:
- Mündliche Prüfung
Setzt voraus:
Modulverantwortliche:
Literatur:
- R. Reischuk : Einführung in die Komplexitätstheorie Teubner, 1990
- S. Arora, B. Barak : Computational Complexity Cambridge UP 2009
- C. Papadimitriou : Computational Complexity Addison-Wesley, 1994
- M. Huth, M. Ryan : Logic in Computer Science Cambridge University. Press 2004
- D. Kozen : Theory of Computation Springer, 2006
Sprache:
- Sowohl Deutsch- wie Englischkenntnisse nötig
Bemerkungen:
Zulassungsvoraussetzungen zur Belegung des Moduls:- Keine (die Kompetenzen der unter Setzt voraus genannten Module werden für dieses Modul benötigt, sind aber keine formale Voraussetzung)
Zulassungsvoraussetzungen zur Teilnahme an Modul-Prüfung(en):
- Erfolgreiche Bearbeitung von Übungsaufgaben gemäß Vorgabe am Semesteranfang
- Seminarvortrag
- Seminararbeit
Modulprüfung(en):
- CS4501-L1: Algorithmik, Logik und Komplexität, mündliche Prüfung, 100% der Modulnote
Das zugehörige Seminar wird im darauffolgenden WS angeboten. Nach Absprache kann das Seminar auch parallel im gleichen Semester durchgeführt werden.
Letzte Änderungen:
06.01.2025