数理の苦手意識とその改善方法について

はじめに

数学や理科、いや特に数学の勉強方法についてかなり思うところがあるので、ここで述べたい。 前提として、私は LINE のオープンチャットで「東大生が勉強を教える！」のような名前のルームを開き、そこで勉強方法や具体的な教科ごとの質問から、人生相談的なものまで対応している。（段々とルーム内のメンバー同士で教え合うようになったので、全てに返事しているわけではないが。）また、大学でも、数学や理科が苦手な人と話す機会が多くある。個別教師や家庭教師を通しても、多くの人を見てきた。

塾講師の方が多くの生徒を見ているぜ！と思う方もいるかもしれない。それはそうだろう。しかし、数学の勉強方法について、それほど深く見ていないはずである。強力な根拠として、そもそも塾講師が数学のより良い勉強方法をご存知ない、と言うことが考えられるだろう。

アメリカでは、勉強の方法を学校で教えると聞く。私が学校に通っていた頃、「勉強しろ勉強しろ」と教師に言われはしたが、具体的にどうやって勉強したらいいか、教えられたことはなかった。今思えば、教師自体が知らなかったからだろうなぁ。勉強の仕方を理解している人たちは、おそらく学習欲が非常に強く、研究職などの、教師以外の職に就くことが多いのかもしれない。推測に過ぎないが。そんな社会において数学の勉強方法を紹介するといった重要な役を担いたい。ひいては、勉強の重要性を説明できるようになりたい。

本記事では、数学の勉強方法について、ぼんやりと方向性を示せることを目標に、つらつらと述べていきたい。まとまったものができるかどうかはわからないが、やってみたい。

数学の苦手意識の本質

よくある数学に苦しめられる例から考えたい。

三角関数で挫折するような人々

数学が苦手（or 得意になりきれない）人は、共通して高校数学 2 の三角関数の分野で挫折していることが多いと思う。（僕調べ。） その理由としては、次のようなものが挙げられるだろう。

• 急に出てきた sin, cos が一体なんなのかわからない
• 三平方の定理があればいらなくない、、？なんでわざわざ、、？
• 加法定理とか出てきたけど、これは何で成り立つの、、？積和公式＆和積公式？？何で？何で成り立つん、、？

とまあざっとこんな感じ。こういった人々の考え方の問題点と解決策をそれぞれ示していく。

数学が苦手な人の考え方の問題点と打開策

• 上の考え方の問題点
  • sin, cos が一体何で何のためにあるのかにこだわり過ぎて、問題演習で手を止めてしまう。
  • よく知らないものが同時に複数出てきた時に、思考を諦めてしまう。
  • 自分だけが理解できていないと思って焦ってしまう。みんな急に出てきた概念に戸惑うに違いないのに。
  • 必要性がわからないと、無意味だと切り捨てて思考を止めてしまう。
  • まとめると、新しいものを受け付ける耐久力が低い。そのせいで、複数の新しい概念が同時に登場することによって思考が停止する。
    • そういった人々は、新しい概念が同時多発的に出てこない英語や国語の方ができる可能性が高く、自分には理系としての適性がないのではないかと思って数学の勉強をよりやめたくなる。
• 改善方法
  • 新しい概念が出てきた時、焦らない。みんなわからない。自分だけがわからないなどと思わない。
  • 新しい概念を使うとき、それの存在意義や成立する理由などを気にせず、とりあえず言われた通りに使ってみる。頭を動かそうとして思考が停止するくらいなら、まずは手を動かせば良いんです。
  • （数学は特にそうだが、）新しい概念が出た時にその意義にこだわらない。数学では、毎回毎回なんのために勉強しているのかわからないテーマばかりである。それらを十分身につけた瞬間に初めて、その意義を体感できる。数学が好きな人は、その視界が急に開ける瞬間が好きなのだと僕は思う。

このように、数学が苦手な人は新しい概念を受け入れる力が弱い。若いうちはまだ良いが、歳をとるにつれてさらに新しい概念への耐性は弱まり、現代においてスマホを避ける高齢者がいるように、新しい技術や製品なども避けるようになっていくだろうと考えられる。多少言い過ぎではあるだろうが、数学が得意な人は、新しいものを積極的に利用し、時代に追いついていくのが好きという傾向があるかもしれない。

数学を教える人に持ってほしい心構え

数学を教える教育者としての視座を高めたい。

僕が数学教育における目標として重要だと思っているポイントは、次のようなものがある。すなわち、

• 「わからない」で焦らないような耐久力

この力を得るためには、「わからない」を乗り越えたとき、大きくステップアップできるという感覚の経験が必要である。成功体験が必要なのである。これを身につけた学生は、困難に直面しても、それを乗り切った後の気持ちよさを知っているため、困難に立ち向かい、「わからない」と向き合いながら問題解決に努力できる。そうではない学生は、少量の「わからない」に直面しただけで逃げ出し、なるべく「わからない」が少ない方向へ行こうとする。「わからない」から逃げている以上、大きなステップアップの機会は少ないと考えられるため、なかなか厳しい未来が待っているかもしれない。（可能性の話です。）

