CS - Berekenbaarheid

Beerend
IRW-FAN!
IRW-FAN!
Berichten: 313
Lid geworden op: 30 sep 2008, 18:15
Locatie: Mechelen
Contacteer:

CS - Berekenbaarheid

Berichtdoor Beerend » 19 jan 2012, 20:56

Schriftelijk examen, heel eenvoudig.

Theorie 2 vragen, elk 6 punten:
1) Show that the language corresponding with the acceptance problem ATM (definitie gegeven) is undecidable using the diagonalization method. Also explain the notion of (un)decidability and the basic idea behind the diagonalization method. What is a countable infinite and an uncountable set? Are the set of all possible languages over the binary alphabet {0,1} and the set of all possible Turing Machines over the same alphabet countable infinite/uncountable? Explain briefly your answer.

2) Define the classes P and NP. Which variants of Turing machines are used in their definitions ans why? Define NP completeness. What is the relation between all these notions.
For each of the languages below say whether or not they belong to P, NP, NP-complete together with a brief explanation why this is (not) the case:
a) PATH
b) SAT
c) CLIQUE
d) complement of CLIQUE
(definities steeds gegeven)

Also explain the notions of a satisfiable Boolean formula and k-clique together with an example.

Oefeningen 2 vragen, elk 4 punten (oefeningen hebben we letterlijk gezien):
1) Let L be an infinite Turing-recognizable language and E an enumerator for L.
Define L' = {w element of L | E does not print any word longer than w before it prints w}
Show that L' is (a) infinite (b) decidable (c) a subset of L.
Also give the definitions of recognizer, recognizable language and enumerator.

2) Proof that the language ALLTM is not decidable, by giving a reduction from ATM. (definities van de talen gegeven)

Terug naar “1ste Master in Ingenieurswetenschappen”

Wie is er online

Gebruikers op dit forum: Geen geregistreerde gebruikers en 1 gast

cron