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

コンピュータ科学特論Ⅱ

このページを印刷する

令和２年度以降入学者 コンピュータ科学特論Ⅱ
令和元年度以前入学者 コンピュータ科学特論Ⅱ
教員名 谷聖一
単位数    2 課程 前期課程 開講区分 文理学部
科目群 地球情報数理科学専攻
学期 前期 履修区分 選択必修
授業の形態 同時双方向型（Zoom予定。Webex に変更する回もある）

Blackboard コースID: 20213069
授業概要 アルゴリズムとデータ構造再入門及び計算複雑性理論入門
効率の良いプログラムを作るには， 良い方法（アルゴリズム）とそれに適したデータの保持方法 (データ構造) を用いる必要がある．一方，問題ごとにそれ以上高速化できない限界もある．本講義の前半では，データ構造とアルゴリズム設計の基本を，実際にプログラミングをしながら学ぶ．後半では，問題が持つ本質的な困難性を扱う計算複雑性理論の基礎を学ぶ．
授業のねらい・到達目標 基本的なデータ構造とアルゴリズム設計を応用したプログラム開発ができるようになる．
また，問題が持つ本質的な困難性を扱う計算複雑性理論の基礎を理解し，問題解決に応用できるようになる．
授業の方法 授業の形式：【講義】
・レポートを課す課題では，総評を行うことでフィードバックを与える．
・プログラムソースコードを提出する課題では，オンラインジャッジを活用することでフィードバックが得られる．
授業計画
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時間）
その他
教科書 講義時に資料を配布する．
参考書 J. Kleinberg, E. Tardos 著 『アルゴリズムデザイン』 共立出版 2008年
成績評価の方法及び基準 レポート:提出された講義外の制作物（証明・プログラムソースコード）及びその解説・解析内容により評価する．(25%)、授業参画度:提出された講義中の制作物（証明・プログラムソースコード）により評価する．(75%)
オフィスアワー 随時受け付ける。原則、事前にメールで予約すること。（Google Chat または Google Meet）

↑このページのトップ