東大 情報理工学系研究科 創造情報学専攻 創造情報学 専門科目 2025年度 院試 過去問 解答例・解説（全3問）

8項目のうち，ここでは基数ソート，左辺値と右辺値，モデル検査，暗号学的ハッシュ関数の 4項目を選ぶ。

1. 基数ソート 基数ソートは，整数や固定長文字列のように桁へ分解できるキーを，桁ごとの安定ソートで 整列する方法である。下位桁から処理するLSD方式では，各桁で安定性を保つことで，すでに 整えた下位桁の順序を壊さずに上位桁へ進める。桁数を $d$，各桁の取り得る値の数を $k$，データ数を $n$ とすると，計数ソートを内部に使えば時間計算量は $O(d(n+k))$ である。比較ソートではないため $O(n\log n)$ の下限に縛られないが， キー表現と補助配列の大きさに依存する。
2. プログラミング言語における左辺値と右辺値 左辺値は，代入の対象になれる記憶場所や参照を表す値であり，変数名や配列要素などが 典型例である。右辺値は，計算結果として得られる一時的な値や，式の値として読み出される ものを指す。たとえば $x=a+b$ では，$x$ は書き込み先としての左辺値であり， $a+b$ は計算結果としての右辺値である。C++のような言語では，右辺値参照を使って 一時オブジェクトの資源をムーブできるため，単なる文法用語ではなく性能にも関わる。
3. モデル検査 モデル検査は，システムを有限状態遷移系として表し，安全性や到達可能性などの性質を 論理式で与えて，その性質が全状態で成り立つかを機械的に調べる手法である。性質が 成り立たない場合には，反例となる実行列を得られるため，並行プログラム，通信プロトコル， 制御ソフトウェアの検証に向く。典型的には時相論理を使い，「いつか応答が返る」 「危険状態には到達しない」といった条件を記述する。課題は状態爆発であり，抽象化， 記号表現，部分順序削減などで探索空間を抑える。
4. 暗号学的ハッシュ関数 暗号学的ハッシュ関数は，任意長の入力から固定長のダイジェストを計算する関数であり， 改ざん検出やデジタル署名，パスワード保存の基礎に使われる。重要な性質は，出力から 入力を復元しにくいこと，特定の入力と同じ出力を持つ別入力を見つけにくいこと，任意の 衝突を見つけにくいことである。入力が少し変わるだけで出力が大きく変化する性質も重要で， これは雪崩効果と呼ばれる。暗号化とは異なり復号を目的としないため，秘密を戻せる形で 保存する用途には使わない。