Booklog - ワンス・アポン・アン・アルゴリズム 物語で読み解く計算

随分と前に買って積んでたので読む。 まえがき ~ はじめに。本書は、計算ーシステマティックな問題解決を具体的な例ー本書では物語を通して紹介していく。 計算の基礎で世界の意味や現実世界の問題解決に繋げることを計算論的思考と呼ばれることもある。計算の汎用性、計算機科学の適用可能性の広さを示すのも本書の目的。 本書は計算を支える 2 つの概念、アルゴリズムと言語の二部で構成される。 はじめにでは、本書の章構成でもある、アルゴリズムと計算・表現とデータ構造・問題解決とその限界・言語の意味・制御構造とループ・再帰・型と抽象化、が何故重要かを説明し、それぞれの概念の依存関係を示して読む順序を提案している。 1,2 章は基礎で、 4 章もデータ構造の基礎となってる。 「はじめに」を読む限りは最近読んでたいくつかの本とのつながりもあり、良い感触。今のところ訳も内容も違和感無し。 なんとなく、例えがある程度知ってるヒト向けかもなと思った。全く知らないヒト向けにしてはちょっと基礎力求められるんじゃなかな。

2026-07-30, read count: 1, page: i ~ xii, 1 ~ 12, pages read: 24

起床。アルゴリズムを使うことが計算。起床のルーチンを例えに、アルゴリズムと計算≒順序付けられた部分問題の解決策の集合とその実行についての説明。 章の前のポエム的なので最初に概念に触れられてるのだけど、各章の物語とは関係ない割に概念がつながってるので、重要なパートっぽい。 1 章。はじめに問題の表現が定められ、各部分問題の解決を繰り返して問題の表現を変換していき、最終的に解決された問題の表現にたどり着く。問題の表現は現実のものに対応している。 ただし問題解決は計算と重なる部分はあるが、純粋に計算が何であるかを表現することはできない。 アルゴリズムを言語で表現することは、有限で、個々のステップに実効性がある形でなければならない。正しい結果を返すこと、正しく終了できることも、アルゴリズムでは重要になる。 意外と難しいぞこの本。 1 章から教科書っぽい文章になった。これは計算機科学の思想・概念を論じてる本だ。物語を利用した思考実験。意図せず気を抜けない本を読み始めてしまった。

2026-07-31, read count: 1, page: 13 ~ 29, pages read: 17

2 章。計算の動的な側面。パラメータがアルゴリズムに柔軟さをもたらす。アルゴリズムの違いは実行時間や実行に必要なリソースに影響を与え、アルゴリズムの複雑性・正確性・効率性といった指標で測れる。 汎用計算機と特定のアルゴリズム一式を実行する計算機。計算を実行するもの＝計算機がアルゴリズムを記述した言語を読める必要があり、また実行の主体になれる必要がある。 アルゴリズムの空間複雑性は、計算が成功するか、必要な資源が足りているか判断する指標となる。時間効率と空間効率。 この本以前にコレだけヘンゼルのポケットのサイズだとか石の数だとかを真面目に考えた本は中々ないんじゃないかな。ここまで来ると笑える。 子供の足で行ける範囲と考えるとそう遠くなかろうけど、連れ出された先が遠いと仮定したら、さぞかしヘンゼルのポケットが大きく石が小さかったんだろうなと言うのが想像できてコレまた笑える。 なんでそんなにポケットパンパンで親にバレないんだよ。 物語をベースにというか、物語はただ利用されてるだけで、殆どは思考実験じゃないかなこの本。中々難しい。 創作の物語にこのシステムの観点を持ち込んだことはなかったので、個人的には新鮮だ。これからの読書生活に影響及ぼすぞコレ。

2026-08-01, read count: 1, page: 30 ~ 46, pages read: 17

通勤。記号を解釈して意味を導くのは計算である。意味はアルゴリズムであり導かれた意味は計算である。 記号をシステマティックに変換して別の記号に変換するのも計算。 きょうは家の事情で忙し過ぎ＆疲労困憊て全然読めなかった。この書き出しだけでも相当メタな話なので、念入りに読むため MP 不足のきょうはここで終える。

2026-08-02, read count: 1, page: 47 ~ 50, pages read: 4

