Zoek
English
  Studiegidsen 2011-2012
Radboud UniversiteitStudiegidsenFaculteit der Natuurwetenschappen, Wiskunde en Informatica > Master Mathematics

Complexiteitstheorie 

Vakcode
NWI-WM072B
Studiepunten
6
Periode
tweede semester
Werkvormen
  • 32 uur hoorcollege
  • 32 uur werkcollege
Vereiste voorkennis
Geen speciale voorkennis is benodigd, behalve enige wiskundige volwassenheid. Enige vertrouwdheid met wiskundige logica (propositielogica en predikaatlogica) strekt tot aanbeveling.
Leerdoelen
  • De student heeft kennis van tijd- en ruimte-begrensde berekenbaarheid, nondeterminisme.
  • De student heeft kennis van reducties en volledigheid, gerelativeerde berekenbaarheid.
  • De student heeft kennis van interactive en zero-knowledge proofs, geparametriseerde complexiteit.
  • De student heeft kennis van diagonalisatie, de polynomiale hierarchie, structuur versus complexiteit van verzamelingen.
  • De student heeft kennis van randomisatie, cryptografie, complexiteit van bewijzen.
Beschrijving
Complexiteitstheorie is een gebied op het grensvlak van wiskunde en informatica waarin problemen worden geklassificeerd volgens de benodigde middelen (zoals rekentijd en geheugen) om ze op te lossen. Dit leidt tot de studie van een aantal fundamentele complexiteitsklassen, zoals de klassen P, NP, PSPACE en vele andere. Deze klassen vormen een ijkpunt voor de moeilijkheidsgraad van computationele problemen, en hebben tal van toepassingen in de wiskunde en daarbuiten. Dit gebied herbergt tevens een van de meest fundamentele onopgeloste problemen uit de wiskunde, namelijk de vraag of de klasse P gelijk is aan NP.
Onderwerpen
  • Tijd- en ruimte-begrensde berekenbaarheid,
  • nondeterminisme,
  • reducties en volledigheid,
  • gerelativeerde berekenbaarheid,
  • diagonalisatie,
  • de polynomiale hierarchie,
  • structuur versus complexiteit van verzamelingen,
  • randomisatie,
  • cryptografie,
  • complexiteit van bewijzen,
  • interactive en zero-knowledge proofs,
  • geparametriseerde complexiteit.
Tentaminering
Schriftelijk tentamen
Literatuur

Syllabus Complexity Theory, beschikbaar op de webpagina van de docent.