Python Programming
CONTENTS
新・お気楽 Python プログラミング入門
- 2022/08/27 新版 (Python3) に改訂
CONTENTS
第 1 回 データ型と制御構造
第 2 回 関数とファイル入出力
第 3 回 再帰定義と高階関数
第 4 回 正規表現とジェネレータ
第 5 回 オブジェクト指向の基礎知識
Algorithms with Python (ver 3.0)
はじめに
Algorithms with Python は、いろいろなアルゴリズムやデータ構造を Python で実装してみようというページです。「アルゴリズムとデータ構造」に関する M.Hiroi の覚え書にすぎませんが、よろしければお付き合いくださいませ。
- 2023/12/01 位数と原始根 に合同式 x2 ≡ a (mod n) の解き方を追加
CONTENTS
●初級編
- 2022/09/03 再帰定義
フィボナッチ関数、累乗、ハノイの塔、組み合わせ、たらいまわし関数、メモ化関数、遅延評価
- 2022/09/03 連結リストとキュー
連結リスト、循環リスト、双方向リスト、ディーキュー (deque)、リングバッファ
- 2022/09/03 二分木とヒープ
二分木、探索、挿入、削除、巡回、ヒープ、ヒープの構築、優先度つき待ち行列
- 2022/09/03 ハッシュ法
ハッシュ法の仕組み、チェイン法、オープンアドレス法、線形走査法、二重ハッシュ法
- 2022/09/03 集合、グラフ、経路の探索
集合、集合の演算、追記: 直積集合、グラフ、隣接行列、隣接リスト、深さ優先探索、幅優先探索、反復深化
- 2022/09/03 整列 [1]
ソートの安定性、バブルソート、挿入ソート、選択ソート、シェーカーソート、シェルソート、コムソート、クイックソート、クイックソートの改良、median-of-9
- 2022/09/03 整列 [2]
ヒープソート、マージソート、マージソートの改良、基数ソート、分布数えソート、直接基数法、基数交換法
- 2022/09/03 整列 [3]
連結リストのクイックソートとマージソート、文字列のソート、マルチキークイックソート、MSD radix sort
- 2022/09/03 文字列の探索
力任せの探索、Boyer - Moore 法 (BM 法)、Horspool のアルゴリズム (BMH 法)、Sunday のアルゴリズム (quick search)
●中級編
- 2022/09/03 乱数
線形合同法、線形合同法の欠点、線形合同法の改良、実数の乱数、モンテカルロ法、M 系列乱数、M 系列の特徴、M 系列の生成、GFSR 法、乱数の生成、線形合同法との比較
- 2022/09/03 乱数 [2]
lagged fibonacci 法、乱数の生成、lagged fibonacci 法の評価、乱数とクイックソート、スキップリスト (Skip List)、データの探索、挿入、削除、スキップリストの評価
- 2022/09/10 欲張り法
欲張り法、最短経路の探索、ダイクストラのアルゴリズム、騎士の巡歴、バックトラックによる解法、欲張り法による解法、騎士の周遊、周遊コースへの変換
- 2022/09/10 欲張り法 [2]
コスト最小のグラフ、プリムのアルゴリズム、クラスカルのアルゴリズム、補足
- 2022/09/10 動的計画法
組み合わせの数、動的計画法による高速化、動的計画法とメモ化、整数の分割、ナップザックの問題、プログラムの作成、実行結果
- 2022/09/10 幅優先探索と反復深化
パズル (8 パズル) の説明、幅優先探索による解法、双方向探索、最長手数の求め方、反復深化による解法、下限値枝刈り法
- 2022/09/10 Union-Find
Union-Find とは？、ナイーブな実装方法、木による Union-Find の実装、プログラムの作成、実行結果、経路の圧縮、プログラムの作成 (2)、実行結果 (2)、2 つの方法を組み合わせる、頂点の連結判定、深さ優先探索による解法、Union-Find による解法
- 2023/10/07 素数
合同式、フェルマーの小定理、べき剰余、エラトステネスの篩、区間篩、素数の判定、フェルマーテスト、偽素数、ミラーラビン素数判定法、メルセンヌ素数、リュカ-レーマー・テスト、双子素数
- 2023/10/15 素因数分解 (prime factorization)
試し割り法、wheel factorization、ポラードのロー法、プログラムの作成、実行例、ロー法の高速化、乱数列の計算を工夫する (1)、乱数列の計算を工夫する (2)、ブレントの変形版、ロー法による素因数分解の実装、p-1 法、p-1 法のプログラム、ロー法と p-1 法を使った素因数分解、実行例
- 2023/11/03 約数とオイラーのトーシェント関数
約数の個数、約数の合計値、約数を求める、約数関数、完全数、過剰数と不足数、友愛数、友愛数の高速化、オイラーのトーシェント関数、メビウス関数、メビウス関数の性質、メビウスの反転公式
- 2023/11/03 拡張ユークリッドの互除法
不定方程式と拡張ユークリッドの互除法、鶴亀算、水差し問題、中国の剰余定理、中国剰余定理の一般化、互いに素でない場合、有限体、拡大体、合同式の徐算
- 2023/12/01 位数と原始根
位数と原始根、ウィルソンの定理、プログラムの作成、プログラムの高速化、原始根を求める、平方剰余、ルジャンドル記号とオイラーの基準、平方剰余の相互法則、合同式 x2 ≡ a (mod n) の解き方、ヤコビ記号、ヤコビ記号の性質、ヤコビ記号の計算
- 2022/10/15 部分和問題
べき集合、ナイーブな解法、深さ優先探索＋枝刈り、動的計画法、プログラムの改良、簡単なテスト、擬似完全数と不思議数
●木構造
- 2022/09/03 トライとパトリシア
トライ、パトリシア、探索、挿入、削除、巡回、共通接頭辞 (common prefix)
- 2022/09/03 Ternary Search Tree
Ternary Search Tree、探索、挿入、削除、巡回、共通接頭辞 (common prefix)、パトリシアへの応用
- 2022/09/03 AVL 木 [1]
二分木の回転操作、AVL 木、データの挿入、平衡度の修正、１重回転、２重回転
- 2022/09/03 AVL 木 [2]
データの削除、AVLtree クラスの作成、AVL 木の評価、Appendix (木の高さによる実装)
- 2022/09/03 2-3 木 [1]
2-3 木、データの探索、データの挿入
- 2022/09/03 2-3 木 [2]
データの削除、Tree23 クラスの作成、2-3 木の評価
- 2022/09/03 赤黒木 [1]
赤黒木、赤黒木の条件、データの挿入、プログラムの作成、木の回転操作と色の塗り替え、データの挿入処理、バランスの修正処理、データ挿入のテスト
- 2022/09/03 赤黒木 [2]
データの削除、バランスの修正、プログラムの作成、バランスの修正処理、データ削除のテスト、RBtree クラスの作成、赤黒木の評価
- 2022/09/03 Treap
Treap、データの挿入、データの削除、Treap クラスの作成、Treap の評価
- 2022/09/10 スプレー木
スプレー木、Spaly 操作、データの探索、挿入、削除、Top-Down Splay、スプレー木の評価
- 2022/09/10 AA 木
AA 木とは？、木のレベル、データの挿入、AA 木のプログラム、データの挿入処理、データ挿入のテスト、データの削除、葉または子を一つ持つ節の場合、子を二つ持つ節の場合、子を三つ持つ節の場合、データ削除のプログラム、データ削除のテスト、AAtree クラスの作成、AA 木の評価
- 2022/09/10 赤黒木 [3]
2-3 木をベースにした赤黒木の条件、Left-Leaning Red Black Tree (LLRB 木) の条件、データの挿入、データ挿入のテスト、データの削除、バランスの修正、データ削除のプログラム、左部分木の修正、右部分木の修正、データ削除のテスト、LLRB23tree クラスの作成、LLRB 木の評価
- 2022/09/10 赤黒木 [4]
2-3 木をベースにした赤黒木、データの挿入、データ挿入のテスト、データ削除のテスト、RB23tree クラスの作成、RB23tree の評価
- 2022/09/10 赤黒木 [5]
2-3-4 木をベースにした LLRB 木、子を 4 つ持つ節の表し方、データの挿入、データ挿入のテスト、データの削除、データ削除のプログラム、データ削除のテスト、LLRBtree クラスの作成、LLRBtree の評価、Appendix 黒高さを使った実装
●探索アルゴリズム
- 2022/11/26 ミニマックス法
ゲームの木、ミニマックス法、ゲーム「カラハ (Kalah)」の説明、プログラムの作成、Board のメソッド、ゲーム木の探索、KALAH の処理、ミニマックス法のプログラム、ゲームの進行、実行結果
- 2022/11/26 アルファベータ法
アルファベータ法、アルファベータ法のプログラム、実行結果
- 2022/11/26 ネガマックス法とネガスカウト法
ネガマックス法、ネガアルファ法、ネガアルファ法の改良、プログラムの作成、実行結果 (1)、null window search、ネガスカウト法、プログラムの作成、実行結果 (2)
- 2022/11/26 置換表と MTD(f) 法
ネガマックス法と置換表、実行結果 (1)、アルファベータ法と置換表、実行結果 (2)、ネガスカウト法と置換表、実行結果 (3)、MTD(f) 法、実行結果 (4)
- 2022/09/10 ヒューリスティック探索
山登り法、最良優先探索、A* (A star) アルゴリズム、双方向の A* (A star) アルゴリズム
- 2022/09/10 ヒープ [2]
Euclidean Minimum Spanning Tree、プログラムの作成、実行結果、プリムのアルゴリズムの改良、実行結果 (2)、キー値の減算処理、簡単なテスト、プリムのアルゴリズムの改良 (2)、実行結果 (3)
- 2022/09/17 ヒープ [3]
最短経路の探索、隣接行列の作成、プログラムの作成、ダイクストラのアルゴリズムの改良、実行結果、A* アルゴリズムによる探索、実行結果 (2)
- 2022/09/17 Algorithm X
敷き詰め問題、Exact Cover Problem、プログラムの作成 (1)、実行結果 (1)、Algorithm X の基本、連想リストによる Algorithm X の実装、プログラムの作成 (2)、実行結果 (2)
- 2022/09/17 Dancing Links
Dancing Links とは？、Dancing Links の操作方法、データ構造の定義、Dancing Linsk の生成、行と列の削除、行と列の復元、Dancing Links による Algorithm X の実装、実行結果
●データ圧縮 (前編)
- 2022/09/17 連長圧縮
ランレングスとは？、ランレングスの開始記号と PackBits、ランレングスの実装、Switched Run Length Encoding、Zero Length Encoding
- 2022/09/17 整数の符号化
符号の種類 (FF 符号、FV 符号、接頭符号、符号木)、α符号、γ符号、δ符号、CBT 符号、ゴロム・ライス符号、ビット入出力処理、ランレングスへの応用
- 2022/09/17 シャノン・ファノ符号とハフマン符号
無記憶情報源モデルとエントロピー、シャノン・ファノ符号、符号木の作成、ハフマン符号、ハフマン木の作成、符号木の取り扱い、符号化のプログラム、復号のプログラム、ハフマン符号のプログラム
- 2022/09/17 LZ77 符号
LZ 符号の基礎知識、LZSS 符号、符号化、復号、スライド窓の構造、最長一致系列の探索、LZSS 符号のプログラム
- 2022/09/17 LZB 符号と LZH 符号
LZSS 符号の弱点、LZB 符号、長さの符号化、距離の符号化、LZH 符号、LZH 符号の処理概要、LZSS 符号の処理、ハフマン符号の処理
- 2022/09/17 LZ78 符号
LZ78 符号、LZW 符号、トライと辞書の対応、符号化、復号、復号の注意点、辞書の操作関数、符号化のプログラム、復号のプログラム、LZW 符号の弱点、CBT 符号による改良
- 2022/09/17 LZT 符号
LZT 符号、ハッシュ法によるトライの実装、キューの作成、辞書の作成、符号化のプログラム、復号のプログラム、LZT 符号とハフマン符号の組み合わせ
●データ圧縮 (中編)
- 2022/09/23 レンジコーダ [1]
算術符号の基本的な考え方、算術符号の符号化、算術符号の復号、算術符号の問題点、レンジコーダの基本的な考え方、レンジコーダの符号化、レンジコーダの復号、レンジコーダの実装、符号化のプログラム、桁上がりの処理、レンジコーダによる符号化、復号のプログラム、レンジコーダによる復号、評価結果
- 2022/09/23 レンジコーダ [2]
桁上がりのないレンジコーダ、プログラムの作成、符号化のプログラム、復号のプログラム、評価結果、適応型レンジコーダ、出現頻度表の初期化と更新、適応型レンジコーダの符号化、適応型レンジコーダの復号、評価結果
- 2022/09/23 レンジコーダ [3]
適応型レンジコーダの高速化、評価結果、二分木を使った高速化、プログラムの作成、評価結果、Binary Indexed Tree、累積度数の求め方、出現頻度の求め方、出現頻度の更新、出現頻度表の初期化と更新、記号の復号、評価結果
- 2022/09/23 有限文脈モデル
マルコフ情報源モデル、有限文脈モデル、プログラムの作成、評価結果、適応型レンジコーダの改良、有限文脈モデルとエスケープ記号、エスケープ確率の計算方法、プログラムの作成、評価結果
- 2022/09/23 バイナリレンジコーダ [1]
バイナリレンジコーダと数値の対応、αモデル、バイナリモデル、バイナリレンジコーダのプログラム、バイナリモデルの作成、評価結果、補足、αモデルの作成、γモデルの作成
- 2022/09/23 バイナリレンジコーダ [2]
バイナリレンジコーダによる LZSS 符号の改良、評価結果、order-1 のプログラム、評価結果、バイナリレンジコーダによる LZT 符号の改良、評価結果
- 2022/09/23 バイナリレンジコーダ [3], スプレー符号
混合法によるバイナリレンジコーダの改良、プログラムの作成、評価結果１、評価結果２、スプレー符号、符号木のスプレー操作、プログラムの作成、スプレイ操作、符号化、復号、ファイルの符号化と複合、評価結果、有限文脈モデル、評価結果
●データ圧縮 (後編)
- 2022/10/01 ブロックソート
ブロックソートの符号化、ブロックソートの復号、ブロックソートのプログラム、MTF (Move To Front) 法、MTF 法のプログラム、MTF 法の改良、2 番目に移動する方法、MTF-1 の説明、MTF-1 のプログラム、さらなる改良、MTF-2 のプログラム、評価結果
- 2022/10/01 ブロックソート [2]
ブロックソートとランレングス (Zero Length Encoding)、プログラムの作成、評価結果、情報源モデルの改良、structured model、プログラムの作成、評価結果、0-1-2 coding、プログラムの作成、評価結果、混合法、プログラムの作成、評価結果
- 2022/10/01 ブロックソート [3]
γモデルとバイナリモデル、評価結果、バイナリレンジコーダによる 0-1-2 coding の実装、評価結果、連長をγモデルで符号化、プログラムの作成、評価結果
- 2022/10/02 Prediction by Partial Matching (PPM)
PPM の基礎知識、エスケープ確率の計算方法、符号化のアルゴリズム、update exclusion、exclusion、出現頻度表と exclusion の処理、トライの作成、符号化のプログラム、復号のプログラム、評価結果
- 2022/10/02 Prediction by Partial Matching (PPM) [2]
Method D、記号の増分値の変更、LRU スキーム、プログラムの作成、評価結果
●接尾辞配列と接尾辞木
●巡回セールスマン問題
- 2022/10/08 巡回セールスマン問題 [1]
巡回セールスマン問題 (TSP) とは？、TSP を総当りで解く、データの入力、円順列とじゅず順列、深さ優先探索で解く、実行結果、TSP を欲張り法で解く、実行結果 (2)、クラスカルのアルゴリズムの変形版で解く、実行結果 (3)
- 2022/10/08 巡回セールスマン問題 [2]
分割統治法とは？、分割の方法、プログラムの作成、分割のテスト、統合の方法、プログラムの作成 (2)、実行結果、Appendix: 選択
- 2022/10/08 巡回セールスマン問題 [3]
局所探索法とは？、2-opt 法、2-opt 法のプログラム、実行結果 (1)、or-opt 法、or-opt 法のプログラム、実行結果 (2)、2-opt 法と or-opt 法の組み合わせ、実行結果 (3)
- 2022/10/08 巡回セールスマン問題 [4]
動的計画法による解法、メモ化関数による実装、実行結果 (1)、繰り返しによる実装、実行結果 (2)、巡回路を求める、実行結果 (3)、簡単な下限値枝刈り法による解法、実行結果 (4)
●番外編
- 2022/10/08 統計学の基礎知識 [1]
度数分布表、平均値と標準偏差、確率変数と確率分布、離散型の確率分布、二項分布、連続型の確率分布、正規分布、確率分布の平均値と分散、連続型確率分布の平均値と分散、母集団と標本、無作為抽出のプログラム、信頼区間、母集団が正規分布の場合、母比率の推定
- 2022/10/08 統計学の基礎知識 [2]
検定の基本的な考え方、適合度の検定、独立性の検定、母集団の平均値の検定、分散が未知の場合、平均値の差の検定、分散が未知の場合、対をなすデータの差の検定、母比率の検定、母比率の差の検定
- 2022/10/08 統計学の基礎知識 [3]
相関図、相関係数、順位相関係数、無相関検定、擬似乱数の検定、回帰、時系列データ、移動平均法
- 2022/10/08 擬似乱数の検定
擬似乱数の性質、等確率性の検定、無規則性の検定 (系列相関係数による検定、分割表による検定)、Sum Test
- 2022/10/08 擬似乱数の検定 [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
- 2023/01/03 新版 (Python3) に改訂
権利・免責事項など
新・お気楽 Python プログラミング入門, 新・お気楽 Python/Tkinter 入門, Algorithms with Python (ver 3.0) の著作権は筆者「広井誠 (Makoto Hiroi)」が保持します。無断使用や無断転載は禁止いたします。
新・お気楽 Python プログラミング入門, 新・お気楽 Python/Tkinter 入門, Algorithms with Python (ver 3.0) で作成したプログラムはフリーソフトウェアとします。ご自由にお使いください。プログラムの改造や配布もご自由にどうぞ。その際は、出典を明記してくださるようお願いいたします。
なお、これらのプログラムは無保証であり、使用したことにより生じた損害について、作者「広井誠 (Makoto Hiroi)」は一切の責任を負いません。また、これらのプログラムを販売することで利益を得るといった商行為は禁止いたします。
Copyright (C) 2006-2023 Makoto Hiroi
All rights reserved.