i7_yoc's something

数学科…なのか？

モデル理論の面白い命題をちょっと紹介【Wathematica Advent Calendar 2022】

数学

この記事はWathematica Advent Calendarの7/6の記事です。(ところで何をAdventしているのだろうか...?)

こんにちは！現在数学科3年のinaです。

皆さんは数学基礎論という分野をご存じでしょうか？大雑把に言うと数学基礎論は「数学」というシステムそのものを考察対象とする数学の分野のことです。(故にメタ数学なんて呼ばれることもあるようです。) ゲーデルの不完全性定理なんかは名前を聞いたことがある、という方も多いのではないでしょうか。

数学基礎論はさらにいくつかに細分することができますが、今回はその中の「モデル理論」という分野をすこ～しだけ紹介したいと思います。

記事中に出てくる証明は読み飛ばしても大丈夫です。証明を追うというよりはむしろどんな命題があるか・それは何を意味するのか、を理解していただけたら嬉しいです！

モデル理論とは？

数学基礎論では、数学における「命題」を形式的な記号列("文"や"論理式"とよばれる *1 )にして扱います。この辺は細かい話は省略しますが、例えば

任意の\epsilon > 0に対してあるn_0 \in \mathbb{N}があり、任意のn \in \mathbb{N}に対して、n>n_0ならば|a_n-a|<\epsilonである

という命題を論理式化すると、

\forall \epsilon > 0 \, \exists n_0 \in \mathbb{N} \, \forall n \in \mathbb{N}[ n>n_0 \rightarrow |a_n-a|<\epsilon]

といった具合です。*2

さて、今作ったような論理式はあくまで"記号の列"であって、それ以上でもそれ以下でもありません。ですが例えば上に書いた記号列を見たとき、「この記号列は数列の収束を表しているんだな」と捉える人が多いはずです。これは、ただの記号の並びを実際の数学的な対象に対応づけていると考えることができます。この対応付けのことを「解釈」とよびます。

ここで重要なのは、解釈は一通りではないということです。例えば上の例では数列の収束以外の解釈は思い浮かばないと思うので、もう少し簡単な例を用意してみます。

\forall A \forall B[A \leq B \lor B \leq A]

この論理式の場合、次のような解釈を行うことができます:

① A,Bは実数、 \leqは実数の通常の大小関係(この場合この命題は真)

② A,Bは集合、 \leqは集合の包含関係(つまり通常は A \subset Bと書くようなものを記号を取り換えて A \leq Bと書いたということ。この場合命題は偽)

③ A,Bはグラフの頂点、 A \leq Bは Aを始点、 Bを終点とするパスが存在することを表す(この場合の真偽は考えているグラフによって異なる)

論理式が真になるような解釈のことを、論理式のモデルと呼びます。

コンパクト性定理

ちょっと強い定理を紹介します。(数学基礎論における)コンパクト性定理とは、以下の命題のことです:

\Gammaを文の集合とする。この時 \Gammaがモデルを持つことと、任意の \Gammaの有限部分集合がモデルと持つことは同値。

証明はGödelの完全性定理*3を認めてしまえばすぐにできますが、一回省略します。コンパクト性定理を認めたうえで、次の定理を証明してみます:

\Gammaを文の集合とする。 \Gammaがいくらでも大きい有限モデルを持てば、 \Gammaは無限モデルを持つ

(証明) 以下のような文たちを考える:

\phi_2 : \exists v_1 \, \exists v_2 [v_1 \neq v_2] (…"最低2個は元がある"みたいなことを指し示す)

\phi_3 : \exists v_1 \, \exists v_2 \, \exists v_3 [v_1 \neq v_2 \land v_1 \neq v_3 \land v_2 \neq v_3] (…"最低3個は元がある"ということ)

のように \phi_n \, (n\in\mathbb{N})を定義する。*4

集合 \Gamma_0 = \Gamma \cup \left( \underset{n \in \mathbb{N}}{\bigcup} \phi_n \right)を考えると、 \Gamma_0の任意の有限部分集合はモデルを持つことがわかる。よってコンパクト性定理から、 \Gamma_0もモデルを持つ。これは少し考えると有限モデルとはなりえないことがわかる。(証明終)

次にこの定理の帰結として、次のような面白い事実を紹介します。

有限と無限の区別はできない？

前の定理から、例えば次のような帰結が得られます:

任意の有限群で成り立つが、任意の無限群で成り立つような等式は存在しない

(証明) 群の元に関する等式 \phiを任意にとる。群の3公理を論理式化したものをそれぞれ g_1, g_2, g_3とし、 \Gamma = \lbrace g_1, g_2, g_3, \phi \rbrace とする。

\phiが任意の有限群で成り立つなら、 \Gammaはいくらでも大きい有限モデルを持つ。よって \Gammaは無限モデルを持つので、これは \phiが成り立つような無限群が存在することを意味する。*5(証明終)

何が言いたいかというと、群の元の等式だけでは有限群か無限群かを区別することはできないのです！こういうように、数学の命題について主張できるのは数学基礎論の面白いところだと思っています。

※「Gは有限群である」という命題で有限群と無限群を区別できるのでは？と思われる方がいるかもしれませんが、今回の主張はあくまで「群の等式は存在しない」と言っています。(つまり例えば aba^{-1}b^{-1}=eといった等式で、任意の有限群で成り立つが任意の無限群で成り立たないものは存在しないという意味です。) 「Gは有限群である」というのは集合論的な主張(有限と無限の定義など)を含んでいて、この場合モデルとしては群というよりむしろ集合論("集合"ではなく"集合論")を考えることになってしまいます。

