Udajove struktury a algoritmy

[jardo]

nemohla by tu niejaka dobra a mudra dusa dat aj spravne odpovede?

[jardo]

a este jedna otazocka, to okrem klikacky na moodli boli aj niejake tereticke otazky ktore trebalo rozpisovat

[Matejus]

podla tych textakov to mam chapat tomu tak , ze bolo len 10 otazok v kazdom teste ?

[tuxik]

podla tych textakov to mam chapat tomu tak , ze bolo len 10 otazok v kazdom teste ?

ano na zapoctovke. Na skuske bude 30 otazok po 2 body ak ma pamat neklame

[hudyy]

ja som pocul take ze 20 po 3 body

[Matejus]

5
Známky: 1
Binárny vyhľadávací strom (BVS) je usporiadaný stratégiou:
Vyberte aspoň jednu odpoveď.
a. Inorder    **
b. Postorder    
c. inou    
d. Preorder    

- podla mna INORDER nie je spravna odpoved, ved si precitajte toto (http://www.sprite.edi.fmph.uniba.sk/~szorad/BPS/Preorder.html):
Prechod stromu pomocou preorderu a zároveň vkladanie hodnôt do nového stromu je častá technika na vytvorenie úplnej kópie binárneho stromu.

- takisto aj prva veta tu hovori: http://www.sprite.edi.fmph.uniba.sk/~szorad/BPS/Vkladanie.html
Vkladanie a vymazávanie vrcholov v binárnom strome sú operácie, ktoré menia túto dynamickú množinu. Preto treba zabezpečiť, aby sa aj po ich vykonaní zachovali vlastnosti binárneho prehľadávacieho stromu. Časová zložitosť oboch operácií je O(h), kde h je hĺbka stromu.
- a v teste je odpoved toto:
1
Známky: 1
Pri použití hašovania je vloženie n prvkov (operácia INSERT), najhoršom prípade vykonané v čase:
Vyberte aspoň jednu odpoveď.

a. T(n) = O(log n)    
b. T(n) = O(n)    
c. T(n) = O(n logn)    
d. T(n) = O(n2)    **

KTO VYPRACOVAL TIE "SPRAVNE" ODPOVEDE ? ci to len od brucha dakto tipoval ?

[kamelot]

Pri použití hašovania je vloženie n prvkov (operácia INSERT), najhoršom prípade vykonané v čase:
Vyberte aspoň jednu odpoveď.

a. T(n) = O(log n)    
b. T(n) = O(n)    
c. T(n) = O(n logn)    
d. T(n) = O(n2)    **

toto je dobre, ma byt O(n^2)

[markus]

inak pozor... v tych txtckach je jeden subor s odpovedami a dalsimi s opravenymi odpovedami:) este som to nekontroloval ale ci nahodou nepozerata zle....

taaakze dorobil som do vokiho skript este aj poznamky z UNIBa.... su tam veci aj navyse co sme nepreberali ale kedze toho nieje vela rozhodol som sa to tam dat kto chce si pozrie kto nie bude na to srat:)

Code [Select] Expand

http://www.upnito.sk/download.php?dwToken=1cfddcd022e2cc5ea0d34dcc2f5ef028

[MorFiuM]

netusite aka je tu spravna odpoved? pozrel som ana ftp, ale nezda sa mi to, co znamena ze od adresy j ?

Code [Select] Expand

Aká je logaritmická cena inštrukcie ADD *i stroja RASP umiestnenej v pamäti od adresy j?
Vyberte aspon jednu odpoved.
a. žiadna z uvedených
b. l(j)+l(c(i))+l(c(c(i)))
c. l(c(0))+l(i)+l(c(i))+l(c(c(i)))
d. l(c(0))+l(i)+l(c(i))

na nete som nasiel toto:

Code [Select] Expand

Záver: Majme program RAM s časovou zložitosťou TRAM(n), potom sa nájde program RASP taký, že jeho časová zložitosť bude c.TRAM(n), t.j.TRASP(n) = O(TRAM(n)).
Záver: Kedykoľvek máme program v jazyku RASP s časovou zložitosťou TRASP(n), potom sa nájde program v jazyku RAM, ktorý je ekvivalentný programu v jazyku RASP a jeho zložitosť TRAM(n) = k.TRASP(n), t.j. TRAM(n) = O(TRASP(n)).
Veta: Stroje RAM a RASP sú z hľadiska zložitosti ekvivalentné.

tym padom by podla mna mala byt spravna odpoved C, lebo zlozitost je taka ista ako u RAM stroja.

[Patto]

5
Známky: 1
Binárny vyhľadávací strom (BVS) je usporiadaný stratégiou:
Vyberte aspoň jednu odpoveď.
a. Inorder    **
b. Postorder    
c. inou    
d. Preorder    

