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

コンピュータ科学特論Ⅱ

このページを印刷する

令和2年度入学者 コンピュータ科学特論Ⅱ
令和元年度以前入学者 コンピュータ科学特論Ⅱ
教員名 谷聖一
単位数    2 課程 前期課程 開講区分 文理学部
科目群 地球情報数理科学専攻
学期 前期 履修区分 選択必修
授業の形態 遠隔授業（「オンライン型（同時双方向）」）形式で実施する．Hangouts meet by Google を用いる予定である（Zoom, Webex, Blackboard Collaborate Ultra に変更する回もある）．
ただし，第5回，第10回，第15回を遠隔授業（「課題研究型」）形式で実施する．
授業概要 アルゴリズムとデータ構造再入門及び計算複雑性理論入門
効率の良いプログラムを作るには， 良い方法（アルゴリズム）とそれに適したデータの保持方法 (データ構造) を用いる必要がある．一方，問題ごとにそれ以上高速化できない限界もある．本講義の前半では，データ構造とアルゴリズム設計の基本を，実際にプログラミングをしながら学ぶ．後半では，問題が持つ本質的な困難性を扱う計算複雑性理論の基礎を学ぶ．
授業のねらい・到達目標 基本的なデータ構造とアルゴリズム設計を応用したプログラム開発ができるようになる．
また，問題が持つ本質的な困難性を扱う計算複雑性理論の基礎を理解し，問題解決に応用できるようになる．

この科目は文理学部(学士(理学))のディプロマポリシーDP6及びカリキュラムポリシーCP9に対応している．
授業の方法 5月11日から8月1日までの授業実施日（12週）に，第5回，第10回，第15回以外の12回を実施する．
遠隔授業（「課題研究型」）形式で実施する第5回，第10回，第15回については，授業中に指示する．
前半は，プログラミングコンテストに出題された問題を題材に，講義と演習を織り交ぜながら進める．後半は，講義形式で行う．
・レポートを課す課題では，総評を行うことでフィードバックを与える．
・プログラムソースコードを提出する課題では，オンラインジャッジを活用することでフィードバックが得られる．
授業計画
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 帰着と完全性（「オンライン型（同時双方向）」遠隔授業）
【事前学習】帰着について事前に確認する （2時間）
【事後学習】帰着に関する課題に取り組む （2時間）
14 充足可能性問題 (SAT)（「オンライン型（同時双方向）」遠隔授業）
【事前学習】SAT について事前に確認する （2時間）
【事後学習】SAT に関する課題に取り組む （2時間）
15 クックの定理・まとめ（これまでの復習・解説を行い授業の理解を深める）（「課題研究型」遠隔授業）
【事前学習】クックの定理について事前に確認する （2時間）
【事後学習】クックの定理に関する課題に取り組む （2時間）
その他
教科書 講義時に資料を配布する．
参考書 J. Kleinberg, E. Tardos 著 『アルゴリズムデザイン』 共立出版 2008年
秋葉拓哉・岩田陽一・北川宜稔 著 『プログラミングコンテストチャレンジブック第２版』 毎日コミュニケーションズ 2014年 第2版
成績評価の方法及び基準 レポート:提出された講義外の制作物（プログラムソースコード）及びその解説・解析内容により評価する．(25%)、授業参画度:提出された講義中の制作物（プログラムソースコード）により評価する．(75%)
オフィスアワー 月曜18時〜19時

↑このページのトップ