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]

Communication Complexity (Q2) ( efterår 2011 - 5 ECTS )

Rammer for udbud

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

Formål

Deltagerne vil efter kurset have detaljeret kendskab til øvre og nedre grænser i kommunikationskompleksitet, samt kendskab til forskellige måder hvorved kommunikationskompleksitet relateres til andre områder af teoretisk datalogi og et grundlag for at forstå i hvilke situationer kommunikationskompleksitet er anvendelig og relevant. Kursets arbejdsform vil også træne deltagernes evne til at søge information på egen hånd, til at formidle og kommunikere faglige problemstillinger og til at læse og forstå videnskabelige artikler.

Obligatorisk program

Produktion af forelæsningsnoter

Indhold

Kommunikationskompleksitet betragter problemer hvor input er fordelt mellem to eller flere parter som må samarbejde om at producere et output. Indenfor kommunikationskompleksitet er man primært intereseret i mængden af kommunikation nødvendig for at parterne korrekt løser et givet problem. Udover at være et dybt og smukt område indenfor teoretisk datalogi, er kommunikationskompleksitet også et af de vigtigste redskaber til at vise nedre grænser i datalogi. Nedre grænser i kommunikationskompleksitet er blevet brugt til at vise nedre grænser i mange andre områder af datalogi, såsom tradeoffs mellem tid og plads i datastrukturer, tradeoffs mellem størrelse af dybde af Booleske netværk, nedre grænser på pladsforbrug af datastrømsberegninger, og nedre grænser på kompleksiteten af property testing. Dette kursus introducerer de gængse modeller for kommunikationskompleksitet og de mest anvendelige teknikker til at vise nedre grænser. I anden halvdel af kurset ses på de anvendelser, f.eks på datastrukturer. Hvilke anvendelser der fokuseres på vil til dels afhænge af deltagernes interesser. Ingen baggrundsviden om kommunikationskompleksitet er nødvendig, men et vist niveau af matematisk modenhed er ønskværdigt.

Faglige forudsætninger

Underviser

Joshua Brody og Peter Bro Miltersen (ansv.)

Undervisnings- og arbejdsform

Forelæsninger og øvelser

Litteratur

Kushilevitz og Nisan: Communication Complexity (Cambridge University Press) samt handouts

Læringsmål

Deltagerne skal ved afslutningen af kurset kunne:

  • beskrive beviser for kendte nedre og øvre grænser i kommunikationskompleksitet.
  • forklare ideerne bag sådanne resultater.
  • anvende kommunikationskompleksitet til situationer i datalogi, såsom VLSI, netværkskompleksitet, datastrømme, property testing og datastrukturer.

Eksamensterminer

Q2

Udbyder

Datalogisk Institut

Tilmelding til undervisning

http://mit.au.dk

Bedømmelse

Mundtlig eksamen, 30 minutter uden forberedelse
7-skala, intern censur