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

コンピュータ科学特論Ⅲ

このページを印刷する

科目名 コンピュータ科学特論Ⅲ
教員名 谷 聖一
単位数    2 課程     開講区分 文理学部
学期 後期 履修区分 選択必修
授業テーマ アルゴリズムとデータ構造再入門及び計算複雑性理論入門
授業のねらい・到達目標 効率の良いプログラムを作るには, 良い方法(アルゴリズム)とそれに適したデータの保持方法 (データ構造) を用いる必要がある.一方,問題ごとにそれ以上高速化できない限界もある.本講義の前半では,データ構造とアルゴリズム設計の基本を,実際にプログラミングをしながら学ぶ.後半では,問題が持つ本質的な困難性を扱う計算複雑性理論の基礎を学ぶ.
授業の方法 前半は,プログラミングコンテストに出題された問題を題材に,講義と演習を織り交ぜながら進める.後半は,講義形式で行う.
事前学修・事後学修,授業計画コメント 事前・事後とも,演習に取り組むこと.
授業計画
11.ガイダンス・配列と整列
22.基本的なデータ構造(スタック・キュー)
33.探索
44.最小全域木1 クラスカルのアルゴリズム
55.最小全域木2 プリムのアルゴリズム
66.最短路探索1 ダイクストラのアルゴリズム
77.最短経路探索2 ベルマンフォードのアルゴリズムとワーシャルフロイドのアルゴリズム
88.分割統治法
99.動的計画法(1)
1010.動的計画法(2)
1111.計算可能性
1212.計算量・計算複雑性
1313.充足可能性問題
1414.課題学習
1515.クックの定理・まとめ
その他
教科書 講義時に資料を配布する.
参考書 J. Kleinberg, E. Tardos 著 『アルゴリズムデザイン』 共立出版 2008年
秋葉拓哉・岩田陽一・北川宜稔 著 『プログラミングコンテストチャレンジブック第2版』 毎日コミュニケーションズ 2014年 第2版
成績評価の方法及び基準 平常点(60%)、授業内テスト(20%)、授業参画度(20%)
オフィスアワー 月曜18時〜19時

このページのトップ