アルゴリズムの紹介

ここでは、プログラムなどでよく使用されるアルゴリズムについて紹介したいと思います。

元々は、自分の頭の中を整理することを目的にこのコーナーを開設してみたのですが、最近は継続させることを目的に新しいネタを探すようになってきました。まだまだ面白いテーマがいろいろと残っているので、気力の続く限りは更新していきたいと思います。
今までに紹介したテーマに関しても、新しい内容や変更したい箇所などがたくさんあるため、新規テーマと同時進行で修正作業も行なっています。


アルゴリズムのコーナーで紹介してきたサンプル・プログラムをいくつか公開しています。「ライン・ルーチン」「円弧描画」「ペイント・ルーチン」「グラフィック・パターンの処理」「多角形の塗りつぶし」を一つにまとめた GraphicLibrary と、「確率・統計」より「一般化線形モデル」までを一つにまとめた Statistics を現在は用意しています。以下のリンク先からダウンロードすることができます。

中にあるのはソース・ファイルのみで、実行形式のファイルはありません ( テスト用のプログラム等を現在準備しています )。C++ を使っていますので、コンパイルには g++ が必要です。各関数の使い方はドキュメントとしていっしょに含めてあります ( Statistics を除く ) ので、そちらをご覧ください。まだバグ等が含まれている可能性は充分あり、見直しをしたい部分も多々あります。どちらもまだ不完全な状態であり、少しずつ修正・拡張を行なっていく予定です。

◆ 更新履歴
2021-05-04文字コードを UTF-8 に統一しました。ソースの追加やいくつかのバグ・フィックスもしてあります。
アップロードできるファイル容量の制限により、Statistics はドキュメントを含めていません。
ドキュメントは doxygen で作成していますので、ソースコードと一緒に入れてある設定ファイル ( Statistics.doxy.cfg ) を使って
doxygen Statistics.doxy.cfg とコマンドを実行することでドキュメントが得られます。
2019-05-18optimization.h を共通ライブラリに追加。いくつかのバグ・フィックス。
2016-07-23共通ライブラリ部分を Statistics から分離 ( Statistics の利用には共通ライブラリが必要になります )
   Statistics ソース内では #include 以下のパスを <common/***.h> としています。
ヘッダファイルを /usr/include/common 以下に保存するか、ソース内のパスを変更することで利用できるようになります。
主成分分析・特異値分解用関数オブジェクトを追加

ということで、まずはライン・ルーチン(画面に直線を描画する)についての紹介です。

  1. 線分描画のアルゴリズム (2008/09/23)
  2. 線分のクリッピング (2008/09/23)
  3. 高速化の手法 (2008/09/23)
  4. 線分描画ルーチンの応用 - 関数オブジェクトの利用 (2008/09/23)

直線の次は円弧です(^^)

  1. 円弧描画のアルゴリズム (2008/11/30)
  2. 楕円を描く (2023/02/12)
  3. サンプル・プログラム (2008/11/30)

ペイントルーチン。いわゆる領域内の塗りつぶしです。

  1. シードフィルアルゴリズム (2008/12/28)
  2. アルゴリズムの高速化 (2008/12/28)
  3. ペイントルーチンの応用 (2014/11/16)

グラフィック・パターンの処理。パターンの単純なゲット・プットから始めて拡大・縮小などの特殊なプットルーチンを紹介します。

  1. パターンの取り込みと描画 (2009/05/24)
  2. パターンの拡大・縮小描画 (2009/05/24)
  3. パターンの回転描画 (2009/05/24)
  4. パターンの自由変形 (2009/06/28)
  5. サンプル補間 (2009/07/19)
  6. スーパーサンプリング (2009/08/30)

ソート・ルーチン。いわゆる並べ替えのアルゴリズムです。

  1. 遅いソート・ルーチン (2011/11/26)
  2. シェル・ソート (2012/01/08)
  3. ヒープ・ソート (2012/01/22)
  4. クイック・ソート (2012/02/26)

多角形の塗りつぶし。ソリッド・スキャン・コンバージョンの紹介です。

  1. ソリッド・スキャン・コンバージョン (2012/05/27)
  2. スキャン・ラインとの交点算出 (2012/09/09)
  3. その他の手法 (2012/09/09)

検索・探索ルーチン。データ列から特定のデータを探し出すアルゴリズムです。

  1. 線形探索/ハッシュ法 (2013/01/20)
  2. 二分探索/二分探索木 (2013/07/07)
  3. 文字列の検索 -1- (2013/10/14)
  4. 文字列の検索 -2- (2013/11/24)
  5. 正規表現 (2014/06/22)

