# 2021年度 大学院入試

## 対策院試科目
### 基礎科目
- 微積分
- 線形代数
- 微分方程式
- フーリエ変換
- 複素解析
- ラプラス変換
- 電磁気学1,2
- 電気電子回路1,2
### 専門科目
- 情報理論
-- 二元通信路(H26,H29,H30)/ 符号多項式(H27,H31)/検査行列(H27,H30)/情報源符号化定理(H28)/畳み込み符号器(H31)/結合確率分布(R1)/ハフマン符号化(R1)
- 信号処理
-- 信号処理システム(H26,H30,H31,R1)/窓関数(H27)/畳み込み(H28)/サンプリング(H29)
- 論理回路と計算機システム
-- 全半加算器(H26,H29,R1)/論理式・回路(H27,H30,H31)/浮動小数点表示(H27,H31)/マルチプレクサ(H28)/CPUマイクロ命令(H28)/記憶システム(H29)/パイプライン(H30)
- データ構造とアルゴリズム
-- ヒープ(H26,H29,R1)/双方向リスト(H27)/クイックソート(H27)/連結リスト(H28)/ダイクストラ(H28)/動的ハッシュ(H29)/キュースタック(R1)

## Tips
### 微積分
- **面積素 $dS$**
$x,y,f(x,y)$空間、$\bf{p}$$=p(x,y,f(x,y))$で考える
面積素$dS$は$\bf{a}$$=(dx,0,f_x(x,y)dx)$,$\bf{b}$$=(0,dy,f_y(x,y)dy)$の平行四辺形からなる、ただし$\bf{a},\bf{b}$のなす角を$\theta$とする
$dS = |\bf{a}||\bf{b}|sin\theta$
$\ \ \ \ \ =\sqrt{|\bf{a}^2||\bf{b}^2|-(\bf{a}\bf{b})^2}$
$\ \ \ \ \ =\sqrt{略}$
$\ \ \ \ \ =dxdy\sqrt{1+f_x(x,y)^2+f_y(x,y)^2}$
したがって
$$
S = \int_D dS = \int_D \sqrt{1+f_x(x,y)^2+f_y(x,y)^2}dxdy
$$
- **ラグランジュの未定乗数法**
条件式$g(x_1,x_2,..,x_n)$における関数$f(x_1,x_2,..,x_n)$の極致の求め方

$F(x_1,x_2,..,x_n)=f(x_1,x_2,..,x_n)+\lambda g(x_1,x_2,..,x_n)$
とおいたとき、
$$
\frac{\partial F}{\partial x_i}=0,
\frac{\partial F}{\partial \lambda}=0
$$
すなわち、
$$
\lambda = \frac{\frac{\partial f}{\partial x_i}}{\frac{\partial g}{\partial x_i}}=\cdots, g(x_1,x_2,..,x_n)=0
$$
を解く

### 線形代数
- **逆行列の求め方**
- 掃き出し法
行列$A$と単位行列$I$を並べた(n,2n)行列$(A \ I)$の**左半分を行基本変形で$I$に変形する**ことで右半分が$A^{-1}$になる
- 余因子を用いる
$A$の逆行列の$ij$成分は$\frac{\Delta_{ji}}{det A}$
（！）成分に注意、最後にまとめて転置してもよい
※余因子$\Delta_{ji}$
$A$のi行目とj列目を除いた行列の行列式を$(-1)^{i+j}$倍したもの

- **対角化**
与えられた正方行列$A$に対して適切な正則行列$P$で$P^{-1}AP$を対角行列とする操作
- **行列Aが正則**
$detA \neq 0$
$\Leftrightarrow rankA=n$
$\Leftrightarrow KerA=\{\vec{0}\}$ など
- **行列式の意味**
変換拡大率
- **$A$が対称行列**
$$
\langle Ax,y \rangle=\langle x,A^T y \rangle=\langle x,A y \rangle
$$
$\langle Ax,y \rangle=(Ax)^T y=x^T A^T y=\langle x,A^T y \rangle=\langle x,A y \rangle$

- 異なる固有値に属する**固有ベクトルは直交**する
$Ax=\lambda x$,$Ay=\mu x$かつ$\lambda \neq \mu$のとき、
$$
\langle x,y \rangle=0
$$
$\lambda \langle x,y \rangle = \langle \lambda x,y \rangle = \langle Ax, y \rangle = x^T A^T y =x^T Ay=\langle x,Ay \rangle=\langle x,\mu y \rangle=\mu \langle x,y \rangle$
この式を変形すると
$(\lambda-\mu)\langle x,y \rangle = 0$
$\Leftrightarrow \langle x,y \rangle = 0$

