Survey Propagation pro řešení SAT a CSP

• Název práce v češtině: Survey Propagation pro řešení SAT a CSP
• Název v anglickém jazyce: Survey Propagation for solving SAT a CSP
• Akademický rok vypsání: 2010/2011
• Typ práce: bakalářská práce
• Ústav: Katedra teoretické informatiky a matematické logiky (32-KTIML)
• Vedoucí / školitel: RNDr. Jan Hric
• Řešitel: skrytý - zadáno a potvrzeno stud. odd.
• Datum přihlášení: 11.04.2011
• Datum zadání: 11.04.2011
• Datum potvrzení stud. oddělením: 24.04.2012

Zásady pro vypracování

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.

Seznam odborné literatury

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

Předběžná náplň práce

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.