CS基礎を固める
プログラムの実行からOS・計算理論まで学ぶ
コードの実行、メモリ、計算量、CPUから学び始めます。データ構造、OS、型とコンパイラを経て、計算できる問題の範囲まで扱います。
プログラミング経験があり、CSを基礎から整理したい方
同じ処理なのに、どうして速さが変わるのか?
学習範囲と終了地点
このコースの主教材はすべて公開済みです。下の順番で最後まで学習できます。
- ステップ
- 22
- 主教材
- 22本
- 確認問題
- 60問
このコースで説明できるようになること
- 配列の読み方、データ構造、アルゴリズムの選択によって処理時間が変わる理由を説明する。
- プログラムの実行とOSの役割を説明し、型・コンパイラ・計算理論の基礎を使ってコードの性質を考える。
22ステップ中0ステップ完了
学習を始める →コースの内容を実装で確かめる
実験で確かめた規則を短い関数にし、テストで動きを確かめます。
学ぶ順番
1番目これから ソースコードから実行中のプログラムまで
学習目標:ソースコードがコンパイラ・インタプリタ・ランタイムを経て実行されるまでの境界を説明できる。
2番目これから 値・型・制御構造・関数・モジュール
学習目標:値、型、式、条件分岐、反復を追跡し、プログラムの状態変化を説明できる。
図鑑で仕組みを補う
3番目これから 命題論理・述語論理と証明
学習目標:命題、論理演算、量化記号を用いて自然言語の主張を形式化し、推論規則がなぜ妥当か説明できる。
4番目これから メモリ・ポインタ・参照・ライフタイム
学習目標:スタック、ヒープ、アドレス、ポインタ、参照を用いて実行中のメモリ状態を図示できる。
5番目これから 計算量と実測性能
学習目標:O・Ω・Θ記法を用いて時間計算量と空間計算量を導出し、入力サイズに対する増え方を説明できる。
6番目これから 二進表現・論理回路・命令セット
学習目標:整数・文字・命令をビット列として表現し、基本的な論理演算が計算へつながる過程を説明できる。
図鑑で仕組みを補う
7番目これから CPU・命令サイクル・パイプライン
学習目標:命令フェッチ、デコード、実行、メモリアクセス、書き戻しの流れを追跡できる。
図鑑で仕組みを補う
8番目これから キャッシュとメモリ階層
学習目標:レジスタ、キャッシュ、主記憶、ストレージからなるメモリ階層と、局所性が必要な理由を説明できる。
図鑑で仕組みを補う
9番目これから 配列・リスト・スタック・キュー・ハッシュ・木
学習目標:主要データ構造の内部表現と操作コストを説明し、要求される操作に応じて選択できる。
図鑑で仕組みを補う
10番目これから 分割統治・貪欲法・動的計画法・バックトラッキング
学習目標:問題の部分構造から、分割統治・貪欲法・動的計画法・バックトラッキングの適用条件を識別できる。
図鑑で仕組みを補う
11番目これから グラフ表現・幅優先探索・深さ優先探索・最短経路
学習目標:現実の問題を頂点・辺・重みとしてモデル化し、隣接リストと隣接行列の違いを説明できる。
12番目これから デバッグ・テスト・再現可能性
学習目標:不具合を再現し、ログ・スタックトレース・デバッガを使って原因箇所を段階的に絞り込める。
13番目これから 集合・関係・関数・組合せ
学習目標:集合、関係、関数を用いて離散的な対象と対応関係を表現し、それぞれの性質を説明できる。
14番目これから 数学的帰納法・再帰・不変条件
学習目標:基底段階と帰納段階を構成し、自然数や再帰的構造に関する性質を証明できる。
主教材:数学的帰納法とループ不変条件:繰り返しの正しさを説明する →
図鑑で仕組みを補う
15番目これから カーネル・特権モード・システムコール
学習目標:ユーザーモードとカーネルモードの保護境界、およびシステムコールで境界を越える流れを説明できる。
16番目これから 仮想記憶・ページテーブル・TLB
学習目標:仮想アドレスをページ番号とオフセットへ分解し、ページテーブルとTLBを通じた物理アドレス変換を追跡できる。
図鑑で仕組みを補う
17番目これから インターリーブ・競合状態・原子性
学習目標:複数スレッドの実行順序を列挙し、共有状態に対する競合状態と失われた更新を検出できる。
図鑑で仕組みを補う
18番目これから ミューテックス・セマフォ・条件変数・デッドロック
学習目標:ミューテックス、セマフォ、条件変数、モニタの状態遷移を追跡し、用途の違いを説明できる。
図鑑で仕組みを補う
19番目これから 構文・意味論・型システム
学習目標:構文、静的意味、動的意味を区別し、プログラムがどの規則で解釈されるか説明できる。
主教材:構文・意味・型:プログラムの正しさを三つに分ける →
図鑑で仕組みを補う
20番目これから コンパイラ・インタプリタ・ランタイム・GC
学習目標:字句解析、構文解析、AST、IR、最適化、コード生成の各段階を追跡できる。
図鑑で仕組みを補う
21番目これから 形式言語・正規表現・有限オートマトン
学習目標:アルファベット、文字列、言語を形式化し、正規表現と有限オートマトンの対応を説明できる。
22番目これから 計算可能性・還元・PとNP
学習目標:チューリング機械と決定問題を用いて、計算可能・決定可能・決定不能の違いを説明できる。
進捗は言語ごとにこのブラウザへ保存されます。気になるステップから読んでもかまいません。