Vereiste voorkennis
Bekendheid met bewijstechnieken als inductie en bewijs uit het ongerijmde. Voldoende wiskundige rijping en gezond verstand.
Toetsing
Twee tentamens (halverwege en aan het eind van de periode). Deze tellen allebei even zwaar mee bij de bepaling van het eindcijfer.
Daarnaast zijn er vijf sets van inleveropgaven. De uitslagen hiervan worden gemiddeld en tellen voor 20% voor het eindcijfer, indien dit het eindcijfer verhoogt.
|
|
|
De drie hoofdvragen in de combinatoriek zijn:
- Hoeveel oplossingen bestaan er (telprobleem)?
- Bestaat er een oplossing (beslissingsprobleem)?
- Welke is de beste oplossing (optimaliseringsprobeem)?
In 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.
Werkvorm
Hoorcolleges en werkcolleges.
Literatuur
F.S. Roberts en B. Tesman CRC Press (2009) Applied Combinatorics, 2nd edition ISBN: 9781420099829
Hetzelfde boek is eerder verschenen bij Prentice Hall (ISBN 9780130796035). De nieuwere editie bevat 40 bladzijden met antwoorden (en soms hele korte uitwerkingen) van geselecteerde opgaven.
|
 |
|