Zkouška - Mareš 4.2.2019

Pokračování přednášky TIN060 Algoritmy a datové struktury I
WhyExactlyDeer
Matfyz(ák|ačka) level I
Příspěvky: 1
Registrován: 4. 2. 2019 11:09
Typ studia: Informatika Bc.

Zkouška - Mareš 4.2.2019

Příspěvek od WhyExactlyDeer »

1. Třídící sítě - napsat vše, co o tom víme
2. Máme množinu slov a chceme spočítat jejich četnosti v nějakém řetězci. Požadavek je, aby byl výpočet lineární vůči délce řetězce společně se slovy, které počítáme.
3. Najděte převod z "existuje 3D-párování" na "mějme matici A a vektor b celočíselné, rovnice Ax=b má řešení kde x je vektor pouze nul a jedniček"

Možná řešení
1. Ani ho moc nezajímal důkaz funkčnosti separátoru, ale nespoléhal bych se na to.
2. Použijeme Aho-Corasicková, jen nebudeme chodit po zpětných hranách, protože to nás stojí čas, ale každému vrcholu budeme počítat návštěvnost. Na konci projdeme automat směrem od listů (například využijeme zásobníku FILO) a hodnotu návštěvnosti přičteme i vrcholu na zkratkové hraně. (Tam jsme ještě nebyli, proto se návštěvnosti vhodně rozdistribuují) Poté se podíváme do všech koncových stavů a návštěvnost udává, kolikrát se daná jehla v řetězci vyskytla.
3. Mějme pro každý prvek řádek matice, který kóduje pro všechny kompatibilní trojice, zda se v nich vyskytuje (A_ij = 1 když i-tý prvek leží v j-té trojici). Rozměry má tedy 3p*r. Vektor x pak udává, které trojice použijeme a vektor b nastavíme na samé jedničky, protože požadujeme, aby se každý prvek (tedy řádek) zúčastnil pouze jednou.
Štěpán Stenchlák
Odpovědět

Zpět na „TIN061 Algoritmy a datové struktury II“