Fundamenten van de informatica

Ga naar: navigatie, zoeken
BartDemoen.jpg

Samenvattingen

Klik hier om de samenvattingen te bekijken

Inleiding

"Update: sinds 2018-2019 wordt het vak weer gedoceerd door professor Blockeel en professor Cools. De cursus is opnieuw niet veel veranderd."

Update: sinds 2016-2017 wordt het vak weer gedoceerd door professor Demoen. De cursus is niet veel veranderd. Enkele hoofdstukken vielen wel weg omdat de leerstof in het vak Bewijzen en redeneren in het eerste semester gezien werd.

Update: sinds 2010 en 2011 wordt het vak gedoceerd door professor Blockeel. De cursus bleef echter dezelfde en ook aan de examenvorm is weinig veranderd. Je hebt nu beide delen zonder pauze ertussen: je krijgt eerst het gesloten boek deel. Wanneer je daarmee klaar bent, geef je af en krijg je het open boek deel. Hint: blijf niet te lang met je gesloten boek deel zitten, anders zit je waarschijnlijk met een tijdstekort voor het open boek deel.

Dit is op zijn minst gezegd een stevig vak, vooral omdat dit nogal wiskundig geïnspireerd is. Het examen is schriftelijk, dus je hoeft prof. Demoen 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 is er ook een tussentijdse toets op theorie en oefeningen. Het is zeker interessant om deze voor te bereiden en daaraan deel te nemen. De helft van de 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

Tussentijdse toetsen

2018-2019

A. Meerkeuzevragen:

(voornamelijk van de lijst op de wiki)

B. Bewijs:

a)Wanneer S een deelverzameling is van T, met T een minimaal opspannende boom van een gewogen graaf G, en e is alle bogen waarvoor S U {b} krijgvrij is, die met het kleinste gewicht, dan bestaat er een MOB T' van G zodat S U {e} is deelverzameling van T'.

b) Bewijs dat de conditie waarvoor S U {b} krijgvrij is in bovenstaande bewering essentieel is, dus dat de bewering niet steeds geldt als deze conditie weggelaten wordt.

C. Oefening 1:

a) Bewijs dat K_2,n steeds vlak is en K_3,n vlak asa n<3

b) In een bepaalde groep studenten geldt: de studenten hebben gemiddeld 5 vrienden binnen die groep. Iemand construeert de "vriendschapsgraaf". Die graaf blijkft vlak te zijn, Hoeveel studenten zitten er minstens in die groep?

c) Een samenhangende vlakke graaf heet outerplanair wanneer volgende constructie een graaf oplevert: voeg een knoop toe in buitenste zijvlak, verbind deze knoop met alle knopen in de oorspronkelijke graaf Toon aan: een enkelvoudige outerplanaire graf steeds e<2v-3 geldt.

D. Oefening 2:

Pas het algoritme van dijkstra toe om in een graaf het kortste pad van a naar z te vinden. Noteer de labels na 7 stappen. En schrijf na afloop het kortste pad op, het gewicht ervan en de volgorde waarin de knopen behandeld werden.

Op het examen was een gerichte graaf gegeven.


2017-2018

Tussentijdse toets

Juist/fout vragen

