College Discrete Wiskunde

Inhoud 2012-2013

De inhoud van het vak Discrete Wiskunde is gelijk gebleven ten opzichte van vorig jaar. In de eerste helft van het tweede semester (periode 3) wordt gekeken naar het aantal mogelijke oplossingen (tellen). In de tweede helft van het tweede semester (periode 4) wordt, nadat de Polya theorie is behandeld, gekeken naar basisproblemen uit de Combinatorische Optimalisering. Voor een uitgebreid overzicht (inclusief korte beschrijving van de onderwerpen), zie Onderwerpen.

Overzicht colleges

De hoorcolleges en werkcolleges met bijbehorende tekst uit het boek staan in de onderstaande tabellen. Ik heb de hoorcolleges van de komende weken reeds ingepland; de werkcolleges van de komende weken komen zo snel mogelijk aan de beurt. In het algemeen zal het programma sterk lijken op dat van vorig jaar, maar ik wil misschien de werkcollege opgaven enigszins aanpassen. Ik heb de lijst met de hoorcolleges en werkcolleges van vorig jaar erbij gezet (voor het geval je vooruit wilt gaan werken). De inleveropgaven en enkele uitwerkingen heb ik even onbereikbaar gemaakt.

Nieuws

(15 mei): Op dinsdag 21 mei is er geen college in verband met de herexamens. Op dinsdag 28 mei is er geen hoorcollege. Het werkcollege gaat wel door. Op het programma staan nog wat opgaven over NP-volledigheid, en verder kun je aan Maarten ook vragen stellen over voorgaande werkcolleges (Hulde!).

(13 mei): Op dinsdag 14 mei wordt de vierde serie inleveropgaven uitgedeeld. De deadline is dinsdag 28 mei. Wie nieuwsgierig is kan deze serie reeds hier downloaden (ze stonden ook al op de werkcollege pagina).

(6 mei): Op dinsdag 7 mei vindt het hoorcollege plaats in BBL 169 (als vanouds); voor het werkcollege verhuizen we naar BBL 065!

(3 mei): Nog even voor alle duidelijkheid: wie minder dan een vier heeft gescoord op het eerste tentamen kan wel deelnemen aan het hertentamen.

(3 mei): De derde serie inleveropgaven is nagekeken. De resultaten staan hier.

(1 mei): Het tentamen is nagekeken. Het behaalde aantal punten kun je hier vinden. Om je cijfer te vinden moet je door 4.5 delen (met (helaas Judith) een maximum van 10).

(23 april): De beoordeelde inleveropgaven zijn uitgedeeld bij het werkcollege. Het restant ligt op mijn kamer (BBL 507) te wachten totdat het wordt opgehaald.

(16 april): Het hoorcollege vindt vanaf nu plaats in BBL 169. Het werkcollege blijft zoals het was in BBL 0.77.

(16 april): De resultaten van de tweede serie inleveropgaven resultaten staan hier. Bij het volgende werkcollege wordt het werk uitgedeeld.

(10 april): Nogmaals de melding van 12 maart: 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).

(9 april): Nogmaals voor alle duidelijkheid: bij het tentamen gaat het vooral om inzicht en het toe kunnen passen van de opgedane kennis. De stellingen over inclusie-exclusie en het uitgebreide binomium van Newton komen op het tentamen te staan (ongeacht of je ze nodig hebt). Maak vooral duidelijk hoe je aan een antwoord bent gekomen; het antwoord zelf is van ondergeschikt belang. Voor alle duidelijkheid kun je hier een oefententamen vinden met een combinatie van vragen van de tentamens van vorige jaren.

(9 april): Bij het werkcollege is de derde serie inleveropgaven uitgedeeld. De deadline is dinsdag 23 april (en dus niet 16 april) bij het begin van het werkcollege. De opgaven staan hier.

(9 april): De uitwerkingen van de tweede serie inleveropgaven staan hier. Er wordt geen enkele garantie verleend op de correctheid hiervan.

(2 april): Het tentamen gaat over de stof in hoofdstuk 2 (niet de secties 4,12,13,15,16,17,18,19; wel het duiventilprincipe en de laatjes van Dirichlet), hoofdstuk 5 (niet secties 6,7), en de hoofdstukken 6 en 7. Ook het oplossen van recurrente betrekking met de JBF-methode en de particuliere oplossing, en met de sommatie-factor methode kan op het tentamen worden gevraagd. Het niveau van de tentamenopgaven ligt op het niveau van de gemakkelijkere inleveropgaven (maar het zijn geen inkoppertjes en iedereen claimt altijd dat een net gemaakt tentamen altijd veel moeilijker is dan een oud tentamen, zelfs wanneer alleen de volgorde van de vragen is veranderd).

