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. Luc De Raedt ook niet te confronteren. Het examen bestaat uit 2 gedeeltes met daartussen een korte pauze als je dat wenst. Eerst krijg je enkele theorievragen voorgeschoteld (gesloten boek). Als je die hebt opgelost moet je dat deel afgeven, en mag je even naar toilet of zo. Daarna krijg je een aantal oefeningen, open boek (alleen cursus met aantekeningen, geen opgeloste oefeningen, geen kopies van anderen). Het examen duurt maximaal 4 uur in totaal: je tijdsverdeling mag je zelf kiezen.

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.

Professor Demoen (vorige prof) liet het theoriegedeelte altijd beginnen 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...). Professor De Raedt lijkt zelf een grote fan van het type vragen"Waar of niet waar en verklaar kort".

(Nog over de vorige prof:) 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.

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

Theorie

1. Definieer de klassen P, NP, NPC, en definieer ook het begrip polynomiale transformatie op een taal. Hierbij mag je veronderstellen dat dat begrippen zoals taal, turingmachine en complexiteit gekend zijn. Stel de relaties tussen P, NP en NPC grafisch voor en geef een beetje uitleg (max. 1/2 blz). Leg ook uit waarom deze relatie zo belangrijk is.
2. Beschouw en bewijs de stelling van Hall (de relatie R en de stelling zelf zijn gegeven).
3. Waar of niet waar? Geef een korte verklaring (max. 2 regels)

Oefeningen

1. 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).
2. Is de volgende uitspraak waar (en argumenteer met een bewijs of tegenvoorbeeld)? De taal L wordt herkend door de deterministische, eindige toestands automaat A. Als A een string s waarvan lengte(s) > |Q| (=het aantal toestanden van de automaat A) herkent, dan is L oneindig.

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