シラバス参照
シラバス参照
| 授業科目名 /Course title (Japanese) |
計算理論 | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Theory of Computing | ||
| 科目番号 /Code |
COM605c COM605d | ||
| 開講年度 /Academic year |
2026年度 | 開講年次 /Year offered |
3 |
| 開講学期 /Semester(s) offered |
後学期 | 開講コース・課程 /Faculty offering the course |
情報理工学域 |
| 授業の方法 /Teaching method |
講義 | 単位数 /Credits |
2 |
| 曜限 /Day, Period |
木／Thu 3 | ||
| 科目区分 /Category |
専門科目 | ||
| 開講類・専攻 /Cluster/Department |
Ⅰ類 | ||
| 担当教員名 /Lecturer(s) |
武永 康彦 | ||
| 居室 /Office |
西9-535 | ||
| 公開E-mail |
takenaga@uec.ac.jp | ||
| 授業関連Webページ /Course website |
なし | ||
| 更新日 /Last update |
2026/03/09 11:37:14 | 更新状況 /Update status |
公開中 /now open to public |
| 主題および達成目標 （2,000文字以内） /Themes and goals （up to 2,000 letters） |
本講義では計算機科学理論のうち、「計算可能性の理論」および｢計算量理論｣と呼ばれる分野を扱う。計算可能性の理論においては、計算・アルゴリズムとは何かについて考え、実際に計算不可能な問題が存在することを示す。 計算量理論においては、問題を解くために必要な計算時間や記憶容量などを分析する。このような計算可能性の理論、計算量理論の基本的考え方について理解をしてもらうことが本講義の目標である。 |
|---|---|
| 前もって履修 しておくべき科目 （1,000文字以内） /Prerequisites （up to 1,000 letters） |
離散数学 |
| 前もって履修しておくこ とが望ましい科目 （1,000文字以内） /Recommended prerequisites and preparation （up to 1,000 letters） |
形式言語理論、アルゴリズム論第一 |
| 教科書等 （1,000文字以内） /Course textbooks and materials （up to 1,000 letters） |
教科書：なし 参考書：M.Sipser「計算理論の基礎」共立出版 笠井琢美、戸田誠之助「計算の理論」共立出版 渡辺治「計算可能性・計算の複雑さ入門」近代科学社 など |
| 授業内容とその進め方 （2,000文字以内） /Course outline and weekly schedule （up to 2,000 letters） |
(a)授業内容 第１回：チューリング機械 第２回：チューリング機械の変形と計算能力 第３回：ランダムアクセス機械、計算可能性とチャーチの提唱 第４回：判定可能、認識可能な言語とその性質 第５回：認識可能でない言語 第６回：判定可能でない言語 第７回：帰着 第８回：帰着を用いた判定・認識不可能性の証明 第９回：時間計算量とチューリング機械 第１０回：クラスP、クラスNP 第１１回：NP完全性 第１２回：様々なNP完全問題 第１３回：Cook-Levinの定理、領域計算量とクラスPSPACE 第１４回：PSPACE完全性、クラス間の関係 第１５回：ゲーム・パズルの計算量 (b) 授業の進め方 本講義の前半では、計算可能性の理論について、計算可能／計算不可能とはどのようなことか議論し、実際に計算不可能な問題が存在することを示す。後半では、計算量理論について、応用上も重要なＮＰ完全性に重点を置いて説明する。 |
| 対面授業・遠隔授業の別 /Face-to-face or online lecture |
対面授業 |
| 実務経験を活かした 授業内容 (実務経験内容も含む) /Course content utilizing practical experience |
|
| 授業時間外の学習 （予習・復習等） （1,000文字以内） /Preparation and review outside class （up to 1,000 letters） |
授業中に十分理解できなかったと思われる部分は、ノートや教科書等で理解しておくことが望ましい。 |
| 成績評価方法 および評価基準 （最低達成基準を含む） （1,000文字以内） /Evaluation and grading （up to 1,000 letters） |
試験は行わず、４回程度のレポート課題の結果に基づいて評価を行なう。 計算可能性および計算量理論の基本的概念について理解することが合格の最低条件である。 |
| オフィスアワー：授業相談 （1,000文字以内） /Office hours （up to 1,000 letters） |
なるべく授業終了後に教室で相談すること。それ以外はまずメールで連絡してください。 |
| 学生へのメッセージ （1,000文字以内） /Message for students （up to 1,000 letters） |
なし |
| その他 /Others |
なし |
| キーワード /Keywords |
計算可能性、計算量、チューリング機械、NP完全性 |