1. Modulverzeichnis (MTS)
  2. Module
  3. Modulbeschreibung anzeigen

Computational Complexity

Anzeigesprache
Zur Modulseite PDF generieren

#40379 / #2

WS 2014/15 - WS 2014/15

Deutsch

Computational Complexity
Komplexitätstheorie

9

Niedermeier, Rolf

benotet

Mündliche Prüfung

Zugehörigkeit


Fakultät IV

Institut für Softwaretechnik und Theoretische Informatik

34351100 FG Algorithmik und Komplexitätstheorie

Keine Angabe

Kontakt


TEL 5-1

Thielcke, Christlinde

lehre@akt.tu-berlin.de

http://www.akt.tu-berlin.de/menue/teaching

Lernergebnisse

Participants of this module can classify discrete computational problems according to their computational complexity using standard complexity classes. They understand structural properties of complexity classes and can make qualitative and quantitative statements about computational complexity questions. The course is principally designed to impart: technical skills 50x , method skills 50 x ,system skills 0x …,social skills 0x

Lehrinhalte

Introduction into structural complexity theory, with particular emphasis on complexity resources time and space. Particular topics are: * complexity classes * theory of the NP-completeness * hierarchy theorems and polynomial time hierarchy * interactive proof systems

Modulbestandteile

Pflichtteil:

Die folgenden Veranstaltungen sind für das Modul obligatorisch:

LehrveranstaltungenArtNummerTurnusSpracheSWSVZ
Computational ComplexityVL0434 L 233SoSeKeine Angabe4
Computational ComplexityUE0434 L 233SoSeKeine Angabe2

Arbeitsaufwand und Leistungspunkte

Computational Complexity (VL):

AufwandbeschreibungMultiplikatorStundenGesamt
Präsenzzeit15.04.0h60.0h
Vor-/Nachbereitung15.06.0h90.0h
150.0h(~5 LP)

Computational Complexity (UE):

AufwandbeschreibungMultiplikatorStundenGesamt
Präsenzzeit15.02.0h30.0h
Vor-/Nachbereitung15.06.0h90.0h
120.0h(~4 LP)
Der Aufwand des Moduls summiert sich zu 270.0 Stunden. Damit umfasst das Modul 9 Leistungspunkte.

Beschreibung der Lehr- und Lernformen

There is a lecture 4 hours per week presenting the whole course material. The lectures are accompanied by 2-hour tutorials, where an active participation and homework on the work sheets distributed every week is required.

Voraussetzungen für die Teilnahme / Prüfung

Wünschenswerte Voraussetzungen für die Teilnahme an den Lehrveranstaltungen:

a) obligatory: Basic course on automata and complexity b) desirable: Basic knowledge on algorithms

Verpflichtende Voraussetzungen für die Modulprüfungsanmeldung:

Dieses Modul hat keine Prüfungsvoraussetzungen.

Abschluss des Moduls

Benotung

benotet

Prüfungsform

Mündliche Prüfung

Sprache

Deutsch

Dauer/Umfang

Keine Angabe

Dauer des Moduls

Für Belegung und Abschluss des Moduls ist folgende Semesteranzahl veranschlagt:
1 Semester.

Dieses Modul kann in folgenden Semestern begonnen werden:
Sommersemester.

Maximale teilnehmende Personen

Dieses Modul ist nicht auf eine Anzahl Studierender begrenzt.

Anmeldeformalitäten

Please register at QISPOS or directly at the examination office.

Literaturhinweise, Skripte

Skript in Papierform

Verfügbarkeit:  nicht verfügbar

 

Skript in elektronischer Form

Verfügbarkeit:  nicht verfügbar

 

Literatur

Empfohlene Literatur
Christos H. Papadimitriou: Computational Complexity, Addison Wesley, 1994.
Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach, Ca mbrid ge University Press, 2009

Zugeordnete Studiengänge


Diese Modulversion wird in folgenden Studiengängen verwendet:

Studiengang / StuPOStuPOsVerwendungenErste VerwendungLetzte Verwendung
Dieses Modul findet in keinem Studiengang Verwendung.

Studierende anderer Studiengänge können dieses Modul ohne Kapazitätsprüfung belegen.

Computer Science Master with focus “Reliable Systems” Computer Science diploma Technical Computer Science Master with focus “Software Engineering” Technical Computer Science diploma

Sonstiges

Keine Angabe