これを実現するための方法を教師は常に考える必要があると思う。 実際に生徒のタイプ別の方法論を書いてみる。

• 難しい問題を解けた時の喜びを知っている生徒
  • すでに一定水準の「わからない」耐久力を持っている。少しずつ限界を高めるように、少しずつより発展的な問題を与えてあげる。しかし、急にレベルアップしすぎると、逆に根強い苦手意識を植え付けてしまったり、アイデンティティの喪失だと信じて嘆いたりしてしまうかもしれない。少しずつ、その生徒にあった幅で問題の難易度を上げるのが良い。
• 少しの「わからない」で諦めてしまう生徒
  • おそらく数学への苦手意識がかなり強く、数学というだけで避けたり諦めたりするような人も多いだろう。特に高校生や大学生にもなれば癖になっており、なかなかその弱りきった耐久力を底上げするのは大変である。
  • 方法としては、ハッとするものではないと思おうが、少しずつ耐久力を上げていってやることに尽きる。数学が得意な人と同様に、初めは彼ら彼女らが確実に解けるレベルの問題から始め、少しずつ少しずつ難易度を上げていってやるしかない。「数学が苦手というのは思い込みに過ぎず、正しい勉強方法を今までの小学校中学校高校で先生が教えなかったから悪いのだ、あなたは悪くないし、数学が苦手というのも間違っている。」ということを何度も何度も伝えてやる必要があるだろう。

最後に

とりあえず書き殴る形になってしまったが、自分の言いたいことを少しは言葉にできたと思う。 大学で学んでいても思うのだが、結局新しいものや自分にとって目新しいもの、不慣れなもの、たったそれだけ何に「苦手」「才能がない」「向いていない」という理由を挙げて逃げてしまうというケースが多いように思えるのである。ただ自分にとって馴染みがないというだけなのに。

今後は、より具体的な数学を勉強するときの参考書や問題集の使い方について、紹介したいと思う。これについてもかなり詰めたので、完成次第、記事のリンクを添付する。 ここまで読んでくださり、ありがとうございました。思うところがあれば、ぜひコメントください。ブラッシュアップしたいと思っております。

関連記事

ut-bioinformatic.hatenablog.jp

巡回セールスマン問題（TSP）の多項式時間定数近似アルゴリズムが存在しないことについて

有名な Traveling Salesman Problem (TSP)

TSP の定義を簡単に述べると次のようになる。すなわち、

グラフ について、頂点 は辺 を持っており、各辺は重み を持っている。この時に巡回路の重みの総和が最小となるものを求めよ。

多項式時間定数近似アルゴリズム

グラフ が与えられたとき、 最適解を で表すことにする。同様に、アルゴリズム の出力値を で表すことにする。 あるアルゴリズム について、任意の入力 に対して、

\begin{align} & ^\exists const \,\,c > 1, \, \, OPT(G) \leq ALG(G) \leq c OPT \end{align}

Hamilton Circuit から TSP

正の定数 が与えられているとする。

• 判定版 HC: ハミルトン閉路が存在するか
• 判定版 TSP: 合計の重み 以下の巡回路が存在するか。 について考える。

判定版 HC を考える。グラフ が入力であるとする。グラフ G の各エッジの重みを全て に設定する。この操作によって判定版 HC の真偽が変わることはない。

このとき、グラフ G の補グラフ と完全グラフ を考える。すると、

\begin{equation} E \cap \bar{E} = \phi, \,\, E \cup \bar{E} = E_c \end{equation}

となる。また、 として、補グラフのエッジの重みを全て と設定する。すると、両者を合わせた完全グラフ は、 に含まれる辺の重みは 1 で、含まれない辺の重みは 1 より大になる。したがって、

\begin{align} ^\exists G, HC(G) &\text{ is True. } \Rightarrow TSP(K_{|V|}) = n \\ ^\exists G, HC(G) &\text{ is False. } \Rightarrow TSP(K_{|V|}) > cn + (n-1) > cn \\ &\quad \text{where $K_{|V|}$ is produced from $G$.} \end{align}

ただし、 はグラフ の巡回路の重みの総和の最小値を表すとする。

TSP の多項式時間定数近似アルゴリズムが存在しないことの証明

• 前提：判定版 HC が多項式時間で解くことができない（）

この前提のもとで、証明する。

始めに、判定版 HC 問題の入力として与えられる任意のグラフ について、先ほど述べたような方法で のエッジに全て重み 1 を導入した上で、さらに を生成できる。それらについて以下が成り立つことは一つ前のセクションでで確認した通りである。

