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)?
Moderator: Praesidium
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.slimmy wrote: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 heslimmy wrote: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)?
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 .Robbe wrote: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?
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.Norfolk wrote: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...
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 wrote: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?
Euh da zouk nu ni zo zeggen, het is gewoon zo dat kwadratische, en hogere machtsfuncties allemaal ook polynomiale functies zijn.filippeesje wrote: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 .
mult zal ook O(T) nemen he dus als je een programma hebt me almaal mults heeft da meer nodigslimmy wrote: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
Voor p 30: die stelling kan nooit gelden voor uniform kost criteriumShinta wrote: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 ?
Users browsing this forum: No registered users and 2 guests