prof. Kucera - veci ke zkousce

Uživatelský avatar
Myshaak
Matfyz(ák|ačka) level III
Příspěvky: 162
Registrován: 18. 1. 2006 22:29
Typ studia: Informatika Mgr.

prof. Kucera - veci ke zkousce

Příspěvek od Myshaak »

Tak nevim, snad mi nekdo odpovi... ;) Jdu k prof. Kucerovi na zkousku a ted jsem koukal na jeho stranky na pozadavky ke zkousce, a i kdyz jsem na prednaskach chybel jen 2x a vse si poctive dopsal, tak nektere veci mi nic moc nerikaji. Konkretne "<i>jedno- a více průchodové třídění na základě adresování pomocí klíčů</i>" , "<i>hledání mediánu v lineárním čase</i>" , "<i>bitonické třídění</i>".
No, to trideni na zakl. adr. pomoci klicu je asi ten linearni tridici algoritmus, to mi doslo, jen nevim co to je to vice pruchodove trideni (to je kdyz mam treba ty dlouhy cisla a tridim to po bytech??), hledani medianu jsme sice meli na posl. prednasce, ale <b> z programovani</b>, bylo to i na algoritmech???? No a konecne "bitonicke trideni", to uz fakt nevim. Kdy jsme to delali?? Sice jsem tu nasel par odkazu, ale nic mi to nepripomina...
Help! :)
"Go for the eyes Boo, go for the eyes! Yeahh!!"
Uživatelský avatar
jaruch
Supermatfyz(ák|ačka)
Příspěvky: 376
Registrován: 5. 2. 2005 14:06
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Příspěvek od jaruch »

To viacpriechodove tiredenie by malo byt presne to, co vravis, ked mas dlhe cisla, tak to zotriedis podla prvych par bitov a potom dalej, median minuly rok bral aj bitonicke triedenie, dokonca to daval ako zachrannu otazku (ale silne pochybujem, ze sa na TOMTO dakto dokazal zachranit)
Shit shit, who the fuck is shooting us?
I've got a universe to master...
Uživatelský avatar
Lukas Mach
Matfyz(ák|ačka) level III
Příspěvky: 261
Registrován: 28. 3. 2006 17:08
Typ studia: Informatika Bc.
Bydliště: Praha a Kladno
Kontaktovat uživatele:

Příspěvek od Lukas Mach »

Mohl by se tu napsat seznam toho, co teda skutecne na prednasce bylo. Ja se muzu kouknout do zapisku z algoritmu az zitra a mimoto jsem tam asi tak 2-3 krat chybel (v 9 rano? kdo to ma stihat?) Takze by bylo fakt super, kdyby to tu par lidi napsalo taky, snad to dame nejak dohromady.

Na otazku, co je bitonicke trideni ti odpovi Google:

http://www.inf.fh-flensburg.de/lang/alg ... onicen.htm

Je to popsane i v Introduction to algorithms, ktere si muzes pujcit v knihovne na Male strane.

Ale na to, ze by to bylo na prednasce, si nevzpominam.

Pruchodove trideni bude pravdepodobne skutecne radixsort a bucketsort.
For every epsilon, there is delta.
Where is my delta?
Uživatelský avatar
snail
Matfyz(ák|ačka) level III
Příspěvky: 144
Registrován: 23. 5. 2005 22:31
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Příspěvek od snail »

U nas loni bitonicky trideni urcite bral, to si pamatuju.
Potom to bral dokonce i na Algoritmech II...ze by derava pamet :lol:
(ted akorat zalezi jestli jeho nebo studentu, kterym to chtel pripomenout :twisted: ).

Vice pruchodovy trideni je zalozeny na radixsortu, protoze je to stabilni
trideni. Ale tridit se musi odzadu (od nejmin vyznamnych cifer).

Hledani medianu v linearnim case bral urcite taky.
Uživatelský avatar
Myshaak
Matfyz(ák|ačka) level III
Příspěvky: 162
Registrován: 18. 1. 2006 22:29
Typ studia: Informatika Mgr.

Příspěvek od Myshaak »

Lukas Mach píše: Na otazku, co je bitonicke trideni ti odpovi Google:

http://www.inf.fh-flensburg.de/lang/alg ... onicen.htm

Je to popsane i v Introduction to algorithms, ktere si muzes pujcit v knihovne na Male strane.

Ale na to, ze by to bylo na prednasce, si nevzpominam.
Jo, ten odkaz jsem tu uz videl, ale vzhledem k tomu, ze je to v anglictine a ja o tom v zivote neslysel, tak neni lehke z toho pochopit, o co jde a dokazat spravnost a slozitost. Na prednasce to letos urcite nebylo (stejne jako median v lin case), tak doufam ze z toho nebude zkouset!
"Go for the eyes Boo, go for the eyes! Yeahh!!"
Odpovědět

Zpět na „2005“