基本情報技術概論I （第４回） 埼玉大学 理工学研究科 堀山 貴史 2011/5/12 基本情報技術概論 I (第４回) アルゴリズム と データ構造 埼玉大学 理工学研究科 堀山 貴史 2008/01/23

データ構造 データ構造 データをどのように記憶するか 基本的なデータ構造 配列 (array) リスト (list) その他のデータ構造 スタック (stack) 待ち行列 (queue, キュー) 木 (tree) ___________ ___________

データ構造： 配列 データを順番にならべて、 添字 でアクセスできるようにしたもの 操作： 参照、探索、更新、削除、挿入 配列 A データ構造： 配列 ________________ データを順番にならべて、 添字 でアクセスできるようにしたもの 操作： 参照、探索、更新、削除、挿入 ________ 配列 A A [1] 30 A [2] 50 A [3] 20 A [4] 70 A [5] 10 …

コンピュータ上での配列 配列 A 二次元配列 A [1] 30 … … A [2] 50 A [3] 20 … … … A [4] 70 メモリ （主記憶装置） A [1] 30 A [1, 1] A [1, 2] … … … A [2, 1] A [2, 2] … A [2] 50 番地 （アドレス） 2000 30 A [3, 1] A [3, 2] … A [3] 20 2001 50 … … … A [4] 70 2002 20 A [5] 10 一次元に変換して メモリに配置する 2003 70 2004 10 … … …

配列の操作 参照 探索 探索キー 70 A [1] 30 A [1] 30 配列Aの 4番は？ A [2] 50 A [2] 50 （探索データ） 70 配列の操作 参照 探索 A [1] 30 A [1] 30 配列Aの 4番は？ A [2] 50 A [2] 50 A [3] 20 A [3] 20 A [4] 70 A [4] 70 A [5] 10 A [5] 10 … … 添字を使って指定 … A[4] 先頭 A[1] から順番に 一致するか調べる

更新 挿入 70 を 更新 A[4] の位置に 35 を 挿入 A [1] 30 A [1] 30 35 A [2] 50 A [2] 50 20 A [3] 20 A [4] 70 35 A [4] 70 A [5] 10 A [5] 10 … … 70 を探索 + 更新 A[4] の場所を空けるため、 後ろに１つずつずらす

削除 削除 （その２） A[4] の位置の データ を 削除 A[4] の位置の データ を 削除 A [1] 30 A [1] 30 50 A [2] 50 A [3] 20 A [3] 20 A [4] 70 A [4] 70 A [5] 10 A [5] 10 … … A[4] が空いたため、 １つずつつめる A[4] に削除マークをつけて、 無いものとして扱う

データ構造： リスト となりの要素の位置（アドレス）を、 ポインタ として明示的に持つ 単方向リスト 双方向リスト 環状リスト データ構造： リスト ________________ となりの要素の位置（アドレス）を、 ポインタ として明示的に持つ ________ 単方向リスト 双方向リスト 環状リスト head (リストの 先頭を指す) 30 30 30 50 50 50 20 20 20 逆方向の探索が容易

コンピュータ上でのリスト 20 となりの要素の位置（アドレス）を、 ポインタ として明示的に持つ 50 2030 … … メモリ （主記憶装置） 2000 2010 30 番地 （アドレス） 2010 30 50 2070 2030 20 20 となりの要素の位置（アドレス）を、 ポインタ として明示的に持つ 2070 50 2030 … …

リストの操作 探索 更新 探索キー 20 を 更新 20 （探索データ） 30 30 50 50 20 20 35 70 70 先頭から順番に ポインタをたどって調べる 20 を探索 + 更新

※ 双方向リストの場合は、 　　逆方向のポインタも 　　同様にケアする必要あり リストの操作 50 の次に 35 を挿入 挿入 削除 20 を 削除 30 30 50 50 35 20 20 70 70 前のデータのポインタを、自分に 自分のポインタを、次のデータに 前のデータのポインタを、 次のデータに

データ構造 基本的なデータ構造 配列 (array) リスト (list) その他のデータ構造 スタック (stack) 待ち行列 (queue, キュー) 木 (tree)

データ構造： スタック push と pop による Last-In First-Out (L I FO) イメージ） 積み上げた書類や本 データ構造： スタック ________________ push と pop による Last-In First-Out (L I FO) イメージ） 積み上げた書類や本 生協の入口の トレイ ___________ 5 push pop 30 50 20

