Website
Modulhandbuch vor WS2020/21

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), 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
Setzt voraus:
Modulverantwortlicher:
Lehrende:
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 Änderung:
14.2.2024