文理学部シラバスTOP > 大学院博士前期課程 > 地球情報数理科学専攻 > コンピュータ科学特論Ⅱ
日本大学ロゴ

コンピュータ科学特論Ⅱ

このページを印刷する

令和２年度以降入学者 コンピュータ科学特論Ⅱ
教員名 谷聖一
単位数    2 課程     開講区分 文理学部
科目群 地球情報数理科学専攻
学期 前期 履修区分 選択必修
授業形態 対面授業
Blackboard ID 20231436
授業概要 計算論入門及び計算複雑性理論入門
効率の良いプログラムを作るには， 良い方法（アルゴリズム）とそれに適したデータの保持方法 (データ構造) を用いる必要がある．一方，問題ごとにそれ以上高速化できない限界もある．本講義の前半では計算論の基本を，後半では問題が持つ本質的な困難性を扱う計算複雑性理論の基礎を学ぶ．
授業のねらい・到達目標 計算可能性などの計算論の基礎を理解する．
また，問題が持つ本質的な困難性を扱う計算複雑性理論の基礎を理解し，問題解決に応用できるようになる．
授業の形式 講義
授業の方法 第1回目授業までに，本授業の Google Classroom 及び本授業用 Google Chat スペースに参加すること．
参加方法は Blackboard にて告知する．なお，Blackboard をこの目的以外に使用することはない．

本講義の前半では計算論の基本を，後半では問題が持つ本質的な困難性を扱う計算複雑性理論の基礎を学ぶ．
レポートを課す課題では，総評を行うことでフィードバックを与える．

オンライン参加が認められた場合の受講方法：授業時間帯に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版
成績評価の方法及び基準 レポート:提出された講義外の制作物（証明・プログラムソースコード）及びその解説・解析内容により評価する．(40%)、授業参画度:提出された講義中の制作物（証明・プログラムソースコード）により評価する．(60%)
Google Classroom, Google Drive, Google Chat でコミュニケーションを行う．
原則として，Blackboard と Slack は使用しない．
オフィスアワー 随時，Google Chat で受け付ける．
なお，対面を希望する場合は事前に Google Chat でで予約すること．

↑このページのトップ