Löwenheim-Skolemの定理

もう一つほどモデル理論のいい話を紹介したいのですが、そのためにLöwenheim-Skolemの定理と呼ばれるこれまた強い定理を紹介します。

論理式に用いる記号の数が可算*6であるとする。このとき文の集合 \Gammaが無矛盾なら、 \Gammaは可算なモデルを持つ。

この定理もGödelの完全性定理からすぐに得ることができます。さっき紹介したコンパクト性定理のときもそうでしたが、つまるところ完全性定理がかなり強いのです(ただし証明も大変)。詳しい人向けに言うと、完全性定理を証明する際に構築するモデルの濃度が文の集合の濃度と同じになるためこの帰結が得られます。

可算の中の非可算…??

この定理から得られるものとして、「Skolemのパラドックス」を紹介します。これは実際には矛盾は生じていないのですが、矛盾が生じていると誤解されがちな例です。

集合論の授業や教科書で、「集合とはものの集まりのことです」みたいなあいまいな説明をされてもやもやした経験はないでしょうか？しかし実は、集合を扱うための「集合論の公理」というものがあります。有名なのはZFC*7と呼ばれるものです。詳細は「公理的集合論」などで調べてください。

集合論の公理(例えばZFC)の文全体を \mathcal{L}^{set} とします。これに出てくる記号の数は可算*8で、またこの公理系は無矛盾であると信じられています*9。よって先ほどのLöwenheim-Skolemの定理から \mathcal{L}^{set} は可算なモデル \mathcal{N}を持ちます。つまり、「集合全体」として可算集合を選ぶような解釈が存在するわけです。

...と、ここで何か気づきませんか？そう、集合は数えきれないほど多くあるのにもかかわらず、集合全体の個数が可算であるような解釈が存在するのです。

もう少し具体的に何が考えてみましょう。例えば集合論の公理からは、「集合は少なくとも非可算無限個存在する」という主張が言えるはずです。しかし、 \mathcal{N}は可算であるにもかかわらず、この文が真になるような解釈なのです。さて、この状況にどうやって対処しましょうか？

これは結構説明が大変なのですが、まずは次のような図を見てください。

ポイントは、" \mathbb{N}から「集合全体」への全単射*10は存在しない”という主張を、どこでしているのかということです。

先ほど述べた通り、可算なモデル \mathcal{N}の中では、集合は非可算個あることが証明できます。一方”集合は可算個”と言っている場合、僕らはそのモデルの「外から」考察を加えているわけです。モデル理論自体も集合論で扱えるので、メタ的な視点からモデルを考えているということもできます。

この辺の話は慣れていない人にとってはちんぷんかんぷんだと思いますし、自分も記事を書こうとして頭がこんがらがり、「本当にわかっているのか...??」と思いました。もしかしたら僕の説明が間違っている可能性もあると思うので、その際はご教示いただければ幸いです。

簡単に要点をまとめると、

①モデルについて考えるということは、「論理式を解釈した世界」について外側から(=メタ的に)考えるということ。

②例えば集合の濃度といったものは、モデルの中で考えるか外で考えるのかによって見え方が異なることがある

ということです。いい話ですね！

おわりに

いかがでしょうか。自分の理解が甘いなと感じるところがあったり、あまりオリジナリティのある内容にはできなかったりと、いろいろ反省しております。割と教科書に書いてあることをそのまま書いてしまった感じが強いので、興味を持った人は下に挙げたEnderton先生の教科書の2.6節あたりを眺めてみてください。

参考文献

[1] Herbert B. Enderton(著), 嘉田勝(訳), 論理学への数学的手引き, 1月と7月, 2020

[2] 『数学基礎論A』(早稲田大学数学科) 講義ノート

[3] 仙台ロジック倶楽部 "数学基礎論と消えたパラドックス" https://sites.google.com/site/sendailogichomepage/files/ref/ref_07, 2022/07/05閲覧

*1:正確には文と論理式は別の概念(特別な論理式が文)なのですが、あまり気にしなくていいです。

*2:本当はこの辺も細かい定義づけが必要なのですが本質でないので割愛

*3:有名な不完全性定理とは全然別のものです。

*4: \phi_1が気になる方は適当に定義してください。(例えば \Gammaの中の適当な文など)

*5: g_1,g_2,g_3を満たすので、 \Gammaのモデルは群になります。

*6:集合が可算であるというのは、簡単に言うと自然数と同じくらいの大きさであるということです。例えば整数や有理数は可算集合ですが実数はそうではありません。

*7:ZFCのCは選択公理と呼ばれる有名な命題のことを指しています。選択公理を認めない立場もあるようで、選択公理を排した公理系はZFと呼ばれています。ZとFはともに人名由来です。

*8:書いている途中ここで"ほんとか...?"となりましたが、解釈するときの各記号への集合の割り当て方が非可算無限通りあるというだけで、記号自体は可算個で済みます。一つの文に非可算無限個の記号が出てくることはないので。

*9:Gödelの不完全性定理があるので、ZFCの無矛盾性は実は証明できないというこれまた面白い事実があります。ほとんどの数学者はZFCが無矛盾だと信じてはいるようですが

*10:集合全体は標準的な解釈によれば集合ではないので、この表現方法はちょっと怪しいです