Er staan 12 punten van het examen op juist of fout vragen. Hieronder een lijst van dit type vraag. Deze lijst is niet volledig. Er worden onder andere ook juist of fout vragen gesteld over hoofdstuk 5.

  1. Een string heeft steeds een eindige lengte. juist
  2. Een taal bevat steeds een eindig aantal strings. fout
  3. De verzameling van alle strings die gevormd kunnen worden met bepaald alfabet, is een taal over dat alfabet. juist
  4. Voor eender welke twee talen S en T, regulier of niet, is TS*T een reguliere taal. fout
  5. {a}* bevat oneindig veel strings. juist
  6. Niet - deterministische automaten kunnen meer talen herkennen dan deterministische. fout
  7. Niet-deterministische eindige automaten kunnen dezelfde talen herkennen als deterministische, maar som efficiënter in tijd (d.w.z. strings worden soms herkend met minder toestandstransities). fout
  8. Niet-deterministische turingmachines kunnen meer talen herkennen dan deterministische. fout
  9. Als L α T en L is een element van de klasse P, dan geldt steeds T is een element van P. fout
  10. We weten zeker dat P een deelverzameling is van NP en dat NP een deelverzameling is van NPC. fout
  11. We weten zeker dat P een deelverzameling is van NPC en dat NPC een deelverzameling is van NP. fout
  12. Elke vlakke graaf voldoet aan v - e + f = 2 met v het aantal knopen, e het aantal bogen en f het aantal zijvlakken. fout
  13. In een samenhangende graaf bestaat er een pad tussen elke twee knopen. juist
  14. K2,2 is homeomorf met K3. juist
  15. Als twee grafen isomorf zijn, hebben ze evenveel knopen. juist
  16. Als twee grafen homeomorf zijn, hebben ze evenveel bogen. fout
  17. Bepalen of een gewogen graaf een Hamiltoniaanse kring met gewicht kleiner dan 100 heeft is zeker in P. fout
  18. Bepalen of een graaf een Eureliaanse kring heeft, is zeker in NP. juist
  19. Bepalen of het korste pad tussen twee gegeven knopen in een gewogen graaf en een gewicht kleiner dan 100, is zeker NP-compleet. fout
  20. Een boom met n knopen heeft steeds n-1 bogen. juist
  21. Elke samenhangende graaf heeft precies 1 opspannende boom. fout
  22. Het algoritme van Kruskal en het algoritme van Prim zijn twee verschillende manieren om hetzelfde probleem op te lossen. juist
  23. Het algoritme van Kruskal en het Algoritme van Prim geven steeds dezelfde uitkomst. fout
  24. Elke boom heeft een twee-kleuring. juist
  25. Elke eindige taal is regulier. juist
  26. Elke reguliere taal is eindig. fout
  27. Elke reguliere taal bevat de lege string.fout
  28. De lege taal is een reguliere taal. juist
  29. Voor elke reguliere taal L geldt: als x en y een element is van L, dan is xy ook een element van L. fout
  30. Voor elke reguliere taal bestaat er een eindige automaat die die taal herkent. juist
  31. De verzameling van {(ab)^n | n element van de natuurlijke getallen} is een reguliere taal. juist
  32. De verzameling van {a^m b^n | n,m element van de natuurlijke getallen} is een reguliere taal. juist
  33. De verzameling van {a^n b^n | n element van de natuurlijke getallen} is een reguliere taal. fout
  34. De verzameling van alle wiskundige uitdrukkingen gevormd met +,-,/,x en haakjes is een reguliere taal. fout
  35. De klasse van talen herkend door eindige toestandsautomaten is dezelfde als de klasse herkend door niet-determinitische eindige automaten. juist
  36. Voor elk java-programma bestaat er een Turningmachine die voor eender welke input dezelfde output geeft als dat programma. juist
  37. Voor elke binaire booleaanse operator f: BxB ->, met B = {0,1} bestaat er een eindige automaat die f berekent. juist
  38. Voor elke functie f: N -> N bestaat er een eindige automaat die f berekent. fout
  39. Voor elke functie f: N -> N bestaat er een TM die f berekent. fout
  40. Uit de stelling van Cook volgt SAT is een element van NPC.juist
  41. Uit de stelling van Cook volgt SAT is geen element van P. fout
  42. Het algoritme van Dijkstra heeft complexiteit 0(n^3) (met n het aantal knopen) juist (want zowel n^2 als n log n zijn O(n^3))
  43. Het algoritme van Dijkstra is assymptotisch equivalent met n^3. (met n het aantal knopen) fout
  44. Het algoritme van Dijkstra kan door een deterministische TM uitgevoerd worden. juist
  45. Een graaf met een euleriaanse kring heeft nooit knopen met oneven graad. juist
  46. Elke samenhangende vlakke graaf heeft een Euleriaanse kring. fout
  47. De tweeledige grafen K3,4 en K4,3 zijn isomorf. juist
  48. Elke tweeledige graaf heeft een tweekleuring. juist.
  49. Elke tweeledige graaf is vlak. fout
  50. Elke vlakke graaf heeft een vierkleuring. juist
  51. K3,3 is vlak. fout
  52. K3,3 heeft een vierkleuring. juist
  53. elke niet-vlakke graaf heeft minstens een kring. juist
  54. Uit de stelling van Kuratowski volgt dat elke graaf die geen subgraaf bevat die isomorf is met K5 of K3,3 valk is. fout
  55. Van elke vlakke graaf kan een boom gemaakt worden door k bogen weg te halen met k het aantal kringen. fout
  56. De tijdscomplexiteit van het algoritme van Prim is linear in het aantal knopen. fout
  57. De tijdscomplexiteit van het algoritme van Prim is linear in het aantal bogen. fout
  58. Om een opspannende boom te hebben moet een graaf samenhangend en vlak zijn. fout
  59. Een eindige taal is steeds regulier. juist
  60. Een reguliere taal bevat steeds de lege string. fout
  61. Voor elke reguliere taal L en voor elke string s kan in tijd O(n) beslist worden of s ∈ L, met n de lengte van s. juist
  62. Elke eindige automaat A beslist of s ∈ L(A) in een aantal stappen O(m), met m het aantal toestanden van A. fout
  63. De verzameling {a^n b^n | n ∈ N} is een reguliere taal over {a,b,c,0,...,9}. fout
  64. De verzameling {a^n b^n | n ∈ N, 2n ≤ 20} is een reguliere taal over {a,b,c,0,...9}. juist
  65. Voor elke functie f : N → {0,1} bestaat er een Turingmachine die f berekent. fout
  66. Voor elke functie f : {0,1}² → {0,1} (d.w.z., voor elke binaire booleaanse operator) bestaat er een Turingmachine die f berekent. juist
  67. Voor elke binaire booleaanse operator f bestaat er een eindige automaat die f berekent. juist
  68. Als L1 α L2 en L1 ∈ P, dan geldt steeds L2 ∈ P. fout
  69. We weten zeker dat P ⊆ NP ⊆ NPC. fout
  70. Een graaf met een Euleriaanse kring heeft nooit knopen met oneven graad. juist
  71. Elke graaf met enkel knopen met even graad heeft een Euleriaanse kring. fout
  72. Elke graaf die K5 bevat heeft zeker geen 4-kleuring. juist
  73. Elke graaf met minder dan n componenten heeft een n-kleuring. fout
  74. Elke vlakke graaf voldoet aan v - e + f = 2 (met v het aantal knopen, e het aantal bogen, en f het aantal zijvlakken). fout
  75. Het algoritme van Kruskal en het algoritme van Prim zijn twee verschillende manieren om hetzelfde probleem op te lossen. juist
  76. Het algoritme van Kruskal en het algoritme van Prim geven steeds dezelfde uitkomst. fout

