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

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

第2週 アルゴリズムの効率、線形構造

2014年10月2日 金岡 晃

授業計画

1

第1週 (9/25)

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

第2週 (10/2)

アルゴリズムの効率、線型構造、

スタックと待ち行列 第3週

(10/9)

＜演習＞アルゴリズムの効率、

線型構造、スタックと待ち行列 第4週

(10/16)

文字列照合（KMP法、BM法）

＋＜演習＞

第5週 (10/23)

休講 第6週

(10/30)

木の構造、木の走査、二分木、

決定木 第7週

(11/13)

＜演習＞木の構造、木の走査、

二分木、決定木 第8週

(11/20)

中間試験

第9週 (11/27)

休講 第10週

(12/4)

グラフ構造と最短路問題＋

＜演習＞

第11週 (12/11)

データ整列：ヒープソート 法、クイックソート法

第12週 (12/18)

＜演習＞データ整列：ヒー プソート法、クイックソー ト法

第13週 (1/8)

データ探索：ハッシュ法、

木構造探索法 第14週

(1/15)

＜演習＞データ探索：ハッ シュ法、木構造探索法

1/21-2/6 期末試験

2014/10/2 アルゴリズムとデータ構造

【復習】第 1 週

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

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

2 2014/10/2 アルゴリズムとデータ構造

アルゴリズムの優劣

2014/10/2 アルゴリズムとデータ構造

3

アルゴリズム＝問題の解を得るための具体的な手順 アルゴリズム＝問題の解を得るための具体的な手順

解の導出方法の効率はそれぞれの方法により異なる 効率の尺度例：計算量（スピード）、メモリ量

素数判定を例にとる

目的： 入力された値が素数であるか 否かを判定する

入力： 自然数 𝑛

出力： 0 （素数でない） または 1（素数である）

シンプルなやり方

入力された 𝑛 が2 ⋯ 𝑛 − 1までの それぞれの数で割り切れるか どうか確認する

このやり方は 効率がよいか？

このやり方は 効率がよいか？

素数判定：高速化を狙う

2014/10/2 アルゴリズムとデータ構造

4

「シンプルなやり方」の無駄な点

「シンプルなやり方」の無駄な点

シンプルなやり方

入力された 𝑛 が2 ⋯ 𝑛 − 1までのそれぞれの数で割り切れるかどうか確認する

𝑛 = 101の場合、2 ⋯ 100までの数字で割り切れるかどうか確認 99回確認

もしnが4で割り切れたとするとその数値はすでに 2 で割り切れる。

2で割り切れなくて4で割り切れる整数はない。

「4で割り切れるかどうか確認」は無駄。

同様に6, 8, 10, … , 98つまり2で割り切れる数（偶数）で確認するのは無駄 改良手法1

入力された 𝑛 が2 で割り切れるか確認。割り切れない場合、

3, 5, 7, ⋯ , (𝑛の直前の奇数） までのそれぞれの数で割り切れるかどうか確認する

演習（その１）

2014/10/2 アルゴリズムとデータ構造

5

平方数を判定する 平方数を判定する

※平方数：ある整数の2乗で表される整数 （例：1, 4, 9, 16, 25)

目的： 入力された値が平方数であるか否かを判定する 入力： 自然数 𝑛

出力： 0 （平方数でない） または 1（平方数である）

手法A

1,2, … , 𝑛 を順に2乗し、𝑛と等しいか確認する。 確認する数：最大𝑛回

• 手法Aよりも高速（確認する数が少ない）アルゴリズムを考えてみよう

• 用紙に記載する内容

– 自分で考えた高速化アルゴリズム

– そのアルゴリズムを用いて𝑛 = 101 が平方数であるか否かを調べた場合、何 回の確認が必要になるかを計算

積木の塔（教科書参照）

2014/10/2 アルゴリズムとデータ構造

6

A D

B C

アーム • テーブルに4つの積木

• それぞれの積木にはAからDまで 名前が書かれている。

• 積木は同じサイズの立方体

• テーブル面は積木3個分の広さだけ

• アームにより1度に1つの積木を掴ん で移動可能

状況 状況

