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.
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:)...
[quote="Norek"]1) Goldberg (napsat algoritmus, znění lemmat a invariantů, co si vzpomenem, potom na 1 ukázal prstem a chtěl dokázat)[/quote]
viz jakakoli skripta/wiki (v orig. nekdy jako "push-relabel maximum flow algorithm")
[quote="Norek"]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í)[/quote]
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)
[quote="Norek"]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í.[/quote]
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).
[quote="Norek"]*) Danou množinu náhrdelníků rozdělit do tříd ekvivalencí.[/quote]
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.