コンピュータサイエンス基礎 50 本ノック

学部50 問。全問無料です。

対象読者: 本テーマ第 1〜3 章の内容（論理回路・加算器、CPU と RISC-V の符号化、OS のスケジューリング・ページング、言語の型付け）を一通り読んだ学部生。手計算の力は仮定しますが、専門用語は各問の確認から入ります。

テーマの目次へ（コンピュータサイエンス基礎）

執筆: Claude Code（Sonnet 5.5）・監査 3 回（Claude Code）・最終 2026-10-12

読み込んでいます…

この冊について（出典・構成・使う定理）

主な参考文献

• D. A. Patterson, J. L. Hennessy, Computer Organization and Design, RISC-V Edition
• R. H. Arpaci-Dusseau, A. C. Arpaci-Dusseau, Operating Systems - Three Easy Pieces
• A. Silberschatz, P. B. Galvin, G. Gagne, Operating System Concepts
• B. C. Pierce, Types and Programming Languages

問題はすべて Rikai の書き下ろしです。参考文献の演習や本文は転載していません。

構成

• 1〜9: ブール関数と論理回路・加算器
• 10〜17: クロック・CPU・命令セット
• 18〜24: 特権モード・プロセス・スケジューリング
• 25〜32: ページングと仮想記憶
• 33〜35: 相互排除とデッドロック
• 36〜41: 小さな言語の簡約
• 42〜46: 型付けと型健全性
• 47〜50: 型推論・部分型・パラダイム

形式: 単一選択 17・複数選択 8・○× 5・数値 8・並べ替え 4・誤り探し 4・記述 4。難易度 ★〜★★★★: 11 / 26 / 13 / 0。

この冊で使う定義・定理（52）

