Discrete Wiskunde voor Informatici, najaar 2002

Het vak is afgeschaft!

Het college Discrete Wiskunde voor Informatici is in het najaar van 2002 voor het laatst gegeven. Een deel van de stof zal (wellicht) in andere colleges binnen de opleiding Informatica terugkomen. Hoe dan ook, de afschaffing betekent dat het hertentamen op donderdag 14 augustus 2003 het laatste reguliere tentamen Discrete Wiskunde voor Informatici was.
Omdat er veel studenten waren die het vak ook na dit tentamen nog niet gehaald hadden, is er op donderdag 4 december 2003 een allerlaatste hertentamen georganiseerd.

Laatste hertentamen nagekeken

Het laatste hertentamen van 4 december 2003 is nagekeken. De cijfers zijn dus bekend. Ze zijn inmiddels definitief.
Zoals bijna gewoon hebben alle studenten een half punt cadeau gekregen. U vindt de resulterende cijfers hier. Mocht u uw studentnummer vergeten zijn, dan vindt u de resultaten ook aan de deur van Rudy's werkkamer, kamer 150, inclusief studentnamen. Bij Rudy kun je ook je eigen uitwerkingen ophalen (graag zelfs!).

Tentamenstof en alternatief

Even voor de goede orde:

tot en met het collegejaar 2001-2002 bevatte het vak Discrete Wiskunde voor Informatici niet het onderwerp complexiteit (maar wel enkele andere onderwerpen)
in het collegejaar 2002-2003 werd het vak feitelijk Discrete Wiskunde met een beetje complexiteit
het nieuwe vak Complexiteit van komend voorjaar wordt feitelijk complexiteit met een beetje (of wat meer) discrete wiskunde.

Bij het laatste herkansingstentamen waren er twee versies: een versie zonder complexiteit (Versie 1) en een versie met complexiteit (Versie 2). De beide versies waren hetzelfde, op één som na. Tijdens het tentamen kon men nog kiezen welke versie men wilde doen. Voor meer details over de twee versies, zie verderop.

Wat als je het vak niet gehaald hebt

