Document

アルゴリズムとデータ構造
2008年度前期
情報工学科
渕田孝康
概要
• アルゴリズム+データ構造=プログラム
– なぜアルゴリズムが必要か?
– なぜデータ構造までが必要か?
– 計算量とは?
• 基本的なデータ構造
– 配列、リスト
– スタック、キュー、ヒープ
– 木構造(2分木、平衡木)
• さまざまなアルゴリズム
– 探索問題
– 並べ替え(ソート)問題
– 文字列処理
Pascal言語の設計者
N. Wirth の言葉
プログラム開発
• 解きたい(解くべき)問題が与えられる
• 開発過程
– 分析:何を解くのか?
– 設計:どのように解くのか?
– 実装:プログラムコードで表現
– テスト:正しく動くか?
• 完成
– 保守など
多項式計算アルゴリズム
• 多項式 f(x) の x=x0 の値を計算する
f ( x)  an x n  an 1 x n 1    a1 x  a0
• 式の通りに計算
– 第1項:n回 の乗算
– 第2項:n-1回 の乗算・・・
– 全部で (n2+3n)/2 回の乗算が必要
• ホーナーの方法(Hornaer’s rule)
– x をできるだけくくりだしながら計算する。
時間効率の良い
アルゴリズム
f ( x)  a0  (a1  ((an1  (an )  x)  x) )  x)  x
– 2n 回の計算で可能
どれくらい違うのか?
400
多項式
Horners
350
300
250
200
150
100
50
0
0
5
10
15
20
25
30
もっとスケールを大きくすると・・・
100000000
多項式
Horners
10000000
1000000
1.6年
100000
10000
1000
100
5.5時
間
10
1
1
10
100
1000
10000
アルゴリズムとデータ構造の必要性
• 簡単なアルゴリズムが「良い」アルゴリズムとは限ら
ない。
• 時間と空間のトレードオフ
–
–
–
–
速くて、メモリをあまり使わない → ◎
速いが、メモリをたくさん使う → ?
遅いが、メモリをあまり使わない → ?
遅くて、メモリをたくさん使う → ×
• 速度=アルゴリズム
• メモリ=データ構造
• どちらも重要
掛け算の例
• 遅いが小メモリ
A
• 速いが大メモリ
A
B
B
aaaabbbb
A×B
aaaabbbb
A×B
calc()
r = A0
s = B0
…
aaaabbbb
A×B
aaaabbbb
A×B
計算時に必要な一時記憶メ
モリ程度
aaaabbbb
A×B
計算
A×B
A×B
必要性
• 知的好奇心・向上心
– より「良い」アルゴリズムを求める。
– 工学的に実用上も有効
• プログラミング技術の向上のため
– やりたいことを実現するプログラムを書くには、アルゴリズムが必要
• 一方で、オブジェクト指向言語の普及
– プログラムの部品化、ブラックボックス化
– 基本部品(リスト、スタック、ソートなど)は部品として与えられ、使い
方さえ知っていれば良い?
– 部品の選択の判断のためには、内部構造を知ることが必要
• 並べ替え:バブルソート、ヒープソート、バケットソート、クイックソート・・・
第1回
チューリング機械と計算機
チューリング機械
• Turing Machine
– A.M.Turingが1936年、「On computable numbers, with
an application to the entschidungsproblem(計算可能
数についてー決定問題への応用)」で発表
– 現在の計算機の基本的な動作は、チューリング機械の原
理と同等であるといえる。
• 計算機で原理上解ける問題=チューリング機械で解ける問題
• 数学の形式体系はチューリング機械の動作に還元可能
• 計算機の不完全性の証明
– 停止問題(チューリング機械が停止するかどうかを判定するチュー
リング機械を作ることはできない)
チューリング機械の構造
• 以下の3つの構成要素
– 右側に無限に長いテープ(記憶装置)
– テープを読み書きするヘッド(入出力装置)
– 内部状態(メモリ)
• 以下の動作を停止するまで繰り返す
–
–
–
–
a
ヘッドの位置のテープを読む(#は空白)
ヘッドの位置に文字を書く
機械の内部状態Sを変える
ヘッドを移動する(左、右、そのまま)
b
#
a
c
左移動
c
#
#
S
#
H
e
l
右移動
l
o
#
#
#
1
2
3
#
チューリング機械のプログラム
• 5つの文字の組
–
–
–
–
–
現在の状態S0
テープから読んだ入力I
テープに書き込む出力O
ヘッドの移動M
次の状態S1
S0
I
O
M
S1
0
0
0
R
0
0
1
1
R
1
1
0
0
R
0
1
1
1
R
2
2
0
0
R
0
2
1
0
L
2
2
#
#
R
0
課題080411
• 次のページのチューリング機械のプログラム
の動作を説明せよ。(2進数加算)
– 適宜、行番号をつけてよい。
• 提出方法:メールで
• 提出先:[email protected]
• 期限:2008年4月17日(木)
Report080411
• Explain the behavior of the program of
turing machine on next page. (binary
addtion)
– You can use the line numbers arbitrarily.
• Submission method : by mail
• Address : [email protected]
• Deadline : 2008/4/17 (thr)
2進数加算(binary addtion)
現状態
入力
出力
移動
次状態
0
1
1
1
0
0
0
0
1
0
1
1
0
1
0
0
1
1
1
1
1
1
1
-1
2
1
2
0
1
-1
2
2
1
0
-1
4
1
3
2
3
1
1
3
3
0
1
3
4
1
1
-1
4
4
0
0
-1
4
-1
5
0
-1
5
1
1
0
1
1
0
4
5
1
5
5
0
•
•
移動は、1で右へ、-1で左へ1マスだけ移
動する。
空のマスは空白文字を意味する。
•
•
•
•
•
現状態=current state
入力=input
出力=output
移動=movement
次状態=next state
•
In movement, 1 means move 1 step
right, and -1 means move 1 step left.
Empty cell means space character.
•