Survey Propagation pro řešení SAT a CSP

• Thesis title in Czech: Survey Propagation pro řešení SAT a CSP
• Thesis title in English: Survey Propagation for solving SAT a CSP
• Academic year of topic announcement: 2010/2011
• Thesis type: Bachelor's thesis
• Department: Department of Theoretical Computer Science and Mathematical Logic (32-KTIML)
• Supervisor: RNDr. Jan Hric
• Author: hidden - assigned and confirmed by the Study Dept.
• Date of registration: 11.04.2011
• Date of assignment: 11.04.2011
• Confirmed by Study dept. on: 24.04.2012

Guidelines

Předběžně:
Metoda Survey propagation (SP, propagování souhrnů) je nejlepší známá metoda pro řešení těžkých SAT problémů, tj. těch, které jsou blízko přechodové fáze mezi řešitelnými a neřešitelnými problémy. Práce má aplikovat a naprogramovat tuto metodu pro nějaký(-é) jiný problém(y) a určit její základní charakteristiky. Původní metoda je paralelizovatelná a tak otázka paralelizovatelnosti vzniká pro aplikaci na nový problém.

References

S. Russell, P. Norvig: Artificial Intelligence, A Modern Approach, Prentice Hall, Englewood Cliffs, USA,
2003

Preliminary scope of work

Metoda Survey propagation (SP, propagování souhrnů) je nejlepší známá metoda pro řešení těžkých SAT problémů, tj. těch, které jsou blízko přechodové fáze mezi řešitelnými a neřešitelnými problémy. Práce má aplikovat a naprogramovat tuto metodu pro nějaký(-é) jiný problém(y) a určit její základní charakteristiky. Původní metoda je paralelizovatelná a tak otázka paralelizovatelnosti vzniká pro aplikaci na nový problém.