アルゴリズム設計E (藤原 暁宏)
科目名: アルゴリズム設計E (01) Algorithm Design E
担当教員: 藤原 暁宏 (大学院情報工学研究院電子情報工学研究系) fujiwara@cse.kyutech.ac.jp
情報科目 選択必修科目 2単位
3年 前期 月曜4限目 1301講義室
授業の概要
“アルゴリズム”は、良いプログラムを書くために理解しておかなければならない必須知識である。本講義では、アルゴリズムについて考え方や原理を理解させ、アルゴリズムの善し悪しについて理論的に評価を行う方法を説明する。また、アルゴリズムのいくつかの基本的なパラダイムについて、その概念、計算量を説明し、効率のよいアルゴリズムの作成方法を教授する。最後に、問題の複雑さについても簡単に触れる。(関連する学習教育目標:C-2-2)
カリキュラムにおけるこの授業の位置付け
本講義では、情報系の計算機科学分野において重要なアルゴリズムの理論的な設計、解析手法について講義する。1年後期の”データ構造とアルゴリズム”、及び、2年前期の”プログラム設計”の単位を修得していることを前提とする。
授業項目 (授業計画)
- (1) アルゴリズムの基礎(評価基準、漸近的評価)
- (2) アルゴリズムの基本データ構造(配列、連結リスト、スタック、キュー)
- (3) アルゴリズムにおける基本概念(木、再帰)
- (4) データの探索(2分探索法、ハッシュ法)
- (5) ソートアルゴリズム1(挿入ソート、ヒープソート)
- (6) ソートアルゴリズム2(クイックソート、安定なソート)
- (7) アルゴリズムの設計手法1(分割統治法)
- (8) アルゴリズムの設計手法2(グリーディ法,動的計画法)
- (9) アルゴリズムの設計手法3(バックトラック法,分枝限定法)
- (10) グラフアルゴリズム(グラフを格納するデータ構造,最短経路問題)
- (11) 多項式と行列(多項式の計算、行列積のアルゴリズム)
- (12) 文字列照合アルゴリズム(ボイヤー-ムーア法)
- (13) アルゴリズムの限界(問題のクラス、解くことのできない問題)
- (14) 問題演習
- (15) 期末試験
- (2) アルゴリズムの基本データ構造(配列、連結リスト、スタック、キュー)
授業の進め方
教科書、及び、配布資料を中心とした講義を行なう。また、各講義の最後に時間を設け課題による演習を行う。期末試験を1回実施する。
授業の達成目標 (学習・教育目標との関連)
この講義では、電子情報工学科の学習・教育目標(C-2-2)に掲げられている「計算機を使ってソフトウェアにより実現できる応用技術を習得し、理解している。」という目標を達成するため、計算機科学分野の基礎概念であるアルゴリズムの基本的手法を理解させるとともに、アルゴリズムの評価手段である漸近的計算量や計算の複雑さについても修得させる。これにより、以下の内容の基本的事項を理解し、それに関する基本的問題を解くことができることを目標とする。
- (1) アルゴリズムの時間計算量の概念と計算方法を理解する。
- (2) 基本的アルゴリズムの動作を理解し、簡単なアルゴリズムの作成ができるようにする。
- (3) 計算の複雑さの概念について理解する。
- (2) 基本的アルゴリズムの動作を理解し、簡単なアルゴリズムの作成ができるようにする。
成績評価の基準および評価方法
毎回の演習課題(30%)により達成目標(1),(2),(3)の達成度を段階的に評価する。また,期末試験(70%)においては達成目標(1),(2),(3)を総合的に評価する。
キーワード
アルゴリズム、漸近的計算量,計算可能性
教科書
下記の教科書を使用するとともに,講義資料を毎回配付する。なお、配布資料はWebにて閲覧可能である。
藤原 暁宏 著: アルゴリズムとデータ構造(森北出版)
参考書
- 茨木俊秀 著: Cによるアルゴリズムとデータ構造(昭晃堂)
- 五十嵐善英、西谷泰昭 共著: アルゴリズムの基礎(コロナ社)