| 科目名 |
アルゴリズムとデータ構造 |
| 担当教員 |
酒居 敬一 |
| 対象学年 |
2年 |
クラス |
学部：専門001 |
| 講義室 |
Ａ１０７ |
開講学期 |
１学期 |
| 曜日・時限 |
月５,木５ |
単位区分 |
選択 |
| 授業形態 |
一般講義 |
単位数 |
2 |
| 準備事項 |
|
| 備考 |
|
| 授業の詳細1 |
講義の目的
アルゴリズムとは，情報処理において問題となる対象にどのような操作を加えて処理を行うかという概念である．そして，データ構造とは，情報処理において問題となる対象をどのように整理し表現するかと言う概念である．両者は独立ではなく，適切なデータ構造を用い，そのデータ構造に則した適切なアルゴリズムを用いることで正しく機能する効率の良い情報処理が可能となる．通俗的な表現「アルゴリズム＋データ構造＝プログラム」は両者の関係を良く捉えている．
本講議では，まずアルゴリズムとデータ構造の必要性を説明し，アルゴリズムとデータ構造の概念を理解し，アルゴリズムやデータ構造に関する基礎を習得することを目的とする．
講義の進め方
これまでの計算機言語の授業でも，すでにアルゴリズムとデータ構造の概念は用いられて来ている．本講義では，アルゴリズムとデータ構造をより明示的に取り扱い，情報処理の概念として必要な基礎を修得することを目標とする．
本講義では，アルゴリズムとデータ構造を表現するためにJavaを用いてる． |
| 授業の詳細2 |
達成目標
本講義を修得することにより，以下の能力が身につく．
1.計算機の中での表現と概念的なデータ構造を対応づけて考えることができる．
2.アルゴリズムとは何か，データ構造とは何か，その概念を直観的に理解できる．
3.アルゴリズムとデータ構造との間に密接な関係があり，両者を適切に設計することにより，プログラムが正しく効率的に動くことを理解できる．
4.ソフトウェア仕様を詳細・分解し，一定以下の粒度になったさいに，適切なアルゴリズムとデータ構造とを選択し，仕様に合った設計として変更を加えることができる．
5.配列構造・リスト構造・二分木・ハッシュ等のデータ構造と，その基本操作を理解し，それを実現するクラスのサブクラスを構成することができる．
6.再帰と繰り返しとの差異を理解し，データ構造に応じて適切にアルゴリズムを選択することができる．
7.ソートのアルゴリズムとその効率について理解できる．
8.グラフのアルゴリズムの基本を理解できる．
9.文字列のアルゴリズムを理解できる．
10.難しい問題が存在すること，現実的時間で解けない場合があること，近似的な解法があることを知る． |
| 授業の詳細3 |
講義計画
1. アルゴリズムと計算量
まず，カリキュラム全体における本講義の占める位置について，特にプログラミングとの関係を中心に説明する．その上で，本講義の授業計画と成績評価について説明する．そして，アルゴリズムとデータ構造の役割と，なぜアルゴリズムとデータ構造について学習するのかを理解する．
つぎに，計算量の概念とO記法を導入し，その意味を理解する．配列，スタック，待ち行列，連結リストとい>ったデータ構造と，それを取り扱うアルゴリズムについての理解を助けるため，計算機に実装されたメモリとデータ構造について述べる．
2-5. 探索
まず探索について説明し，線形なデータ構造(配列やリスト)や非線型なデータ構造(木)に於ける探索アルゴリズムを理解する．
つぎに，非線型なデータ構造として平衡木を説明し，その上でのアルゴリズムを理解する．
さいごに，ハッシュを用いた探索についても理解する．
6-9. 整列
あらかじめ定義してある順序に沿ってデータを並べる操作を整列と呼ぶ．
整列は現実のプログラムでも頻繁に用いられる上に，アルゴリズムの学習をするのに大変良い教材となる．まず，アルゴリズムの単純さの代表であるバブルソートやシェルソートを学習し，つぎに，より高速なソートアルゴリズムであるクィックソートやマージソートを学習する．
さいごに，比較によらない方法としてビンソートを学ぶ． |
| 授業の詳細4 |
10-12. グラフのアルゴリズム
まず，グラフについて説明する．そこでは表現法や探索について理解する．
つぎに，各種の連結性や最短路の探索について学習する．
13. 文字列のアルゴリズム
ここでは，文字列の照合アルゴリズムについて学習する．Knuth-Morris-PrattのアルゴリズムやBoyer-Moore>のアルゴリズムなどについて理解する．
プログラムとして実装する場合の高速計算性についても学ぶ．
14-15. 難しい問題
最適な答えを求めることが困難な問題が世の中にはたくさんある．そういった問題についての紹介と，問題のもつ性質について理解する．
そして，NP完全問題や最適化問題の解法について理解する．
さらに，どれだけ高速な計算機をもってしても最適解が現実的な時間で得られない場合，近似的解法を用いる必要があり，そういった解法についても学習する．
16. 理解度確認
これまでの講義内容についての理解度確認を行う． |
| 授業の詳細5 |
テキスト：
『アルゴリズムとデータ構造』， 石畑清著(岩波書店)
ISBN-10: 4000103431
ISBN-13: 978-4000103435
成績評価：
適宜数回の演習を行なうとともにクォータ末に理解度の確認を行なう．合計で100点を満点とし，60点以上を合格(AA, A, B, C)とする．
確認の方法としては，教科書に説明や実装が示されているアルゴリズムを題材として，以下のようにする．
1. プログラミング言語による実装を示し，使用されているアルゴリズムやデータ構造を説明してもらう．
2. アルゴリズムやデータ構造をプログラミング言語で実装してもらう．
3. 専門用語やアルゴリズムやデータ構造の詳細を説明してもらう．
なお，理解度の確認の際には，教科書をはじめとする，紙の資料を参照しても構わない．
＜成績評価の基準＞
ＡＡ：特に優れた成績を示したもの
Ａ ：優れた成績を示したもの
Ｂ ：良好と認められる成績を示したもの
Ｃ ：合格と認められる成績を示したもの
Ｆ ：不合格
履修上の注意：
同時履修すべき必須科目=「情報システム工学実験第１」
備 考：
履修前の受講が望ましい科目：
なし |
| 授業の詳細6 |
|
| 授業の詳細7 |
|
| 授業の詳細8 |
|
| 授業の詳細9 |
|
| 授業の詳細10 |
|