TOEFL ~その2~

その他

↓これの続きの話です。

i7-yoc.hatenablog.com

さて、前回のTOEFLが終わって半年以上経ちますが、それなりの進捗を出すことができたので記事でも書こうかなと思います。

前回からやったこと

・英単語3800のLv.1~Lv.3を一通り学習

・Listeningのシャドーイングの練習

・Writingの練習

・全体的な演習量の強化

が主な内容です。

単語

TOEFL対策の定番本(らしい)3800をやっと購入。

www.obunsha.co.jp

マイペースなので、9月~12月かけてやっとLv.3まで一周。ネットで色々調べると1か月とか2か月とかで全部回している人もいてすごい。 1回やっただけだと結構忘れます。3周くらいしていますがいまだに7割くらいしか頭に入ってません。携帯アプリの単語帳買って補強しようか迷いましたが結局買いませんでした。

Listening

個人的にListeningを伸ばす一番のコツはシャドーイングだと思います。僕は後述するTPOで練習しました。特に1問目と3or4問目に来るConversationのタイプが苦手なので、このPassageで集中的に練習しました。 あとはノート取りももちろん大事です。コツは、単語を書くことだけに意識が向きすぎてその間の会話を聞き逃さないようにすること。メモは文章である必要はなくて、単語だけで十分です。

Writing

Writingは今まで何故伸びなかったかがわからなかったので、とりあえずトフルゼミナールの問題集を購入。

tofl.jp

これが結構いい本で、なぜ今までのWritingが駄目だったかよくわかりました。一言で言うと、Integratedは構成が不安定で、Independentは具体例が少なく一般論ばかりで作文を組み立てていたことですね。あとは時間がいつもギリギリだったこと。 問題集で基礎演習を積んだり解答例を自己添削した後、ひたすらTPO周回です。

演習量の強化

TOEFLに限らず競技数学・プログラミング(、入試？)など様々なことに言えると思うのですが、過去問を解くことよりも効果のある勉強はないと思っています。 で、どこに過去問があるの？という話ですが、TPO(TOEFL Practice Online)というサービスがあります。これは実は2つのものを指していて、一つはTOEFL公式が提供するプレテスト。1回5000円くらいしますが、公式の採点(ただしSpeakingとWritingは機械採点)が受けられます。もう一つは中国のサービスで、中国人向け？にTOEFLの過去問を公開している場所があります。ですがうまいことやると日本人でも使えます。詳しくは各自調べてみてください。

TPOで成果確認

3月にTOEFLがあるのですが、その前に成果確認がしたかったのと、自信が欲しかったので、2月にTPO(officialな方)を受験しました。

<結果>

日時 Total Reading Listening Speaking Writing
2020/12 66 19 14 16 17
2021/6 80 22 21 20 17
2022/2 103 29 25 21 28

ということで、念願の100点突破！！PracticeなのでUnofficialなスコアとはいえ、とても嬉しかったです。

(Speaking以外は)かなり成果が出ました！とりあえずSpeaking以外の勉強法は正しいとわかったのでこのまま継続。Speakingの対策を集中的に行うことにします。

Speakingの強化

Speakingがあまり伸びなかったので対策。TPOの採点は確かAIがやっているそうです(ちなみに本番は人間メイン+AIがサポート、という形らしい)。本番のスコアがどれくらいになるかは読めない部分もありますが、まあやっておいて損はないでしょう。

対策として、TOEFLのSpeakingは問題ごとに形式が決まっているので、それに応じたテンプレートを作り、実際に使う練習をしました。 具体的には、例えば1問目は短いQuestionが与えられて「Do you agree or disagree with this statement?」みたいな感じなので、テンプレートとしては、

In my opinion, I think that __________.

The main reason is that ____________.

For example, __________.

Another reason is that __________.

For example, __________.

みたいな感じです。これをSpeakingが始まる前にメモ用紙に書いておいて、始まったら穴埋めして読んでいきます。そうすることで、話している最中に全体の構成について考えずに済みます。

スクリプトを用意するときに気を付けるのは、

・ある程度文章の形で書いておく

・できるだけ簡単な・ちゃんと理解している単語を使う

です。

前者についてですが、僕は今までSpeakingの問題をやっている最中に文がうまく組み立てられず止まってしまう、なんてことがありました。それを防ぐために、ある程度文章の形をしたメモを書いておきます。ただし一字一句全部書く時間はないので、自分が見てすぐわかる範囲で適宜省略しましょう。

単語については、難しい単語を使うと話した後で「あれ、これってこの使い方であってたっけ…？」となり、不安になったりわざわざもう一度言い直したりしてしまってあまりうまくいきません(経験談)。なので、自信のない単語は使わない方がbetterです。

他の科目は今までと同じような練習をやってきました。そして3月某日、いよいよ本番！

本番

一番乗りで会場入りするために早めに家を出ます。昼食は軽めにしました。これ結構重要で、睡魔はかなりパフォーマンスに響くと感じています。

Readingは練習では5分くらいしか余らなかったのですが、本番は10分余りました。結構自身もあったのでOK。

Listeningは2or3セクションあるのですが、自分の時は3セクションでした。おそらくどれかのセクションがダミー(採点されずスコアには影響しない)だったのでしょう。最初のConversationと、Section 2のLectureが全然理解できなくて焦りました。あまりベストパフォーマンスを発揮できなかったと感じましたが、これを引きずるわけにもいかないので、気を取り直して後半戦へ。…の前に、Break timeの間にSpeakingのテンプレを作成しておきます。