- podla mna INORDER nie je spravna odpoved, ved si precitajte toto (http://www.sprite.edi.fmph.uniba.sk/~szorad/BPS/Preorder.html):
Prechod stromu pomocou preorderu a zároveň vkladanie hodnôt do nového stromu je častá technika na vytvorenie úplnej kópie binárneho stromu.

- takisto aj prva veta tu hovori: http://www.sprite.edi.fmph.uniba.sk/~szorad/BPS/Vkladanie.html
Vkladanie a vymazávanie vrcholov v binárnom strome sú operácie, ktoré menia túto dynamickú množinu. Preto treba zabezpečiť, aby sa aj po ich vykonaní zachovali vlastnosti binárneho prehľadávacieho stromu. Časová zložitosť oboch operácií je O(h), kde h je hĺbka stromu.
- a v teste je odpoved toto:
1
Známky: 1
Pri použití hašovania je vloženie n prvkov (operácia INSERT), najhoršom prípade vykonané v čase:
Vyberte aspoň jednu odpoveď.

a. T(n) = O(log n)    
b. T(n) = O(n)    
c. T(n) = O(n logn)    
d. T(n) = O(n2)    **

KTO VYPRACOVAL TIE "SPRAVNE" ODPOVEDE ? ci to len od brucha dakto tipoval ?

no jo ale tam v tom texte od uniba spominaju asi priemernu zlozitost ze je O(n) a v otazke sa pytaju na najhorsi pripad a to je asi O(n2)

netusite aka je tu spravna odpoved? pozrel som ana ftp, ale nezda sa mi to, co znamena ze od adresy j ?

Code [Select] Expand

Aká je logaritmická cena inštrukcie ADD *i stroja RASP umiestnenej v pamäti od adresy j?
Vyberte aspon jednu odpoved.
a. žiadna z uvedených
b. l(j)+l(c(i))+l(c(c(i)))
c. l(c(0))+l(i)+l(c(i))+l(c(c(i)))
d. l(c(0))+l(i)+l(c(i))

na nete som nasiel toto:

Code [Select] Expand

Záver: Majme program RAM s časovou zložitosťou TRAM(n), potom sa nájde program RASP taký, že jeho časová zložitosť bude c.TRAM(n), t.j.TRASP(n) = O(TRAM(n)).
Záver: Kedykoľvek máme program v jazyku RASP s časovou zložitosťou TRASP(n), potom sa nájde program v jazyku RAM, ktorý je ekvivalentný programu v jazyku RASP a jeho zložitosť TRAM(n) = k.TRASP(n), t.j. TRAM(n) = O(TRASP(n)).
Veta: Stroje RAM a RASP sú z hľadiska zložitosti ekvivalentné.

tym padom by podla mna mala byt spravna odpoved C, lebo zlozitost je taka ista ako u RAM stroja.

hej ved je ekvivalentny, ale zda sa mi, ze v RASP sa *i nepouziva ... ale vsetko ostatne by malo byt rovnake ako pri ram ...

[kamelot]

Binárny vyhľadávací strom (BVS) je usporiadaný stratégiou:
Vyberte aspoň jednu odpoveď.
a. Inorder    **
b. Postorder    
c. inou    
d. Preorder    

prave som sa docital ze BVS su usporiadene inorder-om... takze je to ok

[Patto]

Inac toto sa mi nezda byt dobre:

2
Známky: 1
Pre metódu Divide-and-conquer je charakteristické:
Vyberte aspon jednu odpoved.
   **a. Použitie rekurzie    
   **b. Postup zhora-nadol (Od problému k elemntárnym podproblémom)    
   **c. Použitie iterácie    
   d. Casté použitie aritmetickej operácie delenia    
   e. Postup zdola-nahor (Od elementárnych podproblémov k celkovému problému)    

podla mna to maju byt odpovede: a.,e. ... ved D&C je zdola nahor (od podproblemov k celkovemu problemu) nie???

[Matejus]

Inac toto sa mi nezda byt dobre:

2
Známky: 1
Pre metódu Divide-and-conquer je charakteristické:
Vyberte aspon jednu odpoved.
   **a. Použitie rekurzie    
   **b. Postup zhora-nadol (Od problému k elemntárnym podproblémom)    
   **c. Použitie iterácie    
   d. Casté použitie aritmetickej operácie delenia    
   e. Postup zdola-nahor (Od elementárnych podproblémov k celkovému problému)    

podla mna to maju byt odpovede: a.,e. ... ved D&C je zdola nahor (od podproblemov k celkovemu problemu) nie???

divide & conquer pozostáva z nasledujúcich častí:
a) Rozdelenie problému na časti (divide).
b) Rekurzívne vyriešenie každého z podproblémov (conquer). Ak je problém dostatočne malý, vyriešime ho nerekurzívne.
c) Spojenie riešení podproblémov do riešenia pôvodného problému (combine).

[Patto]

no to som si cital ale co si tym chcel povedat? ze je to spravne alebo nie? ... ja uz neviem vsade citam inak

[keckus]

