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

コンピュータ科学特論Ⅱ

このページを印刷する

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

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

オンライン参加が認められた場合の受講方法：授業時間帯に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 計算量クラス NP と NP-困難性・NP-完全性
【事前学習】計算量クラス NP の基本性質について事前に確認する （2時間）
【事後学習】計算量クラス NP と NP-完全性に関する課題に取り組む （2時間）
【授業形態】対面授業
11 種々の NP-完全問題
【事前学習】NP-完全問題について事前に確認する （2時間）
【事後学習】NP-完全問題に関する課題に取り組む （2時間）
【授業形態】対面授業
12 SAT の NP-困難性の証明
【事前学習】SAT の NP-困難性の証について事前に確認する （2時間）
【事後学習】SAT の NP-困難性の証に関する課題に取り組む （2時間）
【授業形態】対面授業
13 様々な計算量クラス
【事前学習】様々な計算量クラスについて事前に確認する （2時間）
【事後学習】様々な計算量クラスに関する課題に取り組む （2時間）
【授業形態】対面授業
14 領域計算量に基づく計算量クラス
【事前学習】領域計算量に基づく計算量クラスについて事前に確認する （2時間）
【事後学習】領域計算量に基づく計算量クラスに関する課題に取り組む （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 でコミュニケーションを行う．
原則として，Canvas LMS と Slack は使用しない．
オフィスアワー 随時，Google Chat で受け付ける．
なお，対面を希望する場合は事前に Google Chat でで予約すること．

↑このページのトップ