Fundamenten van de informatica: verschil tussen versies

Ga naar: navigatie, zoeken
(lkCKyRuG)
Regel 1: Regel 1:
  http://www.adventure-traveling.com/ cheap tickets 5214 http://www.word-web-design.com/car_insurance_quotes.html car insurance quotes 6929 http://www.oldstylelist.com/ cheapest car insurance 576629 http://www.blogofascists.com/ car insurance zkcov
+
[[Afbeelding:BartDemoen.jpg|right|200px|]]
 +
 
 +
 
 +
== Inleiding ==
 +
Update: In 2010 werd het vak gedoceerd door professor Blockeel. De cursus bleef echter dezelfde en ook aan de examenvorm is weinig veranderd.
 +
 
 +
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
 +
 
 +
== Examenvragen ==
 +
 
 +
=== Juni 2010 ===
 +
 
 +
We kregen 3 uur voor het hele examen, je mocht zelf kiezen wanneer je met de oefeningen begon.
 +
 
 +
====Theorie====
 +
 
 +
# Meerkeuzevragen
 +
# Bewijs: Een samenhangende graaf zonder kringen en met n knopen heeft n-1 bogen.
 +
 
 +
====Oefeningen====
 +
 
 +
# Gegeven: een niet-deterministische eindige automaat met 3 toestanden.
 +
## Welke taal wordt door deze taal aanvaardt?
 +
## Geef een reguliere uitdrukking voor deze taal.
 +
## Geef een deterministische eindige automaat die dezelfde taal herkent.
 +
# Een cactusgraaf is een samenhangende graaf met de eigenschap dat twee kringen nooit meer dan een knoop gemeenschappelijk hebben. Een voorbeeld: [[Afbeelding:Cactusgraaf.png]]
 +
## Voor welke k geldt er dat elke cactusgraaf een k-kleuring heeft?
 +
## Voor welke cactusgrafen bestaat er een 2-kleuring? Geef voor elke vraag eerst het antwoord en leg dan uit hoe je tot dit resultaat bent gekomen.
 +
# Gegeven: Een spelboom. Pas het minimax-algoritme met alpha/beta-snoeien toe. Duid duidelijk aan welke knopen er door alpha/beta-snedes niet berekend moeten worden.
 +
 
 +
=== Augustus 2009 ===
 +
 
 +
====Theorie====
 +
 
 +
# meerkeuzevragen, bijna letterlijk overgenomen uit zowel proefexamen als juni-examen.
 +
# Vraag over polynomiale transformaties. ik weet de exacte vraagstelling niet meer maar hier een poging: Er zijn 2 talen A en B die beiden polynomiaal en niet leeg zijn. Bewijs dat de volgende uitspraken niet correct zijn:
 +
## A is polynomiaal transformeerbaar naar {} (de lege verzameling dus)
 +
## {} is polynomiaal transformeerbaar naar B
 +
## A is polynomiaal transformeerbaar naar B
 +
# Geef het algoritme van Dijkstra inclusief context en precondities. Bewijs de eindigheid en correctheid. Je mag ook een eigen algoritme & bewijs geven.
 +
# Geef de definitie van een gerichte deelverzameling in een complete tralie. Heeft deze definitie zin op een niet complete tralie (enkel ja antwoorden is niet voldoende, moet ook verantwoord worden)? Geef een voorbeeld van een gerichte deelverzameling. Geef een voorbeeld van een niet gerichte deelverzameling.
 +
 
 +
====Oefeningen====
 +
 
 +
# (vraag van het proefexamen...)
 +
# Geef de grafische weergave van een niet-deterministisch automaat die de taal over {a,b} gegeven door de reguliere expressie (a*b*) | (b*a*) | (ab)* (Hierbij zijn de haakjes gewoon voor de duidelijkheid geplaatst).
 +
# Gegeven is onderstaand netwerk. Constueer een maximale stroming en minimale snede. Is deze minimale snede uniek? Is er maar één manier om deze maximale stroming te verwezenlijken?
 +
 
 +
[[Afbeelding:Netwerk examen fundamenten.png|500px]]
 +
 
 +
=== Juni 2009 ===
 +
Hij heeft waarschijnlijk bijna letterlijk het examen van 16/06/06 hernomen.
 +
====Theorie====
 +
