コンピューター科学と電子工学を、説明とシミュレーションで学びます。分野を選んで実験してみてください。

コーディングテスト 3

応用 2

1. #BOJ 2667

   製氷皿と連結成分

   0を埋める製氷皿から1の住宅をまとめる問題へ。BFSとDFSの訪問順を比較します。

2. Programmers 1844

   ゲームマップの最短経路

   距離とキューの変化を見ながら、BFSで最初に到達した経路が最短になる理由を確認します。

上級 1

1. #POJ 3057

   全員が部屋を出る最小時間

   出口ごとに1秒に1人。BFSの距離とDFSによる二部マッチングを組み合わせます。

コンピューターアーキテクチャ 5

1. 命令サイクル

   フェッチ・デコード・実行でのレジスタとメモリの値の移動を追います。

2. パイプラインとハザード

   5段階パイプラインの重複実行、依存、分岐、フォワーディングを確認します。

3. キャッシュマッピング

   アドレスのタグ・インデックス・オフセットと3つの配置方式を比較します。

4. 仮想メモリとTLB

   TLBとページテーブルによる変換とページフォルトを確認します。

5. 分岐予測

   常に分岐・1ビット・2ビット予測器を比較します。

データ構造 16

応用 12

整列、探索、区間処理、木、ハッシュを学び、問題に応用します。

1. 整列アルゴリズム比較

   同じ配列を7種類のアルゴリズムで整列し、処理量・計算量・用途を比べます。

2. バブルソート

   隣接する値を比較・交換し、未確定の最大値を末尾へ移動させます。

3. 選択ソート

   残りの最小値を繰り返し選び、次の確定位置へ交換します。

4. 挿入ソート

   値を1つずつ取り出し、整列済みの接頭部分へ挿入します。

5. 計数ソート

   値同士を比較せず、出現回数から出力位置を計算します。

6. 二分探索

   整列済み配列の候補を半分ずつ絞り込み、値の検索、下限・上限探索、答えの二分探索を体験します。

7. 2ポインタ法

   2つのポインタを一方向に進め、一部の二乗時間の探索を線形走査に変えます。

8. スライディングウィンドウ

   連続区間に入る値と出る値だけを更新し、区間の情報を効率よく保ちます。

9. 累積和

   累積和を前計算し、区間和を1回の引き算で求めます。

10. 二分探索木

    値の挿入・検索・削除を試し、木の形が変わる様子と偏った木が遅くなる理由を確認します。

11. ハッシュテーブル

    キーをバケットに対応付け、衝突の処理方法を体験します。

12. 幅優先探索と深さ優先探索

    同じグラフをBFSとDFSでたどり、キューとスタックによる訪問順序の違いを確認します。

上級 4

分割統治、ヒープ、最短経路、複数のアルゴリズムの組み合わせを学びます。

1. クイックソート

   ピボットを基準に分割し、左右を再帰的に整列します。

2. マージソート

   配列を再帰的に分割し、整列済みの半分同士をマージする分割統治法です。

3. ヒープソート

   最大ヒープを作り、最大値を繰り返し末尾へ移動させます。

4. ダイクストラ法

   未確定の中で最も近いノードを確定し、隣接ノードへの距離を更新します。

データベース 5

1. SQLの実行順序

   FROMからLIMITまでの論理的な処理順序と中間結果を確認します。

2. JOIN

   INNER、LEFT、RIGHT、FULL OUTER JOINによる行の結合を確認します。

3. インデックスとB+木

   B+木による検索と全件走査を、読み込むページ数で比較します。

4. 正規化

   非正規形を1NF、2NF、3NFに分解し、更新・挿入・削除の異常を確認します。

5. トランザクションと分離レベル

   分離レベルによるダーティリード、非再現読取り、ファントムの違いを調べます。

デジタル論理 4

1. 半加算器と全加算器

   3つの入力を切り替え、和と桁上がりを求める過程を確認します。

2. 2ビット・リップルキャリー加算器

   全加算器を2個つなぎ、桁上がりが次の桁に伝わる様子を確認します。

3. リングオシレータ

   NOTゲートの数を変え、発振する場合と安定する場合を比較します。

4. DRAMとNANDフラッシュ

   データ更新の方法と処理時間をDRAMとNANDで比較します。

組み込み通信 5

1. UARTフレーム

   1文字を開始・データ・パリティ・停止ビットに変換します。

2. I2CとSPI

   クロックとデータの波形を1ビットずつ確認します。

3. CRC計算（Modbus CRC-16）

   XORとシフトによるCRC-16計算をビット単位で追います。

4. PWMとデューティ比

   オン・オフだけで明るさやモータ駆動を変える原理を確認します。

5. ADCサンプリングとエイリアシング

   標本化が遅いと、別の周波数に見える現象を確認します。

オペレーティングシステム 7

1. CPUスケジューリング

   同じ4プロセスをFCFS、SJF、ラウンドロビンで動かし、待ち時間を比較します。

2. 競合状態とクリティカルセクション

   2スレッドの加算が2ではなく1になる実行順を試します。

3. ミューテックス

   所有者を持つロックと、優先度逆転・優先度継承を確認します。

4. セマフォ

   資源数のカウンタで、駐車場と生産者・消費者を制御します。

5. デッドロック

   食事する哲学者の例で循環待ちとその防止を確認します。

6. ページ置換

   FIFO、LRU、OPTで追い出すページとフォルト回数を比較します。

7. メモリ割当てと断片化

   First-fit、Best-fit、Worst-fitで空き領域の変化を比べます。