I00023 (I00023)
Complexiteitstheorie*
< 2006/2007 > 04-09-2006 t/m 13-01-2007 (23-02-2007) H
Informatica - Master variant C (2003) Thematische specialisatie Foundations of computer science (6 ec) Keuze informatica (6 ec)
Informatica - Master variant E (2003) Keuze informatica (6 ec)
Informatica - Master variant MT (2005) Thematische specialisatie Foundations of computer science (6 ec) Foundations of computer science (6 ec) Keuze informatica (6 ec) (6 ec) (6 ec)
Informatica - Master variant O (2003) Thematische specialisatie Foundations of computer science (6 ec) Keuze informatica (6 ec)
Informatica - Master variant O (2005) Thematische specialisatie Foundations of computer science (6 ec) Keuze informatica (6 ec)
omvang
6 ec (168 uur) : 32 uur plenair college, 0 uur groepsgewijs college, 0 uur computerpracticum, 0 uur 'droog' practicum, 32 uur gesprekken met de docent, 0 uur onderling overleg met medestudenten (werkgroepen, projectwerk e.d.), 104 uur zelfstudie
investering
6 ec * 28 u/ec + #std * (1 + 6ec * 0.15 u/student/ec)
inzet tentatief

examinator
afdeling
tijdbesteding

dr. Dick van Leijenhorst
das
195u.

speciale web-site
/~bolke/CXT/BeschrCXT.html

 

CXT gaat over de complexiteit van algorithmen, dus het kostenaspect: snelle programma1s, indeling in klassen, boven- en ondergrenzen, berekeningsmodellen. Het bouwt voort op het college T2 (zie ook inleiding bij de beschrijving van die colleges).

CXT bevat stof die iedere informaticus vanouds geacht wordt te kennen, maar ook wat specialistischer zaken zullen aan bod komen. Het is nl. een ³caputcollege², dat wil zeggen aan de hand van een aantal leuke en belangrijke onderwerpen worden allerlei belangrijke technieken en inzichten gepresenteerd en bestudeerd, zoals:

* Snelheid winnen ten koste van geheugenruimte;
* Wat ieder weten moet van polynomen (toep. o.m. in de cryptografie);
* leuke en slimme constructies van logische circuits;
* hoe ver kan ik een string samenpersen?
* ... etc...

Leerdoelen

Na het volgen van dit schone vak beheerst de student(e) een aantal belangrijke begrippen, trucs en algorithmen uit de complexiteitstheorie in aansluiting op de bekwaamheden verkregen in het collegeT2.

Beheersen wil zoals gebruikelijk zeggen: formuleringen van stellingenparaat hebben; de bewijzen qua structuur zo goed door hebben dat je (de docent overtuigt dat je) ze kunt reconstrueren; opgaven in de trant van de gebodene kunnen maken.

Meer specifiek betreft het de verwerving van kennis van en inzichtin onderwerpen zoals dan wel verwant aan die hierbeneden opgesomd.

Onderwerpen

aa

Hoofdthema¹s:

* Tabulaire methoden zoals dynamisch programmeren (toep. parseren,matrix- vermenigvuldigen, unair partitieprobleem,...);

* Polynoomarithmetiek waaronder SLP's, optimaliteit van het Hornerschema,en evaluatie en interpolatie met toepassing op cryptografische drempelschema's.

* Circuitcomplexiteit,

* Kolmogorowcomplexiteit,

Daarnaast als de tijd reikt nog enkele kleinere onderwerpen.

Toelichting

CXT gaat over de complexiteit van algorithmen, dus het kostenaspect: snelle programma¹s, indeling in klassen, boven- en ondergrenzen, berekeningsmodellen. Het bouwt voort op de colleges T2a en T2b(zie ook inleiding bij de beschrijving van die colleges).

CXT bevat stof die iedere informaticus vanouds geacht wordt te kennen, maar ook wat specialistischer zaken zullen aan bod komen. Het is nl. een ³caputcollege², dat wil zeggen aan de hand van een aantal leuke en belangrijke onderwerpen worden allerlei belangrijke technieken en inzichten gepresenteerd en bestudeerd, zoals:

* Snelheid winnen ten koste van geheugenruimte;
* Wat ieder weten moet van polynomen (toep. o.m. in de cryptografie);
* leuke en slimme constructies van logische circuits;
* hoe ver kan ik een string samenpersen?
* ... etc...

Werkvormen

Per week zijn er 2 uur hoorcollege (in het geval van weinig toehoorders van een wat minder formeel karakter) met wekelijkse opgaven.

Daarnaast twee gereserveerde begeleidingsuren op individuele basis,persoonlijk of via het internet.

Vereiste voorkennis

Het goed doorlopen hebben van de basiscolleges (II, WD1/2, Wk,Wl, T1, T2, WA, P2); speciaal T1 en T2.

Tentaminering


Het tentamen geschiedt in principe mondeling, of via een projectje.

Combinatiemogelijkheden

CXT is nuttig voor vakken in de sfeer van computeralgebra (afd. wiskunde) en telecommunicatie (ISDN) en voor wie wil afstuderen in de complexiteitstheorie.

Ook bevat CXT impliciet of expliciet algemene basiskennis en -vaardigheden van toepassing binnen de gehele informatica.

Het is mooi. Het is leuk.

Literatuur

Er is een dicktaat beschikbaar via het internet. Te vinden met verdere info over CXT via:

http://www.cs.kun.nl/~bolke/Teaching.html


Evaluatie: studentenquêtes ; geen docentevaluatie bekend Rendement: 10 begonnen, 8 echt meegedaan, 4 geslaagd met 1e kans, 1 geslaagd totaal
Q: