L1: 基礎
コンピュータはどうやってプログラムを動かすのか
COMP論理ゲートから、プログラムが動く仕組みまで。NANDゲートだけで、あらゆる回路を組み立てられます。ゲートで作った加算器は、引き算にも使えます。リトルマンコンピュータは、その加算器の隣に百個の郵便受けを並べたもの。プログラムも数値も同じメモリに置かれ、プログラムカウンタが指す場所の内容を、コンピュータは命令として実行します。
コンピューティング
この分野のすべてのツール
Algorithms & Data Structures
- BFS vs DFS ビジュアライザー
- BST / AVL木ビジュアライザー
- ヴィジュネル暗号：鍵の長さを突き止め、解読する
- グラフ彩色エクスプローラー
- ソートアルゴリズム対決
- ダイクストラ法による最短経路
- ディフィー・ヘルマン：公の場で共有する秘密
- トライ木：接頭辞をたどって学ぶ
- ハッシュテーブル可視化ツール
- ブルームフィルタ：「確実にない」と「たぶんある」
- ページ置換：FIFO・LRU・最適置換
- レーベンシュタイン距離ビジュアライザー
- ワンタイムパッド：一度なら破れず、二度で破れる
- 両替問題：貪欲法と最適解
- 二分ヒープ：配列でつくる優先度付きキュー
- 二分探索：四つの選択、十六通りのループ
- 再帰木エクスプローラー
- 最小全域木：クラスカル法とプリム法
- 単換字暗号：文字を数えて26!通りの鍵を破る
- 経路探索アルゴリズム・ビジュアライザー
- 計算量オーダー(Big-O)エクスプローラー
Information Theory & Encoding
Signal & Media Processing
Automata & Cryptography
Demos & Utilities
章
計算機とアルゴリズム
L2: 中等
データ構造が得意なこと
COMPここで扱うデータ構造は、どれもある問いにすばやく答えられる代わりに、別のところでコストがかかります。ブルームフィルタはキーをまったく保存しなくても、確実に含まれていないと判定できます。トライは、ハッシュ表では答えられない接頭辞の問いに答えます。ヒープでは最小のキーがいつでもわかりますが、それ以外に得られる情報はわずかです。最後のページでは、メモリからどのページを追い出すかを考えます。最善の選択には、未来のアクセスを知る必要があります。
L3: 学部
アルゴリズムが正しい理由
COMPアルゴリズムが正しく動くのには、言葉で説明できる理由があります。そして間違っているなら、小さなテストで見つかる原因がどこかにあります。ここでは各ページに、正しい実装と、いかにももっともらしい間違いを並べてみました。二分探索の16通りの書き方のうち14通りは破綻します。お釣りを計算する貪欲法は古いイギリスの硬貨では失敗しますが、アメリカの硬貨では決して間違えません。クラスカル法とプリム法の答えが一致するのには確かな理由があります。また、反転した一つのビットを直す符号は、二つの反転をかえって悪化させてしまいます。
セキュリティ
L1: 基礎
暗号はいかにして破られるか
COMPここに並ぶ暗号はどれも、文字そのものを隠す代わりに、別の何かを表に残してしまいます。換字式暗号なら文字の出現頻度が残り、キーワード暗号ならそれが列となって現れ、二度使い回されたワンタイムパッドなら空白の位置が漏れ出します。一切の手がかりを残さないのは、文面とまったく同じ長さを持つ無作為な鍵だけ。そうなると、その鍵をいかにして相手へ届けるかが最大の難問となります。最後の二つのページでは、誰の目にも触れる開かれた場所で、それを成し遂げる道筋を見ていきます。
L3: 学部
映像配信の保護：デバイスを無効化し、出所を突き止める
COMP一つの問題を構成する二つの側面。スタジオが直面する順に追っていきましょう。まずは、鍵が漏洩しても他の全員のライセンスは有効に保たなければならないという課題です。驚くべきことに、これに必要なヘッダーは、システムの規模がどれほど大きくなっても一切肥大化しません。そして、より困難な後半の課題。それが、誰の鍵であったかを突き止めることです。何人かの契約者が結託し、誰の名前も出ないよう特別に仕立て上げた複製から、それを特定せねばならないのです。
信号と情報
L2: 中等
動画が符号化されるまで
COMP動画エンコーダは単一のアルゴリズムではなく、順序の決まった 8 つの段です。その順序は恣意的ではありません。どの段も、直前の段が仕事を可能にしてくれたからこそ存在します。このツールはそのうちの 1 つを扱います。下の連鎖から残りの 7 つに移動できます。
L3: 学部
LLM はどう次の単語を選ぶか
COMP大規模言語モデルが単語を選ぶまさにその瞬間、内部を紐解く2つのツール。後者は文字通り前者の上で動作します。順位付けする候補は、前者が構築した語彙の項目だからです。
L3: 学部
フーリエ変換の実際
COMP信号は回転する矢印の足し合わせです。そして、そこから現実的な方法で情報を読み取ろうとすれば、教科書の公式には書かれていない何らかの代償を伴います。有限の窓は、そこに収まりきらない波をすべてのビンににじませてしまいます。窓を短くすれば時間は正確に捉えられますが、音の高さは犠牲になります。平均をとる操作もまた、固有の形を持ったフィルターにほかなりません。そして最後のページは、これらすべての計算が実用的な時間で処理できる理由についてです。
L3: 学部
手作業によるデータ圧縮
COMP紙の上で実行できる四つのエンコーダを、直前の方式には見えなかったものをそれぞれがどう捉えるかという順に並べています。四つ目は一切の圧縮を行いません。そしてそれこそが、一つ目がテキストに対してうまく機能する理由なのです。
証明・数え上げ・ゲーム
L2: 中等
2つの値が衝突するとき
MATH誕生日問題は一見するとパーティーの余興のようですが、実は衝突について考察するための標準的な道具なのです。そして続く第2段階で、計算機科学者たちは別の名前で再びこの問題に出会うことになります。
全プロセスの詳細解説
- 読み出し順によって、メモリからの転送量はどれだけ増えるか
- 再帰はどこまで深くできる？
- 測定値を補正し、その必要性をなくす
- ガウスのもう一つの例：ジュノー、36の値
- 64ビット語にはパリティビットがいくつ必要か
- 1台のライセンスサーバーで決勝戦を捌けるか？
- この画像の大きさは？
- 正方形に置く二つの分岐点
- パッドを共有する二つのメッセージから5文字を解読する
- ピアノの最低音
- 計算が終わり、読解が始まるとき
- 2 × 99には801回、99 × 2には25回の命令実行が必要なのはなぜか
- どこまで共有できれば、トライ木のほうが小さくなる？
- キャロルの暗号カードの主張は正しかったのか？
- 1:9のパターンが過剰暗号化を引き起こす最大値
- 1と5に加える第三の額面は？
- 10ステップにおける2つのウォーカーの広がり
- チェッカーボードのテスト画像のピクセル (31, 3) における勾配強度
- 状態数をどれだけ与えても、有限機械が0と1の数を対応付けられない理由
- NANDゲートのみで構築した半加算器と、なぜ5個が最小個数なのか
- 壁から3.0 mの55インチと65インチの4Kテレビ
- 180語における0.453のターゲット不一致ギャップ
- 逆順の64要素におけるバブルソートの正確な交換回数の予測
- 8ビットに変換された42に対する2つの個別のオーバーフローフラグ
これらのツールから生まれた記事
-
Switching off a thousand devices can cost less than switching off one
A disc cannot ask who is playing it, so a revocation has to be broadcast to everybody at once. The scheme every Blu-ray uses prices that broadcast by how the broken devices are arranged in the key tree, and the size of the audience does not appear in the bound at all.
-
Half of written Japanese is 158 characters. The next 45% costs a thousand more.
Word frequencies follow the same lopsided law in every language anyone has checked. It makes the first stage of learning feel miraculous and the last stage feel impossible, and both feelings are the same curve.
-
Why sorting cannot get faster
Sorting a hundred items takes at least 525 comparisons and no future algorithm will improve on it. The proof does not examine any algorithm at all: it counts how many arrangements exist and how much a yes-or-no question can possibly tell you.
-
Why a language model struggles to count the letters in a word
It never sees the letters. Text is split into tokens before the model reads anything, and a great many puzzling failures follow directly from where the splits land.
-
No compressor can shrink every file, and the proof takes one paragraph
Lossless compression works by exploiting predictability, so a file with none of it cannot be made smaller at all. The proof is counting: nine things will not fit into eight boxes.