Speakingはかなり順調で、全部の問題でほぼ止まらずに話し続けることができました。Writingも大きな失敗なく無事こなせたと思います。

唯一間違えたのは会場選びですね。僕は本郷の会場で受験したのですが、仕切りが浅く、Listeningの回答中に隣の人のイヤホンから音漏れしてそちらのLectureが聞こえてしまい、集中力がそがれました。あとWritingが始まったときに周りはまだSpeakingをやっていてうるさかった記憶があります。耳栓を持って行ったのでそれをつけながらやりましたが、やはり静かなのにこしたことはないです。会場選びもネットで調べればもっと色々出てくるはずなので詳細は各自でリサーチしてみてください。

結果

日時 Total Reading Listening Speaking Writing
2020/12 66 19 14 16 17
2021/6 80 22 21 20 17
2022/2 (Unofficial) 103 29 25 21 28
2022/3 100 30 26 21 23

と、いうことで。とりあえず念願の3桁台に乗ることができました！ただ結果が出るまでは110点も夢じゃないと思っていたので、ギリギリな点数だったのは正直ショックです。

まず嬉しかったのはReading満点！ReadingとListeningの結果は試験終了後すぐにわかるのですが、めちゃくちゃ嬉しくて帰り道ずっとニコニコしてました。練習でも満点は確か1回しかとったことがなかったので、本当に嬉しかったです。(でも総合点を見ると、Readingで満点取れてなければ100点に乗らなかったわけで、そう考えると怖いね…)

Listeningも思ったほど悪くなく、2月の模試よりも1点上がりました。こちらも練習では満点とか1ミスとかでできたときもあったので、欲を言えばもっと欲しい気もしますが、まあ十分です。

ただ、SpeakingとWritingは意外と点が出ませんでした…。特にWritingはTPOで28点出せていたのに本番は23点で、なぜ…?? となっています。余裕があればもう1回受けようかなぁ。Speakingも対策した割には上がらず。これはもう少し研究が必要かもしれませんね。

ということで、一昨年から今年にかけてのTOEFL iBTの話でした。

なぜTOEFL受けてるの？なぜ高得点を目指してるの？という話ですが、ちゃんと理由があります。今後はその目的達成に向けた第2ステップに向けて、いろいろ進めていこうと思います。

ここまで読んでくださりありがとうございました！

P≠NP問題とはなにか？【Wathematica Advent Calendar 2021】

数学

Wathematica Advent Calendarの12/7の記事です。

現代の数学はとても広範で深遠な発展を遂げています。しかしそれでも、いまだに証明・反証がなされていない「未解決問題」というものが数多くあります。

例えばかの有名なフェルマーの最終定理はつい25年前までは未解決問題でした。つまり、それまではフェルマーの最終定理が本当に成り立つのか、あるいは成り立たないような反例があるのか、誰もわからなかった。

ABC予想の解決もそうですね。京大の望月教授が解決したということで、去年か一昨年に大きな話題になったと思います。あの命題も望月教授の論文が受理されるまでは「未解決問題」であり、だから名前も「ABC"予想"」だったわけです。

この2つの例はすでに解決されてしまった例ですが、今回紹介するのはいまだに未解決であるうちの一つの問題、「P≠NP問題」です。

P≠NP問題とは?

P≠NP問題とは、簡単に言うとアルゴリズムの「計算量」に関する問題です。計算量と聞いてぱっと来ない人も多いと思うので、例を挙げておきましょう。

計算量について

<例>(足し算問題) 正の整数nに対して、1+2+\cdots+nを求めたい。この計算はどれくらいの計算量で行えるか？

(「1回の計算」とは、2つの数の加減乗除を行うことを指すものとする)

この問題文に書いてある計算を実行する方法はいろいろあります。一番単純な方法としては、

(Step 1) 1+2を計算する

(Step 2) 上で求めた数に3を足す

(Step 3) 上で求めた数に4を足す

…………

(Step n-1) 上で求めた数にnを足す

という方法がありますね。この場合の計算回数は (n-1)回 となります。

つまり、この問題は高々(n-1)回の計算を行えば解ける、ということです。このとき、この問題は計算量O(n-1)で解けるといいます。

n \rightarrow \inftyとしたときはnもn-1も発散速度は変わらないので、通常はO(n-1)ではなくO(n)と書くことが多いです。ちなみにO(n)は「おーだーえぬ」と読みます。

実はこの「足し算問題」は、ほかの解き方をすることもできます。数学Bあたりで習うと思いますが、

1+2+\cdots+n=\frac{n(n+1)}{2}

という公式がありましたね。これを使うと、次のように計算ができます:

(Step 1) n+1 を計算

(Step 2) n \times (n+1) を計算

(Step 3) (1)で求めた数を2で割る

なんと、3回で計算が終わってしまいます！ここで大事なのは「どんなnに対しても」3回で計算が終わるということです。と、いうことでこの問題は計算量O(3)で解けます。3も1も発散速度が変わらない(発散しない)ので、通常は O(1)と書きます。

ちなみに、実際はどんなnに対しても計算時間が同じ、というわけではありません。人間にとってはもちろん、コンピューターにとっても、1+2+\cdots+100000000000000を計算する方が 1+2+3を計算するよりも(機械はほんの少しだけ)大変です。

