Modul CS4501-KP12, CS4501

Algorithmik, Logik und Komplexität (ALK14)

Dauer:

2 Semester

Angebotsturnus:

Jedes Sommersemester

Leistungspunkte:

Studiengang, Fachgebiet und Fachsemester:

Master Entrepreneurship in digitalen Technologien 2020 (Vertiefungsmodul), Technologiefach Informatik, 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), Technologiefach Informatik, 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:

40 Stunden Bearbeitung eines individuellen Themas inkl. Vortrag und schriftl. Ausarbeitung
40 Stunden Prüfungsvorbereitung
160 Stunden Selbststudium und Aufgabenbearbeitung
120 Stunden Präsenzstudium

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

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.