Fundamenten van de informatica: verschil tussen versies

Uit Wina Examenwiki
Naar navigatie springen Naar zoeken springen
← Oudere bewerkingNieuwere bewerking →
David42 (overleg | bijdragen)
8 bewerkingen
Geen bewerkingssamenvatting
Pieterrr (overleg | bijdragen)
21 bewerkingen
Geen bewerkingssamenvatting
Regel 1: Regel 1:
[[Afbeelding:Dereadt.jpg‎|right|200px|]]
[[Afbeelding:BartDemoen.jpg|right|200px|]]
 


== Inleiding ==
== Inleiding ==
Dit is op zijn minst gezegd een stevig vak, vooral omdat dit nogal wiskundig geïnspireerd is.
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 is schriftelijk, dus je hoeft ook prof. Demoen 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 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).
Het examen duurt maximaal 4 uur in totaal: je tijdsverdeling mag je zelf kiezen.
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...).
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.
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.
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 ==
== 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 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 ==
== Examenvragen ==
=== 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) ===
=== theorievragen (van vorige prof) ===
[[Media:Theorie.pdf|voorbeelden theorievragen]]
[[Media:Theorie.pdf|voorbeelden theorievragen]]
Regel 99: Regel 37:
##Bereken een functie die het aantal knopen in functie van ''N'' geeft, of toon aan dat er geen <math>G_N</math> kan bestaan.
##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.
#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) ===
=== 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:
Toon aan dat de klasse P de unie is van drie equivalentieklassen voor de relatie ~ (polynomiale equivalentie), namelijk vand e klassen:
Regel 117: Regel 55:
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)
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) ===
=== 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.
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.


Versie van 6 jun 2009 18:03

Fout bij het aanmaken van de miniatuurafbeelding: Bestand is zoek


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

Examenvragen

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

Oefeningen

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

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

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
Overgenomen van "http://examens.wina.be/index.php?title=Fundamenten_van_de_informatica&oldid=10601"