2017-02-10

後期の振り返りするで。

よねすけ

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

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

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

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

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

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

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

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

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

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

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

作者: D.コックス,落合啓之
出版社/メーカー: 丸善出版
発売日: 2012/07/17
メディア: 単行本
この商品を含むブログを見る

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

2017-01-28

正則言語

よねすけ数学計算理論

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

正則言語

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

決定性有限状態オートマトン( ${\rm DFA}$ )で表される言語
非決定性有限状態オートマトン( ${\rm NFA}$ )で表される言語
$\varepsilon$ 遷移非決定性有限状態オートマトン( $\varepsilon-{\rm NFA}$ )で表される言語

すなわち上の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の逆から示されます.

それでは

2017-01-27

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

よねすけ計算理論数学

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

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

帰納的可算集合(Recursively Enumerable)

言語 $L$ が帰納的可算集合であるとは, あるTM $M$ によって

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

帰納的集合(Recursive)

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

$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を受理しない\}$ です. この言語が対角線論法を用いて示されることでも有名です.

それでは

2016-12-22

愛情の数学

cajihara 数学

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

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

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の項目もあるぐらいなのでかなり有名な話っぽいですが，
高１の時にこの事実を知って以来お気に入りの数学小話(?)のひとつなので，どうしても書きたかったのです．）

次回は，

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

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

おしまい．

2016-12-18

答え

よねすけ数学

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

前回の記事で,

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$ なので $q$ と $1$ の中点を取ると

$\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}$

となり示されました.

それでは.

2016-12-11

おもろい式

よねすけ数学

こんにちは,よねすけです.
明日はじめて阪大に行くのが楽しみすぎて眠れない.遠足の前の日みたいや.

高木貞治の『解析概論』をぼーっとめくってたら

定本解析概論

作者: 高木貞治
出版社/メーカー: 岩波書店
発売日: 2010/09/16
メディア: 単行本（ソフトカバー）
購入: 1人クリック: 49回
この商品を含むブログ (14件) を見る

オモロい式を見つけました.

$\displaystyle\frac{q}{1-q}+\frac{q^3}{1-q^3}+\frac{q^5}{1-q^5}+\cdots=\frac{q}{1-q^2}+\frac{q^2}{1-q^4}+\frac{q^3}{1-q^6}+\cdots$

ただし, $|q|<1$ です.普通に証明するのは簡単やった.

$\displaystyle\begin{eqnarray} (左辺)&=&\sum_{n=0}^{\infty}\frac{q^{2n+1}}{1-q^{2n+1}}\\ &=&\sum_{n=0}^{\infty}q^{2n+1}\left(\sum_{m=0}^{\infty}\left(q^{2n+1}\right)^m\right)\\ &=&\sum_{n=0}^{\infty}\left(\sum_{m=0}^{\infty}q^{(2n+1)(m+1)}\right)\\ (右辺)&=&\sum_{n=0}^{\infty}\frac{q^{n+1}}{1-q^{2(n+1)}}\\ &=&\sum_{n=0}^{\infty}q^{n+1}\left(\sum_{m=0}^{\infty}\left(q^{2(n+1)}\right)^m\right)\\ &=&\sum_{n=0}^{\infty}\left(\sum_{m=0}^{\infty}q^{(2m+1)(n+1)}\right)\\ &=&\sum_{m=0}^{\infty}\left(\sum_{n=0}^{\infty}q^{(2n+1)(m+1)}\right) \end{eqnarray}$

となります.なのであと示すべきことはこの無限和が交換できることです.二重級数は絶対収束すれば足し算の順番を交換しても大丈夫なのでこいつらが絶対収束することを示しましょう.示すべきことは

$\displaystyle\sum_{n,m=0}^{N}|q|^{(2n+1)(m+1)}\leq M$

なる $M$ が $N$ の値によらずに存在することです.こいつが案外厄介.

$\displaystyle\begin{eqnarray} \sum_{n,m=0}^{N}|q|^{(2n+1)(m+1)}&\leq&\sum_{n=0}^{N}\frac{|q|^{2n+1}}{1-|q|^{2n+1}}\\ &\leq&\sum_{n=1}^{\infty}\frac{|q|^n}{1-|q|^n} \end{eqnarray}$

こいつが有界である(収束する)ことは各自頑張って証明してみて下さい*1.

(無限和)=(無限和)の形やから,ポアソンの和公式から示せたらエレガントやなあ,とか思った.

それでは.

*1:ここに証明をいくらか書いてみました.良かったら読んで下さい. otaku-of-suri.hatenablog.com

2016-12-09

そもそも虚軸ってなんなの

cajihara 数学

こんにちは．かじはらです．

