院試の過去問の解答案 - 失われた一般性を求めて

院試のコンピュータサイエンスや数学基礎論の問題の解答案（解答例？）です．問題そのものは大学のホームページ

過去の入試問題 | Department of Mathematics Kyoto University

令和４(2022)年度修士課程入学試験について | 東京大学大学院数理科学研究科理学部数学科・理学部数学科

を見てください．

誤りや指摘等有ればご連絡いただけると助かります．解答を挙げているだけなので著作権の問題はないと思いますがそれに関しても指摘があればご連絡ください．

院試が終わって気が向けばTex打ちするかもしれません．

更新履歴
京都
東京

更新履歴

2022-07-22 kyoto2022-2017, tokyo2022-2020を含むこのページを公開．kyotoはさらに遡って解いたものを追加する予定．

2022-07-28 kyoto2016-2012を追加．これ以上遡るかは未定．

2022-08-01 目次を付けた．

京都

2022年度⑩

fは頑張ってbを右に右にと送っているのですが，bがたまってしまうと1個だけ右に送る代わりに残りは最左端に戻されてしまいます．fがとても不憫です．

2020年度⑩

原始再帰的関数についての問題です．(2)はそのままでは再帰的な定義ではないのでパラメータを増やす必要がある，ということに気づけば手を動かして解けます．

2019年度⑪

直観的には難しくないですが実際に整礎な順序を定める段階で苦戦しました．もう少し良い解法がありそうです．（こういうのは競技プログラミングとかやっていると有利？）停止することの証明で疲れてしまい，ループ不変条件のチェックは清書してません．

2018年度⑩

グラフの各点に対しその連結成分の値の最大値を計算するプログラムです．グラフの隣接行列を知っていれば思いつきやすいです．（とはいえ私はsemiringの行列の問題だということを解く前に聞いていたのですが．）

2017年度⑩

厳密な対応はわかりませんが， $\mathcal{T}$ のterm $M$ に対する $[ M]$ 達はintuitionistic implicational logic (直観主義含意論理？）の公理スキームを与えていると思えます．また， $f$ はmodus ponens，つまり， $f(M,-)$ が公理 $M$ の適用を表していると思えます．これに気づけば正誤の見当はつきます．公理スキームは代入に閉じていることから $X_1$ はダメ，恒真でない論理式を含むことから $X_2$ もダメでこれは $\to$ の前件と後件のバランスを調べれば示せます． $X_3$ は大雑把に言って二重否定除去（bを矛盾と思う）ですが，これは直観主義論理体系の公理からは導出できないはずで，実際 $\to$ の前件への入れ子の度合（ $(((0\to 0)\to 0)\to 0)$ は前件への入れ子が3重になっている．）を調べれば示せます． $X_4$ はなんとなく正しそうですね．（まあ性善説を信じて1つ位は合ってるだろうと勘ぐるのも一つですが．）