3 章。表現とは何であるか。記号(シーニュ)。知覚・提示されるもの(シニフィアン)と概念(シニフィエ)の関係は、記号と表現する意味の対応。 例えば引用符の有無で表現が変わる。使用と言及の差異。シニフィエのシニフィエのように 2 つのレベルの表現を 1 つにまとめられる。 1 つにシニフィアンが複数にシニフィエ、複数のシニフィアンが 1 つのシニフィエを指すこともある。多義語や同義語。文脈によってシニフィエが変わる。 誤った表現が導かれることは計算の正確性に関わる問題。記号を、対象との同一性や類似性で示されるアイコン・対象と規則的なつながりを持つインデックス・言語のように約束事のみで対象とつながるシンボルの 3 種に分ける。 この分類を使って、いかに記号の表現が変換≒計算されているかを見ることができる。 本書の太字の使い方は不規則なのがちょっと気になる。アイコンは太字なのに他は 2 つは太字でなくて、 3 種に分けたのに 1 つ目だけ特別扱いに見える。太字に意味はありません、てか？

2026-08-03, read count: 1, page: 51 ~ 62, pages read: 12

職場にて ~ 4 章。特定のアクセスパターンを持つ集まりデータ型という。先着順のキュー。到着の逆順に要素を処理するスタック。優先順位付きキューはスタックの last in, first out に対し highest in, firrst out 。 セット(集合)は要素を追加・削除・参照できるデータ型で、その集合に含まれることが問題やアルゴリズムの述語に対応しており、広く利用できる。キーワードに基づき情報を探せる拡張をセットに行ったのがディクショナリ(辞書) パターンに最適な要素の配置をデータ構造という。リストは並んだ列のようなデータ構造。ツリー(木)は先祖・子孫のような関係のデータ構造で、要素数が変動する場合の優先順位を求めるのに向く。 データ構造はアルゴリズムを効率的に実行するうえで重要。リストをつなぐ矢印はポインタと呼ぶ。リストの順序にはそのリスト固有の何らかの意味がる。よってある要素にアクセスするためにはその順序を辿る必要がある。このようなアルゴリズムは線形と呼ばれる。 データ型がデータに対して何をすべきかという要求を説明し、データ構造はその要求を満たす具体的な表現を提供する。データ型をデータ構造が実装するという関係にあり、 1 つのデータ型を複数のデータ構造で実装できる。 なんだかこれまでの章より抽象度が低く具体的で普通のデータ構造の話だった。これまでとの落差がでかい。単に知ってることだから読みやすくなっただけなのかもしれん。

2026-08-04, read count: 1, page: 63 ~ 82, pages read: 20

遺失物取扱所 ~ 5 章。探索空間を効率良く体系化する原則、独立された領域に分割された空間に探索対象の要素を配置し、探索対象の要素をある順番で並べる。本棚、引き出し、バインダー等。 探索空間の分割は、常に正しく探しているもの区別できる状態でなければならない。探索対象が順序付けられている速く見つけることができる。 この点で先頭からしか走査できないリストは探索空間を狭めることができないといえる。手がかりやキーが探索空間の内側と外側を区別する。 ディクショナリを実装するデータ構造にリストを使うより二分探索木による実装の方は対数時間で検索や更新を効率化できる。ただしそれは平衡二分探索木の場合であり、平衡でない場合はコストがかさむ。 トライ木は単語の並びも文字も表現できる。辿った経路が最終的な経路の接頭辞になるためプレフィックス木とも呼ばれる。 この辺も何の変哲もないデータ構造の話で特に気づきはないか。インディ・ジョーンズを本書のような視点で見たことがないのだけは新鮮だが。

2026-08-05, read count: 1, page: 83 ~ 106, pages read: 24

準備を整える ~ 6 章。探索対象の探索前の並び替えによって実行時間が線形対数時間や 2 次の実行時間に変わる。並び替えるは実際には線形対数時間より速く並美変えられる場合があるため、効率的なアプローチとなる。 ソートは最小の複雑性が、つまり下限ステップ数がわかっている問題。ソートアルゴリズムは分割統治アルゴリズムの例。分割して問題の複雑度を低減、部分も台を解決し、最後に統合して解を得る。 選択ソート。最小の要素を末尾に追加するか、最大の要素を先頭に追加する並び替え。挿入ソート。挿入したい要素より小さい要素の中で一番後ろに挿入する。挿入ソートは選択ソートより遅くなることはない。違いは自身のソート済みの計算結果を再利用しているかという点。 クイックソート。ある要素を基点に小さい要素と大きい要素にリストを分割し、小さくなったリストをソートして結合する。最善で線形対数時間、最悪で 2 次の実行時間となる。 マージソート。 2 つの部分リスをとソートしてから並行に走査して小さい要素から結合していく。バケットソート。要素をバケットに分類し其々の中でソートして結合する。実質最適。 カウンティングソート。リストの要素のサイズが限られていて配列のインデックスとして利用できる場合に限り使える。その場合に限ればマージソートより速い。 ソートで事前計算することによって再利用される限り実行時間を効率化できる。逆に事前計算の労力が無駄になる可能性がある場合は遅延評価で先延ばしすることもできる。 完全に主観だがデータ構造やアルゴリズムのある程度具体的な説明となると映画が題材であることが意味あるんかよくわからんな。とっつきやすさがあるわけでもないし。

