アルゴリズムとデータ
構造
第１回ガイダンス
2015/10/14
2015年度アルゴリズムとデータ構造
1
なぜ「アルゴリズムとデータ構造」を学ぶのか？
効率的なプログラムを作成できるようになるため
効率的とは
計算時間が短い
メモリ使用量が少ない
メリット
アルゴリズムは全てのプログラム言語で役に立つ
情報理工学専攻大学院入試に出題される科目
IT関連に就職する人は常識とされる
2015/10/14
2015年度アルゴリズムとデータ構造
2
アルゴリズムとは
機械的に実行可能な手続き
（例）自然数a0, a1(a0≧a1)の最大公約数を求める単純なアルゴリズム
「nがa0とa1を共に割り切るかを、n=a1から始めて１つずつ小さな値nに
対してチェックし、初めて割り切る値nを出力」
2015/10/14
2015年度アルゴリズムとデータ構造
3
アルゴリズムの表現
1.
自然言語の文章による表現
[日本語の文章による表現] nがa0とa1を共に割り切るかを、n=a1から始
めて１つずつ小さな値nに対してチェックし、初めて割り切る値nを出力
長： 特別に知識を必要としない、読みやすい，
短： 厳密に書くのが難しい、制御構造を表現しづらい
2.
開
始
n←a1
プログラミング言語による表現
[C言語による表現]
n=a1;
for(;n>0;n--) if(a0%n=0 && a1%n=0) return n;
N
長： 厳密に書ける、制御構造を表現しやすい，
短： 読みにくい、記述言語の知識が必要
3.
フローチャートによる表現(右図) 長： 制御構造を理解し易い
短： 読みにくい
2015/10/14
2015年度アルゴリズムとデータ構造
a0とa1が
共にnで割
り切れる
Y
nを出力
終
了
4
アルゴリズムの擬似コードによる表現
1.
擬似コードによる表現
n←a1
loop
if a0とa1が共にnで割り切れる then
return n
end if
n←n − 1
end loop
無限に繰り返す
nの値を返してこの
手続きから抜ける
長： 読みやすい、制御構造を表現しやすい，
短： 制御構造記述の知識が少し必要
2015/10/14
2015年度アルゴリズムとデータ構造
5
ユークリッドの互除法の擬似コード
a←a0, b←a1
loop
r←aをbで割った余り
if r=0 then
return b
end if
a←b, b←r
end loop
2015/10/14
2015年度アルゴリズムとデータ構造
6
どっちのアルゴリズムの方が効率的？
自然数a0, a1(a0≧a1)の最大公約数を求めるアルゴリズム
単純なアルゴリズム
と
ユークリッドの互除法
ではどちらの方が効率的なアルゴリズムなのか？
どのような計算モデルを用いて、どのように評価するのかを
はっきりさせる必要がある。
2015/10/14
2015年度アルゴリズムとデータ構造
7
計算モデル
（決定性）チューリング機械(Turing Machine)
1936年に発表した論文でAlan Turingが提案したモ
デルであり、計算量の理論でベースとなっているモデル
テープヘッド
制御部
Alan Turing
1912-1954 英国
Σ: 文字集合（有限個のシンボル）
K: 有限個の状態
•１本のテープ、テープヘッド、制御部からなる。
•テープヘッドの位置するマス目には、そこに書かれている（Σに属する）文字を読み
込んだり、異なる文字に書き換えることが可能。
•制御部には現在の（Kに属する）状態が記憶されている。
•現在のテープヘッドが位置するマス目の文字、制御部の状態で次の動作が決まる。
•１回の動作は次の３つからなる。
１．テープヘッドが位置するマス目の文字を書き換える
２．テープヘッドを左右に１マス以下動かす
３．制御部の状態を新しい状態に書き換える
2015/10/14
2015年度アルゴリズムとデータ構造
8
決定性チューリング機械の厳密な定義
チューリング機械とは４つ組M=(K,Σ,δ,s)のこと。
K：有限状態集合
s∈K：初期状態
Σ：アルファベット（有限シンボル集合）
入力の終わりは
K∩Σ=φで、`␣’（空白）と`▷’（先頭）の２つの
`␣’で検知可能
特殊シンボルを含む。入力には`␣’は使えない。
δ：K×Σ → （K∪{h,``yes’’,``no’’})×Σ×{←,→,－}, 遷移関数
h: halting state (停止状態)
yes: accepting state (受理状態）
no: rejecting state (拒否状態）
←: 左にテープヘッドを移動
→:右にテープヘッドを移動
－: テープヘッドを動かさない
ただし δ(q, ▷)=(p, ▷,→)：先頭シンボルに位置づいている場合は
書き換えないでヘッドを右に移動。
2015/10/14
2015年度アルゴリズムとデータ構造
9
決定性チューリング機械による具体的な計算例
0と1からなる文字列の先頭に空白を入れるチューリング機械
M=(K,Σ,δ,s), K={s,q,q0,q1}, Σ={0,1, ␣,▷}
δ(s,0)=(s,0,→)
δ(s,1)=(s,1,→)
δ(s, ␣)=(q, ␣,←)
δ(s, ▷)=(s, ▷,→)
δ(q,0)=(q0, ␣,→)
δ(q,1)=(q1, ␣,→)
δ(q, ␣)=(q, ␣,－)
δ(q, ▷)=(h, ▷ ,→)
δ(q0,0)=(s,0,←)
δ(q0,1)=(s,0,←)
δ(q0, ␣)=(s,0,←)
δ(q0, ▷)=(h, ␣,→)
δ(q1,0)=(s,1,←)
δ(q1,1)=(s,1,←)
δ(q1, ␣)=(s,1,←)
δ(q1, ▷)=(h, ␣,→)
2015/10/14
▷010
▷010
s
▷010
s
▷010␣
▷01␣0
s
▷010␣
s
▷0␣␣0
q0
▷␣010
s
2015年度アルゴリズムとデータ構造
▷01␣0
q0
▷0␣10
q1
▷␣␣10
s
▷01␣␣
q
q
▷010
s
▷␣010
q
s
▷0␣10
q
▷␣010
h
10
計算可能とは？
Σ*はΣに属する文字からなる任意の長さの文字列
def
Σ*上の関数fが計算可能 ⇔
すべてのx∈Σ*に対し
Mにxを与えて実行するとf(x)を出力して停止する
ようなチューリング機械Mが存在すること
上の定義において「チューリング機械」をもっと強力な「チューリング機械の変形」
に換えても計算可能な関数は変わらない！
複数テープチューリング機械（テープが複数）
δ：K×Σk → （K∪{h,``yes’’,``no’’})×Σk×{←,→,－}k
非決定性チューリング機械（入力に対し計算が一意に定まらない）
δ：K×Σ →
2（K∪{h,``yes’’,``no’’})×Σ×{←,→,－}
2XはXの部分集合の集合（Xの部分集合族）
2015/10/14
2015年度アルゴリズムとデータ構造
11
Church（Church-Turing)の提唱(1936)
アルゴリズムをもつ関数（計算できる関数）という直感的な概念を
チューリング機械で計算可能な関数クラスと同一視しよう。
Alonzo Church,
1903-1995, 米国
関数fが帰納的 ⇔ 関数fがλ定義可能 ⇔ 関数fがチューリング機械で計算可能
Gödel
Church
Turing
Church, Kleeneにより証明
Turingにより証明
よって「チューリング機械」を「帰納的関数」または「λ定義可能な関数」と言い換えても同じ
アルゴリズムをもつ関数（計算できる関数）という直感的な概念を
帰納的関数(λ定義可能な関数)と呼ばれる関数クラスと同一視しよう。
2015/10/14
2015年度アルゴリズムとデータ構造
12
万能チューリング機械
• チューリング機械は１つの関数の値しか計算できない専用機。
様々な関数の値が計算できる汎用機はあるのか？→YES
• どんなチューリング機械Mでも文字列pで表現可能
有限シンボルを扱い，有限状態をもつので、遷移関数への入力は
有限個しかない
万能チューリング機械＝
任意のチューリング機械Mに対し，それを表す文字列pと
任意の文字列xの組(p,x)をテープに与えて実行すると，Mにxを
与えて実行したのと同じ結果が得られるチューリング機械
2015/10/14
2015年度アルゴリズムとデータ構造
13
計算不可能な関数なんてあるの？
停止性判定問題
任意のチューリング機械Mの文字列表現pと任意の文字列xの組(p,x)に対し、
チューリング機械Mにxを与えて実行したときに、その実行が停止するかしないか
を判定する問題
停止性判定問題を解くアルゴリズムが存在するかということは
次のような関数haltが計算可能かということ
halt(p,x)= 1 if プログラムpが入力xに対して停止するとき
0 otherwise
関数haltは計算不可能！
2015/10/14
2015年度アルゴリズムとデータ構造
14
関数haltが計算不可能であることの証明
haltが計算可能であると仮定して矛盾を導く。
haltが計算可能であれば、左下のようなチューリング機械Mが存在する。
チューリング機械M
if(halt(u,u)=1) {
while(true){ u←u;}
} else {
return(0);
}
Mにその文字列表現pを与えて実行した場合を考える。
このとき、「停止する」と仮定すると
Mに(u=)pを与えて実行すると停止する
⇒halt(p,p)=1
⇒Mにpを与えて実行すると無限ループにおちいる
(停止するという仮定に矛盾)
逆に「停止しない」と仮定すると
Mに(u=p)を与えて実行すると停止しない
⇒halt(p,p)=0
⇒Mにpを与えて実行すると停止する。
（停止しないという仮定に矛盾）
したがってhaltが計算可能であるという仮定が誤りである。
2015/10/14
2015年度アルゴリズムとデータ構造
15
ランダムアクセス機械
RAM (Random Access Machine)
ランダムアクセス記憶を持つ逐次実行型の計算モデル
入力テープ
テープヘッド
累算器 (四則演算・ジャンプ命令など可能)
制御カウンタ
プログラム
記憶
レジスタ
出力テープ
テープヘッド
記憶レジスタには以下のことを仮定
任意の大きさの整数を格納できる
無限個存在
任意のレジスタに１ステップでアクセス可能
計算能力はチューリング機械と同等
2015/10/14
2015年度アルゴリズムとデータ構造
16
チューリング賞って知ってる？
チューリング賞は、現代計算機の産みの親であるアラン・チューリングの功績を称え
て、 1966年に米コンピューター学会(ACM) が設定した賞である。 （副賞２５万ドル）
最近１2年の受賞者
2003
Alan Kay
オブジェクト指向プログラミング言語の開発
2004
Vinton G. Cerf、 Robert E. Kahn
2005
Peter Naur
2006
Frances E Allen (女性初） コンパイラー最適化技術の開発
TCP/IPプロトコルの開発
Algol 60の開発
2007 Edmund M. Clarke，
E. Allen Emerson，Joseph Sifakis
LSIの回路設計検証などに貢献
2008 Barbara Liskov(女性)
データ抽象化機能をサポートしたプログラム言語CLU、分散プログラムをサポートしたArgusの開発
2009 Charles P. Thacker
現代のパーソナルコンピュータの原型であるAltoに関する先駆的な設計とその実現、イーサネットとタ
ブレットPCへの貢献
2010 Leslie G. Valiant
計算論的学習理論に関する研究と、コンピュータ科学のより幅広い理論への貢献
2011
Judea Pearl
確率的および因果的推論の算法を発展させることで、人工知能に基礎的貢献をした
2012
Silvio Micali, Shafi Goldwasser
2013
Leslie Lamport
分散／並列システムの理論と実践への貢献
2014
Michael Stonebraker
データベースシステム分野の基礎構築に貢献
2015/10/14
暗号理論、計算複雑性理論への貢献、ゼロ知識証明の発明
2015年度アルゴリズムとデータ構造
17
じゃ、ゲーデル賞は？
理論計算機科学分野で優れた功績を残した人に、ACM（アメリカ計
算機学会）のアルゴリズムと計算量理論に関する部会とEATCS
（ヨーロッパ理論コンピュータ学会）が贈る賞である。受賞者には賞
金5,000ドルが贈られる。論理学者クルト・ゲーデルに由来する。計
算機科学分野ではチューリング賞と並んで権威を持つ賞である。
過去１2年の受賞者
Kurt Gödel,
2004 Maurice Herlihy, Michael Saks, Nir Shavit and Fotios Zaharoglou:
1906-1978,
applications of topology to the theory of distributed computing
2005 Noga Alon, Yossi Matias and Mario Szegedy:
オーストリア
their foundational contribution to streaming algorithms
2006 Manindra Agrawal, Neeraj Kayal, Nitin Saxena: the AKS primality test
2007 Alexander Razborov, Steven Rudich: natural proofs
2008 Daniel Spielman, Shanghua Teng: smoothed analysis of algorithms
2009 Omer Reingold, Salil Vadhan, Avi Wigderson:
zig-zag product of graphs and undirected connectivity in log space
2010 Sanjeev Arora, Joseph S. B. Mitchell: their concurrent discovery of a polynomial-time approximation scheme (PTAS)
for the Euclidean Travelling Salesman Problem (ETSP)
2011 Johan Håstad:
proving optimal inapproximability result for various combinatorial problems
2012 Elias Koutsoupias, Christos Papadimitriou, Noam Nisan, Amir Ronen, Tim Roughgarden and Éva Tardos:
laying the foundations of algorithmic game theory
2013 Dan Boneh, Matthew K. Franklin, and Antoine Joux:
for multi-party Diffie–Hellman key exchange and the Boneh–Franklin scheme in cryptography
2014 Ronald Fagin, Amnon Lotem, and Moni Naor: for Optimal Aggregation Algorithms for Middleware
2015 Daniel Spielman, Shanghua Teng or their series of papers on nearly-linear-time Laplacian solvers
日本人では戸田誠之助先生が「多項式階層と複雑性クラス#Pの関係」に関する研究で1998年に受賞
2015/10/14
2015年度アルゴリズムとデータ構造
18
更に、ネヴァンリンナ賞は？
Fields Medal(1936-)，Carl Friedrich Gauss Prize(2006-)と共
に国際数学者連盟が設ける賞で，4年に一度，情報科学に於け
る数学分野に貢献した受賞時に40歳以下の者が対象．
Rolf Nevanlinna,
副賞15,000ドル。（IMU：国際数学者連合)
1895-1980,フィンランド
Year
1982
1986
1990
1994
1998
2002
2006
2010
2014
Laureate
Nationality
Robert Tarjan
United States
Leslie Valiant
United Kingdom
Alexander Razborov
Russia
Avi Wigderson
Israel
Peter Shor
United States
Madhu Sudan
India/ United States
Jon Kleinberg
United States
Daniel Spielman United States
Subhash Khot
india/ United States
John von Neumann 賞 (1992-) 副賞4000ドル (IEEE)
コンピュータ関連の科学・技術に著しく貢献した者を顕彰するために1990年に設置された．
「理論的・技術的・事業的な成功に対して，長期的な視点で」対象者を選考．
個人またはグループで3人まで．von Neumannは現代コンピュータの発明者．
2015/10/14
2015年度アルゴリズムとデータ構造
19
© Copyright 2024 ExpyDoc
