Nech sa Vam v nom vsetko dari ....
KISS
streda 31. decembra 2008
streda 24. decembra 2008
Algoritmy a dátové štruktúry
Tu su nejaké zadania teoretickej časti skúšky z ADS.
1. opravny termin: (05.01.2006)
1. Definujte predpoklad uniformneho hasovania. Vymenujte tri strategie riesenia kolzii pri zatvorenom hasovani. Ktora z nich sa najviac z nich priblizuje predpokladu uniformneho hasovania? Preco?
2. B je velkost tabulky, N je pocet prvkov.
a. Najdite reprezentaciu pre otvorene hasovania, kde ocakavany cas neuspesneho vyhladavania je O(1+lg(N/B)).
b. Aky bude ocakavany cas uspesneho vyhladavania pri tejto strategii? Podrobne zdovodnite.
3. Aky moze byt maximalny rozdiel dlzok dvoch ciest od korena po list v cerveno ciernom strome? Zdovodnite.
4. Ako sa lisia minimalne a maximalne pocty prvkov, ktore mozu byt v 2-3 strome a v B strome stupna aspon t=2 vysky h? Zdovodnite.
5. Nakreslite postupnost AVL stromov, ktore vzniknu pridavanim prvkov 13, 15, 27, 7, 5, 8, 17, 13, 21, 14, 21 do prazdneho AVL stromu a naslednym odoberanim prvkov 8, 17, 14, 13, 5, 3, 15.
6. V Pascale definujte datovu strukturu pre stromovu reprezentaciu disjunktnych mnozin s operaciami UNION a FIND. Napiste nerekurzivnu funkciu FIND(x), ktora pracuje v case O(alfa(n)), kde alfa(n) je pseudoinverzna funkcia k Ackermannovej funkcii.
7. Nakreslite strukturu multilist zachytavajucu nasledovne vztahy: bicykle maju na sklade na Racianskej, Antolskej a Vazovovej; korcule maju na Racianskej a Dunajskej; sportovu obuv len na Dunajskej; sportove batohy drzia na Antolskej a Dunajskej a sportove odevy maju v sklade na Vazovovej.
8. Odhadnite pocet porovnani pri triedeni n-prvkov metodou kvadratickeho vyberu.
9. V pascale navrhnite datovu strukturu presity strom a implementujte proceduru VLOZ PRAVEHO, ktora vlozi vrchol q ako praveho syna vrcholu v. Ak vrchol v mal praveho syna, tento sa stane pravym synom vrchola q.
10. Preco nam treba dolne a horne odhady poctu porovnani optimalneho algoritmu vnutorneho triedenia a ako ich dosahujeme.
13.12.2005
1. Odvodte tesny horny odhad na uspesne vyhladavanie v hasovacej tabulke pre otvorene hasovania, ak prvky vkladame do zoznamov na zaciatok.
2. Je dana hasovacia tabulka velkosti B=13 pre zatvorene hasovanie. Vkladali sa do nej prvky v poradi 24, 7, 34, 20, 13, 8, 33, 21.
a. Zistite, aka hasovacia funkcia a aka strategia riesenia kolizii bola pouzita. Urcte prislusnu konstantu (konstanty).
b. Ako by sa tabulka zmenila, keby sme prvky vkladali v opacnom poradi?
tabulka: 13, 21, , , , , 33, 7, 34, 20, 8, 24, .
3. Ako vyzera najhorsi pripad AVL stromu s 22 vrcholmi? Nakreslite.
4. Nakreslite postupnost B-stromov s minimalnym stupnom 2, ktore vznikli postupnym vkladanim prvkov 200, 300, 100, 500, 50, 250, 450, 600, 150, 400, 270, 130, 210, 230, 70 do povodneho prazdneho stromu s naslednym vymazanim 150, 200, 300, 450.
5. Napiste proceduru, pomocou ktorej prerobite obycajny binarny strom na presity. Ich reprezentaciu si zvolte sami.
6. Aka je maximalna vyska cerveno-cierneho stromu, v ktorom je n prvkov? Dokazte.
7. Uvazujme stromovu reprezentaciu disjunktnych mnozin prvkov s operaciami UNION a FIND. Aka je casova zlozitost operacie FIND bez kompresie cesty, ak pri vykonavani operacie UNION vkladame mensiu do vacsej? Dokazte.
8. Vysvetlite, ako funguje rozkladove hasovanie a yvedte priklad jeho vyuzitia.
9. V Pascale napiste proceduru na utriedenie n-prvkoveho pola celych cisel algoritmom ShakerSort. Urcte zlozitost tohto triediaceho algoritmu.
10. Zadefinujte prislusne pojmy a vysvetlite pojmy dolneho a horneho odhadu na pocet porovnani optimalneho triediaceho algoritmu.
ADS pisomka 12.12.2006
1. Dany je binarny strom.Predpokladajme, ze mame k dispozicii nasledujuce 2 funkcie:
a)postorder(x) - vracia cislo vrchola x v postorderovskom usporiadani vrcholov daneho stromu
b)desc(x) - vracia pocet vlastnych nasledovnikov vrchola x v danom strome
Sformulujte pomocou nich vztah,ktory musi platit, ak je vrchol x nasledovnikom vrchola y v danom strome.
2. Vysvetlite ako funguje rozkladove hasovanie a uvedte priklad jeho pouzitia
3. Uvazujme zatvorene hasovanie s linearnym riesenim kolizii. Matematicky zdovodnite, preco bloky obsadenych miest maju tendenciu narastat.
4. Aka je maximalna vyska cerveno-cierneho stromu, ktory obsahuje n prvkov? Dokazte.
5. Nakreslite postupnost 2-3-stromov,ktore vzniknu vkladanim prvkov 5,10,21,33,27,12,19,15,37,17,3,18,4 do povodne prazdneho stromu a naslednym vymazanim prvkov 21,19,18.
6. Dany je B-strom minimalneho stupna t, ktory ma vysku h. Kolko prvkov moze obsahovat?
Odvodte obe hranice.
7. V Pascale zadefinujte datovu strukturu pre strommovu reprezentaciu mnozin s operaciami UNION a FIND a napiste proceduru UNION (A,B:nametype) (v Pascale), ktora zjednocuje prvky mnozin A a B tak, aby funkcia FIND(x) bez kompresie cesty bezala v case O(log2(n)), kde n je pocet prvkov ulozenych v strukture. (Funkciu FIND nemusite pisat, predpokladame, ze je taka, ako bola definovana na prednaske.)
8. Odvodte tesny horny odhad na ocakavany cas uspesneho vyhladavania v hasovacej tabulke pre otvorene hasovanie v pripade, ze prvky vkladame do zoznamov na zaciatok.
9. Vysvetlite, ako funguje algoritmus stromoveho triedenia a odvodte odhad jeho zlozitosti.
10. Nakreslite strukturu miltilist, ktora bude zachytavat nasledujuce vztahy medzi tovarmi a velkoskladmi. Bicykle maju vo velkosklade na Racianskej, na Antolskej a na Vazovovej.
Korcule maju na Racianskej a na Dunajskej. Sportovu obuv maju len na Dunajskej. Sportove batohy maju na Antolskej a Dunajskej a sportove odevy maju len na Vazovovej.
v TXT a DOC na stiahnutie tu:
http://www.subory.sk/download/211783/ADS.zip
1. opravny termin: (05.01.2006)
1. Definujte predpoklad uniformneho hasovania. Vymenujte tri strategie riesenia kolzii pri zatvorenom hasovani. Ktora z nich sa najviac z nich priblizuje predpokladu uniformneho hasovania? Preco?
2. B je velkost tabulky, N je pocet prvkov.
a. Najdite reprezentaciu pre otvorene hasovania, kde ocakavany cas neuspesneho vyhladavania je O(1+lg(N/B)).
b. Aky bude ocakavany cas uspesneho vyhladavania pri tejto strategii? Podrobne zdovodnite.
3. Aky moze byt maximalny rozdiel dlzok dvoch ciest od korena po list v cerveno ciernom strome? Zdovodnite.
4. Ako sa lisia minimalne a maximalne pocty prvkov, ktore mozu byt v 2-3 strome a v B strome stupna aspon t=2 vysky h? Zdovodnite.
5. Nakreslite postupnost AVL stromov, ktore vzniknu pridavanim prvkov 13, 15, 27, 7, 5, 8, 17, 13, 21, 14, 21 do prazdneho AVL stromu a naslednym odoberanim prvkov 8, 17, 14, 13, 5, 3, 15.
6. V Pascale definujte datovu strukturu pre stromovu reprezentaciu disjunktnych mnozin s operaciami UNION a FIND. Napiste nerekurzivnu funkciu FIND(x), ktora pracuje v case O(alfa(n)), kde alfa(n) je pseudoinverzna funkcia k Ackermannovej funkcii.
7. Nakreslite strukturu multilist zachytavajucu nasledovne vztahy: bicykle maju na sklade na Racianskej, Antolskej a Vazovovej; korcule maju na Racianskej a Dunajskej; sportovu obuv len na Dunajskej; sportove batohy drzia na Antolskej a Dunajskej a sportove odevy maju v sklade na Vazovovej.
8. Odhadnite pocet porovnani pri triedeni n-prvkov metodou kvadratickeho vyberu.
9. V pascale navrhnite datovu strukturu presity strom a implementujte proceduru VLOZ PRAVEHO, ktora vlozi vrchol q ako praveho syna vrcholu v. Ak vrchol v mal praveho syna, tento sa stane pravym synom vrchola q.
10. Preco nam treba dolne a horne odhady poctu porovnani optimalneho algoritmu vnutorneho triedenia a ako ich dosahujeme.
13.12.2005
1. Odvodte tesny horny odhad na uspesne vyhladavanie v hasovacej tabulke pre otvorene hasovania, ak prvky vkladame do zoznamov na zaciatok.
2. Je dana hasovacia tabulka velkosti B=13 pre zatvorene hasovanie. Vkladali sa do nej prvky v poradi 24, 7, 34, 20, 13, 8, 33, 21.
a. Zistite, aka hasovacia funkcia a aka strategia riesenia kolizii bola pouzita. Urcte prislusnu konstantu (konstanty).
b. Ako by sa tabulka zmenila, keby sme prvky vkladali v opacnom poradi?
tabulka: 13, 21, , , , , 33, 7, 34, 20, 8, 24, .
3. Ako vyzera najhorsi pripad AVL stromu s 22 vrcholmi? Nakreslite.
4. Nakreslite postupnost B-stromov s minimalnym stupnom 2, ktore vznikli postupnym vkladanim prvkov 200, 300, 100, 500, 50, 250, 450, 600, 150, 400, 270, 130, 210, 230, 70 do povodneho prazdneho stromu s naslednym vymazanim 150, 200, 300, 450.
5. Napiste proceduru, pomocou ktorej prerobite obycajny binarny strom na presity. Ich reprezentaciu si zvolte sami.
6. Aka je maximalna vyska cerveno-cierneho stromu, v ktorom je n prvkov? Dokazte.
7. Uvazujme stromovu reprezentaciu disjunktnych mnozin prvkov s operaciami UNION a FIND. Aka je casova zlozitost operacie FIND bez kompresie cesty, ak pri vykonavani operacie UNION vkladame mensiu do vacsej? Dokazte.
8. Vysvetlite, ako funguje rozkladove hasovanie a yvedte priklad jeho vyuzitia.
9. V Pascale napiste proceduru na utriedenie n-prvkoveho pola celych cisel algoritmom ShakerSort. Urcte zlozitost tohto triediaceho algoritmu.
10. Zadefinujte prislusne pojmy a vysvetlite pojmy dolneho a horneho odhadu na pocet porovnani optimalneho triediaceho algoritmu.
ADS pisomka 12.12.2006
1. Dany je binarny strom.Predpokladajme, ze mame k dispozicii nasledujuce 2 funkcie:
a)postorder(x) - vracia cislo vrchola x v postorderovskom usporiadani vrcholov daneho stromu
b)desc(x) - vracia pocet vlastnych nasledovnikov vrchola x v danom strome
Sformulujte pomocou nich vztah,ktory musi platit, ak je vrchol x nasledovnikom vrchola y v danom strome.
2. Vysvetlite ako funguje rozkladove hasovanie a uvedte priklad jeho pouzitia
3. Uvazujme zatvorene hasovanie s linearnym riesenim kolizii. Matematicky zdovodnite, preco bloky obsadenych miest maju tendenciu narastat.
4. Aka je maximalna vyska cerveno-cierneho stromu, ktory obsahuje n prvkov? Dokazte.
5. Nakreslite postupnost 2-3-stromov,ktore vzniknu vkladanim prvkov 5,10,21,33,27,12,19,15,37,17,3,18,4 do povodne prazdneho stromu a naslednym vymazanim prvkov 21,19,18.
6. Dany je B-strom minimalneho stupna t, ktory ma vysku h. Kolko prvkov moze obsahovat?
Odvodte obe hranice.
7. V Pascale zadefinujte datovu strukturu pre strommovu reprezentaciu mnozin s operaciami UNION a FIND a napiste proceduru UNION (A,B:nametype) (v Pascale), ktora zjednocuje prvky mnozin A a B tak, aby funkcia FIND(x) bez kompresie cesty bezala v case O(log2(n)), kde n je pocet prvkov ulozenych v strukture. (Funkciu FIND nemusite pisat, predpokladame, ze je taka, ako bola definovana na prednaske.)
8. Odvodte tesny horny odhad na ocakavany cas uspesneho vyhladavania v hasovacej tabulke pre otvorene hasovanie v pripade, ze prvky vkladame do zoznamov na zaciatok.
9. Vysvetlite, ako funguje algoritmus stromoveho triedenia a odvodte odhad jeho zlozitosti.
10. Nakreslite strukturu miltilist, ktora bude zachytavat nasledujuce vztahy medzi tovarmi a velkoskladmi. Bicykle maju vo velkosklade na Racianskej, na Antolskej a na Vazovovej.
Korcule maju na Racianskej a na Dunajskej. Sportovu obuv maju len na Dunajskej. Sportove batohy maju na Antolskej a Dunajskej a sportove odevy maju len na Vazovovej.
v TXT a DOC na stiahnutie tu:
http://www.subory.sk/download/211783/ADS.zip
utorok 23. decembra 2008
Tvorba prístupných e-dokumentov a programov pre nevidiacich
Z tohto predmetu treba odovzdať váš projekt do konca skúškového obdobia, čo by mal byť koniec februára.
Kľúčové informácie nájdete na
Leckého stránke:
Tu su linky na automatické testovanie prístupnosti stránky:
Cynthia Says
Validation Report
AskAlice
WAVE
nezabudnite aj na ručné testovanie stránky.
Kľúčové informácie nájdete na
Leckého stránke:
Tu su linky na automatické testovanie prístupnosti stránky:
Cynthia Says
Validation Report
AskAlice
WAVE
nezabudnite aj na ručné testovanie stránky.
Veselé Vianoce!!!
Prajem krásne Vianoce, veľa darčekov, užite si voľno a naberte veľa síl na skúšky. :)
piatok 19. decembra 2008
štvrtok 18. decembra 2008
Diskretna matematika 1
Materiály na download:
poznámky z prednášok a cvík zo zimného semestra 2007:
od Elenky (PDF)
odo mňa (PDF)
od neznámeho aktivistu (cca 30 MB, JPEGy)
skúšky z DM1, aj minuloročné, 2003 - 2007
domáce úlohy aj s riešeniami z DM1 2007, thx to Sith
nejaké príklady na výroky a množiny z 2007
skriptá Úvod do diskrétnych matematických štruktúr
niečo o kombinatorike
some old stuff (rôzne - 16 MB)
zajtra želám všetkým na DM veľa štastia
poznámky z prednášok a cvík zo zimného semestra 2007:
od Elenky (PDF)
odo mňa (PDF)
od neznámeho aktivistu (cca 30 MB, JPEGy)
skúšky z DM1, aj minuloročné, 2003 - 2007
domáce úlohy aj s riešeniami z DM1 2007, thx to Sith
nejaké príklady na výroky a množiny z 2007
skriptá Úvod do diskrétnych matematických štruktúr
niečo o kombinatorike
some old stuff (rôzne - 16 MB)
zajtra želám všetkým na DM veľa štastia
Geometria pre grafikov
Geometria pre grafikov - davam sem vsetky materialy co poslal prof. Bozek.
Cerstve info z poslednej prednasky - skuska sa sklada z testu a pisomnej casti. Pisomna cast ma 10 prikladov, treba mat aspon 8 dobre, aby sa dalo ist k ustnej casti. Je na nu 30 minut a bude LEN z analytickej geometrie, cize prvej casti. Na ustnej casti sa vyberaju 2 otazky ohladne teorie z celeho semestra. Je moznost si jednu z nich vymenit (len raz). Vyzera to podla mna spravitelne.
Prihlasovanie je len fyzicke, na jeho kabinete...ktory neviem kde je. Terminy budu vyvesene po sviatkoch. Obvykle je po teste aj ustna cast, ale je moznost pisat obe ine dni.
DOWNLOAD (ZIP)
Cerstve info z poslednej prednasky - skuska sa sklada z testu a pisomnej casti. Pisomna cast ma 10 prikladov, treba mat aspon 8 dobre, aby sa dalo ist k ustnej casti. Je na nu 30 minut a bude LEN z analytickej geometrie, cize prvej casti. Na ustnej casti sa vyberaju 2 otazky ohladne teorie z celeho semestra. Je moznost si jednu z nich vymenit (len raz). Vyzera to podla mna spravitelne.
Prihlasovanie je len fyzicke, na jeho kabinete...ktory neviem kde je. Terminy budu vyvesene po sviatkoch. Obvykle je po teste aj ustna cast, ale je moznost pisat obe ine dni.
DOWNLOAD (ZIP)
ADS - terminy
Algoritmy a dátové štruktúry
- pripomínam, že do 19.12.2008 treba mailom dodať beta verziu vášho projektu z ADS. Je najvyšší čas začať kódiť...ja idem na to :)
- pripomínam, že do 19.12.2008 treba mailom dodať beta verziu vášho projektu z ADS. Je najvyšší čas začať kódiť...ja idem na to :)
streda 17. decembra 2008
Novy člen :)
Vitam medzi nami noveho clena Petka(XXL) ......takze vsetci naraz povecte Ahoooooooj PEtko :D
nedeľa 14. decembra 2008
Úvod do matematickej logiky - podklady na písomku z predikátovej logiky
Keďže sa nám blíži písomka z UDML, dávam sem nejaké materiály, ktoré by mohli pomôcť. Aj keď tomu veľmi neverím, minule som mal 3 body.
Ešte dodávam, že Šusterova skupina má písomku vo štvrtok 18.12. ráno cez cviká o 8.10 v akvárkach.
Kulichova skupina má písomku v stredu o 17.00 (??? - Martin si nie je istý).
Pridávam ešte zadanie nejakej písomky z výrokovej logiky z roku 2007.
piatok 12. decembra 2008
A zasa je su tu dalsie testy
Tak ze na verejsnot sa dava ze :
17.12. 2008 :
Moderny pristup k webdizajnu
Matematicka Logika
Delphi
18.12. 2008:
Opravny s Anglictiny
19.12. 2008
Predtermin z diskertky
a kto by nevedl tak najhlavnejsi datum 24.12.2008 VIANOCEEEEEEEE
17.12. 2008 :
Moderny pristup k webdizajnu
Matematicka Logika
Delphi
18.12. 2008:
Opravny s Anglictiny
19.12. 2008
Predtermin z diskertky
a kto by nevedl tak najhlavnejsi datum 24.12.2008 VIANOCEEEEEEEE
streda 3. decembra 2008
Rekord
A je to tu v prispevku KTO TO DOKAZE ?? az 43 komentárov( už ich je 55) (mozete si to overit)
bolo najviac komentarov .... a este stale pribuda ?? :D
P.S Evy pre buducnost :D
Rolničky, rolničky, ktože vám dal hlas?
ten gašparko maličký a či dedo mráz?
keď stádo rolničiek sladko zazvoní
príde k nám dedo mráz, ten hlupák lakomý
vianoce, vianoce, to je zasa deň
okná drnčia ostošesť, buchla plynáreň
dedo mráz, dedo mráz čo si priniesol?
biely prášok, striekačky - to je ale gól!
medveď ľadový
má štyri nohy
a tú piatu má
medzi nohama
pani domáca
oči obracá
keď ryba chladne na stole
a stromček rúca sa
rolničky, rolničky, ktože vám dal hlas?
ten gašparko maličký a či dedo mráz?
prskavky, prskavky nežne prskajú
chytili sa záclony a už sa skrúcajú
.........
bolo najviac komentarov .... a este stale pribuda ?? :D
P.S Evy pre buducnost :D
Rolničky, rolničky, ktože vám dal hlas?
ten gašparko maličký a či dedo mráz?
keď stádo rolničiek sladko zazvoní
príde k nám dedo mráz, ten hlupák lakomý
vianoce, vianoce, to je zasa deň
okná drnčia ostošesť, buchla plynáreň
dedo mráz, dedo mráz čo si priniesol?
biely prášok, striekačky - to je ale gól!
medveď ľadový
má štyri nohy
a tú piatu má
medzi nohama
pani domáca
oči obracá
keď ryba chladne na stole
a stromček rúca sa
rolničky, rolničky, ktože vám dal hlas?
ten gašparko maličký a či dedo mráz?
prskavky, prskavky nežne prskajú
chytili sa záclony a už sa skrúcajú
.........
Volno 12.12.2008
Z príležitosti Dňa otvorených dverí pre absolventov FMFI UK udeľuje dekan doc. RNDr. Ján Boďa, CSc. na deň 12. 12. 2008 všetkým študentom d e k a n s k é v o ľ n o.
utorok 2. decembra 2008
domaca z diskretky
Odstranenie domacej, pre istotu, ze by to hladali cviciaci :P aj ked o tom jemne pochybujem :)
Este raz jedno veľké VĎAKA chlapcom :)
no deti moje lepsie to nebude, malo by to byt spravne radili mudre hlavy,touto cestou dakujeme ;-)
Este raz jedno veľké VĎAKA chlapcom :)
no deti moje lepsie to nebude, malo by to byt spravne radili mudre hlavy,touto cestou dakujeme ;-)
pondelok 1. decembra 2008
Par datumov
4.12.08 vedecko technicke vypocty druhy predtermin
8.12.08 pro seminar MS office
11.12.08 pisomka z angliny 4. lekcia
12.12.08 odovzadanie prvej etapy rocnikoveho projektu
a aby som nezabudla mozne terminy skusok z javy su uz na stranke :-)
vela zdaru
8.12.08 pro seminar MS office
11.12.08 pisomka z angliny 4. lekcia
12.12.08 odovzadanie prvej etapy rocnikoveho projektu
a aby som nezabudla mozne terminy skusok z javy su uz na stranke :-)
vela zdaru
Prihlásiť na odber:
Príspevky (Atom)