2026-08-06, read count: 1, page: 107 ~ 126, pages read: 20

昼食をとる ~ 7 章。組み合わせで膨大な選択肢を持ち手に負えない(イントラクタブルな)問題と近似アルゴリズム。 指数実行時間のアルゴリズム。生成検査は解の候補の生成において組み合わせが爆発する。このような指数アルゴリズムでしか解けない問題は手に負えない(イントラクタブル)と呼ばれる。 NP 完全問題もイントラクタブルな問題。ナップサック問題や巡回セールスマン問題は NP 完全問題の 1 つ。 P=NP 問題。多項式時間で解けるクラス P の問題が、多項式時間で判定できるクラス NP の問題に等しいか。 現実的に計算できない問題の非効率を近似アルゴリズムが改善する。例えば貪欲アルゴリズムは最悪でも最適解の 50% 以内に収まる。 指数アルゴリズムの有効活用として暗号化がある。素因数分解は NP 完全問題かわかっていないが、実行時間は指数時間が最小とわかってる。問題を解く難しさで防御するのは、塀・柵・壁等と同じ原則とみなせる。 本書はなんか厳密な話じゃなく NP 完全≒指数実行時間を要するって単純化してるっぽいな。多項式時間≒現実的に扱える計算量、指数時間≒現実的に扱えない計算量で NP 完全が代表例、ってかんじの。 この章の内容はそのまま最適経路の本の内容とも重なるのでおさらい感ある。

2026-08-07, read count: 1, page: 127 ~ 142, pages read: 16

7 章 さらなる探求 ~ 8 章。言語がアルゴリズムの定義と実行を役割分担させる。文法は、言語を構成する文の外見や単語の順序(具象構文)だけでなく内部構造(抽象構文)も構成する。 計算機科学では、言語は意味を伝えるための正確で効果的な手段である。 言語でな何かを語るということはそこにモデルを作る必要がある。またモデルは型の定義につながる。 時間なく今日はここまで。

2026-08-08, read count: 1, page: 143 ~ 153, pages read: 11

8 章。言語の例として記譜法。楽譜は文でアルゴリズムの記述。演奏が計算で音楽家が計算機。 ギターのタブラチュア譜は五線譜よりより具象的で、五線譜は音程が記号インデックス的である点も含め恣意的な構文。 文法規則。終端記号と非終端記号。終端記号は変わらない意味を持ち、非終端記号は異なる値を取りうる。 文法はいくつかの規則で構成される。例えば非終端記号を終端記号に置き換える命令。 置き換えたあとも非終端記号が含まれる場合は文形式という。置き換えた非終端記号自身を含み終端しない文形式は再帰的であるという。 異なる言語の間での翻訳は抽象構文という中間表現を解することでうまくいく。抽象構文は文の構造を表し、具象構文は文の外見を表す。抽象構文は抽象構文機で構成される。 逆に具象構文から抽象構文を導くのは解析木を解する。 文を開始シンボルから解析する戦略はトップダウン解析、逆に規則の右辺から単一のルートを求めるのはボトムアップ解析。 構文木から具象構文に変換する仮定はプリティプリントと呼ばれる。 タブ譜の音符の長さが曖昧ってのはなんか違うような。大抵五線譜式の規則が導入されてるし。でも併記されてるしそういう側面はあるのかも。 その点に注目したことがなかった程度には五線譜やタブ譜の構文木を意識したことなかったので観点としては気づきを得たかもな。

2026-08-09, read count: 1, page: 154 ~ 166, pages read: 13

