14. CDCL algoritam. Stek literala (trag). Apstraktni sistem pravila za promenu stanja.

0.0(0)
Studied by 0 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/14

encourage image

There's no tags or description

Looks like no tags are added yet.

15 Terms

1
New cards

Šta znači CDCL?

Conflict Driven Clause Learning – učenje klauza na osnovu konflikata.

2
New cards

Koja je glavna ideja CDCL u odnosu na klasični DPLL?

Efikasnija iterativna pretraga uz analizu konflikata i učenje novih klauza.

3
New cards

Zašto CDCL čuva parcijalnu valuaciju, a ne stalno menja formulu?

Tako izbegava ponovljene transformacije velike formule.

4
New cards

Šta predstavlja parcijalna valuacija M?

Konzistentan skup dodeljenih literala; promenljive mogu biti i nedefinisane.

5
New cards

Šta je trag (trail) u CDCL?

Stek označenih literala koji predstavlja trenutnu parcijalnu valuaciju.

6
New cards

Koja su dva tipa literala na tragu?

Literali odlučivanja i izvedeni (propagirani) literali.

7
New cards

Šta su nivoi odlučivanja?

Delovi traga započeti literalom odlučivanja, praćeni njegovim posledicama.

8
New cards

Zašto je stek pogodan za CDCL?

Omogućava efikasno vraćanje unazad uklanjanjem novijih dodela.

9
New cards

Kako se u apstraktnom sistemu opisuje stanje?

Stekom parcijalne valuacije M (a uz analizu konflikata i klauzom C).

10
New cards

Šta radi pravilo Decide?

Dodaje novi nedefinisan literal odlučivanja na novi nivo traga.

11
New cards

Šta radi pravilo UnitPropagate?

Dodaje literal koji je nužno tačan jer su ostali literali njegove klauze netačni.

12
New cards

Šta radi pravilo Backtrack?

Posle konflikta odbacuje poslednju granu i pokušava suprotni literal odlučivanja.

13
New cards

Kada je klauza jedinična u odnosu na M?

Ima jedan nedefinisan literal, a svi ostali su netačni u M.

14
New cards

Kada se može prijaviti SAT za potpunu valuaciju M?

Kad su sve promenljive iz F dodeljene, a nema netačne klauze.

15
New cards

Mini zadatak: M={p}, C=(¬p ∨ q). Šta propagira CDCL?

q, jer je ¬p netačan, pa C postaje jedinična.