アルゴリズムのキホン

アルゴリズムのキホン

アルゴリズム全然知らないので、勉強してみる。

「アルゴリズム」のキホン (イチバンやさしい理工系シリーズ)

第1章 アルゴリズムとは

• 問題解決のための処理手順
• 「正当性」と「停止性」が必要
• 技術計算
  • ユークリッド互除法
  • ガウスの消去法
  • 台形法
  • ダイクストラ法
  • エラトステネスのふるい
• ソート
  • 単純選択法
  • 単純交換法（バブルソート）
  • 単純挿入法
  • シェルソート
  • マージソート
  • クイックソート
• サーチ
  • 線形探索（リニアサーチ）
  • 二分探索（バイナリサーチ）
• 文字列パターン照合
  • 単純文字列照合
  • KMP法
  • BM法
• 構造化プログラミング
  • 逐次構造
  • 選択構造
  • 反復構造

第2章 変数と配列

• 配列
  • 添え字
  • 「BASE 0」と「BASE 1」

第3章 データ構造

• スタック
  • PUSH, POP
  • LIFO (Last In, First Out)
  • FILO (First In, Last Out)
• キュー
  • 待ち行列
  • FIFO (First In, First Out)
  • LILO (Last In, Last Out)
• 単方向リスト
  • データ
  • 次の要素を指し示すポインタ
• 双方向リスト
  • データ
  • 次の要素を指し示すポインタ
  • 前の要素を指し示すポインタ
• N 番目の要素の参照が早いのは配列、遅いのはリスト
• データの挿入・削除が早いのはリスト構造で、遅いのは配列
• 末尾までいったら先頭に戻ってくるのがリングバッファ
  • 携帯の履歴など
• 親一人、子二人の構造を二分木
• 親ノードの値が常に子ノードの値より大きくならない二分木がヒープ
• 節点（ノード）と辺（エッジ）により項目のつながりを図的に表現したのがグラフ
  • 辺に方向性という属性を持たせたグラフを「有向グラフ」
  • 辺に方向性のないものを「無向グラフ」