文理学部シラバスTOP > 大学院博士前期課程 > 地球情報数理科学専攻 > 情報科学特別講究I
日本大学ロゴ

情報科学特別講究I

このページを印刷する

科目名 情報科学特別講究I
教員名 戸田誠之助
単位数    1 課程 前期課程 開講区分 文理学部
科目群 地球情報数理科学専攻
学期 前期 履修区分 必修
授業概要 講究全体を通して，アルゴリズム論全体を俯瞰し，専門的な文献を読み解く力を養う．特に，処理効率の解析手法，アルゴリズム設計技法と各種データ構造の効用を中心に学習する．
授業のねらい・到達目標 アルゴリズム設計技法と各種データ構造の効用が理解できる．

この科目は文理学部(学士(理学))のディプロマポリシーDP6及びカリキュラムポリシーCP9に対応しています。
授業の方法 教科書を事前に学習し，その内容をまとめた資料を作成し，授業時間に資料に基づいて発表する．アルゴリズム論に関する知識や数学的素養に応じて学習のペースを変えてもよい．教科書だけでは理解困難な事項については，別の文献を調査し，その調査結果を報告してもよい．教科書に記載されている演習問題を時間の許す限り解くことが望ましい．
本授業の事前・事後学習は,合わせて1時間の学習を目安とする．
履修条件 学部における授業等を通して，アルゴリズム論の基礎事項を修得していることが望ましい．
授業計画
1 アルゴリズムの役割と効用
【事前学習】発表用資料を準備する．
【事後学習】アルゴリズムの役割と効用について理解を深める．
2 アルゴリズムの計算量解析（概論）
【事前学習】発表用資料を準備する．
【事後学習】アルゴリズムの計算量解析について理解を深める．
3 アルゴリズム設計技法（概論）
【事前学習】発表用資料を準備する．
【事後学習】アルゴリズム設計技法について理解を深める．
4 計算量関数の上界と下界
【事前学習】発表用資料を準備する．
【事後学習】計算量関数の上界と下界について理解を深める．
5 数学的な準備事項
【事前学習】発表用資料を準備する．
【事後学習】数学的な準備を行う．
6 分割統治法
【事前学習】発表用資料を準備する．
【事後学習】分割統治法について理解を深める．
7 分割統治法の計算量解析（substitution method）
【事前学習】発表用資料を準備する．
【事後学習】分割統治法の計算量解析について理解を深める．
8 分割統治法の計算量解析（recursion-tree method）
【事前学習】発表用資料を準備する．
【事後学習】分割統治法の計算量解析について理解を深める．
9 分割統治法の計算量解析（master method）
【事前学習】発表用資料を準備する．
【事後学習】分割統治法の計算量解析について理解を深める．
10 計算量の確率的解析手法
【事前学習】発表用資料を準備する．
【事後学習】計算量の確率的解析手法について理解を深める．
11 確率的アルゴリズム
【事前学習】発表用資料を準備する．
【事後学習】確率的アルゴリズムについて理解を深める．
12 ヒープ（データ構造）
【事前学習】発表用資料を準備する．
【事後学習】ヒープについて理解を深める．
13 ヒープソートと優先順位キュー
【事前学習】発表用資料を準備する．
【事後学習】ヒープソートと優先順位キューについて理解を深める．
14 クイックソート
【事前学習】発表用資料を準備する．
【事後学習】クイックソートについて理解を深める．
15 クイックソートの計算量解析
【事前学習】発表用資料を準備する．
【事後学習】クイックソートの計算量解析について理解を深める．
その他
教科書 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduction to Algorithms, The MIT Press, 2009, 3 edition
参考書 使用しない
成績評価の方法及び基準 授業参画度(100%)
授業参画度は，毎回の発表用資料（レジメ，プレゼン資料等）をもとに評価します．
オフィスアワー 毎週水曜日１２：１０〜１３：００

↑このページのトップ