Versie 6-2-2006 (tentamentijd verbeterd, zie onderaan de pagina)
Kennismaking met begrippen uit de discrete wiskunde en de logica die in de informatica veel gebruikt worden. Verwerven van inzicht en vaardigheid in het gebruik hiervan. In dit vak worden de volgende begrippen behandeld: verzamelingen, relaties, functies, grafen, rijen, ordeningen. Tevens wordt de predikatenlogica geintroduceerd, die gebruikt wordt om een en ander met de vereiste precisie te beschrijven.
We gebruiken het boek Discrete Mathematics (5th edition) van Kenneth A. Ross en Charles R.B. Wright (Prentice-Hall, 2003, ISBN 0-13-065247-4). (De 4de editie van dit boek is ook bruikbaar: zie de lijst van opgaven in de 4de druk voor de juiste nummers van de huiswerk- en werkcollegeopgaven.)
Een degelijk wiskundeboek, speciaal geschreven voor studenten Informatica. De stof wordt uitgebreid behandeld en met veel voorbeelden toegelicht. Het boek bevat 13 hoofdstukken, onderverdeeld in 67 secties. Elke sectie wordt afgesloten met ca. 20 opgaven (exercises): de uitkomsten van de oneven opgaven staan achter in het boek. Verder wordt elk hoofdstuk afgesloten met een korte samenvatting van de belangrijkste begrippen en resultaten, en een aantal aanvullende opgaven (met uitwerkingen achterin het boek). In de cursus Discrete Structuren wordt ongeveer 2/3 van de inhoud van het boek behandeld.
Verder is er een kleine aanvullende syllabus van 7 pagina's. De inhoud daarvan sluit aan bij de hoofdstukken 2 en 13 van het boek. Het gaat hier over een bepaalde stijl voor het opschrijven van bewijzen (Geannoteerde Lineaire Bewijzen, GLB's) die in andere cursussen gebruikt wordt, en om een aantal aanvullende bewijsregels voor de propositie- en de predikatenlogica.
Per week is er 2 x 2 uur hoorcollege en 2 x 2 uur werkcollege. Zie verder het rooster.
Tijdens het hoorcollege wordt aan de hand van het cursusmateriaal een overzicht van de leerstof gegeven. De nadruk ligt op de grote lijnen, niet op de details: die komen bij zelfstudie en werkcollege aan de orde.
Tijdens het werkcollege maak je opgaven over de behandelde stof. Zoals voor alle wiskunde geldt ook voor dit vak dat je het meeste leert van het maken van opgaven. Alle opgaven (en veel uitwerkingen) staan in het cursusmateriaal. De werkcollegedocent is er om je te helpen bij het maken van de opgaven.
Daarnaast is er zelfstudie. Gebruik die om de leerstof grondig door
te nemen en de huiswerkopgaven te maken. Vragen over de huiswerkopgaven kun je
tijdens het werkcollege aan de werkcollegedocent stellen. Je kunt hem ook
uitwerkingen van opgaven geven, die kijkt hij dan voor je na.
Tip: bekijk de avond voor het hoorcollege de te behandelen stof, dan weet
je wat er komen gaat en steek je er meer van op.
In de vijfde week van de cursus is er een deeltoets (vrijdag 16 december, 14.00 - 16.00 uur, Examenhal) over de inhoud van de eerste vier hoofdstukken. Een voldoende toetsresultaat geeft vrijstelling voor de eerste helft van het tentamen in februari. Doel van de deeltoets is je te laten zien wat er op het tentamen van je verwacht wordt.
Leerstof: Chapter 1 (Sets, Sequences and Functions). Een verzameling van diverse elementaire onderwerpen: getaltheorie (floor en ceiling, priemgetallen, deelbaarheid), verzamelingenleer (vereniging, doorsnede, machtsverzameling, product, Venn-diagrammen), functies (domein en beeld, compositie, injectie, surjectie, bijectie).
Opgaven:
In dit hoofdstuk wordt ook veel aandacht besteed aan het bedenken en opschrijven van bewijzen. Voor bewijzen in de propositielogica hanteren we een vast formaat, het geannoteerde lineaire bewijs (GLB) dat in de aanvullende syllabus behandeld wordt. Later, in hoofdstuk 4, behandelen we een ander formaat: bewijzen met inductie. Daarnaast besteden we in hoofdstuk 2 ook aandacht aan bewijzen in het algemeen, los van een vast formaat. Dit gebeurt vooral in sectie 2.3 (Getting Started with Proofs). Werk 2.3 zelf door en maak daarbij de huiswerk-opgaven (1,2,3,4,5,7). Houd daarbij voor ogen wat het doel is van een bewijs: de kritische lezer of toehoorder overtuigen van de geldigheid van een (wiskundige) uitspraak. Als voorbeeld hier een voorbeeld van een bewijs uit het ongerijmde.
Opgaven:
Verder nog twee andere puzzels die met behulp van grafen kunnen worden opgelost. De tweede is wat lastiger dan de eerste: het antwoord is te vinden in het boek op p. 323 (p. 463 in de 4e editie).
Opgaven:
(p -> (p -> q)) <=> (p -> q) (p & (q -> r)) <=> ((p -> q) -> (p & r)) (p <-> q) <=> ((p & q) v (-p & -q))
Verder het welordeningsprincipe, een fundamentele eigenschap van N, de verzameling van natuurlijke getallen. Uit het welordeningsprincipe volgt het principe van (volledige) inductie. Als puzzels ditmaal twee paradoxen mbt. inductie, en de puzzel van de gevangenen.
Opgaven:
Verder deze week alleen werkcollege op maandag 12 december, verder geen onderwijs voor dit vak.
Deeltoetsen van vorige jaren: deeltoets van 2003 en deeltoets van 2004.
De leerstof voor de deeltoets:
Deze week Chapters 6 en 8, over grafen, voortbouwend over hetgeen daarover in Chapter 3 al aan de orde is geweest. Chapter 6 gaat over ongerichte grafen. Onderwerpen zijn: paden en cykels in een graaf, isomorfie van grafen, de graad (degree) van een knoop, de stelling van Euler over Eulercircuits, bomen (trees) en opspannende bomen (spanning trees). Gerichte grafen komen aan de orde in Chapter 8, waarvan wij alleen 8.1 en 8.2 behandelen. De belangrijkste begrippen zijn: ingraad (indegree) en uitgraad, bron (source) en afvoer (sink), gesorteerde labeling van de knopen, kortste pad, kritiek pad.
Verder een puzzel voor de vakantie: het Monty Hall dilemma.
Opgaven:
Opgaven:
Opgaven:
De leerstof: