シラバス参照
|
シラバス参照
|
| 講義概要/Course Information |
| 科目基礎情報/General Information |
| 授業科目名 /Course title (Japanese) |
計算理論 | ||
|---|---|---|---|
| 英文授業科目名 /Course title (English) |
Theory of Computing | ||
| 科目番号 /Code |
COM605c COM605d | ||
| 開講年度 /Academic year |
2024年度 | 開講年次 /Year offered |
3 |
| 開講学期 /Semester(s) offered |
後学期 | 開講コース・課程 /Faculty offering the course |
情報理工学域 |
| 授業の方法 /Teaching method |
講義 | 単位数 /Credits |
2 |
| 科目区分 /Category |
専門科目 | ||
| 開講類・専攻 /Cluster/Department |
Ⅰ類 | ||
| 担当教員名 /Lecturer(s) |
垂井・武永 | ||
| 居室 /Office |
西9-535(武永)、 東3-824(垂井) | ||
| 公開E-mail |
takenaga@cs.uec.ac.jp, juntarui@uec.ac.jp | ||
| 授業関連Webページ /Course website |
なし | ||
| 更新日 /Last update |
2024/02/29 18:17:10 | 更新状況 /Update status |
公開中 /now open to public |
| 講義情報/Course Description |
| 主題および 達成目標（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、P vs NP予想（垂井） 第１４回：NP完全性の説明（垂井） 第１５回：NP完全性の証明（垂井） (b) 授業の進め方 本講義の前半（第１回～第８回、担当：武永）では、計算可能性の理論について、計算可能／計算不可能とはどのようなことか議論し、実際に計算不可能な問題が存在することを示す。後半（第９回～第１５回、担当：垂井）では、計算量理論について、応用上も重要なＮＰ完全性に重点を置いて説明する |
| 実務経験を活かした 授業内容 (実務経験内容も含む) /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 |
計算可能性、計算量、ＮＰ完全性、チューリング機械 |