Bol som na statniciach sam. Na zaciatku (tak 9:10) som dostal zadanie vsetkych piatich otazok. Na pripravu som mal ani nie pol hodiny (tak 9:35). Potom hned za sebou jednotlive skusania, vacsinou je niekto hlavny skusajuci, ostatni sa obcas spytaju ci komentuju bokom. Skusajuci su mili, snazia sa nasmerovat.
Datove struktury: Hashovanie, riesenie kolizii [Holan]
Motivacia, definicia, ze je to rychle, ale bez zaruky v najhorsom pripade. Problem s koliziami. Jak vobec spoznam, ze doslo ku kolizii? Co ked narazim vo vete na slovo, ktore som uz zahashoval, tak to predsa nie je kolizia. No tak ked zistim, ze v priehradke uz nieco je, tak najprv porovnam kluce a az ked sa lisia, tak to vyhlasim za koliziu. Dalej, ako ich riesit: popisal som separovane retazce, otvorenu adresaciu a ako sa skusaju dalsie priehradky (linearne, kvadraticky, dvojite hashovanie). Zmienil som este, ze sa daju prvky aj prepisovat, napr. pri cachovani, alebo ze mozme mat za istych podmienok aj perfektne hashovanie bez kolizii - ale to skusajuceho zas tak nezaujimalo... Ako sa v takom otvorenom hashovani maze? Oznacujeme za zmazane, ale nechavame, inac by sa mohlo stat, ze [ukazujem na obrazku]. Este nieco k tomu, ze ako dlho to cele potrva? To zalezi od zaplnenia tabulky (alfa=n/m). A co potom, ked je tabulka dost plna? Mozme ju prehashovat do inej, trebars 2x vacsej - to bude trvat v tej chvili dlho, ale celkovo sa to neprejavi (smerujem k amortizacii dynamickeho pola). No ale keby sme je nezdvojnasobili, ale pridali 10 priehradok. To by nestacilo, potom uz by to cele bezalo linearne. A keby sme zvysili o 10 %? Reku, neviem, ci by potom ta amortizacia vysla...
Potom ze dictionary v pythone (co je prave hashovacia tabulka) vraj funguje konstantne (dakde pisali) - ako by som tomu rozumel? No tak, ze priemerne konstantne, ale moze sa stat, ze nejake data budu take zle, ze to bude trvat dlho. A dokazal by som take data skodoradostne vymysliet? Vravim, ze este existuje univerzalne hashovanie, ktore ma pre kazde 2 prvky priemerne (cez hashovacie funkcie) rovnaku pravdepodobnost. Takze ak dictionary hashuje univezalne, tak sa ziadne take data vymysliet nedaju. Tak vraj sice uplne univerzalne nehashuje, ale pri kazdom spusteni voli funkciu nahodne, takze sa take data (aspon nijak jednoducho) vymysliet nedaju.
Z tohto som mal 1.
Zlozitost a vycislitelnost: NP uplne problemy [Holan]
Co znamena, ze je problem v NP (obe definicie, dokaz ekvivalencie sa nechcel) - ok. Co znamena, ze je NP tazky - ze nanho mozme previest akykolvek problem v NP. Co je ten prevod? Ze existuje poly. funkcia f, ktora prevadza instancie jedneho problemu M na druhy M' - ze ked M(a) prijme, tak prijme aj M'(f(a)). Je tam len implikacia? Tu som sa snazil popisat, ze tam implikacie nejak bude, lebo neplati opacne, ze by sme akykolvek problem v NP mohli previest na nejaky NP tazky. To je sice pravda, ale tato implikacia je inde, tu ma skutocne byt ekvivalencia: M(a) prijme <=> M'(f(a)) prijme.
Dalej NP uplne: su v NP a zaroven NP tazke, vsetko som to behom toho ukazoval na mnozinovom obrazku.
Potom nejake priklady: SAT, 3SAT, kachlikovanie, OC, HK... Ako vlastne ukazem, ze nejaky problem je NP uplny? Prevodom alebo priamo z definicie... To priamo som trosku motal. Ale popisal som kachlikovanie, zadanie aj prevod, to bolo ok (len ze vraj siet nemusi byt stvorcova... vravim, ze z oboch smerov si to ale mozme doplnit: prazdnymi znakmi / kopirovanim prijimacej konfiguracie - takze mozme pozadovat stvorcovu!).
Este nejaky iny prevod by som si vedel? Tak vravim SAT->3SAT, ze to mi prislo lahke. Tak sa skusajuci smiali, ze som si dobre vybral. I ked keby som si vybral opacne 3SAT->SAT, ze by to bolo este lahsie
Znamka 1,5 - 2
Zaklady NLP: Navrh a vyhodnotenie lingvistickych experimentov, evaluacne metriky [Zabokrtsky]
Chcel som rozpravat o metrikach precision/recall, tak som popisal situaciu, ze mame zlate, binarne anotovane data a chceme sa na nich vyhodnotit fungovanie nejakeho systemu. Ale mozeme mat aj ulohy bez anotovanych dat? Ano, napriklad rozne clustrovacie, cielom je trebars dat do skupin slova, co sa chovaju nejak podobne (slovne druhy, vetne cleny...). Dobre, tak k tym anotovanym. Niektore vzorky su oznacene ako pozitivne, cielom je ich urcit -> matica konfuzie. Musi to byt binarne? Nie, mozeme mat viac tried (ale aj tie mozem vyhodnocovat binarne, vzdy 1 proti ostatnym). Metriky accuracy (ta je nepresna), precision, recall. F1-score: preco to je geometricky priemer prec a rec. a nie aritmeticky. No lebo je lahke mat jedno z tych dvoch vysoke (oznacim vsetko -> vysoky recall) i ked druhe je nizke. Aritmeticky by povedal, ze to je tak stredne uspesne, geometricky tu nevyvazenost viac penalizuje. A preco je v tom F1 ta dvojka? No.. taky je ten priemer... asi by tam nemusela byt, sa to tym len nasobi. Tak inac, preco to F1 robime? No chceme nejak rovnomerne vyjadrit precision a recall spolu. To tak ale nemusi byt vzdy, mozme chciet dat jednemu z toho vacsiu vahu, napr. ked jeden typ chyb je drazsi nez iny alebo ked chyby v jednom smere toklo nevadia (napr. ked sa obcas spam dostane do schranky tak to tolko nevadi, jak ked dolezity e-mail skonci v spame).
Na papieri som mal este vzorec pre BLEU, tak nieco ze o tom. Sluzi to pre vyhodnotenie strojoveho prekladu. Brevity penalty ok. Suma, vahy n-gramov ok. Ale najprv zle povedal, co su to tie P_n. Ziadne pravdepodobnosti! Je to precision na tych n-gramoch - jednoducho kolko n-gramov z evaluovaneho prekladu bolo v referencnom preklade.
K mojmu prekvapeniu za 1 (myslim).
Lingvisticke teorie a formalizmy: Zakladne formalizmy (hlavne GB, HPSG, CG) [Hana]
Vraj k tomu mozem este pridaj aj dalsie, trebars zavislostne, ak chcem. Zacal som obecne rozdielom medzi zlozkovymi a zavislostnymi, potom pristupil ku kategorialnym gramatikam, akoze su najstarsie. Povedal som, ze co su tie kategorie, ze ich maju slova u seba v slovniku a ako sa podla toho analyzuje veta. To bolo sice spravne, ale bol to len popis syntaxe, ale ta gramatika je kompletna od fonetiky az po pragmatiku. Potom chcel skusajuci nieco o tych zavislostnych, nejake porovnanie so zlozkovymi, vratane stromov. Zakladny popis stromov... ok. Ze v zavislostnych sa zle koordinuje - ok. Ze v zlozkovych sa nedaju reprezentovat neprojektivne konstrukcie - to vraj zalezi, ako tu gramatiku vybudujeme (ze nikde nie je povedane, ze tie gramatiky musia byt bezkontextove). Keby som si mal vybrat smer, ktorym by som stromy prevadzal? Vravim, ze u zlozkovych by bol problem, ktory neterminal frazy by mal byt riadiaci clen ostatnych - ok, ale tak keby som to tam mal vyznacene. Naopak zo zavislostnych na zlozkove by bol problem, ze jeden zavislostny odpoveda viacerym zlozkovym.
Ku Government & Binding ani k HPSG sme sa prekvapivo uz vobec nedostali.
Znamka asi 2.
Statisticke metody a strojove ucenie: HMM, trellis, Viterbi, Baum-Welch [Straka+Dusek]
K tejto otazke som sa pri priprave uz nedostal, tak to bolo trochu zmatene (i ked keby som si povedal, ze chcem este viac casu, tak by mi ho iste dali). Chvilu mi trvalo, nez som poskladal, co to su HMM (museli sa mna spytat, co je na nich to "markovovske" - obmedzena historia). Trellis ok. Pomylil som si tie algoritmy, popisal som s pomocou skusajucich ucel a priebeh Viterbiho. Baum-Welcha som si nespomenul.
Viterbi dostane retazec, trebars slovo/vetu, emitovanu HMM, algoritmus ma zistit najpravdepodobnejsiu postupnost stavov. Baum-Welch dostane velke mnozstvo textu a ma natrenovat prechodove a vystupne pravdepodobnosti.
Dostal som 2,5.
Poslali ma na chvilu von, potom si ma zavovali a oznamili znamku. Ze par zaskobrnuti, obcas aj vaznejzich, tak ze pekna dvojka (tie jednotlive znamky z okruhov nevraveli, ale boli tam spisane na papieri). Odchadzal som cca o 10:50, takze samotne skusanie mohlo mat daco malo cez hodinu.
Matematicka lingvistika - 16.9.2020
Vše o státnicích úspěšně završujících roky studia na naší alma mater.
Přejít na
- Aktuální informace
- ↳ Studijní oddělení
- ↳ Knihovna
- ↳ Studentská komora Akademického senátu (SKAS)
- ↳ Volby na ak. rok 2013/2014
- Všichni
- ↳ Práce
- ↳ Klubovna
- ↳ Toto fórum
- ↳ Státní závěrečná zkouška
- ↳ Bakalářské SZZ
- ↳ Magisterské SZZ
- ↳ Info for foreign students
- ↳ Akce
- ↳ Fotbalový turnaj 2008
- Informatika ZS
- ↳ Výuka ZS 1. ročník
- ↳ DMI002 Diskrétní matematika
- ↳ 2007
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ MAI054 Matematická analýza I
- ↳ 2007
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ MAI057 Lineární algebra I
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ PRG030 Programování I
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ SWI120 Principy počítačů a operačních systémů
- ↳ SWI087 Principy počítačů
- ↳ Ostatní
- ↳ DMI051 Úvod do řešení problémů kombinatorických, mat. i jiných (IPS) II
- ↳ Výuka ZS 2. ročník
- ↳ MAI056 Matematická analýza III
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ OFY016 Fyzika pro nefyziky I - Svět kolem nás
- ↳ SWI089 Ochrana informace I
- ↳ SWI096 Internet
- ↳ TIN061 Algoritmy a datové struktury II
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ Ostatní
- ↳ Aplikační software
- ↳ NPRG035 Jazyk C# a platforma .NET
- ↳ NPRG041 Programování v C++
- ↳ AIL062 Výroková a predikátová logika
- ↳ 2007
- ↳ 2006
- ↳ 2005
- ↳ PGR013 Java
- ↳ MAI059 Pravděpodobnost a statistika
- ↳ Výuka ZS 3. ročník
- ↳ SWI099 Administrace Systemu Windows
- ↳ SWI015 Programování v Unixu
- ↳ SWI098 Principy překladačů
- ↳ 2006
- ↳ Ostatní
- ↳ DBI007 Organizace a zpracování dat I
- ↳ 2006
- ↳ MAI062 Algebra I
- ↳ PGR003 Počítačová grafika I
- ↳ SWI090 Počítačové sítě I
- ↳ Výuka ZS NMgr.
- ↳ TIN066 Datové struktury I
- ↳ TIN062 Složitost I
- ↳ TIN064 Vyčíslitelnost I
- ↳ MAI060 Pravděpodobnostní metody
- ↳ SWI004 Operační systémy
- ↳ SWI106 Administrace Unixu
- ↳ Ostatní
- ↳ NTIN090 Základy složitosti a vyčíslitelnosti
- ↳ OPT042 Programování s omezujícími podmínkami
- ↳ AIL002 Neuronové sítě
- ↳ AIL025 Evoluční algoritmy I
- ↳ AIL069 Umělá inteligence I
- ↳ NDBI001 Dotazovací jazyky I
- ↳ TIN070 Testování software
- ↳ NDBI027 Datové sklady a analytické metody pro Business Intelligence
- ↳ NDBI034 Vyhledávání multimediálního obsahu na webu
- ↳ NPRG023 Softwarový projekt
- Informatika LS
- ↳ Výuka LS 1. ročník
- ↳ MAI055 Matematická analýza II
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ MAI058 Lineární algebra II
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ PRG031 Programování II
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ TIN060 Algoritmy a datové struktury I
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ SWI095 Úvod do UNIXu
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ Ostatní
- ↳ Výuka LS 2. ročník
- ↳ SWI071 Ochrana informace II
- ↳ TIN071 Automaty a gramatiky
- ↳ PRG033 Ročníkový projekt - specifikace
- ↳ DMI011 Kombinatorika a grafy I
- ↳ DBI025 Databázové systémy
- ↳ Ostatní
- ↳ SWI036 Programování pro Windows I & II
- ↳ SWI096 Internet
- ↳ PRG005 Neprocedurální programování
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ NSWI143 Architektura počítačů
- ↳ Výuka LS 3. ročník
- ↳ Ostatní
- ↳ PGR004 Počítačová grafika II
- ↳ PRG036 Technologie XML
- ↳ SZZ026 Bakalářská práce
- ↳ PRG003 Metodika programování a filozofie programovacích jazyků
- ↳ MAI064 Matematické struktury
- ↳ MAI042 Numerická matematika
- ↳ SWI021 Počítačové sítě II
- ↳ SWI045 Rodina protokolů TCP/IP
- ↳ NPRG038 Pokročilé programování pro .NET
- ↳ Výuka LS NMgr.
- ↳ SWI109 Konstrukce překladačů
- ↳ NPRG042 Programování v paralelním prostředí
- ↳ SWI117 Technologie vývoje webových aplikací
- ↳ SWI026 Softwarové inženýrství
- ↳ MAI061 Metody matematické statistiky
- ↳ I1 Ostatní Teoretická informatika
- ↳ I2 Ostatní Softwarové systémy
- ↳ I3 Ostatní Matematická lingvistika
- ↳ I4 Ostatní Diskrétní modely a algoritmy
- ↳ AIL026 Evoluční algoritmy II
- ↳ AIL070 Umělá inteligence II
- ↳ NDBI010 Dokumentografické informační systémy
- ↳ NDBI023 Dobývání znalostí
- ↳ NDBI016 Transakce
- ↳ NDBI006 Dotazovací jazyky II
- ↳ NAIL029 Strojové učení
- Matematika
- ↳ Výuka LS 1. ročník
- ↳ Lineární algebra 2
- ↳ Programování 2
- ↳ Matematická analýza 1b
- ↳ Volitelné předměty
- ↳ Výuka LS 2. ročník
- ↳ Pravděpodobnost a statistika
- ↳ Teorie Míry a integrálu II
- ↳ Algebra II
- ↳ Matematická analýza 2b
- ↳ Ostatní
- ↳ Výuka LS 3. ročník
- ↳ Předměty numeriky
- ↳ Úvod do funcionální analýzy
- ↳ Funkcionální analýza I
- ↳ Vybrané partie z funkcionální analýzy
- ↳ Náhodné procesy 2
- ↳ Matematická statistika 2
- ↳ Teorie pravděpodobnosti 2
- ↳ Matematická ekonomie
- ↳ Ostatní
- ↳ LS - Předměty MMIB a pokročilé Algebry
- ↳ Všeobecná diskuse
- ↳ Počítačová algebra
- ↳ Teorie čísel a RSA
- ↳ Aplikovaná kryptografie II
- ↳ Standardy v kryptografii
- ↳ Kryptoanalytické útoky
- ↳ Aplikace bezpečnostních mechanismů
- ↳ Kvantové a DNA počítače
- ↳ Faktorizace velkých čísel
- ↳ Algebraická geometrie v kladné charakteristice
- ↳ Výuka ZS 1. ročník
- ↳ MAA001 Matematická analýza 1a
- ↳ PRM044 Programování I
- ↳ MAA079 Proseminář z kalkulu 1a
- ↳ DMA005 Diskrétní matematika
- ↳ ALG001 Lineární algebra a geometrie I
- ↳ Ostatní
- ↳ Volitelné předměty
- ↳ Výuka ZS 2. ročník
- ↳ MIB
- ↳ Matematická analýza 2a
- ↳ Teorie míry a integrálu
- ↳ Numerika
- ↳ Algebra
- ↳ Předměty finanční matematiky
- ↳ Ostatní
- ↳ Výuka ZS 3. ročník
- ↳ Matematická statistika
- ↳ Teorie pravděpodobnosti
- ↳ Náhodné procesy
- ↳ Optimalizace
- ↳ Předměty numeriky
- ↳ Předměty finanční matematiky
- ↳ Komplexní analýza
- ↳ Funcionální analýza
- ↳ Ostatní
- ↳ ZS - předměty MMIB a pokročilé Algebry
- ↳ Úvod do algebry
- ↳ Složitost pro kryptografii
- ↳ Samoopravné kódy
- ↳ Teoretická kryptografie
- ↳ Aplikovaná kryptografie I
- ↳ Datové a procesní modely
- ↳ Eliptické křivky
- ↳ Členění kryptografických standardů
- ↳ Kryptografické protokoly
- ↳ Úvod do teorie grup
- ↳ Právní aspekty zabezpečení dat
- ↳ Komutativní okruhy
- Fyzika ZS
- ↳ Výuka ZS 1. ročník
- ↳ OFY067 Fyzika v experimentech I
- ↳ MAF027 Lineární algebra I
- ↳ OFY021 Fyzika I (mechanika a molekulová fyzika)
- ↳ OFY056 Programování pro fyziky
- ↳ MAF033 Matematická analýza I
- Oborový mix aktuální
- ↳ Anglický jazyk
- ↳ Tělesná výchova
- ↳ Granty GAUK
- Odkazy
- ↳ Wiki
- ↳ SKAS
- ↳ Spolek Matfyzák
- Matematika Archiv
- ↳ Výuka LS 2006/2007 3. ročník
- ↳ Předměty numeriky
- ↳ Úvod do funcionální analýzy
- ↳ Náhodné procesy 2
- ↳ Matematická statistika 2
- ↳ Teorie pravděpodobnosti 2
- ↳ Matematická ekonomie
- ↳ Výuka LS 2006/2007 2. ročník
- ↳ Pravděpodobnost a statistika
- ↳ Teorie Míry a integrálu II
- ↳ Angličtina
- ↳ Algebra II
- ↳ Matematická analýza 2b
- ↳ Ostatní
- ↳ Výuka LS 2006/2007 1. ročník
- ↳ Volitelné předměty
- ↳ Lineární algebra 2
- ↳ Programování 2
- ↳ Matematická analýza 1b
- Zrušené předměty
- ↳ SWI087 Principy počítačů
- ↳ SWI120 Principy počítačů a operačních systémů
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ PRG029 Programování v C++
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ PRG032 Objektově orientované programování
- ↳ 2006
- ↳ 2005
- ↳ 2004
- ↳ SWI097 Základy operačních systémů
- ↳ NDBI003 Organizace a zpracování dat II
- Roztřídit (resty)
- ↳ Výuka ZS 2005/06 2. ročník
- ↳ Předměty informační bezpečnosti
- ↳ Předměty finanční matematiky
- ↳ Teorie míry a integrálu
- ↳ Numerika
- ↳ Algebra
- ↳ Analýza/kalkulus
- ↳ Matematika obecně
- ↳ Výuka LS 2005/06 2.ročník
- ↳ Základy matematického modelování
- ↳ Finanční management
- ↳ Úvod do optimalizace
- ↳ Numerika
- ↳ Kalkulus
- ↳ Angličtina
- ↳ Diferenciální geometrie
- ↳ Pravděpodobnost a statistika
- ↳ Teorie míry a integrálu II
- ↳ Algebra II
- ↳ Analýza 2b