[Zk] 5.2.2008

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ů.
Kuba
Matfyz(ák|ačka) level II
Příspěvky: 92
Registrován: 2. 6. 2005 22:55
Typ studia: Informatika Mgr.
Bydliště: Praha - Dejvice
Kontaktovat uživatele:

[Zk] 5.2.2008

Příspěvek od Kuba »

Tak jsem dostal A-sort.
Napsal jsem:
definici (a,b)-stromu
co to je ze strom reprezentuje S
rozsireni definice pro A-sort
alg. A-sort a podproc. A-insert (to pridavani na konci jsem popsal jen slovne)
slozitost O(n + nlog(F/n)) a ze kdyz F <= nlogn, tak je slozitost O(n + nloglogn) cili rychlejsi nez Quicksort
co je to F a co je to inverze.

Precetl to, zeptal se jestli "prvnim prvkem" myslim ten nejmensi (ano), a pak se zeptal, ze jestli se mi teda nechce nic pocitat, tak mi da za 3, coz jsem vzal.
Cas: 1h
Cas na uceni: 5 dni po cca 6ti hodinach - bez dukazů složitosti, bez perfektniho a univerzalniho hashovani

Kolega vedle dostal Konstrukci perfektni hashovaci funkce a odesel.

Podle me Koubek uz musi vedet ze kdyz nekomu da Konstrukci perf. hash. fce tak ze to je skoro jako kdyby ho rovnou poslal domu... mel by zavest nejake losovani, nebo tak, aby ho lidi nepodezrivali z diskriminace :) (nebo lepe - predelat tu kapitolu nejak tak aby to bylo vztrebatelnejsi)

Jinak k terminum rikal, ze tam stejne nikdy neprijde vsech 20 lidi a ze kdyz tam prijde nekdo kdo neni zapsan, tak je mu to fuk, klidne ho vyzkousi, dokud tech lidi na 1 terminu bude max 20. Co se tyce dalsich terminu, tak rikal, ze to se s nim kdyztak da nejak dohodnout.
Uživatelský avatar
Che
Donátor
Donátor
Příspěvky: 166
Registrován: 2. 6. 2005 12:29
Typ studia: Informatika Mgr.
Bydliště: EU
Kontaktovat uživatele:

Re: [Zk] 5.2.2008

Příspěvek od Che »

Já měl rozhodovací stromy a moc jsem tam toho nenapsal: jen definici a výpočet počtu porovnání a času v nejhorším případě. Pan Koubek se mně zeptal, zda vím, jak se spočítá odhad pro očekávaný případ, to jsem moc nevěděl, tak mi to obecně vysvětlil a řekl, že mi teda dá trojku :)
Jinak končil jsem cca po 2 hodinách a čvrt a to už jsme tam byli jenom tři, takže dneska to šlo nějak rychle...
shoot that shit
Uživatelský avatar
Trupik
Matfyz(ák|ačka) level III
Příspěvky: 251
Registrován: 3. 1. 2005 14:45
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Re: [Zk] 5.2.2008

Příspěvek od Trupik »

Myslím, že nás pan Koubek má už prokouknutý a trojkaře pozná na první pohled :)
Domovská stránka: http://www.jakubmaly.cz/, blog: http://blog.jakubmaly.cz/
Petice proti olympiádě http://olympiada.nazory.cz

Come on you target for faraway laughter,
Come on you stranger, you legend, you martyr, and shine!
Uživatelský avatar
Kate
Matfyz(ák|ačka) level III
Příspěvky: 146
Registrován: 8. 1. 2005 10:52
Typ studia: Informatika Mgr.
Bydliště: Milada squat
Kontaktovat uživatele:

Re: [Zk] 5.2.2008

Příspěvek od Kate »

prednaselo se letos (resp. zkousi se) i to externi hashovani na konci?
Člověk si nemusí nic myslet, aby něco udělal.
Kuba
Matfyz(ák|ačka) level II
Příspěvky: 92
Registrován: 2. 6. 2005 22:55
Typ studia: Informatika Mgr.
Bydliště: Praha - Dejvice
Kontaktovat uživatele:

Re: [Zk] 5.2.2008

Příspěvek od Kuba »

Jo jo, nekdo to mel
Odpovědět

Zpět na „TIN066 Datové struktury I“