【入試対策 | 北海道大学 | 情報科学院 | 情報理工】走る作曲家のAIカフェ

概要

「北海道大学大学院情報科学院修士課程入学試験」（令和6年8月実施）の情報理工学コース対策ページです。

過去問10年分（2014～2023）を解いた私が、必要な知識や要点をまとめていきます。

（開示の結果、合格最低点+100点でした。試験二日前にフルマラソンを走った身としては、まずまずの結果だと思います。）

戦略

選択問題について

院試は以下の内容で構成されます。

専門科目1: 基礎数学、情報数学、【選択】確率・統計、【選択】情報理論（4問のうち基礎数学と情報数学を含む3問を解答）
専門科目2: アルゴリズムとデータ構造、人工知能、コンピュータシステム、応用数学（4問のうち2問を選択し解答）

俗に、専門科目1では「情報理論」が、専門科目2では「アルゴリズムとデータ構造」と「コンピュータシステム」が簡単だと言われています。

しかし、今後の自分の研究に役立てたいので、専門科目1では「確率・統計」を、専門科目2では「アルゴリズムとデータ構造」と「人工知能」を選択しようと思います。

念のため、「情報理論」と「コンピュータシステム」も少しだけ勉強します。

試験時間について

専門科目1, 2のどちらも試験時間は2時間です。

単純に科目数で割れば、専門科目1では各科目を40分で、専門科目2では各科目を60分で解くことになります。

時間は十分あるので、選択科目の吟味は必ず行う予定です。

「情報理論」と「コンピュータシステム」も勉強するのは、この吟味を行うことによって、科目間で難易度に大きな差があっても対処できるようにするためです。

10年分の過去問を解くことの価値

過去問の内容（科目、範囲、形式）は割とかなりの頻度で変わっています。そのため、10年も昔の問題を解く必要はないように思えますが、出題の傾向は少なからずあります。

それどころか、実は長い間隔で「使いまわし」されている問題がいくつか存在します。例えば、2023年の「コンピュータシステム（専門科目１）」と2015年の「コンピュータ基礎工学（専門科目２）」や、2022年の「情報数学」と2014年の「情報数学」は大問単位で問題が酷似しています。

そのため、10年分の過去問を解く価値は十分にあると考えられます。

※10年より前（～2013）の過去問は最近の過去問と大きく異なるため、解く価値は低いです。

基礎数学

色々な行列

随伴行列\(A^{*}\)：\(A\)を転置してさらに各成分の複素共役をとってできる行列。

エルミート行列：\(A^{*} = A\)が成り立つ行列。

歪エルミート行列：\(A^{*} = - A\)が成り立つ行列。

正規行列：\(A A^{*} = A^{*} A\)が成り立つ行列。

正則行列：\(A A^{-1} = A^{-1} A = I\)が成り立つ行列（逆行列が存在する行列）。

直交行列：\(A^T A = A A^T = I\)が成り立つ行列。\(A^T = A^{-1}\)も成り立つ。

ユニタリ行列：\(A^{*} A = A A^{*} = I\)が成り立つ行列。

直交射影行列：\(A^2 = A\)（冪等性）と\(A^T = A\)（対称性）が成り立つ行列。

対角行列：\(a_{ij} = 0 \quad (i \neq j)\)である正方行列。対角行列同士の積は可換。

固有値分解

固有値分解とは、ある行列\(A\)を、固有ベクトルを列ベクトルとした行列\(P\)と、固有値\(\lambda\)を対角成分とした対角行列\(D\)として、以下のように分解することをいう。

\begin{align} A = P D P^{-1} \end{align}

これを利用して、\(A^n = P D^n P^{-1}\)のように行列のべき乗を求めることができる。

線形部分空間、線形写像

ある集合について、線形部分空間であることを示せ、という問題はここ10年で複数回出題されている。

以下の二つを示せばよい。

加法について閉じていること
スカラー倍について閉じていること

線形写像であることを示せ、という問題も出ることがあるが、同様に加法とスカラー倍について調べればよい。

基底

ベクトル空間\(V\)内のベクトルの組\(\mathbf{a_1}, \mathbf{a_2}, \cdots, \mathbf{a_n}\)が\(V\)の基底であることを示せ、という問題が出題されることがある。

この場合は、以下の二つを示せばよい。

\(V\)のすべてのベクトルが\(\mathbf{a_1}, \mathbf{a_2}, \cdots, \mathbf{a_n}\)の1次結合、つまり
\begin{align} c_1 \mathbf{a_1} + c_2 \mathbf{a_2} + \cdots + c_n \mathbf{a_n} \end{align}
で表される。
\(\mathbf{a_1}, \mathbf{a_2}, \cdots, \mathbf{a_n}\)が1次独立。

\(A \subset B、A = B\)の証明

\(A \subset B\)を示すには、「すべての\(x\)について、\(x \in A\)ならば\(x \in B\)」を示せばよい。

\(A = B\)を示すには、\(A \subset B\)かつ\(A \supset B\)を示せばよい。

停留点

停留点を求める問題は、ここ10年で複数回出題されている。

停留点は関数の変化がなくなる点であるため、\(x\)方向、\(y\)方向ともにその変化量が0、すなわち

\begin{align} \frac{\partial f(x,y)}{\partial x}=\frac{\partial f(x,y)}{\partial y}=0 \end{align}

となる点を求めればよい。

つまり、\(x\)と\(y\)の偏微分を求めて、それらをイコール0にした2式を連立して解けばよい。

このように停留点は簡単に求まるが、次に、その停留点が極大値なのか、極小値なのか、鞍点なのかを判定せよ、と問われることが多い。

停留点を判定するには、以下で定義されるヘッセ行列を使う。

\begin{align} H= \begin{pmatrix}\displaystyle{\frac{\partial^{2} f(x,y)}{\partial x^{2}}}&\displaystyle{\frac{\partial^{2} f(x,y)}{\partial x\partial y}} \\ \\ \displaystyle{\frac{\partial^{2} f(x,y)}{\partial x\partial y}}&\displaystyle{\frac{\partial^{2} f(x,y)}{\partial y^{2}}}\end{pmatrix} \end{align}

したがって、二階偏微分を求める必要がある。

二階偏微分を求めたら、ヘッセ行列の固有値\(\lambda_{1},\lambda_{2}\)を求めることによって、以下のように判別できる。

\begin{align} \begin{cases} \lambda_{1}>0,\lambda_{2}>0&\to\,\text{極小点}\\ \lambda_{1}<0,\lambda_{2}<0&\to\,\text{極大点}\\ \lambda_{1}\lambda_{2}<0&\to\,\text{鞍点} \end{cases} \end{align}

極座標変換

極座標変換ができないと解くのが難しい問題はここ10年で何度も出題されている。

まずは2次元の極座標変換を説明する。

2次元の極座標変換では、\(x\)と\(y\)を次のようにおく。

\begin{align} x = r \cos \theta , \ \ \ y = r \sin \theta \end{align}

このとき、ヤコビアンを計算すると以下のようになる。

\begin{align} J = & \left| \begin{array}{ccc} \frac{\partial x}{\partial r} & \frac{\partial x}{\partial \theta} \\ \frac{\partial y}{\partial r} & \frac{\partial y}{\partial \theta} \end{array} \right| \\ = & \left| \begin{array}{ccc} \cos \theta & - r \sin \theta \\ \sin \theta & r \cos \theta \end{array} \right| \\ = & \ r \left( \cos^2 \theta + \sin^2 \theta \right) \\ = & \ r \end{align}

