Odpovědi k otázkám

[the21st]

c)? Mně přijde, že když se podívám na příklad automatu v knížce Úvod do teoretické informatiky, vidím protipříklad.

Tak sa s nami skus o ten protipriklad podelit, snad to nejak vyriesime.

[janoro]

OK fajn, jedná se o otázku číslo 7:
Stav S1 odpovídá prefixu P1 vzoru V1 a S2 prefixu V2 vzoru V2. Pro nějaké písmeno x je G(S1, x) = S2. Potom

a) délka P1 je vždy menší než délka P2, jejich rozdíl může být libovolný kladný celočíselný

b) délka P1 je vždy menší nebo rovná délce P2, jejich rozdíl může být libovolný nezáporný

c) délka P1 je vždy o 1 menší než délka P2 - bylo označeno jako správná odpověď

d) délka P1 se vždy rovná délce P2

Teď k tomu příkladu, no podívejte se sami
http://imgupload.cz/s5/CIhsNXTPJ8.jpg
Vezměmě stav 7. Stav 7 "vrací" automat na stav 3. Tam to neplatí, nebo mi něco nedochází?

[the21st]

Asi si to uplne nepochopil - G nie je failure funkcia. F je failure funkcia.
G je funkcia ktora ta posuva hlbsie do stromu (tj. z nejakeho uzla do jeho syna) podla toho kde si a ake si nasiel pismeno. F sa zavola ak ta to pismeno nevie posunut hlbsie.

Cize ten automat znazornuje funkciu F, a nie G. Funkcia G je de facto priamo ten strom, ktory sa stavia v predspracovani.

(Druha vec: daj si pozor na tie oznacenia P1, S1, P2, S2. Ak si pozorne precitas tu otazku, zistis ze funkcii G je zadany stav S1 (ku ktoremu prislucha prefix P1), a jeho vysledkom je stav S2 (ku ktoremu prislucha prefix P2). To znamena, ze ak by G bola failure funkcia, tak dlzka P2 by mala byt mensia ako P1 - a taka moznost v odpovediach ani nie je. Vravim to preto, lebo som si toto sam najprv tiez nevsimol, a intuitivne som si P1 a P2 zamenil.)

[JiriD]

Voronoi
1a
2c
3a
4a
5a
6c pokud je v zadání překlep, v možnostech a), b), c) místo Beta psát Gamma .. psal jsem Kučerovi, čekám na odpověď...pokud tam není překlep, tak nevím
7a
8c
9c

[the21st]

Update.
Co sa tyka voronoi, zhoduju sa s JiriD.

[Návštěvník]

Muze mi nekdo rict co je to za otazky? Diky

[JiriD]

Muze mi nekdo rict co je to za otazky? Diky

http://kam.mff.cuni.cz/~ludek/pisemkaADS.pdf

[JPS18]

Preco pri Voronoi je 5.a a nie 5.d. Mne sa zda ze sa neukonci ziadny segment a zacne vznikat jeden novy viz Algovision>Voronoi>degenerovany priklad 2, ak tomu dobre rozumiem co je segment.
Ale zrejme neviem ze co je segment je to oblast alebo ta usecka co sa kresli medzi oblukmi alebo co .. .

[JiriD]

Preco pri Voronoi je 5.a a nie 5.d. Mne sa zda ze sa neukonci ziadny segment a zacne vznikat jeden novy viz Algovision>Voronoi>degenerovany priklad 2, ak tomu dobre rozumiem co je segment.
Ale zrejme neviem ze co je segment je to oblast alebo ta usecka co sa kresli medzi oblukmi alebo co .. .

Jestli jsem správně pochopil ty doprovodné texty k algovizi, je segment ta úsečka.

[Petr Kalný]

binární sčítání, otázka 1.:
proč myslíte, že je správně za b), tedy že je potřeba logN paralelních kroků s N log N operacemi? Proč operací není jen N?

otázka 2.:
v odpovědích je napsáno c), tomu vůbec nerozumím. Nebo to mam brát tak, že c0 znám? Pokud ano tak pak je to banální...

[JiriD]

binární sčítání, otázka 1.:
proč myslíte, že je správně za b), tedy že je potřeba logN paralelních kroků s N log N operacemi? Proč operací není jen N?

Důležitý slovo je "celkově". Jestli tu větu dobře chápu, dá se odpověď b) přepsat do tvaru:
O(log N) paralelních kroku. Celková složitost algoritmu je O(N log N). ale neplatí a)

[the21st]

otázka 2.:
v odpovědích je napsáno c), tomu vůbec nerozumím. Nebo to mam brát tak, že c0 znám? Pokud ano tak pak je to banální...

Poznas a₀ a b₀, a z toho vies zistit c₀

[Monty]

Jsem si vsiml, ze v zadani u VII.Scitani je napsano, ze paralelni krok je vykonani maximalne 8 operaci...tudiz si myslim, ze u 2.otazky obecne nebude stacit jeden paralelni krok na urceni souctu. Nebo se snad pletu?

[the21st]

Jsem si vsiml, ze v zadani u VII.Scitani je napsano, ze paralelni krok je vykonani maximalne 8 operaci...tudiz si myslim, ze u 2.otazky obecne nebude stacit jeden paralelni krok na urceni souctu. Nebo se snad pletu?

U 2. otazky potrebujes vykonat 2 paralelne XORy. A to je menej ako 8 paralelnych operacii. Teda aspon tak som to pochopil ja.

[Monty]

U 2. otazky potrebujes vykonat 2 paralelne XORy. A to je menej ako 8 paralelnych operacii. Teda aspon tak som to pochopil ja.

Pouziti dvou XORu myslis takhle: a_i XOR b_i XOR c_i-1 ...ale podle me se toto provadi N-krat