Dotazy k přednášce:

1. Diskutujte na průsvitce 2, v čem spočívá neefektivita backtrackingu.
2. Co si u backmarkingu pamatuje Mark(Y,b) a BackTo(Y)?
3. Demonstrujte na příkladu, jak funguje backmarking v případě, že je Mark(Y,b)<BackTo(Y).
4. Demonstrujte na příkladu, jak funguje backmarking v případě, že je Mark(Y,b)>=BackTo(Y).
5. Demonstrujte na příkladu problému N královen, jak funguje backmarking.
6. Popište, jak funguje uspořádání hodnot pro backmarking.
7. Popište rozdíl mezi backtrackingem a backmarkingem na pseudokódu pro algoritmus backmarkingu.
8. Co to je cutoff a restart u neúplných stromových prohledávání?
9. Popište algoritmus randomizovaného backtrackingu.
10. Popište algoritmus s omezeným počtu návratů.
11. Proč kombinujeme algoritmus s omezením hloubky s algoritmem s omezeným počtem návratů.
12. Popište, jak funguje prohledávání s kreditem.
13. Popište, jak funguje iterativní rozšiřování.
14. Co to je diskrepance? Jak použijeme diskrepance u prohledávání?
15. Popište princip algoritmu s omezenými diskrepancemi? Jaký je rozdíl, pokud u tohoto algoritmu uvažujeme binární nebo nebinární domény?
16. Popište pseudokód algoritmu s omezenými diskrepancemi.
17. Jakým způsobem je možné zlepšit algoritmus s omezenými diskrepancemi?
18. Popište pseudokód algoritmu ILDS.
19. Popište princip algoritmu s hloubkou omezenými diskrepancemi. V čem spočívá jeho výhoda oproti předchozím dvěma algoritmům s diskrepancemi?
20. Jakým způsobem můžeme porovnat prohledávací algoritmy?
21. Co to jsou náhodné binární CSP problémy?
22. Znáte nějaké aplikačně založené náhodné problémy?
23. Co to je fáze přechodu? Demonstrujte to na řešení náhodného k-SAT problému.