オタクof数理の共同ブログ

京大情報学科数理工学コースの学生4人による共同ブログです

おもろい図形

こんにちは, よねすけです.
f:id:otaku_of_suri:20170212150745p:plain
円の中に一点を適当にとり, それを通る線分とそれに垂直な線分を上の図のようにとったとしましょう. このとき, 円の半径rを用いて

a^2+b^2+c^2+d^2=4r^2
となります. 図形に関する等式で個人的に一番好きなので今回紹介することにしました.

この式の証明をするために下のように補助線を引きます.
f:id:otaku_of_suri:20170212151411p:plain
線分QXは円の中心を通るように取るものとします. そうすると

RS=PX
が分かります. これは線分QXが中心を通る事から, 四角形PRSXが等脚台形であることが分かるからです. 線分PQ, RS三平方の定理から,
PQ=\sqrt{a^2+b^2}, RS=\sqrt{c^2+d^2}
です. 三角形PQXは直角三角形なのでまた三平方の定理を用いる事が出来て,

\begin{eqnarray}
QX^2&=&PQ^2+PX^2=PQ^2+RS^2\\
\Leftrightarrow (2r)^2&=&(\sqrt{a^2+b^2})^2+(\sqrt{c^2+d^2})^2\\
\Leftrightarrow 4r^2&=&a^2+b^2+c^2+d^2
\end{eqnarray}
が示されました.
とても綺麗な式ですね.

それでは.

[追記]
いろいろ突っ込まれそうなので一応書いておくとこの証明ははじめに取る点が円の中心と一致しないときに限り成立します. 円の中心に一致する時は, a=b=c=d=rなので明らかに成り立ちますね. また円の中心でない点を取った場合には適当な回転を行えば上の図のようにacよりも長く, bdよりも短くなるようにすることができるので確かに問題ありません. 図形を用いて証明する場合はこういった面倒があるので大変ですね.

判別式パート3

こんにちは, よねすけです.

otaku-of-suri.hatenablog.com
以前3次方程式の判別式についてまとめました. 今回n次方程式の特別な場合としてのx^n+px+q=0の判別式を求めることが出来たので以下に記しておきます.
判別式と微分の関係については高木貞治の本を参考にしました.

代数学講義 改訂新版

代数学講義 改訂新版


判別式Dは係数p,q多項式で次のように表されます.

\displaystyle D=\sum_{\alpha,\beta}\lambda_{\alpha,\beta}p^{\alpha}q^{\beta}
n次方程式の判別式の重みは定義から
{}_nC_2\times 2=n(n-1)
です. pの重みはn-1であり, qの重みはnなので, 重みについて以下の式
\alpha (n-1)+\beta n=n(n-1)
が成立します. 連続する2整数は互いに素であることを考えれば, \alpha,\betaの値は,
(\alpha, \beta)=(n,0), (0,n-1)
が分かります. これを用いて判別式を改めて書き直すと,
D=\lambda p^n+\mu q^{n-1}
になります. 以下で\lambda,\muをそれぞれ求めて行きましょう.

  • p=0, q=-1のとき

考える方程式は

x^n-1=0
になるのでこの方程式の解はすぐ求まって,
\displaystyle x=\exp\left(2\pi i\frac{k}{n}\right)\ (0\le k{<}n)
です. これと判別式と微分の関係式を用いると,
\displaystyle
\begin{eqnarray}
D&=&(-1)^{\frac{n(n-1)}{2}}\prod_{k=0}^{n-1}f'\left(e^{2\pi i\frac{k}{n}}\right)\\
&=&(-1)^{\frac{n(n-1)}{2}}n^n\exp\left(2\pi i\frac{n-1}{n}\sum_{k=0}^{n-1}k\right)\\
&=&(-1)^{\frac{n(n-1)}{2}}n^n\exp(\pi i(n-1)^2)\\
&=&(-1)^{\frac{n(n-1)}{2}}n^n (-1)^{n-1}
\end{eqnarray}
が分かりました. よって,
\displaystyle
\begin{eqnarray}
\mu(-1)^{n-1}&=&(-1)^{\frac{n(n-1)}{2}}n^n (-1)^{n-1}\\
\Leftrightarrow\mu&=&(-1)^{\frac{n(n-1)}{2}}n^n
\end{eqnarray}
となります.

  • p=-1, q=0のとき

