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
Online hoorcolleges via Kaltura
Zelfstudie met het dictaat i.p.v. werkcollege
Toetsing
Schriftelijk tentamen aan het eind van het semester
Vier 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
Contact
Docent: Lieuwe Vinkhuijzen (Skype: lieuwe.vinkhuijzen1)
Email contact met docent en assistenten: complexiteitleiden@gmail.com
Onderwijscoördinator Informatica, Riet Derogee