問題解決力を鍛える！アルゴリズムとデータ構造 ミートアップ#1

[Eigo-Mt-Fuji]

やりたいこと

• 問題解決力を鍛える！アルゴリズムとデータ構造 - Kindle を読みたい

  • 大槻兼資. 問題解決力を鍛える！アルゴリズムとデータ構造 Kindle 版.

• 読んだ結果１つでもいいから得るもの得て整理したい

進め方

• 本書のねらいを確認
• ポイントを3つ選んで学習
• まとめると

本書のねらいを確認

• アルゴリズムとは「問題を解くための方法，手順」
• 単にアルゴリズムの動作を説明するだけでなく，「どうしたらよいアルゴリズムを設計できるか」という視点

3点集中

今回は、アルゴリズム計算量, アルゴリズム設計技法 全探索(線形探索), アルゴリズム設計技法 動的計画法の3つ。

• アルゴリズム

  • 計算量

  • 時間計算量

    • 「計算量」といえば「時間計算量」
    • 計算時間が「データのサイズの増加にともなってどのように増加していくか」という視点が「時間計算量」
    • 計算時間を大まかに測る「ものさし」の役割が「時間計算量」
      • 実行に要する時間を，実際にアルゴリズムを実装することなく、あらかじめ大雑把に見積もる
    • 平均的には高速だが最悪時には遅いアルゴリズムも存在する。「最悪時間計算量」と「平均時間計算量」の区別が存在
      • 入力データの偏りによっては計算が速く終了するパターンの場合「最悪時間計算量」と「平均時間計算量」にそれぞれ違いが出る
    • 「時間計算量」の他に「領域計算量」というが概念も存在する。
      • 「アルゴリズム実行時のメモリ使用量を表す領域計算量（spacecomplexity）
    • 通常「計算量」といえば「時間計算量」の「最悪時間計算量」を指す

  • オーダー記法

    • アルゴリズムの計算時間を議論するときには，計算量を「オーダー記法」で表す
    • 計算量をオーダー記法で表す過程で定数倍や低次の項の影響を受けないようにすることは重要
      • コンピュータ環境やコンパイラの違いによる計算時間の微妙な違いによる影響を避けたいため、計算量をオーダー記法で表す過程で定数倍や低次の項の影響を受けないようにする。
    • ２つの「オーダー記法」を理解しておく。
    • ランダウのO(ビッグオー)記法
      • アルゴリズムの計算量を表す記法が「O(ビッグオー)記法」
      • アルゴリズムAの計算時間「T(N)」が「おおむねP(N)に比例する」ことを「T(N)＝O(P(N))」 と表す。「O(P(N))」がアルゴリズムAの計算量にあたる。
      • 具体例で考えると、T(N)＝3N^2＋5N＋100の場合、T(N)＝O(N^2)と表す
        • 最高次以外の項を無視して，さらに最高次の係数も無視する
        • 計算量をオーダー記法で表す過程で定数倍や低次の項の影響を受けないようにすることは重要
    • Θ(シータ)記法
      • 漸近的にタイトな限界 = Θ(ビッグシータ)記法
      • タイトな=ぴったりと密着していること, 漸近的に=数値が徐々に近づいていくさま, 限界=上限や下限と同じ。Aのどの要素より大きいもののなかの最小の値のことを上限という。
        • Θ(ビッグシータ)記法 Θ(f(n))と書いた場合
          • 記法の関数f(n)に徐々に近づいて
          • ぴったりと密着
          • 関数f(n)の計算結果が上下ともに限界という意味になる
      • 計算量をΩ(ビッグオメガ)記法で表記することは、上界と下界が一致するという意味を表す
        • 集合のどの要素よりも大きな(小さな)実数(または 集合のどの要素よりも大きな(小さな)実数の集合)を上界(下界)という。実数mがAの上界(下界)であるとは「すべての x ∈ A に対して，x<= m(x ≥ m) が成り立つ。この時の実数m を 1 つの A. の上界(下界)という」
          • 集合とは
            • 思考の対象となる個々の「もの」を一つにまとめたものを集合という
            • 集合を構成する個々の「もの」を集合の元 (げん) また は要素という
              • 最大元 A＝{1, 2, 3}であれば3が最大元。A＝{x | 1≦x＜3} だと最大元が存在しない扱いになる
              • 最小元 A＝{1, 2, 3}であれば1が最小元。A＝{x | 1<x<=3} だと最小元が存在しない扱いになる(上界全体の集合の最小元を上限という
              • 上限 Aのどの要素より大きいもののなかの最小の値のこと。A＝{x | 1≦x＜3} だと上限は3になる
              • 下限 Aのどの要素より小さいもののなかの最大の値のこと。A＝{x | 1<x<=3} だと下限は1になる
      • ちなみに漸近的●●シリーズ
        • 漸近的上界 = O(ビッグオー)記法
        • 漸近的下界 = Ω(ビッグオメガ)記法

  • 設計技法

  • 全探索

    • 世の中における多くの問題は，考えられる場合をすべて調べ上げることによって原理的には解決できます(=全探索)
    • アルゴリズムを設計するとき，まずは「どうしたらすべての場合を考慮しつくせるか」を検討することは有効
    • 全探索アルゴリズムを考案することによって，解きたい問題の構造に対する深い理解を獲得できることがある
    • 結果的に高速なアルゴリズムの設計へと結び付くことがある
    • 全探索は処理時間が長時間化する恐れがあるとはいえ、データ量Nによっては短い時間で処理を終えることもできる
    • 部分和問題に対する全探索アルゴリズムの場合、ありうる場合の数が2N通りある
    • これは、O(N2N)という指数時間の計算量
    • しかし、N20程度であれば１秒以内に処理を終えることができる

  • 全探索(線形探索法)

  • 再帰

  • 動的計画法

  • 再帰(メモ化)

  • ２分探索法

  • 貪欲法

• データ構造
  • 配列
  • 連結リスト
  • ハッシュテーブル
  • スタック
  • キュー
  • グラフ・木構造
  • グラフ・木構造(２分木)
  • グラフ・木構造(２分木 ヒープ)
  • グラフ・木構造(２分木 ２分探索木)
  • Union Find(根付き木構造)
• ソート
  • 挿入ソート
  • マージソート
  • クイックソート
  • ヒープソート
• グラフ探索
  • 幅優先
  • 深さ優先
  • トボロジカルソート
  • 木上の動的計画法
  • s-tパス
  • 二部グラフ判定
• グラフ探索(最短路問題)
  • DAG上の最短路問題
  • 単一始点最短路問題 ベルマンフォード
  • 単一始点最短路問題 ダイクストラ
  • 全点対間最短路問題 フロイド・ワーシャル
• グラフ探索(最小全域木)
  • クラスカル法
• グラフ探索(ネットワークフロー)
  • 連結度
  • 最大流問題
  • 最小カット問題
  • フォード・ファルカーソン法
  • 二部マッチング
  • 点連結度
  • プロジェクト選択問題
• PとNP
  • P = クラスP = クラスPとは、多項式時間以内で解くことができるアルゴリズムが存在するような問題のこと
  • NP = クラスNP = クラスNPは多項式時間以内で、問題の解が本当に合っているかの検証を判定することができる問題のこと
  • 多項式時間とは? 計算理論において多項式で表される計算時間
  • 対義語は指数時間
  • 数学上の未解決問題
  • NP困難
  • NP完全

まとめると

• アルゴリズムの計算量を表す記法が「O(ビッグオー)記法」 アルゴリズムAの計算時間「T(N)」が「おおむねP(N)に比例する」ことを「T(N)＝O(P(N))」 と表す。「O(P(N))」がアルゴリズムAの計算量にあたる。具体例で考えると、T(N)＝3N^2＋5N＋100の場合、T(N)＝O(N^2)と表す。最高次以外の項を無視して，さらに最高次の係数も無視する。計算量をオーダー記法で表す過程で定数倍や低次の項の影響を受けないようにすることは重要

• 全探索(線形探索) = データベースの中から特定のデータを探索する問題はありふれたものですし，日常生活においても，英単語を辞書で調べる行為などが該当大槻兼資. 問題解決力を鍛える！アルゴリズムとデータ構造 (Japanese Edition) (p.68). Kindle 版.

• 動的計画法 = 動的計画法(Dynamic Programming) = 与えられた問題全体を一連の部分問題に上手に分解し，各部分問題に対する解をメモ化しながら，小さな部分問題からより大きな部分問題へと順に解を求めていく手法

備考

• ビット左シフト ( << )
  • 1 << i は 1を iビット左にシフト
  • つまり
  • 1 << 1 は 1を 1ビット左にシフト = 2
  • 1 << 3 は 1を 3ビット左にシフト = 8
  • 1 << 10 は 1を 10ビット左にシフト = 1024
• ビット論理積 (&)
  • a & b は a と bの論理積を計算する
  • 論理積とは、互いの数値を２進数換算し、互いにの２進数ビット(桁)ごとの積(1 or 0)を計算すること
    • 双方のビットが1の場合のみ1、それ以外は0
  • つまり
  • 1 & 0 = 0
    • 0001 & 0000
  • 2 & 1 = 0
    • 0010 & 0001
  • 2 & 2 = 1
    • 0010 & 0010
  • 5 & 2 = 0
    • 0101 & 0010
  • 6 & 2 = 2
    • 0110 & 0010
  • 14 & 6 = 6
    • 1110 & 0110
  • 6 & 14 = 6
    • 0110 & 1110

// 0〜2^Nまで全探査
for(int target = 0; taget < (1 << N); target++) {
    // target 
    int sum = 0;
    for(i = 0; i < N; i++) {
        // ビット論理積
        if (target & (1 << i)) {
            sum += a[i];
        }
    }
}

[Eigo-Mt-Fuji]

いい学習だった。明日もがんばる