自分とBack to the future

私の計算が正しければ―――2015年10月21日は，“Back to the future: Part 2”でドクとマーティがデロリアンで「未来」に降り立ったまさにその日だ*1．この記念すべき時に，自分とBack to the future (BTTF)の思い出について書いておきたい．


自分がBTTFを初めて観たのは小学校低学年頃であったように思う．父親がレンタルビデオ店で借りて見せてくれた中の1本だったのだろう．幼い自分は，魅力的なキャラクター，タイムマシンという概念，科学の夢と希望にあふれた世界にすっかり魅了された．今思えば，BTTFは自分を科学に目覚めさせた「事件」であった．

もちろん，小学生はこういう映画に感化されやすいものだから，科学以外にハマったものはいくらでもある．しかし，不思議なことに，他のものは飽きてしまっても，科学に飽きることは全くなかった．当然のように科学クラブに入り，家では色々な家庭実験を試し，図書館に行ってはちょっと高級な科学本を（分からないなりに）読んだ．もちろん，小学校の「将来の夢」にはドクに憧れて「科学者」と書いた．中学に入っても，初日の自己紹介では「好きな映画はBTTFです」と言い，「理科だけは誰にも負けまい」と勉強していたのを覚えている．


BTTFに出会って以来，科学への憧れはずっと自分の人生の指針となってきた．いつの間にか，自然科学から計算機科学と数学に興味が移ったものの，今は情報系の博士課程で「科学者」を目指している．ドクは自身を「科学者」と言っていたけれど，実態としては「発明家」という感じだから，自然科学ではなく工学寄りの計算機科学を志したのは，やはりドクが自分の原点にあったせいかもしれない．

劇中の2015年で描かれ，実際の2015年で実現した（もしくは凌駕した）テクノロジーを眺めてみると，コンピュータの進歩が目立つ．ホバーボードは実現せずとも，ドローン・小型カメラ・テレビ電話などは現実の2015年の方が優れているし，BTTFの2015年にはインターネットも携帯電話もなかった．情報技術の進化はBTTFの予想を超えていた．そんな，情報技術に関わる「科学者」の端くれとして，BTTFの「未来」の後の未来を作っていく仕事をしていきたいと思っている．ドクも言っていたように，未来は自分で切り開くものである．

*1:ちなみにドクが時空転移装置を思いついたのは1955年11月5日で，自分の誕生日と同じ日

2014年個人的アニメ名場面集

プリキュアメモリ

今年もあと少しでおしまいということで，今年のアニメで自分の印象に残ったシーンを挙げてみました．

『たまこラブストーリー』

やっぱり今年の一番はこれしかない．公開初日に観に行ったときの感動は忘れられないですね．あまりの素晴らしさに錯乱して1500円のおもちキーホルダー買っちゃったよ！

今年最大の勝ち組幼なじみは間違いなくもち蔵．

『一週間フレンズ。』第8話「友達と海。」

8話の海で一緒に花火するシーンが，青春って感じでとてもいいんだこれが．OPの「虹のかけら」も素敵なんだけど，このシーンの裏で流れてるピアノアレンジが一瞬止まる演出もいい！

藤宮さんは天使．

『ハピネスチャージプリキュア』前期ED「プリキュア　メモリ」

おなじみプリキュアのCGダンス．毎年バージョンアップを重ねた結果，ついに今年はアニメ絵と遜色ないCGのレベルに到達！

プリキュア・メモリ(NewStage3 Version)

プリキュア・メモリ(NewStage3 Version)

来春の劇場版は，CGメインのダンス映画っぽいし期待！

『未確認で進行形』OP

今年は『月刊少女野崎くん』でも話題になった動画工房．「恋心入っちゃった」のカットがとても好きです．

私は紅緒様もけっこう好きです．

『ラブライブ！』「snow halation」

今年のアイドルアニメではラブライブが強かった！スクフェスのおかげで，2期からはアニメ観ない層にも浸透した感じがありますね．

（これは昔の）
Wake Up Girlsは悪い意味で印象的だった・・・

『四月は君の嘘』第4話

これぞアニメーションという感じの演出だったのが，『四月は君の嘘』のピアノの音が聞こえなくなっていくシーン．これ，実際にピアノを沈めても演奏してもこんな絵は撮れないし，アニメーションだからこそできる印象的な表現だった．

