[A&C]Enkele vragen

[Norfolk]

Als ik op p 68 het bewijs probeer te geven voor die T(n) per inductie, dan kom ik totaal niet op wat die in klas had uitgewerkt?!
Op het moment dat je die twee sommaties omzet naar zo'n breukstreep, dan kom ik uit op


waardoor ik uitkom op
k = (n + 1)/2

In les kwam hij uit op
1/2 ( n² -n+2nk - 2k² )
waardoor
k = n / 2

Kan iemand dat eens narekenen en zien wat ik eventueel fout deed (of zijn berekening posten, dan kan ik tenminste zien wat ik fout deed)

[Norfolk]

Op p. 89 staat:

Aangezien men begint met i = 0, wordt de body van de while-lus, i := f(i), ten hoogste l keer uitgevoerd.

Daaruit concluderen we dat dat van de orde O(l) is. Ik zou eerder zeggen O(l^2) aangezien je for-lus l keer doet, en de while lus ook l keer doet :s
Waarom is dit maar O(l)?

[slimmy]

Kan iemand dat eens narekenen en zien wat ik eventueel fout deed (of zijn berekening posten, dan kan ik tenminste zien wat ik fout deed)

kan er iemand ineens heel da bewijs geven? want ik geraak daar maar ni mee weg

[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 ?

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.

Ma waarom KAN die ni gelden op p 30 :p

[Shinta]

Als ik op p 68 het bewijs probeer te geven voor die T(n) per inductie, dan kom ik totaal niet op wat die in klas had uitgewerkt?!
Op het moment dat je die twee sommaties omzet naar zo'n breukstreep, dan kom ik uit op


waardoor ik uitkom op
k = (n + 1)/2

In les kwam hij uit op
1/2 ( n² -n+2nk - 2k² )
waardoor
k = n / 2

Kan iemand dat eens narekenen en zien wat ik eventueel fout deed (of zijn berekening posten, dan kan ik tenminste zien wat ik fout deed)

Ja kunde ff da bewijs geve zoals in de les want keb da ni opgeschreve gehad :p.

[Shinta]

Op p. 89 staat:

Aangezien men begint met i = 0, wordt de body van de while-lus, i := f(i), ten hoogste l keer uitgevoerd.

Daaruit concluderen we dat dat van de orde O(l) is. Ik zou eerder zeggen O(l^2) aangezien je for-lus l keer doet, en de while lus ook l keer doet :s
Waarom is dit maar O(l)?

Hmm eigenlijk wel, maar alsget van een ander oogpunt bekijkt, dan was er in de les gezegd dat de automaat (die gesimuleerd wordt door dat algoritme) ten hoogste n stappen neemt, dus het algoritme hangt al zeker af van O(n), maar die while is ook belangrijk, omdat dat aangeeft hoe vaak uw algoritme backtrackt, en dit is maximaal l keer (maar het is bijna nooit zo veel dus) dus daarom is de complexiteit O(l+n). Ik denk dat het niet O(l*n) is om dezelfde reden dat bij de oefeningen van reeks 5 oefening 2c waar de complexiteit ook maar O(n+log m) is, enkel is bij ons de log m gelijk aan l.

[Shinta]

Kzal nog ma ne keer op men eige replyen.

Als je een algoritme krijgt me een paar for en while lussen en ge wordt gevraagd om daar de uniforme, logaritmische plaats en tijdscomplexiteit van te berekenen. Wa moete dan doen:

1) Alles omzetten naar RAM/RASP en dat daar van berekenen ?
2) Gewoon met algoritme werken zodat een instructie voor het uniforme 1 tijdseenheid kost en elke variabele/geheugenplaats 1 eenheid, en voor de logaritmische plaatscomplexiteit de som van alle maximale groottes in alle gebruikte geheugenplaatsen en voor tijdscomplexiteit, euh, meer tijd vo IO ?...

Want aget volgens puntje 2 doet wete ni wa in de registers staat he dus dan moete me gebruikt geheuge werke enzo..

[Norfolk]

Als ik op p 68 het bewijs probeer te geven voor die T(n) per inductie, dan kom ik totaal niet op wat die in klas had uitgewerkt?!
Op het moment dat je die twee sommaties omzet naar zo'n breukstreep, dan kom ik uit op


waardoor ik uitkom op
k = (n + 1)/2

In les kwam hij uit op
1/2 ( n² -n+2nk - 2k² )
waardoor
k = n / 2

Kan iemand dat eens narekenen en zien wat ik eventueel fout deed (of zijn berekening posten, dan kan ik tenminste zien wat ik fout deed)

Ja kunde ff da bewijs geve zoals in de les want keb da ni opgeschreve gehad :p.

Basis:
n = 1: ok
Inductiestap:
(Stel we weten T(r) <= 4c * r voor r < n)
T(n) <= c * n + (4c / n)(max_k(som_n-k+1^n-1(i) + som_k^n-1(i)))

(max_k(som_n-k+1^n-1(i) + som_k^n-1(i)))
(som_a^b(i) = 1/2 (b - a + 1) (a + b))
= (1/2) (n^2 - n + 2nk - 2k^2)

maximum als k = n/2
k ingevuld geeft:
= (1/2) (n^2 - n + n^2 - n^2 / 2) < 3n^2 / 4
<= c * n + (4c / n) (3n^2 / 4)
<= c * n + 3cn
<= 4 c n

[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.

Ma waarom KAN die ni gelden op p 30 :p

Omdat ge op p 31 zegt dat de band nooit langer kan worden dan O(T(n)).

[Shinta]

Das gewoon in de les gezegd denkik da n/2 het optimaalste is ...

Kheb da bewijs ook eens uitgewerkt en behalve enkele keren wa foefelen kommek wel et juiste uit.

[slimmy]

Bij randomized algorithms, ik begrijp toch dat algoritme voor Min-Cut ni zenne. :S kan er iemand da uitleggen?

[Shinta]

Bij randomized algorithms, ik begrijp toch dat algoritme voor Min-Cut ni zenne. :S kan er iemand da uitleggen?

kvin die min-cut ok mor iet vreemd.
Tgeen dage dus eigenlijk wilt doen is herhaaldelijk 2 verschillende nodes samenmergen tot 1 en dan die pijlen behouden. En dat herhaalt ge dan tot ge ni meer kunt..

of zoiets.

[Norfolk]

Nog iets da we ni moeten kennen, van die 127-en verder, zijn er geen oefeningen, moeten we dat dan kennen?

ja da moete we denkik wel kenne, enkel H4 ni

p 119 tot 126 hebben we toch niet gezien in les? Dus dat zult ge ook niet moeten kennen he?

[slimmy]

Nog iets da we ni moeten kennen, van die 127-en verder, zijn er geen oefeningen, moeten we dat dan kennen?

ja da moete we denkik wel kenne, enkel H4 ni

p 119 tot 126 hebben we toch niet gezien in les? Dus dat zult ge ook niet moeten kennen he?

oef

[Robbe]

Nog iets da we ni moeten kennen, van die 127-en verder, zijn er geen oefeningen, moeten we dat dan kennen?

ja da moete we denkik wel kenne, enkel H4 ni

p 119 tot 126 hebben we toch niet gezien in les? Dus dat zult ge ook niet moeten kennen he?

NOW he tells us