\begin{align} ^\exists G, HC(G) \text{ is True. } \Rightarrow TSP(K_{|V|}) = n \\ ^\exists G, HC(G) \text{ is False. } \Rightarrow TSP(K_{|V|}) > cn \\ \end{align}

この事実を利用して、背理法を行う。帰無仮説を次のように定義する。

• ある多項式時間アルゴリズム ALG について、ある定数 があって、 ただし、 はグラフ G の巡回路の重みの総和の最小値（ ）を表す。

このとき、その について、以下が成り立つことは明らか。すなわち、

\begin{align} ^\exists G, HC(G) \text{ is True. } \Rightarrow TSP(K_{|V|}) = n \Rightarrow ALG(G) \leq cn \\ ^\exists G, HC(G) \text{ is False. } \Rightarrow TSP(K_{|V|}) > cn \Rightarrow ALG(G) > cn \end{align}

これは逆も成り立つ。以下が証明。

• のとき
  • より TSP(G) < cn となる。
  • が取りうる値は {以上の数 } なので、
  • のとき、自明に G はハミルトン閉路ももつ。つまり、 is True:
• のとき
  • より、
  • のとき、G がハミルトン閉路を持たないのは自明。つまり、 is False.

まとめると次のようになる。

\begin{align} ALG(G) \leq cn \Rightarrow HC(G) \text{ is True.}\\ ALG(G) > cn \Rightarrow HC(G) \text{ is False.} \end{align}

このことは矛盾を孕んでいる。この式は と の大小関係を比較することによって、G がハミルトン閉路を持つかどうかがわかるということを意味する。 は多項式時間アルゴリズムであることにも注目すると、判定版 HC 問題が多項式時間で解けてしまっていることになり、前提に矛盾する。（判定版 HC は NP 完全問題なので、 に矛盾する。と同義。）

したがって、 の仮定のもとで、TSP の多項式時間定数近似アルゴリズムは存在しないことが証明された。 以上。

証明を終えて

What an elegant proof!

これが初めてこの証明を理解した時の感想である。いやいや、綺麗すぎる。 TSP の多項式時間近似アルゴリズムの存在と に深い関係があることを実感した。非常に面白い。これ、テストに出るかなぁ。

メッセージ

計算量理論は非常に面白い。計算量理論は、我々が難しい問題に直面した時、その問題が難しいということを評価する方法としての役割を担っている。個人の能力が低いからではなく、客観的に、対象としている問題が非常に難しいのだということを説明する力は、分業化が進み個人の能力差の大きく開いた現代において、重要なリベラルアーツではないだろうか。問題が圧倒的に難しいのに、個人の能力のせいだと考え、病んでしまう人もいるのではないだろうか。そういった、「問題の難しさの評価」という観点は理解しやすいし、重要性が分かりやすくはっきりしており、初学者のとっかかりには良いのではないだろうか。かく言う私も、初学者ではあるのだが。

線形回帰モデルの一つ抜き交差確認法の平均二乗誤差 MSE についての考察

線形回帰モデル

\begin{equation} f(x) = \sum_{i = 1}^b \theta_i \phi(x_i) \end{equation}

を用いた、 正則化回帰に対する、一つ抜き交差確認法による、平均二乗誤差 について、

\begin{equation} MSE = \dfrac{1}{n}\left\|\widetilde{H}^{-1} H \vec{y}\right\| ^2 \end{equation}

が成り立つことを証明する。

損失関数 を最小にする を求める。ここで、 とし、さらに

\begin{equation} \Phi := (\phi_1, \phi_2, ..., \phi_n) ^T \end{equation}

と定義する。

損失関数の 微分は以下のようになる。

\begin{align} -2 \Phi^T \vec{y}+2 {\theta} \Phi^T \Phi + 2 \lambda {\theta} = 0 \\ \left(\Phi^T \Phi+\lambda I\right) \theta-\Phi^T \vec{y}=0 \\ \left(\Phi^T X+\lambda I\right) \theta=\Phi^T \vec{y} \\ \hat{\theta}=\left(\Phi^T \Phi+\lambda I\right)^{-1} \Phi^T \vec{y} \end{align}

データ を除いた をそれぞれ とすると、 ,
であり、

\begin{align} \Phi_i^T \Phi_i=\Phi^T \Phi-\phi_i \phi_i^T \\\ \Phi_i^T \vec{y}_i=\Phi^T \vec{y}-{\phi_i}^T {y_i}\\\ \end{align}

となる。これと、Sherman Morrison-Woodbury 公式を利用することで、予測値 を求めることができる。すなわち、

