[A&C]Enkele vragen

[Shinta]

Als ge de complexiteit (Tijds- plaats- uniform en logaritmisch) wilt bepale van een echt algoritme in bv pascal ofzo. Dan moete da toch eerst omzette na een RAM /RASP (liefst RAM, das makkelijker :p) om me die l(i)+l... te kunnen werken he ? Voor de eenvoudigheid ?

[slimmy]

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?

staat in de tuyeaux, kan er iemand mij hier is mee helpen? Shinta? (ge verveelde u toch!)

[Shinta]

a) We kunnen de MULT instructie simuleren door een opeenvolging van optellingen, laten we om conflicten te vermijden hiervoor aparte registers gebruiken voor deze simulatie. Elke keer dage dan MULT tegen komt substitueert ge deze dan door de opeenvolging van instructies om dat te simuleren.
b) Stel MULT wordt gesimuleerd door een opeenvolging van k instructies (op het examen kan je dit dan best ook echt uitwerken ), dan heeft de beperkte ram maximaal k keer de T(n) van de gewone ram.

Da ist zowa int beknopt uitgelegd :p.

[slimmy]

hmm, ma als geen MULT simuleert, dan gaat daar toch een loopje inzitten en dan is die complexiteit toch ni constant?

[Norfolk]

1/ Wat betekent op blz 19 l precies, uitgedrukt in woorden in plaats van met die formules ?

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.
(Moest iemand het nog niet echt doorhebben )

Het rare eraan is dat voor een negatief getal, evenveel plaatsen gebruikt worden als voor datzelfde getal maar dan positief. 8 en -8 zullen dus beide 4 plaatsen nodig hebben...

Edit: let wel op dat je de juiste log pakt he dus voor de lengte in binair moet ge de 2-log nemen, ...

[Shinta]

hmm, ma als geen MULT simuleert, dan gaat daar toch een loopje inzitten en dan is die complexiteit toch ni constant?

niet constant, maar ge kunt wel de bovengrens bepalen he

Norfolk merci

[Norfolk]

die pijl nor boven wetek nog altijd ni goe wa da betekent.

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*).

Bij machines en berekenbaarheid hadden we dit geschreven als X1X2X3...Xi-1qXi...Xj
En je had dan die staprelatie |- ook die er kon voor zorgen dat dat overging naar X1X2...Xi-1YpXi+1...Xj ofzo. Daar werd de plaats van de 'q' of de 'p' ingevuld op de plaats van de schrijfkop gewoon voor de makkelijkheid.
Sorry voor het niet gebruiken van Tex voor die voorbeeldjes, maar je kan dit zien op p320 van boek van M&B.

Ik hoop dat het wel duidelijk is nu

Edit: en op p.27 staat ^w voor dat de schrijfkop op het eerste symbool van w staat.
Dus de kop staat op het eerst volgende symbool na ^
En ^ bedoel ik dat pijltje naar boven he

[slimmy]

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

[Norfolk]

2/ Moet het op blz 29 niet k*j+i zijn in plaats van k*i+j ?

ja, ik heb in mijn cursustext de i en de j omgewisseld in de tekst "wordt gesimuleerd voor de jde cel voor band i"

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, ...
Is een vraag die ik in de les aan hem had gesteld...

[filippeesje]

aan dan had ik dat toch juist in gedachten :p.

Nog een vraagje daarover, wat zit er dan juist in dat eerste blokje van k cellen? (Dus tussen het blok van c cellen en het blok dat de eerste cellen van de k tapes bevat)

Is dit bedoeld om de posities van de lees-/schrijfkop bij te houden per tape?

[Nickman]

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

Ge moet gewoon zien of ge da kunt laten eindigen met een true.
Ik heb da toen in de les gedaan met die kleurdinges.
Als ge dan uitkomt dat geen enkele van de F'en de "speciale" kleur heeft, dan is het satisfiable.
Du sgewoon een combinatie van x1, x2, x3 en x4 vinden zodat de gehele uitdrukking true geeft.

[Yo_rik]

Nog een vraagje daarover, wat zit er dan juist in dat eerste blokje van k cellen? (Dus tussen het blok van c cellen en het blok dat de eerste cellen van de k tapes bevat)

Is dit bedoeld om de posities van de lees-/schrijfkop bij te houden per tape?

klopt

[Shinta]

2/ Moet het op blz 29 niet k*j+i zijn in plaats van k*i+j ?

ja, ik heb in mijn cursustext de i en de j omgewisseld in de tekst "wordt gesimuleerd voor de jde cel voor band i"

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, ...
Is een vraag die ik in de les aan hem had gesteld...

ja tuurlijk :p

ge kunt ni eerst de 1e band afgaan want deze is oneindig.. woeps

[Norfolk]

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.

Ja in principe zorgt die ervoor dat je niet alle buckets moet overlopen in de laatste forlus van p 42.
Je moet dat maar eens uitwerken met een voorbeeldje dan ziet ge dat vrij snel. ik zal even mijn uitgewerkt voorbeeldje typen:

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

Ik heb bij de nonempty eerst de letters even neergezet en dan de getallen zodat je kan zien hoe ik aan die getallen kom

Als je zo dat algoritme op p 42 even zelf simuleert, dan ziet ge dat ge niet alle 26 buckets moet concateneren maar enkel diegene die bij die nonempty staan

[Shinta]

Ja khaddet ook al uitgevonden toch bedankt om men vermoede te stave :p