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