1/14
Looks like no tags are added yet.
Šta znači CDCL?
Conflict Driven Clause Learning – učenje klauza na osnovu konflikata.
Koja je glavna ideja CDCL u odnosu na klasični DPLL?
Efikasnija iterativna pretraga uz analizu konflikata i učenje novih klauza.
Zašto CDCL čuva parcijalnu valuaciju, a ne stalno menja formulu?
Tako izbegava ponovljene transformacije velike formule.
Šta predstavlja parcijalna valuacija M?
Konzistentan skup dodeljenih literala; promenljive mogu biti i nedefinisane.
Šta je trag (trail) u CDCL?
Stek označenih literala koji predstavlja trenutnu parcijalnu valuaciju.
Koja su dva tipa literala na tragu?
Literali odlučivanja i izvedeni (propagirani) literali.
Šta su nivoi odlučivanja?
Delovi traga započeti literalom odlučivanja, praćeni njegovim posledicama.
Zašto je stek pogodan za CDCL?
Omogućava efikasno vraćanje unazad uklanjanjem novijih dodela.
Kako se u apstraktnom sistemu opisuje stanje?
Stekom parcijalne valuacije M (a uz analizu konflikata i klauzom C).
Šta radi pravilo Decide?
Dodaje novi nedefinisan literal odlučivanja na novi nivo traga.
Šta radi pravilo UnitPropagate?
Dodaje literal koji je nužno tačan jer su ostali literali njegove klauze netačni.
Šta radi pravilo Backtrack?
Posle konflikta odbacuje poslednju granu i pokušava suprotni literal odlučivanja.
Kada je klauza jedinična u odnosu na M?
Ima jedan nedefinisan literal, a svi ostali su netačni u M.
Kada se može prijaviti SAT za potpunu valuaciju M?
Kad su sve promenljive iz F dodeljene, a nema netačne klauze.
Mini zadatak: M={p}, C=(¬p ∨ q). Šta propagira CDCL?
q, jer je ¬p netačan, pa C postaje jedinična.