アルゴリズム — 流れ図を動かして確かめる
アルゴリズムはソフトウェアの設計図です。ここでは流れ図（フローチャート）で書かれた手順を、実際に1ステップずつ動かしながら確かめていきます。
見出し右の灰色の番号は、講義スライド Algorithm05012024.pptx（2024-10-22 版・全76枚）の該当ページです。原スライドの記述に誤りがあった箇所は、その場で訂正を示し、末尾の付録に一覧をまとめました。
再生バーのある図はすべて動きます。▶ 再生で自動、▶❘ で1コマずつ、シークバーをつまめば好きな場面へ前後に移動でき、速度も変えられます。流れ図のいま実行中の記号が緑に光り、変数の値が右の表に積み上がります。配列やデータは自由に変えられます。各章末には確認クイズがあり、上部の「理解度」に正解数が出ます。
さらに、この教材の各アルゴリズムには ▶ プログラミンで動かす ボタンがあります。 ブロックを組み合わせるプログラミンが、 そのアルゴリズムを組み上がった状態で開き、「▶ はじめる」で1ブロックずつ光りながら動きます。 一覧は プログラミンで動かす（一覧） にあります。
アルゴリズムとは原スライド p.4–6
コンピュータはハードウェアとソフトウェアでできています。アルゴリズムは、そのソフトウェアの設計図にあたるものです。
アルゴリズムとは、問題を解決するための処理手順を形式的に表したもの。ただし、処理が停止する必要がある。
「停止する必要がある」という条件は見落とされがちですが本質的です。答えが出ても止まらない手順はアルゴリズムとは呼びません。この章以降に出てくる繰り返しは、すべて「いつ終わるか」がはっきりしています。
変数と配列
変数は記憶装置の上に作られた箱です。箱には名前（変数名）がついていて、そこに値を入れることを 変数 ← 値 と書きます。配列は、その箱を並べて番号（添字）で呼べるようにしたものです。
流れ図の記号原スライド p.7–9
流れ図の記号は JIS X 0121:1986（日本産業規格）で決まっています。形そのものに意味があるので、形を見れば何をする箇所かが分かります。
3つの制御構造原スライド p.10–20
どんなに複雑なアルゴリズムも、順次・分岐・繰り返しの3つの組み合わせだけで書けます。
| 構造 | 英語 | 意味 |
|---|---|---|
| 順次 | sequence（連続） | 1つひとつ順番に処理する |
| 分岐 | branch / selection（選択） | 条件によって判断し、処理が分かれる |
| 繰り返し | iteration（反復） | 条件によって判断し、処理を繰り返す |
条件判断と論理値
判断のひし形が返す値は True（真・成立する） か False（偽・成立しない） の2つだけです。複数の条件を組み合わせるときは、次の真理表に従います。
確認クイズ 分岐（選択）構造の説明として正しいものはどれですか？
変数トレース原スライド p.18–23
流れ図が正しいかどうかを確かめる方法が変数トレースです。記号を1つ通るたびに、変数の値を表に書き出していきます。
飴玉を5個食べる流れ図を、①〜④の番号どおりにたどります。1ステップずつ進めて、カウンタがどう変わるか見てください。
同じ繰り返しは、ループ端記号を使うと3行で書けます。繰り返し指定は
＜変数名＞：＜初期値＞，＜増分値＞，＜最終値＞ の順です。
たとえば カウンタ：1, 1, 5 は「カウンタを1から5まで1ずつ増やしながら繰り返す」という意味になります。
1からNまでの総和原スライド p.25–27
整数 N を入力し、1 から N までの総和を求めます。繰り返しの基本形です。
総和は S = N(N+1)2 という公式でも求まります。流れ図は N 回繰り返しますが、公式なら1回の計算で済みます。同じ答えを出すアルゴリズムでも手数が違う — これが第15章の計算量の話につながります。
原スライドは p.25 で S ← S + i、p.26 で S = S + i と書き分けられています。代入は ←、等しいかの比較は = と使い分けるのが流れ図の作法なので、p.26 も ← に統一するのが正しい書き方です。
フィボナッチ数列原スライド p.28–29
直前の2項を足して次の項を作る数列です。変数を3つ使って値をずらしていくのが要点です。
隣り合う2項の比 fibn / fibn−1 は、項を進めるほど 1.6180339…（黄金比 φ）に近づきます。上の表の右端の列で確かめられます。
最大公約数と最小公倍数原スライド p.30–35
同じ答えを出す2つのアルゴリズムを比べます。素朴な方法と賢い方法で、手数がどれだけ違うかを体感してください。
方法1：2から順に割ってみる（試し割り）
2つの自然数 m, n を 2 から順に割っていき、両方とも割り切れた数を覚えておきます。小さいほうの数まで調べ終わったとき、最後に覚えた数が最大公約数です。
方法2：ユークリッドの互除法
大きいほうを小さいほうで割った余りに置き換えることを、余りが 0 になるまで繰り返します。紀元前300年ごろの『原論』に載っている、現存する最古のアルゴリズムのひとつです。
試し割り
ユークリッドの互除法
線形探索と2分探索原スライド p.36–41
多くのデータから目的の値を探すことを探索といいます。前から順に見ていく方法と、半分に切っていく方法を比べます。
データは昇順に並んでいるものとします（2分探索には並んでいることが必要です）。探したい値 X を選んで、両方を走らせてください。
線形探索 — 前から順に
2分探索 — 範囲を半分ずつに
配列の添字は [0] から始まります（p.36・p.38 の図もそうなっています）。i ← 1 で始めると先頭の Array[0] を一度も見ないまま終わるため、先頭にある値は絶対に見つかりません。上のトグルを「i ← 1（原スライド）」にして X = 1 を探すと、実際に「見つかりません」と表示されます。
なお、原スライド p.40（X = 25）と p.41（X = 10）のトレース図は k = 4 → Array[4] = 12 から始まっており、こちらは i ← 0 で計算されています。流れ図の側の書き間違いと判断できます。
2分探索は毎回 k ← ⌊(i+j)/2⌋ で中央を見て、X が中央より小さければ右半分を捨て（j ← k−1）、大きければ左半分を捨てます（i ← k+1）。1回の比較で候補が半分になるのが強みです。
確認クイズ 昇順に並んだ 1000 個のデータから2分探索で目的の値を探すとき、最悪でおよそ何回の比較で「見つかった／無い」が分かりますか？
バブルソート原スライド p.42–49
多くのデータを並べ替えることをソートといいます。バブルソートは、隣り合う2つを比べて順番が逆なら交換するという単純な方法です。
1巡するといちばん大きい値が右端に確定します（泡が浮くように見えるのでバブル）。2巡目は右端を除いた範囲、3巡目はさらに1つ手前まで、と範囲が狭まっていきます。
流れ図
① 判断の書き方が紛らわしい。原スライドの判断は Array[j] ＜ Array[j+1] ？ で、False のときに交換へ進みます。結果として昇順に並ぶので間違いではありませんが、「小さいか？」と聞いて「いいえ」なら交換する、という二重否定になっています。上のコードのように Array[j] > Array[j+1] ？ を True で交換と書けば素直です。
② 改良版（p.49）の繰り返し範囲が1つ多い。j ： 0, 1, N−i と書かれていますが、この指定だと i = 1 のとき j は N−1 まで動き、Array[j+1] = Array[N] という存在しない要素を読んでしまいます（配列外参照）。正しくは j ： 0, 1, N−i−1 です。基本版（p.48）の N−2 は正しいので、改良の際に添字がずれたものと思われます。
改良版では、1巡してもまったく交換が起きなければ、すでに整列済みと分かるので途中で打ち切れます。上の「改良」に切り替えて、すでに並んでいるデータで試すと効果が分かります。
確認クイズ N 個の配列で、改良版の内側ループを j ： 0, 1, N−i と書いてしまうと（正しくは N−i−1）、i = 1 のとき何が起きますか？
最小法（選択ソート）原スライド p.50–53
残っている中からいちばん小さい値を探して先頭に持ってくる、を繰り返す方法です。一般には選択ソートと呼ばれます。
バブルソートが「隣どうしを何度も交換する」のに対し、最小法は1巡につき交換は1回だけです。比較の回数は同じでも、交換の回数が大きく減ります。
クイックソート原スライド p.54–60
基準の値（ピボット）を1つ選び、それより小さい組と大きい組に分ける。分けた組それぞれに同じ手続きをもう一度呼び出す — これが再帰呼出しです。
手続きの定義の中で自分自身を呼び出すことを再帰呼出し（recursive call）といいます。問題を小さくして自分に投げ直すので、書く量は少ないのに強力です。
呼び出しの記録
1回の分割で、ピボットより小さい組と大きい組にざっくり半分ずつ分かれます。半分にする操作は log2n 回で終わり、各段で全体を1回ずつ見るので、平均 O(n log n)。バブルソートの O(n²) より圧倒的に速くなります（第15章）。
確認クイズ クイックソートが平均して速い（O(n log n)）のは、なぜですか？
データ構造原スライド p.61–64
多くの値を扱うときは、値の並べ方・つなぎ方そのものを設計します。それがデータ構造です。
リストの連結
リストを [ 34, 76, 88, 2 ] のように書きます。2つのリストをつなぐ操作を連結といい、@ で表します。
スタックとキューこの Web 版で追加した発展
データをためて、順に取り出すときの2つの基本的な決まりです。同じ順に入れても、取り出す順番が逆になります。
| 名前 | 入れる／出す | 取り出す順 | 身のまわりの例 |
|---|---|---|---|
| スタック stack・積み重ね |
push（上に積む）／ pop（上から取る） | 後入れ先出し LIFO（Last In, First Out） |
皿の山、ブラウザの「戻る」、机に積んだ本 |
| キュー queue・待ち行列 |
enqueue（後ろに並ぶ）／ dequeue（先頭から出る） | 先入れ先出し FIFO（First In, First Out） |
レジの行列、印刷の待ち順、順番待ちの受付 |
スタック LIFO・後入れ先出し
キュー FIFO・先入れ先出し
関数の再帰呼出し（第11章クイックソートや第14章ハノイの塔）は、呼び出しをスタックに積み上げて、戻るときに上から下ろしています。上の「呼び出しの記録」でインデントが深くなるのが、積み上がっていくスタックの様子です。いっぽう印刷の待ち行列やネットワークのパケット処理はキューで順番を守ります。
確認クイズ スタックに 1, 2, 3 の順で push したあと、3回 pop すると、出てくる順番はどれですか？
ハノイの塔原スライド p.65–71
再帰呼出しの威力がいちばん分かりやすい例です。3行の手続きで、何十手もの正しい手順が生成されます。
- 棒 ① にある N 個の円盤を、棒 ③ に移す
- 一度に動かせる円盤は1つだけ
- 小さい円盤の上に大きい円盤を載せてはいけない
- ①②③以外の場所に円盤を置いてはいけない
手順（出力例）
円盤が1枚増えるたびに手数はほぼ2倍になります。N = 8 で 255 手、N = 64 なら約1844京手。1秒に1手動かしても約5800億年かかります（伝説どおり、世界が終わるまで終わりません）。
計算量原スライド p.72–75
アルゴリズムを考えるとき、効率を見積もることは重要です。データ数が増えたときに、繰り返し回数がどう増えるか — これを計算量といいます。
| オーダー | 意味 | データが2倍になると | 例 |
|---|---|---|---|
| O(1) | データ数によらず一定 | 変わらない | 配列の添字アクセス |
| O(log n) | log n に比例 | 1回増えるだけ | 2分探索 |
| O(n) | n に比例 | 2倍 | 線形探索、総和 |
| O(n log n) | n log n に比例 | 2倍と少し | クイックソート（平均） |
| O(n²) | n² に比例 | 4倍 | バブルソート、最小法 |
「2分探索は、要素が 2n 個（2倍）になったとすると、繰り返しの回数は、平均して1回増えるだけである」とありますが、log₂(2n) = log₂n + 1 なので、平均ではなく（最悪の場合でも）ちょうど1回増えるだけです。「平均して」は不要です。
100万件のデータで O(n²) のアルゴリズムを走らせると1兆回の計算になり、現実的な時間で終わりません。どのアルゴリズムを選ぶかが、そもそも計算できるかどうかを決めます。機械学習ライブラリが内部でどんな計算量の手法を使っているかを気にするのは、このためです。
確認クイズ 計算量が O(n²) のアルゴリズムで、データ数を2倍にすると、計算の手数はおよそ何倍になりますか？
原スライドからの訂正一覧Algorithm05012024.pptx / 2024-10-22 版
Web 化にあたって全76枚の流れ図・数値・トレースを検証しました（図形と接続線を復元して分岐の向きまで確認しています）。見つかった誤りと訂正内容です。
| 頁 | 原スライドの記述 | 訂正 | 影響 |
|---|---|---|---|
| 39 | 2分探索の初期化 i ← 1, j ← N−1 |
i ← 0, j ← N−1 添字は [0] から。p.40・p.41 のトレース図は i = 0 で計算されている |
重大 先頭の要素が絶対に見つからない |
| 49 | 改良版バブルソートの内側ループ j ： 0, 1, N−i |
j ： 0, 1, N−i−1 基本版（p.48）の N−2 は正しい |
重大 Array[N] を読む配列外参照 |
| 55 | 「p: ピポット」 | 「p: ピボット（pivot）」 | 誤字 |
| 48, 49 | Array[j] ＜ Array[j+1] ？ → False のときに交換へ進む |
Array[j] ＞ Array[j+1] ？ → True のときに交換 |
紛らわしい 結果は正しいが二重否定 |
| 73 | 2分探索は要素が2倍になると繰り返し回数が平均して1回増える | log₂(2n) = log₂n + 1 なので（最悪でも）ちょうど1回増える | 表現 |
| 26 | S = S + i, i = i + 1 | S ← S + i, i ← i + 1 p.25 は ← で書かれており不統一。= は比較に使う |
表記 |
| 32 | M Mod i = 0 かつ n Mod i = 0 | m Mod i = 0 かつ n Mod i = 0 変数は小文字の m。大文字 M は別の変数に見える |
表記 |
| 30 | 最大公約数の説明で変数が O, P | p.31 以降と揃えて m, n。とくに O は数字の 0 と紛らわしい | 表記 |
| 42–46 | 「２つづつ取り出して」 | 「２つずつ取り出して」 | 送り仮名 |
| 66, 68 | 「大きな円盤を載せる」「乗せる」が混在 | どちらかに統一（載せるが一般的） | 表記 |
検証して「正しかった」もの
- p.34 ユークリッドの互除法：K > Y なら交換、K = 0 まで r ← Y mod K；Y ← K；K ← r、最後に Y を表示。完全に正しい流れ図です
- p.27 総和のトレース答え：N = 4 のとき S は 1 → 3 → 6 → 10、i は 2 → 3 → 4 → 5。答えの数値はすべて合っています
- p.37 線形探索：i ← 0 から始まり i ≧ N で打ち切り。正しい
- p.51 最小法：i ： 0,1,N−2、k ： i+1,1,N−1 の範囲指定は正しい
- p.58–60 クイックソートのトレース：ピボット 56 から始まる12個の分割過程を1手ずつ追跡しましたが、すべて正しい
- p.70 ハノイの塔の出力例：Hanoi(3,1,3,2) の7手、順番も移動先もすべて正しい。移動回数 2N − 1 も正しい
- p.74 バブルソートは要素2倍で 2² = 4倍：正しい
この Web 版で加えたもの
- 流れ図とトレース表の連動（第4・5・6章）— いま実行中の記号が光り、変数の値が1行ずつ積み上がります
- 再生プレイヤ（全アニメ共通）— 再生／一時停止・1コマ送り／戻し・シークバーで任意の位置へ・速度調整。動画のように前後に行き来しながら1手ずつ確かめられます
- 章末クイズ（全6問）— 各章の要点を選択式で確認でき、上部の「理解度」に正解数が出ます
- スタックとキュー（第13章・新規）— 同じ順に入れて取り出す順が逆になること（LIFO / FIFO）を、実際に積む・並ぶで確かめられます
- バグの再現（第8章）— p.39 の i ← 1 をトグルで切り替えて、先頭の要素が見つからない様子を実際に確かめられます
- 試し割りと互除法の手数比較（第7章）— 同じ答えでも繰り返し回数が桁違いであること
- 実測の計算量（第15章）— 理論値のグラフだけでなく、その場でアルゴリズムを走らせて比較回数を数えています
- 最小法とバブルソートの交換回数の差、クイックソートの再帰の深さと呼び出し記録
第5回のまとめ原スライド p.76
- アルゴリズムとは — 問題を解決する処理手順。停止することが条件
- 流れ図（flowchart） — JIS X 0121:1986。順次・分岐・繰り返しの3つで書ける
- さまざまなアルゴリズム — 総和、フィボナッチ、最大公約数、ハノイの塔
- 探索と並べ替え — 線形探索・2分探索、バブルソート・最小法・クイックソート
- 計算量 — O(n), O(log n), O(n log n), O(n²)