したがって、\(dxdy = r \ dr d \theta\)となる。

次に、3次元の極座標変換を説明する。

3次元の極座標変換では、\(x\)と\(y\)を次のようにおく。

\begin{align} x = r \cos \theta \cos \varphi, \quad y = r \cos \theta \sin \varphi, \quad z = r \sin \theta \end{align}

このとき、ヤコビアン行列\(J\)は以下のようになる。

\begin{align} J = \frac{\partial(x, y, z)}{\partial(r, \varphi, \theta)} = \begin{pmatrix} \cos \theta \cos \varphi & -r \cos \theta \sin \varphi & -r \sin \theta \cos \varphi \\ \cos \theta \sin \varphi & r \cos \theta \cos \varphi & -r \sin \theta \sin \varphi \\ \sin \theta & 0 & r \cos \theta \end{pmatrix} \end{align}

したがって、ヤコビアン行列の行列式 \( \det(J) \) は次のように計算される：

\begin{align} \det(J) = r^2 \cos \theta \end{align}

以上のことは、\(\cos \theta\)と\(\sin \theta\)を入れ替えても成り立つ。

マクローリン展開・テイラー展開

マクローリン展開もテイラー展開も、この10年で1度ずつ出題されている。式の形は目に焼き付けておいた方が良いだろう。

マクローリン展開は次のように定義される：

\begin{align} f(x) = f(0) + f'(0)x + \frac{f''(0)}{2!}x^2 + \frac{f'''(0)}{3!}x^3 + \cdots + \frac{f^{(n)}(0)}{n!}x^n + \cdots \end{align}

この定義を ∑（シグマ）記号を使って表現すると、以下のようになる：

\begin{align} f(x) = \sum_{n=0}^{\infty} \frac{f^{(n)}(0)}{n!} x^n \end{align}

テイラー展開は次のように定義される：

\begin{align} f(x) = f(a) + f'(a)(x - a) + \frac{f''(a)}{2!}(x - a)^2 + \frac{f'''(a)}{3!}(x - a)^3 + \cdots + \frac{f^{(n)}(a)}{n!}(x - a)^n + \cdots \end{align}

この定義を ∑（シグマ）記号を使って表現すると、以下のようになる：

\begin{align} f(x) = \sum_{n=0}^{\infty} \frac{f^{(n)}(a)}{n!} (x - a)^n \end{align}

逆三角関数、双曲線関数

「基礎数学」では、毎年、微分積分力を試す問題が出題される。大学に入ってから登場したこれらの関数について、逆関数の微分公式と共に確認しておこう。

まずは、逆三角関数から。

\(\sin^{-1}\)の微分：

\(y = \sin^{-1} x\)の逆関数は、\(x = \sin y\)である。

両辺を微分すると、\(\frac{dx}{dy} = \cos y\)となる。

したがって、逆関数の微分公式より、

\begin{align} \frac{d}{dx} \sin^{-1} x &= \frac{dy}{dx} = \frac{1}{\frac{dx}{dy}} \\ &= \frac{1}{\cos y} \\ &= \frac{1}{\sqrt{1 - \sin^2 y}} = \frac{1}{\sqrt{1 - x^2}} \end{align}

となる。

\(\cos^{-1}\)の微分：

同様に求めることで、

\begin{align} \frac{d}{dx} \cos^{-1} x = - \frac{1}{\sqrt{1 - x^2}} \end{align}

を得る。

\(\tan^{-1}\)の微分：

同様に求めることで、

\begin{align} \frac{d}{dx} \tan^{-1} x = \frac{1}{1 + x^2} \end{align}

を得る。

次に、双曲線関数について。

双曲線関数は以下のように定義される。

\(\cosh x = \frac{e^x+e^{-x}}{2}\)
\(\sinh x = \frac{e^x-e^{-x}}{2}\)
\(\tanh x = \frac{\sinh x}{\cosh x} = \frac{e^x-e^{-x}}{e^x+e^{-x}}\)

以下の関係式が成り立つ。

\(\cosh^2 x - \sinh^2 x = 1\)
\(1 - \tanh^2 x = \frac{1}{\cosh^2 x}\)
\(1 - \frac{1}{\tanh^2 x} = -\frac{1}{\sinh^2 x}\)

微分は以下のとおり。

