「アルゴリズム図鑑」を読んだので、その要点

読書感想文です。
アルゴリズム図鑑 絵で見てわかる26のアルゴリズム | 石田 保輝, 宮崎 修一 |本 | 通販 | Amazon

感想

• 逆引きもできると嬉しい。こういうことをしたいときにどれを選ぶと良いのか。
• プログラミング言語は出てこないので、自分の好きな言語と合わせて使うのが良い。という意味ではこの本だけでは足りないかもしれない。
• プログラミング言語を学びつつ
  • 「こういう問題のときにはこのアルゴリズムが使えそう」と当たりをつけた上で
    • この本に登場してくる図を見て、こういう解法になるね、というステップで使う、のか。
• いずれにしても用語の整理には良いかも。図鑑なので頭からお尻まで読みきらなくても、思い出したときに引けばよいのかもしれない。

序章　アルゴリズムの基本

• 0-1　アルゴリズムとは？
  • 計算や作業を遂行するための手順
  • 「プログラム」はプログラミング言語で書かれたもの。アルゴリズムはその前段階。
• 0-2　計算時間の測り方
  • ステップ数
  • 1ステップとは、「計算を終了するまでに基本単位を何回実行したか」

第1章　データ構造

• 1-1　データ構造とは？
  • 例: 上から順
  • 例: 五十音順
• 1-2　リスト
  • リスト: データ構造の一つで、データを一直線に並べた構造
    • 追加や削除が簡単
    • アクセスに時間がかかる
• 1-3　配列
  • 配列: データ構造の一つで、データを1列に並べるもの
    • 今更聞けない配列とリストのデータ構造 - Qiita
    • データへのアクセスは簡単
    • 追加や削除にはコストがかかる
      • 電話帳のイメージ
• 1-4　スタック
  • データを1列に並べるが、新しく追加したデータからしかアクセスできない
    • 書類を一番上に起き、一番上から取り出すイメージ
• 1-5　キュー
  • データを1列に並べるが、追加する側と削除する側が反対。
    • 待ち行列のイメージ
• 1-6　ハッシュテーブル
  • KeyとValue のセット
  • ハッシュ関数を利用できる
• 1-7　ヒープ
  • グラフの木構造
  • プライオリティキューを実現するときに使われる
• 1-8　2分探索木
  • 各ノードにデータが格納される

第2章　ソート

• 2-1　ソートとは？
  • 数字を小さい順に並び替える
  • 入力として与えられた数字を小さい順に並べ替える
• 2-2　バブルソート
  • 右から左に向かって隣り合う2つの数字を比較して入れ替える
  • 『アルゴリズム図鑑』のアルゴリズムをPython3で実装(バブルソート編) - Qiita
• 2-3　選択ソート
  • 数列の中から最小値を検索し、左端の数値と入れ替える
  • 『アルゴリズム図鑑』のアルゴリズムをPython3で実装(選択ソート編) - Qiita
• 2-4　挿入ソート
  • 数列の左側から順番にソートする
  • 最初に取り出した数字をその左の数字と比較する
• 2-5　ヒープソート
  • データ構造のヒープを利用する
  • 『アルゴリズム図鑑』のアルゴリズムをPython3で実装(ヒープソート編) - Qiita
• 2-6　マージソート
  • 分割、マージ、ソートする
• 2-7　クイックソート
  • pivot という基準になる数を選び、それより小さい数か大きい数のそれぞれのグループに分け、それらをソートする。
  • アルゴリズムの内部にアルゴリズム自身を使う「再帰」

第3章　配列の探索

• 3-1　線形探索
  • 配列からデータを探索する
  • 前から順番にデータを調べていく
• 3-2　2分探索
  • 配列からデータを探索する
  • データがソートされている場合にのみ適用できる
  • 配列の真ん中あたりのデータと目的のデータを比較する

第4章　グラフ探索

• 4-1　グラフとは？
  • ここでは、頂点がいくつか合って、いくつかの頂点ペアが辺で結ばれているもの
  • 路線図中から経路を見つけるなど
• 4-2　幅優先探索
  • グラフを探索する
  • 頂点を探索する際、視点に近い頂点から優先的に探索していく
• 4-3　深さ優先探索
  • 頂点を探索する際、1つの道を行けるところまで進んでいき、これ以上進むことができなくなったところで引き返し、次の候補を進んでいく
• 4-4　ベルマン-フォード法
  • グラフの二点間の最短距離を求める
• 4-5　ダイクストラ法
  • 間を通る辺のコストの総和が最も小さいものを求める
  • ベルマンフォード法とダイクストラ法の概念を完全に理解する - Qiita
• 4-6　A* (エースター)
  • ダイクストラ法を更に発展させたもの

第5章　セキュリティのアルゴリズム

• 5-1　セキュリティとアルゴリズム
• 5-2　暗号の基本
• 5-3　ハッシュ関数
• 5-4　共通鍵暗号方式
• 5-5　公開鍵暗号方式
• 5-6　ハイブリッド暗号方式
• 5-7　ディフィ-ヘルマン鍵交換法
• 5-8　メッセージ認証コード
• 5-9　デジタル署名
• 5-10　デジタル証明書

第6章　クラスタリング

• 6-1　クラスタリングとは？
  • 多数のデータが与えられたときに、それを似た者同士に分類する
• 6-2　k-means法

第7章　その他のアルゴリズム

• 7-1　ユークリッドの互除法
• 7-2　素数判定法
• 7-3　ページランク
• 7-4　ハノイの塔

後半は目次引用のみ。キーワードとして知っておけば良いかなという感想。

余談・参考

しめじソートが人気なので解説してみる - プログラマのつれづれなるままに
しめじソート | たまちのブログ
▽しめじソート▽100グラムにちょうせん! - ピタゴラスイッチ - NHK

8時間を0.01秒に短縮　「アルゴリズムの素晴らしさが2分で分かる動画」が今すぐ勉強したくなる分かりやすさ（1/2 ページ） - ねとらぼ
30 分でわかる！アルゴリズムの基本 - Speaker Deck

以上です～