テーブルの上に1本の 積木の塔を作りたい テーブルの上に1本の 積木の塔を作りたい やりたいこと

ただし、上からA、B、C、Dの順 になるように

積木の塔を解く

2014/10/2 アルゴリズムとデータ構造

7

初期の状態 初期の状態 目的の状態 目的の状態

(T, T, T, A)

(B, C, D, T)

(T, T, T, A) (T, C, T, A) (T, C, T, T) (T, A, T, T) (T, A, D, T) (T, C, D, T) (B, C, D, T)

𝑚𝑜𝑣𝑒 𝐵, 𝐶 𝑟𝑒𝑚𝑜𝑣𝑒 𝐷 𝑚𝑜𝑣𝑒 𝐵, 𝐴 𝑚𝑜𝑣𝑒 𝐶, 𝐷 𝑚𝑜𝑣𝑒 𝐵, 𝐶

𝑚𝑜𝑣𝑒(𝐴, 𝐵)

スライド19 の場合 スライド19

の場合

より少ない 移動数 より少ない

移動数 (T, T, T, A) (T, T, B, A) (T, T, B, T) (T, T, D, T) (T, C, D, T) (B, C, D, T)

𝑚𝑜𝑣𝑒 𝐶, 𝐵 𝑟𝑒𝑚𝑜𝑣𝑒 𝐷 𝑚𝑜𝑣𝑒 𝐶, 𝐷 𝑚𝑜𝑣𝑒 𝐵, 𝐶 𝑚𝑜𝑣𝑒 𝐴, 𝐵 やり方（アルゴリズム）はこれらだ けではない。

より少ない移動数で目的の状態まで 遷移できるアルゴリズムがより高速 なアルゴリズム、と言える。

6ステップ

6ステップ 55ステップステップ

第 2 週

アルゴリズムの効率、線形構造

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

8 2014/10/2 アルゴリズムとデータ構造

本日の到達目標と概要

• 到達目標

– アルゴリズムの効率の考え方を理解する – データ構造の 1 つである線形構造を理解する

• 概要

– 計算量とオーダ記法

– データ構造の基礎となるレコードと関係 – 全順序関係

9 2014/10/2 アルゴリズムとデータ構造

アルゴリズムの効率

2014/10/2 アルゴリズムとデータ構造

10

3の倍数か判定をする

目的： 入力された値が3の倍数であるか否かを判定する 入力： 自然数 𝑛

出力： 0 （3の倍数でない） または 1（3の倍数である）

𝑚𝑜𝑑の利用

𝑛 𝑚𝑜𝑑 3を計算し、0になるかどうかを判定

3ずつ引いていく

𝑛 = 𝑛 − 3を繰り返し計算し、1または2になったら0を出

力、0になったら1を出力 各桁の数を足し合わせる

𝑛の各桁の数字を上位から取り出し、足して3での余りを調べる。すべての数字の 処理が終わった結果が0だったら1を出力、それ以外（1または2）だったら0を出力

アルゴリズムの効率

2014/10/2 アルゴリズムとデータ構造

11

𝑚𝑜𝑑の利用

𝑛 𝑚𝑜𝑑 3を計算し、0になるかどうかを判定

3ずつ引いていく

𝑛 = 𝑛 − 3を繰り返し計算し、1または2になったら0を出

力、0になったら1を出力 各桁の数を足し合わせる

𝑛の各桁の数字を上位から取り出し、足して3での余りを調べる。すべての数字の 処理が終わった結果が0だったら1を出力、それ以外（1または2）だったら0を出力

• 「𝑚𝑜𝑑の計算」と「減算」と「数字を取り出し、足して3での余りを調べ る」の3つの作業はすべて同じ時間で実行できる

前提 前提

作業の回数を見る 作業の回数を見る

1回 1回

𝑛/3 回 𝑛/3 回

log₁₀ 𝑛 回 log₁₀ 𝑛 回

アルゴリズムの効率

2014/10/2 アルゴリズムとデータ構造

12

𝑚𝑜𝑑の利用

3ずつ引いていく

各桁の数を足し合わせる 作業の回数を見る 作業の回数を見る

