# 東京科学大（旧東工大） 情報理工学院 情報工学系 専門科目（情報工学） 2024年度 院試 過去問 解答例・解説

> 東京科学大（旧東工大） 情報理工学院 情報工学系 専門科目（情報工学） 2024年度の院試過去問、3項目の解説。テーマは重積分と極座標、正定値行列。大問1問の途中式・最終答を無料公開。解答PDFは6年分収録で3,200円。問題本文は非収録。

- Web版: https://inshihub.com/exam-solutions/institute-of-science-tokyo/school-of-computing/computer-science/2024
- 解答・解説PDF: https://inshihub.com/exam-solutions/institute-of-science-tokyo/school-of-computing/computer-science（税込3,200円、6年分を収録）
- 最終更新: 2026-11-19
- 公式の過去問: https://admissions.isct.ac.jp/ja/013/graduate/examination-questions（主に2021〜2025年実施（数学系は2020〜2024年実施）、公式の解答例: 解答例の掲載なし）
- 問題本文は収録していません。公式の問題と照らして読んでください。
- 大問ごとの解説は無料公開です。途中式と最終答は、ここに載っている大問を除き解答PDFに収録しています。

## 第1問 — 行列式・二次形式・変数変換

### 解説

**行列式の積**

逆行列を含む積では，$\det(AB^{-1})=\det A/\det B$ を使う。
条件 $c\ne0,\ d\ne24$ は，右側の行列が正則であることを保証するために与えられている。

**二次形式の勾配**

対称行列 $Q$ に対して $\frac12x^{\mathsf T}Qx$ の勾配は $Qx$ である。
停留点の一意存在は線形方程式 $Qx=-c$ の一意解の問題であり，最小性はヘッセ行列 $Q$ の正定値性で決まる。

**密度の変数変換**

ロジスティック変換は単調なので，逆関数とヤコビアンで密度を移せる。
値域の端点を入れ忘れると，密度の式は正しくても確率分布として不完全になる。

**採点の置き所**

行列式では逆行列を展開せず，分子と分母の行列式へ分けることが第一の得点源である。
二次形式では勾配，一意性，最小性をそれぞれ $Qx+c$，正則性，正定値性に対応させる。
変数変換では，逆関数，ヤコビアン，値域の三つを漏らさず書く。

**検算**

停留点は，求めた $(-9/7,-4/7)$ を $2x_1-x_2+2=0$，$-x_1+4x_2+1=0$ に代入して確認できる。
$f_Y$ は値域全体で積分すると，単調変換の公式により元の一様分布の全確率 1 に戻る。

### 解答

-

$$
P=
    \begin{pmatrix}2&0&0\\13&5&a\\25&8&b\end{pmatrix}
    \begin{pmatrix}c&3&4\\0&9&27\\0&24&3d\end{pmatrix}^{-1}
$$

  なので
  

$$
|P|=\frac{
    \det\begin{pmatrix}2&0&0\\13&5&a\\25&8&b\end{pmatrix}}
    {\det\begin{pmatrix}c&3&4\\0&9&27\\0&24&3d\end{pmatrix}}.
$$

  分子は
  

$$
2(5b-8a)=10b-16a
$$

  であり，分母は
  

$$
c(27d-648)=27c(d-24)
$$

  である。したがって
  

$$
|P|=\frac{10b-16a}{27c(d-24)}.
$$

-

$$
h(x)=\frac12 x^{\mathsf T}Qx+c^{\mathsf T}x+3
$$

  で $Q$ が対称なので
  

$$
\nabla h(x)=Qx+c
$$

  である。指定された
  

$$
Q=\begin{pmatrix}2&-1\\-1&4\end{pmatrix},\qquad
    c=\begin{pmatrix}2\\1\end{pmatrix}
$$

  では
  

$$
\frac{\partial h}{\partial x_1}=2x_1-x_2+2,\qquad
    \frac{\partial h}{\partial x_2}=-x_1+4x_2+1.
$$

  これらを $0$ とおくと
  

$$
2x_1-x_2=-2,\qquad -x_1+4x_2=-1
$$

  であり，
  

$$
x_1=-\frac97,\qquad x_2=-\frac47
$$

  を得る。

方程式 $Qx+c=0$ の解が存在し一意に定まるための必要十分条件は
  $Q$ が正則であることである。さらにその点で $h$ が最小値をとるための必要十分条件は，
  $Q$ が正定値であることである。

- $X$ は $[-1,1]$ 上の一様分布なので
  

