Complexiteit

Werkvormen

  • 16 uur hoorcollege
  • 16 uur werkcollege
  • 52 uur zelfstudie

Toelichting werkvormen

Gedurende een half semester is er wekelijks een hoorcollege en een werkcollege.

Vereiste voorkennis

NWI-IBC027 Algoritmen en Datastructuren

Leerdoelen

Na afloop van de cursus kan de student de efficiëntie analyseren van diverse algoritmen en is in staat NP-compleetheid van diverse problemen te bewijzen.

Inleiding

Complexiteit gaat over de efficiëntie van algoritmen. Aan de ene kant worden voor concrete algoritmen methoden gepresenteerd waarmee deze efficiëntie kan worden vastgesteld. Aan de andere kant wordt voor diverse problemen aannemelijk gemaakt dat er geen efficiënte algoritmen voor bestaan door te laten zien dat ze NP-volledig zijn.

Onderwerpen

Onderwerpen:

  • Analyse van de efficiëntie van algoritmen.
  • Master methode voor divide and conquer.
  • Kennismaking met nieuwe algoritmen waarin die analyse een rol speelt, in het bijzonder geometrische algoritmen.
  • De klassen P en NP.
  • SAT als basis van NP-volledigheid.
  • Voorbeelden van bewijzen van NP-volledigheid.

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.

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 het voorkennisvak wordt gebruikt

Website


Vakcode
NWI-IBC028
Studiepunten
3 ec
Periode
vierde kwartaal
Collegerooster opvragen
SWS / PersoonlijkRooster

Docent

Opgenomen in

  • Bachelor Informatica