1回 1回

𝑛/3 回 𝑛/3 回

log₁₀𝑛回 log₁₀𝑛回

𝑂 1

𝑂 𝑛

𝑂 log 𝑛

𝑛の数に関係なく決まる。定数。

𝑛に比例して決まる。

log 𝑛に比例して決まる。

※対数の底が記載されていないが問題ない。対数であることが重要

アルゴリズムの時間効率

2014/10/2 アルゴリズムとデータ構造

13

それぞれ違うユーザから全く同じ プログラムが作られることはない

問題 𝑃 を解くプログラム 問題 𝑃 を解くプログラム プログラムの時間効率

同じアルゴリズムであればプログ ラムの実行時間に大きな差はない

アルゴリズムによってプログラムの効率が決まる

オーダ記法

2014/10/2 アルゴリズムとデータ構造

14

計算時間の近似的な目安 計算時間の近似的な目安

𝑂 𝑓 𝑛 と表現されたときの時間計算量

𝑂 𝑓 𝑛 と表現されたときの時間計算量

𝑂 𝑓 𝑛

𝑛 が十分大きいところでは 𝑓 𝑛 に比例した処理時間にな る。つまり 𝑓 𝑛 の定数倍の時間として十分精度良く近似 できる。

1. 𝑚𝑜𝑑の利用

2. 3ずつ引いていく

3. 各桁の数を足し合わせる

𝑂 1 𝑂 𝑛

𝑂 log 𝑛

𝑂 1 < 𝑂 log 𝑛 < 𝑂 𝑛

なので1→3→2の順に効率が良い

アルゴリズムの時間効率の考え方

2014/10/2 アルゴリズムとデータ構造

15

問題 𝑃 を解くプログラム 問題 𝑃 を解くプログラム

やり方（アルゴリズム）はいろいろ アルゴリズムの オーダで比較 アルゴリズムの

オーダで比較 オーダが一緒でもプログラム自身の効率はプログラムで変わる 例）𝑛回のなんらかの作業をするプログラム

・プログラムAは 100 × 𝑛回の掛け算

・プログラムBは 1000 × 𝑛回の掛け算

オーダは一緒だが Aのほうが高速

オーダがまずプログラムの効率を決め

その係数がプログラムの最終的な効率を決める

多項式オーダの計算量

2014/10/2 アルゴリズムとデータ構造

16

多項式オーダ

𝑂 𝑛

多項式オーダ

𝑂 𝑛

サイズ𝑛の問題を処理するのに解く時間が

𝐶

𝑛

+ 𝐶

𝑛

+ 𝐶

𝑛

+ ⋯ + 𝐶

𝑛

+ 𝐶

で与えられるような計算の複雑さ。

「多項式時間の計算量」と呼ぶことも。

𝑂 𝑛 、 𝑂 𝑛 ² の例

2014/10/2 アルゴリズムとデータ構造

17

𝑂 𝑛

𝑂 𝑛

𝑂 𝑛

𝑂 𝑛

九九の𝑛バージョンの、 𝑛の段の表を作る

九九の𝑛バージョンの、一覧表を作る

様々なオーダ

2014/10/2 アルゴリズムとデータ構造

18

𝑂 1 𝑂 𝑛 𝑂 𝑛

𝑂 log 𝑛 𝑂 𝑘

𝑂 𝑛!

任意の実数 𝑎 > 0 , 𝑏 > 1 について

が成り立つ。

𝑂 log 𝑛 < 𝑂 𝑛

< 𝑂 𝑏

< 𝑂 𝑛!

𝑂 𝑛 log 𝑛

レコード

2014/10/2 アルゴリズムとデータ構造

19

• データ構造の基本

• 一般に複数のフィールド（Field、欄ともいう）からなる。

• 各フィールドに名前を付け、格納できるデータの型も前もって指定 してある

例 例

レコードの定義： 氏名

（文字列）

年齢

（非負整数）

識別子

（非負整数）

各レコード： 山田太郎 54 99990001

佐藤次郎 20 99990002

鈴木一朗 39 99990003

関係

2014/10/2 アルゴリズムとデータ構造

20

