(A screenshot from the presentation: slideplayer.com/slide/3238789)
We invite all to the open lecture Computer Science of the center devoted to a problem of feasibility of Boolean formulas — one of the most known and important algorithmic tasks. Lecture will take place within a meeting with listeners of an online course "Algorithms: theory and practice. Methods". Time and venue: On December 25, 19:00, BTs of Tayms (St. Petersburg, Kantemirovskaya St. 2A, 4 floor). Participation is free, but registration is required: goo.gl/IiNvV8
Problem of feasibility — a canonical difficult task on which the huge number of researches is carried out: both practical, and theoretical. In particular, annual international conference is devoted to this task. Every year there take place competitions of programs for this task (so-called sat-solver). Such programs are actively used in many application areas. Just several months ago Donald Cnut added volume 4B of the monograph "Programming Art" which third is devoted to a problem of feasibility.
In lecture the following questions will be considered, in particular:
— why for the algorithm solving this problem for polynomial time one million dollars is put;
— as greedy algorithms, search with returns, local search, random walks and other technicians are used for algorithm elaboration for a problem of feasibility;
— how exactly sat-solver are used in practice (we will use sat-solver for a solution of some combinatory task).
This article is a translation of the original post at habrahabr.ru/post/273505/
If you have any questions regarding the material covered in the article above, please, contact the original author of the post.
If you have any complaints about this article or you want this article to be deleted, please, drop an email here: firstname.lastname@example.org.
We believe that the knowledge, which is available at the most popular Russian IT blog habrahabr.ru, should be accessed by everyone, even though it is poorly translated.
Shared knowledge makes the world better.