Document

アルゴリズムイントロダクション輪講
D3照山順一
全体連絡
• 輪講について：
アルゴリズムイントロダクションを読んでいきます。
• 発表：担当箇所をパワーポイントで説明
• 時間・場所：毎週月曜１３時～、２研
• 分担など：研究室の輪講のページを参照
やろうとしている範囲
1章：序論
2章：オーダーの話
3章：和の計算
4章：漸化式
5章：集合など
6章：確率など
7章：ヒープソート
8章：クイックソート
9章：線形時間ソート
10章：中央値、順序統計量
16章：動的計画法
17章：貪欲アルゴリズム
18章：ならし解析
23章：初等グラフアルゴリズム
24章：最小全域木
25章：単一始点最短路
26章：全点対間最短路
27章：最大フロー
36章：NP完全問題
37章：近似アルゴリズム
1章：序論
• アルゴリズムとは何か？
• アルゴリズムの良さ、解析
• ソーティング
– 挿入ソート
– マージソート
– 他のアルゴリズムは７章以降で
1章：序論
• アルゴリズムとは？
– 問題を解くための道具
入力
手続き
出力
1章：序論
• 問題：ソーティング
• 入力：列
• 出力：非減少列
列
{5,2,4,6,1,3}
手続き
非減少列
{1,2,3,4,5,6}
具体例、インスタンス
• アルゴリズムが問題を解く：
⇒すべてのインスタンスに対して正しく出力し停止する。
1章：序論：挿入ソート
• 挿入ソート
: 正しくソートされている
524613
524613
254613
245613
1章：序論：挿入ソート
• 挿入ソート
: 正しくソートされている
524613
524613
254613
245613
245613
124563
123456
1章：序論：疑似コード
• 本教科書の注意点：
アルゴリズムは言葉での説明もあるが、厳密
な形としては疑似コードで与えられていく
1章：序論：疑似コード
１：字下げ
２：ループ、条件分岐
３：コメント
４：代入
５：変数
６：配列
1章：序論：疑似コード
１：字下げ
２：ループ、条件分岐
３：コメント
４：代入
５：変数
６：配列
1章：序論：疑似コード
１：字下げ
２：ループ、条件分岐
３：コメント
４：代入
５：変数
６：配列
1章：序論：疑似コード
１：字下げ
２：ループ、条件分岐
３：コメント
４：代入
５：変数
６：配列
1章：序論：疑似コード
１：字下げ
２：ループ、条件分岐
３：コメント
４：代入
５：変数
６：配列
：i と j 両方に e を代入
1章：序論：疑似コード
１：字下げ
２：ループ、条件分岐
３：コメント
４：代入
５：変数
６：配列
1章：序論：疑似コード
１：字下げ
２：ループ、条件分岐
３：コメント
４：代入
５：変数
６：配列
1章：序論：疑似コード
１：字下げ
２：ループ、条件分岐
３：コメント
４：代入
５：変数
６：配列
5 1
21 42 5
4 6
6 3
245613
1章：序論：解析
• アルゴリズムの解析：アルゴリズムの良さ
計算時間：入力サイズの関数
コスト繰返回数
ti :今の位置と挿入する位置との差
1章：序論：解析
最良時間
最悪時間
：アルゴリズムの評価として採用
係数、低次項を無視
増加率を気にする！
1章：序論：分割統治法
• よりよいアルゴリズムを設計したい：
分割統治法：部分問題を再帰的に解く
分割：部分問題に分割
統治：部分問題を再帰的に解く
結合：部分問題の解から元の問題を解く
マージソート：
分割：列を半分に分割
統治：それぞれ再帰的に解く
結合：ソートされた２つの列から１つのソート列を生成
1章：序論：分割統治法
マージソート：
分割：列を半分に分割
統治：それぞれ再帰的に解く
結合：ソートされた２つの列から１つのソート列を生成
1234
2348
1579
第Ⅰ部：数学的基礎
•
•
•
•
２章：オーダーの話
３章：和の計算
４章：漸化式⇒オーダー計算への近道
５章：集合など
今日はここまで終わらせる予定
• ６章：確率など
• 大事なところをかいつまんでいきます。
• 分からなければ質問してください。
2章：オーダー
• 計算時間の漸近的な挙動：
十分に大きなデータ入力を考える
2章：オーダー
• 計算時間の漸近的な挙動：
十分に大きなデータ入力を考える
2章：オーダー
• 計算時間の漸近的な挙動：
十分に大きなデータ入力を考える
2章：オーダー
2章：オーダー
•
も
満たさない２つの関数：
も
2章：よく使う関数
• よく使う記号と関数
– 単調性
– 切り上げ (ceiling) :
– 切り捨て (flooring) :
– 多項式 :
– 指数関数
– 対数関数
2章：よく使う関数
• よく使う記号と関数
– 階乗 n! :スターリングの公式
– 反復対数関数
となる最小のi
3章：和の計算
• while, for の評価で使う
Σの式の評価：
算術級数：
幾何級数：
調和数：
3章：和の計算
• 和の評価の方法：数学的帰納法
• 上界、下界の評価もできる。
＊帰納法とオーダーを混ぜると間違いやすい[板書]
3章：和の計算：評価のテクニック
• 項の上界の利用
– 最大の項
– 幾何級数
– 和の分割
定数
– 積分近似
評価しやすい
3章：和の計算：評価のテクニック
– 和の分割
– 積分近似
4章：漸化式
• 今日の一番の山場：いったん休憩？
• 漸化式からオーダーを求める：
• 置き換え法、反復法、分類法
4章：置き換え法
• 推測⇒帰納法
– うまくいけば強力だが、推測しやすいものにしか適用できない
境界条件は？
定数a, a+1 で成り立てば
n>aで漸化式が成り立つ。
例）T(2) , T(3) で考える。
ならどの値でもよい
4章：置き換え法
• 微妙な例：
• 推測：
• 代入してみると、
• 対処法：低次項を引く
なら成り立つ！！
4章：置き換え法
• 帰納法とオーダー記法：混ぜると間違えやすい！
• 誤った証明：
4章：反復法
• 漸化式を繰り返し展開して、和の形から評価する。
境界条件までのステップ数
各段階でのコストの和
4章：反復法
• 再帰木(recursion tree):再帰計算の視覚化
4章：分類法
• 便利な道具：
4章：分類法
オーダーに影響がないくらい小さい
オーダーを支配するくらい大きい
だいたい同じ
4章：分類定理の証明
１）n が b のべき乗のときを証明
２）任意のnでも成り立つ
4章：分類定理の証明
• n が b のべき乗のときを証明
(１)以下の式が成り立つ(反復法、再帰木)
4章：分類定理の証明
(2)
の評価：
のオーダーの中身
4章：分類定理の証明
(2)
の評価：
のオーダーの中身
4章：分類定理の証明
(2)
の評価：
実は導ける
4章：分類定理の証明
• 一般のnのとき(概略のみ)：
天井関数と床関数によるオーダーへの影響は？
• 上界の証明方針：反復法：
べき乗の時とほとんど同じ関係式
5章：集合
•
•
•
•
離散数学における基本的なもの
集合、関係、関数、グラフ、木・・・
簡単に説明・・・
23章～27章：グラフアルゴリズムなので分か
らない用語が出てきたらここに戻るように。
5章：集合
• 集合：要素の集まり
• 空集合：
• 部分集合：
• 真部分集合：
• 積集合、和集合、差集合：
• 補集合：
• ド・モルガンの法則：
5章：集合
• 分割：
•
•
•
•
•
サイズ(要素数、基数)：
加算無限：自然数と1対1対応
非加算無限：自然数と1対1対応しない
べき集合：
直積：
5章：集合
• 包除原理(inclusion-exclusion)(問題5.1-3)
5章：関係
• 2項関係：直積の部分集合
• 反射的(reflexive)：
• 対称的(symmetric)：
• 推移的(transitive)：
• ３つの性質を持つ関係を同値関係という。
5章：関係：同値関係
• 同値関係の例：
偶奇が同じ
Nで割ったあまりが同じ：mod N
• 集合を同値関係毎に分割してみる
同値類：
同値類の性質：
1：同値類は分割をなす
2：任意の分割は同値関係を表す
5章：関係：同値関係
1：同値類は分割をなす
Ⅰ：
反射性・推移性から、
よって、
Ⅱ：同値類の和集合はA
反射的なので、
5章：関係：同値関係
2：任意の分割は同値関係を表す
A上の分割：
次のような関係を考え、同値関係であることを示す：
反射性：aRa は自明
対称性：aRb : a, bは同じ集合の要素 ⇒ bRa
推移性： aRb かつ bRc ⇒ aRc
5章：関係：他の用語
• 反対称的： aRb かつ bRa の時、a=b
例）
• 反順序関係：反射的かつ反対称的
• 反順序集合：反順序関係が定義された集合
• 全順序：すべてのペアに対して反順序関係が成立
5章：関数
• 関数：
Aの要素すべてに対して、Bの要素が唯一に対応
• 単射、全射、全単射：
• 置換：
• 逆関数：
なる全単射
5章：グラフ
• 有向グラフ：
V：頂点集合
E：辺集合
1
2
3
4
5章：グラフ
• 無向グラフ：
V：頂点集合
E：辺集合
1
2
3
4
5章：グラフ
• 有向グラフと無向グラフで用語が少し変わる
頂点の次数
有向グラフ
無向グラフ
uからvに接続
uから出る、vに入る
uとv上に接続
uとvは隣接
出次数、入次数
次数＝出次数+入次数
隣接頂点の数
• 経路、閉路：
• 連結：全頂点間に経路がある (有向：強連結)
• 同型：グラフが等価になる頂点間の全単射が存在
5章：グラフ
• 部分グラフ：
• 誘導グラフ：
• 完全グラフ：全頂点間に辺がある
• ２部グラフ：頂点集合をV1とV2に分割した時、
辺がV1-V2間のみである
• 森：閉路がない無向グラフ
• 木：閉路がなく連結な無向グラフ
• ダグ(DAG)：閉路がない有向グラフ
5章：木
木：閉路のない連結な無向グラフ
＊以下の命題はすべて等価である
1：Gは木
2：任意の2頂点は唯一の単純経路で連結
3：Gは連結で、どの辺を除いても非連結となる
4：Gは連結で、|E| = |V|-1
5：Gは閉路を持たず、|E| = |V|-1
6： Gは閉路を持たず、一つでも辺を増やせば、閉路ができる
5章：木
1：Gは木
2：任意の2頂点は唯一の単純経路で連結
3：Gは連結で、どの辺を除いても非連結となる
4：Gは連結で、|E| = |V|-1
5：Gは閉路を持たず、|E| = |V|-1
6： Gは閉路を持たず、一つでも辺を増やせば、閉路ができる
(1)→(2)：経路が2つあると閉路があり矛盾
(2)→(3)：ほぼ自明
(3)→(4)：帰納法
5章：木
1：Gは木
2：任意の2頂点は唯一の単純経路で連結
3：Gは連結で、どの辺を除いても非連結となる
4：Gは連結で、|E| = |V|-1
5：Gは閉路を持たず、|E| = |V|-1
6： Gは閉路を持たず、一つでも辺を増やせば、閉路ができる
(4)→(5)：閉路を持つと連結でなくなる
(5)→(6)：閉路がない⇒森、森かつ辺の数→(1)、(1)→(2)
(6)→(1)：Gは連結
5章：いろいろな木
•
•
•
•
根付き木：先祖・子孫、親・子の関係
順序木： k番目の子かも区別
２分木 (k分木) ：子が高々２つ(k個)
位置木：何番目の子かラベルが付いている
根（root）
深さ（depth）

Download Report