# 2 pagina's meerkeuzevragen ==> "copy-paste" van het Proefexamen!!!!
 +
# We beschouwen twee talen A en B over {a,b}. De taal A bestaat enkel uit de string aa en B bevat bb, maar aa niet, en voor de rest een aantal andere strings die niet gegeven zijn. Verder is gegeven dat B een P-taal is. Toon aan dat A ook in de klasse P zit. Toon ook aan dat B polynomiaal in A transformeert door een algemene constructie van een Turing Machine te geven die de functie uit de polynomiale transformatie berekent.
 +
# Geef een algoritme voor het vinden van een minimaal opspannende boom. Bewijs correctheid en eindigheid (Kies zelf welk algoritme je geeft - het mag zelfs een eigen variatie zijn - maar bewijs al je uitspraken zonder verwijzingen naar andere algoritmes.) en geef context/preconditie.
 +
# Definieer het begrip gerichte deelverzameling van een complete tralie. Heeft deze definitie ook zin voor niet-complete tralies? (Leg uit!) Geef een voorbeeld van een gerichte deelverzameling en een niet-gerichte deelverzameling. Vergeet de beschouwde tralie(s) niet te vermelden!
 +
 
 +
====Oefeningen====
 +
# Bepaal voor elk natuurlijk getal N of er een graaf <math>G_N</math> bestaat (en indien ja, geef het aantal knopen in functie van N), met de volgende eigenschappen:
 +
#*<math>G_N</math> is vlak, enkelvoudig en samenhangend.
 +
#*Elk zijvlak van <math>G_N</math> grenst aan exact ''N'' bogen.
 +
#*Exact de helft van de knopen van <math>G_N</math> heeft graad 3, de andere helft heeft graad 4.
 +
#**(Oplossing: enkel <math>G_4</math> bestaat en deze heeft 16 knopen.)
 +
# Geef een grafische weergave van een niet-deterministische automaat die de taal over {a,b} gegeven door de regeliere expressie (a*b) | (ab*) | ba beslist. (Hierbij zijn de haakjes gewoon voor de duidelijkheid geplaatst.) Geef ook de transitie-afbeelding (in formulevorm) horende bij deze automaat.
 +
# Gegeven is onderstaand netwerk. Constueer een maximale stroming en minimale snede. Is deze minimale snede uniek? Is er maar één manier om deze maximale stroming te verwezenlijken?
 +
 
 +
[[Afbeelding:Netwerk examen fundamenten.png|500px]]
 +
 
 +
=== Juni 2008 ===
 +
====Theorie====
 +
# Bewijs dat de taal <math>L=\{0^n1^n|n\in\mathbb{N}\}</math> niet regulier is.
 +
 
 +
#
 +
## Geef de definitie van een polynomiale transformatie
 +
## Bewijs: Als <math>L_1 \propto L_2</math> en <math>L_2 \in P</math> dan <math>L_1 \in P</math>.
 +
# Een hoop kleine vraagjes over <math>K_n</math> en <math>K_{n,m}</math> en nog een hoop kleine vraagjes over vanalles en nog wat. (Huwelijk, vlakheid van een graaf, SAT (NP/P/NPC?))
 +
# Geef de drie invariante eigenschappen die nodig zijn om de correctheid van het algoritme van Dijkstra te bewijzen.
 +
 
 +
====Oefeningen====
 +
# Een oefening op een minimale boom (vergelijkbaar met de oefening over de nieuwe spoorwegen). Leg je stappen uit.
 +
# We definiëren de omtrek <math>o </math> van een graaf als het aantal bogen in de kleinst mogelijke kring. Bewijs dat voor een samenhangende, enkelvoudige, vlakke graaf met <math>e\geq 3 </math> en minstens één kring de volgende formule geldt: <math>e\leq \frac{o}{o-2}(v-2) </math>
 +
# Stroming van netwerken: Is het mogelijk om voor elke boog een minimale stroming in te stellen ? Stel dat dit altijd mogelijk zou zijn, wat kan je dan zeggen over MaxFlow, vertrekkende van Stelling 4.2.7.
 +
# Er is een niet deterministische automaat gegeven; Geef de bijhorende reguliere expressie en geef een deterministische versie van deze automaat.
 +
 
 +
=== Augustus 2007 ===
 +
==== Theorie ====
 +
