CS基礎を固める

プログラムの実行からOS・計算理論まで学ぶ

コードの実行、メモリ、計算量、CPUから学び始めます。データ構造、OS、型とコンパイラを経て、計算できる問題の範囲まで扱います。

プログラミング経験があり、CSを基礎から整理したい方

同じ処理なのに、どうして速さが変わるのか?

学習範囲と終了地点

このコースの主教材はすべて公開済みです。下の順番で最後まで学習できます。

ステップ
22
主教材
22本
確認問題
60問

このコースで説明できるようになること

  • 配列の読み方、データ構造、アルゴリズムの選択によって処理時間が変わる理由を説明する。
  • プログラムの実行とOSの役割を説明し、型・コンパイラ・計算理論の基礎を使ってコードの性質を考える。

最後の主教材:計算可能性・還元・PとNP

各ステップの主教材を読了にし、確認問題がある場合は全問に正解すると完了です。補足記事と実験は任意です。

最後のステップを見る ↓

22ステップ中0ステップ完了

学習を始める →

コースの内容を実装で確かめる

実験で確かめた規則を短い関数にし、テストで動きを確かめます。

学ぶ順番

  1. 1番目これから

    ソースコードから実行中のプログラムまで

    学習目標:ソースコードがコンパイラ・インタプリタ・ランタイムを経て実行されるまでの境界を説明できる。

    主教材:ソースコードから実行中のプログラムまで →

  2. 2番目これから

    値・型・制御構造・関数・モジュール

    学習目標:値、型、式、条件分岐、反復を追跡し、プログラムの状態変化を説明できる。

    主教材:値・型・制御構造・関数・モジュール →

    図鑑で仕組みを補う
  3. 3番目これから

    命題論理・述語論理と証明

    学習目標:命題、論理演算、量化記号を用いて自然言語の主張を形式化し、推論規則がなぜ妥当か説明できる。

    主教材:命題論理・述語論理と証明 →

  4. 4番目これから

    メモリ・ポインタ・参照・ライフタイム

    学習目標:スタック、ヒープ、アドレス、ポインタ、参照を用いて実行中のメモリ状態を図示できる。

    主教材:メモリ・ポインタ・参照・ライフタイム →

    図鑑で仕組みを補う
  5. 5番目これから

    計算量と実測性能

    学習目標:O・Ω・Θ記法を用いて時間計算量と空間計算量を導出し、入力サイズに対する増え方を説明できる。

    主教材:計算量と実測性能 →

    図鑑で仕組みを補う
  6. 6番目これから

    二進表現・論理回路・命令セット

    学習目標:整数・文字・命令をビット列として表現し、基本的な論理演算が計算へつながる過程を説明できる。

    主教材:二進表現・論理回路・命令セット →

    図鑑で仕組みを補う
  7. 7番目これから

    CPU・命令サイクル・パイプライン

    学習目標:命令フェッチ、デコード、実行、メモリアクセス、書き戻しの流れを追跡できる。

    主教材:CPU・命令サイクル・パイプライン →

    図鑑で仕組みを補う
  8. 8番目これから

    キャッシュとメモリ階層

    学習目標:レジスタ、キャッシュ、主記憶、ストレージからなるメモリ階層と、局所性が必要な理由を説明できる。

    主教材:キャッシュとメモリ階層 →

    図鑑で仕組みを補う
  9. 9番目これから

    配列・リスト・スタック・キュー・ハッシュ・木

    学習目標:主要データ構造の内部表現と操作コストを説明し、要求される操作に応じて選択できる。

    主教材:データ構造を、必要な操作から選ぶ →

    図鑑で仕組みを補う
  10. 10番目これから

    分割統治・貪欲法・動的計画法・バックトラッキング

    学習目標:問題の部分構造から、分割統治・貪欲法・動的計画法・バックトラッキングの適用条件を識別できる。

    主教材:貪欲法・分割統治・動的計画法を使い分ける →

    図鑑で仕組みを補う
  11. 11番目これから

    グラフ表現・幅優先探索・深さ優先探索・最短経路

    学習目標:現実の問題を頂点・辺・重みとしてモデル化し、隣接リストと隣接行列の違いを説明できる。

    主教材:BFSとDFSを、探索順と最短路から理解する →

    図鑑で仕組みを補う
  12. 12番目これから

    デバッグ・テスト・再現可能性

    学習目標:不具合を再現し、ログ・スタックトレース・デバッガを使って原因箇所を段階的に絞り込める。

    主教材:デバッグとテスト:原因の仮説を小さな検証に変える →

    図鑑で仕組みを補う
  13. 13番目これから

    集合・関係・関数・組合せ

    学習目標:集合、関係、関数を用いて離散的な対象と対応関係を表現し、それぞれの性質を説明できる。

    主教材:集合・関係・数え上げ:重複と対応を正しく扱う →

    図鑑で仕組みを補う
  14. 14番目これから

    数学的帰納法・再帰・不変条件

    学習目標:基底段階と帰納段階を構成し、自然数や再帰的構造に関する性質を証明できる。

    主教材:数学的帰納法とループ不変条件:繰り返しの正しさを説明する →

    図鑑で仕組みを補う
  15. 15番目これから

    カーネル・特権モード・システムコール

    学習目標:ユーザーモードとカーネルモードの保護境界、およびシステムコールで境界を越える流れを説明できる。

    主教材:カーネル・特権モード・システムコール →

    図鑑で仕組みを補う
  16. 16番目これから

    仮想記憶・ページテーブル・TLB

    学習目標:仮想アドレスをページ番号とオフセットへ分解し、ページテーブルとTLBを通じた物理アドレス変換を追跡できる。

    主教材:仮想記憶・ページテーブル・TLB →

    図鑑で仕組みを補う
  17. 17番目これから

    インターリーブ・競合状態・原子性

    学習目標:複数スレッドの実行順序を列挙し、共有状態に対する競合状態と失われた更新を検出できる。

    主教材:インターリーブ・競合状態・原子性 →

    図鑑で仕組みを補う
  18. 18番目これから

    ミューテックス・セマフォ・条件変数・デッドロック

    学習目標:ミューテックス、セマフォ、条件変数、モニタの状態遷移を追跡し、用途の違いを説明できる。

    主教材:ロックと条件変数:共有状態を守り、変化を待つ →

    図鑑で仕組みを補う
  19. 19番目これから

    構文・意味論・型システム

    学習目標:構文、静的意味、動的意味を区別し、プログラムがどの規則で解釈されるか説明できる。

    主教材:構文・意味・型:プログラムの正しさを三つに分ける →

    図鑑で仕組みを補う
  20. 20番目これから

    コンパイラ・インタプリタ・ランタイム・GC

    学習目標:字句解析、構文解析、AST、IR、最適化、コード生成の各段階を追跡できる。

    主教材:コンパイラ・インタプリタ・ランタイム・GC →

    図鑑で仕組みを補う
  21. 21番目これから

    形式言語・正規表現・有限オートマトン

    学習目標:アルファベット、文字列、言語を形式化し、正規表現と有限オートマトンの対応を説明できる。

    主教材:形式言語・正規表現・有限オートマトン →

  22. 22番目これから

    計算可能性・還元・PとNP

    学習目標:チューリング機械と決定問題を用いて、計算可能・決定可能・決定不能の違いを説明できる。

    主教材:計算可能性・還元・PとNP →

進捗は言語ごとにこのブラウザへ保存されます。気になるステップから読んでもかまいません。