スタックの実現法 配列 リスト … 20 50 30 A [1] A [2] A [3] スタック ポインタ 30 50 20 5 push pop 30 50 20

データ構造： 待ち行列 （キュー） enqueue と dequeue による First-In First-Out (F I FO) データ構造： 待ち行列 （キュー） ________________ enqueue と dequeue による First-In First-Out (F I FO) イメージ） レジの前の行列 ___________ 5 enqueue 30 50 20 dequeue

キューの実現法 配列 リスト … 進行方向 front 5 A [1] 20 enqueue A [2] 50 rear A [3] 30 dequeue front 20 rear 50 30

表は、配列を用いたリストの実現を示しており、 リスト [ 東京、品川、名古屋、新大阪 ] を表している。 練習：　配列を用いたリストの実現 表は、配列を用いたリストの実現を示しており、 リスト [ 東京、品川、名古屋、新大阪 ] を表している。 このリストを、[ 東京、新横浜、名古屋、新大阪 ] に 変化させる操作はどれか。 ここで、A ( i, j ) は、表の第 i 行 第 j 列の要素を表す。 また、→ は代入を表す。 A 列 1 2 行 1 “東京” 2 2 “品川” 3 3 “名古屋” 4 4 “新大阪” 5 “新横浜”

第１の操作 第２の操作 ア 5 → A(1, 2) A(A(1, 2), 2) → A(5, 2) イ 5 → A(1, 2) 練習：　配列を用いたリストの実現 第１の操作 第２の操作 ア 5 → A(1, 2) A(A(1, 2), 2) → A(5, 2) イ 5 → A(1, 2) A(A(2, 2), 2) → A(5, 2) ウ A(A(1, 2), 2) → A(5, 2) 5 → A(1, 2) エ A(A(2, 2), 2) → A(5, 2) 5 → A(1, 2)

１つのスタックだけを用いて出力可能なデータ列はどれか ア. イ. ウ. エ. (H16年度 春) A, D, B, C B, D, A, C 練習：　スタック A, B, C, D の順に到着するデータに対して、 １つのスタックだけを用いて出力可能なデータ列はどれか ア. イ. ウ. エ. (H16年度 春) A, D, B, C B, D, A, C C, B, D, A D, C, A, B ウ A B C A B C A B ウ A A B A D A D A

アルゴリズム

アルゴリズム 問題を解決するための、有限ステップからなる手順 自然言語や、流れ図（フローチャート）で示す 重要 ・ 問題を解く鍵になるアイデアを把握 ・ アイデアを実現する手順を考える 1 → i A(i) = K i + 1 → i 探索成功の処理 探索失敗の処理 No Yes i > n 開 始 終 了 生協に行く 棚のチョコレートを手に持つ レジに行く 財布から代金を払う お釣りがあれば、受け取る チョコレートを食べる

流れ図 （フローチャート） 制御の流れを図で表したもの 基本的な記号 繰り返しの開始と終了 （ループ名、終了条件を 開始や終了 記述） 処理 参考： その他の記号 処理の流れ データの入出力 条件に応じて、 次の処理を変える （分岐条件を記述） 書類を印刷 ディスプレイに表示

情報処理技術者試験での 疑似言語 記述形式 説明 ○ 手続, 変数の名前, 型などの宣言 /* 文 */ 注釈 処 理 ・ 変数 ← 式 処　　理 ・ 変数 ← 式 変数に式を代入する ・ 手続 ( 引数, … ) 手続を呼び出す 条件式 処理１ 処理２ 選択処理 ( if then else ) 処理 前判定繰返し処理 ( while ループ ) 変数：初期値, 条件式, 増分 繰返し処理 ( for ループ )

アルゴリズム (超入門)： X，Y， Z の最大値 開 始 X 3 X → MAX X, Y, Z を入力 Y 2 No Z 5 MAX < Y Yes MAX Y → MAX No MAX < Z Yes y z MAX を出力 Z → MAX x 終 了