\begin{aligned} \phi\_i{ }^T \hat{\vec{\theta}}_i &= \phi_i^T\left(U-\phi_i \phi_i{ }^T\right)^{-1}\left(\Phi^T \vec{y}-y_i \phi_i\right) \\\ & =\phi_i^T\left(U^{-1}+\frac{U^{-1} \phi_i \phi_i^T U^{-1}}{1-{\phi_i}^T U^{-1} \phi_i}\right)\left(\Phi^T \vec{y}-y_i \phi_i\right) \\\ & =\phi_i{ }^T \frac{U^{-1}-\phi_i^T U^{-1} \phi_i U^{-1}+U^{-1} \phi_i \phi_i^T U^{-1}}{1-\phi_i^T U^{-1} \phi_i}\left(\Phi \vec{y}-y_i \phi_i\right) \\\ & =\frac{\phi_i^T U^{-1}-\phi_i^T\left(\phi_i^T U^{-1} \phi_i\right) U^{-1}+\left(\phi_i^T U^{-1} \phi_i\right) \phi_i^T U^{-1}}{1-\phi_i{ }^T U^{-1} \phi_i}\left(\Phi^T \vec{y}-y_i \phi_i\right) \\ & =\frac{\phi_i^T U^{-1}\left(\Phi^T \vec{y}-y_i \phi_i\right)}{1-\phi_i{ }^T U^{-1} \phi_i} \end{aligned}

ただし、一行目から二行目で ShermanMorrison-Woodbury 公式の特別な形を利用した。四行目か ら五行目は、 がスカラー値であることから、分子の第二項と第三項が相殺することを 利用した。

したがって、予測値と実測値の差 は次のように表すことができる。

\begin{aligned} E_i & =\frac{\phi_i^T U^{-1}\left(\Phi^T \vec{y}-y_i \phi_i\right)}{1-\phi_i^T U^{-1} \phi_i}-y_i \\\ & =\frac{\phi_i^T U^{-1} \Phi^T \vec{y}-y_i}{1-\phi_i^T U^{-1} \phi_i} \end{aligned}

ここで、 について考える。 の 番目の要素 は簡単に求められて、

\begin{equation} H_{i, j}= \begin{cases}-\left(a_{i, j}-1\right) & (\text { if } i==j) \\ -a_{i, j} & \text { (otherwise) }\end{cases} \end{equation}

（ただし、 である。）

すると、 の対角成分だけからなる の逆行列 についても同様で、

\begin{equation} \widetilde{H}_{i, j}^{-1}= \begin{cases}\dfrac{1}{1-a_{i, j}} & (\text { if } i==j) \\ 0 & (\text { otherwise })\end{cases} \end{equation}

一方で、 の 番目の要素が

\begin{equation} \left[\vec{\phi}_i{ }^T U^{-1} \Phi^T\right]_{i, j}=\phi_i^T U^{-1} \vec{\phi}_j=a_{i, j} \end{equation}

であることは、少し考えることでわかる。

以上より、

\begin{aligned} E_i & =\dfrac{\vec{\phi_{i}}^T U^{-1} \Phi^T \vec{y}-y_i}{1-\vec{\phi_{i}}^T U^{-1} \vec{\phi_{i}} } \\\ & =\dfrac{\left(\sum_{j=1}^n a_{i, j} y_j\right)-y_i}{1-a_{i, i}} \\\ & =\dfrac{-\left(a_{i, 1} y_1+a_{i, 2} y_2+\ldots+a_{i, n} y_n\right)-y_i}{1-a_{i, i}} \\ & =\dfrac{-a_{i, 1} y_1-a_{i, 2} y_2-\ldots-\left(a_{i, i}-1\right) y_i-a_{i, i+1} y_{i+1}-\ldots-a_{i, n} y_n}{1-a_{i, i}} \\\ & =\widetilde{H}_{i, i}^{-1} \left(H_{i, 1} y_1+H_{i, 2} y_2+\ldots+H_{i, n} y_n\right) \end{aligned}

となり、 を縦に並べた列ベクトル は次のように表せる。すなわち、

\begin{equation} \vec{E} = \widetilde{H} ^{-1} H \vec{y} \end{equation}

したがって、平均二乗誤差 MSE は、

\begin{aligned} M S E & =\dfrac{1}{n} \sum_{i=1}^n E_i^2 \\ & =\dfrac{1}{n} \vec{E}^T \vec{E} \\ & =\dfrac{1}{n}\|\vec{E}\|^2 \\ & =\dfrac{1}{n}\left\|\widetilde{H}^{-1} H \vec{y}\right\|^2 \end{aligned}

となり、題意を示すことができた。以上で、証明終わり。

東大生の応用情報技術者試験、合格発表。 2022/12/22

2022 秋 応用情報技術者試験（AP）

ipa が開く国家試験である、応用情報技術者試験、略して AP を受験したのでそれについて思い出を記しておく。 2022/12/22(木) に合格発表が行われた。

思い出に耽る

