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

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

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

2014年9月25日 金岡 晃

この授業について

• 講義科目名称

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

• 英文科目名称

– Algorithms and Data Structures

– Seminar in Algorithms and Data Structures

• 開講期間

– 秋学期

• 配当年

– 2学年

• 単位数

– 2

• 科目必選区分

– 必修

• 担当教員

– 金岡 晃

• 開講日時

– 木曜日3限 – 木曜日4限

授業概要

• 授業の目的と学習概要

– プログラムを作る上で必ず学ばなければならない基礎の一つで あるデータ構造とアルゴリズムを学ぶ。プログラミングの基礎 となる、基本的な種々のデータ構造とそれらに関連する基本的 なアルゴリズムを理解すること、また演習により理解を促進す ることを目的とする。

• 授業概要

– 各種のデータ構造とそれらに関連する基本的なアルゴリズムを 学ぶ。データ構造とアルゴリズムは、プログラムを作る上で必 ず学ばなければならない基礎の一つであり、少しでも本格的な 良いプログラムを作ろうと思えば、データ構造とアルゴリズム に関する知識が欠かせない。このようなプログラミングの基礎 となる、基本的な種々のデータ構造とそれらに関連する基本的 なアルゴリズムを解説、演習する。

2013/9/26 アルゴリズムとデータ構造

2

授業計画

第1週 (9/25)

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

第2週 (10/2)

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

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

(10/9)

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

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

(10/16)

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

＋＜演習＞

第5週 (10/23)

休講 第6週

(10/30)

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

決定木 第7週

(11/13)

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

二分木、決定木 第8週 中間試験

第9週 (11/27)

休講 第10週

(12/4)

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

＜演習＞

第11週 (12/11)

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

第12週 (12/18)

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

第13週 (1/8)

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

木構造探索法 第14週

(1/15)

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

1/21-2/6 期末試験

教科書と参考書

• 教科書

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

（斎藤信男・西原精一共著、コロナ社）

• 参考書

– 「データ構造」（星守、昭晃堂）

– 「アルゴリズムとデータ構造」（平田富 夫、森北出版）

2013/9/26 アルゴリズムとデータ構造

4

評価方法とオフィスアワー

• 評価方法

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

• 中間試験 50点

• 期末試験 50点

• 合計60点以上を合格とする – アルゴリズムとデータ構造演習

• 演習課題 60点

• 中間試験 20点

• 定期試験 20点

• 合計60点以上を合格とする

• オフィスアワー

– オフィスアワーについてはメールで個別に時間を予約するもの とする

• 連絡先：[email protected]

授業用

サイト

• http://www.klab.is.sci.toho-u.ac.jp/classes/

•

金岡が受け持っている講義の資料（この講 義以外も）をアップロードしています

•

「アルゴリズムとデータ構造」のページも 作成しました

•

講義資料を

化してすべて載せていきま す。

2013/9/26 アルゴリズムとデータ構造

6

講義の進め方

講義 講義

演習（実習室）

演習（実習室）

座学（III号館204） 座学（III号館204）

実習（たぶんIII号館1F） 実習（たぶんIII号館1F）

第

週

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

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

8 2013/9/26 アルゴリズムとデータ構造

本日の到達目標と概要

• 到達目標

– アルゴリズムの意味とデータ構造の必要性を理解する

• 概要

– アルゴリズムの意味を知る：「素数判定」

– データ構造の意味を知る：「積木の塔」

アルゴリズムとは

2013/9/26 アルゴリズムとデータ構造

10

アルゴリズム アルゴリズム

• 問題を解くための手順を定式化した形で表現したもの

• 問題の解を得るための具体的な手順

アルゴリズムと プログラムの関係

アルゴリズムと プログラムの関係

コンピュータにアルゴリズムを指示するための文書をプログラムと言う

より厳密に言うと「アルゴリズムを指示するための人間が可 読可能な文書をソースプログラムと言う」

アルゴリズムの優劣

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

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

素数判定を例にとる

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

入力： 自然数 𝑛

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

シンプルなやり方

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

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

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

素数判定：高速化を狙う

2013/9/26 アルゴリズムとデータ構造

12

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

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

シンプルなやり方

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

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

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

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

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

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

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

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

素数判定：さらなる高速化

改良手法1

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

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

「改良手法1」の計算量

「改良手法1」の計算量

𝑛 = 101の場合、2,3,5, ⋯ , 99で割り切れるかどうか確認 50回確認

99 → 50と ほぼ半減

まだ無駄がある

「𝑛 = 101の場合、2,3,5,7,9, ⋯ , 99で割り切れるかどうか確認」

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

たとえば たとえば

𝑛 = 101の場合、11以上の数で割り切れるかどうか確認するのは無駄。

