データ構造とアルゴリズム論 第6章 探索のアルゴリズム

Slides:



Advertisements
Similar presentations
プログラミング 平成24年1月11日 森田 彦.
Advertisements

プログラミング 平成25年10月29日 森田 彦.
プログラミング 平成22年10月20日 森田 彦.
プログラミング 平成24年10月16日 森田 彦.
データ構造とアルゴリズム論 第5章 整列(ソート)のアルゴリズム
プログラミング 平成25年12月3日 森田 彦.
プログラミング 平成25年11月19日 森田 彦.
第10回 整列 ~ バブルソート,挿入ソート,選択ソート~
データ構造とアルゴリズム論 第5章 整列(ソート)のアルゴリズム
データ構造とアルゴリズム論 第5章 レコード構造を使った処理-クラスの利用
プログラミング 平成24年10月23日 森田 彦.
プログラミング 平成23年10月19日 森田 彦.
データ構造とアルゴリズム論 第4章 レコード構造を使った処理-クラスの利用
第10回 ソート(1):単純なソートアルゴリズム
データ構造とアルゴリズム論 第9章 木構造 平成16年12月21日 森田 彦.
岩井 儀雄 コンピュータ基礎演習  ー探索、整列ー 岩井 儀雄
データ構造とアルゴリズム論 第6章 探索のアルゴリズム
①データ構造 ②アルゴリズム ③プログラム言語 ④マークアップ言語
データ構造とアルゴリズム論 第2章 配列(構造)を使った処理
プログラミング 平成25年12月10日 森田 彦.
ネットワークプログラミング論 平成28年12月12日 森田 彦.
プログラミング 平成24年10月30日 森田 彦.
データ構造とアルゴリズム論 第7章 探索のアルゴリズム
データ構造とアルゴリズム論 第9章 木構造 平成17年12月20日 森田 彦.
データ構造とアルゴリズム論 第2回目テスト 平成15年12月9日 森田 彦.
データ構造とアルゴリズム論 第8章 再帰処理 平成15年12月2日 森田 彦.
プログラミング 平成25年11月5日 森田 彦.
データ構造と アルゴリズム論 平成29年9月27日 森田 彦.
ネットワークプログラミング論 平成28年12月26日 森田 彦.
プログラミング 平成22年11月24日 森田 彦.
プログラミング 平成23年12月21日 森田 彦.
ネットワークプログラミング論 平成28年10月31日 森田 彦.
データ構造とアルゴリズム論 第4章 レコード構造を使った処理-クラスの利用
データ構造とアルゴリズム論 第3章 ファイルを用いたデータ入出力2
データ構造とアルゴリズム論 第3章 ファイルを用いたデータ入出力
データ構造とアルゴリズム論 第7章 再帰処理 平成17年12月6日 森田 彦.
データ構造とアルゴリズム論 第6章 整列(ソート)のアルゴリズム
データ構造とアルゴリズム論 第1章 アルゴリズムの表現-流れ図
プログラミングⅠ 平成30年10月29日 森田 彦.
ネットワークプログラミング論 平成28年12月19日 森田 彦.
データ構造とアルゴリズム論 第9章 木構造 平成29年12月20日 森田 彦.
データ構造とアルゴリズム論 第9章 木構造 平成30年6月27日 森田 彦.
データ構造とアルゴリズム論 第2回目テスト 平成16年12月14日 森田 彦.
データ構造とアルゴリズム論 第5章 整列(ソート)のアルゴリズム
データ構造とアルゴリズム論 第5章 整列(ソート)のアルゴリズム
プログラミング 4 整列アルゴリズム.
データ構造とアルゴリズム論 第4章 レコード構造を使った処理-クラスの利用
2009/10/23 整列アルゴリズム (1) 第4講: 平成21年10月23日 (金) 4限 E252教室 コンピュータアルゴリズム.
プログラミング 4 探索と計算量.
データ構造とアルゴリズム論 第5章 整列(ソート)のアルゴリズム
プログラミングⅠ 平成30年10月22日 森田 彦.
プログラミングⅠ 平成31年1月7日 森田 彦.
プログラミング 平成22年12月15日 森田 彦.
データ構造とアルゴリズム論 第4章 レコード構造を使った処理-クラスの利用
情報数理Ⅱ 第11章 データ構造 平成29年1月18日.
データ構造とアルゴリズム (第5回) 静岡大学工学部 安藤和敏
基本情報技術概論(第10回) 埼玉大学 理工学研究科 堀山 貴史
プログラミング 平成24年11月13日 森田 彦.
データ構造とアルゴリズム論 第6章 探索のアルゴリズム
基本情報技術概論(第5回) 埼玉大学 理工学研究科 堀山 貴史
基本情報技術概論(第5回) 埼玉大学 理工学研究科 堀山 貴史
データ構造とアルゴリズム論 第7章 再帰処理 平成16年11月30日 森田 彦.
プログラミングⅠ 平成30年12月10日 森田 彦.
ソートのプログラムの流れ 配列の中身を小さい順に並び替える a[1],a[2],…a[n]の値を順に出力する
データ構造とアルゴリズム論 第9章 連結リスト
プログラミング 平成24年12月11日 森田 彦.
プログラミング 平成28年10月25日 森田 彦.
Q q 情報セキュリティ 第7回:2005年5月27日(金) q q.
プログラミング 平成28年10月18日 森田 彦.
プログラミング論 バイナリーサーチ 1.
Presentation transcript:

