[Zap] 20.1.2011

[Zap] 20.1.2011

Příspěvekod netsir » 20. 1. 2011 10:15

Zapocet probihal ve stejnym duchu jako obvykle, otazky tentokrat byly:
    1) TS prijimajici jazyk anbncn.
    2) PRF sign(x).
    3) Dokazte, ze Batoh je NP-uplny.
    4) Ukazte, ze splnitelnost HORN-SAT patri do P.
netsir
 

Re: [Zap] 20.1.2011

Příspěvekod oskee » 20. 1. 2011 11:26

Ja by som len dodal nastin riesenia ulohy 4) (tie prve 3 by mali byt bezproblemove, respektive ich riesenia najdete roztrusene v topicu), pretoze vacsina ludi, s ktorymi som sa potom bavil, s tym mala problem. Ja sam som to nemal cele, ale Kucera prehlasil, ze som bol na polceste :wink:

Cize - HORN-SAT - test splnitelnosti hornovskej KNF (taka, ktora ma v kazdej klauzuli najviac 1 kladny literal) v polynomialnom case.

1) vsetky literaly nastavime na 0. Tym mame zarucene pravdive vsetky klauzule, ktore su bez kladneho literalu.
2) prejdeme klauzule obsahujuce len jeden kladny literal a tieto nastavime na 1.
3) tu som skoncil v domneni, ze to staci, Kucera mi vsak povedal ze nie a snazil sa sformulovat nejaky protipriklad, ale po chvili to vzdal, pretoze tam cakali dalsi ludia na opravenie. Povedal vsak nieco o tom, ze to zlyha na nejakom pripade, kde je v KNF nejaka klauzula, kde su 2 literaly, kladny a zaporny a ten zaporny je potom ako samostatna kladna klauzula niekde inde; takze je treba spravit este nejaky jeden korekcny prechod - aky, to neviem, ale aspon som vas varoval, ze 1) a 2) nestaci 8)

Este poznamka k casu na test, pretoze som to nikde nenasiel - je ho priblizne tolko, co na skusku, cize cca 1.5-2h.
oskee
 

Re: [Zap] 20.1.2011

Příspěvekod ucm » 21. 1. 2011 12:49

Pro problem ekv. HORN SATU (<= 1 negativni literal v konjunkco):

1. najdi konjunkci, ktera obsahuje pouze negativni literal a zadny pozitivni. Pokud neni, tak jdi na 6.
2. Promenna X v konjunkci musi byt 0 (jinak by konjunkce byla 0 a tedy cela formule by byla 0)
3. Odtran konjunkci z formule (uz o ni vime hodnotu, jenom by prekazela)
4. Najdivsechny konjunkce, ktere obsahuji formulis promennou X a zjisti, jak to s nimi je (= dej do prom v konjunkci hodnotu 0 a zjisti, jak to ovlivni hodnotu konjunkce).
4.1 Pokud konjunkce obsahuje pouze 1 pozitivni literal X, tedy konjunkce je (X), tak je to spor, a formule nema splnitelne reseni
4.2 Pokud konjunkce obsahuje not X, tak je pravdiva a konjunkci muzeme odstranit
4.3 ...nechce se mi to sem vsechno psat, ale proste do konjunkce dosadite nutnou hodnotu a spoctete, jak vypada nova konjunkce, zda jeste muze byt pravdiva, zda je nezbytna atd.
5. Pokud existuje konjunkce s prave 1 negativnim literalem, jdi na 1.
6. Nyni mame pouze konjunkce s alespon 1 pozitivnim literalem, takze kdz do vsech zbyvajicich promennych dosadime 1, tak i formule bude 1 a formule je tedy splnitelna
ucm
 


Zpět na NTIN090 Základy složitosti a vyčíslitelnosti

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník