（プレゼンテーションのスクリーンショット： slideplayer.com/slide/3238789 ）
最も有名で重要なアルゴリズムの問題の1つであるブール式の実行可能性に関するコンピューターサイエンスセンターによる公開講義に皆さんを招待します。 講義は、オンラインコース「アルゴリズム：理論と実践」の学生とのミーティングの一環として開催されます。 メソッド 。 」 時間と場所：12月25日、19：00、BCタイムズ（サンクトペテルブルク、2Aカンテミロフスカヤ通り、4階）。 参加は無料ですが、登録が必要です： goo.gl/IiNvV8
実行可能性の問題は標準的な困難な課題であり、それには膨大な量の研究が実行されています。実用的および理論的です。 特に、年次国際会議はこのタスクに専念しています。 毎年、このタスクのためのプログラムの競争があります（いわゆるsat-solvers）。 このようなプログラムは、多くのアプリケーション分野で積極的に使用されています。 ほんの数ヶ月前、ドナルド・クヌースはモノグラフ「The Art of Programming」にボリューム4Bを追加しました。
講義では、特に次の問題に対処します。
-なぜこの問題を多項式時間で解決するアルゴリズムの場合、100万ドルが投入されるのか。
-貪欲なアルゴリズムと同様に、リターンを伴うブルートフォース、ローカル検索、ランダムウォーク、およびその他の手法を使用して、実行可能性問題のアルゴリズムを開発します。
-sat-solverが実際にどのように使用されているか（いくつかの組み合わせの問題を解決するためにsat-solverを使用します）。