od 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
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
Este poznamka k casu na test, pretoze som to nikde nenasiel - je ho priblizne tolko, co na skusku, cize cca 1.5-2h.
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.