テスト勉強は2022/9 あたりに本格化し、そこから2ヶ月ほど少しずつ対策をおこなっていた。 学部で勉強している、

• アルゴリズム
• サイバーセキュリティ
• ソフトウェア構成要素

については余裕を持って理解できたが、

• ストラテジ
• システム監査
• マネジメント
• ネットワーク

が難しかった。データサイエンティストというのは、情報科学ができるだけではなく、 ビジネスにも精通していなければならないものである。それを痛感したテスト対策期間であった。 ただ、youtube を活用した勉強を徹底し、なんとか午前試験は 8 割、午後も 7 割前後をキープできるくらいまで力をつけられた。

試験当日を振り返る

2022/10/9 試験当日、サンシャインシティ池袋の上の方のフロアにいった。椅子が微妙で、午前午後の 150 分 2 セットでお尻が完全に痛くなってしまい、集中するのがやっとだった。大学受験の模試の時は余裕で一日テストを受けられたのに、いつの間にかそういった体力は無くなってしまっていた。それがショックだった。 テストの出来としては、午前は 8 割いっただろうという手応えだった。午後はシステムアーキテクチャ？か何かがめちゃめちゃ簡単であり、全体として 7 割ほどはあるだろうという見積であった。

そういえば、試験会場のすぐ横くらいで、北海道のご当地グルメフェアが開催されていたので、帰りに寄ろうと思ったが、予約をしていないと入れなかったみたいで、結局香ばしい匂いに心が惑わされただけであった。

合格発表の結果はいかに

結果は、合格であった。よかった。点数は以下のようになった。

• 午前試験：85 % (60 % で合格)
• 午後試験：75 % (60 % で合格)

  

  試験結果

  蓋を開けてみればかなり余裕を持っての合格だった。 午後試験で落ちるかも？？と心配していたが、大問1個分くらい余裕があったし、 twitter とかを見てる感じ、平均よりはできているようだった。 本当によかったよかった。

次は、、？

次は高度を受けるのか、、？

否、もう受けまい。 一日中の試験はもうしんどすぎて、体力的に厳しいことがわかった。。高度を受けるためには、ジムで体づくりをしなくっちゃあなぁ。

試験関連ページ

こちらも見てね。 ut-bioinformatic.hatenablog.jp

MinMax Theorem の証明。レイリー商と対称行列の固有値についての考察

今回扱う定理について

今回示す問題は、固有値にまつわる有名な定理であり、 Min-Max Theorem と呼ばれている。

Min-Max Theorem:

定理の紹介

はレイリー商と呼ばれている。 証明に入る前にレイリー商の性質について述べる。レイリー商は、引数が 行列 の固有ベクトルの時に、その固有ベクトルに対応する固有値を返す。 このことは簡単に確認できる。固有ベクトル は を満たすことから、

The Proof of Min-Max Theorem

行列 は の実対称行列である。 を定数として考える。証明の流れとしては、二つの不等式を導出し、 導出された不等式を利用して、等号を示す。また、「」と「」に 注意することが重要であり、それがこの定理の本質であると考えている。

A は実対称行列なので、対角化できる。 固有ベクトルを、対応する固有値が小さい方から大きい順に とおくと、 は正規直交基底をなす。

実 次元空間の 次元部分空間 について、 を考えると、 に対して、

を満たす が存在する。 を利用すると、 どんな に対しても （どんな に対しても）、レイリー商は、

\begin{equation} R_A(v) = \dfrac{\lambda_1 \alpha_1^2 + \lambda_2 \alpha_2^2 + \dots \lambda_k \alpha_k^2} {\alpha_1^2 + \alpha_2^2 + \dots + \alpha_k^2}
\leq \dfrac{\lambda_k(\alpha_1^2 + \alpha_2^2 + \dots + \alpha_k^2)} {\alpha_1^2 + \alpha_2^2 + \dots + \alpha_k^2}
= \lambda_k \end{equation}

を満たす。 は任意の において成り立ち、 についての条件も再度まとめると、今までの議論は以下のように書き下すことができる。すなわち、

この式は次の式の十分条件である。 つまり、この式が成り立てば、以下の式も成り立つということである。

\begin{equation} \min_{V_k} \left(\max_{v \in V_k } R_A(v) \right) \leq \lambda_k \end{equation}

これが、導出しようとしていた不等式の一方になる。

続いて、もう一方についても導出する。 ここで、補題「どんな 次元部分空間 であっても、 基底 で表現できる が存在する」 を証明する。背理法による。もし、ある 次元部分空間 で、そういった が存在しないとすると、 基底 からなる 次元部分空間と 次元部分空間に 共通部分がないということになる。そのことから、全体の空間は少なくとも 次元より大きくなければならないが、 < なので、矛盾。したがって、この補題は示された。

補題を用いて議論を続ける。補題から、 どのような 次元部分空間 においても、 ある で、