天真爛漫な女の子に振り回されるのも，中学生の青春って感じで，いい．


来年も良いアニメがたくさん観れるといいですね．皆様，良いお年を．

Schwartz-Zippelの補題

数学

自分のお気に入りの補題のなかにSchwartz-Zippelの補題というものがある．代数，確率，それに組合せ的な話が出てきてとても楽しい補題である．日本語の文献が少ないようなので，ここで紹介しておきたい．補題のStatementは以下の通りである．

Schwartz-Zippelの補題
$p(x_1,\dots,x_n) \neq 0$ を体 $\mathbf{F}$ 上の $n$ 変数非ゼロ多項式とする．$S$ を $\mathbf{F}$ の有限部分集合とし， $r_1, \dots, r_n$ を $S$ から独立かつ一様ランダムに選ぶとする．すると $\mathrm{Pr}(p(r_1, \dots, r_n) = 0) \leq \frac{\mathrm{deg}(p)}{|S|} $ である．

（証明）$d := \mathrm{deg}(p)$とする． $n$ に関する帰納法で証明する．$n=1$ の場合は，$d$ 次多項式は高々 $d$ 個の根しか持たないことから明らかである．$n - 1$ まで正しいとして， $n$ の場合を示そう．$p$ を $x_1$ に関して整理して次のように分解する:
\[
p(x_1, \dots, x_n) = \sum_{i=0}^k x_1^i p_i(x_2, \dots, x_n)
\]
ただし，$p_k \neq 0$ とする．ここで， $A$ を $p(r_1, \dots, r_n) = 0$ となる事象， $B$ を $p_k(r_2, \dots, r_n) = 0$ となる事象とする．$p_k$ の次数が高々 $d-k$ であることに注意すると，帰納法の仮定から $\mathrm{Pr}(B) \leq (d-k) / |S| $. 一方， $p_k(r_2, \dots, r_n) \neq 0$ であるとすると， $A$ が起こるためには $r_1$ は 1変数 $k$ 次多項式 $\tilde{p}(x_1) = p(x_1, r_2, \dots, r_n)$ の根でなければならない．そのような確率は $n=1$ の場合から $\mathrm{Pr}(A \mid \bar{B}) \leq k / |S| $ である．これより
\begin{align*}
\mathrm{Pr}(A) &= \mathrm{Pr}(A \mid B) \mathrm{Pr}(B) + \mathrm{Pr}(A \mid \bar{B}) \mathrm{Pr}(\bar{B}) \\
&\leq \mathrm{Pr}(B) + \mathrm{Pr}(A \mid \bar{B}) \\
&\leq \frac{d-k}{|S|} + \frac{k}{|S|} = \frac{d}{|S|}
\end{align*}

応用

この補題の面白い使い方として，次のようなものがある． $A$ を各成分が $x_1,\dots, x_n$の $\mathbf{F}$ 係数多項式であるような行列としよう．このとき $\det A$ は多項式となるが，これが非ゼロであるか判定するにはどうしたら良いだろうか？掃き出しをやろうとすると，成分が $x_1,\dots, x_n$ の複雑な有理関数となってしまい，多項式時間ではできない．しかし，Schwartz-Zippelの補題によると，$\mathbf{F}$ が十分に大きければ（たとえば $|S| > 2 \mathrm{deg}\det A $ となる $S \subseteq \mathbf{F}$ が取れるならば）， $x_1,\dots, x_n$ に一様ランダムに値を代入して得られる定数行列 $\tilde{A}$ の行列式を計算して，ゼロか非ゼロか判定するだけで，片側誤り確率 $1/2$ 未満で正しく判定できる！

実は，$A$ を工夫して作ると $\det A = 0$ の判定によって無向グラフの完全マッチングの存在判定ができることが知られている（そのときに使う行列は Tutte行列 と呼ばれている）．完全マッチングの多項式時間アルゴリズムは実装がとても大変だが，判定だけであればこんな方法で簡単にできる．


参考文献
乱択アルゴリズムといえばこれ

  • Motowani, Raghavan, “Randomize Algorithms”

Schwartz-Zippelの補題の歴史が載っている