[Zk] 16. 1. 2014

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ů.
tobik
Matfyz(ák|ačka) level I
Příspěvky: 10
Registrován: 27. 5. 2011 18:10
Typ studia: Informatika Bc.

[Zk] 16. 1. 2014

Příspěvek od tobik »

Zkušeností ze zkoušek s panem profesorem Koubkem je spousta (plné pdfko), přesto ta moje mi přišla dost unikátní, takže ji sdílím, abych potěšil následující generace.

Dostal jsem AVL stromy, což je všeobecně známá věc, leč mně bylo už předem jasné, že správně nadefinovat rotace a vyvažování bude nad moje síly, a tedy mě čeká dříve či později odchod domů. Ukázalo se, že rotace a vyvažování nebyly zdaleka mým jediným problémem.
  • Zvoral jsem už základní definici binárních vyhledávacích stromů. Jako základní podmínku jsem uvedl, že L(v) <= v <= P(v). Což je nerovnost, které se využívá při průchodu stromem, ale požadovaná vlastnost musí samozřejmě být silnější.
  • Zvoral jsem základní operaci delete na vyhledávacích stromech. Moje verze v případě, že odebírám vrchol s dvěma syny, říkala, že vrchol nahradím jedním ze synů (což by porušilo binaritu). Naštěstí jsem si pak vzpomněl, že se vrchol nahrazuje maxem z levého podstromu.
  • Zvoral jsem definici hloubky pro podstromy hl(L(v)) a hl(P(v)), z čehož se pak vyvozuje základní vlastnost AVL stormů. Je totiž potřeba myslet na případ, kdy v jednoho syna nemá a ručně dodefinovat hl := -1 pro tento případ. Je to v zásadě formální špek, ale Koubek mě v tom pokoupal.
  • Zvoral jsem důkaz hloubky stromu. Důkaz jsem neuměl, jen jsem si pamatoval, že se dokazuje exponenciální počet vrcholů ve stromě s hloubkou k, že se to dělá indukcí, že tam figuruje 2^(k/2) a že to není těžké. Navrhl jsem důkaz, který všechno jmenované splňoval, leč na některé dost důležité věci jsem zapomněl a důkaz byl tedy odmítnut.
  • Nenadefinoval jsem jedinou rotaci správně.
S těmi rotacemi jsem začal hezky systematicky, u insertu jsem popsal ty jednoduché případy, kdy se nic neporuší, pak jsem ukázal, kdy se to naopak pokazí a je potřeba rotovat. Za následující hodinu a půl jsem vyplodil jednu a půl rotace při operaci insert. Načež si Koubek ke mě sedl a okamžitě jsme seškrtali vše, co jsem tam měl. Pak to probíhalo stylem, že já navrhl rotaci, on řekl ne, bude to takhle. Rotování po delete shrnul slovy, že je to jen analogie k insertu, jen opačně. Načež mi řekl, že mě nepotěší, a dal mi za tři.

Takže abych to shrnul, v podstatě ve všem, co jsem napsal, jsem měl chybu. Ty lehčí věci mě nechal Koubek opravit, ty těžší vymyslel za mě. Což je dost v protikladu s tím, za co dost často vyhazuje. Evidentně stačí vědět, že AVL je binární strom a že se nějak rotuje a vyvažuje. Jak se to děje, to už je irelevantní :D

Budoucím generacím bych doporučil se obloukem vyhnout Koubkovým skriptům, snad jen jako pomocný materiál a haldy se mi z nich zdály docela pochopitelné (pokud si člověk namaluje, co se v nich děje). Naopak bych doporučoval se držet co to jde starých ADS sešitů, protože průnik datovek s ADS je dost velký, akorát v ADS jsou věci vysvětlovány jednodušeji a přímočařeji, i ty důkazy jsou snazší. A na projití to bohatě stačí.
Kapitán mísa

Re: [Zk] 16. 1. 2014

Příspěvek od Kapitán mísa »

Já jsem dostal rozhodovací stromy. Věděl jsem tak nějak vše až na ty důkazy. Odhadl jsem S(n) podle Stirlinga, ale už jsem neumlátil přesně odhad pro nlog(e/n) a odhadl jsem to jako O(nlong). Pan profesor s tím neměl žádný problém. Pak jsem se snažil odhadnout A(n), ale věděl jsem jen, že je to B(n!)/n! a odhad pro B(n!) jsem znal jen výsledek, ovšem ne postup výpočtu, jen jsem řekl, že se na to jde přes sumy. Řekl mi zda chci ještě zkusit vymyslet ten odhad. Já se zeptal, jak si na tom právě stojím, tak mi řekl, že za dva a já to bral a šel :) Čili u těch důkazu je nejdůležitější znát nějakou ideu než přesné postupy. Dokonce jsem prohodil značení A(n) a S(n), ale to nedělalo žádný problém, jen si nechal důkladně vysvětlit, že myslím to samé, jen to jinak značím a nedělal žádné předčasné závěry. Jinak tam padalo docela často hašování. Doporučil bych raději zvolit strategii vědět o každé věci něco a nějak trochu ideu důkazu, než pár věcí nevědět vůbec, protože tam prostě není žádná záchranná otázka navíc.
cunav5am
Matfyz(ák|ačka) level I
Příspěvky: 16
Registrován: 4. 6. 2007 09:37
Typ studia: Informatika Mgr.

Re: [Zk] 16. 1. 2014

Příspěvek od cunav5am »

tobik píše:Naopak bych doporučoval se držet co to jde starých ADS sešitů, protože průnik datovek s ADS je dost velký, akorát v ADS jsou věci vysvětlovány jednodušeji a přímočařeji, i ty důkazy jsou snazší.
Nevím jak dnes, ale co jsem byl já, tak na ADS byly na dost věcí jen pseudo-důkazy kde nezbývalo než věřit, apod...
tobik
Matfyz(ák|ačka) level I
Příspěvky: 10
Registrován: 27. 5. 2011 18:10
Typ studia: Informatika Bc.

Re: [Zk] 16. 1. 2014

Příspěvek od tobik »

cunav5am píše:
tobik píše:Naopak bych doporučoval se držet co to jde starých ADS sešitů, protože průnik datovek s ADS je dost velký, akorát v ADS jsou věci vysvětlovány jednodušeji a přímočařeji, i ty důkazy jsou snazší.
Nevím jak dnes, ale co jsem byl já, tak na ADS byly na dost věcí jen pseudo-důkazy kde nezbývalo než věřit, apod...
To je možné, ale právě v kontextu toho, co třeba píše Kapitán mísa o něco výše, to zase tolik nevadí. Pokud to člověk potřebuje mít rychle z krku, nemá moc času na učení a stačí mu za 3, tak z té zjednodušené ADS verze je vidět vše mnohem snáz a rychleji.
Odpovědět

Zpět na „TIN066 Datové struktury I“