Prospectus

nl en

Complexity

Course
2019-2020

Toegangseisen

Niet van toepassing

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. Het college borduurt vorot op de eerstejaars colleges

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

  • Vier of 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