\begin{equation} v = \alpha_k {u_k} + \alpha_{k+1} {u_{k+1}} + \dots + \alpha_n {u_n} \end{equation}

を満たす が存在する。 そういった を用いると、レイリー商は、

\begin{align} R_A(v) & = \dfrac{\lambda_k \alpha_k^2 + \lambda_{k+1} \alpha_{k+1}^2 + \dots + \lambda_n \alpha_n^2} {\alpha_k^2 + \alpha_{k+1}^2 + \dots + \alpha_n^2} \\ & \geq \dfrac{\lambda_k(\alpha_k^2 + \alpha_{k+1}^2 + \dots + \alpha_n^2)} {\alpha_k^2 + \alpha_{k+1}^2 + \dots + \alpha_n^2} \\ & = \lambda_k \end{align} つまり、

\begin{align} \max_{v \in (V_k \cap \text{span} \lbrace {u_k}, {u_{k+1}}, \dots, {u_n} \rbrace)} R_A(v) \geq \lambda_k. \label{max 十分} \end{align}

これは、以下を示すのに十分である。（この式が成り立つならば次の式は成り立つ。）

\begin{align} \max_{v \in V_k} R_A(v) \geq \lambda_k. \end{align}

ここで、議論の始めの方で述べたように、 上の式は任意の 次元部分空間 について 成立するので、以下が成り立つ。すなわち、

\begin{equation} \max_{v \in V_k }R_A(v) \geq \lambda_k \Leftrightarrow \min_{V_k} \left(\max_{v \in V_k } R_A(v) \right) \geq \lambda_k \end{equation}

これが導出したかった二つ目の不等式になる。 今までの議論で得た二つの不等式（ と ）から、以下が導かれる。すなわち、

\begin{align} & \min_{V_k} \left(\max_{v \in V_k } R_A(v) \right) \leq \lambda_k \text{ かつ } \min_{V_k} \left(\max_{v \in V_k } R_A(v) \right) \geq \lambda_k \\ \Leftrightarrow & \min_{V_k} \left(\max_{v \in V_k } R_A(v) \right) = \lambda_k \end{align} となり、Min-Max Theorem は示された。 以上。

終わりに

結構丁寧に論を運んだ自信がある。英語版 wikipedia よりもかなり丁寧に書いた。 Cauchy's Interlace Theorem もレイリー商の不等式評価を利用して証明することができる。 レイリー商、名前もかっこいいし、性質も Cool だし、憧れます。 （もちろん、レポートに丸写ししてはなりません、、！）

