Komplexitätstheorie

NUMMER: 150262
KÜRZEL: ComplTh
DOZENT: Prof. Dr. Thomas Zeume
FAKULTÄT: Center of Computer Science
SPRACHE: Deutsch
SWS: 6
CREDITS: 9
WORKLOAD:
ANGEBOTEN IM: jedes Wintersemester

INFOS

Be­ginn: Diens­tag den 27.​10.​2020 Vor­le­sung Diens­tags: ab 14:00 bis 16.​00 Uhr im On­line Vor­le­sung Don­ners­tags: ab 14:00 bis 16.​00 Uhr im On­line Übung Don­ners­tags: ab 14:00 bis 16.​00 Uhr im On­lineWin­ter­se­mes­ter 2020/2021Die Or­ga­ni­sa­ti­on und sämt­li­che Kurs­ak­ti­vi­tä­ten er­fol­gen über einen Mood­le-Kurs.Mood­le-Kurs: https://​moodle.​ruhr-uni-bo­chum.​de/​m/​course/​view.​php?​id=32920


PRÜFUNGUNGSFORM

Die An­ga­ben zu den Prü­fungs­mo­da­li­tä­ten (im SoSe/WiSe 2020) er­fol­gen vor­be­halt­lich der ak­tu­el­len Si­tua­ti­on. Not­wen­di­ge Än­de­run­gen auf­grund uni­ver­si­tä­rer Vor­ga­ben wer­den zeit­nah be­kannt­ge­ge­ben.
Ter­min nach Ab­spra­che mit dem Do­zen­ten.
Prü­fungs­form: münd­lich
Prü­fungs­an­mel­dung: Flex­Now
Dauer: 30min


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

Keine


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