データ構造とアルゴリズム論 第6章 探索のアルゴリズム データ構造とアルゴリズム論 第6章 探索のアルゴリズム 平成28年6月10日 森田 彦

理解度チェック1(問題1) 空欄①~③には以下のどの順で数字が並びますか?適切な並びを選択して下さい。 1.4 3 8   2. 4 8 3 3. 3 4 8 4.3 8 4    5. 8 3 4

理解度チェック1 解答 空欄①~③に入る適切な並びは? 1.4 3 8 2. 4 8 3 3. 3 4 8 4.3 8 4 5. 8 3 4 理解度チェック1 解答 空欄①~③に入る適切な並びは? 1.4 3 8   2. 4 8 3 3. 3 4 8 4.3 8 4    5. 8 3 4 A 1 2 3 4 3 8 1 A[1]とA[2]を比較し、A[1]<A[2]なので交換する。 4 ① ② ③ 1 8 3

理解度チェック2(問題2) 空欄①~⑤には以下のどの順で数字が並びますか?適切な並びを選択して下さい。 1.12 10 7 5 9 1.12 10 7 5 9    2.12 10 7 9 5 3.12 10 9 5 7 4.12 10 9 7 9

理解度チェック2 解答 i=0 i=1 i=2 空欄①~⑤に入る適切な並びは? 1.12 10 7 5 9 2. 12 10 7 9 5 理解度チェック2 解答 空欄①~⑤に入る適切な並びは? 1.12 10 7 5 9   2. 12 10 7 9 5 3.12 10 9 5 7 4. 12 10 9 7 9 A 1 2 3 4 10 12 7 5 9 i=0 10 12 7 5 9 12 10 10 12 10 i=1 12 10 7 5 9 10 10 i=2 12 10 7 5 9 9 7 7 9

理解度チェック3(問題3) 空欄①に入る最も適切な数値は次のいずれですか? 1.2   2. 3 3.4 4.5 5. 6

理解度チェック3 解答 1.2 2. 3 3.4 4.5 5. 6 iの初期値は、整列済み配列の末端の要素番号。 理解度チェック3 解答 空欄①に入る最も適切な数値は次のいずれですか? 1.2   2. 3 3.4 4.5 5. 6 iの初期値は、整列済み配列の末端の要素番号。 今の場合、A[3]までが整列済み。 したがって、答は3。

探索とは? あるデータ群から、目的のデータと合致するものを探し出す、という処理。→検索とも言う。  Webページの検索機能の強化→現在急速に発展 本章では、最も基本的な探索アルゴリズムを学習。

本章(本日)の学習のねらい 基本的な探索アルゴリズムを学習し、その処理の流れを理解する。 → 線形探索、2分探索 基本的な探索アルゴリズムを学習し、その処理の流れを理解する。              → 線形探索、2分探索 探索アルゴリズムの効率について考察する。 探索アルゴリズムを実際のプログラムに応用する。

