Fundamenten van de informatica

Bestand:Dereadt.jpg‎

Inleiding

Dit is op zijn minst gezegd een stevig vak, vooral omdat dit nogal wiskundig geïnspireerd is. Het examen is schriftelijk, dus je hoeft ook prof. Demoen ook niet te confronteren. Het examen bestaat uit 2 gedeeltes met daartussen een pauze die langer is als je sneller klaar ben met het eerste deel. Eerst krijg je 2 uur om de theorie op te lossen. Dit gedeelte is uiteraard gesloten boek. Eens dat gedaan is mag je buiten wat van het zonnetje gaan genieten, en als het tijd is mag je er weer invliegen voor maximaal 2 uurtjes voor de oefeningen. Dit gedeelte is open boek, maar dat maakt voor de oefeningen totaal geen verschil (tenzij je een formule vergeten bent, en ze nog heel goed weet staan). Mijn ervaring was dat je voor het eerste deel heel veel tijd over hebt, maar dat je voor het tweede deel hard moet doorwerken. Zorg dat je zeker niks meer moet gaan zoeken in je cursus, want daar heb je geen tijd voor. Voorbeelden van theorievragen zitten bij de examenvragen, en ze gaan over alle mogelijke delen van de cursus. Geen enkele vraag heeft meer/minder kans dan een andere om te verschijnen op het examen. Dat betekent dat je dus vrij veel bewijzen zult moeten kunnen, dus het is van belang dat je ze goed begrijpt, want ze allemaal louter vanbuiten leren zorgt er gegarandeerd voor dat je alles doorheen slaat op het examen. Het theoriegedeelte begint altijd met een hoop meerkeuzevraagjes (met het multiple-choice-puntentellings-systeem...) waarvan het niet noodzakelijk is dat er exact 1 antwoord juist is (desnoods zijn ze allemaal juist, of soms zelfs geen enkel, en soms sommige...). Bij de oefeningen zit soms een oefening op combinatoriek, meestal een oefening op complexiteit, zeker 1 of meerdere oefeningen op grafentheorie en soms een vraag op vastepuntstheorie. Binnen elk van deze onderdelen heeft elk soort oefening evenveel kans om op het examen te verschijnen. De oefeningen vereisen bijna altijd een heel goed inzicht in de leerstof. Oefeningen over grafen zijn bijna altijd voorgesteld als een soort raadseltjes met een concrete situatie of een verhaaltje. Jij moet dan op een creatieve manier grafen aanwenden om het probleem op te lossen.

Onder het jaar zijn er ook 2 tussentijdse toetsen op theorie. Het is zeker interessant om deze voor te bereiden en daaraan deel te nemen. De helft van zo'n tussentijdse toets bestaat uit meerkeuzevragen en daar durven er wel eens terug van op het examen komen.

verandering vakinhoud

Tot 2004 had de cursus 2 extra hoofdstukken: recursievergelijkingen oplossen met reeksen, en lambdacalculus. Schrik dus niet indien er onbegrijpelijke examenvragen tussen oude examens staan. Het hoofdstuk van complexiteit is uitgebreid sinds 2004.

Tot en met 2006 gaf een andere prof dit vak.

Examenvragen

11/06/07

Beschouw een vlakke, enkelvoudige en samenhangende graaf waarin elke knoop graad 3 heeft. Elk vlak in deze graaf heeft ofwel 5 ofwel 6 aangrenzende bogen. Zoek het aantal vlakken met 5 aangrenzende bogen (antwoord = 12)

theorievragen (van vorige prof)

voorbeelden theorievragen

16/06/06

Theorie (van vorige prof)

1. Eerst waren er twee paginas met allerlei meerkeuzevragen, een beetje zoals op de tussentijdse toets, waarbij je telkens de juiste mogelijkheden moest aanduiden. Dit konden er een, twee, maar ook allemaal of geen zijn. Voor voorbeelden, zie oude tussentijdse toetsen.
2. Geef een algoritme om een minimaal opspannende boom van een graaf te vinden. Bewijs de eindigheid en correctheid ervan. Bespreek de context/precondities.
3. Zijn volgende stellingen juist of onjuist? Bewijs de juiste, geef een tegenvoorbeeld voor de onjuiste (of bewijs dat ze niet juist zijn).Gegeven een reguliere taal L.
   • als $A\subset L$, dan is A regulier.
   • als $L\subset A$, dan is A regulier.
   • als A regulier, dan is $A\cap L$ regulier.
   • als A regulier, dan is $A\cup L$ regulier.

Oefeningen

1. Stel $G_N$ is een graaf die aan de volgende eigenschappen voldoet:
   • $G_N$ is vlak, enkelvoudig en samenhangend.
   • Elk zijvlak van $G_N$ grenst aan exact N bogen.
   • Exact de helft van de knopen van $G_N$ heeft graad 3, de andere helft heeft graad 4.
   1. Bereken een functie die het aantal knopen in functie van N geeft, of toon aan dat er geen $G_N$ kan bestaan.
2. De twee andere oefeingen waren een niet-deterministische eindige automaat (+ geef expliciet de delta-relatie uit de definitie), en een min cut-max flow oefening, alletwee vrij standaard.

Examenvraag 2004 juni & september - 2005 juni (van vorige prof)

Toon aan dat de klasse P de unie is van drie equivalentieklassen voor de relatie ~ (polynomiale equivalentie), namelijk vand e klassen:

(a) P1: tot deze klasse behoren alle talen L op een alfabet T die voldoen aan L = T*

(b) P2: tot deze klasse behoren alle lege talen op een alfabet T. D.w.z. L = {leeg}.

(c) P3: De enige interesante klasse bestaande uit talen L op een alfabet T zodat L niet leeg is en L is ook niet T*

Bewijs staat in http://www.cs.kuleuven.be/~bmd/FVI/oefeningen_all.pdf pagina 18. Deze vraag wordt niet op dezelfde manier gesteld maar in een practische variant ervan, het bewijs moet je dan gewoon aanpassen met de gegeven variabelen in de vraagstelling. Deze vraag wordt zo goed als 100% zeker gesteld. Kleurenbewijs en min-max zijn ook goeie kanshebbers voor de andere vragen!

Voor de oefeningen mag je rekenen op een doenbare automaat en een netwerkmodel waar je dan de maximale stroming van moet berekenen voor alle bogen en een minimale snede tekenen, een bijvraag is dan bijvoorbeeld of het de enige minimale snede is. Het netwerk ziet er uit als een Ruit met een diagonaal(negatieve boog). Zie ook dat je hier je bewijzen goed onder de knie hebt want de derde praktijkvraag is bewijs: <een ongeziene stelling> die je moet afleiden uit andere bewijzen(ni simpel)

proefexamen 2003 (van vorige prof)

Bewijs volgende stelling : de eigenschap dat 1 taal polynomiaal in een andere transformeerbaar is is transitief. Leg de stelling eerst wat uit en bewijs ze dan.

In juni vraagt men meestal de 5 kleurenstelling als "grote" theorie vraag.
in augustus vraagt men meestal dat algoritme om het netwerk volledig "efficient" te gebruiken (ik weet niet meer hoe het noemt, ik dacht dat dat het laatste algoritme van de grafen theorie was).

• was dat niet iets met min-cut/max-flow