- 直交行列による対角化
固有値がすべて異なるとき、大きさ１の固有ベクトルによる直交行列で対角化できる
固有ベクトル$\{p_k\}$として、$r_k = \frac{1}{|p_k|}p_k$とおくと上記の直交行列$R$は$R = [r_1,r_2, \cdots, r_n]$となり
$$
R^{-1}AR = R^TAR=\Lambda
$$

### 微分方程式
- **特殊解**
微分方程式を満たす１つ解＝任意定数が決まっているもの
### フーリエ変換
- **テイラー展開**
$f(z)$の$z=a$を中心としたテイラー展開
$$
f(z)=f(a)+\frac{f'(a)}{1!}(z-a)+\frac{f''(a)}{2!}(z-a)^2 \cdots \\
\ =\sum_{k=0}^{\infty} \frac{f^{(k)}}{k!} (z-a)^k
$$
- **フーリエ級数・係数**
$2\pi$周期関数$f(x)$を$-\pi \leq x \leq \pi$に限定して考えると
$$
f(x) = \frac{a_0}{2} + \sum_{n=1}^{\infty} \{a_n cos(nx) + b_n sin(nx)\}
$$
ただしその係数$a_n, b_n$は
$$
a_n = \frac{1}{\pi}\int_{-\pi}^{\pi} f(x)cosnx dx \\
b_n = \frac{1}{\pi}\int_{-\pi}^{\pi} f(x)sinnx dx
$$
- **[一般化]区間[-L,L]でのフーリエ級数**
$$
f(x) = \frac{a_0}{2} + \sum_{n=1}^{\infty} \{a_n cos(n\frac{\pi}{L} x) + b_n sin(n\frac{\pi}{L}x)\}
$$
ただしその係数$a_n, b_n$は
$$
a_n = \frac{1}{L}\int_{-L}^{L} f(x)cos (n\frac{\pi}{L}x) dx \\
b_n = \frac{1}{L}\int_{-L}^{L} f(x)sin (n\frac{\pi}{L}x) dx
$$
- **パーセバルの等式**
区間[-L,L]で定義された連続な関数$f(x)$について
$$
\frac{1}{L}\int_{-L}^{L} \{f(x)\}^2 dx = \frac{a_0^2}{2}+\sum_{n=1}^{\infty} (a_n^2 + b_n^2)
$$
※導出
$\{f(x)\}^2$を「元の$f(x)$×フーリエ展開後の$f(x)$として積分」する

### 複素解析
- **コーシー・リーマンの関係式**
$z(x,y)=x+iy,\ \ f(z)=g(x,y)+ih(x.y)$の複素微分可能の必要十分条件は
$$
\frac{\partial g}{\partial x}=\frac{\partial h}{\partial y}
かつ
\frac{\partial h}{\partial x}=-\frac{\partial g}{\partial y}
$$
- **双曲線関数**
$$
sinhx=\frac{e^x-e^{-x}}{2}, coshx=\frac{e^x+e^{-x}}{2}
$$
基本性質
$$
cosh^2x-sinh^2x=1
$$
これは、$(coshx,sinhx)$が双曲線$x^2-y^2=1$上の点であることを意味する
- **留数定理**
特異点$a$の周りを一周する積分は留数さえ導ければ**留数定理**より求めることができる
$$
\oint f(z)dz = \sum_a 2 \pi i Res(a,f)
$$
- 留数
特異点$a$がｎ位の極である場合に留数を求める公式
$$
Res(a,f) = \frac{1}{(n-1)!} \lim_{z\rightarrow a} \frac{d^{n-1}}{dz^{n-1}} \{(z-a)^n f(z)\}
$$
特に１位の極に対しては
$$
Res(a,f) = \lim_{z \rightarrow a} \{(z-a)f(z) \}
$$

- **双曲線関数と三角関数をつなげる**
1. オイラーの公式によって実数の三角関数と複素数のexpとの関係をつくる
2. 三角関数に与えるものを実数$x$から複素数$z$に拡張する
3. 置き換えられる項を双曲線関数に置き換える
（例）
$sinz=\frac{e^{iz}-e^{-iz}}{2}$
$iz=ix-y$より、
$sinz=\frac{e^{ix-y}-e^{-ix+y}}{2}$
$\ \ \ \ \ \ \ \ =\frac{1}{2}(-i)\{(e^{-y}-e^y)cosx+i(e^{-y}+e^y)sinx\}$
$\ \ \ \ \ \ \ \ =\frac{e^{-y}+e^y}{2}sinx-i\frac{e^{-y}-e^y}{2}cosx$
$\ \ \ \ \ \ \ \ =coshy\cdot sinx+isinhy \cdot cosx$

### ラプラス変換
- **ラプラス変換の定義**（参考：テキストp207）
$f(t)$は$[0,\infty)$で定義され、$s$を複素数とすると
$$
\mathcal{L}[f(t)]=F(s)=\int_0^{\infty} f(t) e^{-st} dt
$$
- **ラプラス変換対**
導出できるようになれば問題なし
http://okawa-denshi.jp/techdoc/2-1-4Rapurasuhyou.htm

### 電気電子回路１
- **初期値、最終値の定理**
ラプラス関数のまま、過渡現象の最終値・初期値を得られる
$$
f(0_+) = \lim_{s\rightarrow\infty} sF(s) \\
f(\infty) = \lim_{s\rightarrow 0} sF(s)
$$
ともに、**微分関数のラプラス変換の式より求める**ことができる
具体的には$s$を$0$また$\infty$に飛ばして導く
$$
\mathcal{L}[f'(t)] = sF(s)-f(0)
$$

- **交流回路の３つの電力**
負荷にかかる電圧を$V[V]$,流れる電流を$I[A]$とする
- 有効電力$P[W]$
$$
P = VI \times cos \theta
$$
この$cos\theta$を「力率」という

- 無効電力$Q[var]$
$$
P = VI \times sin \theta
$$
この$sin \theta$を「無効率」という

### 電気電子回路２
- **MOSFET**
D：ドレイン、G：ゲート、S：ソース
**・Sに対してDの電位が高い**
**・SG間に電圧がある**
以上２つの条件を満たすとき
→　**DS間に電流$I_d = g_m V_{gs}$が流れる**
$g_m$を相互コンダクタンスという

### 情報理論
- **無記憶通信路**
各通信が独立に行われる＝その通信が次の通信に影響されない

- **通信路容量 $C_0$**
X:入力,Y:出力,入出力の分布

- **符号化率 R**
kビットの情報化系列をnビットの符号化系列に変換するとき
$$
R=\frac{k}{n}\ \ \ (<1)
$$

- **拘束長 K**
1bitの入力情報が影響を受ける範囲

- **ベイズの定理**
$$
P(B|A) = \frac{P(B)\cdot P(A|B)}{P(A)}
$$
条件付き確立から何となくわかる

### 信号処理
- **信号処理システム** $y=L[x]$ (参考：Ch3)
- **[ 線形性 ]**
定数倍が外に出る、+-算を分けられる
$$
L[c_1f_1(t)+c_2f_2(t)]=c_1L[f_1(t)]+c_2L[f_2(t)]
$$
- **[ 因果性 ]**
<=>システム実現可能
入力が入ってから出力があること＝出力が過去と現在のみに依存する
- **[ 安定性 ]（BIBO安定）**
有界入力信号に対し、出力は常に有界
$$
\int_{-\infty}^{\infty} |h(t)| dt < \infty \\
\sum_{n=-\infty}^{\infty} |h[n]| < \infty
$$
- **[ 時不変性 ]**
入力がずれた分、出力もずれる
$$
L[f(t-\tau)]=g(t-\tau)
$$

- **単位インパルス信号** ＝畳み込み演算の元
**任意の離散時間信号$x[n]$は単位インパルス信号を用いて以下のように表される**
$$
x[n] = \sum_{k=-\infty}^{\infty} x[k]\delta[n-k]
$$

- **窓関数**
窓の長さを$M$とする
- **[ 矩形窓 ]**
$$
\omega[n]=
\begin{cases}
1 \ \ (n=0,1,\cdots,M-1) \\
0 \ \ other
\end{cases}
$$
**特徴**
スペクトルは多くのピークを持ち、中央部のピークが最も高く、**両側に離れるにつれてピークは低くなる**
- **[ ハニング窓 ]**
$$
\omega^{HN}[n]=0.5-0.5cos(\frac{2\pi n}{M-1}) \ \ \ \ \ (n=0,1,\cdots,M-1)
$$

- **標本化定理**：元の波形に復元できるようなサンプリングを実現する定理
元波形の**最大周波数の2倍**を超えるサンプリング周波数を用いる
$$
2f_{MAX} < f_s
$$

- **z変換**
$$
\mathcal{Z}[x[n]] = \sum_{n=-\infty}^{\infty} x[n] z^{-n}
$$
- z変換表

- 伝達関数によるBIBO安定性判定
$\Leftrightarrow$~~伝達関数の極の実部がすべて負である~~伝達関数の極がｚ平面の単位円内側に存在すること$\Leftrightarrow$発散しない
- LTIシステムにおける**時間領域と周波数領域とｚ領域の関係**

### 論理回路と計算機システム
- **パイプラインの乱れ**
- **[ 構造ハザード ]**
**異なる命令同士で同じメモリやレジスタにアクセス**しようとする時に発生するハザード
１つ前の命令の**OFステージが終わる**まで、**IFステージの実行**を待たなければならない
- **[ データハザード ]**
先行命令の**演算結果を格納する前のレジスタにアクセス**する時に発生するハザード
１つ前の命令の**Sステージを終わる**まで、**OFステージの実行**を待たなければならない
- **[ 制御ハザード ]**
１つ前の命令の演算が**分岐結果を含む**時に発生するハザード
１つ前の命令の**EXステージを終わる**まで、**IFステージの実行**を待たなければならない
- パイプラインの乱れの例
>[構造ハザード]
>命令i) C->R2
>命令i+1) Add R1,R2,R3
>>このとき構造ハザードが発生する
- **固定小数点表示**
- 補数表現
・利点：減算を加算として行える→減算回路を使用しなくても構築できる
・ｎビットで表現できる範囲 ※０を２回表現するか否か
１の補数（$2^n-1-X$）：$-2^{n-1}+1$ ~ $2^{n-1}-1$
２の補数（$2^n-X$）：$-2^{n-1}$ ~ $2^{n-1}-1$
- 減算
あふれ（最大ビットを超える）が発生すれば無視すれば良い
- **浮動小数点表示**
mは仮数、eは指数、rは基数
$$
A = mr^e
$$
- 浮動小数点２進数
仮数部は符号を含めてｐビット（符号s=1ビット,仮数m=p-1ビット）
$\alpha$余り表現とする場合、次のように表される
$$
A = (-1)^s (1.m)_2 2^{e-\alpha} \ \ \
$$

