| 科目名 |
アルゴリズムとデータ構造１ |
| 担当教員 |
酒居 敬一 |
| 対象学年 |
2年 |
クラス |
学部：専門001 |
| 講義室 |
Ａ１０６ |
開講学期 |
１学期 |
| 曜日・時限 |
月３,木３ |
単位区分 |
選択 |
| 授業形態 |
一般講義 |
単位数 |
2 |
| 準備事項 |
|
| 備考 |
|
| 授業の詳細1 |
講義の目的
アルゴリズムとは，情報処理において問題となる対象にどのような操作を加えて処理を行うかという概念である．そして，データ構造とは，情報処理において問題となる対象をどのように整理し表現するかと言う概念である．両者は独立ではなく，適切なデータ構造を用い，そのデータ構造に則した適切なアルゴリズムを用いることで正しく機能する効率の良い情報処理が可能となる．通俗的な表現「アルゴリズム＋データ構造＝プログラム」は両者の関係を良く捉えている．
本講議では，まずアルゴリズムとデータ構造の必要性を説明し，アルゴリズムとデータ構造の概念を理解し，アルゴリズムやデータ構造に関する基礎を習得することを目的とする．
講義の進め方
「計算機言語第1」と「計算機言語第2」ではプログラミングの構文要素を重点的に学習して来た．これまでの計算機言語の授業でも，すでにアルゴリズムとデータ構造の概念は用いられて来ている．本講義では，アルゴリズムとデータ構造をより明示的に取り扱い，情報処理の概念として必要な基礎を修得することを目標とする．
本講義では，アルゴリズムとデータ構造を表現するためにC言語を用いてる． |
| 授業の詳細2 |
達成目標
本講義を修得することにより，以下の能力が身につく．
１．計算機の中での表現と概念的なデータ構造を対応づけて考えることができる．
２．アルゴリズムとは何か，データ構造とは何か，その概念を直観的に理解できる．
３．アルゴリズムとデータ構造との間に密接な関係があり，両者を適切に設計することにより，プログラムが正しく効率的に動くことを理解できる．
４．ソフトウェア仕様を詳細・分解し，一定以下の粒度になったさいに，適切なアルゴリズムとデータ構造とを選択し，仕様に合った設計として変更を加えることができる．
５．配列構造・リスト構造・二分木・ハッシュ等のデータ構造と，その基本操作を理解し，それを実現するクラスのサブクラスを構成することができる．
６．再帰と繰り返しとの差異を理解し，データ構造に応じて適切にアルゴリズムを選択することができる．
７．ソートのアルゴリズムとその効率について理解できる． |
| 授業の詳細3 |
講義計画
アルゴリズムとデータ構造入門
１．まず，カリキュラム全体における本講義の占める位置について，特にプログラミングとの関係を中心に説明を受ける．その上で，本講義の授業計画と成績評価についての説明を受ける．
次に，アルゴリズムとデータ構造の役割と，なぜアルゴリズムとデータ構造について学習するのかを理解する．
２．アルゴリズムとデータ構造基礎
オブジェクト指向の概念とJava言語について再度触れる．
さらに，計算量の概念とO記法を導入し，その意味を理解する．
３．メモリとデータ構造
ここでは，配列，スタック，待ち行列，連結リストといったデータ構造と，それを取り扱うアルゴリズムについての理解を助けるため，計算機に実装されたメモリとデータ構造について述べる．
４．プログラムとアルゴリズム
つづいて，二分木と言った非線形なデータ構造と，これを扱うアルゴリズム，特に再帰的なアルゴリズムについて学ぶ．つぎにハッシュやソートと言った良く利用されるデータ構造やアルゴリズムの概観を得る．
５．配列
配列は線形構造を持つデータ型の中では最も長い歴史を持ち，また最も良く使われる．ここでは，配列とそれに対する基本的なデータの取り扱いを学ぶ．
６．連結リスト
参照型を用いると様々なデータ構造を構成することができる．特に Java言語では参照型の扱いが整理されていることが特徴の一つである．ここでは，線形リストとその操作アルゴリズムを学習する．
７．スタック
スタックはLIFO (Last In First Out)のデータアクセスを行う線形データ構造である．ここでは，スタックとそれに対する基本的なデータの取り扱いを学ぶ． |
| 授業の詳細4 |
８．待ち行列
待ち行列はFIFO (First In First Out)のデータアクセスを行う線形データ構造である．
ここでは，待ち行列とそれに対する基本的なデータの取り扱いを学ぶ．
９．二分木
線形リストは探索が遅い．これを解決するデータ構造の一つに二分木がある．ここでは，二分木のデータ構造と操作アルゴリズムについて学習し，その操作の計算量を理解する．
１０．探索
探索アルゴリズムについて学習し，二分探索木やソートやハッシュの必要性について理解する．ここでは，まず線形探索を学習し，二分探索，ハッシュ法について学習をすすめる．
１１．ハッシュ
ハッシュテーブルは巧妙に構成されたデータ構造であり，その探索アルゴリズムは二分木よりさらに速い．ここではハッシュテーブルの構成法を学習する．
１２．ソート
あらかじめ定義してある順序に沿ってデータを並べる操作をソートと呼ぶ．
ソートは現実のプログラムでも頻繁に用いられる上に，アルゴリズムの学習をするのに大変良い教材となる．まず，アルゴリズムの単純さの代表であるバブルソートを学習し，つぎに，より高速なソートアルゴリズムであるクィックソートを学習する．
１３．再帰的アルゴリズム
再帰は重要なアルゴリズムの概念である．とくに参照型を用いた柔軟なデータ構造を扱う場合には，基本的に再帰的アルゴリズムを用いるしかない．ここでは，再帰的アルゴリズムを詳細に検討し，その動作の理解をする．
１４．くり返し処理と再帰的処理
くり返し処理と再帰的処理をとりあげ，記述の簡潔さ，プログラムとして記述したときの効率，それらの間の変換について理解する．
１５．クォータ末試験
講義の理解度を調べる試験を行う．
１６．まとめ
クォータ末試験の解説の後，本講義をまとめる． |
| 授業の詳細5 |
テキスト：
『アルゴリズムとデータ構造』， 石畑清著(岩波書店)
成績評価：
適宜数回の演習を行なうとともにクォータ末に試験を行なう．合計で100点を満点とし，60点以上を合格(AA, A, B, C)とする．再試験はしない。
＜成績評価の基準＞
ＡＡ：特に優れた成績を示したもの
Ａ ：優れた成績を示したもの
Ｂ ：良好と認められる成績を示したもの
Ｃ ：合格と認められる成績を示したもの
Ｆ ：不合格
履修上の注意：
同時履修すべき必須科目=「情報システム工学実験第１」
備 考：
JABEE「情報ネットワークシステム工学教育プログラム」必須科目
履修前の受講が望ましい科目：
なし
|
| 授業の詳細6 |
|
| 授業の詳細7 |
|
| 授業の詳細8 |
|
| 授業の詳細9 |
|
| 授業の詳細10 |
|