Author Topic: USA - Udajove struktury a algoritmy (Read 88018 times)

ApokalypS · « **Reply #300 on:** 18.05.2008, 20:52:44 »

Quote from: kOsTi on 18.05.2008, 20:09:30

ak by to niekoho zaujimalo tak z PT som vyhrabal take otazky:

otazka znie, ci bude davat podobne otazky..
lebo co som zatial pocul, cital, videl.. tak by sa to malo lisit..

kOsTi · « **Reply #301 on:** 18.05.2008, 20:56:06 »

a co si take pocul, cital a videl ohladom otazok na skusku?

ApokalypS · « **Reply #302 on:** 18.05.2008, 21:01:59 »

no tak co sa tyka prikladu, tak to co tu uz bolo spomenute.. pseudokod a podobne..
a co sa tyka teorie.. niekde som to tu uz pisal..

hladam.. nasiel som..

Quote from: ApokalypS on 15.05.2008, 21:55:10

ze tie teoreticke moze byt napisany kod a vysvetlit vsetko v nom..
priklad bude napisat pseudokod alebo kod.. uz teraz je mi z toho na grc..
a aby som vas potesil este viac.. teraz v stredu je jeden termin a opravak je az 2. jula
plocica vravel, ze na dekanate tak vybavili.. a ziadne ine terminy nebudu..

takze bud teraz spravim.. alebo mam cely jun na to.. co je dost na nic..

to s tym terminom ma serie doteraz..
ale tak hadam spravim, aby som nemusel opravovat.. len donutis sa ucit je tazke.. ked je vonku tak pekne..

TradeMark · « **Reply #303 on:** 18.05.2008, 23:50:15 »

3 prednaska - posledne slajdy - formalna a semifirmalna specifikacia dacoho - WTF???

JCube · « **Reply #304 on:** 18.05.2008, 23:58:11 »

semiformalna to je niklaus wirth - v tej jeho knizke je to pekne rozobrate
formalna - to je take daco ako sme mali na FaLP tam staci spomenut ze kazda ADT ma prvky, operacie, a vlastnosti

fatalerror · « **Reply #305 on:** 19.05.2008, 05:16:12 »

nerobi niekto tahak?resp prednasky v doc

kOsTi · « **Reply #306 on:** 19.05.2008, 05:28:20 »

mas to na grande... v PT priecinku nieco podobne

Sooloni · « **Reply #307 on:** 19.05.2008, 05:28:37 »

nema nekto kluc na cvika USA v moodli?

doc.returner · « **Reply #308 on:** 20.05.2008, 19:08:18 »

Opravte ma ak je niekde chyba...

procedure PREORDER(VERTEX):
begin
LABEL[VERTEX] <- COUNT;
COUNT <- COUNT + 1;
if (LSON[VERTEX]) != 0) then PREORDER(LSON[VERTEX]);
if (RSON[VERTEX]) != 0) then PREORDER(RSON[VERTEX]);
end

procedure POSTORDER(VERTEX):
begin
if (LSON[VERTEX]) != 0) then POSTORDER(LSON[VERTEX]);
if (RSON[VERTEX]) != 0) then POSTORDER(RSON[VERTEX]);
LABEL[VERTEX] <- COUNT;
COUNT <- COUNT + 1;
end

EDIT: Jedna chyba opravena... Predtym bolo

Quote

if (RSON[VERTEX]) != 0) then POSTORDER(RSON[VERTEX]);
if (LSON[VERTEX]) != 0) then POSTORDER(LSON[VERTEX]);

doc.returner · « **Reply #309 on:** 20.05.2008, 22:44:18 »

Pozeram ze procedurka MERGE je dost blbo zrobena na prednaske...
http://en.wikipedia.org/wiki/Merge_algorithm > prednaskovy MERGE imho

ApokalypS · « **Reply #310 on:** 21.05.2008, 00:20:06 »

a o relacii "snivajte s nami" ste uz poculi..

ale k veci.. mam otazku.. k vete o dekompozicii som nasiel iba toto:

Code: [Select]

VETA O REKURZII (Dekompozícii)
Majme problém s časovou zložitosťou T(n) = a.T(n/c) + b.n	(1)
konštanty a,b,c  R+ a nech r = a/c, potom (1) má riešenie:
	r < 1	T(n) = O(n)
	r = 1	T(n) = O(n.logn)
	r > 1	T(n) = O(nloga)

