Planning
Op deze pagina komt te staan wat er op welk college behandeld wordt, en welke opgaven je wanneer moet maken.
| Week 1 | 7 februari | DFA's en reguliere talen (p. 31 – 47, slides). |
| 7 februari | Opgaven uit hoofdstuk 1: 1 – 6, 14a | |
| 9 februari | NFA's en reguliere expressies (p. 47 – 76, slides). | |
| Op dinsdag 14 februari 2012 moet inleveropgave 1 ingeleverd worden. Lees hiervoor «partiële en totale automaten». Het is van harte aanbevolen opgaven in LaTeX te schrijven. Hier een klein voorbeeld in LaTeX van een DFA, wat dit pdf-document geeft. | ||
| Week 2 | 14 februari | Myhill–Nerode stelling en Pomplemma (p. 77 – 82 en aantekeningen over de Myhill-Nerode stelling, slides). |
| 14 februari | Opgaven uit hoofdstuk 1: 14b, 15 – 19, 21, 29 en de extra opgaven uit de aantekeningen. | |
| 16 februari | Contextvrije Grammatica's, afsluitingseigenschappen en grammaticatransformaties (p. 101 – 111, slides). | |
| Op dinsdag 21 februari 2012 moet inleveropgave 2 ingeleverd worden. | ||
| Week 3 | 21 februari | Greibach normaalvorm en PDA's (p. 111 – 124, slides). |
| 21 februari | Let op, dit werkcollege duurt maar tot 15:45. Opgaven uit hoofdstuk 2: 1, 3, 4, 5, 6, 16, 8, 12-13, 18a, 25. | |
| 23 februari | Vervolg PDA's & voorbeelden Myhill-Nerode (p. 111 – 128 en aantekeningen over context-vrije talen, slides). | |
| Op dinsdag 28 februari 2012 moet inleveropgave 3 ingeleverd worden. | ||
| Week 4 | 28 februari | Introductie Turing machines (p. 137 – 147, slides). |
| 28 februari | Bespreken deeltoets 2010-2011 & (uitwerkingen) vragen over de stof dusver. Dat wil zeggen, alles wat behandeld is op de eerste zeven colleges en alles wat er bij hoort zoals aangegeven op de planning, behalve de inleiding tot Turing machines). | |
| 1 maart | Deeltoets: alle stof tot en met week 4. Vindt plaats in Drift 21, zaal 032 van 11:00 tot 13:00. | |
| Op dinsdag 6 maart 2012 moet inleveropgave 4 ingeleverd worden. | ||
| Week 5 | 6 maart | Turing machines & kleine aanpassingen; de Church–Turing these (p. 137 – 161, slides) |
| 6 maart | Opgaven uit hoofdstuk 3: 3, 6, 7, 8abc, 12, 15. | |
| 8 maart | Beslisbare talen (p. 167 – 172, slides). Bijbehorende opgaven van hoofdstuk 4: 2, 3, 5, 9, 10 en 12. | |
| Op dinsdag 13 maart 2012 moet inleveropgave 5 ingeleverd worden. | ||
| Week 6 | 13 maart | Onbeslisbare talen & reductie (p. 172 – 215, slides) |
| 13 maart | Opgaven uit hoofdstuk 5: 1, 4, 6-7 en 10. | |
| 15 maart | Meer over onbeslisbare talen & reductie (p. 172 – 215, slides). Bijbehorende opgaven uit hoofdstuk 5: 5.9, 5.12-13, 5.20, 5.23, 5.30. | |
| Op dinsdag 20 maart 2012 moet inleveropgave 6 ingeleverd worden. | ||
| Week 7 | 20 maart | Stelling van Rice & Tijdscomplexiteitsklassen (p. 249 – 275, slides) |
| 20 maart | Opgaven uit hoofdstuk 7: 1, 2 en 6. | |
| 22 maart | Tijdscomplexiteitsklassen, Reducties en NP-volledigheid. (p. 275 – 287, slides). Bijbehorende opgaven uit hoofdstuk 7: 7, 11, 14 en 17 | |
| Op dinsdag 27 maart 2012 moet inleveropgave 7 ingeleverd worden. | ||
| Week 8 | 27 maart | Stelling van Cook–Levin en meer over NP-volledigheid (p. 287 – 298, slides) |
| 27 maart | Opgaven uit hoofdstuk 7: 25, 7.27 en 28. | |
| 29 maart | Ruimtecomplexiteit en de stelling van Savitch (p. 307 – 319, slides). Opgaven uit hoofdstuk 8: 4, 6, 8, 11, 12. | |
| Op dinsdag 3 april 2012 moet inleveropgave 8 ingeleverd worden. | ||
| Week 9 | 3 april | Cryptografie (p. 405–411, slides) |
| 3 april | Alle eerdere opgaven, eindtoets vorig jaar. | |
| 5 april | Vragenuur. Mail uiterlijk 3 april middernacht vragen die je wilt bespreken. Let wel, begint om 09:00 in Drift 21 zaal 0.05. |
|
| Week 10 | 10 april | Eindtoets: alle stof. Vindt plaats in Achter de Dom, zaal 2.02 van 13:30 tot 16:30. Uitwerkingen hier |
| Week 15 | 15 mei | Herkansing: eerste deel, tweede deel of beide delen. Vindt plaats in Drift 21, zaal 1.05 van 17:00 tot 20:00. |