netusite aka je tu spravna odpoved? pozrel som ana ftp, ale nezda sa mi to, co znamena ze od adresy j ?

Code [Select] Expand

Aká je logaritmická cena inštrukcie ADD *i stroja RASP umiestnenej v pamäti od adresy j?
Vyberte aspon jednu odpoved.
a. žiadna z uvedených
b. l(j)+l(c(i))+l(c(c(i)))
c. l(c(0))+l(i)+l(c(i))+l(c(c(i)))
d. l(c(0))+l(i)+l(c(i))

na nete som nasiel toto:

Code [Select] Expand

Záver: Majme program RAM s časovou zložitosťou TRAM(n), potom sa nájde program RASP taký, že jeho časová zložitosť bude c.TRAM(n), t.j.TRASP(n) = O(TRAM(n)).
Záver: Kedykoľvek máme program v jazyku RASP s časovou zložitosťou TRASP(n), potom sa nájde program v jazyku RAM, ktorý je ekvivalentný programu v jazyku RASP a jeho zložitosť TRAM(n) = k.TRASP(n), t.j. TRAM(n) = O(TRASP(n)).
Veta: Stroje RAM a RASP sú z hľadiska zložitosti ekvivalentné.

tym padom by podla mna mala byt spravna odpoved C, lebo zlozitost je taka ista ako u RAM stroja.

pri RASP treba vzdy este uvazovat vybratie konkretnej instrukcie, kedze nemas oddelene data od programu, cize je to take iste, az na to, ze na zaciatku este musi byt l(adresa instrukcie) co by bolo v tomto pripade l(j) , lenze pri *i je to uplna blbost, lebo RASP stroj to nepodporuje

[Matejus]

no to som si cital ale co si tym chcel povedat? ze je to spravne alebo nie? ... ja uz neviem vsade citam inak

no ze podla toho co som precital by mali byt spravne odpovede na otazku:

Pre metódu Divide-and-conquer je charakteristické:
   a. Použitie rekurzie       
   c. Použitie iterácie   
   e. Postup zdola-nahor (Od elementárnych podproblémov k celkovému problému)   

[radix]

Binárny vyhľadávací strom (BVS) je usporiadaný stratégiou:
Vyberte aspoň jednu odpoveď.
a. Inorder    **
b. Postorder    
c. inou    
d. Preorder    

prave som sa docital ze BVS su usporiadene inorder-om... takze je to ok

jop na foliach to bolo tusim

[domino3d]

Inac toto sa mi nezda byt dobre:

2
Známky: 1
Pre metódu Divide-and-conquer je charakteristické:
Vyberte aspon jednu odpoved.
   **a. Použitie rekurzie    
   **b. Postup zhora-nadol (Od problému k elemntárnym podproblémom)    
   **c. Použitie iterácie    
   d. Casté použitie aritmetickej operácie delenia    
   e. Postup zdola-nahor (Od elementárnych podproblémov k celkovému problému)    

podla mna to maju byt odpovede: a.,e. ... ved D&C je zdola nahor (od podproblemov k celkovemu problemu) nie???

divide & conquer pozostáva z nasledujúcich častí:
a) Rozdelenie problému na časti (divide).
b) Rekurzívne vyriešenie každého z podproblémov (conquer). Ak je problém dostatočne malý, vyriešime ho nerekurzívne.
c) Spojenie riešení podproblémov do riešenia pôvodného problému (combine).

toto je kokotina da sa to rovnako pochopit, ktore je spravne? ono  si rekurzivne rozdeli problem na male a potom ich nerekurzivne vyriesi a nakoniec spoji vysledok, vsak? opravte ma ak ne, a teraz ktora odpoved je ta dobra co som napisal, alebo ja neeviem uz mix mam z toho v hlave

[ivo261as]

správne je podla mňa použitie rekurzie a postup zhora nadol. Pozrite napr. na algoritmus MAXMIN, naprv veľké pole rozdelí na menšie pole a to spracuje rekurzívnym volaním seba a ak je veľkosť poľa 1 alebo 2 tak určí minimum a maximum (elementárny podproblém)

[timwood]

Divide&Conquer pouziva zakladnu vlastnost rekurzie: rozdelenie problemu na konecny pocet podproblemov rovnakeho typu a spojenie dielcich rieseni pre najdenie riesenia obecneho. [Algoritmy: P.Wroblewski]

[byglajs]

Počujte a tá iterácia je na čo dobrá ? Veď nepotrebujem prechádzať prvky jeden po druhom , keď sa to už rozdelí. viď. Quicksort

[Matejus]

aj ja som si to myslel ... clovek aby zhanal 5 roznych skript aby si utvrdil jednoduchu informaciu. OMG ... SNP (system nap***)

[domino3d]

no ja zajtra nespravim.........        zase 

SNP rulez

[Matejus]

preco si tak "fandis" ? uz si snad robil, ze hovoris ZASE ....

[Melkor]

matejus.... nie zeby si sa ucil, ale pises tu somariny