検索したい科目／教員名／キーワードを入力し「検索開始｣ボタンをクリックしてください。
※教員名では姓と名の間に１文字スペースを入れずに、検索してください。
コンピュータ科学特論Ⅱ
| 令和２年度以降入学者 | コンピュータ科学特論Ⅱ | ||||
|---|---|---|---|---|---|
| 教員名 | 谷聖一 | ||||
| 単位数 | 2 | 課程 | 開講区分 | 文理学部 | |
| 科目群 | 地球情報数理科学専攻 | ||||
| 学期 | 前期 | 履修区分 | 選択必修 | ||
| 授業の形態 | 対面授業 Blackboard コースID: 20221462 |
|---|---|
| 授業概要 | 計算論入門及び計算複雑性理論入門 効率の良いプログラムを作るには， 良い方法（アルゴリズム）とそれに適したデータの保持方法 (データ構造) を用いる必要がある．一方，問題ごとにそれ以上高速化できない限界もある．本講義の前半では計算論の基本を，後半では問題が持つ本質的な困難性を扱う計算複雑性理論の基礎を学ぶ． |
| 授業のねらい・到達目標 | 計算可能性などの計算論の基礎を理解する． また，問題が持つ本質的な困難性を扱う計算複雑性理論の基礎を理解し，問題解決に応用できるようになる． |
| 授業の方法 | 授業の形式：【講義】 ・レポートを課す課題では，総評を行うことでフィードバックを与える． ・学部の指示により遠隔形式で実施することになった場合は，同時双方向型授業（Zoom）とする． 対面参加できない学生の要件は，学部の方針に従う． 学部が定める要件を満たし，オンライン参加が認められた場合の受講方法： ・授業時間帯にZoomにて授業に参加する． |
| 授業計画 | |
|---|---|
| 1 |
ガイダンス（授業のテーマや到達目標及び授業の方法について説明する） 計算論と計算複雑性理論の問題意識 【事前学習】「データ構造」と「アルゴリズム」について復習しておく （2時間） 【事後学習】計算論と計算複雑性理論の問題意識に関する課題に取り組む （2時間） |
| 2 |
自然数
【事前学習】自然数について事前に確認する （2時間） 【事後学習】自然数に関する課題に取り組む （2時間） |
| 3 |
ゲーデル数
【事前学習】動的計画法について事前に確認する （2時間） 【事後学習】動的計画法に関する基本的な課題に取り組む （2時間） |
| 4 |
有限オートマトン
【事前学習】動的計画法に関する高度な課題について事前に確認する （2時間） 【事後学習】動的計画法に関する高度な課題に取り組む （2時間） |
| 5 |
有限オートマトンと正則言語
【事前学習】自然数とゲーデル数について事前に取り組む （2時間） 【事後学習】自然数とゲーデル数に関する課題に取り組む （2時間） |
| 6 |
非決定性プッシュダウンオートマトンと文脈自由言語
【事前学習】形式言語とオートマトンについて事前に取り組む （2時間） 【事後学習】形式言語とオートマトンに関する課題に取り組む （2時間） |
| 7 |
計算モデル
【事前学習】計算モデルについて事前に取り組む （2時間） 【事後学習】計算モデルに関する課題に取り組む （2時間） |
| 8 |
計算可能性
【事前学習】計算可能性について事前に取り組む （2時間） 【事後学習】計算可能性に関する課題に取り組む （2時間） |
| 9 |
帰着と完全性
【事前学習】帰着について事前に確認する （2時間） 【事後学習】帰着に関する課題に取り組む （2時間） |
| 10 |
時間計算量
【事前学習】時間計算量について事前に確認する （2時間） 【事後学習】時間計算量に関する課題に取り組む （2時間） |
| 11 |
領域計算量
【事前学習】領域計算量について事前に確認する （2時間） 【事後学習】領域計算量に関する課題に取り組む （2時間） |
| 12 |
計算量クラス
【事前学習】計算量クラスについて事前に確認する （2時間） 【事後学習】計算量クラスに関する課題に取り組む （2時間） |
| 13 |
クラスPとクラスNP（同時双方向型）
【事前学習】クラスPとクラスNPについて事前に確認する （2時間） 【事後学習】クラスPとクラスNPに関する課題に取り組む （2時間） |
| 14 |
充足可能性問題 (SAT)
【事前学習】SAT について事前に確認する （2時間） 【事後学習】SAT に関する課題に取り組む （2時間） |
| 15 |
クックの定理・まとめ（これまでの復習・解説を行い授業の理解を深める）
【事前学習】クックの定理について事前に確認する （2時間） 【事後学習】クックの定理に関する課題に取り組む （2時間） |
| その他 | |
|---|---|
| 教科書 | 講義時に資料を配布する． |
| 参考書 | Michael Sipser, Introduction to the Theory of Computation, Course Technology Ptr, 2012, 3 edition John Hopcroft, Rajeev Motwani, Jeffrey Ullman 『Introduction to Automata Theory, Languages, and Computation』 Addison Wesley 2006年 第3版 |
| 成績評価の方法及び基準 | レポート:提出された講義外の制作物（証明・プログラムソースコード）及びその解説・解析内容により評価する．(25%)、授業参画度:提出された講義中の制作物（証明・プログラムソースコード）により評価する．(75%) 基本的対面出席者も Zoom 参加者も Blackboard, Google Classroom, OneDrive, Google Drive, Google Chat でコミュニケーション行う． |
| オフィスアワー | 随時受け付ける。原則、事前にメールで予約すること。（Google Chat または Google Meet） |