\((\cosh x)'=\sinh x\)
\((\sinh x)'=\cosh x\)
\((\tanh x)'=\frac{1}{\cosh^2 x}\)

積分は以下のとおり。

\(\int \cosh x \, dx = \sinh x + C\)
\(\int \sinh x \, dx = \cosh x + C\)
\(\int \tanh x \, dx = \log( \cosh x) + C\)

※ちなみに、\(tan x\)の積分は、\(- \log|\cos x| + C\)である。

情報数学

言語

言語の中でも、特に正規言語と文脈自由言語について問われることが多い。それぞれの代表例や特徴は必ず覚えておいた方が良い。

まずは、正規言語を説明する。

正規言語は、有限オートマトンによって認識される言語であり、正規文法によって生成される。

正規文法の例を以下に示す。

\( S \rightarrow aS \)
\( S \rightarrow bS \)
\( S \rightarrow \epsilon \) （\(\epsilon\)は空文字を表す）

この文法は、\(\{a, b\}\)からなる任意の文字列（例えば、\(\epsilon\), \(a\), \(b\), \(aa\), \(ab\), \(ba\), \(bb\) など）を生成する。

他にも、正規言語の例として、以下があげられる。

\(L = { a^n \mid n ≥ 0 }\)(空文字列または任意の個数の \(a\) からなる言語。)
\(L = (ab)^*\)(\(ab\) の繰り返しからなる言語。)

次に、文脈自由言語を説明する。

文脈自由言語は、プッシュダウンオートマトンによって認識される言語であり、文脈自由文法によって生成される。

文脈自由文法は、生成規則が左辺に1つの非終端記号を持ち、右辺が任意の文字列であるような形をしている文法である。

文脈自由文法の例を以下に示す。

\( S \rightarrow aSb \)
\( S \rightarrow \epsilon \)

この文法は、同数の \(a\) と \(b\) を持つ文字列（例えば、\(\epsilon\), \(ab\), \(aabb\), \(aaabbb\) など）を生成する。

この言語は、正規文法では表現できないが、文脈自由文法によって生成可能である。

他にも、文脈自由文法の例として、以下があげられる。

\(L = { a^n b^n | n ≥ 0 }\)(同じ数の \(a\) と \(b\) からなる言語。)
\(ww^R | w ∈ {a, b}^*\)(任意の文字列 \(w\) とその逆順 \(w^R\) からなる言語。)

ついでに、文脈依存文法も説明する。

文脈依存言語は、線形有界オートマトンによって認識される言語であり、文脈依存文法によって生成される言語である。

文脈依存文法の生成規則は、形式 \(α A β → α γ β\) を持ち、ここで \(A\) は非終端記号、\(α\)、\(β\)、および \(γ\) は任意の文字列である。

文脈依存言語の例を以下に示す。

\(L = { a^n b^n c^n | n ≥ 1 }\)(同じ数の \(a, b, c\) からなる言語。)

さらに、ここ10年で1度しか出題されていないが、言語の範囲で重要なポンピング定理について触れておく。

ポンピング定理：

任意の正規言語 \(L\) について、あるポンピング長 \(p\)（自然数）が存在して、\(L\) のすべての文字列 \(s\) が以下の条件を満たす場合に限り、\(s \in L\) である。

\(s\) の長さは \(p\) 以上である。
\(s\) は \(s = xyz\) という形に分割できる。
\(|xy| \leq p\)。
\(y \neq \epsilon\)。
任意の非負整数 \(i\) に対して、文字列 \(x　y^i　z \in L\) である。

具体例を以下に示す。

問題：言語 \(L = \{0^n 1^n \mid n \geq 0\}\) が正規言語でないことをポンピング定理を使って証明せよ。

仮に、言語 \(L = \{0^n 1^n \mid n \geq 0\}\) が正規言語であると仮定する。すると、ポンピング長 \(p\) が存在するはずである。

\(L\) から \(s\) を選ぶ。ここで、\(s = 0^p 1^p\) とする。この文字列 \(s\) の長さは \(2p\) で、ポンピング補題の条件を満たす。
ポンピング補題に従い、\(s\) を \(s = xyz\) の形に分割する。ここで、\(|xy| \leq p\) であり、\(y \neq \epsilon\) である。

\(|xy| \leq p\) なので、\(x\) と \(y\) はすべて \(0\) から構成される。具体的には、\(x = 0^a\)、\(y = 0^b\)、\(z = 0^{p-a-b} 1^p\) という形になる。ここで、\(a\) と \(b\) は非負整数であり、\(a + b \leq p\)、かつ \(b > 0\) である。

ポンピング補題により、任意の非負整数 \(i\) に対して、文字列 \(xy^iz\) が \(L\) に属するはずである。

しかし、\(i \neq 1\) の場合を考える。

\(i = 0\) のとき、
\(xy^0z = xz = 0^a 0^{p-a-b} 1^p = 0^{p-b} 1^p\)
である。ここで、\(b > 0\) なので、この文字列は \(0\) の数と \(1\) の数が一致せず、\(L\) に属さない。
\(i = 2\) のとき、
\(xy^2z = xyyz = 0^a 0^{2b} 0^{p-a-b} 1^p = 0^{p+b} 1^p\)
である。ここでも、\(b > 0\) なので、この文字列も \(0\) の数と \(1\) の数が一致せず、\(L\) に属さない。

これらの例から、\(xy^iz\) が \(L\) に属さない \(i\) が存在することが示される。したがって、ポンピング補題の条件を満たさないため、仮定に矛盾する。

したがって、言語 \(L = \{0^n 1^n \mid n \geq 0\}\) は正規言語ではないことが証明された。

命題論理

積和標準形（DNF; 選言標準形）：真理値表を書いて、全体の真理値が1になる最小項をORでつなぐ。

和積標準形（CNF; 連言標準形）：真理値表を書いて、全体の真理値が0になる最小項をANDでつなぐ。

片方を求めたら、ド・モルガン則を使ってもう片方を求めることもできる。

述語論理

ここでは、過去にわかりやすい問題が出題されているので、それを用いて説明する。

人の集合 P と述語 LOVES(x, y)（意味は「x は y を好きである」）を考える。

このとき、以下の二つの述語論理式を考える。

\(A: ∀x ∈ P ∃y ∈ P \ LOVES(x, y)\)
\(B: ∃y ∈ P ∀x ∈ P \ LOVES(x, y)\)

Aの意味：「P のすべての x に対して、P のある y が存在し、x はその y を好きである」（言い換えると、「P のすべての人には、好きな人がいる」ということを表している。）

Bの意味：「P のある y が存在し、P のすべての x がその y を好きである」（言い換えると、「P の中には、みんなから好かれている特定の人がいる」ということを表している。）

距離関数

距離関数であるための条件は以下の3つである。

\( d(A, B) = 0 \) \(\Leftrightarrow\) \( A = B \)
\( d(A, B) = d(B, A) \)
\( d(A, C) \leq d(A, B) + d(B, C) \)

同値関係

集合 \( A \) 上の二項関係 \( R \) は以下の3つの性質を満たすとき、同値関係であるという。

反射律：任意の \( x \in A \) に対して、\( xRx \) が成り立つ。
対称律：任意の \( x, y \in A \) に対して、\( xRy \) ならば \( yRx \) が成り立つ。
推移律：任意の \( x, y, z \in A \) に対して、\( xRy \) かつ \( yRz \) ならば \( xRz \) が成り立つ。

確率・統計

一致性

一致性とは、ある母数\(\theta\)の推定量\(\hat{\theta}\)が\(\hat{\theta} \xrightarrow{P} \theta\)を満たすことをいい、\(\hat{\theta}\)を一致推定量と呼ぶ。

ここで、\(\xrightarrow{P}\)は「確率収束する」という意味である。

標本平均、標本分散、不偏分散の一致性は以下のとおり。

標本平均

大数の弱法則\(\overline{x} \xrightarrow{P} \mu\)から、平均\(\overline{x}\)は\(n\)が大きくなると母平均に近づく。

標本分散

標本分散は以下の式で表される。
\begin{align} s^2 = \frac{1}{n} \sum_{i=1}^n (x_i - \overline{x})^2 \end{align}
この式は、以下のように変形できる。
\begin{align} s^2 &= \frac{1}{n} \sum_{i=1}^n (x_i - \overline{x})^2 \\ &= \frac{1}{n} \sum_{i=1}^n ((x_i - \mu) - (\overline{x} - \mu))^2 \\ &= \frac{1}{n} \sum_{i=1}^n (x_i - \mu)^2 - (\overline{x} - \mu)^2 \\ \end{align}
この式の第２項は\((\overline{x} - \mu) \xrightarrow{P} 0\)であるため、\((\overline{x} - \mu)^2 \xrightarrow{P} 0\)となる。
また、\(\nu_i = (x_i - \mu)^2\)とおくと、\(\nu_i\)は互いに独立で同じ分布に従う確率変数となり、大数の法則を適用できる。
これから、第１項は\(\overline{\nu} \xrightarrow{P} \sigma^2\)となり、\(s^2 \xrightarrow{P} \sigma^2\)がいえる。

不偏分散

不偏分散は以下の式で表される。
\begin{align} u^2 = \frac{1}{n-1} \sum_{i=1}^n (x_i - \overline{x})^2 \end{align}
\(n \rightarrow \infty\)のとき、無限大に発散する分母について、\(s^2\)と高々１しか差がない\(u^2\)も一致性を持つ。

不偏性

不偏性とは、推定量\(\hat{\theta}\)の期待値が\(E[\hat{\theta}] = \theta\)と、常に母数に等しくなる性質をいい、その性質を持つ推定量を不偏推定量と呼ぶ。

これは一致性と異なり、標本の大きさ\(n\)に依存しない基準である。

不偏推定量でなければ、推定には偏りがあるといい、偏りを\(E[\hat{\theta}] - \theta\)で定義する。

標本平均、標本分散、不偏分散の不偏性は以下のとおり。

標本平均

\begin{align} E[\overline{x}] = \frac{1}{n} \sum_{i=1}^{n} E[x_i] = \frac{1}{n} \sum_{i=1}^{n} \mu = \mu \end{align}

標本分散、不偏分散

偏差平方和を\(T_{xx} = \sum (x_i - \overline{x})^2\)とおくと、
\begin{align} T_{xx} &= \sum (x_i - \overline{x})^2 \\ &= \sum [(x_i - \mu) - (\overline{x} - \mu)]^2 \\ &= \sum [(x_i - \mu)^2 - 2 (x_i - \mu)(\overline{x} - \mu) + (\overline{x} - \mu)^2] \\ &= \sum (x_i - \mu)^2 - 2 (\overline{x} - \mu) \sum (x_i - \mu) + \sum (\overline{x} - \mu)^2 \\ &= \sum (x_i - \mu)^2 - 2 (\overline{x} - \mu) (n \overline{x} - n \mu) + n (\overline{x} - \mu)^2 \\ &= \sum (x_i - \mu)^2 - 2 (\overline{x} - \mu) n (\overline{x} - \mu) + n (\overline{x} - \mu)^2 \\ &= \sum (x_i - \mu)^2 - n(\overline{x} - \mu)^2 \end{align}
となる。
ここで期待値を計算すると次の結果が得られる。
\begin{align} E[T_{xx}] &= \sum E[(x_i - \mu)^2] - n E[(\overline{x} - \mu)^2] \\ &= \sum V[x_i] - nV[\overline{x}] \\ &= n \sigma^2 - n \frac{\sigma^2}{n} \\ &= (n-1) \sigma^2 \end{align}
したがって、標本分散は不偏性を持たず、不偏分散は不偏性を持つ。

期待値、分散、共分散

期待値：

\begin{align} E(X) = \int_{-\infty}^{\infty} xf(x) dx = \mu \end{align}

\begin{align} E(X) = \sum_i x_i f(x_i) = \mu \end{align}

\begin{align} E(cX + dY + t) &= E(cX + dY) + t \\ &= E(cX) + E(dY) + t \\ &= cE(X) + dE(Y) + t \end{align}

分散：

\begin{align} V(X) = E[(X - \mu)^2]= \int_{-\infty}^{\infty} (x - \mu)^2 f(x) dx = \sigma^2 \end{align}

\begin{align} V(X) = \sum_i (x_i - \mu)^2 f(x_i) = \sigma^2 \end{align}

\begin{align} V(X) = E(X^2) - \mu^2 \end{align}

\begin{align} V(cX + t) &= V(cX) \\ &= c^2 V(X) \end{align}

\(X, Y\)が無相関のとき、以下が成り立つ。

\begin{align} E(XY) = E(X) E(Y) \\ V(X+Y) = V(X) + V(Y) \end{align}

共分散：

\begin{align} Cov(X, Y) &= E(XY) - E(X) E(Y) \\ V(X+Y) &= V(X) + V(Y) + 2 Cov(X, Y) \quad \text{\(X, Y\)が無相関\( \iff Cov(X, Y) = 0\)} \end{align}

独立と無相関

独立なら無相関だが、無相関でも独立とは限らない。

確率変数\(X, Y\)が独立とは：

任意の\(x, y\)に対して\(P(X = x, Y = y) = P(X = x) P(Y = y)\)が成立する（確率が二つの積に分解できる）
\(X\)と\(Y\)の間には何の関係もない

確率変数\(X, Y\)が無相関とは：

\(E(XY) = E(X)E(Y)\)
共分散\(Cov(X,Y)\)が0
相関係数が0
\(X\)と\(Y\)の間には直線的な関係がない

無相関だが独立でない例：

\((X, Y) = (1, 0), (0, 1), (-1, 0), (0, -1)\)となる確率がそれぞれ\(\frac{1}{4}\)であるような場合。

色々な確率分布

ベルヌーイ分布：

注目している結果の起こる確率は一定で、各回の試行結果は互いに独立であるような試行をベルヌーイ試行という。
2種類の結果は値（1と0）で表し、成功（値1）である確率を\(p\)とする。
1回のベルヌーイ試行で得られる確率分布をベルヌーイ分布とよぶ。
確率関数は
\begin{align} P(X = 1) = f(1) &= p \\ P(X = 0) = f(0) &= 1 - p \end{align}
と表され、その期待値と分散は
\begin{align} \mu &= p \\ \sigma^2 &= p(1-p) \end{align}
となる。

二項分布：

成功確率\(p\)の\(n\)回のベルヌーイ試行を行ったとき、成功の確率が\(x\)、失敗の確率が\(n-x\)である確率、すなわち、成功の回数\(X = x\)に対する確率関数は
\begin{align} P(X = x) = f(x) = {}_n C_x p^x (1-p)^{n-x} \end{align}
となる。
\(B(n, p)\)で表される。
期待値と分散は
\begin{align} \mu &= np \\ \sigma^2 &= np(1-p) \end{align}
となって、\(n=1\)のとき、ベルヌーイ分布に一致する。

ポアソン分布：

ポアソン分布は、二項分布\(B(n, p)\)において期待値\(np = \lambda\)を固定し、試行回数と成功確率について\(n \leftarrow \infty, p \leftarrow \infty\)のような極限をとったときに得られる確率分布として定義される。
つまり、\(n\)が大きく\(p\)が小さい二項分布に対する近似として使用できる。
ポアソン分布の確率関数は
\begin{align} f(x) = \frac{e^{- \lambda} \lambda^x}{x!} \end{align}
であり、期待値と分散は
\begin{align} E(X) = V(X) = \lambda \end{align}
となる。
ある時間間隔\(T\)の間に電話のかかってくる回数など。

幾何分布：

成功の確率が\(p\)であるベルヌーイ試行を、初めて成功するまで繰り返したときの試行回数\(X\)の確率分布を幾何分布という。
初めて成功するのが\(x\)回目であるとすると、それまでの\(n-1\)回は失敗であるため、その確率は
\begin{align} P(X=x) = f(x) = p(1-p)^{x-1} \end{align}
であり、期待値と分散は
\begin{align} E(X) &= \frac{1}{p} \\ V(X) &= \frac{1-p}{p^2} \end{align}
となる。

一様分布：

区間\([a, b]\)内のどの値も同じ起こりやすさを持つ、すなわち、確率密度関数が
\begin{align} f(x) = \begin{cases} \frac{1}{b-a} \quad (a \leq x \leq b) \\ 0 \quad (\text{otherwise}) \end{cases} \end{align}
で表される分布を一様分布とよび、\(U(a, b)\)と表す。
期待値と分散は
\begin{align} E(X) &= \frac{a+b}{2} \\ V(X) &= \frac{(b-a)^2}{12} \end{align}
である。

正規分布：

確率密度関数は
\begin{align} f(x) = \frac{1}{\sqrt{2 \pi \sigma^2}} \exp(- \frac{(x-\mu)^2}{2 \sigma^2}) \end{align}
で与えられ、\(N(\mu, \sigma^2)\)で表される。
\(Z = \frac{X-\mu}{\sigma}\)と変換すると、\(Z\)は平均0、分散1の標準正規分布に従う。この変換を標準化という。
標準正規分布の確率密度関数は
\begin{align} \varphi(x) = \frac{1}{\sqrt{2 \pi}} \exp(- \frac{z^2}{2}) \end{align}
と表され、累積分布関数は
\begin{align} \varPhi(x) = \int_{- \infty}^{z} \frac{1}{\sqrt{2 \pi}} \exp(- \frac{z^2}{2}) \end{align}
となる。

指数分布：

どの時点でも同様な起こりやすさをもつランダムな現象があるとき、一定の時間内に生起する回数はポアソン分布に従うが、生起するまでの待ち時間の分布は指数分布に従う。
確率密度関数は
\begin{align} f(t) = \lambda e^{- \lambda t} \end{align}
であり、期待値と分散は
\begin{align} E(X) &= \frac{1}{\lambda} \\ V(X) &= \frac{1}{\lambda^2} \end{align}
で与えられる。

情報理論

色々なエントロピー、相互情報量

エントロピーの意味：例えば、\(H(X)\)が大きいとは、\(X\)が各値を取る確率の偏りが小さく、不確実性が大きいことを意味する。

相互情報量の意味：例えば、\(I(X;Y)\)が大きいとは、\(X, Y\)の片方がわかったときに他方について得られる情報が多く、不確実性が大きく減少することを意味する。

エントロピー、同時エントロピー、条件付きエントロピー、相互情報量の間に成り立つ関係式は、毎年ほぼ確実に問われるため、暗記はマストである。ベン図を思い浮かべると良い。

以下に関係式を列挙する。

\begin{align} H(X,Y) \leq H(X) + H(Y) \end{align}

\begin{align} I(X;Y) = H(X) + H(Y) - H(X, Y) \end{align}

\begin{align} I(X;Y) = H(X) - H(X|Y) = H(Y) - H(Y|X) \end{align}

\begin{align} H(X|Y) = H(X, Y) - H(Y) \end{align}

\begin{align} H(Y|X) = H(X, Y) - H(X) \end{align}

\(H(Y|X)\)は以下の式によって求められる。

\begin{align} H(Y|X) = - \sum P(X) \sum P(Y|X) \log_2 P(Y|X) \end{align}

また、通信路容量の問題もよく出題される。

無記憶定常通信路の通信路容量\(C\)は

\begin{align} C = \max_{P_X} I(X;Y) \end{align}

によって計算できる。

(7, 4)ハミング符号、巡回符号

過去に、(7, 4)ハミング符号、巡回符号に関する問題も出題されている。

情報理論は問題のパターンが限られているので、これもしっかり解けるようにしておきたい。

具体例を以下に示す。

問題

符号語
\(w = (x_1, x_2, x_3, x_4, x_1 + x_3 + x_4, x_1 + x_2 + x_3, x_2 + x_3 + x_4)\)
となる \((7,4)\) ハミング符号において、系列 1011011 を受信した。単一誤りまでを想定した場合、送信された情報源記号は何であったと推定されるか答えよ。+は2元体上の加算を表す。
2元体上の生成多項式が \(G(x) = x^4 + x^2 + 1\) である符号長7の巡回符号において、情報ビット 110 を符号化した後の2元系列を答えよ。

(1)の解答

(7,4)ハミング符号のパリティ検査方程式の係数行列（検査行列）\(\mathbf{H}\)は、与えられた符号語\(\mathbf{w}\)より、以下のとおりである。

\begin{align} \mathbf{H} = \begin{bmatrix} 1 & 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 & 1 \end{bmatrix} \end{align}

\(\mathbf{w} \mathbf{H}^T\)を計算し、シンドロームを求めると、

\begin{align} \mathbf{w} \mathbf{H}^T = \begin{bmatrix} 1 & 0 & 1 & 1 & 0 & 1 & 1 \end{bmatrix} \begin{bmatrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 \end{bmatrix} \end{align}

となる。これは、\(\mathbf{H}^T\)の3行目と一致するので、\(w_3\)を訂正すればよい。

したがって、送信された情報源記号は\(1001011\)である。

(2)の解答

情報ビット110を係数とする多項式は

\begin{align} X(x) = x^2 + x \end{align}

である。これに\(x^{7-3} = x^4\)を掛けると、

\begin{align} X(x) x^4 = x^6 + x^5 \end{align}

となる。これを生成多項式\(G(x) = x^4 + x^2 + 1\)で割った剰余は、

\begin{align} C(x) = x^3 + x + 1 \end{align}

であり、符号多項式は以下のように求められる。

\begin{align} W(x) = X(x) x^4 + C(x) = x^6 + x^5 + x^3 + x + 1 \end{align}

したがって、求める2元系列は、\(1101011\)である。

正規マルコフ情報源のエントロピー

今年（2024年）の情報理論では、ここが問われるのではないかと踏んでいる。

具体例を以下に示す。

問題

以下の2元マルコフ情報源\(S\)について、情報源\(S\)のエントロピー\(H(S)\)を求めよ。\(\log_2 3 = 1.585, \log_2 5 = 2.322\)とする。

s_0 >> s_0 : 0 / 0.4
s_0 >> s_1 : 0 / 0.1
s_0 >> s_2 : 1 / 0.5
s_1 >> s_0 : 0 / 0.4
s_1 >> s_1 : 1 / 0.6
s_2 >> s_1 : 1 / 0.2
s_2 >> s_2 : 0 / 0.8

解答

正規マルコフ情報源\(S\)のエントロピー\(H(S)\)の求め方は以下の通りである。

定常分布を求める
各状態\(s_i\)において、記憶のない情報源とみなし、その場合のエントロピー\(H_{s_i} (S)\)を求める
上で求めたエントロピー\(H_{s_i} (S)\)を、定常分布にしたがった割合で合算する

したがって、まずは定常分布を求める。定常分布は以下の二つの関係式から求めることができる。

\begin{align} w_0 + w_1 + &\cdots + w_{N-1} = 1 \\ \mathbf{w} \Pi &= \mathbf{w} \end{align}

ここで、\(\Pi\)は状態遷移確率行列であり、以下のとおりである。

\begin{align} \mathbf{\Pi} = \begin{bmatrix} 0.4 & 0.1 & 0.5 \\ 0.4 & 0.6 & 0 \\ 0 & 0.2 & 0.8 \end{bmatrix} \end{align}

したがって、定常分布は以下のとおり。

\begin{align} (w_0, w_1, w_2) = (0.2, 0.3, 0.5) \end{align}

今、\(S\)が状態\(s_0\)にあるときだけに注目すると、この情報源は\(0, 1\)を\(0.5, 0.5\)の確率で発生する記憶のない情報源とみなせる。

その場合のエントロピーは

\begin{align} H_{s_0} (S) = \mathcal{H} (0.5) = - 0.5 \log_2 0.5 - (1 - 0.5) \log_2 (1 - 0.5) = 1 \end{align}

であり、同様に状態\(s_1, s_2\)について考えると

\begin{align} H_{s_1} (S) = \mathcal{H} (0.6) = - 0.6 \log_2 0.6 - (1 - 0.6) \log_2 (1 - 0.6) = 0.971 \\ H_{s_2} (S) = \mathcal{H} (0.2) = - 0.2 \log_2 0.2 - (1 - 0.2) \log_2 (1 - 0.2) = 0.722 \end{align}

となる。定常分布では、\(s_0\)にいる確率が\(0.2\)、\(s_1\)にいる確率が\(0.3\)、\(s_2\)にいる確率が\(0.5\)であるから、エントロピー\(H(S)\)は

\begin{align} H (S) &= 0.2 \times H_{s_0} (S) + 0.3 \times H_{s_1} (S) + 0.5 \times H_{s_2} (S) \\ &= 0.2 \times 1 + 0.3 \times 0.9771 + 0.5 \times 0.722 \\ &\simeq 0.854 \end{align}

となる。

アルゴリズムとデータ構造

計算量、オーダー表記

ここ2年（2022, 2023年）は計算量の問題が出題されているため、オーダー表記はしっかり押さえておくべきである。

項の強さを強い順に並べると以下のとおりである。

\(n!, 2^n, n^3, n^2, n \log n, n, \sqrt{n}, \log n\)

隣接リスト

ここ2年（2022, 2023年）は隣接行列と隣接リストがセットで出題されている。

どちらも簡単だが、隣接リストには表記ゆれがあるので、北大の授業「アルゴリズムとデータ構造」（3年春ターム開講）の過去問に倣って、以下のように書くと安心である。

隣接リストの例：

頂点	隣接リスト
a	b, f, g, h
b	d, c, f
c	d, e
d	null
e	null
f	null
g	null
h	g

全域木

全域木は、ここ10年で複数回出題されているため、確認しておいた方が良い。

全域木とは、もとのグラフのすべての点を含み、さらに選んだ辺が木となっているようなグラフである。

全域木の個数を数える方法は以下の通りである。

ラプラス行列\(L\)（各行各列がグラフの頂点に対応していて、対角成分にはその頂点の次数、非対角成分には枝がある部分に\(-1\)、ない部分に\(0\)を格納した正方行列）を作る。
\(L\)の11余因子\(L_{11}\)の行列式の値が全域木の個数となる。

最小全域木とは、選んだ辺の重みの合計が一番小さい全域木のことである。

最小全域木を求めるアルゴリズム①「クラスカル法」は以下のとおりである。

重みが小さい順に辺をチェックする。
チェックした辺を追加しても閉路ができなければ辺を追加する。追加して閉路ができてしまう場合は無視する。
すべての辺をチェックし終わったときに追加された辺が最小全域木である。

最小全域木を求めるアルゴリズム②「プリム法」は以下のとおりである。

スタートの点を１つ決める（どこでも良い）。
スタート点から辿れる辺の中で最も重みが小さい辺を追加する（最も重みが小さい辺が複数ある場合は、重みが小さいどの辺を選んでも良い）。
追加した辺につながっているすべての点から辿れる辺かつ追加しても閉路とならない辺の中から最も重みが小さい辺を追加する。
追加できる辺がなくなったとき、最小全域木である。

グラフの種類

木：閉路が存在しない連結なグラフ

単純グラフ：多重辺や自己ループを含まないグラフ

二部グラフ：頂点が二つのグループに分かれており、異なるグループの頂点間にのみ辺が引かれているグラフ

完全グラフ：全ての頂点間に辺が引かれているグラフ

完全二部グラフ：二部グラフで、異なるグループの頂点間には全て辺が引かれているグラフ

オイラーグラフ：一筆書きできるグラフ

ユークリッドの互除法

アルゴリズムgcd(a,b)は以下の手順に従う。

b が 0 ならば、a を返す
b が 0 でなければ、gcd(b, a%b) を返す

再帰回数が\(O(\log a)\)であることの理由：

\(a > b > r, q \geq 1\)より、\(a = bq + r > 2r\)である。
つまり、互除法は各ステップで少なくとも半分に値が減少するため、最大で \( \log_2 a \) 回のステップが必要である。
したがって、再帰の深さは \( O(\log a) \) である。

人工知能

Q学習

Q学習は、ここ10年で二度出題されている（2017, 2023年）。

問われる内容は簡単なので、基礎的なことは覚えておいて損はない。

有限マルコフ決定過程とは：

マルコフ性を満たす環境においてエージェントが意思決定をして状態が確率的に遷移し、状態や行動が有限であるということ。
環境がマルコフ性を持つとは、過去の環境の履歴すべてが、現在の環境情報に集約されていることを指す。

方策の例：

グリーディ方策
\begin{align} \pi(s, a) = \arg\max\limits_a Q(s, a) \end{align}
ε-グリーディ方策
\begin{align} \pi(s, a) = \begin{cases} \arg\max\limits_a Q(s, a) & \text{with probability } 1 - \epsilon \\ \text{random action} & \text{with probability } \epsilon \end{cases} \end{align}
ソフトマックス方策
\begin{align} \pi(s, a) = \frac{e^{Q(s, a) / \tau}}{\sum\limits_{b} e^{Q(s, b) / \tau}} \end{align}

Q値の更新式：

\begin{align} Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \left( r_{t+1} + \gamma \max\limits_a Q(s_{t+1}, a) - Q(s_t, a_t) \right) \end{align}

Q値の収束性：

エージェントが十分に多くのエピソードを経験し、すべての状態-行動ペアを探索することで、Q値は収束し、最適方策が得られる。理論的には、探索が無限に続く場合、適切な学習率と割引率の選択により、Q値は最適な値に収束することが保証されている。

ニューラルネットワーク

ニューラルネットワークは、人工知能の範囲では最も出題頻度が高い。つまり、最重要ポイントである。

誤差逆伝播法：ネットワーク内の各重みについて損失関数の勾配を計算する方法。

最急降下法：その勾配を使って重みを更新する方法。具体的には、以下のように更新される。

\begin{align} w_{i+1} &= w_i - \alpha \frac{\partial L}{\partial w_i} \end{align}

ここで、\(w_i\)は更新する重み、\(\alpha\)は学習率、\(L(\cdot)\)は損失関数である。

過学習を抑える方法：

方法1: ドロップアウト（Dropout）
ドロップアウトは、ニューラルネットワークの訓練中にランダムにいくつかのノード（ニューロン）を無効化する（ゼロにする）手法である。これは、ネットワークが特定のノードやその結合に過度に依存するのを防ぎ、より汎用的な特徴を学習するのを助ける。
- 説明:
  1. 各訓練ステップで、指定された確率（例えば50%）でノードを無効化する。
  2. テスト時には全てのノードを使用するが、訓練時に無効化した確率に応じてノードの出力をスケールする。
方法2: L2正則化（L2 Regularization）
L2正則化は、重みパラメータに対してペナルティを加える手法である。具体的には、損失関数に重みの二乗和を加えることで、大きな重みが成長するのを防ぎ、過学習を抑制する。
- 説明:
  1. 損失関数 \( L \) に対して、以下のようなペナルティ項 \( \lambda \sum w^2 \) を追加する。
  2. ここで、\( \lambda \) は正則化の強さを制御するハイパーパラメータであり、\( w \) は重みパラメータを表す。
  3. このペナルティにより、重みが大きくなることを抑制し、モデルの複雑さを制限する。

他にも、余分な説明変数を減らすL1正則化、ハイパーパラメータチューニングやアンサンブルといった方法がある。

コンピュータシステム

補数表現

補数表現の問題はほぼ毎年出題される。簡単な問題が多いので、点の稼ぎどころである。

補数の計算だけでなく、補数を使うことの意味も押さえておくべきである。

2の補数表現を用いて負の10進数を2進数で表すには、以下の手順を踏めばよい。

指定のビット数で、対象の10進数を正にした値を2進数で表す。
ビットを反転させる。
反転した値に1を加算する。

最後に1を加算する操作を除けば、1の補数となる。

1の補数には｢負のゼロ｣が存在するため、負の整数を1の補数で表現するとき、\(n\)ビットの2進数で表現できる整数の範囲は\(- 2^{n-1} + 1\)から\(2^{n-1} - 1\)までである。

一方、2の補数には負のゼロが存在しないため、表現できる負の数が1つ多くなって、範囲は\(- 2^{n-1}\)から\(2^{n-1} - 1\)までとなる。

補数を用いる利点としては、符号付き整数の表現に効果的であり、加算器だけで減算が可能になることが挙げられる。これにより、ハードウェアが簡素化され、計算速度が向上する。

固定小数点方式、浮動小数点方式

この2つもほぼ毎年出題されるため、確実に解けるようにしておきたい。

固定小数点方式：数値を固定された小数点位置で表現する方式。この方式では、小数点以下の桁数があらかじめ決まっており、整数部と小数部の桁数が固定されている。例えば、16ビットの固定小数点数の場合、8ビットを整数部、8ビットを小数部として扱う。この方式は、計算が簡単で処理が高速であるが、表現できる数の範囲と精度が限られている。

浮動小数点方式：数値を仮数部と指数部に分けて表現する方式。この方式では、小数点の位置が仮数部と指数部によって動的に決定されるため、非常に大きい数や非常に小さい数を表現することができる。 IEEE 754規格が広く使われており、32ビットの単精度と64ビットの倍精度が一般的である。浮動小数点方式は、広い範囲の数を表現できる一方で、計算が複雑で丸め誤差が生じることがある。

具体的には、有限のビット数で無限小数を表現する際に、元の数値を近似的に表現する必要がある場合に生じる。この近似により、演算結果が正確な値から僅かにずれることがあり、これが丸め誤差の原因である。特に、小数点以下の桁数が長い数値や、極端に大きいまたは小さい数値の演算時に顕著に現れることが多い。

誤差についてまとめておく。

丸め誤差：「表現できる数の範囲」（有効桁）を超えてしまった際に有効桁以降を切り捨てることによって発生する誤差。
打ち切り誤差：コンピュータの計算処理を途中で打ち切ることにより発生する誤差。
桁落ち：値がほぼ等しい数値差を求めた時に発生する誤差。
情報落ち：大きい値と小さい値の数値を和もしくは差を求めた時に発生する誤差。

また、正規化について問われることも多い。

正規化：小数点の位置を調整し最上位桁を0以外の値にする作業のこと。正規化によって、有効桁数を最大化し丸め誤差を少なくすることができる。

キャッシュメモリ

キャッシュメモリに関する問題は、ここ10年で二度出題されている（2015, 2023年）。

問われた内容はほぼ同じであり、以下を押さえておけばよい。

キャッシュメモリの割り付け方式：

ダイレクトマップ方式：主記憶のブロック番号から、キャッシュメモリでのブロック番号が一意に定まる方式。具体的には、主記憶上のブロック番号にハッシュ演算を行い、一意に対応するキャッシュメモリのブロック番号を算出する。
フルアソシアティブ方式：主記憶のブロックがどのキャッシュブロックにも対応付けられる方式。ダイレクトマップ方式と異なり、最初に書きこもうとしたブロックがふさがっていても、空いているブロックに書けるため、ヒット率が向上する。しかし、主記憶のどのブロック内容がキャッシュのどのブロックに格納されているのか、すべて記憶しておく必要があり、検索にも時間がかかる。
セットアソシアティブ方式：ダイレクトマップ方式とフルアソシアティブ方式の中間に位置する方式。具体的には、連続したキャッシュブロックをセットとしてまとめ、そのセットの中であればどのブロックでも格納できる方式である。

スラッシング：

CPUがアクセスするメモリブロックが頻繁にキャッシュ内で置き換えられる現象。この現象は、特定のアクセスパターンによって、キャッシュの一部にメモリブロックが集中して配置されるために発生する。スラッシングが発生すると、キャッシュミスが増加し、キャッシュの利点である高速なデータアクセスが失われ、結果としてシステムのパフォーマンスが大幅に低下する。アプリケーションにとっては、処理速度が遅くなる、レスポンスが悪化するなどの悪影響を受ける可能性がある。

IPアドレス

IPアドレスに関する問題は、ここ最近の出題頻度が高い。IPAがよく出題するような問題が出る。

ネットワークアドレス：与えられたIPアドレスとサブネットマスクをそれぞれ2進数で表し、各ビットでAND演算を行なえばよい。

ブロードキャストアドレス：ネットワークアドレスのホスト部のすべてのビットを1にすればよい。

割り当て可能なアドレス数を間接的に問われることがあるが、\(2^{\text{ホスト部のビット数}}\)からネットワークアドレスとブロードキャストアドレスの2個を引き算することを忘れないように。

｢拡張｣や｢分割｣に関する、少し難しめの問題も出るが、その場合はホスト部のビット数を増やすことを考えればよい。

OSスケジューラ

OSスケジューラに関する問題も頻出である。タスクのスケジューリング方式は必ず理解しておかなければならない。

到着順方式(First Come First Served)：タスクには優先度をもたせず、実行可能になった順に実行し、タスクの実行が終了するまでプリエンプションは発生しない。
優先順位方式：各タスクに与えた優先度の高い順に実行する方式。この方式では、現在実行しているタスクよりも高い優先度を持つタスクが実行可能状態になると、タスクの実行はプリエンプションされる。優先順位方式のうち、タスクの優先度をあらかじめ決めた値から変えない方式を静的優先順位方式という。この方式では、優先度が固定化されるため、優先度の低いタスクにはCPU使用権が与えられず、なかなか実行できないというスタベーション(starvation)が起こる可能性がある。このスタベーションを回避するため、待ち時間が一定時間以上となったタスクの優先度を動的に高くして、実行できるようにした方式が動的優先度順方式である。優先度を高くして実行の可能性を与えることをエージング(aging)ということから、エージング方式とも呼ばれる。
ラウンドロビン方式：実行可能待ち行列の先頭のタスクから順にCPU時間（タイムクォンタム）を割り当て、そのタスクがタイムクォンタム内に終了しない場合は、実行を中断して実行可能待ち行列の末尾に移し、次のタスクにCPUを割り当てる、ということを繰り返す方式。実行可能待ち行列にあるタスクを平等に実行できるため、タイムシェアリングシステム(TSS: Time Sharing System)のスケジューリングに適している。タイムクォンタムを長くすれば到着順方式に近づき、短くすれば処理時間が短いタスクの応答時間が短くなるため、結果として処理時間順方式に近づく。
フィードバック待ち行列方式：ラウンドロビン方式に優先度を加えた方式であり、言い換えれば、多段のラウンドロビン方式である。優先度ごとにタイムクォンタムが異なる待ち行列をもつため、多重待ち行列方式とも呼ばれる。この方式では、最初に最も高い優先度を割り当て、処理が終了しない場合は、順次その優先度を低くしていく。これはCPUを占有しやすいタスクの優先度を徐々に下げるという考えだが、これによりスタベーション問題が発生するため、エージング手法などを用いての対応が必要となる。
処理時間順方式(Shortest Processing Time First)：処理時間の短いタスクから順に実行する方式。ただし、処理時間を前もって予測できないため、実際にはフィードバック待ち行列方式として実現される。

また、以下の用語も重要である。

ターンアラウンド時間：ジョブの到着から完了までにかかる総時間
レスポンス時間：ジョブの到着から最初に処理が開始されるまでの時間

ページング方式

ページング方式に関する問題は頻出である。しかし、問われる内容や形式は様々であることから、網羅的な理解が必要とされる。

ページング方式とは：

プログラムをページという固定長の単位に分割し、ページ単位でアドレス変換を行う。実行に必要なページのみ主記憶に読み込むため、主記憶の有効活用やフラグメンテーション問題の解決が期待できる。

ページング方式は仮想記憶方式（磁気ディスクなどの補助記憶を利用することによって、主記憶の物理的な容量よりはるかに大きなアドレス空間を提供する方式）を実現する方法の１つである。

仮想記憶方式を実現する方式には、他に「セグメンテーション方式」も存在し、この方式では、プログラムをセグメントという論理的な単位（大きさは可変）に分割し、セグメント単位でアドレス変換を行う。

ページング方式では、仮想アドレスと実アドレスの対応付けをページテーブルというアドレス対応表を用いて行う。

ページフォールトとは：

ページフォールトとは、プログラムがアクセスしようとしたメモリページが物理メモリ上に存在しないため、オペレーティングシステムがディスクからそのページを読み込む必要がある状況、または、その割込みを指す。ページフォールトが発生した場合、オペレーティングシステムは直ちに、物理メモリ上のページから一定の基準（最後にアクセスされてからの経過時間など）で一つを選び、ストレージ上に退避している要求ページと入れ替える処理（スワップ）を行って、プロセスがそのページにアクセスできるようにする。

ページイン・ページアウトとは：

ページを主記憶に読み込むことをページインと呼び、主記憶から追い出して補助記憶に書き出すことをページアウトと呼ぶ。

ページサイズを拡大することにより生ずる利点と欠点：

大きなサイズのページを管理できるため、ページ数を少なくでき、管理情報に使うメモリサイズを削減できる。また、管理情報の検索にかかる時間の削減が可能である。しかし、無駄に大きなページになって何も入らない場所が増えるため、ページイン、ページアウトするときにディスクアクセス量が大きくなって時間がかかり、レスポンスが低下する。

アドレス空間やページサイズは変更せずに、主記憶上に置かれるページテーブルの領域を小さく抑えるための方法：

ページテーブルを階層化する（多段ページング）。ただし、階層化により、ページテーブルアクセス時のオーバーヘッドが増加し、メモリアクセスの遅延が発生する可能性がある。

ページ置き換えアルゴリズム：

例）【仮想ページの参照順 (仮想ページ番号の並び)】 2→4→3→1→3→4→5→4→3→1→4

FIFOの場合（最も長く存在する（最も早くページインした）ページを選択する）

参照列	2	4	3	1	3	4	5	4	3	1	4
ページ枠	2	2	2	1	1	1	1	1	3	3	3
		4	4	4	4	4	5	5	5	1	1
			3	3	3	3	3	4	4	4	4
ページフォールト	1	1	1	1	0	0	1	1	1	1	0

LRUの場合（最も長い間参照されていないページを選択する）

参照列	2	4	3	1	3	4	5	4	3	1	4
ページ枠	2	2	2	1	1	1	5	5	5	1	1
		4	4	4	4	4	4	4	4	4	4
			3	3	3	3	3	3	3	3	3
ページフォールト	1	1	1	1	0	0	1	0	0	1	0

LRUやFIFOの基本的な考え方は、「その時点以降の最も遠い将来まで参照されないページがどれかを推測する」ことだといえる。

C言語

C言語プログラムの穴埋め問題がよく出題される。以下の点に注意したい。

使用されているのに、宣言されていない変数やポインタ、構造体はないか。
ポインタにすべきかどうか。

ノイマン型コンピュータ

ノイマン型コンピュータの問題も頻出である。特に、フォンノイマンボトルネックは問われることが多い。

ノイマン型コンピュータの動作：

CPUが直接実行する機械語プログラムはデータとともに主記憶に格納される。
CPUはプログラムカウンタが示す番地に格納されている命令語を主記憶から読み出し、その意味を解釈し、逐次実行する。
一般に個々の命令語は命令の種類を示すオペコードと命令の対象を示すオペランドから構成される。
オペランドが対象のデータの格納番地である場合には、これを間接アドレッシングと呼ぶ。

より具体的に、プロセッサは以下のように動作する。

Instruction fetch：命令をメモリから取得する。この段階では、プログラムカウンタ（PC）が指し示すメモリ上のアドレスから命令を読み取る。
Decode：取得した命令を解釈し、どの操作を行うかを決定する。命令デコーダがこの役割を果たし、命令のオペコードを解析して次のステップを決定する。
Operand read：命令の実行に必要なオペランド（操作対象データ）を取得する。これには、レジスタやメモリからオペランドを読み取る操作が含まれる。
Execute：実際に命令を実行する。算術演算や論理演算、データの移動など、命令が指定する操作を行う。
Write back：実行結果をレジスタやメモリに書き戻す。これにより、演算結果が次の命令で使用できるようになる。

フォンノイマンボトルネック：

フォンノイマンボトルネックとは、ノイマン型コンピュータにおけるプロセッサとメモリ間のデータ転送速度がシステム全体のパフォーマンスの制約となる現象を指す。プロセッサが非常に高速で命令を処理できる場合でも、メモリからのデータ転送が遅いと、プロセッサがその能力を十分に発揮できず、システム全体の効率が低下する問題が生じる。これにより、メモリ帯域がシステム性能のボトルネックとなり、計算能力がメモリの読み書き速度に依存してしまう。

OSI参照モデル

アプリケーション層

やりとりされたデータの意味内容を直接取り扱う。SMTP（メール）、HTTP（Webアクセス）などそれぞれのアプリケーションに特化したプロトコル。

プレゼンテーション層

データの表現形式を管理する。文字コードや圧縮の種類などのデータの特性を規定する。

セッション層

最終的な通信の目的に合わせてデータの送受信管理を行う。コネクション確立・データ転送のタイミング管理を行い、特性の異なる通信の差異を吸収する。

トランスポート層

エラーの検出/再送などデータ転送の制御により通信の品質を保証する、ネットワークアドレスはノードに対して付与されるが、トランスポート層では、ポート番号によりノード内のアプリケーションを特定する。TCPやUDPがこの層に該当する。

ネットワーク層

エンドツーエンドのやり取りを規定。MACアドレスをはじめとするデータリンクアドレスはローカルネットワーク内だけで有効であるため、ネットワークを越えた通信を行う場合に付け替える必要があるが、ネットワーク層で提供されるアドレスは、通信の最初から最後まで一貫したアドレスである。IPアドレスが使用され、グローバルにデバイスを識別し、最適な経路を選択する。

データリンク層

同じネットワークに接続された隣接ノード間での通信について規定。HDLC手順や、MACフレームの規格が該当する。物理的なネットワークの信頼性を確保する役割を持つこの層ではMACアドレスが利用され、ネットワーク内のデバイスを識別する。

物理層

最下位に位置し、システムの物理的、電気的な性質を規定する。デジタルデータを、どのように電流の波形や電圧的な高低に割り付けるのかといったことや、ケーブルが満たすべき抵抗などの要件、コネクタピンの形状などを定める。

DNS

DNS（Domain Name System）とは、インターネットなどのIPネットワーク上でドメイン名（ホスト名）とIPアドレスの対応関係を管理するシステム。利用者が単なる番号列であるIPアドレスではなく、日常使っている言語の文字を組み合わせた認識しやすいドメイン名でネットワーク上の資源にアクセスできるようにする。