SluitenHelpPrint
Switch to English
Cursus: INFOB3DW
INFOB3DW
Discrete wiskunde
Cursus informatie
CursuscodeINFOB3DW
Studiepunten (EC)7,5
Inhoud
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.
SluitenHelpPrint
Switch to English