L1: 基礎
コンピュータはどうやってプログラムを動かすのか
COMP論理ゲートから、プログラムが動く仕組みまで。NANDゲートだけで、あらゆる回路を組み立てられます。ゲートで作った加算器は、引き算にも使えます。リトルマンコンピュータは、その加算器の隣に百個の郵便受けを並べたもの。プログラムも数値も同じメモリに置かれ、プログラムカウンタが指す場所の内容を、コンピュータは命令として実行します。
インタラクティブな数学・理科レッスン (ノ◕ヮ◕)ノ*:・゚✧
コンピュータは言われたとおりのことを、良いアルゴリズムと悪いアルゴリズムの差を無視できなくなるほどの速さで実行します。ここでは両方を走らせ、その差が開いていくのを見ることができます。
単体のツールではなく、短い系列として。各ステップは次のステップに具体的なものを渡すので、順番に進める価値があります。
L1: 基礎
COMP論理ゲートから、プログラムが動く仕組みまで。NANDゲートだけで、あらゆる回路を組み立てられます。ゲートで作った加算器は、引き算にも使えます。リトルマンコンピュータは、その加算器の隣に百個の郵便受けを並べたもの。プログラムも数値も同じメモリに置かれ、プログラムカウンタが指す場所の内容を、コンピュータは命令として実行します。
L1: 基礎
COMPここに並ぶ暗号はどれも、文字そのものを隠す代わりに、別の何かを表に残してしまいます。換字式暗号なら文字の出現頻度が残り、キーワード暗号ならそれが列となって現れ、二度使い回されたワンタイムパッドなら空白の位置が漏れ出します。一切の手がかりを残さないのは、文面とまったく同じ長さを持つ無作為な鍵だけ。そうなると、その鍵をいかにして相手へ届けるかが最大の難問となります。最後の二つのページでは、誰の目にも触れる開かれた場所で、それを成し遂げる道筋を見ていきます。
L2: 中等
MATH誕生日問題は一見するとパーティーの余興のようですが、実は衝突について考察するための標準的な道具なのです。そして続く第2段階で、計算機科学者たちは別の名前で再びこの問題に出会うことになります。
L2: 中等
COMPここで扱うデータ構造は、どれもある問いにすばやく答えられる代わりに、別のところでコストがかかります。ブルームフィルタはキーをまったく保存しなくても、確実に含まれていないと判定できます。トライは、ハッシュ表では答えられない接頭辞の問いに答えます。ヒープでは最小のキーがいつでもわかりますが、それ以外に得られる情報はわずかです。最後のページでは、メモリからどのページを追い出すかを考えます。最善の選択には、未来のアクセスを知る必要があります。
L2: 中等
COMP動画エンコーダは単一のアルゴリズムではなく、順序の決まった 8 つの段です。その順序は恣意的ではありません。どの段も、直前の段が仕事を可能にしてくれたからこそ存在します。このツールはそのうちの 1 つを扱います。下の連鎖から残りの 7 つに移動できます。
L3: 学部
COMP一つの問題を構成する二つの側面。スタジオが直面する順に追っていきましょう。まずは、鍵が漏洩しても他の全員のライセンスは有効に保たなければならないという課題です。驚くべきことに、これに必要なヘッダーは、システムの規模がどれほど大きくなっても一切肥大化しません。そして、より困難な後半の課題。それが、誰の鍵であったかを突き止めることです。何人かの契約者が結託し、誰の名前も出ないよう特別に仕立て上げた複製から、それを特定せねばならないのです。
L3: 学部
COMP大規模言語モデルが単語を選ぶまさにその瞬間、内部を紐解く2つのツール。後者は文字通り前者の上で動作します。順位付けする候補は、前者が構築した語彙の項目だからです。
L3: 学部
COMP信号は回転する矢印の足し合わせです。そして、そこから現実的な方法で情報を読み取ろうとすれば、教科書の公式には書かれていない何らかの代償を伴います。有限の窓は、そこに収まりきらない波をすべてのビンににじませてしまいます。窓を短くすれば時間は正確に捉えられますが、音の高さは犠牲になります。平均をとる操作もまた、固有の形を持ったフィルターにほかなりません。そして最後のページは、これらすべての計算が実用的な時間で処理できる理由についてです。
L3: 学部
COMPアルゴリズムが正しく動くのには、言葉で説明できる理由があります。そして間違っているなら、小さなテストで見つかる原因がどこかにあります。ここでは各ページに、正しい実装と、いかにももっともらしい間違いを並べてみました。二分探索の16通りの書き方のうち14通りは破綻します。お釣りを計算する貪欲法は古いイギリスの硬貨では失敗しますが、アメリカの硬貨では決して間違えません。クラスカル法とプリム法の答えが一致するのには確かな理由があります。また、反転した一つのビットを直す符号は、二つの反転をかえって悪化させてしまいます。
L3: 学部
COMP紙の上で実行できる四つのエンコーダを、直前の方式には見えなかったものをそれぞれがどう捉えるかという順に並べています。四つ目は一切の圧縮を行いません。そしてそれこそが、一つ目がテキストに対してうまく機能する理由なのです。
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.