レコードの集合があって、レコード間に何らかの関係をつくると、

データ構造になる

順序関係

順序関係 • アルファベット順

• 出席番号順

• 背の順

• 成績順

全順序関係

全順序関係

全順序関係の定義

2014/10/2 アルゴリズムとデータ構造

21

全順序関係 全順序関係

集合𝑆の任意の要素 𝑥, 𝑦, 𝑧 について、要素間の関係 𝑅 に関して次の 4つの性質が成り立つものを、集合𝑆上の全順序関係と言う。

１．反射律： 𝑥𝑅𝑥

２．推移律： 𝑥𝑅𝑦 ∧ 𝑦𝑅𝑧 ⇒ 𝑥𝑅𝑧 ３．反対称律： 𝑥𝑅𝑦 ∧ 𝑦𝑅𝑥 ⇒ 𝑥 = 𝑦 ４． 𝑥𝑅𝑦 ∨ 𝑦𝑅𝑥

∨：または

∧：かつ

⇒：ならば

例 例

• 数値の大小関係（ ≤ ）

• 辞書式順序（アルファベット順、アイウエオ順）

半順序関係

2014/10/2 アルゴリズムとデータ構造

22

全順序関係の4つの性質のうち、反射律・推移律・反対称律の3つだけ を満たすもの

例 例

• 集合の包含関係（ ⊆ ）

𝑆 = 𝜙, 1 , 2 , 3 , 1,2 , 1,3 , 2,3 , 1,2,3 の場合 1,2 ⊆ 1,3

1,3 ⊆ 1,2

False

False 4. が成り立たない

データの論理構造

2014/10/2 アルゴリズムとデータ構造

23

• レコード𝑎, 𝑏, 𝑐, 𝑑を含むファイル𝑆

• 全順序構造がある 𝑎 ≤ 𝑏

𝑎 ≤ 𝑐 𝑎 ≤ 𝑑

𝑏 ≤ 𝑐 𝑏 ≤ 𝑑 𝑐 ≤ 𝑑

本質的には𝑎 ≤ 𝑏 ≤ 𝑐 ≤ 𝑑

データの論理構造 データの論理構造

𝑎 𝑏 𝑐 𝑑

レコード

関係

グラフになっている グラフになっている

データの物理構造

2014/10/2 アルゴリズムとデータ構造

24

𝑎 𝑏 𝑐 𝑑

上記の論理構造を物理的にコンピュータに格納する必要性がある 順配置

順配置

1 a 2 b 3 c 4 d

リンク配置 リンク配置

a b c d

論理構造から物理構造を構成することはプログラミングの重要な仕事 論理構造から物理構造を構成することはプログラミングの重要な仕事

線形構造

2014/10/2 アルゴリズムとデータ構造

25

全順序関係を表すデータ構造

𝑎 𝑏 𝑐 𝑑

線形構造の論理表現：線形リスト

本日の到達目標と概要

• 到達目標

– アルゴリズムの効率の考え方を理解する – データ構造の 1 つである線形構造を理解する

• 概要

– 計算量とオーダ記法

– データ構造の基礎となるレコードと関係 – 全順序関係

26 2014/10/2 アルゴリズムとデータ構造

例題：全順序関係

• 数値をフィールドに持つデータ構造を作り、数値の大小関係（ ≤ ） を用いた 3 つのレコードを用意し、全順序関係を持つ集合 𝑆 を作って ください。

• またその集合が全順序関係を持つことを証明してください。

• 答案に書くもの

– 2-1 ：データ構造 – 2-2 ：集合 𝑆

– 2-3 ：集合 𝑆 が全順序関係を持つことの照明

2014/10/2 アルゴリズムとデータ構造

27

例題の回答例

2014/10/2 アルゴリズムとデータ構造

28

2-1 ^{氏名（文字列） 年齢（非負整数） 識別子（非負整数）}

山田太郎 54 99990001

佐藤次郎 20 99990002

鈴木一朗 39 99990003

2-2

2-3 • 年齢で順序関係を構築

• 各レコードを「山田」「佐藤」「鈴木」で示す

