6学期講義/算法数理工学

新着情報

10/7開講.
講義中は板書手段として以外のPCの使用を禁じる。
(一部の教員が授業中のPCの使用を問題視しているみたいです。この授業に限らず、少なくとも指示のあった授業では使用を控えましょう)

科目区分

計数数理:限定選択A

教員

牧野 和久

場所

工61号講義室

教科書・参考書

  • データ構造とアルゴリズム(杉原厚吉(著)、共立出版)
  • アルゴリズムとデータ構造(茨木俊秀(著)、昭晃堂)
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein : Introduction to Algorithm (MITpress)

成績評価

宿題のレポートと期末テスト(場合によっては中間テストも)で評価する。
出席は救済用。

過去問


シケプリ


シラバス

計算機で問題を解くための手続きを明確に記述するアルゴリズムの設計法を学ぶ.ここで大切なことは,機械で実行できるように手続きを明確に記述すること,および記述したアルゴリズムの良さを設計の段階で(コンピュータプログラムに翻訳して走らせて見なくても)見通せることである.そのための基本技術を,整列、探索、グラフ計算,数値計算,幾何計算などの初歩的問題を例にとって学ぶ.

1 算法の良さの計り方
  算法,計算複雑度

2 基本算法
  挿入,削除, 整列, 選択,検索

3 データ構造
  リスト, スタック, キュー, ヒープ,
  ハッシュ法,バケット

4 設計手法
  再帰法, 分割統治法,均衡化,
  逐次添加法, 動的計画法

5 グラフ算法
  深さ優先探索, 幅優先探索,
  強連結成分分解, 最小全域木,
  最短路, 最大流

6 応用算法
  幾何計算,最適化算法など

7 問題の難しさの計り方
  NP,NP完全,NP困難

関連サイト


講義まとめ


  • 最終更新:2009-10-30 13:12:57

このWIKIを編集するにはパスワード入力が必要です

認証パスワード