Department of Information and Computing Sciences

Departement Informatica Onderwijs
Bachelor Informatica Informatiekunde Kunstmatige intelligentie Master Computing Science Game&Media Technology Artifical Intelligence Business Informatics

Onderwijs Informatica en Informatiekunde

Vak-informatie Informatica en Informatiekunde

Discrete wiskunde

Website:website met extra informatie
Vakcode:INFOB3DW
Studiepunten:7.5 ECTS
Periode:periode 3 (week 6 t/m 15, d.w.z. 5-2-2018 t/m 13-4-2018; herkansing week 27)
Timeslot:B
Deelnemers:tot nu toe 0 inschrijvingen
Rooster:De officiële roosters staan ook in Osiris
Docenten:
vormgroeptijdweekzaaldocent
college   di 9.00-10.456-14 - Han Hoogeveen
 
do 13.15-15.006-9 -
11-14 -
werkcollege groep 1        Marieke van der Wegen
  
Tentamen:
week: 10do 8-3-201813.30-16.30 uurzaal: -
week: 15do 12-4-201813.30-16.30 uurzaal: -
week: 27do 5-7-201813.30-16.30 uurzaal: -aanvullende toets
Nota bene:Er is geen recente vakbeschrijving beschikbaar.
Onderstaande tekst is een oude vakbeschrijving uit collegejaar 2016/2017
Inhoud:

Waarschuwing: Hoewel ik natuurlijk geen potentiële klanten wil wegjagen wil ik er wel op wijzen dat het vak behoorlijk pittig zal zijn voor studenten die weinig wiskunde zijn gewend ook al is er geen tot weinig voorkennis nodig. Kijk bijv. even bij de werkcollege opgaven (of bij de inleveropgaven, maar die zijn pittiger).

Dit vak wordt door het departement Informatica verzorgd op verzoek van het departement Wiskunde. Het is zowel bij Wiskunde als bij Informatica een niveau 3 keuzevak.

Om het vak te halen moet je zowel de tussentoets in het midden van periode 3 als de eindtoets aan het eind van periode 3 maken. Wanneer er iets mis gaat, dan kun je het hertentamen gebruiken om één of beide deelresultaten te compenseren. Afhankelijk van het aantal herkansers is er een mondeling of een schriftelijk hertentamen. Verder zijn er nog inleveropgaven.

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.
Literatuur:Kan veranderen!
F.S. Roberts en B. Tesman CRC Press (2009) Applied Combinatorics, 2nd edition ISBN: 9781420099829 Dit boek kun je onder andere bij de webshop van A-Eskwadraat bestellen (https://aeskwadraat.itdepartment.nl/home). Hetzelfde boek is eerder verschenen bij Prentice Hall (ISBN 9780130796035); dit is nog verkrijgbaar bij een aantal boekensites. De inhoud van dit boek is volledig gelijk aan de inhoud van het nieuwe boek, maar het nieuwe boek bevat nog 40 bladzijden met antwoorden (en soms hele korte uitwerkingen) van geselecteerde opgaven.
Werkvorm:Er zijn twee hoorcolleges van twee uur elk en twee werkcolleges, ook van twee uur elk, in de week.
Toetsvorm:Toetsvormen: Ongeveer middenin en aan het eind van periode 3 zijn er deeltentamens; 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.

Afhankelijk van het aantal herkansers is er een mondeling dan wel een schriftelijk hertentamen. Je kunt kiezen of je het eerste, tweede, of beide tentamens wilt herkansen. De score van de inleveropgaven telt niet meer mee bij de berekening van het eindcijfer na herkansing. Volgens de regels van de faculteit mag je alleen deelnemen wanneer je een 4 hebt gehaald, maar die regel hanteer ik soepel.

Inspanningsverplichting voor aanvullende toets:Om aan de aanvullende toets te mogen meedoen moet de oorspronkelijke uitslag minstens 4 zijn.
Beschrijving:Zie inhoud...
wijzigen?