Navraag bij de studieadviseur heeft ons geleerd dat mensen die het vak nog niet gehaald hebben, nu het vak Complexiteit (in het voorjaarssemester) moeten doen. Dat vak is `equivalent' met Discrete Wiskunde voor Informatici, dat wil zeggen: je mag de vakken tegen elkaar uitruilen.
Ook als je niet van het onderwerp complexiteit houdt, hoeft het geen ramp te zijn dat je dit nieuwe vak moet doen: het onderwerp complexiteit zal wat geleidelijker worden opgebouwd dan dat dat in het najaar van 2002 is gebeurd. Misschien begrijp je het dan wel beter dan je nu gedaan hebt, en kun je het vak Complexiteit makkelijker halen dan Discrete Wiskunde voor Informatici (al dan niet met een beetje complexiteit).

Tentamenstof najaar 2002 (Versie 2 van het laatste herkansingstentamen)

Tot de tentamenstof behoort:

alles wat op hoorcollege en werkcollege is behandeld;
de theorie en opgaven in het dictaat (zie beneden bij Materiaal), voor zover niet expliciet uitgesloten;
de theorie en opgaven over complexiteit in de uitgedeelde kopieën (zie beneden bij Materiaal).

Voor wie niet alles precies heeft opgeschreven, volgt hier een overzicht van de onderwerpen / gedeeltes die je in ieder geval moet kennen:

Paragraaf 1 uit het dictaat: Definities en voorbeelden (van grafen);
Paragraaf 2 uit het dictaat: Ketens en kringen, behalve Stelling 2.2 en Gevolg 2.3;
Paragraaf 3 uit het dictaat: Euler grafen;
Paragraaf 4 uit het dictaat: Hamilton grafen;
Paragraaf 5 uit het dictaat: Bomen;
Paragraaf 6 uit het dictaat: Vlakke grafen en duale grafen, behalve
- het bewijs van Stelling 6.10,
- stappen 3-5 van het bewijs van Stelling 6.11.
Paragraaf 7 uit het dictaat: Rangschikkingen, permutaties en combinaties;
Paragraaf 8 uit het dictaat: Recurrente betrekkingen en voortbrengende functies, behalve
- het bewijs van Stelling 8.6,
- de theorie vanaf halverwege blz. 40 (waar staat: `Soms kunnen we voortbrengende ...'),
- opgave 5, opgaven 11-16;
Paragraaf 9 uit het dictaat: Het principe van inclusie en exclusie, behalve
- voorbeeld 9.13 vanaf halverwege blz. 55 (waar staat: `Ga na (zie opgave 11) ...'),
- opgave 11;
Paragraaf 10 uit het dictaat: De huwelijksstelling van Hall;
Paragraaf 11 uit het dictaat: Transversalen, behalve
- de partiële transversaal,
- Stelling 11.2 en Gevolg 11.3
- opgave 3
Paragraaf 12 uit het dictaat: Toepassingen van de huwelijksstelling van Hall
Complexiteit:
- rekenen met O(.),
- optimaliseringsproblemen en beslissingsproblemen,
- lengte van de invoer,
- (voorbeelden van) polynomiale problemen, P,
- (voorbeelden van) polynomiale reducties,
- (voorbeelden van) niet-deterministische (polynomiale) algoritmes, NP,
- (voorbeelden van) NP-volledige problemen, NPC, Hamilton probleem, handelsreizigersprobleem, SAT, 3-SAT, Kliek,
- (voorbeelden van) NP-harde problemen

Aan dit overzicht kunnen geen rechten worden ontleend.

Behalve toepassing van de theorie kan op het tentamen ook gevraagd worden om resultaten te bewijzen.

De specifieke Versie 2-som op het laatste herkansingstentamen zal gaan over complexiteit (dan weet je dat vast).

Tentamenstof Versie 1 van het laatste herkansingstentamen

De volledige tentamenstof voor Versie 1 ontstaat door de stof over Complexiteit te vervangen door de iets verderop genoemde onderwerpen.
Bij elkaar is dit in principe de stof zoals die in het najaar van 2001 in het avondcollege is behandeld door Christiaan van de Woestijne. Dit zal niet zoveel verschillen met de stof van najaar 2000 of eerder. Het kan wel verschillen met de stof van het dagcollege van najaar 2001 (door Roos). Christiaan heeft destijds een overzicht van de leerstof van toen gemaakt. Als extra service vindt u dit overzicht hier. Het is slechts aanvullende informatie voor het laatste herkansingstentamen.
De extra onderwerpen van Versie 1 ten opzichte van Versie 2 zijn:

Enumeratie (hoofdstuk III in het dictaat van vóór najaar 2002)
- Het tellen van grafen; multinomiaalcoefficient
- De stelling van Burnside
- De theorie van Polya
- Het tellen van niet-isomorfe grafen
Matroiden (de extra aantekeningen die Christiaan heeft uitgedeeld; dit komt grofweg overeen met Hoofdstuk V, paragraaf 18 en 20 in het dictaat van vóór najaar 2002)
- Definitie
- Voorbeelden
- Het gretige algoritme
Maximale stroom / minimale snede problemen, met het algoritme van Ford & Fulkerson (de extra aantekeningen die Christiaan heeft uitgedeeld)

Deze onderwerpen zijn inmiddels definitief.

De specifieke Versie 1-som op het tentamen gaat over een (of meer) van deze onderwerpen.

Materiaal

Aan het begin van het semester (najaar 2002) is natuurlijk al een dictaat met theorie en opgaven uitgekomen (Mag. uitgifte 505207). Daarnaast is in de laatste weken van het college het volgende materiaal uitgedeeld:

kopieën met theorie over complexiteit (blz. 548-570 uit Sara Baase & Allen van Gelder, Computer Algorithms, Introduction to Design & Analysis , Addison-Wesley, Reading, Massachusetts, derde editie, 1999);
twee A5-jes met opgaven bij de theorie over complexiteit;
aanwijzingen voor het oplossen van de opgaven uit het dictaat (EUR 1,--);
als oefening: twee tentamens van het vorige jaar, waarvan een met uitwerkingen; let op: opgave 3 van het tentamen van 17 januari 2002 en opgave 1 van het tentamen van 15 augustus 2002 behoren dit jaar niet tot de tentamenstof;
als oefening: geselecteerde tentamenopgaven en (vergelijkbaar moeilijke) huiswerkopgaven van twee jaar geleden; let op: opgave 2 van het tentamen van 16 augustus 2001 behoort dit jaar niet tot de tentamenstof.

Dit uitgedeelde materiaal is ook nu nog te verkrijgen bij Rudy van Vliet, kamer 150, tel. 071-5277050, rvvliet@liacs.nl.

Oefenen

Nu het laatste herkansingstentamen voorbij is, zul je niet meer voor een tentamen Discrete Wiskunde voor Informatici hoeven te oefenen. Je zou het nog wel voor de lol kunnen doen. Daarom vindt u hier de laatste drie tentamens van het vak: dat van 14 januari 2003, dat van 14 augustus 2003 en dat van 4 december 2003. Van het eerstgenoemde tentamen is ook de nette uitwerking beschikbaar. Mocht je fouten ontdekken in de uitwerking, dan houd ik me aanbevolen.

Vragen en/of opmerkingen kunnen worden gestuurd naar Rudy van Vliet: rvvliet@liacs.nl.

Laatste wijziging: 5 januari 2004 - http://www.liacs.nl/home/rvvliet/discwisk02.html