Discrete Structuren 2009-2010

Deze pagina wordt regelmatig bijgewerkt: raadpleeg altijd de meest recente versie.

Versie 22-3-2010

Inhoud

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.

Cursusmateriaal

We gebruiken het boek Discrete Mathematical Structures (6th edition) van Kolman Busby Ross (Prentice-Hall, 2009, ISBN 0132078450), maar het boek van de cursus van vorig jaar, Discrete Mathematics van Ross en Wright is ook nog bruikbaar.

Cursusopzet

Per week is er 2 x 2 uur hoorcollege en 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 voor het werkcollege en het huiswerk worden op de webpagina bekend gemaakt. 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. Het maken van de huiswerkopgaven is verplicht en de uitwerkingen worden beoordeeld en tellen voor 20% in het eindcijfer mee.
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 (donderdag 11 maart, 9.00 - 11.00 uur) over de stof van de eerste vier weken. Een voldoende toetsresultaat geeft vrijstelling voor de eerste helft van het tentamen in april. Doel van de deeltoets is je te laten zien wat er op het tentamen van je verwacht wordt.

Voor wie nog wil nakijken hoe vorig jaar de stof was opgezet, is hier de hoofdpagina met verwijzingen naar de slides en ander materiaal. De slides geven een samenvatting van de stof van het oude boek.

Weekrooster

In het weekrooster staat de planning van deze cursus: welke leerstof aan de orde is, wat het huiswerk is en welke opgaven tijdens het werkcollege aan de orde zullen komen.

Week 1 (maandag 8 februari - woensdag 10 februari 2010)

Leerstof: Hoofdstuk 1 (Fundamentals). Een verzameling van diverse elementaire onderwerpen: verzamelingenleer (vereniging, doorsnede, machtsverzameling, product, Venn-diagrammen), functies (domein en beeld, compositie, injectie, surjectie, bijectie), relaties, grafen en equivalentierelaties.

Er is een handout van het maandagcollege en het woensdagcollege.

Opgaven:

Hier zijn de opgaven voor het werkcollege voor donderdag 11 februari.

En de huiswerkopgaven voor maandag 15 februari. Enkele opmerkingen n.a.v. opmerkingen van Stefan e.a.:

1.2.44: een streep boven een verzamelingen-expressie is een complement (i.p.v. superscript c)

1.3.29: Beide boeken voorzien in voldoende uitleg van de karakteristieke functie.

5.1.22: Beide boeken gebruiken een Amerikaanse terminologie voor soorten functies: onto = surjectief; one-to-one = injectief; one-to-one-correspondence= bijectief

Verder geldt: injectief + surjectief = bijectief en bijectief is een noodzakelijke en voldoende voorwaarde voor het bestaan van een inverse functie: f^{-1} (x) = y is per definitie waar dan en slechts dan als f(y) = x

5.1.32: foutje: f o g moet zijn: g o f

Week 2 (maandag 15 februari - woensdag 17 februari 2010)

Er is een handout van het maandagcollege en het woensdagcollege.

Hier zijn de opgaven voor het werkcollege voor donderdag 18 februari.

En de huiswerkopgaven voor maandag 22 februari.

Bij opgave 4.5.15 moet je zelf de relatie definieren, maar je moet dan nog wel laten zien dat het een quivalentie-relatie is.

Zie voor aanvullende informatie voor opgave RW4.3.1-2 (o.a. een formele definitie), de slides van vorig jaar van week 3.

RW4.2.7 wordt vanwege het irrelevante rekenwerk geheel vervangen door twee leerzamere sommen:

RW4.2.7.a wordt: Bewijs dat n^2 > n+1 voor alle n>= 2.

RW4.2.7.b wordt: Als p(n) = ''n^2 + 5n + 1 is even'' bewijs dat: p(k) => p(k +1) voor alle positieve gehele getallen. Voor welke getallen is p(n) eigenlijk waar?

Week 3 (maandag 22 februari - woensdag 24 februari 2010)

De handout van het maandagcollege en het woensdagcollege.

En de opgaven voor het werkcollege voor donderdag 25 februari.

Met de huiswerkopgaven voor maandag 1 maart.

Week 4 (maandag 1 maart - woensdag 3 maart 2010)

De handout van het maandagcollege en het woensdagcollege.

En de opgaven voor het werkcollege voor donderdag 4 maart.

Met de huiswerkopgaven voor maandag 8 maart.

Week 5 (maandag 8 maart - woensdag 10 maart 2010)

Deze week een deeltoets over de stof van de eerste 4 weken op donderdag 11 maart.

De handout van het maandagcollege en het college van donderdag.

Op het werkcollege van woensdag 10 maart wordt het huiswerk van week 3 en week 4 besproken.

Week 6 (maandag 15 maart - woensdag 17 maart 2010)

De handout van het maandagcollege met paragraaf 4 en het college van donderdag.

En de opgaven voor het werkcollege voor donderdag 18 maart.

Met de huiswerkopgaven voor maandag 22 maart.

Week 7 (maandag 22 maart - woensdag 23 maart 2010)

De handout van het maandagcollege met oefeningen voor het woensdagcollege.

Week 8,9 (maandag 29 maart - woensdag 7 april)

Voorbereiden op het tentamen: 15 april. Het tententamen wordt nabesproken op 27 april van 11.15 tot 12.00 uur
p.dykstra@rug.nl