[Tuyeaux] Examenvragen

[Norfolk]

Naar aanleiding van mijn topic in Algemeen maak ik hier een apart stuk voor de examenvragen van 2e BAC. Zo worden deze al niet door elkaar gegooid en is het achteraf makkelijker voor mij om ze in de tuyeaux te zetten.

Dus post maar raak!
(en ja dit is copy paste van tekstje in 1e BAC )

[Norfolk]

Zorgt er iemand voor de vragen van programmeerparadigma's?

[Michael Cochez]

Ik heb de opgave meegenomen, ik wil die wel geven.

[Norfolk]

Bedankt Op welke manier kan je die bij mij krijgen? Ik ben morgen aanwezig op unief, of anders kan je die eventueel inscannen oid?

[Scheder]

hoe zittet hier eigenlijk mee?
staan de tuyaux van het 2e semester al online of is da te snel?
*vraagt een student die de stress voelt opkomeXD*

*edit: ik bedoelde 1e semester en in het bijzonder van machines en berekenbaarheid [wat niet in de huidige tuyaux zit btw ]

[Phil]

Examenvragen van M&B 1e semester:

1. Definitie Turing Machine
2. Bewijs omzetting PDA final state naar empty state (of andersom, kweet niemer juist)
3. Iets me PDA omzette na CFG ofzo
4. Toepassingen van CFG

Dan oefeningen moeste nen TM ontwerpen, nen PDA ontwerpen en iets omzette na Chomsky Normal Form.

[Scheder]

ok thx

[Scheder]

en van algoritmen en complexiteit?
die haddek blijkbaar ni zelf genoteerd?

Peter.

[Phil]

Oefening op RAM en 4 Big-Oh dingen.

Dan theorie:

Iets met het simuleren van een RAM machine fzo..

Dan iets me een invariant van die bomen.

Iets met K-color

en dan nog iets dat ik niemer just weet :p

Ik herinner me niet meer veel van da examen precies :d

[Scheder]

AEC
1) Geef de tijdscomplexiteit van volgende 2 functies

Code: Select all

		a:	functie f(m, n) {

				int i = 0;

				int total = 0;

				while (i < m) {

					int j = 0;

					while (j < n) {

						total += 5;	// Ik weet ni meer exact wa het dee, mr da doe er ni echt toe voor de tijdscomplexiteit

						j++;

					}

					i++;

				}

			}

			

			O(m*n) dus

			

		b:	functie f(m, n) {

				int i = 0;

				int j = 0;

				int total = 0;

				while (i < m) {

					while (j < n) {

						total += 5;	// Ik weet ni meer exact wa het dee, mr da doe er ni echt toe voor de tijdscomplexiteit

						j++;

					}

					i++;

				}

			}

			

			O(m+n) dus

		

		/* Kben wel ni meer 100% zeker, kheb deze vraag ni opgeschreven,

			maar voor zover dak mij herinner moet het toch zoiets zijn */

2) p21 en p22
a: Geef de vertaling van STORE*i (2pt)
b: Geef de tijdskost volgens het logaritmisch criterium voor de individuele RASP instructies uit (a), zoals dit gedaan wordt bovenaan p21 (2pt)
3) a: p66 Leg uit waarom een knoop geen hoofdknoop kan zijn van 2 verschillende indices i, in de veronderstelling dat S = {a1, ..., an} bestaat uit n verschillende elementen (4pt)
b: Toon aan dat stelling p65 hieruit volgt, ook zonder veronderstelling dat alle elementen verschillend zijn (2pt)
4) p99 SAT
a: Schets een niet-deterministisch algoritme voor SAT dat een polynomiaal tijdscomplexiteit heeft. De beschrijving moet voldoende gedetailleerd zijn om duidelijk te maken dat de tijdscomplexiteit wel degelijk polynomiaal is (3pt)
b: Volstaat dit om aan te tonen dat SAT element is van NP-TIME? (2pt)
5) p114 VC is NP-compleet
Leg uit waarom deze reductie van CLIQUE naar VC een polynomiaal reductie is (3pt)