(2 april): Voor alle duidelijkheid: op 9 april is er zowel een hoor- als een werkcollege.

(19 maart): De tweede serie inleveropgaven staat op het web. De deadline is dinsdag 2 april bij aanvang van het werkcollege. Graag netjes, verzorgd werk inleveren (met een nietje).

(19 maart): Komende dinsdag zitten we in BBL 0.83.

(19 maart): Maarten heeft de eerste serie inleveropgaven nagekeken. De resultaten staan hier. Het werk is uitgedeeld bij het werkcollege; wie het nog niet heeft teruggekregen kan het bij mij op mijn kamer (BBL 5.07) op komen halen.

(12 maart): Komende dinsdag zitten we weer in Ruppert B.

(12 maart): 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).

(20 februari): De zoektocht naar boeken heeft al binnen een uur succes opgeleverd. Wie een boek wil lenen dan wil kopen van een oud-student kan dat aan mij doorgeven.

(19 februari): Ongeacht wat er gebruikelijk is bij andere vakken: het is de bedoeling dat je alleen aan de inleveropgaven werkt, en ze dus zelf ook maakt. Gezamenlijk overleggen is niet erg, maar dan moet je het resultaat daarvan zelf uitwerken (dat is dus wezenlijk anders dan werk overschrijven).

(15 februari): Dinsdag 19-2 wordt de eerste serie inleveropgaven on-line gezet. De uitwerkingen kun je uiterlijk 5 maart inleveren bij aanvang van het werkcollege.

(14 februari): Voor alle duidelijkheid: de komende weken vindt het hoorcollege plaats in Ruppert B van 9.00 tot 10.45. Om 11.00 uur gaan we door met werkcollege in BBL 0.77.

(11 februari): Voor alle duidelijkheid: morgenochtend om 9.00 uur beginnen we met hoorcollege in Ruppert B. Om 11.00 uur gaan we door met werkcollege in BBL 0.77.

Helaas, het is niet gelukt om een grotere zaal te vinden voor het werkcollege van 11.00-13.00. Dat betekent dat we in BBL 0.77 blijven. We moeten dan maar een paar tafels uit andere zalen lenen. Voor het vierde blok is er wel een andere zaal geregeld, maar we kijken eerst even aan hoe het nu gaat.

(5-2-2013) Het aangepaste zaalrooster staat op het web (en ook de oude zaal BBL 077 staat nog genoemd, maar dat is dus verleden tijd). De komende weken vindt het hoorcollege plaats in RUPPERT B (en niet in BBL 0.83 zoals ik eerder hier heb geschreven). Ik ben bezig om ook voor het werkcollege van 11.00 - 12.45 een grotere zaal te vinden.

(5-2-2013) Het is gelukt om een student-assistent te vinden. En niet zomaar iemand: Maarten Roelofsma gaat onder andere meehelpen bij de begeleiding bij het werkcollege.

Algemene informatie

De omvang van het vak bedraagt 7.5 studiepunten. Het is een semestervak, dat plaats vindt in de derde en vierde periode; er is 1 maal hoorcollege en 1 maal werkcollege per week, en dit twee perioden lang. 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.

Voor een uitgebreid overzicht (inclusief korte beschrijving van de onderwerpen), zie Onderwerpen.

Vereiste voorkennis: Bekendheid met bewijstechnieken als inductie en bewijs uit het ongerijmde. Bekendheid met reeksen, zoals de Taylor reeks. Op kunnen lossen van eenvoudige reeksen.

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.

Docenten

Dit jaar is de verantwoordelijke docent Han Hoogeveen (slam@cs.uu.nl, kamer 507 in het BBL, toestel 4089); hier kun je terecht met vragen, opmerkingen, klachten en loftuitingen. Het is nog onduidelijk of er een student-assistent komt.

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 (niet alle uitwerkingen zijn foutloos overigens).

Outline college

Stof uit het boek die tijdens college aan bod komt
Uit het boek worden behandeld de hoofdstukken 1, 2 en 5 t/m 8. Het boek is nogal uitgebreid; daarom behandel ik alleen de hoogtepunten (vooral bij H2 is dat het geval). De stof die ik over sla uit de bovenstaande hoofdstukken behoort WEL tot de tentamenstof. Verder behandel ik nog een deel van de stof uit de hoofdstukken 12 en 13; daar heb ik samenvattingen van. Verder komt er nog wat op het web te staan over het oplossen van recurrente betrekkingen; ook dat hoort bij de tentamenstof.