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

コンピュータ科学特論I

このページを印刷する

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

このページのトップ