「大人の教養・知識・気付き」を伸ばすブログ

一流の大人(ビジネスマン、政治家、リーダー…)として知っておきたい、教養・社会動向を意外なところから取り上げ学ぶことで“気付く力”を伸ばすブログです。目下、データ分析・語学に力点を置いています。

MENU

計算理論(その01/X)

0. 序章

0.1 オートマトン、計算可能性および複雑性

 本書はオートマトン、計算可能性および複雑性を扱う。これらは以下の問いに結びついている:

コンピュータの根本的な可能性と限界とは何か?

オートマトン、計算可能性および複雑性の各領域において、この質問はそれぞれ異なる解釈がなされる。

     
領域
内容
    (1) オートマトン 計算の数理モデルが持つ定義や性質を扱う。
    (2) 計算可能性 計算問題が解決可能か否かを類別する。
    (3) 複雑性 計算が困難であるまたは容易であるかを決定づける

ものは何かを議論する。

0.2 数学的用法

 以降、基礎的な数学的用法を扱う(以降、ここでは一般的な高校・大学数学で扱う範囲の議論は省略し、一般的な数学における用語と言い回しが異なったり、新しい概念、以降のために確認した方が良いもののみ扱う。)。

0.2.1 タプル

オブジェクトの数列はある順序で並んだオブジェクトのリストである。以降では数列を



\begin{aligned}
(7,21,57)
\end{aligned}


と括弧「"()"」で囲うことで表現することにする。数列では順番に意味があるため、(7,21,57)(21,7,57)は異なるものとして扱う*1
 数列は無限の場合と有限の場合がある。有限の場合を特にタプルということがある。
 A,Bを2つの集合とするとき、AB\mathrm{Descartes}A\times B*2はその第一成分がAに、その第二成分がBに属するような順序を持ったすべての組み合わせをいう。

0.2.2 述語

 関数の中でもその値域が\mathrm{TRUE},\mathrm{FALSE}のいずれかしか取り得ないものを述語(\mathrm{predicate},\ \mathrm{property})という*3。たとえば入力した自然数が偶数ならば真、そうでなければ偽と返す関数evenは述語である。
 その定義域がk次タプルA\times A\times\cdots\times Aであるような述語を関係(relation)*4、特にk項関係という。


 関数として書く代わりに述語と集合をまとめて表記する方がより便利な場合がある。述語P:\mathcal{D}\rightarrow\{\mathrm{TRUE},\mathrm{FALSE}\}(P,S)と書かれることがある。ここでS=\{a\in D| P(a)=\mathrm{TRUE}\}である。


 特別な二項関係として同値関係(equivalence relation)がある。これは2つのオブジェクトが何らかの特徴の観点で同等である(equal)ことを捉える概念である。二項関係Rが同値関係であるとはRが以下の性質を持つことをいう:

  1. Rは反射律を満たす:{}^{\forall}x(xRx)
  2. Rは対称律を満たす:{}^{\forall}x,{}^{\forall}y\left(xRy=yRx\right)
  3. Rは推移律を満たす:{}^{\forall}x,{}^{\forall}y,{}^{\forall}z\left(xRy,yRz\Rightarrow xRz\right)
0.2.3 グラフ

 無向グラフ*5はその一部*6が線で連結した点の集合である。グラフ理論では点はノード(node)や頂点(vertex)と呼ばれ、線はエッジ(枝・辺)と呼ばれる。
 ある特定のノードが持つエッジの数を次数(degree)という。任意の2つのノード間には1つの辺までしか許されない。状況によってはループと呼ばれる、自分へのノードを許す場合もある。

 ノードi,jを含むグラフGにおいて組み合わせ(i,j)i,jを連結する枝を表す。無向グラフではi,jの順序は重要ではなく、そのため(i,j)(j,i)は同じ枝を表す。順序の無い組み合わせを集合の記法\{i,j\}で無向の枝を表す場合がある。もしVGのノードの集合、Eが枝の集合だとするならば、G=(V,E)と書く。グラフは図またはより形式的に特定のV,Eにより表現することができる。


 グラフは時にデータを表現するのに用いられる。ノードが都市、辺がそれらをつなぐ高速道路を、もしくはノードが人、辺がその間の友好関係を表すことがある。利便性のためにグラフのノードおよび/または辺は、このときラベル付けされたグラフと呼ばれることもある。

 グラフGのノードがHのノードの部分集合で、Gの辺が対応するノードのHの辺であるとき、GHサブグラフであるという。





 グラフにおけるパス(経路)は枝により結ばれたノードの列である。単純パスはどのノードも2度経由しないパスを表す。もし任意の2つのノードにそれらをつなぐ経路があるならばグラフは連結している(connected)という。パスが同じノードで始まって終えられるならばそのパスを循環(cycle)という。少なくとも3つのノードを持ち最初のノードと最終のノードのみが繰り返すような循環を単純循環という。グラフが木(tree)であるとは、連結しているが単純循環を持たないようなグラフである。


 有向グラフは線の代わりに矢印で表す。ある特定のノードから出て行く矢印の数をそのノードの出次数(outdegree)といい、ある特定のノードに入る矢印の数を入次数(indegree)という。有向グラフにおいてノードiからjへのエッジを組み合わせ(i,j)で表す。有向グラフGは形式的には(V,E)で書く。ここでVはノードの集合で、Eは辺の集合である。すべての矢印が同じ方向を向いて進んでいるようなパスを有向パスという。有向パスがすべての2つのノードをつないでいるならば有向グラフは強く連結されているという。有向グラフは二項関係を用いるのが簡単な表現方法である。もしRが定義域をD\times Dとするような二項関係であるならば、ラベル付けされたグラフG=(D,E)Rを表す。このときE=\{(x,y)|xRy\}である。

