学部・大学院区分
Undergraduate / Graduate

情報・博前

時間割コード
Registration Code

2550064

科目区分
Course Category

科目名　【日本語】
Course Title

計算論基礎特論B

科目名　【英語】
Course Title

Basic Topic in Theory of Computation B

コースナンバリングコード
Course Numbering Code

GSI156057J

担当教員　【日本語】
Instructor

番原　睦則 ○

担当教員　【英語】
Instructor

BAMBARA Mutsunori ○

単位数
Credits

開講期・開講時間帯
Term / Day / Period

春２期月曜日３時限
Spring2 Mon 3

対象学年
Year

１年
1

授業形態
Course style

開講系（学部）・開講専攻（大学院）
Subject

必修・選択
Required / Selected

授業の目的　【日本語】
Goals of the Course(JPN)

本講義では，知識駆動型ソフトウェアを構築するためのアプローチとして，
命題論理の充足可能性判定(SAT; Boolean Satisfiability)と制約充足問題
(CSP; Constraint Satisfaction Problem)について学ぶ．

授業の目的　【英語】
Goals of the Course

In this course, we study Boolean Satisfiability (SAT) and Constraint
Satisfaction Problem (CSP) as approaches to developing
knowledge-driven software.

到達目標　【日本語】
Objectives of the Course(JPN)

本講義では，知識駆動型ソフトウェアを構築するためのアプローチとして，
命題論理の充足可能性判定(SAT; Boolean Satisfiability)と制約充足問題
(CSP; Constraint Satisfaction Problem)について学ぶ．以下に挙げる3つを
達成目標とする．

1. SAT/CSPの基礎を理解する．
2. SAT/CSPソルバーの代表的なアルゴリズムを習得する．
3. SAT/CSP技術を現実問題に応用する力を身に付ける．

到達目標　【英語】
Objectives of the Course

授業の内容や構成
Course Content / Plan

1. 制約充足問題(CSP)
2. CSPソルバー
3. 制約伝播アルゴリズム
4. 命題論理の充足可能性判定(SAT)
5. SATソルバー
6. 矛盾からの節学習
7. 制約充足問題のSAT符号化

履修条件・関連する科目
Course Prerequisites and Related Courses

関連する科目: 計算論基礎特論A

成績評価の方法と基準
Course Evaluation Method and Criteria

講義中に与える演習課題の評価30%，期末試験70%，合計100点満点で60点以上
を合格とする．

教科書・参考書
Textbook/Reference book

必要に応じて配布する．

課外学習等（授業時間外学習の指示）
Study Load(Self-directed Learning Outside Course Hours)

授業で出される演習問題を授業時間外で解き，授業内容の理解を深めておくこと．

授業開講形態等
Lecture format, etc.

遠隔授業（オンデマンド型）で行う場合の追加措置
Additional measures for remote class (on-demand class)