od tobik » 16. 1. 2014 17:06
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í
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čí.
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.
[list]
[*]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ě.[/list]
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čí.