素数判定：これで最速になるか？

2013/9/26 アルゴリズムとデータ構造

14

改良手法2

入力された 𝑛 が2 で割り切れるか確認。

割り切れない場合、3, 5, 7, 11,13, ⋯ , 𝑥 と素数を小さい順から並べ、それぞれの 素数で割り切れるかどうか確認する。

ただし、𝑥は 𝑥 < 𝑛 を満たす最大の素数

𝑛 = 101の場合、2,3,5,7,9で割り切れるかどうか確認

4回確認 ^{99 → 4と}

「シンプルなやり方」の計算量の4.0%に

「シンプルなやり方」と比較すると劇的に高速

「シンプルなやり方」と比較すると劇的に高速

ある程度の素数をあらかじめ記憶（ストック）しておかなければなら ない（＝データ量が必要になる）

ある程度の素数をあらかじめ記憶（ストック）しておかなければなら ない（＝データ量が必要になる）

素数判定の手法

さまざまな手法がある エラトステネスの篩（ふるい）

APR素数判定法 AKS素数判定法 フェルマーテスト

ミラー-ラビン素数判定法

・・

・

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

これらはすべて

「アルゴリズム」

演習（その１）

2013/9/26 アルゴリズムとデータ構造

16

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

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

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

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

手法A

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

確認する数：最大𝑛回

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

演習（その１）

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

積木の塔（教科書参照）

2013/9/26 アルゴリズムとデータ構造

18

A D

B C

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

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

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

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

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

状況 状況

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

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

まずやってみよう

A D

B C A

D

C B

A D C B

A D C B

A D B C

A D C B

D C B A

表現を変えてみよう

2013/9/26 アルゴリズムとデータ構造

20

積木𝑥をつかんて𝑦の上に移動する操作：𝑚𝑜𝑣𝑒 𝑥, 𝑦 積木𝑥をテーブルの空いた場所に移す操作：𝑟𝑒𝑚𝑜𝑣𝑒 𝑥

DA

B C DA

CB

A D CB

A D CB

A DB C

A DCB

DCBA

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

モデルで表現してみよう

コンピュータの中に積木やアーム、テーブルを用意する わけにはいかない。

擬似的にそれと同等の意味を持つモデルを用意する。

0 0 0 0 1

0 0 0 0 1

0 0 0 0 1

1 0 0 0 0

行列を用いたモデル化

A B C D T A

B C D

𝑥行𝑦列の要素 𝑥, 𝑦 は「𝑥が𝑦の上に接して 載っているかどうか」の真偽を示す。 1な らば載っている。 0ならば載っていない。

この場合、AからDに加え、「机」そのもの を示す T が入った。

机と積木の状態を他の表現で表したもの＝モデル化 机と積木の状態を他の表現で表したもの＝モデル化

モデルにも優劣がでる

2013/9/26 アルゴリズムとデータ構造

22

「行列を用いたモデル化」の問題点

「行列を用いたモデル化」の問題点

• 無駄な情報が多い（データ量が多い）

• 全部の組み合わせではなく「 𝑥が何の上に接して載っているかどうか」

だけの情報で良い 矢印を用いたモデル化

x→y： 「xはyの上に載っている」を示す

初期状態は

A→T, B→T, C→T, D→A で表すことができる ベクトルを用いたモデル化

(x¹, x², x³, x⁴)：

Aはx¹の上、Bはx²の上、Cはx³の上、Dはx⁴の上に載っていることを示す 初期状態は (T, T, T, A) で表すことができる

制約条件：解くべき問題に制約が存在する

モデルに明示されていない性質がある モデルに明示されていない性質がある

積木の塔を解くにあたっての制約

1つの積木のすぐ上にはたかだか1つの積木しか載せられない テーブルに接して載せることができる積木はたかだか3つ どの積木も自分自身の上には載せられない

どの積木もテーブルまたは積木の上に載っている

どの積木も同時に2つ以上のテーブルまたは積木の上には載せられない 2つ以上の積木を一斉に移動することはできない

上に何も載っていない積木だけ移動できる

上に何も載っていないテーブルまたは積木の上にのみ移動できる

A D

B C

人間は無意識に 制約を考慮して 利用している 人間は無意識に 制約を考慮して 利用している コンピュータに は制約を明示し ないといけない コンピュータに は制約を明示し ないといけない

積木の塔を解く

2013/9/26 アルゴリズムとデータ構造

24

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

(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ステップステップ

本日の到達目標と概要

• 到達目標

– アルゴリズムの意味とデータ構造の必要性を理解する

• 概要

– アルゴリズムの意味を知る：「素数判定」

– データ構造の意味を知る：「積木の塔」