• 系 2.4 NAND の関数完全性 コンピュータアーキテクチャとCPUの構造：トランジスタから RISC-V まで → 3, 7 番
• 定義 2.1 ブール関数 コンピュータアーキテクチャとCPUの構造：トランジスタから RISC-V まで → 1, 2, 8 番
• 定義 4.1 全加算器と桁上げ伝播加算器 コンピュータアーキテクチャとCPUの構造：トランジスタから RISC-V まで → 5, 6 番
• 定義 8.1 命令セットアーキテクチャ（ISA） コンピュータアーキテクチャとCPUの構造：トランジスタから RISC-V まで → 12, 13, 14, 15 番
• 定義 5.1 同期式順序回路とタイミングパラメータ コンピュータアーキテクチャとCPUの構造：トランジスタから RISC-V まで → 10, 11 番
• 定義 6.1 記憶プログラム方式（フォン・ノイマン型アーキテクチャ） コンピュータアーキテクチャとCPUの構造：トランジスタから RISC-V まで → 12, 17 番
• 例 7.1 add 命令が 1 個実行されるまで コンピュータアーキテクチャとCPUの構造：トランジスタから RISC-V まで → 13 番
• 例 8.2 add x5, x6, x7 を 32 ビットに符号化する コンピュータアーキテクチャとCPUの構造：トランジスタから RISC-V まで → 14 番
• 演習 9.4 コンピュータアーキテクチャとCPUの構造：トランジスタから RISC-V まで → 14 番
• 演習 9.1 コンピュータアーキテクチャとCPUの構造：トランジスタから RISC-V まで → 3 番
• 命題 4.4 桁上げ先読みと接頭辞計算 コンピュータアーキテクチャとCPUの構造：トランジスタから RISC-V まで → 6 番
• 命題 5.2 タイミング制約と最高動作周波数 コンピュータアーキテクチャとCPUの構造：トランジスタから RISC-V まで → 10, 11, 16 番
• 命題 3.1 CMOS の消費エネルギー コンピュータアーキテクチャとCPUの構造：トランジスタから RISC-V まで → 9 番
• 命題 2.2 ブール関数の個数 コンピュータアーキテクチャとCPUの構造：トランジスタから RISC-V まで → 1, 2 番
• 命題 7.2 パイプライン化による速度向上 コンピュータアーキテクチャとCPUの構造：トランジスタから RISC-V まで → 16 番
• 定理 2.3 加法標準形と AND・OR・NOT の完全性 コンピュータアーキテクチャとCPUの構造：トランジスタから RISC-V まで → 3, 4, 7, 8 番
• 定理 4.2 桁上げ伝播加算器の正しさ コンピュータアーキテクチャとCPUの構造：トランジスタから RISC-V まで → 5 番
• 定義 3.2 コンテキストスイッチ OS の役割：抽象化・スケジューリング・仮想記憶はなぜ必要か → 20 番
• 定義 6.2 デッドロック OS の役割：抽象化・スケジューリング・仮想記憶はなぜ必要か → 34, 35 番
• 定義 5.1 ページングによるアドレス変換 OS の役割：抽象化・スケジューリング・仮想記憶はなぜ必要か → 25, 26, 27, 32 番
• 定義 2.1 特権モードとユーザモード OS の役割：抽象化・スケジューリング・仮想記憶はなぜ必要か → 18, 19 番
• 定義 2.2 システムコール OS の役割：抽象化・スケジューリング・仮想記憶はなぜ必要か → 19 番
• 例 5.2 アドレス変換を最後まで計算する OS の役割：抽象化・スケジューリング・仮想記憶はなぜ必要か → 26 番
• 例 5.7 Belady の異常：FIFO はメモリを増やすと遅くなることがある OS の役割：抽象化・スケジューリング・仮想記憶はなぜ必要か → 29, 30, 31 番
• 例 4.4 3 方式の平均待ち時間と応答時間 OS の役割：抽象化・スケジューリング・仮想記憶はなぜ必要か → 21, 22 番
• 演習 7.4 OS の役割：抽象化・スケジューリング・仮想記憶はなぜ必要か → 33, 35 番
• 補題 6.3 OS の役割：抽象化・スケジューリング・仮想記憶はなぜ必要か → 34 番
• 命題 5.3 OS の役割：抽象化・スケジューリング・仮想記憶はなぜ必要か → 27 番
• 命題 4.3 OS の役割：抽象化・スケジューリング・仮想記憶はなぜ必要か → 20, 22, 23 番
• 命題 5.5 OS の役割：抽象化・スケジューリング・仮想記憶はなぜ必要か → 28, 32 番
• 注意 4.2 OS の役割：抽象化・スケジューリング・仮想記憶はなぜ必要か → 23 番
• 定理 6.4 デッドロックの 4 必要条件（Coffman 条件） OS の役割：抽象化・スケジューリング・仮想記憶はなぜ必要か → 33, 34, 35 番
• 定理 5.8 LRU はスタックアルゴリズムであり Belady の異常を起こさない OS の役割：抽象化・スケジューリング・仮想記憶はなぜ必要か → 29, 30, 31 番
• 定理 4.1 最短ジョブ優先の最適性 OS の役割：抽象化・スケジューリング・仮想記憶はなぜ必要か → 21, 23, 24 番
• 系 5.5 型健全性 プログラミング言語論：機械語から型システムとパラダイムまで → 43, 44, 46 番
• 定義 3.1 翻訳器と解釈器 プログラミング言語論：機械語から型システムとパラダイムまで → 49 番
• 定義 4.1 言語 L の構文と簡約関係 プログラミング言語論：機械語から型システムとパラダイムまで → 36, 37, 38, 39, 40, 46 番
• 定義 6.3 参照透過性 プログラミング言語論：機械語から型システムとパラダイムまで → 49 番
• 定義 6.6 部分型と包摂規則 プログラミング言語論：機械語から型システムとパラダイムまで → 47, 50 番
• 定義 5.1 言語 L の型付け関係 プログラミング言語論：機械語から型システムとパラダイムまで → 42, 43, 44, 45 番
• 例 6.8 共変にすると壊れる：Java の配列 プログラミング言語論：機械語から型システムとパラダイムまで → 50 番
• 例 5.7 型推論を最後まで計算する プログラミング言語論：機械語から型システムとパラダイムまで → 48 番
• 補題 4.3 値の基本性質 プログラミング言語論：機械語から型システムとパラダイムまで → 36, 37, 38, 40 番
• 命題 6.4 共通部分式除去の健全性 プログラミング言語論：機械語から型システムとパラダイムまで → 49 番
• 命題 6.7 関数型の変性 プログラミング言語論：機械語から型システムとパラダイムまで → 47, 50 番
• 注意 6.2 プログラミング言語論：機械語から型システムとパラダイムまで → 41 番
• 注意 3.2 プログラミング言語論：機械語から型システムとパラダイムまで → 49 番
• 定理 6.1 Church–Rosser の定理（合流性） プログラミング言語論：機械語から型システムとパラダイムまで → 41 番
• 定理 4.4 簡約の決定性 プログラミング言語論：機械語から型システムとパラダイムまで → 38, 39, 40, 41 番
• 定理 5.6 健全な静的検査の不完全性 プログラミング言語論：機械語から型システムとパラダイムまで → 43 番
• 定理 5.4 保存定理 プログラミング言語論：機械語から型システムとパラダイムまで → 44, 46 番
• 定理 5.3 進行定理 プログラミング言語論：機械語から型システムとパラダイムまで → 44, 46 番