＜NP 完全性 (Karp's Reduction)＞3-SAT から Vertex Cover への多項式時間還元について（polynomial reduction 3-SAT to VC）

はじめに

大学で学んだ多項式時間還元について、日本語記事でわかりやすいものが見つからなかったため、ここに記す。数ヶ月後におそらく試験で出題されるので、その試験対策としても。 blog 末尾でも述べるつもりであるが、Garey と Johnson による黒い本 Computers and intractability. を参考にしている。

解くべき問題の整理

Vertex Cover を判定問題にする必要がある。を与えられた自然数とし、命題を以下のように定める。

• 命題 VC: の頂点からなる被覆 VC が存在する。
• 命題 3-SAT: 「リテラルの数、節の数がそれぞれ である論理積標準形 が充足可能である。」

3-SAT から VC へ多項式時間還元可能であることを示す。

3-SAT から VC の多項式時間変換

が与えられた時の 3-SAT を の VC 問題に変換する。リテラルは とし、各節は とする。 は任意の三つのリテラルの論理和である。例えば のようになっている。

から、図１のようなグラフ を作成する。 グラフ G は n 組のリテラルノードペアと m 個のクロースノードガジェットからなる。両者について詳しく説明する。

• 組のリテラルノードペア： のノードを一つずつ作成し、両者を一つの辺で結んだもの
• 個のクロースノードガジェット： を構成する三つのリテラル のノードを作成し、それぞれ辺で結んだもの。辺は {a, b}, {b, c}, {c, a} のちょうど三つである。
• リテラルノードペアとクロースノードガジェットについて、各ガジェット に対して、それを構成するノード a, b, c と、リテラルノードペアにおける a, b, c の間にそれぞれ辺をちょうど一つ結ぶ。 のとき、リテラルノードペアの と対応するものの間にそれぞれちょうど一つの辺を作成する。

実際のグラフは以下のようになる。（いずれ追記します。）

すると、このグラフ の頂点被覆は自明に以下の性質を持つ。

• リテラルノードペアの辺を被覆するために、リテラルノードペアの少なくとも一方は頂点被覆集合に含まれる。少なくとも 個は頂点被覆集合 VC に含まれる。
• クロースノードガジェットの辺を被覆するために、各三つの頂点のうち、少なくとも 2 つは頂点被覆集合 VC に含まれる。

このことから、最小頂点被覆集合の大きさは であることが導かれる。また逆に、ある頂点被覆集合 V のサイズが であるとき、以下が成立する。すなわち、

• 各リテラルノードペア（）について、ちょうどどちらか一つが V に含まれる。
• 各クロースノードガジェットの三つの頂点のうち、ちょうど二つが V に含まれる。

これらを確認した上で、以下で 「論理積標準形 を満たす真理値割当が存在する グラフ はサイズ 以下の頂点被覆集合が存在する」を示す。

論理積標準形 を充足する真理値割当が存在する グラフ はサイズ 以下の頂点被覆集合が存在する

論理積標準形を充足する真理値割当を とする。 十分条件「論理積標準形 を満たす真理値割当が存在する グラフ はサイズ 以下の頂点被覆集合が存在する」を示す。初めに、頂点集合 V を空集合とする。

1. 真理値割当 をリテラルノードペアに反映する。つまり、リテラルノードペア については、 が真であればノード を V に加え、そうでなければノード を V に入れる。
2. G(f) の作成ルールと が を充足することから、各クロースノードガジェット のうち少なくとも一つのノードは真であることが保証されており、その真となっているノード以外の 2 つのノードを V に入れる。（ に真となっているノードが複数ある場合はそのうち一つを選び、それ以外の二つのノードを V に入れる。）

ここまでの段階で V のサイズは である。V が頂点被覆集合であることを示せば、十分性は示せたことになる。

1. V が頂点被覆集合であるかということについて考える。 まず、各リテラルノードペア においては、どちらか一方が V に含まれていることから、両者をつなぐ辺 {} は被覆されている。
2. 各ガジェット の三つの頂点 のうち二つが V に含まれていることから、ガジェット内の三つの辺はどれも被覆されている。
3. 各ガジェットについて、それとリテラルノードペアを結ぶ三つの辺は被覆されている。ガジェット の三つの頂点 のうち、少なくとも一つは真が割り当てられており、それを a とする。b, c はガジェット に含まれるノード a はリテラルノードペア () のノード a と辺を共有する。リテラルノードペアにおいて a は真が割り当てられているので、V に含まれている。したがって、リテラルノードペアのノード a とガジェットのノード a を結ぶエッジは被覆されている。 の生成ルールから、ガジェット の三頂点のうち a 以外の2 点、つまり頂点 は V に含まれている。したがって、ガジェット の b とリテラルノードペアの b を結ぶ辺は被覆される。c についても同様に被覆される。

以上より、V はサイズ の頂点被覆集合であることが示された。 したがって、十分性を示すことができた。

論理積標準形 を充足する真理値割当が存在する グラフ はサイズ 以下の頂点被覆集合が存在する

必要性の証明を行う。

下準備

何らかの から生成されたグラフ G(f) が与えられたとし、そのグラフ G(f) にサイズ 以下の頂点被覆集合が存在するとする。グラフ G(f) は三頂点からなるガジェットと、二頂点からなるペアの二つの構造が繋がっているものとみなせて、二頂点からなるペアの数を n, ３頂点からなるガジェットの数を m とし、n 個のペアのうち 番目のペアをそれぞれ とする。ペア とガジェット について、ペアのノード とガジェットのノード が辺を共有しているとき、「a は x に対応している」とする。各ガジェットの各頂点は、ちょうど一つのリテラルノードと辺を共有することから、各ガジェットの各頂点について、ちょうど一つのリテラルノードが対応づけれらる。そうして対応づけが完了したとする。すると、ガジェット について、, l_i[1], l_i[2] ] に対応するリテラルノードがそれぞれ であるとき、ガジェット は論理和 {a, b, c} に対応すると呼ぶことにする。すると、G(f) の元となった論理積標準形 f は、各ガジェットに対応する論理和の論理積で与えられることがわかる。 ここまでの段階で、G(f) から をただ一つに求める（復元する）ことができた。

ペアを {} か {} のどちらにするかで は 2 通りあるように思えるが、どちらであっても充足可能性には影響しないため、この決定の仕方は問題にはならない。

以上の過程を経て G から生成された論理積標準形を f(G) と表すことにする。

証明のメイン

G(f) から上の段落のようにして を求めたとする。この G は仮定より、サイズ 以下の頂点被覆集合 V をもつが、これは先ほどの議論：

このグラフ の頂点被覆は自明に以下の性質を持つ。

• リテラルノードペアの辺を被覆するために、リテラルノードペアの少なくとも一方は頂点被覆集合に含まれる。少なくとも 個は頂点被覆集合 VC に含まれる。
• クロースノードガジェットの辺を被覆するために、各三つの頂点のうち、少なくとも 2 つは頂点被覆集合 VC に含まれる。