考える方程式は

x^n-x=x\left(x^{n-1}-1\right)
なのでこの方程式の解は
\displaystyle x=0,\exp\left(2\pi i\frac{k}{n-1}\right)\ (0\le k{<}n-1)
です. x=0を除いた解のみから構成される判別式は一個上で求めた判別式のn-1次の場合にあたるのでそれを用いると
\displaystyle
\begin{eqnarray}
D&=&(-1)^{\frac{(n-1)(n-2)}{2}}(n-1)^{n-1}(-1)^{n-2}\times\prod_{k=0}^{n-2}\exp\left(2\pi i\frac{k}{n-1}\times 2\right)\\
&=&(-1)^{\frac{(n-1)(n-2)}{2}}(n-1)^{n-1}(-1)^n\times\exp\left(4\pi i\frac{k}{n-1}\sum_{k=0}^{n-2}k\right)\\
&=&(-1)^{\frac{(n-1)(n-2)}{2}}(n-1)^{n-1}(-1)^n\times\exp(2\pi i(n-2))\\
&=&(-1)^{\frac{(n-1)(n-2)}{2}}(n-1)^{n-1}(-1)^n
\end{eqnarray}
がわかります. よって
\displaystyle
\begin{eqnarray}
\lambda(-1)^n&=&(-1)^{\frac{(n-1)(n-2)}{2}}(n-1)^{n-1}(-1)^n\\
\Leftrightarrow\lambda&=&(-1)^{\frac{(n-1)(n-2)}{2}}(n-1)^{n-1}
\end{eqnarray}
となります.

以上からn次方程式x^n+px+q=0の判別式は

\displaystyle D=(-1)^{\frac{(n-1)(n-2)}{2}}(n-1)^{n-1}p^n+(-1)^{\frac{n(n-1)}{2}}n^nq^{n-1}
これは確かに以前求めた3次方程式の判別式にも一致することはすぐに確かめられます.以下のリンクの通りです.
otaku-of-suri.hatenablog.com

それでは.

後期の振り返りするで。

こんにちは、よねすけです。

後期のテストも随分前に終わって春休みに入っているのに振り返りをするのを忘れていたなあ、ということで振り返りを書きます。

応用代数学(月曜2限)
群論の基本的な内容と表現論の初歩の内容を授業で扱いました。丁寧に授業を運んでくれたので特に躓くことなく理解できたと思いました。試験は授業で行った証明などを実際に書かせる問題が多かったです。

言語・オートマトン(月曜3限)
DFA, NFA, εNFA, PDA, NPDA, TMなどを扱いました。この授業は再履修して取った授業ですが実に面白かったと思います。試験は2回の小テストから出題されるのでテスト勉強はしやすかったです。

アルゴリズムとデータ構造入門(月曜4限)
これも再履修で取った授業です。一回生の時に未受験で落としてしまったので3回生になって取りましたが、Schemeを書くこともなくアルゴリズムをいろいろと紹介されました。本当は自分で実装したほうが良いのだろうなと思いました。

生命情報学(火曜5限)
生命情報学に関することをいろいろスライド授業で学びました。下の図はPyMOLを用いてDNAの2重螺旋を横から見た様子です。成績評価はレポート2回で行われるそうです。
f:id:otaku_of_suri:20170209232432p:plain

パターン認識機械学習(水曜2限)
パターン認識機械学習パターン認識機械学習について学びました。なんだか勉強がしにくかったです。。。試験はプリントに載っていることをきちんと理解すれば解ける問題は解ける気がします。

線形制御理論(水曜3限)
フィードバック系について偏差をどのように小さくするかについて(?)学びました。過去問5年分をやったのに思ってたのとは違うのが出てきて辛かったです。成績評価はレポートと試験で行われるそうです。8回以上レポートを出せば単位を落とすことはないらしいです(?)。

アルゴリズム論(木曜2限)
チューリングマシンの話題を中心に問題の可解、非可解性やP≠NP問題に関することを扱いました。授業は面白いのですが実際に問題を解くとなると地頭ゲーになってくるのがしんどいですね。レポート2回と試験で成績評価するそうです。

