USA - Udajove struktury a algoritmy

[ApokalypS]

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]

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

[ApokalypS]

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

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]

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

[JCube]

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]

nerobi niekto tahak?resp prednasky v doc

[kOsTi]

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

[Sooloni]

nema nekto kluc na cvika USA v moodli?

[doc.returner]

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

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

[doc.returner]

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

[ApokalypS]

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

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

Code [Select] Expand

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]

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

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

[Corse]

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]

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]

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]

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]

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]

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]

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

[SSPPYY]

A co takto vytvorenie OPTIMALNEHO BVS?
Tomu chape niekto?

[Guisseppe]

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]

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]

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]

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]

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