6-1 線形探索 端から順番に探索する方法 3を発見! 例:カードの中から数字の3を探す。 5 1 3 6-1 線形探索 端から順番に探索する方法  例:カードの中から数字の3を探す。 5 1 3 3を発見! 流れ図で表すと・・・ → p.98参照

最大(2n+1)回の比較が必要 → 改良の余地は? → 番兵法へ(p.99) <線形探索のアルゴリズム> 開始 A[1]~A[n]にデータ保管済み Noの入力 探したい数字を入力 データの終端のチェック i ← 1 毎回必要? No i≦n Yes ’ありませんでした。’ Yes A[i] =No No i,’番目にありました。’ i ← i+1 次をめくる 終了 最大(2n+1)回の比較が必要 → 改良の余地は? → 番兵法へ(p.99)

最大比較回数が減った! <番兵法のアルゴリズム> A[1]~A[n]にデータ保管 最後の1回だけ! 開始 Noの入力 i ← 1 データ終端を見分ける番兵の用意 A[n+1] ← No データの終端のチェック A[i] =No Yes 最後の1回だけ! No i≦n No i ← i+1 Yes ’ありませんでした。’ i,’番目にありました。’ 終了 最大比較回数が減った!

【基礎課題6-1】(p.100) データ数がn個の時の、最大比較回数(データが見つからなかった場合の比較回数)は?  線形探索法では、(2n+1)回  番兵法では    回?  n+2 (n+1)+1 流れ図の確認→【基礎課題6-2】(ループ端記号の場合) 【基礎課題6-3】(A[0]~A[n-1]の場合) 線形探索の(練習)プログラム→【基礎課題6-4】(p.103)

2分探索法 6-2 2分探索 線形探索では、データ数に比例して(データ照合のための)比較回数が増大。 データ数が10倍→計算時間も10倍 6-2 2分探索 線形探索では、データ数に比例して(データ照合のための)比較回数が増大。 データ数が10倍→計算時間も10倍   → 大きなデータ数では、効率が悪い! もっと効率の良い方法は? 2分探索法

例:数字「30」の書かれたカードを探す。 ※最初に昇順にソートしておく。 A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] 1 3 7 12 13 14 20 22 30 41 ① 「30」と真ん中のA[5]を比較 ③ 「30」とA[9]を比較  ② 「30」と真ん中のA[8]を比較 1 3 7 12 13 14 20 30 41 22 1 3 7 12 13 14 20 30 41 22 1 3 7 12 13 14 20 22 30 41 1 3 7 12 13 14 20 22 30 41 13 22 「30」がA[9]にあることを発見!→ 終了! 探索範囲がA[9]~A[10]に絞られる。 探索範囲がA[6]~A[10]に絞られる。 データ数が2倍になっても比較回数は1回増えるだけ! 流れ図の確認→p.107 → 【基礎課題6-5】で確認 プログラムは【基礎課題6-6】で作成

6-3 アルゴリズムの効率 p.110をよく読んで下さい。 2分探索法は線形探索法(番兵法)より効率が良い。 6-3 アルゴリズムの効率  2分探索法は線形探索法(番兵法)より効率が良い。  p.110をよく読んで下さい。 【基礎課題6-5】をきちんとやっておくことが必要。

6-4 応用課題 線形探索の応用→【応用課題6-A】 2分探索の応用→【応用課題6-B】 6-4 応用課題 線形探索の応用→【応用課題6-A】 2分探索の応用→【応用課題6-B】 【応用課題6-B】のプログラムを作成する事ができれば、本章の理解度はOKです。

今後の予定 6/17 第7章 再帰処理 6/24 第8章 連結リスト 7/ 1 第9章 木構造 7/ 8 第10章 スタックとキュー 6/17 第7章 再帰処理 6/24 第8章 連結リスト 7/ 1 第9章 木構造 7/ 8 第10章 スタックとキュー 7/15 第2回テスト & 課題チェック 7/22 課題最終チェック(力試しの課題を含む)

学習に当たって これまでの基礎課題を全て終了した学生は【応用課題6-A】および【応用課題6-B】のチェックを終了すれば演習を終えても結構です。