I00030: Formeel Denken

Docenten

Stof

Het dictaat staat als pdf file op deze web pagina. Op het college wordt het dictaat ook als fotokopie in afleveringen uitgedeeld. De hoofdstukken van het dictaat zijn:

Propositielogica
Predicatenlogica
Talen
Combinatoriek
Automaten

Over ieder hoofdstuk zal een toets worden afgenomen (deze toetsen zijn niet verplicht, de beoordeling aan eind van de cursus is door middel van een tentamen.) De toetsen kunnen evenwel worden gebruikt om het eindcijfer te verbeteren, volgens de formule verder op deze pagina.

(HBO studenten die vorig seizoen al met hun schakelprogramma begonnen zijn maar Formeel Denken nog niet hebben afgerond, kunnen een aangepaste versie van de cursus doen die correspondeert met het voormalige I00133. Neem voor de details hiervan contact op met één van de docenten.)

Rooster

De coördinaten van de cursus zijn:

Zowel op dinsdag als op woensdag wordt een combinatie van hoorcollege en werkcollege gegeven. De toetsen duren altijd drie kwartier (op dinsdag 14.45-15.30 en op woensdag 11.45-12.30), en worden voorafgegaan door werkcollege.

datum hoorcollege werkcollege toets
19 september 1.1, 1.2, 1.3 1: 1-3
20 september 1.4 1: 9
26 september 1.5 1: 14-15
27 september 1.6, 1.7 1: 17-18, 20
3 oktober toets 1
4 oktober 2.1 2: 1-2
10 oktober 2.2 2: 6, 11-17
11 oktober 2.3 2: 19-21
17 oktober vakantie
18 oktober vakantie
24 oktober 2.4, 2.5 2: 27
25 oktober 2.6 2: 28
31 oktober toets 2
1 november 3.1 3: 6, 8
7 november 3.2 3: 11, 13-14
8 november 3.3 3: 20-22
14 november 3.4, 3.5 3: 27-29
15 november toets 3
21 november 4 graphen 4: 1-3, 5-6
22 november 4 graphen 4: 4, 7-9
28 november 4 recursie 4: 1-2
29 november 4 inductie 4: 3-6
5 december toets 4
6 december 5 5: 3
12 december 5.1 5: 5, 7, 10-15
13 december 5.2 5: 19, 20, 22, 24
19 december 5.3 5: 27-28
20 december toets 5
9 januari
 		 inhaaltoets
14.45-15.30
22 januari
 
 		 vragenuurtje
13.45-14.30
HG00.062

(Deze tabel wordt gedurende het semester eventueel aangepast naar de laatste inzichten.)

Beoordeling

Het eindcijfer is

max(tentamen, (gemiddelde van de vijf beste toetsen + tentamen)/2)

Zowel de toetsen als het tentamen zijn "gesloten boek". De inhaaltoets is ook toegankelijk voor studenten die alle andere toetsen hebben gedaan (in dat geval vervalt het laagste toetscijfer.)

Een fotootje van het college

[FD 2006]

De prijsvraag

Halverwege het college werd er een kleine prijsvraag gehouden (de prijs: een bus pepernoten). De opdracht was om als eerste een reguliere expressie te vinden voor de taal:

{ w ∈ {a,b}* | w bevat een even aantal a's en een oneven aantal b's }

De prijsvraag werd op de valreep gewonnen door Dennis Aarts met de reguliere expressie:

a((ab U ba)(aa U bb)*(ab U ba) U aa U bb)*(ab U ba)((ab U ba)(aa U bb)*(ab U ba) U aa U bb)* U b((ab U ba)(aa U bb)*(ab U ba) U aa U bb)*

Voor het beoordelen van de inzendingen van deze wedstrijd had ik een klein ocaml programmaatje gemaakt om reguliere expressies en eindige automaten naar elkaar te converteren. Dat programmaatje leidde me naar de oplossing

(a(bb)*a)*(b U ab(bb)*a)(a(bb)*a U (b U ab(bb)*a)(a(bb)*a)*(b U ab(bb)*a))*

die wel korter, maar ook minder mooi is. (Mochten er bugs in het programmaatje zitten dan hoor ik het graag.)

Tenslotte leverde nog wat langer nadenken de nóg kortere reguliere expressie, die gebaseerd is op Dennis' oplossing:

(a(aa U bb)*(ab U ba) U b)((ab U ba)(aa U bb)*(ab U ba) U aa U bb)*

De torens van Hanoi

Hier is het C programmaatje uit het college over de torens van Hanoi, voor wie het zelf wil proberen.

Uitwerkingen

Toetsen en Tentamens

Toetsen en tentamens van dit jaar

Toetsen en tentamens van vorig jaar

Toetsen en tentamens van eervorig jaar

Nog oudere toetsen

En een nóg oudere toets