Studiegids

nl en

Discrete Besliskunde

Vak
2021-2022

Voorkennis

Combinatoriek en optimalisering

Omschrijving

Het vak Discrete besliskunde is één van de vier vakken die in Leiden het besliskundecurriculum vormen. Het behandelt een aantal onderwerpen uit het vakgebied dat in het Engels bekend staat als "discrete optimization" of "combinatorial optimization". De focus ligt op het algoritmisch benaderen van problemen, en op het bewijzen van de correctheid van de gegeven methoden. Er komt een selectie van de volgende onderwerpen aan de orde:

  1. Coöperatieve en non-coöperatieve speltheorie
  2. Grafentheorie (bomen, zoeken, Euler- en Hamiltongrafen)
  3. Netwerkoptimalisatie (kortste pad probleem, maximale flow probleem)
  4. Complexiteitstheorie (P vs. NP)
  5. Geheeltallige lineaire programmering
  6. Speciale lineaire modellen (transportprobleem, toewijzingsprobleem)
  7. Knapzakproblemen
  8. Schedulingproblemen

Voor veel van deze onderwerpen wordt basiskennis van de complexiteitstheorie en lineair programmeren als bekend verondersteld. In deze zin is het vak een vrij direct vervolg op het vak Combinatoriek en optimalisering. Voor verdere informatie over het besliskundecurriculum, zie website

Werkvorm

Wekelijks 4 uur hoorcollege

Toetsing

Het eindcijfer van het vak is opgebouwd uit twee delen, te weten:

  • praktische oefening: 6 huiswerkopgaven (25%)

  • schriftelijk (her-)tentamen (75%)
    Voor zowel de huiswerkopgaven gemiddeld als voor het (her-)tentamen moet ten minste een 5 behaald zijn om het vak te halen, en tenminste een onafgerond eindcijfer van 5,5.
    Voor deelname aan het (her-) tentamen is een huiswerkgemiddelde van minstens een 5 niet vereist

Literatuur

Collegedictaat. Dit is vanaf eind augustus 2021 beschikbaar om te downloaden van de webpagina van het vak. Ook zal het vanaf begin september 2021 in gedrukte vorm te koop zijn.

Extra informatie

De weekplanning is vanaf eind augustus 2021 te zien op de webpagina. Voor de cijferregistratie en het doen van belangrijke mededelingen wordt ook een Brightspacepagina gebruikt; ook hierover komt meer informatie beschikbaar op de webpagina.

Links

Website college