0.3 文字列(string)と言語

 文字列(strings of characters)はコンピュータ科学において基本的な構成要素である。ここではアルファベットを任意の空でない有限集合だとし、アルファベットの元はアルファベットを表す記号である。通常、アルファベットおよびアルファベットに属する記号を表現するための字体を表すのにそれぞれ\Sigma, \Gammaを用いる。以下がアルファベットの例である:



\begin{aligned}
\Sigma_1&=\{0,1\},\\
\Sigma_2&=\{a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z\},\\
\Gamma&=\{0,1,x,y,z\}
\end{aligned}


 あるアルファベットからの文字列(string over an alphabet)はそのアルファベットからの記号からなる有限の数列を指し、普通はお互いに隣り合わせで書き、コンマで区切らない。たとえばアルファベット\Sigma_1=\{0,1\}に対して01001はアルファベット\Sigma_1からの文字列である。w\Sigma_1からの文字列であるとき、w長さ(length)|w|と書き、その文字列が含む記号の数を言う。長さが0であるような文字列は空記号といい、\mathcal{\varepsilon}で表す。文字列wが長さとしてnを持つ場合、ww=w_1w_2\cdots w_n,\ w_i\in\Sigma,\ i=1,2,\cdots,nと書くことができる。アルファベットwの逆元をw^Rと書くことにすれば、w^{R}=w_nw_{n-1}\cdots w_1である。またアルファベットw=w_1w_2\cdots w_nに含まれるアルファベットw_iw_{i+1}\cdots w_j,1\leq i\lt n,i\lt j\leq nを部分文字列(substring)という。たとえば\mathrm{ghi}\mathrm{abcdefghijk}の部分文字列である。

 アルファベットx=x_1x_2\cdots x_m,\ x_i\in\Sigma,i=1,2,\cdots,m,\ y=y_1y_2\cdots y_n,\ y_j\in\Sigma,j=1,2,\cdots,nに対してxyの連接xyxy=x_1\cdots x_my_1\cdots y_nで定義される。同じ文字列を何度も連結する場合はx^kでそれを表すこととする。

 文字列の辞書式順序は辞書における順序と同じものである。

0.4 ブール代数

 ブール代数\mathrm{TRUE},\ \mathrm{FALSE}の2値のみから構築された数学的体系である。当初は純粋数学として受容されてきたものの、今やこの体系はデジタル家電やコンピュータデザインにおける基礎と見なされている。ブール代数において\mathrm{TRUE},\ \mathrm{FALSE}はブール値といい、0,1で表現されることがある。ブール値は2つの可能性がある状況、たとえば高電圧と低電圧が起こり得る導体や真か偽を取り得る命題、\mathrm{yes}\mathrm{no}で答え得る質問に用いる。
 ブール値はブール演算子を用いて計算できる。

   否定(\mathrm{NOT}) \neg0=1,\neg1=0
   論理積(\mathrm{AND}) 1\land0=0,0\land1=0,0\land0=0,1\land1=1
   論理和(\mathrm{OR}) 0\land0=0,1\land0=1,0\land1=1,1\land1=1

 ブール演算子は、より複雑な算術結果を表すのに和や積を用いるように、単純な命題をより複雑なブール表現に結合するのに用いる。たとえば命題Pおよび命題Qに対してP\land QPかつQを意味する。Pの値をその演算の被演算子(\mathrm{operand})という。
 他のブール演算子が度々現れることもある。排他的論理和\mathrm{XOR}は、どちらか一方のみが1であるときに1となるような演算子で、\oplusで表される。また等価(\mathrm{quality})は両被演算子が同じ値であるときに1を返す演算子で、\leftrightarrowと書く。最後に実質含意(\mathrm{implication})は\rightarrowで表され、最初の被演算子1で2つ目が0であるときのみに0を返す演算子である。

   排他的論理和 等価 実質含意
   0\oplus0=0 0\leftrightarrow0=1 0\rightarrow0=1
   0\oplus1=1 0\leftrightarrow1=0 0\rightarrow1=1
   1\oplus0=1 1\leftrightarrow0=0 1\rightarrow0=0
   1\oplus1=0 1\leftrightarrow1=1 1\rightarrow1=1

これらの演算子を用いると様々な関係を構築できる。以下の各行は同値である。

P\lor Q  ⇔  \neg\left(\neg P\land \neg Q\right)
P\rightarrow Q  ⇔  \neg P\lor Q
P\leftrightarrow Q  ⇔  \left(P\rightarrow Q\right)\land\left(Q\rightarrow P\right)
P\oplus Q  ⇔  \neg\left(P\leftrightarrow Q\right)

\mathrm{AND}および\mathrm{OR}の分配則はブール表現を操作するのに便利である。

  • P\land\left(Q\lor R\right)=\left(P\land Q\right)\lor\left(P\land R\right)
  • P\lor\left(Q\land R\right)=\left(P\lor Q\right)\land\left(P\lor R\right)

*1:集合では順番は考えないため、\{7,21,57\}, \{21,7,57\}は同じものである。

*2:数学の文脈では直積と呼ぶ方が普通かもしれない。

*3:これはITにおける意味で、数学では自由変数を含む式のことを述語という。以降では無論、前者の意味を扱う。

*4:そのままカタカナで用いるのが普通なようだ。

*5:単にグラフということもある。

*6:自らも含み得る。

プライバシーポリシー お問い合わせ