Studiegids

nl en

Complexiteit

Vak
2017-2018

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

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 Studenten-website:

Onderwijsvorm

hoorcollege en werkgroep

Toetsing

-• Schriftelijk tentamen aan het eind van het semester

  • Vijf huiswerkopgaven

  • Het gemiddeld huiswerkcijfer telt mee als bonus indien het tentamencijfer >= 5,0 is.

  • Het eindcijfer wordt dan als volgt berekend:
    als (tentamencijfer >= 5,0): eindcijfer = tentamencijfer + (gemiddeld huiswerkcijfer ) / 10
    als (tentamencijfer < 5,0): eindcijfer = tentamencijfer

Literatuur

dictaat (reader) waarin ook opgaven zijn opgenomen

Aanmelden

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

Voor studenten die niet staan ingeschreven voor de bachelor Informatica is er een beperkte capaciteit. Neem contact op met de studieadviseur.

Contact

Onderwijscoördinator Informatica, Riet Derogee

Website

Complexiteit