NWI-IBC028
Complexiteit
Cursus informatieRooster
CursusNWI-IBC028
Studiepunten (ECTS)3
CategorieBA (Bachelor)
VoertaalEngels, Nederlands
Aangeboden doorRadboud Universiteit; Faculteit der Natuurwetenschappen, Wiskunde en Informatica; Informatica en Informatiekunde;
Docenten
Docent
G.X. Allais, MSc
Overige cursussen docent
Docent
dr. M.C. de Bondt
Overige cursussen docent
Contactpersoon van de cursus
prof. dr. H. Zantema
Overige cursussen docent
Docent
prof. dr. H. Zantema
Overige cursussen docent
Coördinator
prof. dr. H. Zantema
Overige cursussen docent
Collegejaar2017
Periode
KW3  (05-02-2018 t/m 15-04-2018)
Aanvangsblok
KW3
Onderwijsvorm
voltijd
OpmerkingVoertaal Nederlands tenzij Engels noodzakelijk is.
Inschrijven via OSIRISJa
Inschrijven voor bijvakkersJa
VoorinschrijvingNee
WachtlijstNee
Plaatsingsprocedure-
Cursusdoelen
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.
Inhoud
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, in het bijzonder door het analyseren van de onderliggende recurrente betrekkingen. 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.

Toetsinformatie
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.

Voorkennis
NWI-IBC027 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 het voorkennisvak wordt gebruikt.

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

Toelichting werkvormen: Gedurende een half semester is er wekelijks een hoorcollege en een werkcollege.

Verplicht materiaal
Boek
Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, MIT Press, Third Edition, 2009. Van materiaal buiten dit boek is een eigen dictaat beschikbaar.

Werkvormen
Cursus
AanwezigheidsplichtJa

Hoorcollege
AanwezigheidsplichtJa

Werkcollege
AanwezigheidsplichtJa

Zelfstudie

Toetsen
Tentamen
Weging1
GelegenhedenBlok KW3, Blok KW4