1. Home
  2. /
  3. Studium
  4. /
  5. Lehrveranstaltungen
  6. /
  7. ComplTh

Komplexitätstheorie

NUMMER: 150262
KÜRZEL: ComplTh
MODULBEAUFTRAGTE:R: Prof. Dr. Thomas Zeume
DOZENT:IN: Prof. Dr. Thomas Zeume
FAKULTÄT: Fakultät für Informatik
SPRACHE: Deutsch
SWS: 6
CREDITS: 9
ANGEBOTEN IM: jedes Wintersemester

LERNFORM

Moodle

LERNZIELE

Die Vor­le­sung hat das Ziel, einen brei­ten Über­blick über die grund­le­gen­den Kon­zep­te und Re­sul­ta­te der Kom­ple­xi­täts­theo­rie zu geben:
- Klas­si­sche Re­sul­ta­te für Platz- und Zeit­kom­ple­xi­täts­klas­sen: z.B. die Kor­re­spon­denz zwi­schen Spie­len und Spei­cher­platz-Be­schrän­kun­gen, der Nach­weis, dass sich mit mehr Platz oder Zeit auch mehr Pro­ble­me lösen las­sen, wei­te­re grund­le­gen­de Be­zie­hun­gen zwi­schen Zeit- und Platz­ba­sier­ten Klas­sen, und die Kom­ple­xi­täts­welt zwi­schen NP und PSPACE
- Grund­zü­ge der Kom­ple­xi­täts­theo­rie par­al­le­ler, zu­falls­ba­sier­ter und ap­pro­xi­ma­ti­ver Al­go­rith­men
- Ein­füh­rung in aus­ge­wähl­te neue­re The­men: Kom­ple­xi­täts­theo­rie des in­ter­ak­ti­ven Rech­nens, des pro­ba­bi­lis­ti­schen Be­wei­sens und Fi­ne-grained Com­ple­xi­ty.
Diese Ver­an­stal­tung rich­tet sich an Stu­die­ren­de der Ma­the­ma­tik und In­for­ma­tik.

INHALT

Die Kom­ple­xi­täts­theo­rie un­ter­sucht und klas­si­fi­ziert Be­rech­nungs­pro­ble­me be­züg­lich ihrer al­go­rith­mi­schen Schwie­rig­keit. Ziel ist es, den in­hä­ren­ten Res­sour­cen­ver­brauch be­züg­lich ver­schie­de­ner Res­sour­cen wie Re­chen­zeit oder Spei­cher­platz zu be­stim­men, und Pro­ble­me mit ähn­li­chem Res­sour­cen­ver­brauch in Kom­ple­xi­täts­klas­sen zu­sam­men­zu­fas­sen. Die be­kann­tes­ten Kom­ple­xi­täts­klas­sen sind si­cher­lich P und NP, die die in po­ly­no­mi­el­ler Zeit lös­ba­ren bzw. ve­ri­fi­zier­ba­ren Pro­ble­me um­fas­sen. Die Frage, ob P und NP ver­schie­den sind, wird als eine der be­deu­tends­ten of­fe­nen Fra­gen der theo­re­ti­schen In­for­ma­tik, ja sogar der Ma­the­ma­tik, an­ge­se­hen. P und NP sind je­doch nur zwei Bei­spie­le von Kom­ple­xi­täts­klas­sen. An­de­re Klas­sen er­ge­ben sich unter an­de­rem bei der Un­ter­su­chung der des be­nö­tig­ten Spei­cher­plat­zes, der ef­fi­zi­en­ten Par­al­le­li­sier­bar­keit von Pro­ble­men, der Lös­bar­keit durch zu­falls­ge­steu­er­te Al­go­rith­men, und der ap­pro­xi­ma­ti­ven Lös­bar­keit von Pro­ble­men.

VORAUSSETZUNGEN CREDITS

Bestandene Modulabschlussprüfung

EMPFOHLENE VORKENNTNISSE

Grund­la­gen der Theo­re­ti­schen In­for­ma­tik

LITERATUR

1. Pa­pa­di­mi­troiu, C. "Com­pu­ta­tio­nal Com­ple­xi­ty ", Ad­di­son-Wes­ley, 1993
2. "Com­pu­ta­tio­nal Com­ple­xi­ty: A Mo­dern Ap­proach", Cam­bridge Uni­ver­si­ty Press, 2009 http://​theory.​cs.​princeton.​edu/​complexity/​book.​pdf
3. We­ge­ner, Ingo "Kom­ple­xi­täts­theo­rie: Gren­zen der Ef­fi­zi­enz von Al­go­rith­men", Sprin­ger Ver­lag, 2003
4. Kozen, Dex­ter "Theo­ry of Com­pu­ta­ti­on", Sprin­ger, 2006