Třídy Booleovských formulí s efektivně řešitelným SATem.
| Thesis title in Czech: | Třídy Booleovských formulí s efektivně řešitelným SATem. |
|---|---|
| Thesis title in English: | Classes of Boolean Formulae with effectively soluable SAT. |
| Key words: | splnitelnost, třídy booleovských formulí, SAT |
| English key words: | satisfiability, classes of boolean formulae, SAT |
| Academic year of topic announcement: | 2013/2014 |
| Thesis type: | rigorosum thesis |
| Thesis language: | čeština |
| Department: | Department of Theoretical Computer Science and Mathematical Logic (32-KTIML) |
| Supervisor: | |
| Author: | hidden - assigned and confirmed by the Study Dept. |
| Date of registration: | 19.12.2013 |
| Date of assignment: | 19.12.2013 |
| Confirmed by Study dept. on: | 19.12.2013 |
| Date and time of defence: | 09.04.2014 00:00 |
| Date of electronic submission: | 19.12.2013 |
| Date of submission of printed version: | 19.12.2013 |
| Date of proceeded defence: | 09.04.2014 |
| Guidelines |
| Úkolem diplomanta je zpracovat přehled výsledků o třídách Booleovských formulí, pro které je problem splnitelnosti (SAT) řešitelný v polynomiálním čase, a pokusit se zjistit vzájemné vztahy těchto tříd (vzhledem k inkluzi) pro dvojice tříd u kterých tento vztah není znám, případně odvodit další zajímavé výsledky o těchto třídách. |
| References |
| Boolean Functions and Computation Models
Clote, Peter; Kranakis, Evangelos Springer Verlag 2002 ISBN: 3-540-59436-1 Boolean Functions : Theory, Algorithms, and Applications Crama, Yves; Hammer, Peter L. dosud nepublikovaný obsáhlý manuskript dostupný na http://www.rogp.hec.ulg.ac.be/Crama/Publications/BookPage.html |
| Preliminary scope of work |
| Problém splnitelnosti Booleovských formulí (SAT) je jedním z nejznámějších výpočetně těžkých problémů v teoretické informatice. Velkou praktickou důležitost proto mají třídy formulí, pro které je SAT řešitelný v polynomiálním čase. Práce se zabývá zkoumáním právě těchto tříd. |