co vy na to..

doc.returner · « **Reply #311 on:** 21.05.2008, 00:24:43 »

http://www.brian-borowski.com/Matrix/

Pre lepsie pochopenie Matrix Chain Multiplication (Order)...

Corse · « **Reply #312 on:** 21.05.2008, 01:14:41 »

Neviem, ci to tu uz nebolo alebo ci to nie je na ftp ale nejake sady otazok z 2006:

=============================30.5.06========================
** 1. sada

1. rekurzia a jej pouzitie na priklade
2. sekvencne subory, vlastnosti
3. nasobenie dvoch 2-bitovych cisel, nakreslit schemu

** 2. sada

1. zlozitost RAM programov
2. algoritmus HEAP sort
3. zostrojte AVL strom z cisel ... a postupne odstrante vrcholy 4,6

** 3. sada

1. zoznamy, operacie na zoznamoch, zlozitost
2. problem vyberu k-tehu najmensieho prvku, zlozitost
3. metoda PREORDER bez rekurzie

** 4. sada

1. ADT
2. optimalny BVS
3. PL jazyk na RAM nieco

=================7.6.06========================
1. Linearny aritmeticky model zlozitosti programu
2. Triedenie Porovnavanim
3. Vytvor Binarny Vyhladavaci Strom (BVS) z cisel : 14,8,16,........

1. Mnoziny a operacie na nich, struktura mnozin
2. Zoznamy, rozdieli medzi jednolivymi + operacie v nich
3. Priklad Usporiadat 16 cisel podla priameho zlucovania

1 Hashovacie funkcie, prikazy I,D,M, Hashovacie tabulka,zlozitost...
2 Metoda Devide et conquer, popisat , uvedte priklad pouzitia...
3 Priklad Napiste rekurzivny Postorder

======================23.6.06==========================

1. Zlozitost algoritmov> definujte zlozitost, miery zlozitosti, priklad
2. Radixsort (bucket)
3. Vytvorte 2-3 strom z nasledujucich cisel: 4, 2, 1, 3, 7, 6, 5

1.Rozhodovacie stromy a triedenie porovnavanim
2.PREORDER strategia znackovania/prehladavania stromov. Programov PL jazyku
3.

?