薬局からの折り返し電話 ~ 9 章。言語の意味が抽象構文を作る。文が 2 つ以上の意味を持つとき、それを曖昧であるという。 単語や記号が曖昧になりうるのを語彙的曖昧性(多義性)、文中の組み合わせであいまいになりうるのを文法的曖昧性(構造的曖昧性)と呼ぶ。 曖昧さは非決定性とは違う。非決定性は言語の機能で、曖昧さは言語の構文定義のバグ。 言語の表す意味については意味論(semantics)、その個々の文については意味(meaning)。その言語が示す意味すべてを集めたのが意味領域。 抽象構文が何を示す(表示する)かで意味づけするかを示すのが表示的意味論。 非終端記号の規則に基づく変換は、文の意味が抽象構文を介しシステマティックに構築される様子を示す。この様に構文規則から体系的に決まることを合成的と呼ぶ。 単純な楽譜は合成的だが、自然言語はたいてい非合成的。五線譜でもタイは小節をまたいで複数の小節をまとめて扱う規則で上書きする必要があるので非合成的。 表示的意味論は言語から与えられた意味を計算するアルゴリズムと言える。その文の意味を計算できる計算機のことをインタプリタ(解釈器)と呼ぶ。 表示的意味論で数学的対象云々が触れられてないからちょっと形式化とは距離がある浮いた感じがするな。別にわたしも理解してるわけじゃないけど。

2026-08-10, read count: 1, page: 167 ~ 180, pages read: 14

習慣の力 ~ 10 章。言語が違えば意味論も違うが、直接効果をもたらす操作、操作の順序・適用・繰り返しを体系化数制御構造という 2 つの命令で構成されるという性質は共有している。 ループはあるまとまった行動を何回か繰り返すこと。繰り返す行動はループの本体と呼ばれ、ループの本体を実行吸うことはループの反復と呼ばれる。 ループの本体は反復ごとに同じであり、変化が必要な場合は変数により実現される。 ループを抜け出す条件は終了条件と呼ばれ、それにより終了するループと終了しないループを区別できる。 ループは制御構造の 1 つ。他の主要な制御構造は、ステップのまとまりを一連の順序あるステップにまとめる逐次合成、複数のステップから条件に合う 1 つを選ぶ条件分岐がある。 制御構造を示す記法としてフローチャートがある。フローチャートは視覚言語である。 ループには repeat ループ、 while ループ、 for ループがある。 while ループは継続する条件を満たす限りループを続けるため、条件が成り立たなければ全く実行されないこともある。 for ループは反復回数が決まっている場合に使われる。 for ループは終了が保証されているが repeat ループと while ループは終了が保証されず永遠に動き続ける可能性がある。 なんとなく、記号論や意味論を概要に留めて説明を踏み込んでないから本書で読み解くのが難しいのであって、制御構造のようなそこまで抽象的でないテーマは読み解くのは容易いのかもしれんな。

2026-08-11, read count: 1, page: 181 ~ 198, pages read: 18

何もないところで止まる ~ 11 章。停止性問題。 ループは変数を介して世界≒状態にアクセスして終了条件を満たしループを終えるか決める。 ループの命令列を作り出すことを展開という。 ループが終ることを分析するアルゴリズムは作れない。停止性問題の非可解性。 はい・いいえで答えられる問題は決定問題とよばれ、決定可能・決定不能に分かれる。 入力に対する出力を問うのは関数問題、アルゴリズムで解けない問題は計算不能・計算可能に分けられる。 決定可能な問題の数は可算、決定不能な問題の数は非可算。可算無限と非可算無限。 難しいのもそうでないのも分け隔てなく広く取り扱ってるからの独特のリズム感がこの本はあるなとようやくわかってきたわ。

2026-08-12, read count: 1, page: 199 ~ 214, pages read: 16

これをもう一度読みなさい ~ 12 章。 再帰。自己相似性と自己参照という特性を持つ。 再帰とループはいずれも書き換えが可能な点は同じだが、データ定義にも使える点で再帰のほうが基礎的な特性を持つ。 再帰の終了条件は残りの要素がなくなった時。そのような要素のデータ構造での条件分岐はパターンマッチと呼ばれる。 再帰における不動点とは、変数を適用しても結果がもとと同一になる点。定義上同一とみなせる点。 再帰にはたくさんの分類がある。記述された再帰は再帰のアルゴリズム定義自体、展開された再帰は実行時に再帰構造に展開された計算。 有限の再帰と無限の再帰。再帰の中で再帰を引き起こさない点は既定と呼ばれ、有限の再帰に含まれる。 直接的な再帰と間接的な再帰では、直接的に自己参照するかという違いがある。 他にも、生成的再帰・構造的再帰、線形再帰、非線形再帰という区別もある。 図にビルって書いてるけどビフの誤記。広く浅くだとこうなるのかなとは思うが、本書で触れてる停止性や計算量に絡んでないのがちょっと物足りない気がした。 次に読むのは記号と再帰の本にしたいなという気が仕上がってきた。

