WS 2011/2012 » Komplexitätstheorie
Ziegler

ÜbersichtSupplements

Aktuelles

01.02.2012krankheitshalber muß morgen (Donnerstag) die Vorlesung leider ausfallen
06.12.2011Am 16.12. findet an Stelle der Übung im Raum 201 die Vorlesung im Raum 301 statt;
dafür ist am 22.12. Übung.
27.10.2011Wegen einer Habilitationsprüfung beginnt die Vorlesung am 3.11. mit 30 Minuten Verspätung.
24.10.2011Erste Übung am 27.Oktober (Donnerstag) um 14h25 im S2|15-201
17.10.2011The second lecture will take place on Tuesday, October 25.
Time (and place) for exercises and subsequent lectures will be agreed upon based on a doodle-poll; see the first exercise sheet.
No lecture on October 19 (Wednesday)!
06.09.2011Initial session (Vorbesprechung) 18.10.2011 14h25 im S101/A2

 

Veranstalter

Name Raum Tel.
Ziegler, Martin

 

Vorlesung

TagUhrzeitin Raum
Donnerstags14:25 - 16:05S2|15-201

 

Literatur

 

Übung

Nr.Zeitin Raumbei
1Freitags, 11:40 - 13:20S2|15-201Carsten Rösnick

 

Formalien

Für Bachelor im dritten Studienjahr
V2Ü2, 6 ECTS Punkte
auch anrechenbar für den Studiengang Informatik, vgl. MHB 432
Veranstaltungssprache: Englisch (default)

 

Contents

  • asymptotics, models of computation, ressources
  • Turingmachines and their progrogramming
  • polynomial time and space
  • exemplary problems SAT, 3SAT, IS, Clique
  • relations among them, reduction
  • class NP, Cook-Levin Theorem
  • further NP-complete problems
  • approximation algorithms and quality
  • examples: VC, metr. TSP, Knapsack
  • nonapproximability
  • PSPACE and QBF
  • winning strategies on graphs
  • Savitch's Theorem
  • reachability and NL
  • Immerman-Szelepcsényi
  • parallel complexity and circuits
  • P-completeness
  • cryptographie and UP
  • randomized complexity
  • polynomial hierarchy
  • Sipser-Gács-Lautemann

 

Skript

von Prof. Blömer und (auf english) von Prof. Bläser

 

Aktuelles

Achtung: Vom 23.10.2017 bis 25.10.2017 ist das Studienbüro wegen Semestervorbereitung geschlossen! Die Sprechstunden entfallen!


Ordnungen, Formulare, etc.

Dokumente wie Prüfungsplan-formulare, Studien- und Prüfungspläne oder Modulhandbücher finden Sie im Downloadbereich

Sabine Bartsch
Iryna Bysaha
Meike Mühlhäußer
Alexandra Neutsch
Bettina Plutz (in Elternzeit)

Sprechzeiten:
Mo13:30-15:30
Mi, Do10:30-12:30

studienbuero(at)mathematik.tu-darmstadt.de

Studienberatung

 Albrun Knof

Sprechzeiten:
Mo13:30-15:00
Mi10:30-12:00

Die Sprechstunden finden in Raum S2|15 241 statt. Es ist keine Terminvereinbarung notwendig.

Weitere Fragen bitte per Mail an:

studienberatung(at)mathematik.tu-darmstadt.de

 

 

A A A | Print Drucken | Impressum Impressum | Contact Kontakt
    zum Seitenanfangzum Seitenanfang