京大 情報学研究科 社会情報学コース 2022年度 院試 解答例・解説

論理回路の読み取り

真理値表をカルノー図のように眺めると、(a) は第1ビットに依存しないことがすぐ分かる。(b) は $x_1$ を制御信号とするマルチプレクサであり、この形に直すとゲート数を自然に4個まで減らせる。

符号割当ての確認

ハミング距離3の符号なら、各符号語の半径1の球が互いに交わらない。したがって、各受信ブロックが対応する符号語から距離1以内にあることと、符号語どうしの距離が3以上であることを答案に書けば、復号の一意性を説明できる。

OS問題の採点点

用語の定義だけでは弱い。ファイル入出力では「論理単位と物理単位の違い」、スケジューリングでは「選択と制御移転の分担」、スプーリングでは「排他資源を直接保持しない」ことまで書くと、仕組みとして説明できる。

最大回数の式

二分探索の式は、探索成功だけを見るか、不成功探索の葉まで含めるかで書き方が少し変わる。答案では自分の数え方を明示すればよい。逐次探索は、整列済みかどうかにかかわらず、最悪では最後の要素まで確認する。

再帰と効率

再帰的であること自体が速さを保証するわけではない。マージソートが速いのは、分割により問題サイズが半分になり、各階層の仕事量が線形に抑えられるからである。

木の連続格納

完全二分木に近い形なら連続格納は効率がよいが、欠けた子が多いと空きセルが増える。この問題では、$L$ と $H$ が深い位置にあるため、途中に空欄が必要になる。

キューのポインタ規約

head と tail の定義は教科書により異なる。答案では「tail は次の空き位置」など規約を書いてから図示すると、同じ状態を一貫して説明できる。

NP完全の要点

「難しそう」という説明では不十分である。NP完全性は、NP所属とNP困難性の2条件から成る。特に帰着は「この問題が解ければ他のNP問題も解ける」という意味を持つ。

RSAの安全性

RSAの数学的中核はモジュラ指数であり、安全性の議論は素因数分解の困難性に置く。ただし、暗号方式としての安全性は鍵長、乱数、パディング、実装の副チャネル対策にも依存する。

弱実体の表し方

子は親がいなければ識別できず、親が退職すれば管理対象から外れる。したがって、親のキーを含む複合主キーと `ON DELETE CASCADE` が自然である。

B${}^+$木の答案

採点で重要なのは、あふれた葉の分割、不足した葉の借用、借用できないときの併合、内部節点不足による高さの減少を順に説明することである。区切りキーの具体値は採用する教科書流儀で差が出る。

条件付き独立性

ベイジアンネットワークの中心は、矢印の有無ではなく「何を条件にすると独立になるか」である。共通原因、連鎖、合流点では独立性の読み方が変わるため、具体例を1つ作って説明すると安定する。

比較問題の書き方

長所だけを並べると答案が平板になる。対象プロジェクトの不確実性、規制、契約、利用者参加の有無と結びつけて、どのモデルがなぜ有利かを書くと説得力が出る。

APとAUCの関係

再現率は関連文書を1つ見つけるたびにだけ増える。APはその増分幅を全て $1/R$ とした面積計算である。この説明を入れると、単なる暗記ではなく関係の理由を示せる。

PageRankの減衰係数

ランダムジャンプは、グラフを既約かつ非周期に近づける役割を持つ。これを0にすると、周期性や閉じた強連結成分の影響がそのまま出る。

列挙問題の注意

この種の問題は項目名だけでは不足する。各項目について「何を防ぎ、何を助けるのか」を一文で説明し、最後に似た概念を束ねると答案全体が整理される。

時期と群落構造

この問題では、事故時期が落葉広葉樹の展葉前であったことが核心である。放射性物質がどこに沈着し、その後どの経路で新しい葉や動物に移るかを順に追うと、図の大小関係を説明できる。

密度と体積

浮力は排除した海水の重さと体の重さの差で決まる。したがって、低密度で大きな体積を持つ器官ほど浮力への寄与が大きい。ただし、気体は深度で体積が変わるため、潜水動物では「どの深度で有効か」も重要になる。

手法比較

種構成の調査では、検出できないことが「いない」ことを意味しない。各手法の検出確率が種、季節、地形、行動で変わるため、複数手法を組み合わせると信頼性が上がる。

用語説明の型

各小問は定義だけでなく、どの条件でその概念が意味を持つかを書くとよい。平均と中央値なら分布形、NDVIなら植物の分光反射、陽葉と陰葉なら光環境への適応を結びつける。

事前と事後を分ける

リスク管理は「起こる前に確率と影響を下げる」、危機管理は「起こったときに被害を抑える」と整理すると書きやすい。自然災害では、両者を断絶させず、訓練と事後検証で更新することが重要である。

対数目的関数

$\log$ は単調増加なので、制約内で両変数を増やせる方向があれば最適ではない。第2問は角点最適性をKKT乗数の非負性で判定するのが最短である。

具体例の使い方

ハザードマップの議論では「便利である」で止めず、どの災害で何を判断できるかを書く。一方で、想定条件と不確実性を明示しないと、過信というデメリットを説明できない。

時間軸が本質

通常の防災計画が役割分担表になりがちなのに対し、タイムラインは「いつ」を明示する。気象や水位のように先行情報がある災害で特に有効である。

幾何と位相

幾何は「どこに、どんな形であるか」を扱い、位相は「何と何がつながっているか」を扱う。GISでは両方が必要であり、座標が正しくても隣接関係が壊れているとネットワーク解析や面管理で誤りが起こる。

情報から論じる

この問題ではNIMSの暗記だけでなく、情報が分断されたときに何が起こるかを示すとよい。危機対応では、正しい情報が正しい時点で正しい相手に届くこと自体が調整機能である。

三原則の分担

真正性は「正しい記録か」、見読性は「使える形で読めるか」、保存性は「将来まで残るか」で分けると混同しにくい。電子化では、保存しただけでは見読性も真正性も自動的には保証されない。

共有の難しさ

医療情報共有では、データを送れることと、相手が同じ意味で使えることは別である。形式、用語、患者ID、権限、監査を一体で設計する必要がある。

同じ式と違う名前

$A/G$ はAIでは再現率、医療では感度と呼ばれる。同じ数式でも、分野により「何を避けたいか」が違うため、よく使う指標の組合せが変わる。

単位の扱い

この問題では $1k=1024$、$1M=1024k$ と明示されている。画像サイズは byte、通信速度は bit/s なので、最後に8倍する点を落とさない。

システム間連携

病院情報システムでは、単体機能よりも連携が重要である。オーダ、実施、画像、レポート、会計がつながることで、二重入力を減らし、診療情報を同じ患者文脈で参照できる。