Zoek
English
  Studiegidsen 2012-2013
Radboud UniversiteitStudiegidsenFaculteit der Natuurwetenschappen, Wiskunde en Informatica > Bachelor Informatica en Informatiekunde

Analyse van algoritmen 

Vakcode
NWI-IBC013
Studiepunten
3
Periode
derde kwartaal
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
  • Complexiteit


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