De drie hoofdvragen in de combinatoriek zijn:
-
Hoeveel oplossingen bestaan er (telprobleem)?
-
Bestaat er een oplossing (beslissingsprobleem)?
-
Welke is de beste oplossing (optimaliseringsprobeem)?
Bij deze cursus zullen voornamelijk de eerste en de derde vraag aan bod komen. Hierbij komen ook de benodigde technieken aan bod.
Inhoud:
-
Basisregels voor het tellen van het aantal mogelijkheden
-
Genererende functies
-
Opstellen en oplossen van recurrente betrekkingen.
-
Tellen met behulp van de techniek van Inclusion/Exclusion.
-
PĆ³lya theorie.
-
Dynamische programmering;
-
Kortste pad en minimale opspannende boom;
-
Matching en toewijzingsproblemen;
-
Max flow en min cost max flow problemen;
-
Complexiteitstheorie.
Vereiste voorkennis: Bekendheid met bewijstechnieken als inductie en bewijs uit het ongerijmde. Voldoende wiskundige rijping en gezond verstand.
|
|