[A&C]Enkele vragen

[slimmy]

Nog is een tuyeaux vraagje:

Code: Select all

Zie p.43, 2de bullet:

(a) Geef aan hoe NonEmpty[l] eenvoudig genitialiseerd kan worden, gegeven de lexografisch

geordende koppels (j, sij ).

(b) Hoe kom je aan die O(m + ltot)?

[Shinta]

Nog is een tuyeaux vraagje:

Code: Select all

Zie p.43, 2de bullet:

(a) Geef aan hoe NonEmpty[l] eenvoudig genitialiseerd kan worden, gegeven de lexografisch

geordende koppels (j, sij ).

(b) Hoe kom je aan die O(m + ltot)?

Kga sbiet beginne alle tuyauxs probere op te lossen beginnende met die van 2006/2007. Kzal de resultate dan wel poste zodawe die kunne bespreke.

[Norfolk]

Nog is een tuyeaux vraagje:

Code: Select all

Zie p.43, 2de bullet:

(a) Geef aan hoe NonEmpty[l] eenvoudig genitialiseerd kan worden, gegeven de lexografisch

geordende koppels (j, sij ).

(b) Hoe kom je aan die O(m + ltot)?

deze is wel easy he

a) je steekt voor elke (j, sij), en stel dat sij = ak, de k in NonEmpty[j]. Zorg wel dat je dat in volgorde doet en steeds vanachter toevoegd en dat je geen dubbele toevoegt, maar dat is eenvoudig te checken aangezien deze achter elkaar staan.

b) Dat sorteren komt overeen met de eerste versie die je zag met radix sort. Dus daar was de complexiteit gelijk aan O(m + n). Aangezien de input (en dus n) hier gelijk is aan ltot, is het nu O(m + ltot).

[Robbe]

p107, 3-CNF

Is 3-CNF ook logisch equivalent met CNF, want dat vind ik precies maar niet.

p116, constructie van Vertex Cover naar Hamiltonian Circuit

die constructie is allemaal goed en wel, maar wat heeft dit nu juist te maken met een Hamiltionian circuit?

[Norfolk]

p. 60:

Bij de formule van T(n) <= c * n + (1/n) * ...
Waar komt die 1/n en die c*n vandaan? Die 1/n komt van dat je 1 uit n neemt denk ik, maar dan dacht ik dat die ook bij die c * n zou moeten...

[Shinta]

p107, 3-CNF

Is 3-CNF ook logisch equivalent met CNF, want dat vind ik precies maar niet.

p116, constructie van Vertex Cover naar Hamiltonian Circuit

die constructie is allemaal goed en wel, maar wat heeft dit nu juist te maken met een Hamiltionian circuit?

Ja die zijn logisch equivalent, je kan elke uitdrukking opsplitsen zodat ze in 3-CNF zijn. Het zijn eigenlijk dezelfde problemen in een ander jasje. Er staat in de cursus wel ni wage moet doen age minder dan drie literals hebt in uw disjunctieve expressie maar da kunde zelf wel uitvinden he .

Awel :p gebt uwe VC, en A, B, C en D zijn de vier componenten van 1 knoop van uw HC, en in die reductie zegde eigenlijk dage elke ongerichte knoop van uw VC kunt simuleren als een knoop van uw (gerichte) HC omdat in uw HC elke knoop moet bezocht worden, en dit geldt ook voor uw HC.

[Shinta]

p. 60:

Bij de formule van T(n) <= c * n + (1/n) * ...
Waar komt die 1/n en die c*n vandaan? Die 1/n komt van dat je 1 uit n neemt denk ik, maar dan dacht ik dat die ook bij die c * n zou moeten...

c*n is de tijd nodig om je elementen te verdelen, de rest van de uitdrukking is het gemiddelde van al de mogelijke opties van keuzes voor het pivot-element.

