• Welcome to TUKE FÓRUM - Fórum pre študentov Technickej Univerzity v Košiciach.
 

Udajove struktury a algoritmy

Started by deCode666, 16.02.2009, 14:38:26

« predchdzajce - alie »

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

Quote from: Matejus on  28.05.2009, 15:14:23
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

#180
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

Quote from: Matejus on  28.05.2009, 17:44:05
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)

while (2*2 == 5) { echo "If you're reading this, something is definitely wrong"; }

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:)

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

MorFiuM

Quote from: Domino3D on  28.05.2009, 03:31:49
netusite aka je tu spravna odpoved? pozrel som ana ftp, ale nezda sa mi to, co znamena ze od adresy j ?
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:
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

Quote from: Matejus on  28.05.2009, 17:44:05
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)

Quote from: MorFiuM on  28.05.2009, 18:05:24
Quote from: Domino3D on  28.05.2009, 03:31:49
netusite aka je tu spravna odpoved? pozrel som ana ftp, ale nezda sa mi to, co znamena ze od adresy j ?
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:
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

Quote from: Matejus on  28.05.2009, 17:44:05
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

while (2*2 == 5) { echo "If you're reading this, something is definitely wrong"; }

Patto

Inac toto sa mi nezda byt dobre:

Quote2
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

Quote from: Patto on  28.05.2009, 18:31:55
Inac toto sa mi nezda byt dobre:

Quote2
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

#189
Quote from: MorFiuM on  28.05.2009, 18:05:24
Quote from: Domino3D on  28.05.2009, 03:31:49
netusite aka je tu spravna odpoved? pozrel som ana ftp, ale nezda sa mi to, co znamena ze od adresy j ?
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:
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

Quote from: Patto on  28.05.2009, 18:59:05
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

Quote from: kamelot on  28.05.2009, 18:23:28
Quote from: Matejus on  28.05.2009, 17:44:05
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

Quote from: Matejus on  28.05.2009, 18:46:11
Quote from: Patto on  28.05.2009, 18:31:55
Inac toto sa mi nezda byt dobre:

Quote2
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
vivat academicus

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)
If you can't finish your work in 24 hours, work at night.
http://www.utfg.net/

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

#197
no ja zajtra nespravim.........    :ohmigod:    zase  :ohmigod:

SNP rulez
vivat academicus

Matejus

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

Melkor

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