$$
f_X(x)=
    \begin{cases}
      \frac12,& -1\le x\le1,\\
      0,&\text{otherwise}
    \end{cases}
$$

  である。
  

$$
Y=\frac1{1+e^{-X}}
$$

  は単調増加変換であり，逆変換は
  

$$
x=\log\frac{y}{1-y}
$$

  である。また
  

$$
\frac{dx}{dy}=\frac1{y(1-y)}.
$$

  $x\in[-1,1]$ に対応する $y$ の範囲は
  

$$
\frac1{1+e}\le y\le \frac{e}{1+e}
$$

  である。よって
  

$$
f_Y(y)=
    \begin{cases}
      \displaystyle \frac{1}{2y(1-y)},&
      \displaystyle \frac1{1+e}\le y\le\frac{e}{1+e},\\
      0,&\text{otherwise}.
    \end{cases}
$$

### 最終答

$|P|=(10b-16a)/\{27c(d-24)\}$。$\nabla h=(2x_1-x_2+2,\,-x_1+4x_2+1)^{\mathsf T}$，停留点は $(-9/7,-4/7)$。停留点の一意存在は $Q$ 正則，最小値条件は $Q$ 正定値。$f_X=1/2$ on $[-1,1]$，$f_Y(y)=1/\{2y(1-y)\}$ on $[1/(1+e),e/(1+e)]$。

## 第2問 — 文法・オートマトン・論理

### 解説

**導出木の左右順**

文法にある乗算規則は $T\to T\times F$ であり，左側が再び $T$，右側が $F$ である。
木のラベルが同じでも，左右が入れ替わると別の規則を使ったことになる。

**正規文法とNFA**

右線形文法の規則 $X\to aY$ は，状態 $X$ から入力 $a$ で状態 $Y$ へ進む遷移に対応する。
規則 $X\to a$ は，入力 $a$ で受理状態に入る遷移と考えればよい。

**無矛盾性の示し方**

矛盾しないことを示すには，導出が存在しないことを直接示すより，すべての仮定を真にする真理値割当てを一つ与える方が簡潔で確実である。

**採点の置き所**

導出木の正誤判定では，葉の文字列だけでなく，内部節点が許された生成規則に合うかを確認する。
正規文法とNFAの対応では，非終端記号を状態，終端記号をラベル付き遷移と見て空欄を埋める。
無矛盾性では，矛盾する集合は導出列，無矛盾な集合はモデルを示すと明快である。

**典型ミス**

第2式は，関係を満たす二要素の間に別の要素があるという稠密性を表す。整数の隣り合う二数の間には整数がないが，有理数なら中点 $(x+y)/2$ が入る。「共通上界が存在する」という条件へ読み替えない。じゃんけん型関係は循環し，第1式の推移性も満たさない。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/institute-of-science-tokyo/school-of-computing/computer-science

## 第3問 — 計算量と二分探索木

### 解説

**計算量の支配項**

多項式同士では次数が最大の項が支配し，$n^{\log n}$ は任意の固定次数の多項式より速く増える。
$\sin^2 n$ は 1 以下なので，上界評価では $n^2 2^n$ で押さえるのが自然である。

**BST の重複値**

挿入コードは `data > p->data` のときだけ右へ進み，それ以外は左へ進む。
したがって等しい値は左部分木へ入る。この条件を読み落とすと，重複を含む配列の高さが変わる。

**AVL 回転**

右右型は左回転，左左型は右回転で直せる。
右左型・左右型では，まず子側を逆向きに回転してから親を回転する二重回転になる。
回転後も二分探索木の大小関係を保つよう，子の部分木を親側へ付け替える点がコード上の要である。

**採点の置き所**

計算量比較では，対数，多項式，指数，階乗の階層関係を使って並べる。
BST では重複値の扱いをコード条件から読み，挿入順に木を描くと高さの根拠になる。
AVL 木では不平衡の型を判定してから，単回転か二重回転かを選ぶ。

**検算**

通常 BST の高さは，挿入後の最長根葉パスを実際にたどって確認する。
AVL 木の高さが通常 BST より小さくなること，かつ各節点の左右部分木高さ差が 1 以下になることを確認すると，
回転の向きの誤りに気づきやすい。

途中式と最終答は解答PDFに収録しています: https://inshihub.com/exam-solutions/institute-of-science-tokyo/school-of-computing/computer-science

---

出典: 院試hub（https://inshihub.com/exam-solutions/institute-of-science-tokyo/school-of-computing/computer-science/2024）。引用するときはWeb版のURLを示してください。