数理工学セミナー(金曜2限)
グレブナ基底と代数多様体について扱いました。

グレブナ基底と代数多様体入門・上

グレブナ基底と代数多様体入門・上

ゼミ形式でこの本を読み進めて、ヒルベルトの零点定理まで進みました(最後のゼミはインフルエンザで出ることが出来なかった。残念)。

正則言語

こんにちは, よねすけです.

正則言語

正則言語とは正則表現で表される言語のことです. 同値な表現方法として以下があります.

すなわち上の4つの表現方法はいずれも能力として等価であるということです.

正則言語の閉包性

正則言語には閉包性という性質があります. 具体的には正則言語L_1,L_2について,

  • \overline{L_1}は正則言語
  • L_1\cup L_2は正則言語
  • L_1\cap L_2は正則言語

などです. それぞれ証明しましょう.

証明

  • L_1は正則言語なのである{\rm DFA} Aで認識される言語です. A=(Q,\sum,\delta,q_0,F)として, 次のオートマトンBを考えます. B=(Q,\sum,\delta,q_0,Q-F)とすると, 受理状態と非受理状態が綺麗に入れ替わることが分かるのでL(B)=\overline{L_1}となり, \overline{L_1}{\rm DFA}で受理できることが分かりました. よって\overline{L_1}も正則言語です.
  • L_1,L_2は正則言語なのである正則表現R_1,R_2を用いて, L_1=L(R_1),L_2=L(R_2)と書くことが出来ます. このとき正則表現の書き方からL(R_1+R_2)L_1\cup L_2と一致することが分かります. よって正則言語の和集合もまた正則表現になることが分かります.
  • L_1\cap L_2=\overline{\overline{L_1}\cup\overline{L_2}}がド・モルガンの公式から分かるので上に証明したことから正則言語の積集合もまた正則言語であることが分かります.

正則言語の閉包性の証明には正則表現の4つの表現方法をうまく活用することで簡単に示すことが出来ます.

正則言語の性質

正則言語の性質としてPumping Lemmaがあります.

Pumping Lemma

Lを正則言語とします. あるn\in\mathbb{N}で, 長さn以上のすべてのw\in Lに対してw=xyzと分解します. そうするとx,y,zについて

  • y\ne\varepsilon
  • |xy|\le n
  • k\in\mathbb{Z}_{\ge 0}に対して, xy^kz\in L

です.

Pumping Lemmaは正則言語そのものよりも考える言語が正則言語で無いことを示す事によく使われます. 例えばL_{01}=\{0^i1^i|i\ge 1\}が正則言語でないことはPumping Lemmaの逆から示されます.


それでは

チューリングマシンが受理する言語

こんにちは, よねすけです.

今回はチューリングマシンの話を書きたいと思います. 以下チューリングマシンをTMと省略します.

帰納可算集合(Recursively Enumerable)

言語L帰納可算集合であるとは, あるTMMによって

L=L(M)
と書けることを言います. この集合を{\rm RE}と書く事があります.

帰納的集合(Recursive)

言語L帰納的集合であるとは, ある必ず止まるTMMによって

L=L(M)
と書けることを言います. この集合を{\rm R}と書くことがあります. この定義から明らかなように
{\rm R}\subset{\rm RE}
が分かります. {\rm R}に含まれる言語は必ず止まるTMによって認識出来るので可解であることも分かります.
このような言語は色々あります. 一番簡単な言語はalphabet\sumからなる列全体を集めた次の言語
L_3=\sum^*
じゃないでしょうか. これを認識するTMはすべての入力に対して初期状態と受理状態を一致させることによって設計できます. 状態遷移図は次のようになります.

f:id:otaku_of_suri:20170127135742p:plain

このときTMは1ステップで必ず止まるのでL_3帰納的集合であることが分かります.

このような集合の他にそもそもTMで認識出来ない集合もあります. そのような言語の例として空集合問題や対角線言語があります. 空集合問題において考える言語は

L_e=\{M|L(M)=\phi\}
です. 空集合問題は一般に非可解である, すなわち{\rm R}に含まれないことはよく知られていますが, {\rm RE}にすら実は含まれないということはとても驚きでした.
対角線言語において考える言語は
L_d=\{\sigma_i|{\rm TM}\sigma_iは\sigma_iを受理しない\}
です. この言語が対角線論法を用いて示されることでも有名です.