今日はこんな問題を考えてみます．

${ \displaystyle x^2 = -1 }$

この式を「一次元の世界の計算」と呼んでおきましょう．

これは考える範囲を複素数としなければ解をもたず．

${ \displaystyle x = \pm i }$

となります．簡単ですね．

さて，複素数はどんなものかといわれたら多くの人が次の式を思い起こすと思います．

${ \displaystyle z = x + iy　(z \in \mathbb{C},\, x,y \in \mathbb{R}) }$

複素数を座標で表すときに，ちょうどこのxを直交座標のx軸に対応させて実軸と呼び，yをy軸に対応させて虚軸と呼びました．

式で見ると当然のように思えますがそもそもなぜ虚軸をy軸と対応させたのでしょうか．

そこでいったんさっきの問題をわきに置いて次の問題を考えたいと思います．

${ \displaystyle \left( \begin{array}{cc} a & b \\ c & d \end{array} \right)\left( \begin{array}{cc} a & b \\ c & d \end{array} \right) = \left( \begin{array}{cc} -1 & 0 \\ 0 & -1 \end{array} \right)\\ が成り立つような実数a,b,c,dを求めよ． }$

実際に計算すればわかることですがこの問題の解は実は無数にあります．ここでは最も簡潔だと思われる

${ \displaystyle \left( \begin{array}{cc} 0 & -1 \\ 1 & 0 \end{array} \right) }$

を採用しましょう. この行列を $X$ と置き，最初の問題を書き直すと

${ \displaystyle X^2 = -I }$

となります．これを「二次元の世界の計算」と呼びましょう．最初に考えた「一次元の世界の計算」と形がとても似ていますね．

「一次元の世界」で掛け算を考えたとき，その単位元は「1」です。その世界で「ある一次の行列を２乗すると-1になる数」を考えようとすると実数の範囲では答えが見つからず，複素数という概念を導入しなければならなくなりました．

「二次元の世界」で掛け算を考えたとき，その単位元は「 $I$ 」です．「ある二次の行列を２乗すると $-I$ になる数」を考えるとちゃんと実数の範囲で答えが見つかります．

ここまでくると一次元だった(実数の)直線を複素数に拡張しよう，つまり虚数単位を導入しようとするとき，二次元である平面を考える発想はとても自然なことに思えてきませんか？

ではなぜ虚軸は「x軸と直交をなすy軸」なのでしょうか．単に平面を考えるだけなら別に直交していなくてもいいはずですよね．（まあ直交してるものを考えるのが一番わかりやすいじゃん，と言われてしまうとその通りなのですが．）

行列 $X$ をこんな風に書き換えてみましょう．

${ \displaystyle X = \left( \begin{array}{cc} 0 & -1 \\ 1 & 0 \end{array} \right) =\left( \begin{array}{cc} \cos 90^\circ & -\sin 90^\circ \\ \sin 90^\circ & \cos90^\circ \end{array} \right) }$

回転行列がでてきました．つまり「二次元の世界」で $X^2 = -I$ の解となる行列（のひとつ）は直交座標を90度回転させるようなものだということになります．

つまり実軸を(正の符号を採用すれば反時計回り，負の符号なら時計回りに)90度回転させたものが虚軸に対応する，ということが，こう書くととても腑に落ちますね．わーい．

なんだかまわりくどく書いてしまいました．

そもそもどうしてこんなことを書いたかと言うと，高校数学の新課程に関して，素人ながら少し思うことがあったからです．

高校数学の新課程では行列がなくなり，複素平面が復活しました．

でも，今までの議論を思い出すと，この新課程には違和感を覚えます．

今日本屋で高校数学の参考書の複素平面のページを見たら，最初に

${ \displaystyle z = x + iy　(z \in \mathbb{C},\, x,y \in \mathbb{R})\\ i = \sqrt{-1} }$

こういう式がいきなり書いてあるものが多くて，それ以降は共役がどうの，絶対値がどうの，といったことが書いてあって．

高校の頃，どうやって複素平面について学んだのかはよく覚えてませんが，もし今の自分が誰かに複素平面について説明しろ，と言われたら最初の行列の概念を使うと思うんです．だから行列を消して，複素数を復活させる，ということが，自分にとってはむずがゆい．

…偉そうに高校数学に文句を言ってしまいました．すみません．

最後まで読んでくれた方，ありがとうございます．

おしまい．

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

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

後期の振り返りするで。

正則言語

正則言語

正則言語の閉包性

証明

正則言語の性質

Pumping Lemma

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

帰納的可算集合(Recursively Enumerable)

帰納的集合(Recursive)

愛情の数学

答え

おもろい式

そもそも虚軸ってなんなの