Vraag 1:
p94 het bewijs is weer evident, maar niet voor mij.
Vraag 2:
Waarom is O(c * d^q(n)) = O(2^p(n))?
p95 laatste regel
Vraag 3:
Hoe doede het bewijs van de eerste stelling op p99
Vraag 4:
Wat willen ze juist zeggen op pagina 100?
Vraag 5:
Wat is een configuratie concreet?
p102
Vraag 6:
Bij puntje 4 op p102 kan er iemand meer utileg geven bij de twee termen waar de B in voorkomt? Waar die voorstaan?
Vraag 7:
Kan er iemand bij puntje 5,7 en 8 van de Stelling van Cook wat verduidelijkend uitleg geven.
p103-104
Vraag 8:
Op p 107 geven ze een B in de stelling. Waarom zou die dezelfde uitkomst geven als A? Eigenlijke vraag. Waarom zal door het invoeren van die Y's het resultaat niet veranderen.
Vraag 9:
waarom is p'(B) = tt? (p108)
Vraag 10:
Op p108 zegge ze onderaan dat de expressie hoogste 8 keer langer word.
Waarom?
Vraag 11:
Kan iemand een eenvoudigere definitie geven van de defitnie op p 112
Vraag 12:
p118 geven ze onderaan een vb en ze zegge dat k=2. Maar die k wordt bepaald op een of andere manier staat er in de beschrijving op p 116.Das de grote van de vertexcover? Hoe bepalen we in het voorbeeld dat de VC 2 is?
Vraag 13:
Het stukje code op p120 wat wille ze ermee aantone bij het bewijs?
Vraag 14:
Ben niet goed mee met de uitleg onderaan op p120 die verder loopt bovenaan p121
Vraag 15:
Stelling p121. waarom is dat weer evident?
Vraag 16:
Is er geen duidelijker woord dan niet-leeg complement?
Vraag 17:
De tekst bovenaan p122, Waarom duid die tekst aan dat het in P-SPACE is. Plus ze spreken er over een NDFA dus zou ik toch eerder NP-Space denken.
Grtz
[AlgEnComp] Vragen bij Hfst 6 van Algo
Moderator: Praesidium
-
Quintus Maximus
- Posts: 222
Vraag1: Een deterministische turing machine IS een niet deterministische turing machine!!!! (einde bewijs)
Vraag2: goei vraag, peins dat iet met die big-Oh te make heeft
Vraag3: Uit "Introduction to Automata Theory, Languages and Computation":
the first part of the proof is showing that SAT is NP. This part is easy:
1: Use the nondeterministic ability of an NTM to guess a truth assignment T for the given expression E. If the encoded E is of length n, then O(n) time suffices on a multitape NTM. Note that this NTM has many choices of move, and may have as many as 2^n different configurations reached at the end of the guessing process, where each branch represents the guess of a different truth assignment.
2. Evaluate E for the trugh assignemnt T if E(T) = true, then accept. Note that this part is deterministic. The fact that other btanches of the NTm may not lead to acceptance has no bearing on the outcome, since if even one satisfying truth assignment is found, the NTM accepts.
The evaluation can be done easily in O(n^2) time on a multitape NTm. This the entire recogintion of SAT by the multitape NTM takes O(n^2) time.
Vraag4:
We proberen dus te bewijzen dat SAT NP compleet is (dat is de stelling van Cook)
SAT is NP compleet als alle talen L uit NP kunnen gereduceerd worden tot SAT in polynomiale tijd.
L is in NP als er een NDTM bestaat die L accepteert in p(n) tijd.
We willen dus elke NDTM kunnen omzetten naar een booleanse uitdrukking die een waarheidstoekenning heeft.
pak dus een NDTM M =(Q,T,I,d,b,q0,qf) met Q de staten, q0 de beginstaat, qf de eindstaat, T de symbolen die op de band kunnen staan b het blanco symbool en I de inputsymbolen. d is de transitiefunctie.
indien nu s in L (M is de turing machine die L accepteert in p(n) tijd)
dan zijn er configuraties van die resulteren in acceptance van s.
dus de eerste configuratie begint in de staat q0
C0 = (q0, ^ s) --> q0 is de stat ^ is de positie van de lees/schrijf kop en s is hetgeen dat achter ^ komt.
de laatste configuratie staat in de staat qf
Cl = (qf, ^s')
een configuratie Ci kan met een stap overgaan in Ci+1
Ci |-- Ci+1
Als het allemaal in p(n) tijd gebeurt kunnen er niet meer dan p(n) configuraties zijn en er kunnen ook niet meer dan p(n) symbolen op de tape staan.
En dan gaat hij verder met hoe hij van die configuraties een waarheidsuitdrukking ws maakt.
Vraag5:
Een configuratie is iets dat zegt wat de huidige toestand van de turing machine is --> in welke staat hij staat en waar de lees/schrijf kop zich bevindt.
dus (q, s ^ s') is een configuratie die zegt dat de turing machine in staat q is en dat de lees schrijfkop staat op de cel die de eerste letter van s bevat.
Vraag6:
Eenvoudig:
in de initiele staat (q0)
staat heel de string s op de band gevolgd door blanco symbolen
de string s bestaat uit symbolen yj en y1 is het blanco symbool
dus Bi,j,0 met 0<=i<=n-1, yj = si+1
Zegt dat cel i si+1 bevat
cel 0 bevat dus s1
cel 1 bevat dus s2
...
cel n-1 bevat sn
en alle cellen van n tot p(n) (er kunnen niet meer dan p(n) cellen zijn)
bevatten blanco = y1
Vraag7:
Vraag8: "Waarom zal door het invoeren van die Y's het resultaat niet veranderen." Da is juist wa ze aant bewijzen zijn!!!
Vraag9:
Als rho(A) = true
Dan is minstens 1 van de z'jes true. Stel dat dit zi is.
Nu moeten we aantonen dat rho'(B) true is.
dit kan enkel als alle disjuncties waar zijn
(z1 v z2 v y1) ^ (z3 v -y1 v y2) ^ .... ^ (zi V -yi-2 v yi-1) ^ ...
(zi V -yi-2 v yi-1) is waar omdat zi true is
al de factoren ervoor zijn waar omdat de yj true zijn als j <= i-2
al de factoren erna zijn waar omdat dan de -yj true zijn.
Vraag10:
Vraag11: neen, dit kan niet eenvoudiger.
Vraag12: de graaf G op figuur 8 (p 118) heeft een VC van 2,
namelijk de verzameling die nodes 1 en 2 bevat,
die twee nodes hebben samen alle edges uit heel de graaf.
(node 1 alleen is geen VC want die heeft geen eindputn uit de edge 2-3
en node 2 alleen is geen VC want die heeft geen eindpunt uit de edge 1-4)
Vraag13: geen idee.
VRaag15: een DTM IS een NDTM
Vraag16: nie echt.
Vraag17: P-SPACE = NP-SPACE
Vraag2: goei vraag, peins dat iet met die big-Oh te make heeft
Vraag3: Uit "Introduction to Automata Theory, Languages and Computation":
the first part of the proof is showing that SAT is NP. This part is easy:
1: Use the nondeterministic ability of an NTM to guess a truth assignment T for the given expression E. If the encoded E is of length n, then O(n) time suffices on a multitape NTM. Note that this NTM has many choices of move, and may have as many as 2^n different configurations reached at the end of the guessing process, where each branch represents the guess of a different truth assignment.
2. Evaluate E for the trugh assignemnt T if E(T) = true, then accept. Note that this part is deterministic. The fact that other btanches of the NTm may not lead to acceptance has no bearing on the outcome, since if even one satisfying truth assignment is found, the NTM accepts.
The evaluation can be done easily in O(n^2) time on a multitape NTm. This the entire recogintion of SAT by the multitape NTM takes O(n^2) time.
Vraag4:
We proberen dus te bewijzen dat SAT NP compleet is (dat is de stelling van Cook)
SAT is NP compleet als alle talen L uit NP kunnen gereduceerd worden tot SAT in polynomiale tijd.
L is in NP als er een NDTM bestaat die L accepteert in p(n) tijd.
We willen dus elke NDTM kunnen omzetten naar een booleanse uitdrukking die een waarheidstoekenning heeft.
pak dus een NDTM M =(Q,T,I,d,b,q0,qf) met Q de staten, q0 de beginstaat, qf de eindstaat, T de symbolen die op de band kunnen staan b het blanco symbool en I de inputsymbolen. d is de transitiefunctie.
indien nu s in L (M is de turing machine die L accepteert in p(n) tijd)
dan zijn er configuraties van die resulteren in acceptance van s.
dus de eerste configuratie begint in de staat q0
C0 = (q0, ^ s) --> q0 is de stat ^ is de positie van de lees/schrijf kop en s is hetgeen dat achter ^ komt.
de laatste configuratie staat in de staat qf
Cl = (qf, ^s')
een configuratie Ci kan met een stap overgaan in Ci+1
Ci |-- Ci+1
Als het allemaal in p(n) tijd gebeurt kunnen er niet meer dan p(n) configuraties zijn en er kunnen ook niet meer dan p(n) symbolen op de tape staan.
En dan gaat hij verder met hoe hij van die configuraties een waarheidsuitdrukking ws maakt.
Vraag5:
Een configuratie is iets dat zegt wat de huidige toestand van de turing machine is --> in welke staat hij staat en waar de lees/schrijf kop zich bevindt.
dus (q, s ^ s') is een configuratie die zegt dat de turing machine in staat q is en dat de lees schrijfkop staat op de cel die de eerste letter van s bevat.
Vraag6:
Eenvoudig:
in de initiele staat (q0)
staat heel de string s op de band gevolgd door blanco symbolen
de string s bestaat uit symbolen yj en y1 is het blanco symbool
dus Bi,j,0 met 0<=i<=n-1, yj = si+1
Zegt dat cel i si+1 bevat
cel 0 bevat dus s1
cel 1 bevat dus s2
...
cel n-1 bevat sn
en alle cellen van n tot p(n) (er kunnen niet meer dan p(n) cellen zijn)
bevatten blanco = y1
Vraag7:
Vraag8: "Waarom zal door het invoeren van die Y's het resultaat niet veranderen." Da is juist wa ze aant bewijzen zijn!!!
Vraag9:
Als rho(A) = true
Dan is minstens 1 van de z'jes true. Stel dat dit zi is.
Nu moeten we aantonen dat rho'(B) true is.
dit kan enkel als alle disjuncties waar zijn
(z1 v z2 v y1) ^ (z3 v -y1 v y2) ^ .... ^ (zi V -yi-2 v yi-1) ^ ...
(zi V -yi-2 v yi-1) is waar omdat zi true is
al de factoren ervoor zijn waar omdat de yj true zijn als j <= i-2
al de factoren erna zijn waar omdat dan de -yj true zijn.
Vraag10:
Vraag11: neen, dit kan niet eenvoudiger.
Vraag12: de graaf G op figuur 8 (p 118) heeft een VC van 2,
namelijk de verzameling die nodes 1 en 2 bevat,
die twee nodes hebben samen alle edges uit heel de graaf.
(node 1 alleen is geen VC want die heeft geen eindputn uit de edge 2-3
en node 2 alleen is geen VC want die heeft geen eindpunt uit de edge 1-4)
Vraag13: geen idee.
VRaag15: een DTM IS een NDTM
Vraag16: nie echt.
Vraag17: P-SPACE = NP-SPACE
[img]http://users.skynet.be/quintensoetens/sigG4.jpg[/img]
-
B_PC_Freak
- Posts: 3
vraag 7:
puntje 5: hier gebeurt wat er wordt gezegd: de eindconfiguratie wordt herhaald tot we aan p(n) configuraties zijn. Dit is omdat we enkel in configuratie p(n) op de eindstaat gaan checken. Gevolg is wel dat eens we in de eindconfiguratie zijn we deze moeten kopieren tot we p(n) configuraties hebben.
ge hebt dus iets van de vorm:
voor alle t: Tr,t ==> voor alle i,j,k:
-Bi,j,t = B i,j,t+1 :maw de inhoud van de tape moet dezelfde blijven
-Tk,t = Tk,t+1 : maw de staat moet dezelfde blijven
-Ki,t = Ki,t+1 : maw de positie van de leeskop moet dezelfde blijven
Tr,t: op tijdstip t zitten we in een eindstaat (remember r=index vd eindstaat)
puntje 7: Cellen die niet gelezen worden veranderen niet:
er staat iets vd vorm voor alle i,j,t:
Bi,j,t=Bi,j,t+1 of Ki,t
maw we hebben twee keuzes: ofwel zal bij het overgaan van één configuratie naar de volgende er niets aan dat element veranderen, ofwel bezoekt de lees/schrijfkop tijdens die configuratie die bepaalde locatie
puntje 8: Dit garandeerd de correcte werking van de TM
Het algemene principe is:
Als we op een bepaald tijdstip t in een bepaalde staat T zijn en als de Leeskop over een bepaalde cel i staat, en de inhoud van i is het karakter yj, dan kunnen we een transitie naar een volgende staat uitvoeren indien deze volgens delta mag. Dit wordt uitgedrukt in de therm A(i,j,k,i',j',k')
Natuurlijk moet dit voor alle i,j,k gelden, en dan wordt er ook nog uitgelegd hoe de i',j' en k' kunnen worden bekomen
puntje 5: hier gebeurt wat er wordt gezegd: de eindconfiguratie wordt herhaald tot we aan p(n) configuraties zijn. Dit is omdat we enkel in configuratie p(n) op de eindstaat gaan checken. Gevolg is wel dat eens we in de eindconfiguratie zijn we deze moeten kopieren tot we p(n) configuraties hebben.
ge hebt dus iets van de vorm:
voor alle t: Tr,t ==> voor alle i,j,k:
-Bi,j,t = B i,j,t+1 :maw de inhoud van de tape moet dezelfde blijven
-Tk,t = Tk,t+1 : maw de staat moet dezelfde blijven
-Ki,t = Ki,t+1 : maw de positie van de leeskop moet dezelfde blijven
Tr,t: op tijdstip t zitten we in een eindstaat (remember r=index vd eindstaat)
puntje 7: Cellen die niet gelezen worden veranderen niet:
er staat iets vd vorm voor alle i,j,t:
Bi,j,t=Bi,j,t+1 of Ki,t
maw we hebben twee keuzes: ofwel zal bij het overgaan van één configuratie naar de volgende er niets aan dat element veranderen, ofwel bezoekt de lees/schrijfkop tijdens die configuratie die bepaalde locatie
puntje 8: Dit garandeerd de correcte werking van de TM
Het algemene principe is:
Als we op een bepaald tijdstip t in een bepaalde staat T zijn en als de Leeskop over een bepaalde cel i staat, en de inhoud van i is het karakter yj, dan kunnen we een transitie naar een volgende staat uitvoeren indien deze volgens delta mag. Dit wordt uitgedrukt in de therm A(i,j,k,i',j',k')
Natuurlijk moet dit voor alle i,j,k gelden, en dan wordt er ook nog uitgelegd hoe de i',j' en k' kunnen worden bekomen
Who is online
Users browsing this forum: No registered users and 53 guests