このことから、最小頂点被覆集合の大きさは であることが導かれる。また逆に、ある頂点被覆集合 V のサイズが であるとき、以下が成立する。すなわち、

1. 各リテラルノードペア（）について、ちょうどどちらか一つが V に含まれる。
2. 各クロースノードガジェットの三つの辺のうち、ちょうど二つが V に含まれる。

より、最小頂点被覆集合に一致し、各リテラルノードペアのちょうど一方と、各クロースノードガジェットの三つの頂点のうちちょうど二つが V に含まれるということがわかる。

まず、各リテラルノードペアについてはちょうど一つのノードが V に含まれているので、含まれているノードに対応するリテラルを真とする。各リテラル について、 の一方のみが真に割り当てられ、矛盾は存在しない。この真理値割当を と呼ぶことにする。

こうして得られた割当 が G(f) から一意に生成された論理割当 f(G) を充足することを示せば、必要性が示せたことになる。これは、「各ガジェットにおいて、どれか一つの頂点は真を割り当てられたリテラルノードと辺を共有する」ことを示すことと同値である。それを、背理法によって証明する。 帰無仮説：「あるガジェット ] で、どの頂点も、真を割り当てられたリテラルノードと辺を共有しないものが存在する」を仮定する。まず、V が最小頂点被覆であることから、任意のガジェットは、三つの頂点のうち、V に含まれていない頂点がちょうど一つ存在する。 当然、そのガジェット ] においても V に含まれていない頂点が存在し、それに対応するリテラルが a であるとする。帰無仮説より、リテラルノードペアにおいて、a ではなく、 が V に含まれていることから、 ガジェットの頂点 a とリテラルノードペアの頂点 a を結ぶ辺は被覆されていないことになる。これは、V が頂点被覆集合であることに矛盾する。 従って、帰無仮説は棄却された。したがって、V から生成された真理値割当 は、グラフ G から生成された論理積標準形 を充足するということが示された。 この瞬間、必要性は証明された。

必要十分性についてと多項式時間還元であることの証明

必要性と十分性が示されたことから、以下の命題は真である。すなわち、 「論理積標準形 を満たす真理値割当が存在する グラフ はサイズ 以下の頂点被覆集合が存在する」は示された。

ここで、G(f) や f(G) の変換は、多項式時間で行われていることが簡単に確認できる。 したがって、3-SAT 問題は頂点被覆集合問題に多項式時間還元可能であるということが示された。 以上。

まとめ

かなり丁寧に書きました。適宜ブラッシュアップします。例えば、図は面倒なのでまだ作っていませんが、いずれ追加します。 なかなかの完成度で証明を書けたと思うが、これをレポートなどに転用しないように。コピペは誰も幸せになりません。

参考文献

Garey, Michael R., and David S. Johnson. "Computers and intractability." A Guide to the (1979).

関連記事

ut-bioinformatic.hatenablog.jp

東大生の応用情報技術者試験対策〜産業財産権〜

この記事について

この記事では応用情報技術者試験に向けての対策を行っていきます。今回の内容は、産業財産権についてです。

産業財産権とは

産業財産権とは、著作権と並ぶ、知的財産権に分類される権利である。（従って、産業財産権の中に著作権が含まれるような解答の選択肢は不採用となる。） その構成は、

• 特許権
  • 自然法則や自然の仕組みを利用した、価値ある発明を保護する権利。出願日から 20 年間有効。
• 実用新案権
  • 発明を除いた、物の組み合わせや形などの考案を保護する権利。出願日から 10 年間有効。
• 意匠権
  • 物の価値を高めるような形やデザインを保護する権利。出願日から 25 年間有効。
• 商標権
  • 商品の名称やロゴなどを保護する権利。出願日から 10 年間有効。

となる。 注意したいのは、冒頭でも書いたように、著作権は含まれないということである。

思ったこと、気づいたこと

デザインを保護する意匠権が、発明を保護する特許権よりも有効な期間が長いというのを今回知ったが、不思議である。私はどうしても理系寄りの考えをしてしまうので、デザインの価値よりも自然科学を利用した発明を保護する特許権の有効期間も、意匠権の有効期間と同様の 25 年にするべきではないかと思った。

ただ、よくよく考えると発明された技術の使用を制限するという一面が特許権には存在することから、特許権の有効期間が長すぎると、全体として製品の質が上がりにくくなったり、発明の質が低下（みんなリバースエンジニアリングとかするのかも）したりするのではないかと思った。なので、デザインという領域よりも、使用制限が与える負の影響が大きいゆえに、特許権は意匠権よりも有効期間を短くしているのだろうと思った。

まとめ

産業財産権は、特許権、実用新案権、意匠権、商標権の四つから成り立ち、著作権を含まない。著作権と商業財産権は共に知的財産権に含まれている。 試験では、著作権が含まれていない選択肢を選べば大体正解だろう。