Inleiding
Voor veel praktische problemen zijn efficiente algoritmen ontwikkeld, zoals voor het zoeken, opslaan en verwijderen van gegevens in rood-zwart-bomen. Al deze acties kunnen in logaritmische tijd uitgevoerd worden; daar zijn deze rood-zwart-bomen voor uitgevonden. Dit resultaat is van groot belang bij allerlei vormen van het bijhouden van grote hoeveelheden gegevens. Hoe dergelijke algoritmen eruit zien is bij "Algoritmen en Datastructuren" al aan de orde gekomen, en hoe je formele afschattingen van efficientie kunt formuleren en bewijzen is bij "Complexiteit" behandeld. In dit vak "Analyse van Algoritmen" komen beide invalshoeken samen: we zullen allerlei algoritmen bekijken en daarvan de efficientie analyseren. Daarnaast komen diverse nieuwe algoritmen aan de orde.
|
Leerdoelen
Na afloop van de cursus kan de student de efficientie analyseren van diverse algoritmen en heeft zijn/haar kennis van algoritmen uitgebreid.
|
Onderwerpen
Onderwerpen: - Ontwerp van algoritmen en analyse van de efficientie.
- Kennismaking met nieuwe algoritmen die gebruik maken van geavanceerde datastructuren, en de analyse daarvan.
- Lineair programmeren.
- Getaltheoretische algoritmen.
- Geometrische algoritmen.
- NP compleetheid.
|
Studielastverdeling
- 16 uur hoorcollege
- 16 uur werkcollege
- 52 uur zelfstudie
|
Toelichting werkvormen
Gedurende een half semester is er wekelijks een hoorcollege en een werkcollege.
|
Toetsvorm
Dit vak wordt afgesloten met een schriftelijk tentamen. Het is een 'gesloten boek' tentamen, dat wil zeggen dat er geen meegebracht materiaal (boeken, aantekeningen) bij gebruikt mogen worden.
|
Vereiste voorkennis
- Algoritmen en Datastructuren
|
Literatuur
Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, MIT Press, Third Edition, 2009 Dit is hetzelfde boek dat ook bij beide voorkennisvakken wordt gebruikt
|
Website
http://www.win.tue.nl/~hzantema/aa.html
|