[Zk] Hric 11.2.2009

Pokračování přednášky TIN060 Algoritmy a datové struktury I
Magog
Matfyz(ák|ačka) level I
Příspěvky: 15
Registrován: 18. 3. 2008 19:36
Typ studia: Informatika Bc.

[Zk] Hric 11.2.2009

Příspěvek od Magog »

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 podmnožina S tak, že součet prvků v 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 taková, že součet prvků množiny 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.
Naposledy upravil(a) Magog dne 12. 2. 2009 09:48, celkem upraveno 1 x.
Uživatelský avatar
mhb
Matfyz(ák|ačka) level II
Příspěvky: 50
Registrován: 3. 2. 2008 03:38
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Re: [Zk] Hric 11.2.2009

Příspěvek od mhb »

<vtip>
Algoritmus na nalezení nejmenší společné podposloupnosti:
1. Vrátím prázdnou posloupnost.
</vtip>

Ale jinak se mi ta písemka docela líbí. Dobré otázky. :-)
Magog
Matfyz(ák|ačka) level I
Příspěvky: 15
Registrován: 18. 3. 2008 19:36
Typ studia: Informatika Bc.

Re: [Zk] Hric 11.2.2009

Příspěvek od Magog »

Hmm, soudruzi z NDR udelali nekde chybu. Opraveno
Odpovědět

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