Zkouška 21.12.2021 Mareš

Pokračování přednášky TIN060 Algoritmy a datové struktury I
chabrokolice
Matfyz(ák|ačka) level I
Příspěvky: 2
Registrován: 5. 6. 2021 08:36
Typ studia: Informatika Bc.

Zkouška 21.12.2021 Mareš

Příspěvek od chabrokolice »

1. KMP - všechno na co si člověk vzpomene
2. Parlamentní kluby: V parlamentu s n poslanci je m různých klubů Jeden poslanec může být členem mnoha různých klubů. Každý klub potřebuje zvolit svého předsedu a tajemníka tak, aby všichni předsedové a tajemníci byli navzájem různé osoby (tedy aby nikdo neseděl na více křeslech)
3. 3D párování -> SAT

Řešení:
2. Vytvořím si bipartitní graf, kde v jedné partitě jsou poslanci a v druhé funkce (za každý klub jeden předseda a jeden tajemník). Spojím poslance s funkcemi co můžou vykonávat. Nad tím třeba FF najdu maximální párování. Koreknost a časová a prostorová složitost.
3. Pořídím si proměnné t_x, které budou 1 pokud příslušná trojice je v párování a 0 pokud ne. Přidám dva typy klauzulí:
Pokud dvě trojice představované t_k a t_l sdílí vrchol, tak potřebuji zařídit to, že maximálně jedna z proměnných bude pravdivá. Přidám klauzuli neg(t_k) or neg(t_l) (vznikne z implikace t_k -> neg(t_l) respektive t_l -> neg(t_k))
Pro každý vrchol přidám klauzuli zařizující, že aspoň jedna trojice, které je součástí, je v párování (třeba když je vrchol v trojicích představovaných t_1, t_5, t_13, tak přidám klauzuli t_1 or t_5 or t_13)
Problém tvoří vrcholy, které nejsou součástí žádné trojice. Ty se nijak neprojeví po převodu, ale původní úlohu dělají neřešitelnou. Při převodu tedy ověřím, že každý vrchol je součástí aspoň jedné trojice. Když ne, tak za převod prohlásím třeba x and neg(x).
Nějak oargumentovat to, že převod je polynomiální.
Odpovědět

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