Examenvragen

Juni 2017

Theorie (Gesloten boek)

  1. 40 juist-of-foutvragen met giscorrectie (enkele stonden op de wiki en de tussentijdse toets, maar zeker niet allemaal).
  2. Bewijs de formule van Euler voor een vlakke, samenhangende graaf G en geef de aanpassing die nodig is om de formule te doen kloppen bij niet-samenhangende grafen.
  3. Bewijs de stelling van Kleene.

Oefeningen (Open boek)

  1. Gegeven graaf G met 5 knopen, en de graad van elke knoop is twee of drie. Geef de mogelijke waarden van v, e en f waarvoor G bestaat.
  2. Gegeven een NFSA: Nfsa.png
    1. Beschrijf de taal die de NFSA aanvaard in woorden.
    2. Geef de reguliere expressie voor deze taal.
    3. Geef de overeenkomstige DFA die de taal aanvaard.
  3. Gegeven een bepaald transportnetwerk dat alfabetisch geordend is en waarvan de capaciteit op elke boog 1 is.
    1. Duid de stroming aan op elke boog.
    2. Geef de maximale stroming.
    3. Geef de minimale snede.
    4. Als er nog een andere minimale snede is, geef deze dan.
  4. Gegeven een gewogen graaf en 8 tekeningen van deze graaf, met de labels op de eerste aangeduid.
    1. Duid de labels aan op de verschillende tekeningen zoals ze bij Dijkstra (versie 1) zouden staan na de 1ste, 2de, ..., 8ste uitvoering van de lus.

Augustus 2016

Theorie (Gesloten boek)

  1. 36 juist-of-foutvragen met giscorrectie (enkele stonden op de wiki en de tussentijdse toets, maar zeker niet allemaal).
  2. Bewijs dat een graaf een kring bevat wanneer er 2 verschillende paden zijn tussen 2 knopen.

Oefeningen (Open boek)

for(int i = 1; i <= n; i++)

 for(int j = 1; j <= n; j++)
   for(int k = 1; k <= i; k++)
     print("hello")

  1. Gegeven het bovenstaande algoritme:
    1. Druk de complexiteit T(n+1) uit in termen van T(n).
    2. Geef T(n) in O-notatie.
    3. Wat is T(3)?
  2. Bewijs de volgende stellingen:
    1. Een niet-vlakke graaf heeft minstens 5 knopen en 9 bogen.
    2. We weten dat als een graaf Kn als deelgraaf bevat, hij geen (n-1)-kleuring heeft. Geldt het omgekeerde? Toon aan.
  3. Pas het algoritme van Prim en dat van Kruskal toe op dezelfde graaf.