開 始 開 始 1 → i 0 → SUM 1 → i 0 → SUM i ≦100 No i ≦100 Yes i + 1 → i アルゴリズム：　1～100 の和 開 始 開 始 1 → i 0 → SUM 初期値設定 1 → i 0 → SUM 繰返し条件 繰返しループ i ≦100 while 型の繰返し No i ≦100 Yes SUM + i → SUM SUM + i → SUM 次の繰返しの準備 i + 1 → i i + 1 → i 繰返しループ SUM を出力 SUM を出力 終 了 終 了

補足説明：　 ２ ｎ と ｌｏｇ 2 ｎ （次回、必要です） 0 回 1 0 回 1 回 2 回 3 回 4 回 5 回 6 回 log 2 n 回 … 1 2 4 8 16 32 64 2 倍 n 2 倍 1 回 2 2 倍 2 回 4 2 倍 3 回 8 2 倍 4 回 16 2 倍 5 回 32 2 倍 6 回 64 2 倍 … … 2 倍 n 回 2 n

A 列 1 2 行 1 “東京” 2 2 “品川” 3 3 “名古屋” 4 4 “新大阪” 5 “新横浜” 第１の操作 第２の操作 ア 練習：　配列を用いたリストの実現 [ 東京、品川、名古屋、新大阪 ] [ 東京、新横浜、名古屋、新大阪 ] A 列 1 2 行 1 “東京” 2 2 “品川” 3 3 “名古屋” 4 4 “新大阪” 5 “新横浜” 第１の操作 第２の操作 ア 5 → A(1, 2) A(A(1, 2), 2) → A(5, 2) イ 5 → A(1, 2) A(A(2, 2), 2) → A(5, 2) ウ A(A(1, 2), 2) → A(5, 2) 5 → A(1, 2) ウ エ A(A(2, 2), 2) → A(5, 2) 5 → A(1, 2)

１つのスタックだけを用いて出力可能なデータ列はどれか ア. 練習：　スタック A, B, C, D の順に到着するデータに対して、 １つのスタックだけを用いて出力可能なデータ列はどれか ア. (H16年度 春) A, D, B, C B C A A B B C D B C D

１つのスタックだけを用いて出力可能なデータ列はどれか イ. 練習：　スタック A, B, C, D の順に到着するデータに対して、 １つのスタックだけを用いて出力可能なデータ列はどれか イ. (H16年度 春) B, D, A, C A B A B A C A A C D A C D

１つのスタックだけを用いて出力可能なデータ列はどれか エ. 練習：　スタック A, B, C, D の順に到着するデータに対して、 １つのスタックだけを用いて出力可能なデータ列はどれか エ. (H16年度 春) D, C, A, B A B C D A B C A B A A B C D A B C

この文面は、TOKYO TECH OCW の利用 条件を参考にしました この教材のご利用について この教材は、以下に示す利用条件の下で、著作権者にわざわざ許諾を求めることなく、無償で自由にご利用いただけます。講義、自主学習はもちろん、翻訳、改変、再配布等を含めて自由にご利用ください。 非商業利用に限定 この教材は、翻訳や改変等を加えたものも含めて、著作権者の許諾を受けずに商業目的で利用することは、許可されていません。 著作権の帰属 この教材および教材中の図の著作権は、次ページ以降に示す著作者に帰属します。この教材、または翻訳や改変等を加えたものを公開される場合には、「本教材 (or 本資料) は http://www.al.ics. saitama-u.ac.jp/horiyama/OCW/ の教材です (or 教材を改変したものです」 との旨の著作権表示を明確に実施してください。なお、この教材に改変等を加えたものの著作権は、次ページ以降に示す著作者および改変等を加えた方に帰属します。 同一条件での頒布・再頒布 この教材、または翻訳や改変等を加えたものを頒布・再頒布する場合には、頒布・再頒布の形態を問わず、このページの利用条件に準拠して無償で自由に利用できるようにしてください。

この教材のご利用について 配布場所 http://www.al.ics.saitama-u.ac.jp/horiyama/OCW/ この powerpoint ファイルの著作者 堀山 貴史　2007-2011 horiyama@al.ics.saitama-u.ac.jp 改変等を加えられた場合は、お名前等を追加してください 図の著作者 p. 3 ～ 7, 9 ～ 11, 13, 15, 17 ～ 19, 24, 29, 31 ～ 33 クリップアート : Microsoft Office Online / クリップアート p. 8, 13 メモリ : http://webweb.s92.xrea.com/ その他 堀山 貴史