圧縮ルーチン。単純なランレングス法からJPEG2000まで。

  1. ランレングス法 (2014/10/19)
  2. 減色・パレット化 (2014/12/21)
  3. ハフマン符号化 - 静的ハフマン圧縮 (2015/02/01)
  4. ハフマン符号化 - 適応型ハフマン圧縮 (2015/03/08)
  5. LZ法 (2015/05/16)
  6. JPEG法 -1- (2015/09/06)
  7. JPEG法 -2- (2015/11/10)
  8. ウェーブレット変換 -1- (2016/03/31)
  9. ウェーブレット変換 -2- (2016/04/25)
  10. 算術符号化 (2016/05/21)
  11. EBCOTMQ-Coder (2016/05/25)

暗号化アルゴリズム。様々な暗号化技術とその解読方法。

  1. 19世紀より前の暗号 (2007/03/04)
  2. 暗号機の発達 (2007/08/15)
  3. 公開鍵暗号 (2007/12/09)
  4. エルガマル暗号 (2012/08/11)

数値演算法。数値演算いろいろ。

  1. 整数の演算 (2016/07/31)
  2. 多倍長整数の演算 (2016/07/31)
  3. 乗算処理の高速化 (2016/07/31)
  4. 高速フーリエ変換 (2016/07/31)
  5. 有理数と無理数の演算 (2016/07/31)
  6. 素数判定法 (2016/07/31)
  7. 連立方程式を解く -1- (2016/07/31)
  8. 連立方程式を解く -2- (2016/07/31)
  9. 数値積分法 -1- (2016/07/31)
  10. 極値計算法 (2017/04/16)
  11. 素因数分解 -1- (2018/03/04)
  12. 素因数分解 -2- (2018/03/04)

固有値問題。固有値の計算法とその応用。

  1. 対称行列の固有値 (2016/09/03)
  2. カルーネン・レーベ展開 (2016/09/03)
  3. 画像の固有空間 (2016/09/03)

画像処理。画像に対する様々な処理法。

  1. シーム・カービング (2016/10/23)
  2. ガボール・フィルタ (2016/10/23)
  3. 顕著性マップ (2016/10/23)
  4. エッジ抽出 (2017/08/12)
  5. コーナー検出 (2019/11/10)
  6. Scale-Invariant Feature Transform ( SIFT ) (2021/06/20)

確率・統計。確率の話から統計検定・推定まで。

  1. 組み合わせ・順列 (2010/02/28)
  2. 確率空間 (2010/04/25)
  3. 離散確率分布 (2010/05/30)
  4. 多変数の確率分布 (2010/07/04)
  5. 正規分布 (2010/08/29)
  6. 標本分布 (2010/08/29)
  7. 標本の抽出と要約 (2010/09/26)
  8. 推定 (2010/10/31)
  9. 検定 (2010/12/05)
  10. 順序統計量 (2011/01/30)
  11. 二標本の解析 - 1 - (2011/05/08)
  12. 二標本の解析 - 2 - (2011/05/08)
  13. 回帰分析法 (2012/05/20)
  14. 分散分析法(ANOVA) (2011/12/28)
  15. 共分散分析法(ANCOVA) (2012/03/31)
  16. 因子分析法 (2012/07/01)
  17. ベイズの定理 (2012/12/09)
  18. 一般化線形モデル (2014/03/09)
  19. ロジスティック回帰 (2014/03/09)
  20. 順序ロジスティック回帰 (2016/05/03)
  21. ポアソン回帰 (2014/09/28)
  22. 生存時間解析 (2016/02/08)
  23. 正則化最小二乗法 (2016/03/20)
  24. 主成分回帰 ( PCR ) と部分最小二乗法 ( PLS ) (2016/07/17)
  25. 数量化法 (2020/12/29)

曲線描画。曲線の描画方法をいろいろ紹介。

  1. 多項式を利用した曲線描画 (2013/03/02)
  2. ベジェ曲線 (2013/04/14)
  3. B-スプライン曲線 (2016/08/11)

パターン認識。データの分類や自動認識について。

  1. 凝集型クラスタリング (2016/12/18)
  2. K-平均法 (2017/02/12)
  3. 自己組織化写像 ( SOM ) (2017/03/05)
  4. パーセプトロン (2017/10/08)
  5. ニューラル・ネットワーク (2017/12/10)
  6. サポート・ベクタ・マシーン (2019/01/12)
  7. 決定木 (2019/03/02)
  8. 畳み込みニューラル・ネットワーク (2024/02/24) New

[Back to HOME]タイトルに戻る
inserted by FC2 system