1. reprezentacia udajov pomocou stromov
2. ekvivalencia RAM a RASP programov
3. priklad, podla radix sortu zotriedit slova roznej dlzky (boli slova ako "a, ab, aac, aba, baca,
cc" no skratka nieco podobne zotriedit radixom)

1. algoritmus najdenia kostry grafu (akoze lol)
2. BVS
3. adt specifikacia US string
======================29.6.06==========================

1. Dynamicke programovanie
2. Zlucovanie Heapov/hald
3. PL, RAM a zlozitost pre 1+2+...+n

Corse · « **Reply #313 on:** 21.05.2008, 01:25:47 »

predstav si, ze tam doplnas nuly ... a ze tie nuly su mensie ako "a"

alebo najlepsie .. predstav si tam "nič"

EDIT: pozor...ty si napisal ze doplnas zlava ...ale ty musis doplnat zprava!!!

etc.: baca
cbc#
bc##
cc## ...

JCube · « **Reply #314 on:** 21.05.2008, 01:27:44 »

Quote from: Dulus on 21.05.2008, 01:22:19

Quote from: puq on 21.05.2008, 00:46:16
a ten pohla do zrkadla, je aj priklad na nekonecny cyklus
A to ma potom este treba zlozitost k tomu a je hotovo. Aspon za 20 bodov urcite

A este taka otazka. Ked sa radixom tridia cisla a mame cisla s roznym poctom cislic tak zlava doplname nuly. A ked triedime trebars slova tak potom zlava doplname co .... akoze tiez "nuly" ...nejake znaky co maju mensiu "hodnotu" ako a-cko ....alebo tam doplname a-cka .... lebo sak akoze abeceda obsahuje iba pismena a prvy "prvok" je pismeno a ....... alebo ako to tam funguje potom ??

no ten algoritmus co bol na prednaske najprv utriedil retazce podla dlzky a triedil najpr najdlhsie retazce a potom postupne pridaval do triedenia kratsie

Dulus · « **Reply #315 on:** 21.05.2008, 01:32:48 »

takze teda ... mame ..... aaa,aab,aac,aa,ab,ac,a,b,c ..... cize utriedime to ako ?? ked najprv utriedime najdlhsie tak mame aaa,aab,aac .... potom pridame kratsie ..... predpokladam ze kratsie su akoze mensie takze aa,ab,ac,aaa,aab,aac .... a teraz najkratsie a z toho mam teraz misung ... takze a,aa,ab,ac,aaa,aab,aac,b,c alebo a,b,c,aa,ab,ac,aaa,aab,aac, ....

Corse · « **Reply #316 on:** 21.05.2008, 01:37:14 »

Quote from: Dulus on 21.05.2008, 01:32:48

takze teda ... mame ..... aaa,aab,aac,aa,ab,ac,a,b,c ..... cize utriedime to ako ?? ked najprv utriedime najdlhsie tak mame aaa,aab,aac .... potom pridame kratsie ..... predpokladam ze kratsie su akoze mensie takze aa,ab,ac,aaa,aab,aac .... a teraz najkratsie a z toho mam teraz misung ... takze a,aa,ab,ac,aaa,aab,aac,b,c alebo a,b,c,aa,ab,ac,aaa,aab,aac, ....

kukni 6 prednaska P1020326.jpg tam to je bars krasne potriedene

JCube · « **Reply #317 on:** 21.05.2008, 01:38:22 »

Quote from: Dulus on 21.05.2008, 01:32:48

takze teda ... mame ..... aaa,aab,aac,aa,ab,ac,a,b,c ..... cize utriedime to ako ?? ked najprv utriedime najdlhsie tak mame aaa,aab,aac .... potom pridame kratsie ..... predpokladam ze kratsie su akoze mensie takze aa,ab,ac,aaa,aab,aac .... a teraz najkratsie a z toho mam teraz misung ... takze a,aa,ab,ac,aaa,aab,aac,b,c alebo a,b,c,aa,ab,ac,aaa,aab,aac, ....

a aa aaa aac ab ac b c

doc.returner · « **Reply #318 on:** 21.05.2008, 01:50:58 »

Ked uz sme pri tej teme - zoznamy NONEMPTY[] su len na to, aby sme vedeli ktore "nadoby" nie su prazdne, hej?

SSPPYY · « **Reply #319 on:** 21.05.2008, 02:01:56 »

A co takto vytvorenie OPTIMALNEHO BVS?
Tomu chape niekto?

Guisseppe · « **Reply #320 on:** 21.05.2008, 02:35:14 »

mohol by mi niekto vysvetlit ako sa robi AVL, trebars z cisel 4,5,7,2,1,3,6? je to v 9 prednaske odfotene na tabuli(P1020403.JPG), ale ako sa "prehadzuju" tie cisla?

buhehe · « **Reply #321 on:** 21.05.2008, 02:40:09 »

no to mas tie rotacie...LL RR LR a RL...podla toho co sa ti kde zvacsilo abo narusilo tha pouzijes rotaciu...
http://ksp.mff.cuni.cz/tasks/16/cook4.html tu su jaktak vysvetlene...

doc.returner · « **Reply #322 on:** 21.05.2008, 03:02:54 »

Quote from: Guisseppe on 21.05.2008, 02:35:14

mohol by mi niekto vysvetlit ako sa robi AVL, trebars z cisel 4,5,7,2,1,3,6? je to v 9 prednaske odfotene na tabuli(P1020403.JPG), ale ako sa "prehadzuju" tie cisla?

Skusal si uz http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm ?

kOsTi · « **Reply #323 on:** 21.05.2008, 03:04:47 »

to 1 2 3 som len tak zajebal

jasne ze keby sme pridavali postupne 1 2 3 tak by bolo

1 2
\ / \
2 -> 1 3
\
3

potom 4

2
/ \
1 3
\
4

buhehe · « **Reply #324 on:** 21.05.2008, 03:49:28 »

teraz pozeram na priklad heapsort....co ma vlastne robit? podla toho algoritmu ma vyplut nerastucu postupnost....ne neklesajucu? opravte ma ak sa mylim...

News:

Author Topic: USA - Udajove struktury a algoritmy (Read 88018 times)