Zk. 14.2.2011

Přednáška navazuje na přednášky Algoritmy a datové struktury I a II a Programování I a II bakalářského studia. Bude věnována dvěma základním datovým strukturám, hašování a $(a,b)$-stromům (tato struktura se také nazývá $B$-stromy). Popisují se zde základní vlastnosti těchto struktur a jejich složitost. Na závěr přednášky se provede stručné zhodnocení třídicích algoritmů.
Mousak
Matfyz(ák|ačka) level I
Příspěvky: 8
Registrován: 15. 1. 2008 22:04
Typ studia: Informatika Bc.

Zk. 14.2.2011

Příspěvek od Mousak »

Padala bezna temata (a,b), AVL, atd. - sedel jsem v druhe rade a dostal c-univerzalni systemy (cili theorem o prvni rade funguje zrejme az na konecne mnoho vyjimek ;) ).

K tem univerzalnim systemum jsem napsal definici, proc se to pouziva (jine podminky oproti treba sep. hash. => randomizace), existenci (c = ...), vlastnosti (oc. delka retezce, dolni odhad pro vel. systemu a Markov. ner.) a nakonec konstrukci. Tady bych rad podotknul, ze jsem tam nemel ty sileny upravy a rozepsany odhady, ale jen zakladni myslenky toho dukazu. Cili pokud si pamatujete zacatek, myslenku a konec a budete to mit vsechno spravne, tak se max. zepta na par detailu a bude to stacit.

Kvuli nepresnostem (a mozna tem nerozepsanejm dukazum?) jsem dostal jeste otazku pro boj mezi 1-2: (a,b)-stromy - aproximace vyvazovani.

Hodne stesti
Odpovědět

Zpět na „TIN066 Datové struktury I“