# Geef de definitie van een deterministische Turingmachine en een niet-deterministische Turing-machine.
 +
# Definitie: voor een gewogen graaf G is T een maximaal opspannende boom indien T een opspannende boom van G is met het grootste gewicht. Specifieer een algoritme om de maximale opspannende boom van een samenhangende gewogen grafe te vinden. Vertrek hierbij van het algoritme van Primm. Argumenteer (bewijs) dat het algoritme correct is.
 +
# Beschouw de volgende uitspraken & geef aan of ze waar of niet waar zijn. Geef ook aan waarom (max. 2 zinnen).
 +
##er bestaat een Turingberekenbare functie <math>f: \mathbb{N} \rightarrow \mathbb{N}</math>
 +
##er bestaat een samenhangende graaf waarvoor <math>e > 3v-6</math>
 +
##in <math>\mathbb{N},|</math> zijn er oneindig veel bovengrenzen voor <math>\{2,3\}</math>
 +
##als TSP <math>\not\in</math> P dan SAT <math>\not\in</math> P
 +
##doorsnede van 2 reguliere talen is regulier
 +
##de unie van twee reguliere talen is regulier
 +
##als F een algoritme is O(f), G een algoritme is van O(g) en f is O(g) dan is F sneller op elke invoer dan G
 +
##de graaf <math>K_6</math> is vlak
 +
##als een taal recursief opsombaar is, dan is ze recursief
 +
#Geef de definitie van een complete tralie. Definieer ook de onderliggende begrippen.
 +
===11/06/07 ===
 +
==== Theorie ====
 +
# 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.
 +
# Beschouw en bewijs de stelling van Hall (de relatie R en de stelling zelf zijn gegeven).
 +
# Waar of niet waar?  Geef een korte verklaring (max. 2 regels)
 +
## <math> \mathbb{N}, \leq</math> is een complete tralie
 +
## SAT <math>\in</math> P
 +
## Als TSP <math>\in</math> P geldt ook SAT <math>\in</math> P.
 +
## Is de taal <math>L_1 = \{0^n 1^n | n \in \mathbb{N} \} </math> een reguliere taal?
 +
## Is de taal <math>L_2 = \{0^n 1^m | n,m \in \mathbb{N} \} </math> een reguliere taal?
 +
## Zijn <math>L_1</math> en <math>L_2</math> Turing berekenbaar?
 +
## Heeft elke enkelvoudige graaf een 5-kleuring?
 +
## Een graaf T is een boom als T samenhangend is en kringloos
 +
## Kunnen we een rij natuurlijk getallen <math>\mathbf{a} = (a_1, a_2, \cdots, a_n) </math> coderen als een natuurlijk getal <math>g(\mathbf{a})</math> zodat we uit later nog kunnen decoderen en de rij natuurlijke getallen construeren uit <math>g(\mathbf{a})</math>?
 +
 
 +
==== Oefeningen ====
 +
# We beschouwen een spelboom [[Afbeelding:Fundamenten oefening 1.JPG]] en veronderstellen dat max = Doos aan zet is. 
 +
## Pas de minimax-procedure toe op de spelboom.
 +
## Welke takken worden door het alpha-beta-algoritme weggesnoeid?
 +
## Wat is de best mogelijke zet voor max?
 +
# Is de volgende uitspraak waar (en argumenteer met een bewijs of tegenvoorbeeld)? ''De taal L wordt herkend door de deterministische, eindige toestandsautomaat A. Als A een string s waarvan lengte(s) > |Q| (=het aantal toestanden van de automaat A) herkent, dan bevat de taal L(A) een oneindig aantal strings.
 +
# We beschouwen de verzameling 'fullerenen'.  Een voorbeeld: [[Afbeelding:Fundamenten oefening 2.JPG]]  Dit zijn enkelvoudige, vlakke, samenhangende grafen waarvan elke knoop graad 3 heeft en elk vlak in deze graaf heeft ofwel 5 ofwel 6 aangrenzende bogen. Zoek het aantal vlakken met 5 aangrenzende bogen en bewijs je antwoord. (antwoord = 12)
 +
# Definieer een taal L = {<math> s \in \{a,b\}^* | </math> s bevat ofwel geen a's ofwel exact 2 a's }
 +
## Definieer een deterministische eindige toestandsautomaat die L aanvaardt en stel deze grafisch voor.
 +