2026-08-13, read count: 1, page: 215 ~ 238, pages read: 24

最新作 ~ 13 章。 再帰的なアルゴリズムの実行について。置換(書き換え)により再帰的な定義からトレースを組み立てる。 置換は局所的に行われるため全体の文脈は変わらない。 計算のトレースは基本的に中間結果や状態の一連のスナップショット。 インタプリタはアルゴリズムの実行時のスタックやコピーされた引数を追跡する。 再帰では呼び出し元に戻って計算を続ける必要があり、各バージョンの情報で管理するのにスタックが向く。 引数の値をパターンマッチで使われているパラメータの名前に関連付けるのを束縛という。 再帰の定義の中で一度だけ自己言及するのを線形再帰、複数回自己言及するのを非線形再帰と呼ぶ。 複数の自己言及があるからといって、計算機はそれらを並列に実行してもしなくてもよい。 理論の前にプログラミングで再帰に触れてる分、言葉を覚える的な流れ作業チックになってしまうよな。やる気の問題かも知れんが。

2026-08-14, read count: 1, page: 239 ~ 256, pages read: 18

夕食の時間 ~ 14 章。 計算機科学では特定の振る舞いをするものの種類を型と呼ぶ。型はアルゴリズムや計算の性質を述べつのに役立つ。 1 つは入力と出力、もう 1 つは型パラメータ。 1 つのパラメータで異なる型を記述できる多相をパラメータ多相と呼ぶ。 型付け規則では前提から規則に寄って結論を導くことで型の相互作用を予測できる。最も基本的な規則は適用規則で、関数の型と引数の型から結果の型を導く。 型付け規則を用いてアルゴリズム定義の間違い防ぎ正しく構築するのを型主導プログラミングと呼ぶことがある。 型付け規則の違反は型エラーと呼ばれ、型エラーがないことを型が正しいという。型が正しいことを調べるアルゴリズムは型チェッカーと呼ばれる。 動的型チェックはアルゴリズムの実行最中に型をチェックする。誤りが検知された場合にできることは計算を中止することくらい。 静的型チェックはアルゴリズムを実行せずに型をチェックする。実行を必要としないことで型チェクが 1 度で済むのも利点。 ただし動的型チェックの方が実行時にチェックできる分、値も含めより正確に型をチェックできる。 また正確な型の振る舞いを判定することは決定不能な問題であり近似的である。全ての分岐を調べる必要もあり、安全のために支払う対価といえる。 さほどハリー・ポッター詳しくなく親近感もわかないため普通の型の話として読んでる。本書の前提を満たしてないけど結果は導けてるみたいな、ちょうど本書で触れられた型付け規則の穴があるような話と同じだ。

2026-08-15, read count: 1, page: 257 ~ 276, pages read: 20

1 日の終わりに ~ 15 章、用語集、訳者あとがき、索引。 抽象化によりパターンが特定され、パラメータを通して状況に合わせ柔軟に適合でき、簡潔な形式で再利用可能になる。それはインタフェースを定義すること。 共通部分に注目し他の細部を無視するような汎化するのが抽象化(細部の抽象化)。 計算機科学では抽象化の結果を抽象的概念と呼び、抽象的概念の例はインスタンスと呼ぶ。 抽象的概念に名前がつけられパラメータを定義したものはインタフェースと呼ばれる。 抽象化のレベルの難しさについて。アルゴリズムをはじめ様々なものは関数抽象。 型をはじめとして計算で変換される抽象化はデータ抽象。 アルゴリズムの処理時間を線形・非線形に分類するのも抽象化。 チューリングマシンは計算機を抽象化した抽象機械、ラムダ計算はどんなアルゴリズム言語も単純化された計算に翻訳できる計算の抽象化。 チャーチ・チューリングのテーゼではこれらの表現力を超える計算はないとされる。 用語集と索引がよくまとまってるので振り返る際にメモより役に立ちそう。 本書はこれで終わり。感触としては多分やる気のある非 CS 読者なら楽しく読めたのではないかと思う。ここからより深いテーマは専門書に進むのがよいのだろう。 物語と計算機科学の概念の類似性を導入のフックとして物語置いてきぼりで進んでるような感じで、実質物語と絡んでない。 本書中の計算機科学の抽象的な概念の説明では踏み込まずに終えてるので、物語との関係もあってふわついた印象だった。後半だれてしまった。 不完全燃焼感あるし次は読みきれるかわからんが専門書読むぞ。

2026-08-16, read count: 1, page: 278 ~ 324, pages read: 47