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

コンピュータ科学特論Ⅱ

このページを印刷する

科目名 コンピュータ科学特論Ⅱ
教員名 谷聖一
単位数    2 課程 前期課程 開講区分 文理学部
科目群 地球情報数理科学専攻
学期 前期 履修区分 選択必修
授業概要 アルゴリズムとデータ構造再入門及び計算複雑性理論入門
効率の良いプログラムを作るには， 良い方法（アルゴリズム）とそれに適したデータの保持方法 (データ構造) を用いる必要がある．一方，問題ごとにそれ以上高速化できない限界もある．本講義の前半では，データ構造とアルゴリズム設計の基本を，実際にプログラミングをしながら学ぶ．後半では，問題が持つ本質的な困難性を扱う計算複雑性理論の基礎を学ぶ．
授業のねらい・到達目標 基本的なデータ構造とアルゴリズム設計を応用したプログラム開発ができるようになる．また，問題が持つ本質的な困難性を扱う計算複雑性理論の基礎を理解し，問題解決に応用できるようになる．

この科目は文理学部(学士(理学))のディプロマポリシーDP6及びカリキュラムポリシーCP9に対応している．
授業の方法 前半は，プログラミングコンテストに出題された問題を題材に，講義と演習を織り交ぜながら進める．後半は，講義形式で行う．
本授業の事前・後学習は ，各２時間の学習を目安とする．
授業計画
1 ガイダンス（授業のテーマや到達目標及び授業の方法について説明する）
配列と整列
【事前学習】配列と整列について復習しておく
【事後学習】配列と整列に関する課題に取り組む
2 基本的なデータ構造（スタック・キュー）
【事前学習】スタックとキューについて復習しておく
【事後学習】スタックとキューに関する課題に取り組む
3 探索
【事前学習】スタックとキューを応用した探索について事前に確認する
【事後学習】スタックとキューを応用した探索に関する課題に取り組む
4 最小全域木（１）クラスカルのアルゴリズム
【事前学習】クラスカルのアルゴリズムについて事前に確認する
【事後学習】クラスカルのアルゴリズムに関する課題に取り組む
5 最小全域木（２）プリムのアルゴリズム
【事前学習】プリムのアルゴリズムについて事前に取り組む
【事後学習】プリムのアルゴリズムに関する課題に取り組む
6 最短路探索（１）ダイクストラのアルゴリズム
【事前学習】ダイクストラのアルゴリズムについて復習する
【事後学習】ダイクストラのアルゴリズムに関する課題に取り組む
7 最短経路探索（２）ベルマンフォードのアルゴリズムとワーシャルフロイドのアルゴリズム
【事前学習】ベルマンフォートのアルゴリズムとワーシャルフロイドのアルゴリズムについて事前に確認する
【事後学習】ネットワークフローに関する課題に取り組む
8 分割統治法
【事前学習】分割統治について事前に確認する
【事後学習】分割統治に関する課題に取り組む
9 動的計画法（１）概念・一般論
【事前学習】動的計画法について事前に確認する
【事後学習】動的計画法に関する基本的な課題に取り組む
10 動的計画法（２）応用
【事前学習】動的計画法に関する高度な課題について事前に確認する
【事後学習】動的計画法に関する高度な課題に取り組む
11 計算可能性
【事前学習】計算可能性について事前に確認する
【事後学習】計算可能性に関する課題に取り組む
12 計算量・計算複雑性
【事前学習】時間計算量について事前に確認する
【事後学習】時間に関する課題に取り組む
13 帰着と完全性
【事前学習】帰着について事前に確認する
【事後学習】帰着に関する課題に取り組む
14 充足可能性問題 (SAT)
【事前学習】SAT について事前に確認する
【事後学習】SAT に関する課題に取り組む
15 クックの定理・まとめ（これまでの復習・解説を行い授業の理解を深める）
【事前学習】クックの定理について事前に確認する
【事後学習】クックの定理に関する課題に取り組む
その他
教科書 講義時に資料を配布する．
参考書 J. Kleinberg, E. Tardos 著 『アルゴリズムデザイン』 共立出版 2008年
秋葉拓哉・岩田陽一・北川宜稔 著 『プログラミングコンテストチャレンジブック第２版』 毎日コミュニケーションズ 2014年 第2版
成績評価の方法及び基準 レポート(25%)、授業参画度(75%)
レポートは、提出された講義外の制作物（プログラムソースコード）及びその解説・解析内容により評価する．
授業参画度は、提出された講義中の制作物（プログラムソースコード）により評価する．
オフィスアワー 月曜18時〜19時

↑このページのトップ