Fundamenten van de informatica
proefexamen 2003
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 je meestal de 5 kleurenstelling als "grote" theorie vraag.
in augustus vraagt die 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 --Stevel 7 jun 2006 08:09 (CEST)
Examenvraag 2004 juni & september - 2005 juni
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 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)