CONTENTS
CONTENTS
はじめに
Algorithms with Python は、いろいろなアルゴリズムやデータ構造を Python で実装してみようというページです。「アルゴリズムとデータ構造」に関する M.Hiroi の覚え書にすぎませんが、よろしければお付き合いくださいませ。
CONTENTS
- 2006/11/19 再帰定義
フィボナッチ関数、累乗、ハノイの塔、組み合わせ、たらいまわし関数、メモ化関数、遅延評価
- 2006/11/26 連結リストとキュー
連結リスト、循環リスト、双方向リスト、ディーキュー (deque)、リングバッファ
- 2006/12/03 二分木とヒープ
二分木、探索、挿入、削除、巡回、ヒープ、ヒープの構築、優先度つき待ち行列
- 2006/12/10 ハッシュ法
ハッシュ法の仕組み、チェイン法、オープンアドレス法 (2006/12/16)、線形走査法、二重ハッシュ法
- 2006/12/17 集合、グラフ、経路の探索
集合、集合の演算、グラフ、隣接行列、隣接リスト、深さ優先探索、幅優先探索、反復深化
- 2006/12/23 整列 [1]
ソートの安定性、バブルソート、挿入ソート、選択ソート、シェーカーソート
シェルソート、コムソート、クイックソート、クイックソートの改良
- 2006/12/30 整列 [2]
ヒープソート、マージソート、基数ソート、分布数えソート、直接基数法、基数交換法
- 2007/01/05 整列 [3]
連結リストのクイックソートとマージソート、文字列のソート、マルチキークイックソート、MSD radix sort
- 2007/01/13 トライとパトリシア
トライ、パトリシア、探索、挿入、削除、巡回、共通接頭辞 (common prefix)
- 2007/01/20 Ternary Search Tree
Ternary Search Tree、探索、挿入、削除、巡回、共通接頭辞 (common prefix)、パトリシアへの応用
- 2007/01/27 文字列の探索
力任せの探索、Boyer - Moore 法 (BM 法)、Horspool のアルゴリズム (BMH 法)
Sunday のアルゴリズム (quick search)、Shift_JIS への対応
- 2007/02/03 AVL 木 [1] (改訂 2007/02/10)
二分木の回転操作、AVL 木、データの挿入、平衡度の修正、１重回転、２重回転
- 2007/02/10 AVL 木 [2]
データの削除、AVLtree クラスの作成、AVL 木の評価、Appendix (木の高さによる実装)
- 2007/02/17 2-3 木 [1]
2-3 木、データの探索、データの挿入
- 2007/02/18 2-3 木 [2]
データの削除、Tree23 クラスの作成、2-3 木の評価
- 2007/02/24 赤黒木 [1] (改訂 2008/12/28)
赤黒木、赤黒木の条件、データの挿入、プログラムの作成、木の回転操作と色の塗り替え、データの挿入処理、バランスの修正処理、データ挿入のテスト
- 2007/02/25 赤黒木 [2] (改訂 2008/12/28)
データの削除、バランスの修正、プログラムの作成、バランスの修正処理、データ削除のテスト、RBtree クラスの作成、赤黒木の評価
- 2007/03/03 乱数 (更新 2007/03/11)
線形合同法、線形合同法の欠点、線形合同法の改良、実数の乱数、モンテカルロ法
(2007/03/11) M 系列乱数、M 系列の特徴、M 系列の生成、GFSR 法、乱数の生成、線形合同法との比較
- 2007/03/17 乱数 [2] (更新 2007/03/21)
lagged fibonacci 法、乱数の生成、lagged fibonacci 法の評価、乱数とクイックソート
(2007/03/21) スキップリスト (Skip List)、データの探索、挿入、削除、スキップリストの評価
- 2007/03/25 Treap
Treap、データの挿入、データの削除、Treap クラスの作成、Treap の評価
- 2007/03/31 スプレー木
スプレー木、Spaly 操作、データの探索、挿入、削除、Top-Down Splay、スプレー木の評価
- 2007/04/01 欲張り法
欲張り法、最短経路の探索、ダイクストラのアルゴリズム、騎士の巡歴、バックトラックによる解法、欲張り法による解法、騎士の周遊、周遊コースへの変換
- 2007/04/07 欲張り法 [2], 動的計画法
コスト最小のグラフ、プリムのアルゴリズム、クラスカルのアルゴリズム、動的計画法、ナップザックの問題
- 2007/04/08 ミニマックス法とアルファベータ法 (改訂 2007/04/14)
ゲームの木、ミニマックス法、アルファベータ法、ゲーム「カラー」の説明、ミニマックス法のプログラム、アルファベータ法のプログラム
- 2007/04/15 ネガマックス法とネガスカウト法
ネガマックス法、ネガアルファ法、ネガアルファ法の改良、null window search、ネガスカウト法
- 2007/04/21 置換表と MTD(f) 法
ネガマックス法と置換表、アルファベータ法と置換表、ネガスカウト法と置換表、MTD(f) 法
- 2007/04/28 幅優先探索と反復深化
パズル (8 パズル) の説明、幅優先探索による解法、双方向探索、最長手数の求め方、反復深化による解法、下限値枝刈り法
- 2007/05/03 ヒューリスティック探索
山登り法、最良優先探索、A* (A star) アルゴリズム、双方向の A* (A star) アルゴリズム
- 2007/05/12 連長圧縮
ランレングスとは？、ランレングスの開始記号と PackBits、ランレングスの実装、Switched Run Length Encoding、Zero Length Encoding
- 2007/05/13 整数の符号化
符号の種類 (FF 符号、FV 符号、接頭符号、符号木)、α符号、γ符号、δ符号、CBT 符号、ゴロム・ライス符号、ビット入出力処理、ランレングスへの応用
- 2007/05/19 シャノン・ファノ符号とハフマン符号
無記憶情報源モデルとエントロピー、シャノン・ファノ符号、符号木の作成、ハフマン符号、ハフマン木の作成、符号木の取り扱い、符号化のプログラム、復号のプログラム、ハフマン符号のプログラム
(2007/10/06) 修正１、修正２
- 2007/05/20 LZ77 符号
LZ 符号の基礎知識、LZSS 符号、符号化、復号、スライド窓の構造、最長一致系列の探索、LZSS 符号のプログラム
- 2007/05/26 LZB 符号と LZH 符号
LZSS 符号の弱点、LZB 符号、長さの符号化、距離の符号化、LZH 符号、LZH 符号の処理概要、LZSS 符号部の処理、ハフマン符号部の処理、修正 (2007/10/06)
- 2007/05/27 LZ78 符号
LZ78 符号、LZW 符号、トライと辞書の対応、符号化、復号、復号の注意点、辞書の操作関数、符号化のプログラム、復号のプログラム、LZW 符号の弱点、CBT 符号による改良
- 2007/06/02 LZT 符号
LZT 符号、ハッシュ法によるトライの実装、キューの作成、辞書の作成、符号化のプログラム、復号のプログラム、LZT 符号とハフマン符号の組み合わせ
- 2007/06/03 レンジコーダ
算術符号の基本的な考え方、レンジコーダの基本的な考え方、レンジコーダの実装、符号化のプログラム、桁上がりの処理、復号のプログラム
- 2007/06/09 レンジコーダ [2]
桁上がりのないレンジコーダ、符号化のプログラム、復号のプログラム、適応型レンジコーダ、出現頻度表の初期化と更新、符号化、復号、修正 (2007/10/06)
- 2007/06/10 レンジコーダ [3]
適応型レンジコーダの高速化、二分木を使った高速化、プログラムの作成、Binary Indexed Tree、累積度数の求め方、出現頻度の求め方、出現頻度の更新、出現頻度表の初期化と更新、記号の復号
- 2007/06/16 有限文脈モデル
マルコフ情報源モデル、有限文脈モデル、プログラムの作成、適応型レンジコーダの改良、有限文脈モデルとエスケープ記号、エスケープ確率の計算方法
- 2007/06/17 バイナリレンジコーダ (改訂 2007/06/25)
バイナリレンジコーダと数値の対応、αモデル、バイナリモデル、バイナリレンジコーダのプログラム、バイナリモデルの作成、αモデルの作成、γモデルの作成、補足 (2007/08/04)、修正１、修正２ (2007/10/17)
- 2007/06/23 バイナリレンジコーダ [2] (改訂 2007/06/25)
バイナリレンジコーダによる LZSS 符号の改良、order-1 のプログラム、バイナリレンジコーダによる LZT 符号の改良
- 2007/06/30 バイナリレンジコーダ [3], スプレー符号
混合法によるバイナリレンジコーダの改良、スプレー符号、符号木のスプレー操作、符号化、復号、有限文脈モデル
- 2007/07/14 接尾辞配列 (suffix array)
suffix array とは？、マルチキークイックソートによる suffix array の作成、Larrson Sadakane 法、doubling technique、データ構造の工夫、プログラムの作成
- 2007/07/16 接尾辞配列 (suffix array) [2]
二段階ソート法、プログラムの作成、二段階ソート法の改良 (ratio-2)、順位ソート法
- 2007/07/21 接尾辞配列 (suffix array) [3]
三分割法、プログラムの作成、三分割法の改良 (個数の少ない Type をソート)
- 2007/07/22 接尾辞配列 (suffix array) [4]
ratio-2 による三分割法の改良、プログラムの作成
- 2007/07/29 接尾辞配列 (suffix array) [5]
三分割法の改良、improved two-stage suffix sorting algorithm、プログラムの作成
- 2007/08/05 ブロックソート
ブロックソートの符号化、復号、ブロックソートのプログラム、MTF (Move To Front) 法、MTF 法のプログラム、MTF 法の改良 (MTF-1, MTF-2)、評価結果
- 2007/08/11 ブロックソート [2]
ブロックソートとランレングス、Zero Length Encoding、structured model、0-1-2 coding、混合法
- 2007/08/12 ブロックソート [3]
γモデルとバイナリモデル、バイナリレンジコーダによる 0-1-2 coding の実装、連長をγモデルで符号化
- 2007/08/26 Prediction by Partial Matching (PPM)
PPM の基礎知識、エスケープ確率の計算方法、符号化のアルゴリズム、update exclusion、exclusion、出現頻度表と exclusion の処理、トライの作成、符号化・復号のプログラム
- 2007/09/02 Prediction by Partial Matching (PPM) [2]
Method D、記号の増分値の変更、LRU スキーム、プログラムの作成
- 2009/01/03 AA 木
AA 木とは？、木のレベル、データの挿入、AA 木のプログラム、データの挿入処理、データ挿入のテスト、データの削除、葉または子を一つ持つ節の場合、子を二つ持つ節の場合、子を三つ持つ節の場合、データ削除のプログラム、データ削除のテスト、AAtree クラスの作成、AA 木の評価
- 2009/01/04 赤黒木 [3]
2-3 木をベースにした赤黒木の条件、Left-Leaning Red Black Tree (LLRB 木) の条件、データの挿入、データ挿入のテスト、データの削除、バランスの修正、データ削除のプログラム、左部分木の修正、右部分木の修正、データ削除のテスト、LLRB23tree クラスの作成、LLRB 木の評価
- 2009/01/10 赤黒木 [4]
2-3 木をベースにした赤黒木、データの挿入、データ挿入のテスト、データ削除のテスト、RB23tree クラスの作成、RB23tree の評価
- 2009/01/11 赤黒木 [5]
2-3-4 木をベースにした LLRB 木、子を 4 つ持つ節の表し方、データの挿入、データ挿入のテスト、データの削除、データ削除のプログラム、データ削除のテスト、LLRBtree クラスの作成、LLRBtree の評価、Appendix 黒高さを使った実装
- 2007/11/11 統計学の基礎知識
度数分布表、平均値と標準偏差、確率変数と確率分布、離散型の確率分布、二項分布、連続型の確率分布、正規分布、確率分布の平均値と分散、母集団と標本、無作為抽出のプログラム、信頼区間、母比率の推定
- 2007/11/24 統計学の基礎知識 [2]
検定の基本的な考え方、適合度の検定、独立性の検定、母集団の平均値の検定、平均値の差の検定、対をなすデータの差の検定、母比率の検定、母比率の差の検定
- 2007/12/02 統計学の基礎知識 [3]
相関図、相関係数、順位相関係数、無相関検定、擬似乱数の検定、回帰、時系列データ、移動平均法
- 2007/12/15 擬似乱数の検定
擬似乱数の性質、等確率性の検定、無規則性の検定 (系列相関係数による検定、分割表による検定)、Sum Test
- 2007/12/16 擬似乱数の検定 [2]
BitStream クラスの作成、等確率性の検定 (The Monobit Test, The Poker Test)、無規則性の検定 (The Runs Test, 組み合わせテスト)
[1] A.V.Aho, John E. Hopcroft, Jeffrey D. Ulman, 『データ構造とアルゴリズム』, 培風館, 1987
[2] 奥村晴彦, 『Ｃ言語による最新アルゴリズム事典』, 技術評論社, 1991
[3] 近藤嘉雪, 『Ｃプログラマのためのアルゴリズムとデータ構造』, ソフトバンク, 1998
CONTENTS
『お気楽 Python プログラミング入門』、『Algorithms with Python』、『お気楽 Python/Tkinter 入門』の著作権は筆者「広井誠 (Makoto Hiroi) 」が保持します。無断使用や無断転載は禁止いたします。
『お気楽 Python プログラミング入門』、『Algorithms with Python』、『お気楽 Python/Tkinter 入門』で作成したプログラムはフリーソフトウェアとします。ご自由にお使いください。プログラムの改造や配布もご自由にどうぞ。その際は、出典を明記してくださるようお願いいたします。
なお、これらのプログラムは無保証であり、使用したことにより生じた損害について、作者「広井誠 (Makoto Hiroi) 」は一切の責任を負いません。また、これらのプログラムを販売することで利益を得るといった商行為は禁止いたします。
Copyright (C) 2006-2009 Makoto Hiroi
All rights reserved.