### データ構造とアルゴリズム
- **完全２分木**（参考：テキストp36）
最大レベルを除いたどのレベルも完全に接点が詰まっており、
かつ**最大レベルで節点が左詰め**になっている２分木
- QueとStack
- Que
データを追加した順に取り出す
待ち行列的な
- Stack
新しく追加したデータから先に取り出す
一方にしか穴が空いていない筒
- 隣接行列と隣接リスト
メモリ使用量のトレードオフに注意
- 隣接行列
１箇所につき{0,1}の$1bit$で済む
- 隣接リスト
疎な(0が多い)隣接行列となるときは必要メモリ量がより少なくなる

## 所感
- 5/12
院試勉強をはじめたらしい
とりあえず各科目一周して基礎科目をメインに進める
- 6/19
研究室で基礎科目の院試模試が行われる
複素解析と電磁気がほぼ全くわからず困る、線形代数とラプラスとオペアンプは出来が良く、良し悪しに科目によって大きく差があることを確認できた
- 7月中旬まで
専門科目をメインに進める
なかだるみしたと思われる
- 8/5（本番まで13日）
昨年の過去問で院試プレを行う
基礎科目：思っていたより難しく、もっとできるつもりだったので焦る
専門科目：ほどほどにできた手応えがある~~が解答例がないので真偽は不明~~、たぶん7,8割くらい(_8/8追記_)
- 8/7
H31の過去問をする
基礎科目：数学はよくできた7,8割くらい、電気電子回路が怪しいのであらためて再勉強必要か
専門科目：数の表現は要復習
- 8/18（試験日）
9:30試験開始に合わせて7:50に目覚ましをかけるも6:30に目覚める
研究室で自習するも、忘れていた時計を取りに一度家に帰る
試験中は、換気のためにドアを開けていて、座席位置がドア前だった自分は暑さで少し朦朧とした、予想外な出来事
午前中の基礎科目は、1線形代数,2微分方程式,3複素解析,4フーリエが出題され、線形代数・微分方程式・フーリエ・電気電子回路１２を解いた
自分の調子が良かったように感じた
午後の専門科目は、信号処理・アルゴリズム・論理回路を解いた
アルゴリズムの探索の問題をやや不安になりながら解いた、もう少し教科書を使って幅広く勉強すれば良かったなと感じた
- 8/19(面接前日)
普段よりは不思議と落ちついている
点数大丈夫的な質問をされないことを祈る
服装と身なりにはしっかり気をつけて行きたい