Zkouška Mareš 22.12.2011

Pokračování přednášky TIN060 Algoritmy a datové struktury I
Norek
Matfyz(ák|ačka) level I
Příspěvky: 2
Registrován: 22. 12. 2011 21:11
Typ studia: Informatika Bc.

Zkouška Mareš 22.12.2011

Příspěvek od Norek »

1) Goldberg (napsat algoritmus, znění lemmat a invariantů, co si vzpomenem, potom na 1 ukázal prstem a chtěl dokázat)
2) Dokázat NP-úplnost problému: Zda existuje 01 vektor x, že pro danou celočíselnou matici A a celočíselný vektor b platí: Ax = b (napověděl, že to máme dokázat převodem z 3D párování)
3) Jsou dány 2 náhrdelníky, máme dokázat, jestli jsou si ekvivalentní. Náhrdelník je cyklická posloupnost písmenek. 2 náhrdelníky jsou si ekvivalentní, pokud se jeden dá z druhého dostat rotací písmenek a/nebo inverzí.
*) Danou množinu náhrdelníků rozdělit do tříd ekvivalencí.
mathemage
Matfyz(ák|ačka) level III
Příspěvky: 130
Registrován: 14. 1. 2011 10:03
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

Re: Zkouška Mareš 22.12.2011

Příspěvek od mathemage »

Aby se nereklo, tak se pokusim aspon neco zodpovedet - mne samotnyho to totiz stvalo, kdyz jsem na neco nemohl prijit a nemohl jsem najit nikde odpoved:)...
Norek píše:1) Goldberg (napsat algoritmus, znění lemmat a invariantů, co si vzpomenem, potom na 1 ukázal prstem a chtěl dokázat)
viz jakakoli skripta/wiki (v orig. nekdy jako "push-relabel maximum flow algorithm")
Norek píše:2) Dokázat NP-úplnost problému: Zda existuje 01 vektor x, že pro danou celočíselnou matici A a celočíselný vektor b platí: Ax = b (napověděl, že to máme dokázat převodem z 3D párování)
x ... bitvektor pritomnosti trojic (tj. indikator, zda trojice bude vybrana do parovani)
A ... vrcholy "indexujou" radky, trojice "indexuji" sloupce; radek je bitvektor s jednickami u sloupcu, jejichz v trojicich se vyskytuje; analogicky sloupce ukazuji jednicky u radku/vrcholu, ktere tyto 3ice obsahuji.
b ... same "1" (skalarni soucin radku s "x" je pocet 3ic, ve kterych se vyskytuje)
Norek píše:3) Jsou dány 2 náhrdelníky, máme dokázat, jestli jsou si ekvivalentní. Náhrdelník je cyklická posloupnost písmenek. 2 náhrdelníky jsou si ekvivalentní, pokud se jeden dá z druhého dostat rotací písmenek a/nebo inverzí.
Nejprve musime mit jistotu, ze nahrdelniky jsou stejne dlouhe. Pak je vezmeme, nekde ho rozstrihneme, z jednoho udlame KMP automat, z druheho vytvorime seno 2x za sebou zopakovanim a automatem v nem najdem prvni nahrdelnik (bude to jeho rotace). Udelame dalsi seno reverzi (pro inverzi nahrdelniku).
Norek píše:*) Danou množinu náhrdelníků rozdělit do tříd ekvivalencí.
Nejdrive roztridime do skupin s nahrdelniky stejne velikosti. Pro kazdou skupinu zvlast vyresime: misto KMP automatu udelame automat Aho-Corasickove a z kazdeho nahrdelniku udelame sena vyse uvedenym zpusobem. Prohledanim a nalezenim vyskytu roztridime do skupiny, ktera urci prislusnou rotaci.
Carpe Diem!
Odpovědět

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