Matfyz Wiki
Diff for ''
| Deletions are marked like this. | Additions are marked like this. |
| Line 1: | Line 1: |
| <div style="background-color: #CEF; border: 1px solid #8AF; padding: 5px 5px 5px 5px; margin: 5px 5%;"> <small> '''[[Státnice_-_Informatika_-_I2:_Softwarové_systémy|Státnice -- Softwarové systémy]]'''<br/> ''Složitost a vyčíslitelnost'' -- [[Státnice - Metody tvorby algoritmů_I2|Tvorba algoritmů (10🎓)]], [[Státnice - NP-úplnost_I2|NP-úplnost (15🎓)]], [[Státnice - Aproximační algoritmy a schémata_I2|Aproximační algoritmy (6🎓)]], [[Státnice - Algoritmicky vyčíslitelné funkce_I2|Vyčíslitelné funkce a rekurzivní množiny (8🎓)]], [[Státnice - Algoritmicky nerozhodnutelné problémy_I2|Nerozhodnutelné problémy (9🎓)]], [[Státnice - Věty o rekurzi_I2|Věty o rekurzi (6🎓)]]<br/> ''Datové struktury'' -- [[Státnice - Stromové vyhledávací struktury_I2|Stromy (32🎓)]], [[Státnice - Hašování_I2|Hašování (13🎓)]], [[Státnice - Třídění_I2|Třídění (10🎓)]]<br/> ''Databázové systémy'' -- '''[[Formální základy databázové technologie|Formální základy]]''': [[Formální základy databázové technologie/Relace|Relace (12🎓)]], [[Formální základy databázové technologie/Datalog|Datalog (9🎓)]], [[Formální základy databázové technologie/Ostatni|Ostatní (0🎓)]] '''[[Databázové modely a jazyky|Modely a jazyky]]''': [[Databázové modely a jazyky/SQL|SQL (7🎓)]], [[Databázové modely a jazyky/DIS|DIS (7🎓)]], [[Databázové modely a jazyky/Odborne|Odborné (3)]] '''[[Implementace databázových systémů|Implementace]]''': [[Implementace databázových systémů/Transakce|Transakce (5🎓)]], [[Implementace databázových systémů/Indexace|Indexace (10🎓)]], [[Implementace databázových systémů/Komprese|Komprese (3)]]<br/> ''Softwarové inženýrství'' -- [[Programovací jazyky a překladače|Programovací jazyky a překladače]], [[Objektově orientované a komponentové systémy|Objektově orientované a komponentové systémy]], [[Analýza a návrh softwarových systémů|Analýza a návrh softwarových systémů]]<br/> ''Systémové architektury'' -- [[Operační systémy (státnice)|Operační systémy]], [[Distribuované systémy|Distribuované systémy]], [[Architektura počítačů a sítí|Architektura počítačů a sítí]]<br/> ''Počítačová grafika'' -- [[Geometrické modelování a výpočetní geometrie|Geometrické modelování a výpočetní geometrie]], [[Analýza a zpracování obrazu, počítačové vidění a robotika|Analýza a zpracování obrazu, počítačové vidění a robotika]], [[2D počítačová grafika, komprese obrazu a videa|2D počítačová grafika, komprese obrazu a videa]], [[Realistická syntéza obrazu, virtuální realita|Realistická syntéza obrazu, virtuální realita]]<br/> <br> 🎓 - znamená kolikrát byla otázka u státnic </small> </div> |
# Hloubka vs. Vyska vs. Hladina |
| Line 15: | Line 3: |
| [[Category:Státnice - Softwarové systémy]] | <{ForumPost(poster="_angwin", timestamp=2009-02-04 23:41:55)}> Jak se tak postupne prokousavam Koubkovyma skriptama, tak jsem narazil na tyto tri terminy. Vzdy se jedna o vzdalenosti vrcholu od korene, resp. od listu. Zatim jsem nezavrhnul hypotezu, ze vyska se cisluje od listu a hloubka/hladina se cisluje od korene. Muzete to nekdo prosim potvrdit nebo ty veci v textu pouziva zcela nahodne? Asi jsem prehlidel nejakou definici... <{/ForumPost}> <{ForumPost(poster="Myshaak", timestamp=2009-02-05 00:59:24)}> > _angwin wrote:Jak se tak postupne prokousavam Koubkovyma skriptama, tak jsem narazil na tyto tri terminy. Vzdy se jedna o vzdalenosti vrcholu od korene, resp. od listu. > > Zatim jsem nezavrhnul hypotezu, ze vyska se cisluje od listu a hloubka/hladina se cisluje od korene. Muzete to nekdo prosim potvrdit nebo ty veci v textu pouziva zcela nahodne? Asi jsem prehlidel nejakou definici... Zdar, je to tak, jak rikas. Teda nerucim za to, ze to je konzistentne v celych skriptech, ale treba v popisu A-sortu je zminena "vyska" a znamena to vzdalenost od listu, zatimco "hloubka" se pocita od korene. <{/ForumPost}> <{ForumPost(poster="Schiroo", timestamp=2009-02-09 14:02:16)}> Definice hloubky a hladiny je u (a,b)-stromů: > Když *v* má * \ro(v)* synů, pak jsou očíslovány od 1 do *\ro(v)*. Řekneme, že vrchol *v* je v **hloubce** h, když cesta z kořene *t* do *v* má délku *h*. Množina všech vrcholů v hloubce h se nazývá **h-tá hladina**. Už jsem se dočetl i k výšce (Hladinově propojené (a,b)-stromy s prstem, amortizovaná složitost operací ) :) > Připomínáme, že výška vrcholu v kořenovém stromě je maximální délka cesty z tohoto vrcholu do některého listu v jeho podstromu, V (a,b)-stromech nezáleží na tom, který list budeme uvažovat, všechny cesty mají stejnou délku. Tedy Mishaak měl pravdu, nová informace je ta, že je to (snad) ve skriptech konzistentní vzhledem k tomu, že je to tam explicitně definované. <{/ForumPost}> |