Discrete wiskunde

Website:

website met extra informatie

Vakcode:

INFOB3DW

Studiepunten:

7.5 ECTS

Periode:

periode 34 (week 6 t/m 27, dwz 4-2-2013 t/m 5-7-2013; herkansing week 34)

Timeslot:

Deelnemers:

tot nu toe 35 inschrijvingen

Rooster:

Let op: m.i.v. het collegejaar 2008/2009 is het rooster te vinden in Osiris

Docenten:

vorm	groep	tijd	week	zaal	docent
college		di 9.00-10.45	6-10	BBL-077	Han Hoogeveen
			6	BBL-083
			7-10	RUPPERT-B
			12-15	BBL-077
			12	RUPPERT-B
			13-15	BBL-083
			17	BBL-077
			17	BBL-169
			19-20	BBL-077
			19-20	BBL-169
			22-26	BBL-077
			22-26	BBL-169
			27	BBL-001
werkcollege					Han Hoogeveen Maarten Roelofsma
	groep 1	di 11.00-12.45	6-15	BBL-077
			17	BBL-077
			19-20	BBL-065
			22-23	BBL-065
			24	BBL-001
			25	BBL-065
			26	MIN-208

Inhoud:

Het eerste tentamen is gepland op dinsdag 16 april van 9.30-12.30. Er zijn twee zalen gereserveerd: BBL 0.83 en BBL 0.79 (we proberen eerst of BBL 0.83 groot genoeg is; zo niet, dan is BBL 0.79 beschikbaar als overloop).

Dit vak wordt door het departement Informatica verzorgd op verzoek van het departement Wiskunde. Het is een niveau 3 keuzevak bij Wiskunde; studenten Informatica kunnen het opvoeren in hun profileringsruimte. De inhoud van het vak is gewijzigd ten opzichte van vorig jaar: een gedeelte van de stof van vorig jaar (Latijnse vierkanten, block designs, coderingstheorie) is vervangen door stof die afgelopen jaar in het vak Combinatorische Optimalisatie (WISB376) zat.

Het is een semester-vak; er is 1 maal hoorcollege en 1 maal werkcollege per week, en dit twee perioden lang. Volgens de voorlopige planning staat het hoorcollege geroosterd op dinsdagochtend 9.00-10.45; het werkcollege staat geroosterd op dinsdagochtend 11.00-12.45.

Om het vak te halen moet je zowel de tussentoets aan het eind van periode 3 als de eindtoets aan het eind van periode 4 maken. Wanneer er iets mis gaat, dan kun je het hertentamen gebruiken om één of beide tussenresultaten te compenseren.

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 in periode 3:

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.

Inhoud in periode 4:

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:

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); 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 is zowel in periode 3 als in periode 4 een keer per week een hoorcollege van twee uur. Daarnaast is er een werkcollege, ook van twee uur in de week. In de eerste week is er geen werkcollege.

De tentamens zijn nog niet gepland. Ik ga mikken op dinsdagochtend, maar wanneer er (onverhoopt) een middag beschikbaar is waarop geen overlappende tentamens zijn gepland, dan neem ik die. Ik houd de standaard tentamenweken van Wiskunde aan (15-19 april en 25-29 juni).

Toetsvorm:

Toetsvormen: Na afloop van periode 3 en periode 4 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.

Het hertentamen is mondeling; dit kun je gebruiken om één of beide deeltentamens te herkansen (de vragen bij het mondeling hebben dan alleen betrekking op het deel dat je wilt herkansen). De berekening van het eindcijfer is dan als hierboven beschreven. 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:

Zie boven.

Beschrijving:

Zie inhoud.

wijzigen?