Vær opmærksom på at dette website indeholder et arkiv med historiske data. Det aktuelle kursuskatalog findes på kursuskatalog.au.dk

AU kursuskatalog arkiv

[Forside] [Hovedområder] [Perioder] [Udannelser] [Alle kurser på en side]

Kompleksitetsteori (Q1+2) ( efterår 2008 - 10 ECTS )

Rammer for udbud

  • Uddannelsessprog: engelsk (eller dansk)
  • Niveau: Kandidatkursus
  • Semester/kvarter: Q1+Q2 i /
  • Timer per uge: Forelæsninger (2+2t/uge)
  • Deltagerbegrænsning: Ingen
  • Undervisningssted: Århus
  • Hovedområde: Det Naturvidenskabelige Fakultet
  • Udbud ID: 12546

Formål

Deltagerne vil efter kurset have detaljeret kendskab til grundlæggende resultater og teknikker i Kompleksitetsteori og et grundlag for at forstå emner og resultater ud over de, der behandles i kurset. Kursets arbejdsform vil også træne deltagernes evne til at formidle og kommunikere faglige problemstillinger og til at læse og forstå videnskabelige artikler.

Obligatorisk program

Udarbejdning af forelæsningsnoter samt aflevering af 4-5 opgavesæt.

Indhold

Kompleksitetsteori er studiet af effektiv beregning og fundamentale begrænsninger heraf. Teorien sætter en istand til på en præcis måde at opstille spørgsmål herom og give kvalificerede svar på disse. Eksempler på sådanne spørgsmål er: Hvor meget tid og plads kræves for at løse konkrete beregningsproblemer? Kan brugen af tilfældighed eller massiv parallelisme gøre beregninger signifikant hurtigere? Hvor godt kan optimeringsproblemer vi ikke er istand til at løse eksakt approximeres? Kurset vil give en fundamental indføring i klassiske resultater i kompleksitetsteori og herefter behandle (udvalgte) nyere resultater og områder.

Faglige forudsætninger

Kombinatorisk Søgning

Underviser

Kristoffer Arnsfelt Hansen, Peter Bro Miltersen

Undervisnings- og arbejdsform

Forelæsninger

Litteratur

Annonceres senere

Kursushjemmeside

http://www.daimi.au.dk/~arnsfelt/CT08

Læringsmål

Deltagerne skal ved afslutningen af kurset kunne:

  • skelne og forklare centrale begreber i kompleksitetsteori.
  • bevise resultaterne gennemgået i kurset.
  • anvende generelle teknikker til at løse kompleksitetsteoretiske problemstillinger.
  • perspektivere relationener mellem kompleksitetsteori og andre områder af teoretisk datalogi.

Udbyder

Datalogisk Institut

Tilmelding til undervisning

http://www.brics.dk/~mis/enrollment.html

Bedømmelse

Mundtlig eksamen uden forberedelse
7-skala, intern censur