【東工大情報工学系院試】数理論理学&オートマトンと形式言語の勉強法

2023年10月27日 16:11

こんにちは、Ryopperです。私は2024年度に外部で大学院を受験しました。

受験した大学院は以下の二つです。
1. 東京大学学際情報学府先端表現情報学コース
2. 東京工業大学情報理工学院情報工学系

外部大学院受験をして感じたことは、院試は情報戦ということです。
外部生は情報が全く出回りません。私も非常に苦労しました。
来年度以降、大学院を受験する方に向けての記事を書きたいと思います。

本記事は【東工大情報工学系院試】数理論理学&オートマトンと形式言語の勉強法です

大問2(数理論理学、オートマトンと形式言語)

数理論理学、オートマトンと形式言語は大問2で出題されます。配点は300点です。情報系の基礎科目なので、非情報系から受験する方は対策が必須になります。

しかし、覚えてしまえば安定して得点が取れる科目でもあるので、頑張って対策しましょう。

頻出範囲は、真理値表、論理式の真偽、命題集合の矛盾、冠頭標準形です。
自然演繹もでますが、基本的に穴埋め問題がほとんどで難しい問題は出ません。

ユニバースの濃度を答える問題など、一般的ではない？？問題がたまにでます。(私は、非情報系学部出身なので何が一般的か知りませんが。。。)

数理論理学に関しては、特に過去問メインで学習するのが良いです。
覚えることもそこまで多くないし、典型問題しか出ないです。

後述する参考書は、初学者が全体的な知識をさらうっていう意味ではよかったです。ある程度知識がある方は、さっさと過去問に取り掛かるのが良いです。

メジャーな参考書情報は知りませんが、私は以下の参考書で学習しました。
「はじめての」と付くだけあって、かなり丁寧に書いてあり、簡単です。
2日あれば、読めると思います。ただし、第3章の自然演繹パートに関しては、少しオーバーワークかもしれません。

ただし、この本は東工大情報工学系の過去問の範囲とやや差があるので、やはり過去問メインで勉強を進めるのが良いと思います。

この分野は、結構覚えることがあります。以下の範囲全て重要です。

典型問題しか出ないのでやはり過去問メインで解くのが良いです。
初学者に限っていうと、一度簡単な参考書をさらってからの方が効率的かもしれません。(私の場合は、そうしました。)

空動作の除去, ε-NFA→NFA変換, NFA→DFA変換に関しては、理解しているつもりでも実際に解いてみると、解けないってことがあるかもしれません。理論の理解と同時に実際に手を動かして解いてみてください。

あと、ポンピング補題は、東工大情報工学系の教授たちは大好きなのかもしれません。結構頻出です。ただ、なかなか理解しにくい理論で結構苦労しました、、YouTubeでPumping Lemma検索すると結構わかりやすい動画が出てきます。(英語ですが。)

勉強時間の比重的なことを言うと、
数理論理学:オートマトンと形式言語 = 1:4
くらいが良い気がしています。

参考書をあげるとすれば以下の二冊が良いと思います。

こちらは、私が実際に使った参考書です。
「はじめて学ぶ」という言葉に相応しく、簡単です。
初学者にはちょうど良いと思いますが、先ほど理解に苦しんだと述べたポンピング補題に関する説明はないので、そこは別途補う必要があります。

こちらも、いろんなサイトでオススメされていました。
ポンピング補題に関しても書いてあるみたいです。

オートマトンと形式言語に関しても、参考書は東工大情報工学系の過去問の範囲とやや差があると感じました。なので、過去問はやり込むべきです。

今回はここまで。

大問1で出題される数学
大問3で出題されるプログラミング&データ構造とアルゴリズム
についてもについても解説しているのでご覧ください。

※記事にある商品リンクはAmazonアソシエイト・プログラムを利用しています。

この記事が参考になったらサポートお願いします！