## Definieer L ook via een reguliere expressie.
 +
# Zoek de maximale stroming voor onderstaand transportnetwerk (duidt de stroming aan bij elke boog). Duidt ook de minimale snede aan.  Bestaat er meer dan één minimale snede voor dit netwerk?  Bestaat er meer dan één manier om de maximale stroming te verwezenlijken?  (Ja of neen is niet voldoende: geef alternatieven of een tegenvoorbeeld.[[Afbeelding:Fundamenten oefening 3.JPG]]
 +
 
 +
=== theorievragen (van vorige prof) ===
 +
[[Media:Theorie.pdf|voorbeelden theorievragen]]
 +
===16/06/06 ===
 +
==== Theorie (van vorige prof) ====
 +
#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.
 +
#Geef een algoritme om een minimaal opspannende boom van een graaf te vinden. Bewijs de eindigheid en correctheid ervan. Bespreek de context/precondities.
 +
#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 <math>A \subset L</math>, dan is A regulier.
 +
#*als <math>L \subset A</math>, dan is A regulier.
 +
#*als A regulier, dan is <math>A \cap L</math> regulier.
 +
#*als A regulier, dan is <math>A \cup L</math> regulier.
 +
 
 +
==== Oefeningen ====
 +
#Stel <math>G_N</math> is een graaf die aan de volgende eigenschappen voldoet:
 +
#*<math>G_N</math> is vlak, enkelvoudig en samenhangend.
 +
#*Elk zijvlak van <math>G_N</math> grenst aan exact ''N'' bogen.
 +
#*Exact de helft van de knopen van <math>G_N</math> heeft graad 3, de andere helft heeft graad 4.
 +
##Bereken een functie die het aantal knopen in functie van ''N'' geeft, of toon aan dat er geen <math>G_N</math> kan bestaan.
 +
#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.<br>
 +
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
 +
 
 +
[[Categorie:2bw]]
 +
[[Categorie:1bi]]
 +
[[Categorie:Aoi]]

Versie van 27 mrt 2011 om 17:23

BartDemoen.jpg


Inleiding

Update: In 2010 werd het vak gedoceerd door professor Blockeel. De cursus bleef echter dezelfde en ook aan de examenvorm is weinig veranderd.

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

Examenvragen

Juni 2010

We kregen 3 uur voor het hele examen, je mocht zelf kiezen wanneer je met de oefeningen begon.

Theorie

  1. Meerkeuzevragen
  2. Bewijs: Een samenhangende graaf zonder kringen en met n knopen heeft n-1 bogen.

Oefeningen

  1. Gegeven: een niet-deterministische eindige automaat met 3 toestanden.
    1. Welke taal wordt door deze taal aanvaardt?
    2. Geef een reguliere uitdrukking voor deze taal.
    3. Geef een deterministische eindige automaat die dezelfde taal herkent.
  2. Een cactusgraaf is een samenhangende graaf met de eigenschap dat twee kringen nooit meer dan een knoop gemeenschappelijk hebben. Een voorbeeld: Cactusgraaf.png
    1. Voor welke k geldt er dat elke cactusgraaf een k-kleuring heeft?
    2. Voor welke cactusgrafen bestaat er een 2-kleuring? Geef voor elke vraag eerst het antwoord en leg dan uit hoe je tot dit resultaat bent gekomen.
  3. Gegeven: Een spelboom. Pas het minimax-algoritme met alpha/beta-snoeien toe. Duid duidelijk aan welke knopen er door alpha/beta-snedes niet berekend moeten worden.

Augustus 2009

Theorie

  1. meerkeuzevragen, bijna letterlijk overgenomen uit zowel proefexamen als juni-examen.
  2. Vraag over polynomiale transformaties. ik weet de exacte vraagstelling niet meer maar hier een poging: Er zijn 2 talen A en B die beiden polynomiaal en niet leeg zijn. Bewijs dat de volgende uitspraken niet correct zijn:
    1. A is polynomiaal transformeerbaar naar {} (de lege verzameling dus)
    2. {} is polynomiaal transformeerbaar naar B
    3. A is polynomiaal transformeerbaar naar B
  3. Geef het algoritme van Dijkstra inclusief context en precondities. Bewijs de eindigheid en correctheid. Je mag ook een eigen algoritme & bewijs geven.
  4. Geef de definitie van een gerichte deelverzameling in een complete tralie. Heeft deze definitie zin op een niet complete tralie (enkel ja antwoorden is niet voldoende, moet ook verantwoord worden)? Geef een voorbeeld van een gerichte deelverzameling. Geef een voorbeeld van een niet gerichte deelverzameling.