それでは

愛情の数学

こんにちは.かじはらです.
クリスマスが近いので愛にまつわる数学の話をしたいと思います.

以前よねすけくんが無理数無理数乗が有理数になる,という話をしていました.

otaku-of-suri.hatenablog.com

では複素数複素数乗が実数になることはあるのでしょうか?

まずは複素数複素数乗を定義しなければなりません.

{
\begin{align*}
&z,w \in \mathbb{C}\\
&z^w = e^ {\log{z^w}} = e^{w \log z}
\end{align*}
}

対数を使って定義するんでしたね.
複素数対数がどのように定義されていたかもついでにおさらいしておきましょう.

{
\begin{align*}
\log z
&= \log re^{i \theta}\\
&= \log r + \log e^{i \theta}\\
&= \log r + i \theta + 2 \pi n i
\end{align*}
}

複素数対数は一意に値が定まらない多価関数になるんでしたね.

前回も虚数の話をしたので話題が重複してしまって申し訳ありませんが,今回も虚数に登場してもらいましょう.

{ \displaystyle
i^i
}
これはまさしく複素数複素数乗の一種です.これを上の定義に則って計算してみましょう.

{
\begin{align*}
i^i
&= e^{\log{i^i}}\\
&= e^{i \log i}\\
&= e^{i \log e^{\frac{\pi}{2}i}}\\
&= e^{i \log e^{(\frac{\pi}{2}+ 2n \pi)i}}\\
&= e^{-(\frac{\pi}{2}+ 2n \pi)}
\end{align*}
}

よくわからない式がでてきました.これではどんな値が具体的にはわからないですね.
しかしここで注目すべきはそこではありません.よく見てください.

なんと虚数が消えています!!!!!!!!!

計算結果は実数の実数乗の形をしているので,具体的な値はわからずともこの値が実数であることは確かです.

つまり,

愛(i)の愛情(i乗)は実数になる!!!!!!!



え…?愛にまつわる数学ってこれ…?ここにきてダジャレ…?ダジャレなの…?

という声が聞こえてきそうですね.

(調べたところ「i^i乗」というwikipediaの項目もあるぐらいなのでかなり有名な話っぽいですが,
高1の時にこの事実を知って以来お気に入りの数学小話(?)のひとつなので,どうしても書きたかったのです.)


次回は,

高校数学の試験で「{a_{n+1}=f(a_n)}の数列の極限を求めよ.」という形式の問題が出された時,{\alpha = f(\alpha)}を解いて{\alpha}極限値として答えを求める方法がなぜダメなのか?

について考察します.(かじはらの気分が年明けあたりまで変わらなければ.)

おしまい.

答え

こんにちは,よねすけです.

前回の記事で,

otaku-of-suri.hatenablog.com

最後に証明を残したところがあるので,それだけ示したいと思います.示すべきことは0{<}q{<}1において

\displaystyle\sum_{n=1}^{\infty}\frac{q^n}{1-q^n}<\infty

です.二通りほど示し方を考えました.
ダランベールの収束判定法を用いる
ダランベールの収束判定法を使えば簡単に示せます.

\displaystyle a_n=\frac{q^n}{1-q^n}

と置くと,n\to\infty

\displaystyle\frac{a_{n+1}}{a_n}=\frac{q^{n+1}}{1-q^{n+1}}\cdot\frac{1-q^n}{q^n}=q\cdot\frac{1-q^n}{1-q^{n+1}}\to q<1

となるので示せました.

ちょっとテクる
うまい(?)方法を思いついたので書いてみます.q<1なのでq1の中点を取ると

\displaystyle q{<}\frac{q+1}{2}{<}1

となります.これを使うと

\displaystyle q^n<\frac{q+1}{2}\iff\frac{1}{1-q^n}<\frac{2}{1-q}

が分かります.これをはじめの式に適用すると

\displaystyle\sum_{n=1}^{\infty}\frac{q^n}{1-q^n}{<}\frac{2}{1-q}\sum_{n=1}^{\infty}q^n=\frac{2q}{(1-q)^2}

となり示されました.

それでは.