Kga vanavond men oplosingen van de tuyauxs inscanne, kvin de driver ni zo de scanner dus..

[filippeesje]

Bij het bewijs van de stelling van Cook, de constructie van de booleaanse uitdrukking w_s, hoe kom je daar juist aan de lengtes van de delen van die uitdrukkingen

In het stukje ervoor staat er dat U(x1, x2, .. xl) lengte O(l^2) heeft, hoe komt je dan aan lengte O(p(n)) voor 1, O(p^3(n)) voor 2 en O(p^2(n)) voor 3?

[Shinta]

Op blz 29 staat dat er een polynomiaal verband bestaat tussen de tijdscomplexiteit op RAM en DTM als men het logaritmisch kost criterium gebruikt. Waarom lukt dit niet voor het uniform kost criterium ?

Op pagina 30 die stelling zegt men ook dat M', M simuleert met T'(n) in O(T^3(n)) voor het logaritmische criterium, wat is dan de big oh voor het uniform kost criterium ?

[Shinta]

Bij het bewijs van de stelling van Cook, de constructie van de booleaanse uitdrukking w_s, hoe kom je daar juist aan de lengtes van de delen van die uitdrukkingen

In het stukje ervoor staat er dat U(x1, x2, .. xl) lengte O(l^2) heeft, hoe komt je dan aan lengte O(p(n)) voor 1, O(p^3(n)) voor 2 en O(p^2(n)) voor 3?

je vergelijkt iets van compleet verschillende lengtes he, aan de ene kant heb je x1 ... xl, aan de andere kant heb je (voor 1) T0,t .. Tr,t, en het is misschien niet zo dat r gelijk is aan l he (het kan wel ). Daarbij nog: met p(n) een polynoom.

[filippeesje]

Is het dan iets als:
- voor 1: O(r^2 * p(n)) = O(p(n))
- voor 2: O(p^2(n) * p(n)) = O(p^3(n))
- voor 3: O(m^2 * p(n) * p(n)) = O(p^2(n))

PS: ik snap hier de ballen van dus slaagt me ni dood als ik volkomen verkeerd zit .

[Shinta]

Is het dan iets als:
- voor 1: O(r^2 * p(n)) = O(p(n))
- voor 2: O(p^2(n) * p(n)) = O(p^3(n))
- voor 3: O(m^2 * p(n) * p(n)) = O(p^2(n))

PS: ik snap hier de ballen van dus slaagt me ni dood als ik volkomen verkeerd zit .

Euh da zouk nu ni zo zeggen, het is gewoon zo dat kwadratische, en hogere machtsfuncties allemaal ook polynomiale functies zijn.

[slimmy]

en op blz staat dat het in O(T^3) gesimuleerd word, en daar onder staat het bewijs zonder mult en DIV instructies, en da's dan T^2, hoe komt ge uiteindelijk aan die T^3, want da staat nergens bewezen

[Shinta]

en op blz staat dat het in O(T^3) gesimuleerd word, en daar onder staat het bewijs zonder mult en DIV instructies, en da's dan T^2, hoe komt ge uiteindelijk aan die T^3, want da staat nergens

mult zal ook O(T) nemen he dus als je een programma hebt me almaal mults heeft da meer nodig

[Norfolk]

Op blz 29 staat dat er een polynomiaal verband bestaat tussen de tijdscomplexiteit op RAM en DTM als men het logaritmisch kost criterium gebruikt. Waarom lukt dit niet voor het uniform kost criterium ?

Op pagina 30 die stelling zegt men ook dat M', M simuleert met T'(n) in O(T^3(n)) voor het logaritmische criterium, wat is dan de big oh voor het uniform kost criterium ?

Voor p 30: die stelling kan nooit gelden voor uniform kost criterium

p 29: Die stelling lukt wel voor uniform. Maar omdat de stelling van p30 niet lukt voor uniform dan kunnen we niet van een polynomiaal verband hiertussen spreken.