Oefeningen

  1. (vraag van het proefexamen...)
  2. Geef de grafische weergave van een niet-deterministisch automaat die de taal over {a,b} gegeven door de reguliere expressie (a*b*) | (b*a*) | (ab)* (Hierbij zijn de haakjes gewoon voor de duidelijkheid geplaatst).
  3. Gegeven is onderstaand netwerk. Constueer een maximale stroming en minimale snede. Is deze minimale snede uniek? Is er maar één manier om deze maximale stroming te verwezenlijken?

Netwerk examen fundamenten.png

Juni 2009

Hij heeft waarschijnlijk bijna letterlijk het examen van 16/06/06 hernomen.

Theorie

  1. 2 pagina's meerkeuzevragen ==> "copy-paste" van het Proefexamen!!!!
  2. We beschouwen twee talen A en B over {a,b}. De taal A bestaat enkel uit de string aa en B bevat bb, maar aa niet, en voor de rest een aantal andere strings die niet gegeven zijn. Verder is gegeven dat B een P-taal is. Toon aan dat A ook in de klasse P zit. Toon ook aan dat B polynomiaal in A transformeert door een algemene constructie van een Turing Machine te geven die de functie uit de polynomiale transformatie berekent.
  3. Geef een algoritme voor het vinden van een minimaal opspannende boom. Bewijs correctheid en eindigheid (Kies zelf welk algoritme je geeft - het mag zelfs een eigen variatie zijn - maar bewijs al je uitspraken zonder verwijzingen naar andere algoritmes.) en geef context/preconditie.
  4. Definieer het begrip gerichte deelverzameling van een complete tralie. Heeft deze definitie ook zin voor niet-complete tralies? (Leg uit!) Geef een voorbeeld van een gerichte deelverzameling en een niet-gerichte deelverzameling. Vergeet de beschouwde tralie(s) niet te vermelden!

Oefeningen

  1. Bepaal voor elk natuurlijk getal N of er een graaf bestaat (en indien ja, geef het aantal knopen in functie van N), met de volgende eigenschappen:
    • is vlak, enkelvoudig en samenhangend.
    • Elk zijvlak van grenst aan exact N bogen.
    • Exact de helft van de knopen van heeft graad 3, de andere helft heeft graad 4.
      • (Oplossing: enkel bestaat en deze heeft 16 knopen.)
  2. Geef een grafische weergave van een niet-deterministische automaat die de taal over {a,b} gegeven door de regeliere expressie (a*b) | (ab*) | ba beslist. (Hierbij zijn de haakjes gewoon voor de duidelijkheid geplaatst.) Geef ook de transitie-afbeelding (in formulevorm) horende bij deze automaat.
  3. Gegeven is onderstaand netwerk. Constueer een maximale stroming en minimale snede. Is deze minimale snede uniek? Is er maar één manier om deze maximale stroming te verwezenlijken?

Netwerk examen fundamenten.png

Juni 2008

Theorie

  1. Bewijs dat de taal niet regulier is.
    1. Geef de definitie van een polynomiale transformatie
    2. Bewijs: Als en dan .
  1. Een hoop kleine vraagjes over en en nog een hoop kleine vraagjes over vanalles en nog wat. (Huwelijk, vlakheid van een graaf, SAT (NP/P/NPC?))
  2. Geef de drie invariante eigenschappen die nodig zijn om de correctheid van het algoritme van Dijkstra te bewijzen.

Oefeningen

  1. Een oefening op een minimale boom (vergelijkbaar met de oefening over de nieuwe spoorwegen). Leg je stappen uit.
  2. We definiëren de omtrek van een graaf als het aantal bogen in de kleinst mogelijke kring. Bewijs dat voor een samenhangende, enkelvoudige, vlakke graaf met en minstens één kring de volgende formule geldt:
  3. Stroming van netwerken: Is het mogelijk om voor elke boog een minimale stroming in te stellen ? Stel dat dit altijd mogelijk zou zijn, wat kan je dan zeggen over MaxFlow, vertrekkende van Stelling 4.2.7.
  4. Er is een niet deterministische automaat gegeven; Geef de bijhorende reguliere expressie en geef een deterministische versie van deze automaat.

