Dotazy k přednášce

1. Vytvořte hypergraf podmínek pro problém s proměnnými A,B,C,D s doménami {1,..,10} a podmínkami A+B=C, B*C>10, B+C+D>20, C>5.
2. Co to je binární CSP? Uveďte příklad binárního CSP.
3. Jak se vytvoří duální problém k zadanému CSP?
4. Uvedený CSP převeďte pomocí duálního problému na binární CSP. Máte zadány proměnné A,B,C,D,E,F, jejich doména je {0,1} a omezení jsou
   • c1: A + B + F = 1
   • c2: A - C + D = 1
   • c3: D + E - F > 0
   • c4: B + E - F = 0
5. Co to je binarizace? Jaké má výhody a nevýhody?
6. Kdy je CSP problém vrcholově konzistentní?
7. Kdy je hrana A,B hranově konzistentní?
8. Proč konzistence hrany X,Y nezajišťuje konzistenci hrany Y,X?
9. Dokážete vysvětlit algoritmus revize hrany? Pro proměnné A,B s doménami {1,..,5} revidujte hranu B,A s omezením B>A.
10. Jaký je výsledek revize hrany A,B pro předchozí příklad?
11. Popište algoritmus AC-1.
12. Popište, jak funguje algoritmus AC-1 na následujícím příkladu. Máme proměnné A, B,C s doménami {1,...,10} a jsou zadána omezení B<A, A =< C+4.
13. Popište algoritmus AC-3.
14. Jak pracuje algoritmus AC-3 na příkladu uvedeném u AC-1 algoritmu.
15. Dokážete vysvětlit, co to je podpora hodnoty?
16. Uveďte všechny podpory hodnot pro následující problém. Proměnné A, B, C mohou nabývat hodnot 3, 4, 5, a máme omezení A =< B, B > C.
17. Jaké datové struktury se používají v algoritmu na inicializaci podpor, který využívá algoritmus AC-4?
18. Dokážete na pseudokódu algoritmu na inicializaci podpor vysvětlit, jak tento algoritmus funguje?
19. Vysvětlete na následujícím příkladu, jakým způsobem dochází k aktualizaci podpor v průběhu výpočtu algoritmu AC-4, pokud dojde k vyřazení hodnoty b1 z domény proměnné j.
    

    Podpory
20. Dokážete na pseudokódu algoritmu AC-4 vysvětlit, jak tento algoritmus funguje?
21. V čem se liší algoritmus AC-2001 od algoritmu AC-3?
22. Pokud je problém hranově konzistentní, znamená to, že má vždycky řešení? Ukažte to i na příkladu.