Python Programming
CONTENTS
お気楽 Python プログラミング入門
CONTENTS
第 1 回 データ型と制御構造
第 2 回 関数とファイル入出力
第 3 回 再帰定義と高階関数
第 4 回 正規表現とジェネレータ
第 5 回 オブジェクト指向の基礎知識
Algorithms with Python
はじめに
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] (改訂 2010/10/10)
データの削除、AVLtree クラスの作成、AVL 木の評価、Appendix (木の高さによる実装)
- 2007/02/17 2-3 木 [1] (修正 2010/10/10)
2-3 木、データの探索、データの挿入
- 2007/02/18 2-3 木 [2] (改訂 2010/10/10)
データの削除、Tree23 クラスの作成、2-3 木の評価
- 2007/02/24 赤黒木 [1] (改訂 2008/12/28)
赤黒木、赤黒木の条件、データの挿入、プログラムの作成、木の回転操作と色の塗り替え、データの挿入処理、バランスの修正処理、データ挿入のテスト
- 2007/02/25 赤黒木 [2] (改訂 2008/12/28, 2010/10/10)
データの削除、バランスの修正、プログラムの作成、バランスの修正処理、データ削除のテスト、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]
コスト最小のグラフ、プリムのアルゴリズム、クラスカルのアルゴリズム、追記 (2012/01/29)
- 2007/04/07 動的計画法 (改訂 2012/01/22)
組み合わせの数、動的計画法による高速化、動的計画法とメモ化、整数の分割、ナップザックの問題、プログラムの作成、実行結果
- 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] (修正 2010/10/16)
適応型レンジコーダの高速化、二分木を使った高速化、プログラムの作成、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 木 (改訂 2010/10/10)
AA 木とは？、木のレベル、データの挿入、AA 木のプログラム、データの挿入処理、データ挿入のテスト、データの削除、葉または子を一つ持つ節の場合、子を二つ持つ節の場合、子を三つ持つ節の場合、データ削除のプログラム、データ削除のテスト、AAtree クラスの作成、AA 木の評価
- 2009/01/04 赤黒木 [3] (改訂 2010/10/10)
2-3 木をベースにした赤黒木の条件、Left-Leaning Red Black Tree (LLRB 木) の条件、データの挿入、データ挿入のテスト、データの削除、バランスの修正、データ削除のプログラム、左部分木の修正、右部分木の修正、データ削除のテスト、LLRB23tree クラスの作成、LLRB 木の評価
- 2009/01/10 赤黒木 [4] (改訂 2010/10/10)
2-3 木をベースにした赤黒木、データの挿入、データ挿入のテスト、データ削除のテスト、RB23tree クラスの作成、RB23tree の評価
- 2009/01/11 赤黒木 [5] (改訂 2010/10/10)
2-3-4 木をベースにした LLRB 木、子を 4 つ持つ節の表し方、データの挿入、データ挿入のテスト、データの削除、データ削除のプログラム、データ削除のテスト、LLRBtree クラスの作成、LLRBtree の評価、Appendix 黒高さを使った実装
- 2009/12/12 接尾辞木 (suffix tree) [1]
接尾辞木の簡単な作り方、接尾辞木の特徴、使用メモリの低減、節の定義、単純な実装方法、簡単な実行例、簡単な応用例、追記 (2009/12/20)
- 2009/12/19 接尾辞木 (suffix tree) [2]
Ukkonen のアルゴリズム、サフィックスリンク、サフィックスリンクの作り方、節を分割しないときの注意点、プログラムの作成、葉の挿入処理、節の分割処理、簡単な実行例、実行速度の比較、追記 (2009/12/20)
- 2009/12/26 接尾辞木 (suffix tree) [3]
一般化接尾辞木とは？、一般化接尾辞木の構築方法、プログラムの作成、パターンの探索、簡単な実行例１、共通部分文字列の探索、簡単な実行例２
- 2010/01/17 接尾辞配列 (suffix array) [6]
クラス SuffixArray の定義、パターンの探索、簡単な実行例、高さ配列とは？、逆接尾辞配列、高さ配列の構築アルゴリズム、高さ配列を用いた接尾辞配列の巡回、部分文字列の探索問題、繰り返し出現する部分文字列を求める
- 2012/01/28 Union-Find
Union-Find とは？、ナイーブな実装方法、木による Union-Find の実装、プログラムの作成、実行結果、経路の圧縮、プログラムの作成 (2)、実行結果 (2)、2 つの方法を組み合わせる、頂点の連結判定、深さ優先探索による解法、Union-Find による解法
- 2012/02/05 巡回セールスマン問題 (修正 2012/02/12)
巡回セールスマン問題 (TSP) とは？、TSP を総当りで解く、データの入力、円順列とじゅず順列、深さ優先探索で解く、実行結果、TSP を欲張り法で解く、実行結果 (2)、クラスカルのアルゴリズムの変形版で解く、実行結果 (3)
- 2012/02/12 巡回セールスマン問題 [2]
分割統治法とは？、分割の方法、プログラムの作成、分割のテスト、統合の方法、プログラムの作成 (2)、実行結果、深さ優先探索との組み合わせ、実行結果 (2)、Appendix: 選択 (2012/02/18)
- 2012/02/19 巡回セールスマン問題 [3]
局所探索法とは？、2-opt 法、2-opt 法のプログラム、実行結果 (1)、or-opt 法、or-opt 法のプログラム、実行結果 (2)、2-opt 法と or-opt 法の組み合わせ、実行結果 (3)
- 2012/02/26 巡回セールスマン問題 [4] (改訂 2019/06/29)
動的計画法による解法、メモ化関数による実装、実行結果 (1)、繰り返しによる実装、実行結果 (2)、巡回路を求める、実行結果 (3)、簡単な下限値枝刈り法による解法、実行結果 (4)
- 2012/03/24 ヒープ [2]
Euclidean Minimum Spanning Tree、プログラムの作成、実行結果、プリムのアルゴリズムの改良、実行結果 (2)、キー値の減算処理、簡単なテスト、プリムのアルゴリズムの改良 (2)、実行結果 (3)
- 2012/03/31 ヒープ [3]
最短経路の探索、隣接行列の作成、プログラムの作成、ダイクストラのアルゴリズムの改良、実行結果、A* アルゴリズムによる探索、実行結果 (2)
- 2014/01/12 Algorithm X
敷き詰め問題、Exact Cover Problem、プログラムの作成 (1)、実行結果 (1)、Algorithm X の基本、連想リストによる Algorithm X の実装、プログラムの作成 (2)、実行結果 (2)
- 2014/01/19 Dancing Links
Dancing Links とは？、Dancing Links の操作方法、データ構造の定義、Dancing Linsk の生成、行と列の削除、行と列の復元、Dancing Links による Algorithm X の実装、実行結果
番外編
- 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, 組み合わせテスト)
参考文献
- A.V.Aho, John E. Hopcroft, Jeffrey D. Ulman, 『データ構造とアルゴリズム』, 培風館, 1987
- 奥村晴彦, 『Ｃ言語による最新アルゴリズム事典』, 技術評論社, 1991
- 近藤嘉雪, 『Ｃプログラマのためのアルゴリズムとデータ構造』, ソフトバンク, 1998
お気楽 Python/Tkinter 入門
CONTENTS
権利・免責事項など
お気楽 Python プログラミング入門、Algorithms with Python、お気楽 Python/Tkinter 入門の著作権は筆者「広井誠 (Makoto Hiroi)」が保持します。無断使用や無断転載は禁止いたします。
お気楽 Python プログラミング入門、Algorithms with Python、お気楽 Python/Tkinter 入門で作成したプログラムはフリーソフトウェアとします。ご自由にお使いください。プログラムの改造や配布もご自由にどうぞ。その際は、出典を明記してくださるようお願いいたします。
なお、これらのプログラムは無保証であり、使用したことにより生じた損害について、作者「広井誠 (Makoto Hiroi)」は一切の責任を負いません。また、これらのプログラムを販売することで利益を得るといった商行為は禁止いたします。
Copyright (C) 2006-2019 Makoto Hiroi
All rights reserved.