Juni 2016

Theorie (Gesloten boek)

  1. 36 juist-of-foutvragen met giscorrectie (enkele stonden op de wiki en de tussentijdse toets, maar zeker niet allemaal).
  2. Bewijs: Wanneer het algoritme van Dijkstra de knoop met de kleinste L-waarde (voorlopige afstand) kiest, is dit deze waarde de lengte van het korste pad van de bron naar die knoop. Invarianten waarmee je dit kon bewijzen, waren gegeven.

Oefeningen (Open boek)

for(int i = 0; i < n; i++)

 for(int j = 0; j < n; j++)
   for(int k = 0; k < i*j; k++)
     t++

  1. Gegeven het bovenstaande algoritme
    1. Druk de complexiteit T(n+1) uit in termen van T(n).
    2. Geef T(n) in O-notatie.
    3. Wat is T(5)?
  2. Bewijs de volgende stellingen.
    1. Elke boom is een tweeledige graaf.
    2. Elke niet-lege enkelvoudige graaf met evenveel bogen als knopen heeft minstens 1 kring.
    3. In een complete tralie L, ≤ geldt ∀s∈L : inf(L) ≤ s ≤ sup(L).
  1. Gegeven een stromingsnetwerk, bereken de maximale stroming en de minimale snede met het geziene algoritme

Juni 2015

Theorie (Gesloten boek)

  1. 36 juist-of-foutvragen met giscorrectie.
  2. Bewijs: Als de taal L1 ⊆ T1* polynomiaal transformeert in de taal L2 ⊆ T2* door een functie f

die berekend wordt door een TM M met een tijdscomplexiteit die O(n^k) (k ∈ N \ {0}) is, dan bestaat er een positieve constante c ∈ R+ zodat |f(x)| ≤ c|x|^k voor alle niet-lege x ∈ T1∗.

Oefeningen (Open boek)

  1. Een vraag over het k-domino spel (bestaande uit steentjes met ogen a en b en enkele eigenschappen waaraan het spel voldoet),

voor welke k is dit spel mogelijk?

  1. Gegeven: 3 niet-deterministische automaten a, b en c;
    1. Geef een reguliere expressie voor de taal herkend door deze a.
    2. Geef een zo eenvoudig mogelijke deterministische automaat voor gegeven b.
    3. Geef een alternatieve definitie voor de taal herkend door c (zonder gebruik te maken van automaten).
  2. Maximale stroming en minimale snede zoeken voor een gegeven netwerk mbhv het algoritme in de cursus.

Juni 2014

Theorie

  1. 36 juist-of-foutvragen met giscorrectie. (Veel vragen kwamen letterlijk uit het proefexamen of uit de oefenzittingen)
  2. Bewijs: Een continue afbeelding is monotoom

Oefeningen

  1. Bewijs volgende stelling: Als P != NP dan is geen enkele reguliere taal NP-Compleet. Verwijs naar stellingen in de cursus
  2. Gegeven: Een cactusgraaf is een samenhangende graaf met de eigenschap dat twee kringen nooit meer dan een knoop gemeenschappelijk hebben. Een voorbeeld: Cactusgraaf.png
    1. Bewijs dat cactusgrafen vlak zijn (gebruik de stelling van Kuratowski)
    2. Voor welke k geldt er dat elke cactusgraaf een k-kleuring heeft?
    3. 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.

Juni 2011

Het examen duurde 3 uur en je mocht de tijd zelf verdelen.

Theorie

  1. 36 juist-of-foutvragen met giscorrectie.
  2. Bewijs: een enkelvoudige vlakke graaf heeft een 5-kleuring. (Je mag voorgaande stellingen gebruiken.)

Oefeningen

  1. Gegeven: een simpele niet-deterministische eindige automaat.
    1. Welke taal wordt door deze automaat aanvaard?
    2. Geef een reguliere expressie voor deze taal.
    3. Geef een deterministische eindige automaat die dezelfde taal bepaalt.
  2. Gebruik formules voor grafen om aan te tonen dat …
  3. Gegeven: een netwerk. Pas het algoritme toe om een maximale stroming te vinden. Duid voor elke stap het gevolgde pad (met labels) en het tussenresultaat aan op de bijgeleverde figuren.

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 automaat aanvaard?
    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