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> |
{{Předmět|Textové Algoritmy|Tomáš Dvořák|NTIN087}} |
| Line 15: | Line 3: |
| [[Category:Státnice - Softwarové systémy]] | ## ZK ZS 07/08 ## Zkouška je ústní, většinou tak pro 6 lidí. Den předem oznámil zkoušející přesnou hodinu, kdy má který student přijít. Na zkoušku určitě stačí jen to, co je ve slidech, není třeba shánět jinde. Detailnější věci ze slidů nejsou úplně potřeba (ač se můžou hodit). Poptáváno je asi vše co lze na slidech nalézt (snad až na nějaké dlouhé konstrukce). ### Otázky (pro jednoho člověka) ### * 1) Nalézt dvojice podslov slova x v suffixovém stromě. (viz. slide [číslo7](http://ksvi.mff.cuni.cz/%7Edvorak/vyuka/TIN087/SufixTrees2.pdf)) * 2) Kódovat slovo pomocí suffixového pole (viz. slide [číslo 24](http://ksvi.mff.cuni.cz/%7Edvorak/vyuka/TIN087/SufixArrayConstruction.pdf)) (slovo bylo stejné) * 3) Konstrukce DAWG / CDAWG na slovo cocoa (jak se konstruují, jaká je prostorová složitost, porovnání se suffix stromem) * 4) Problém nejdelší společnépodposloupnosti - najít nějaký rozumný algoritmus ... Wagner - Fischer (viz. slide [číslo 14,15](http://ksvi.mff.cuni.cz/%7Edvorak/vyuka/TIN087/StringDistance.pdf)) * 5) Problém palindromu (viz. slide [číslo 13](http://ksvi.mff.cuni.cz/%7Edvorak/vyuka/TIN087/Uvod.pdf)) Po napsání řešení následuje kontrola a diskuze nad řešením. Obvykle se zkoušející vyptává např. na čas, náročnost a další upřesnění. Chce, aby to člověk chápal, ale není třeba do detailů. Dost se toho dá vymyslet až tam (pokud to člověk chápe :-) ### hodnocení ### Pomyslným žebříčkem je 100 bodů (tedy 20 za každou otázku), do 90 na jedničku, 80 na dvojku, 60 na trojku (myslím, že to tak říkal) Nakonec podle tohoto žebříčku zkoušející spočítá body (spíše strhne ze 100), ne ale nijak přísně => vytvoří známku. Pokud je známka dost nerozhodná (pár bodů pod hranicí), nabídne zkoušející další otázku, kterou je možno skore vylepšit. ## Hodnocení předmětu ## Předmět patří mezi ty jednodušší, člověk si ale rozšíří obzor o další algoritmy a struktury, které se mohou hodit. Zkouška je příjemná, nestresující. Zkoušející se spíše z člověka snaží dostat odpověď, než že by se v zadání šťoural. ## Odkazy ## * [Stránka předmětu, slidy](http://ksvi.mff.cuni.cz/%7Edvorak/vyuka/NTIN087/) [Category:Předměty](Category:Předměty) [Category:Informatika](Category:Informatika) |