Moderator: Praesidium
Code: Select all
2. Stel dat we een beperkte soort RAM invoeren die geen MULT instructie heeft.
(a) Kan de beperkte RAM de gewone RAM simuleren? M.a.w. bestaat er voor elk gewoon RAM programma een equivalent programma voor de beperkte RAM?
(b) Is het zo dat de tegenhanger van de stelling op p.21 geldt, m.a.w. dat er een constante k bestaat zodat de logaritmische tijdscomplexiteit slechts met ten hoogste een factor k toeneemt bij simulatie van een RAM programma door de beperkte RAM?
Die l is gewoon de lengte van uw n. Dus als ge hebt n = 8 en je slaat alles op in binair, dan zult ge lengte 4 nodig hebben. Dus zoals eerder gezegd is dat voor logaritmisch plaatscomplexiteit Aangezien ge 4 plaatsen nodig hebt voor uw n.Shinta wrote:1/ Wat betekent op blz 19 l precies, uitgedrukt in woorden in plaats van met die formules ?
slimmy wrote:hmm, ma als geen MULT simuleert, dan gaat daar toch een loopje inzitten en dan is die complexiteit toch ni constant?
Ja dat is denk ik inderdaad de positievan de lees/schrijfkop. (Dat is op p.26 zeker?) Daar staat de Q dat ge in een bepaalde toestand zit, en ge hebt k keer dat deel tussen haakjes. Voor elke band, want ge hebt k banden, staat er links van de schrijfkop een deel symbolen (de eerste T*) en dan de positie van uw schrijfkop, en dan nog een deel symbolen (de andere T*).Shinta wrote:die pijl nor boven wetek nog altijd ni goe wa da betekent.
neen zoals het in de cursustekst staat is het juist. Eerst worden alle 1e cellen van de k tapes in een blok gezet, dan alle 2e cellen, ...slimmy wrote:ja, ik heb in mijn cursustext de i en de j omgewisseld in de tekst "wordt gesimuleerd voor de jde cel voor band i"Shinta wrote:2/ Moet het op blz 29 niet k*j+i zijn in plaats van k*i+j ?
Ge moet gewoon zien of ge da kunt laten eindigen met een true.slimmy wrote:bleh, stom vak
ge hebt zo in reeks 8 oefening 2:
stel 3-CNF expressie E heeft 4 variabelen x1,x2,x3,x4. Voor else set van 3 verschillende indices (1 tot 4) heeft E clauses (
en . Is E satisfiable? Geef een tegenvoorbeeld?
I don't get it
ja tuurlijk :pNorfolk wrote:neen zoals het in de cursustekst staat is het juist. Eerst worden alle 1e cellen van de k tapes in een blok gezet, dan alle 2e cellen, ...slimmy wrote:ja, ik heb in mijn cursustext de i en de j omgewisseld in de tekst "wordt gesimuleerd voor de jde cel voor band i"Shinta wrote:2/ Moet het op blz 29 niet k*j+i zijn in plaats van k*i+j ?
Is een vraag die ik in de les aan hem had gesteld...
Ja in principe zorgt die ervoor dat je niet alle buckets moet overlopen in de laatste forlus van p 42.Shinta wrote:Kbegrijp nog altijd ni goe wa dattie NonEmpty bij de derde versie van de Radix Sort juist doet en hoe die in het plaatje past.
Code: Select all
m = 26 want we werken hier gewoon met alfabet
s1: water l1: 5 Lmax: 5
s2: soort l2: 5 Ltot: 13
s3: dom l3: 3
Dus
Length[1]: /
Length[2]: /
Length[3]: dom
Length[4]: /
Length[5]: water, soort
en
Nonempty[1]: d, s, w : 4, 19, 23
Nonempty[2]: a, o : 1, 15
Nonempty[3]: m, o, t : 13, 15, 20
Nonempty[4]: e, r : 5, 18
Nonempty[5]: r, t : 18, 20
Users browsing this forum: No registered users and 7 guests