1. アルゴリズムと計算量.

Presentation on theme: "1. アルゴリズムと計算量."— Presentation transcript:

1 1. アルゴリズムと計算量

2 授業の説明

3 コンピュータ内でデータをどのように保持するのか
「データ構造」の講義で学ぶ内容 密接な関係 データ構造の話 アルゴリズムの話 コンピュータ内でデータをどのように保持するのか データを使って どのように 処理させるのか データ 処理結果

4 処理効率の向上＝洗練されたアルゴリズム＋データ構造の正しい選択
データ構造の重要性 処理効率の向上＝洗練されたアルゴリズム＋データ構造の正しい選択 アルゴリズムの設計 データ構造を考慮 コンピュータ資源を考慮 データ構造の選択 アルゴリズムを考慮 コンピュータ資源を考慮 データ 処理結果

5 他の科目との関連

6 アルゴリズムの話

7 手続きとは？ 問題を解く手順が書かれている 基本的な演算・操作 記述は有限の長さ Jfkdsoaiejfl;ldsfdsajklaf
kljklfjdajfkldldsfdsajklaf fkdjkfdsafjkdssfdsajklaf 基本的な演算・操作 Jfkdstioewpkmvm,ajklaf Jfkdsamekocigjkf;ajkdsf Jewojfdkvm,ladkfgiuako ldsfiewjfnmdaljcidoagjkf 記述は有限の長さ

8 アルゴリズムとは？ 手続き どんな入力でも 必ず停止する 定義域 値域

9 アルゴリズムの例（ユークリッドの互助法）
　m、nは自然数 　(1) r ← （n を m で割った余り）, (2)に移る。 　(2) r = 0 ならば m が最大公約数と答え，計算を停止する。 　　 r ≠ 0 ならば n ← m, m ← r, (1)に移る。 ３４ １４ ０ ６ ２ n m r

10 何故、「n を m で割った余り」を考えるのか？
ユークリッドの互助法（イメージの構築） n＝［長い方］ m ＝［短い方］ n を m で割った余り 何故、「 n ← m, m ← r 」の代入を行うのか？ 何故、「n を m で割った余り」を考えるのか？ 今まで短かった方が今度は長い方に 今まで余りだった方が今度は短い方に

11 ユークリッドの互助法（具体例） ３４ ６ ６ １４ ２ １４ ３４ １４ ６ ２ ０ n m r

12 停止しない手続きの例（問題設定） 最大公約数問題を市松模様問題として解釈 市松模様問題 → 入力：長方形（縦と横の長さ）
　　　→　入力：長方形（縦と横の長さ） 　　　→　出力：出来るだけ大きい正方形で市松模様を 　　　　　　　　　つけたときの、その正方形のサイズ ［長い方］を「短い方］で割った［余り］ 　　　　＝［長］－ ｛［短］×切捨て（［長］/［短］）｝

13 停止しない手続きの例（手続き） 市松模様問題を解く手続き 計算誤差は無いものとする（現実的な仮定ではない）
　(1) r ← （［長い方］を［短い方］で割った［余り］）, (2)に移る。 　(2) r = 0 ならば ［短い方］ が正方形のサイズと答え，計算を停止する。 　　 r <> 0 ならば ［長い方］ ← ［短い方］, ［短い方］ ← ［余り］, (1)に移る。 計算誤差は無いものとする（現実的な仮定ではない）

14 停止しない手続きの例（定義域） 横 市松模様を解く手続き 縦：横 縦 縦横比が 実数 値域 縦横比が 有理数

15 自分で考えてみよう 縦横比が有理数だと必ず停止することを証明してみよう 停止しないような縦横比を見つけてみよう

16 ロシア乗算法（ハードに適した方法） ÷２ ×２ 端数を保存 ４５ → １０１１０１ ２２ → １０１１０１ ２で割る ４５ × １９ ２２
３８ １９ × ＋ １９ → １００１１ ３８ → １００１１０ ２を掛ける １１ ７６ × ５ １５２ ７６ × ＋ ２ ３０４ １５２ × ＋ １０進数で１０倍 →右に０を追加 ２進数で２倍 １ ６０８ × ＝ 合計 ８５５

17 効率の良し悪しの尺度 プログラムの評価 運転技術の評価 最速F1ドライバーとは？ 高速プログラムとは？ 最新型マシーンと旧型マシーン
短距離と長距離 優勝回数と平均順位 プログラムの評価 高速プログラムとは？ 最新型コンピュータと旧型コンピュータ 大規模データと小規模データ 最悪計算量と平均計算量

18 計算量（物差と量り方） テストコースで車を５０回走らせた 何を量るか（物差） どう評価するか（量り方） 何を量るか（物差）
速度を量る 燃費を量る どう評価するか（量り方） 最悪のタイムで評価 平均で評価 何を量るか（物差） 計算時間を量る 　 →　時間計算量 使用メモリを量る →　空間計算量 どう評価するか（量り方） 最悪の場合で評価 →　最悪計算量 平均で評価　 →　平均計算量

19 漸近的計算量 良いアルゴリズムはどっち？

20 時間計算量の例 A B “何倍か？“はアルゴリズムに依存する A 10 B A 100 B A 1000 B 何倍？ 何倍？ 10×10の
10倍 10倍 何倍？ 何倍？ 10×10の 計算時間 100×100 の計算時間 1000×1000 の計算時間

21 時間計算量の例 c ：Pの１回の（最悪）処理時間 Pはn３回行われる 　⇒　計算時間は（最悪） c n３ 　　　（計算時間はn３に比例） ←無視 P

22 何を気にしているのか？ 例：（行列の積の計算時間）と（正方形の体積） ⇒ 体積は辺の長さの３乗に比例 ⇒ 計算時間はデータサイズの３乗に比例
（体積の増え方）と（辺の長さの増え方）の関係は？ 　　　⇒　体積は辺の長さの３乗に比例 　　　　　　（辺が２倍になれば体積は２３＝８倍になる） （データサイズ）と（計算時間）の関係は？ 　　　⇒　計算時間はデータサイズの３乗に比例 　　　　　　O(n3)と表記する

23 計算量のオーダ t(n)はO(f(n))

24 計算量のオーダ t(n)はΩ(f(n))

25 計算量のオーダ