P0450300

データ構造とアルゴリズム

Data Structures and Algorithms

開講部

システム工学部

開講学科

電子情報システム学科

開講学年

2年次

開講時期

前期

単位数

2

単位区分

選択

系列区分

専門

講義区分

講義
講師若木利子この授業の2012年度のアンケートを参照

授業の教育目的及び方針

ソフトウェアの開発では効率的なアルゴリズムとデータ構造の設計・解析が必要になる。本講義では計算機を使って問題を効率的に解く際に必要となる基本的アルゴリズムとその実現に適したデータ構造、及び、計算量について解説し、現実のソフトウェアの設計・開発に応用できる能力を修得させることを目指す。なお本科目の講義の直後に開講されている「プログラミング演習I」の科目で、実際に計算機を用いて本講義内容に関連する例題や課題の演習を行い、本科目に関する種々の手法の深い理解と技術の修得の定着を目指す。

授業内容

1.アルゴリズムとデータ構造の定義(例. ユークリッドの互助法)
2.計算量の定義: O記法とΩ記法
3.基本的データ構造(配列とリスト) 
4.スタック (再帰呼び出し)
5.待ち行列とリングバッファ 
6.グラフの定義と木構造/リストとの関係
7.再帰的データ構造と再帰的アルゴリズム
8.木の走査(前順,間順,後順)と算術式の記法(ポーランド記法)
9.線形探索と番兵,2分探索 
10.2分探索木の構築(挿入)と探索,計算量
11.2分探索木からの削除,平衡木
12. ハッシュ法(衝突,ハッシュ関数, 内部ハッシュと外部ハッシュ) 
13.種々の整列(ソート)の手法と計算量の概要, バブルソート,2分木ソート
14. クイックソートの考え方とアルゴリズム,及び計算量
15. ヒープソートの考え方とアルゴリズム,及び計算量

評価方法

期末試験により評価する。

教科書

必要に応じプリントを配布する。

備考

参考書:「アルゴリズムとデータ構造」石畑 清著(岩波書店)
「プログラミング演習I」と共に履修することが望ましい。

環境との関連

環境に関連しない科目

最終更新 : Thu Sep 20 07:50:47 JST 2012