Augustus 2007

Theorie

  1. Geef de definitie van een deterministische Turingmachine en een niet-deterministische Turing-machine.
  2. Definitie: voor een gewogen graaf G is T een maximaal opspannende boom indien T een opspannende boom van G is met het grootste gewicht. Specifieer een algoritme om de maximale opspannende boom van een samenhangende gewogen grafe te vinden. Vertrek hierbij van het algoritme van Primm. Argumenteer (bewijs) dat het algoritme correct is.
  3. Beschouw de volgende uitspraken & geef aan of ze waar of niet waar zijn. Geef ook aan waarom (max. 2 zinnen).
    1. er bestaat een Turingberekenbare functie
    2. er bestaat een samenhangende graaf waarvoor
    3. in zijn er oneindig veel bovengrenzen voor
    4. als TSP P dan SAT P
    5. doorsnede van 2 reguliere talen is regulier
    6. de unie van twee reguliere talen is regulier
    7. als F een algoritme is O(f), G een algoritme is van O(g) en f is O(g) dan is F sneller op elke invoer dan G
    8. de graaf is vlak
    9. als een taal recursief opsombaar is, dan is ze recursief
  4. Geef de definitie van een complete tralie. Definieer ook de onderliggende begrippen.

11/06/07

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)
    1. is een complete tralie
    2. SAT P
    3. Als TSP P geldt ook SAT P.
    4. Is de taal een reguliere taal?
    5. Is de taal een reguliere taal?
    6. Zijn en Turing berekenbaar?
    7. Heeft elke enkelvoudige graaf een 5-kleuring?
    8. Een graaf T is een boom als T samenhangend is en kringloos
    9. Kunnen we een rij natuurlijk getallen coderen als een natuurlijk getal zodat we uit later nog kunnen decoderen en de rij natuurlijke getallen construeren uit ?

Oefeningen

  1. We beschouwen een spelboom Fundamenten oefening 1.JPG en veronderstellen dat max = Doos aan zet is.
    1. Pas de minimax-procedure toe op de spelboom.
    2. Welke takken worden door het alpha-beta-algoritme weggesnoeid?
    3. Wat is de best mogelijke zet voor max?
  2. Is de volgende uitspraak waar (en argumenteer met een bewijs of tegenvoorbeeld)? De taal L wordt herkend door de deterministische, eindige toestandsautomaat A. Als A een string s waarvan lengte(s) > |Q| (=het aantal toestanden van de automaat A) herkent, dan bevat de taal L(A) een oneindig aantal strings.
  3. We beschouwen de verzameling 'fullerenen'. Een voorbeeld: Fundamenten oefening 2.JPG Dit zijn enkelvoudige, vlakke, samenhangende grafen waarvan elke knoop graad 3 heeft en elk vlak in deze graaf heeft ofwel 5 ofwel 6 aangrenzende bogen. Zoek het aantal vlakken met 5 aangrenzende bogen en bewijs je antwoord. (antwoord = 12)
  4. Definieer een taal L = { s bevat ofwel geen a's ofwel exact 2 a's }
    1. Definieer een deterministische eindige toestandsautomaat die L aanvaardt en stel deze grafisch voor.
    2. Definieer L ook via een reguliere expressie.
  5. Zoek de maximale stroming voor onderstaand transportnetwerk (duidt de stroming aan bij elke boog). Duidt ook de minimale snede aan. Bestaat er meer dan één minimale snede voor dit netwerk? Bestaat er meer dan één manier om de maximale stroming te verwezenlijken? (Ja of neen is niet voldoende: geef alternatieven of een tegenvoorbeeld.Fundamenten oefening 3.JPG

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 , dan is A regulier.
    • als , dan is A regulier.
    • als A regulier, dan is regulier.
    • als A regulier, dan is regulier.

Oefeningen

  1. Stel is een graaf die aan de volgende eigenschappen voldoet:
    • is vlak, enkelvoudig en samenhangend.
    • Elk zijvlak van grenst aan exact N bogen.
    • Exact de helft van de knopen van 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 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