１． 山田≦山田、佐藤≦佐藤、鈴木≦鈴木 いずれも真 ２． 佐藤≦鈴木 ∧ 鈴木≦山田 ⇒ 佐藤≦山田 真

３． 山田≦山田 ∧ 山田≦山田 ⇒ 山田＝山田 佐藤≦佐藤 ∧ 佐藤≦佐藤 ⇒ 佐藤＝佐藤

鈴木≦鈴木 ∧ 鈴木≦鈴木 ⇒ 鈴木＝鈴木 いずれも真 ４． 山田≦佐藤 ∨ 佐藤≦山田

山田≦鈴木 ∨ 鈴木≦山田

佐藤≦鈴木 ∨ 鈴木≦佐藤 いずれも真

1~4のすべてを満たすので、全順序関係である

演習

2014/10/2 アルゴリズムとデータ構造

29

演習（その１）

2014/10/2 アルゴリズムとデータ構造

30

平方数を判定する 平方数を判定する

※平方数：ある整数の2乗で表される整数 （例：1, 4, 9, 16, 25)

目的： 入力された値が平方数であるか否かを判定する 入力： 自然数 𝑛

出力： 0 （平方数でない） または 1（平方数である）

手法A

1,2, … , 𝑛 を順に2乗し、𝑛と等しいか確認する。 確認する数：最大𝑛回

制約： 利用できる算術演算は加算（＋）、減算（－）、積（×）のみ

演習：手法Aよりも高速（確認する数が少ない）アルゴリズムを考え、実装して みよう

演習（その 2 ）

2014/10/2 アルゴリズムとデータ構造

31

積木の塔を解く 積木の塔を解く

演習：積木の塔を解くアルゴリズムを考え、実装してみよう 入力：初期状態。（T,T,T,A）のようなベクトル。

※ベクトルの入力方法は任意

出力：目的の状態（B,C,D,T）に至るまでの状態と動作（moveとremove）

の内容の列挙

注：現段階では実現は難しいかもしれないので、

できなかった場合は、どういう考えでやろうとし て（アルゴリズムのイメージ）、どう失敗したか を示せるように

注：現段階では実現は難しいかもしれないので、

できなかった場合は、どういう考えでやろうとし て（アルゴリズムのイメージ）、どう失敗したか を示せるように

演習（その 2 ）：実行イメージ

2014/10/2 アルゴリズムとデータ構造

32

> java Tower T T T A (T, T, T, A)

move (B, C) (T, C, T, A)

remove (D) (T, C, T, T)

move(B,A) (T, A, T, T)

move(C,D) (T, A, D, T)

move(B,C) (T, C, D, T)

move(A,B) (B, C, D, T)

> java Tower T T T A (T, T, T, A)

move (B, C) (T, C, T, A)

remove (D) (T, C, T, T)

move(B,A) (T, A, T, T)

move(C,D) (T, A, D, T)

move(B,C) (T, C, D, T)

move(A,B) (B, C, D, T)

演習（その 3 ）

• 計算量が 𝑂 𝑛 、 𝑂 𝑛

の例をそれぞれ 1 つずつ考え、実装 してみる

– 例：「九九の表を作る」

– 「＊＊という状況で＊＊＊という問題を解く」というまず状況 設定と解かれるべき問題をプログラムのソースコードにコメン ト文として書くこと

– 同じく、コメント文に問題の解き方を書き、それがなぜその オーダになるかを示すこと

2014/10/2 アルゴリズムとデータ構造

33

計算量を考える 計算量を考える

締切と提出方法

• 締切

– 来週（10月9日）の16:10まで

※来週のこの講義＋演習時間が終わるまで

• 提出方法

– 電子メール

• メールアドレス

– [email protected]

– メールのタイトルに「アルゴリズムとデータ構造第1回課題」と書 いてください

– 作ったプログラム（計3つ）をメールに添付してください。

• 注意事項

– 必ず金岡から受領確認メールを返します。

• 必ず日本語で受領確認メールを返します

• 英語のメールはエラーメール（アドレスが間違っている）の可 能性が高いです

– メールで提出がされていないものは未提出とみなします

2014/10/2 アルゴリズムとデータ構造

34