Studiegids

nl en

Complexiteit

Vak
2015-2016

Toegangseisen

eerstejaarscolleges informatica

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 zoeken/selectie/ sorteren, beslissingsbomen, adversary argument, optimaliteit, recursieve algoritmen en 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-hard, NP-volledigheid, reducties en de stelling van Cook zullen aan de orde komen.

Leerdoelen

Kennis en ervaring opdoen met de analyse van algoritmen, waaronder het
analyseren van de worst case complexiteit en een aantal technieken om
optimaliteit van algoritmen te bepalen. Er wordt geleerd om op een
kritische en analytische wijze naar problemen en algoritmen te kijken.
Verder wordt geleerd wat het betekent als een probleem NP-volledig is, en
hoe men NP-volledigheid kan bewijzen met behulp van reducties.

Rooster

Het meest recente rooster is te vinden op de LIACS website

Onderwijsvorm

Hoorcollege en werkgroep

Toetsing

  • Schriftelijk tentamen aan het eind van het semester

  • Enkele (5 of 6) huiswerkopgaven

  • Het eindcijfer wordt als volgt berekend: eindcijfer = 0,1 * gemiddeld huiswerkcijfer + 0,9 * tentamencijfer

Literatuur

Dictaat (reader) waarin ook opgaven zijn opgenomen

Aanmelden

Aanmelden via Usis: Selfservice > Studentencentrum > Inschrijven
Activiteitencodes te vinden via de facultaire website

Contact

Onderwijscoördinator Informatica, Riet Derogee

Website

Complexiteit