文理学部シラバスTOP > 大学院博士前期課程 > 地球情報数理科学専攻 > 情報科学特別講究II
日本大学ロゴ

情報科学特別講究II

このページを印刷する

令和２年度以降入学者 情報科学特別講究II
教員名 谷聖一
単位数    1 課程 前期課程 開講区分 文理学部
科目群 地球情報数理科学専攻
学期 後期 履修区分 選択必修
授業形態 対面授業
Canvas LMSコースID・コース名称 X09761B1　2024情報科学特別講究Ⅱ（谷聖一・後・金3）
授業概要 コンピュータ科学に関する技術
授業のねらい・到達目標 情報科学特別講究Ⅰに続いて，コンピュータ科学の技術が社会全体における応用について広範囲にわたって情報を収集・分析することにより、コンピュータ科学の現状を正確に把握できるようになることを目標とする。
授業の形式 講究
授業の方法 基本的に GitHub, Scrapbox, Discord でコミュニケーション行う．
コンピュータ科学あるいはその周辺分野の中から各自研究課題を定め，演習を行う．
各自に割り当てられた研究課題に関する教科書や基礎的な研究論文を学習し、ゼミでの発表や議論を通じてその分野に関する理解を深めていく．テーマによっては，ソフトウェア開発も行う．
授業計画
1 計算量クラスと基本定理：構成可能性と階層定理
【事前学習】構成可能性と階層定理に関する発表の準備を事前に行う （1時間）
【事後学習】構成可能性と階層定理に関する議論で生じた課題を検討する （2時間）
【授業形態】対面授業
2 計算量クラスPとNP：クラスP
【事前学習】クラスPの定義及び基本性質を事前に確認する （2時間）
【事後学習】クラスPに関する議論で生じた課題を検討する （1時間）
【授業形態】対面授業
3 計算量クラスPとNP：クラスNP
【事前学習】クラスNPの定義及び基本性質を事前に確認する （2時間）
【事後学習】クラスNPに関する議論で生じた課題を検討する （1時間）
【授業形態】対面授業
4 計算量クラスPとNP：多項式時間版の帰着と困難性・完全性
【事前学習】多項式時間版の帰着と困難性・完全性に関する発表の準備を事前に行う （2時間）
【事後学習】多項式時間版の帰着と困難性・完全性に関する議論で生じた課題を検討する （1時間）
【授業形態】対面授業
5 計算量クラスPとNP：NP-完全問題
【事前学習】NP-完全問題に関する発表の準備を事前に行う （2時間）
【事後学習】NP-完全問題に関する議論で生じた課題を検討する （1時間）
6 計算量クラスPとNP：Cook-Levinの定理の証明
【事前学習】Cook-Levinの定理の証明に関する発表の準備を事前に行う （2時間）
【事後学習】Cook-Levinの定理の証明に関する議論で生じた課題を検討する （1時間）
【授業形態】対面授業
7 計算量クラスPとNP：様々なNP-完全問題
【事前学習】様々なNP-完全問題に関する発表の準備を事前に行う （2時間）
【事後学習】様々なNP-完全問題に関する議論で生じた課題を検討する （1時間）
【授業形態】対面授業
8 基本な計算量クラスとそれらの関係：基本的な計算量クラス
【事前学習】ランダムアクセス機械　の定義及び基本性質を事前に確認する （2時間）
【事後学習】ランダムアクセス機械 に関する議論で生じた課題を検討する （1時間）
【授業形態】対面授業
9 基本な計算量クラスとそれらの関係：補集合の計算量クラスと Immerman-Szelepc ́enyi の定理
【事前学習】補集合の計算量クラスと Immerman-Szelepc ́enyi の定理 に関する発表の準備を事前に行う （2時間）
【事後学習】補集合の計算量クラスと Immerman-Szelepc ́enyi の定理に関する議論で生じた課題を検討する （1時間）
【授業形態】対面授業
10 基本な計算量クラスとそれらの関係：基本的な計算量クラスに対する完全性
【事前学習】基本的な計算量クラスに対する完全性に関する発表の準備を事前に行う （2時間）
【事後学習】基本的な計算量クラスに対する完全性に関する議論で生じた課題を検討する （1時間）
【授業形態】対面授業
11 基本な計算量クラスとそれらの関係：神託付チューリング機械・チューリング帰着
【事前学習】神託付チューリング機械・チューリング帰着に関する発表の準備を事前に行う （2時間）
【事後学習】神託付チューリング機械・チューリング帰着に関する議論で生じた課題を検討する （1時間）
【授業形態】対面授業
12 基本な計算量クラスとそれらの関係：多項式時間階層
【事前学習】神託付チューリング機械・チューリング帰着の定義及び基本性質を事前に確認する （2時間）
【事後学習】神託付チューリング機械・チューリング帰着に関する議論で生じた課題を検討する （1時間）
【授業形態】対面授業
13 確率的な計算
【事前学習】確率的な計算に関する発表の準備を事前に行う （2時間）
【事後学習】確率的な計算に関する議論で生じた課題を検討する （1時間）
【授業形態】対面授業
14 確率計算の計算量クラス
【事前学習】確率計算の計算量クラスに関する発表の準備を事前に行う （2時間）
【事後学習】確率計算の計算量クラスに関する議論で生じた課題を検討する （1時間）
15 対話型証明系とグラフ同型判定問題
【事前学習】対話型証明系とグラフ同型判定問題に関する発表の準備を事前に行う （2時間）
【事後学習】対話型証明系とグラフ同型判定問題に関する議論で生じた課題を検討する （1時間）
【授業形態】対面授業
その他
教科書 講義時に指示する
参考書 講義時に指示する
成績評価の方法及び基準 授業参画度:毎回の開発内容・発表の内容・議論への参加の状況により評価する。(100%)
授業参画度は、毎回のディスカッションにより評価する。
オフィスアワー 随時、Discord で対応する。
備考 このシラバスでは、計算量をテーマとした場合の内容を記述している。
選択したテーマに応じて、同様の内容を行う。

↑このページのトップ