Studiegids

nl en

Complexiteit

Vak
2009-2010

Beschrijving

In dit college wordt de complexiteit van algoritmen bekeken: dit is het aantal elementaire stappen dat een algoritme nodig heeft om het onderhavige probleem op te lossen. We onderscheiden worst case, average case en best case complexiteit. Enkele te behandelen onderwerpen zijn: O-notatie, algoritmen voor selectie/sorteren, beslissingsbomen, adversary argument, optimaliteit, recurrente betrekkingen, polynoomevaluatie, graafproblemen. We zullen zien dat er voor veel problemen een polynominaal algoritme bestaat. Er zijn evenwel ook problemen (waaronder bijvoorbeeld het handelsreizigersprobleem) die echt moeilijk zijn: de NP-volledige problemen. Ook NP, NP-volledigheid en reducties zullen aan de orde komen.

Methode

hoorcollege en werkgroep

Examinering

schriftelijk

Voorkennis

eerstejaarscolleges informatica

Literatuur

dictaat (reader) waarin ook opgaven zijn opgenomen

Website

Complexiteit