od Magog » 11. 2. 2009 15:42
Zřejmě standartní písemka, ale byl jsem teprve na prvním termínu.
1) Vytvořit vyhledávací stroj algoritmem Aho-Corasicková na základě množiny hledaných slov.
2) a) Obecný popis úloh vhodných pro dynamické programování.
b) Popis algoritmu pro hledání nejdelší společné podposloupnosti.
3) Dokažte, že maximální tok je roven minimálnímu řezu.
4) Jsou dány následující problémy:
Instance problému Součet podmnožiny je konečná množina S obsahující přirozená čísla a přirozené číslo b. Odpověď na problém je ano, pokud existuje S´ podmnožina S tak, že součet prvků v S´ je roven b.
Instance problému Rovnost (jmenovalo se to nejak jinak, ale nevim presne jak, mozna nekdo doplni) je konečná množina S obsahující přirozená čísla. Odpověď na problém je ano, pokud existuje S´ taková, že součet prvků množiny S´ a jejího doplňku (tedy množiny S\S´) jsou si rovny.
Popište polynomiální algoritmus převodu Součtu množiny na Rovnost.
Zřejmě standartní písemka, ale byl jsem teprve na prvním termínu.
1) Vytvořit vyhledávací stroj algoritmem Aho-Corasicková na základě množiny hledaných slov.
2) a) Obecný popis úloh vhodných pro dynamické programování.
b) Popis algoritmu pro hledání nejdelší společné podposloupnosti.
3) Dokažte, že maximální tok je roven minimálnímu řezu.
4) Jsou dány následující problémy:
Instance problému Součet podmnožiny je konečná množina [i]S[/i] obsahující přirozená čísla a přirozené číslo [i]b[/i]. Odpověď na problém je ano, pokud existuje [i]S´[/i] podmnožina [i]S[/i] tak, že součet prvků v [i]S´[/i] je roven [i]b[/i].
Instance problému Rovnost (jmenovalo se to nejak jinak, ale nevim presne jak, mozna nekdo doplni) je konečná množina [i]S[/i] obsahující přirozená čísla. Odpověď na problém je ano, pokud existuje [i]S´[/i] taková, že součet prvků množiny [i]S´[/i] a jejího doplňku (tedy množiny [i]S\S´[/i]) jsou si rovny.
Popište polynomiální algoritmus převodu Součtu množiny na Rovnost.