その理由は「『1回の計算』とは、2つの数の加減乗除を行うことを指すものとする」というところにあります。でも実際は、例えば5桁の数同士を足し算するときはまず一の位同士を足して、次に十の位を足して、...、というように5回の計算をしていますよね。このように「桁数」を考慮していないので、一見奇妙な結果が生まれるわけです。でも大まかなイメージはつかめていただけたかと。

P問題

ここからはいろいろな「計算問題」を分類していきます。

あるkがあり、計算量 O(n^{k})で解けるような問題を「多項式時間で解ける」問題、または「P問題」といいます。例えば、さっきの足し算問題はP問題です。なぜかというと、方法1を使えばこの問題は O(n)=O(n^{1})で解けるからです。ちなみにPは英語でPolynomial(多項式)のことです。

もしある問題が計算量 O(n^{999})では解けなくても、計算量 O(n^{1000})で解けたらP問題になります。

多項式時間での計算は、(例えそれがO(n^{1000})であっても)「速い」計算とみなされます。では逆に「遅い」計算とは何か？例えば計算量が O(n!)や O(2^{n})必要な計算です。 n=1,2,3,...といった小さい数では n!や 2^{n}は n^{1000}に比べて圧倒的に小さな数ですが、nが大きくなっていくと最終的には前者の方がずっと大きな数になってしまいます。(これは、 \frac{2^{n}}{n^{1000}} \rightarrow \infty \, (n \rightarrow \infty)であることからわかります。

NP問題

一方、「答えが正しいかを多項式時間で確認できる」問題を「NP問題」といいます。NP問題であるが、P問題であるかはわからないものの例を挙げてみましょう。わかりやすいように設定を変えて、Twitterを使って考えてみます。

<例>(クリーク発見問題) Twitter上のn個のアカウントが与えられる。 k \leq nとする。 このとき、与えられたアカウントの中で、次の条件を満たすk個のアカウントの集合を発見できるか？:

「そのk個のアカウントのうち、任意の2つはFF(相互フォロー)の関係にある」

　　

この問題は、答えを見つけるのは難しいですが、もし答えが与えられたら確認作業は容易に( O(n^{2})で)できます。(理由は読者への演習問題としよう)

つまり、答えを高速に計算できるかはわからないのでP問題かの判断はまだできませんが、答えの検証は高速に行えるのでNP問題であるといえます。

ある問題がP問題なら、それは必ずNP問題にもなります。なぜなら、P問題で多項式時間で計算した答えは必ず正しいからです。なので、「まず多項式時間で答えを計算する」「次にそれが与えられたものと一致するかを調べる」ということを行えばいいわけです。

P≠NP問題

ではここで本題に入りましょう。P≠NP問題とはすなわち、

「NP問題ではあるけど、P問題ではないような計算問題はあるか？」

という問題です。言い換えると、

「答えを言われればすぐに納得できるけど、自分で答えを出すのにはとても時間がかかるような問題はあるか？」

ということです。ただし「とても時間がかかる」というのは直観と必ずしも合致しないので注意してください。

P≠NP問題の行く先

P≠NP問題の行く先として考えられる可能性は3つあります。それは、

・P=NP、つまりすべてのNP問題はP問題である

・P≠NP、つまりNP問題だがP問題ではないものがある。

・決定不能。すなわち、「そもそもP≠NP問題に対する証明・反証が存在しない」ことが証明できる。

というものです。

多くの数学者はP≠NPだろうと予測しています。P=NPなら、今までできないと思われていた多くのことができるようになり、様々な分野で大きなブレイクスルーが起きるかもしれません。

「証明・反証が存在しない」というのは少し理解が難しいかもしれません。ゲーデルの不完全性定理を知っている人はピンとくるでしょう。

ミレニアム懸賞問題

数学の世界にはこのように、解決が難しい問題がたくさんあります。P≠NP問題はその中でもトップレベルに難しいもので、アメリカのクレイ研究所によって「ミレニアム懸賞問題」に指定されています。これを解くと、なんと100万ドルをもらえるそうです！解決する自信のある方、富豪になりたい方は是非どうぞ！

ちなみにミレニアム懸賞問題は7つありますが、そのうちの1つ(ポアンカレ予想)だけが解決されており、P≠NPを含む残りの6つは未解決だそうです。

おまけ

Wathematicaが100万ドルを獲得する日もそう遠くないのかも...??

f:id:i7_yoc:20211205214644p:plain

参考資料

[1] 数学セミナー2013年12月号「P≠NP予想最前線」日本評論社, 2013

[2] Michael A. Nielsen, Isaac L. Chuang, Quantum Computation and Quantum Information, Cambridge University Press, 2010

[3] "P vs NP problem" https://www.claymath.org/millennium-problems/p-vs-np-problem Clay Mathematics Institute, 2021/12/06閲覧

TOEFL

その他

お久しぶりです。

久しぶりに何か書こうと思って、最近やっているTOEFLのことを少し書こうかなと思いました。

 

・2020/12時点のスコア

R: 19, L: 14, S: 16, W: 17   Total: 66

初回の点数です。よくはないですね。Lが特に。

で、何が敗因だったかというと、

・そもそも初回なのでどのようなものかをよく把握していなかった

・Sの話し方、Wの書き方の練習をちゃんとやっていなかったので、特に構成が悲惨だったのだと思う(よく覚えていない)

・Lに関してもメモを取る練習をあまりしていなかった

・教材代をケチって古本屋で買いあさっていたので、あまり傾向があっていなかった。特にLのpassageの長さに本番びっくりした覚えがある

 

という感じでしょうか。要は一言で言えば「精進不足」でしたね。

ということで、2回目に向けて、

 

・ListeningとSpeakingを重点的に強化。市販の教材(確かLはトフルゼミナール、SはZ会)をまずは1周して要領をつかむ。

・・・正直教材はどこのでもいい気がしてます。旺文社、Z会、トフルゼミナールの中から本屋で立ち読みして一番良さそうなのを買っただけですので。

 

・特にLに関しては「どう答えにつなげるか」よりもまず「何を言っているのか認識する」段階から始めることにした。

・・・これに関してはシャドーイングの練習がかなり有効だったと思います。この教材で勉強しました。といっても最初の1/3くらいしかやってないんですが、それでもだいぶリスニング能力が改善したような気がします。

www.kadokawa.co.jp

・Rに関しては、ぼちぼち問題を解きつつ本業の数学の方で洋書を読み始めていたのでそれでカバーできるのでは？と思っていた(甘い)。

・Wまで手が回らなかった(めちゃめちゃ甘い)

ということで今振り返るとすごくぬるい対策しかしてこなかったわけです。そして2回目(2021/6)の結果は、

R: 22, L: 21, S: 20, W: 17   Total: 80

ということで、とりあえずの目標にしていた80点にはぎりぎり届きました！やはり集中的に対策したLとSはしっかり伸びてくれました。その一方でほぼ何もしてないWに関しては点数もそのまま…

あと、2回目はHome Edition(=自宅受験)で受けたのですがこれが結構めんどくさい。始まる前の試験官とのコミュニケーションがうまくいかなかったり、休憩時間になっても試験官からの指示が全くなかったり、挙句の果てには終わって試験官に呼び掛けても何も返事がない。退出してしまったら後日ETSから「ホワイトボードを消してるのが確認できなかった。今回はスコア出すけど気をつけろよ(意訳)」的なお叱りメールが届いたりしました。次からは会場受験かなぁ。

 

で、2回目の反省ですが、

・Writingの対策という概念がなかった(????)

・そろそろちゃんと語彙を身につけたほうがよさそう。練習しているとき、選択肢の単語の意味を間違えるミスがそこそこあった。

この2点が大きいですね。

 

さて、次の申し込みもすでに済ませてあります。それまでにすべきことは、

・Writingの対策…すでに問題集を買って、Integrated Taskは大体要領を得たと思います。あとはTPOをひたすら回すのとIndependent Taskの練習

・6月に受けて以降、夏休みの間TOEFLと疎遠な生活をしていたせいでRとSの能力がだいぶ落ちているのでリハビリ。

・Rは引き続き問題演習と洋書の読書で対策。ちゃんとPrefaceなども(できる限り)自力で読むようにする

・単語はやっと王道の3800を購入。とりあえず~80までの単語は1周したが、かなり知らない語が多かった。でもその単語力でも実際に80点取れているんだから、単語ちゃんとやればもっともっと伸びるのでは？

 

ということで、今後も頑張ります！

一つの大きな機会に向けて練習していく、というのは情報オリンピックやパソコン甲子園なんかをやっていた頃を思い出しますね。自分でいうことではないですが、あの時(自分なりには)結構努力してそれなりの成果も残せたので、それが今も自信につながっている気がします。

もうすぐ二十歳の節目なのでもう一つくらい記事を書きたいですね。それでは！

こんにちは(近況を書きます)

生活

自粛生活も終わりを迎えようとしている中、皆様いかがお過ごしでしょうか。僕は課題に追われながら過ごしています。レポートをようやく書いたと思えば次は3日後が締め切りのレポートの課題図書を読まないといけませんが、その間の息抜きとしてこんなものを書いているのです。

 

今日の主題ですが、

・最近競プロをやってません

これにはいくつか理由があります。

まず単純な理由としては、学業が思った以上に忙しい、というのがあります。毎週実験レポートを書くのはなかなか大変で、だんだんと質が落ちてきてる気がします…。それとバイトを多めに入れたので精進する時間がないというのもありますが、それは結果論でして、今は精進に時間を割く必要はないと感じたからバイトを入れているのです。バイト楽しいのでいいんですが。

 

で、次の理由としては、大学では情報分野ではなく数学分野を専攻したい、というのがあります。情報科学も高校3年間でいろいろやってきて、いろいろ楽しむことができました。例えば競プロ以外にも機械学習をちょっと触ったりしました。ほんの少しですが…。あとは科学の甲子園なんかでも情報分野を担当して、それなりの成績を残せた気がします。

ではなぜ数学かというと、一言で言ってしまえば数学の学問体系が好きなんですよ。数学は学問として探求する対象として一番優れている、と思ったわけです。

少し話がそれますが、今困っていることとして物理の授業の理解度が低いという点が挙げられます。これの理由はある程度分かっていて、「何を根拠としてこういう話が出てきたのかわからない」「式変形の厳密さに欠ける」といったあたりです。(少し違うかもしれません。思っていることを正確に言葉に表すのは難しいので…)

二番目は正確な根拠が省略されているにしろ大体結果が予想できるからいいのですが、一番目で言いたいことは簡単に言えば「物理学の核心をつかめていない」ということです。

もちろん数学に関しても核心をつかんでいるといえるレベルには到底達していません。たとえて言うならば、今自分の手元にiPhoneがあるのですが、「iPhoneの機能を完全に使いこなせるわけじゃないけど、とりあえずTwitterができるということは知っているから使う」というか、そんな感じです。(数学に関しての理解はこの例よりももっとずっと浅いかもしれません。) まとめると、数学のことを分かった気になっていて、これからはそちらをメインにやっていきたい、ということです。

 

最後、これが一番大きいんじゃないかなと思いますが、競プロで充実した経験が得られたから、というのがあります。JOIに1回、PCKに2回落ちまして、競プロをはじめて1年半たってもまだ緑コーダー、という時期がありました。しかし、本気で精進すればJOIにもPCKにも本選進出することができ、AtCoderでも黄色になることができました。ただし黄色は一瞬タッチしただけで、今は青に戻ってしまいましたが。

競プロ用のTwitterアカウントを作成した時、黄色なんてものはずっと遠くにある異次元のような存在で、JOI春合宿に行くような人や東大・京大の上位層しかなれないようなものだと思っていました。しかし自分も、努力によって実力をつけ、そこまで登ることができました。(これはAtCoderの人口が増えた・ABCのRated対象が変わって黄色になりやすくなったなどの理由もあるかもしれません。またこういういい方は現代の「努力すれば必ず報われる・その逆も成り立つ」という強い主張に従順な感じがしていい気はしませんが…)

なので、今競プロをしなくても、そうなりたいと望んだ時に精進すればいずれまた今のレベル以上になれると思っていますし、ほかの分野に関しても(例えば数学なんかに関しては)結構楽観的な予測をしています。まあそのうち本当の「才能の限界」に気づいて打ちのめされる日が来るのかもしれませんが…

 

まあというわけなんですよ。ICPCなんかも出ようか少し迷っている面がありますが、まあそれはそのうち決めていこうと思います。

AtCoderで黄色になりました。

競技プログラミング

2020/3/22のABC159で黄色になりました。

f:id:i7_yoc:20200323154708p:plain

 

AtCoderを初めて約3年、67回目のコンテストでようやく黄色になりました。

せっかくなので黄色になるまでを振り返ってみようと思います。

 

・青になるまで

黄色になるためにはまず青になる必要がありますね。青になるまでの記事も昔書いたのでリンクをおいておきます。

AtCoderで青になりました。 - YoC精進記

 

・青になってから

レートの推移でわかると思いますが、青になってから一度停滞期がありました。highestからレートが150下がりました。

主な原因はAGCで0完をしてしまったことなんですが、その先もなかなかレートが戻りませんでした。

f:id:i7_yoc:20200323155405p:plain

では、どうやってこの状況から立て直したかを自分なりに分析をしてみます。

 

大きな要因として、日頃から競プロをする習慣をつけてしっかりと精進したことが大きいと思います。AtCoder Scoresで精進グラフを表示してみました。

f:id:i7_yoc:20200323155717p:plain

停滞期のあたりはちょうど精進が止まっていた時期で、精進をはじめてからはレートが伸びているのがわかります。(最近の傾きが緩やかなのは、適正難易度の問題を埋めきってしまって復習中心になっているからです。)

日頃問題を解いてないと、気づかぬうちに忘れてしまうことがたくさんあります。(特に実装面においてはこれが言えると思います。)

さて、精進を再開したきっかけですが、グラフを見ると昨年11月くらいから精進を再開していることがわかります。この時期に僕に何があったかというと…パソコン甲子園本選に行きました。そう、実はこの日から今年の2月末辺りまで100日とちょっとStreakを繋いできたんですよね(唐突な自慢)。

日頃のコンテスト(ABCとか)に慣れてくると1回1回のコンテストを軽視してしまいがちです。ですが、PCKやJOIは1年に1回だけの大会であり、僕にとっては「この大会のための」精進をするような大会でした。このような大会に出ることでより競プロのモチベーションが上がったと思います。このような大会に出ることで、もっと実力をつけたいと思えるようになり、また競プロの楽しさに再び気づくことができ、日頃から精進をしようと思えたのでした。ここになるまで精進をしてこなかったのは駄目だなと思いますが、まあ結果としてこのことに気づけたからOKみたいな面があると思います。

 

で、もうちょっと具体的な話をします。

これを見てください。

f:id:i7_yoc:20200323161140p:plain

AtCoderの過去問(ただしRatingのシステム導入後のもの)の、difficultyが青・黄色の問題を(ほぼ)全部解きました。(またもや唐突な自慢)

昔はdifficultyの表示がなかったのですが、精進から離れている間にAtCoderProblemsがdifficultyを表示してくれるようになり、適正難易度の問題を選ぶことができるようになりました。ありがたいですね。

あまり難易度の高すぎる問題を解いても解説すら理解できずにモチベを失ってしまうかもしれませんし、かと言って難易度の低い問題ばかりを埋めていても(早解きの練習にはなるかもしれませんが)実力がつくとは思えません。

ちなみに解説ACについてですが、僕は程々ならしてもOK派です。これは結果論になってしまうのですが、例えば2時間くらいいろいろ考察したが何も思い浮かばなかったとか、そういう場合に解説を見て、自分が思いつくのは不可能そうな考え方を使う問題に出くわすこともあります。例えば、僕はNimやGrundy数の概念を青になってから知りましたが、どのようにGrundy数を設定するとうまく行くか、とか、そもそもゲームの問題は基本的にどのように考えるものなのかとか、そのようなものを自分から再発明するのはなかなか大変ですしかなりの時間を要することになると思います。

ただ、解説ACは最小限に留めるべきだとも思っています。なぜかというと、先程のProblemsの画像を見てもらえばわかりますが、例えば青difficultyの問題はたかだか100問程度です。(Ratingシステム導入前の問題を含めても150問程度。) これは頑張れば普通に埋めてしまえるような量で、解説ACしたあとの演習が十分にできないと思うのです。

あとこれもあくまで自分の意見ですが、difficultyがx色のコンテスト中に解けるようになりたい場合は、その色の他に、その1つ上の色の問題も合わせて埋めるといいと思います。(つまり自分のレートの1個上まで埋めるようなイメージです。) じっくり考察して解けることと、コンテスト中に通せることはまた別です。1個上の色くらいの問題をやると、考察力に余裕が出てきて、コンテスト中に目標難易度の問題を解くことができると思います。JOIのときも同じようなことを思ってました。

自分はあまりやらなかったのですが、ばちゃをやるのも有効だとは思います。

 

とここまで参考になるかわからない文章を書いてきましたが、黄色コーダーを目指す人たちのお役に立てたら幸いです！

 

 

PCK本戦

競技プログラミング

11/9〜10にPCK本戦に出るため会津若松へ行ってきました。

 

[Day 0:11/8]

多くの学校の人たちが前泊している中、自分たちは前泊ができないので家で寝た。

 

[Day 1:11/9]

朝6:30くらいに家を出て、途中で相方と合流して新幹線へ。新幹線で適当に過去問をやろうって話になって解いたらWAが出た。

磐越西線へ乗り換え。公欠でローカル線に乗ってるのは不思議な気分。

 

顧問と合流し会津若松到着。駅から少し歩いたところにラーメン屋があったので入った。おいしかった。そのあと、バスで大学へ。案の定当日勢はほとんどいなかった。

 

開会式。両隣の学校も自分たちと同じ関東地域枠だったので少し話した。

 

さあ、ここからが本質の競技である。

僕らの作戦としては、PCKはペナルティーによって順位が結構上下するので、ある程度解いた後お互いチェックして提出、という方法で戦った。ちなみに予選もそれで成功した。

 

僕は基本的に後半担当なので6〜を解くことになっていた。先に7をみたが、N<=20の場合だけbitDPすればいいことにすぐ気づけたのでよかった。(ただbitDPは気づけても適切に実装する能力が必要なのだが。) 6はN<=40なので半分全列挙を考えた。

 

相方がある程度解いたみたいなのでPCを借りた。が、この時点で開始1時間半くらい経過していたが、まだ1問も出していなかったので、審査員特別賞対象の2をのぞく前半の問題を提出した。5だけWAが出たので先にそっちを修正した。N-KとKを混同しているだけかと思って出したら今度はTLEが出た。よく考えなくてもO(N^2)だったのでセグ木でO(NlogN)にして通す。

 

審査員特別賞の2も変なことしよう、という話になって5で使ったセグ木を2でも使い出す。まあもちろんオーバーキルでACできたが、どうやら審査員特別賞の求めるものと真逆の方向性を行ってしまったようだった。

 

6を書く。半分全列挙を書くが手元でREする。どこがおかしいのかわからなかったので先に解法により自信の持てる7を書くことにした。

 

7を書く。bitDPは案の定最初からうまくいくわけではなかったが、変数の書き間違いをいくつか直したらすぐテストケースが通った。提出すると1発AC。

 

6の半分全列挙を相方に見てもらいながらもう一度1から書き直す。手元ではテストケースが通ったのだが、提出するとWA。ここでもう時間がなかったので、コーナーケースに落とされてる可能性を考えて、変数の初期値とかをいじって提出する、をひたすら繰り返していたがACできぬまま終了。

 

6完3WA、凍結前10位。予選も凍結前10位だったのでこんなところか、って感じ。

 

懇親会へ向かう。相模原中等の人たちが同じテーブルにいたので色々話してた。あと審査員の方のうちの一人が弊校出身らしく、色々話させていただいた。じゃんけん大会で相方が結構最後の方まで残っていたので、せっかくなら図書カードを獲って欲しかったな、と思う。

 

部屋に入る。競技の時もらった風船が浮いている。まあもっとも、競技中は他チームの風船を見なくても手元のディスプレイにある順位表を見て解いた問題数を確認できるのだが。

 

日経コンの2回目があったので出た。ABはいつも通り、かと思ったがBで場合分けを忘れて4WAも出してしまった。Cが解けなかったのでDを解いた。レートが＋1だけ上がった。

 

[Day 3:11/10]

まずはモバイル部門の観戦へ。いくつか発表を聞いていたが、アプリもさることながらプレゼン力もすごい。

問題解説を聞きに行く。1〜5,7は僕の考えたのと同じ。6は半分全列挙じゃなくて普通のDPでした。悔しい。12のセグ木をいつか書いてみたいなぁ〜と思いました。

 

飯を食べる。弊校の学食にも存在する唐揚げカレーを食べました。唐揚げの衣が結構カリカリしてておいしかった(唐突の食レポ)。

 

時間があったので売店で会津大学グッズ(ペンとノート)を買った。さらに時間があったのでAtCoderをやってた。

 

表彰式とかは特に書くべきようなこともなかったのでここでおわり。