//tips
今のところ数学しか出てきていない・・・
//少しずつ基本技術理解
集合論理から確認。
1,2,3からなる集合Uの部分集合の数は、空集合およびU全部を含めて2^N乗で表される。
Nは要素数。
集合B>集合A ：真部分集合
集合Aで集合B出ないもの差集合。
それぞれの差集合を合わせたものをAとBの対称差という。
集合Aの要素数はn(A)と表す。
命題にある変数xを含み、そのxによって真偽が決まる命題を条件命題・命題関数といいp(x)のように表される。
なぜこれが出てきたのか探っていると0,1で表されるビットの反転、そこから暗号化などにつながるよう。
処理の対象となる事象は、全て有限長のビット列に符合される。
この情報量(ビット)は情報量I(J)=-log1p(J)で表される。p(J)は事象Jの発生確率。
1/2の確率の時は1ビット、1/6の確率の時は約2.58ビットと発生確率が少なくなるほど情報量が大きくなる性質を持つ。
これはある情報を表現するのに何ビット必要かを逆に規定できるものになり、例えば英語大文字2文字を26文字の中から選ぶとすると、26×26=676通りの表現ができ、1/676の確率を考えると10ビットの情報量が必要となることがわかる。
情報の伝達を行う際に、できるだけ情報を圧縮して送る情報源符号化が行われ、ハフマン符号化では各文字の出現確率をベースにし、出現度の高い文字は短いビット列で、低い文字は長いビット列で符号化することで、１情報源あたりの情報量を抑えている。
a,b,c,dの出現確率に合わせてビット表記がされている。
符号化を行う場合は出現率が一番高いものを根元に置き、枝分けしていくハフマン木という手法が用いられている。次に高い確率を左の枝へおき0を加算,その次に高い確率を右の枝におき1を加算。確率が最小のものを次の根に選び、これをずっと繰り返していく。
ランレングス符号化というものもあり、これはデータ列の冗長度に着目し、同じデータ値が連続するものを反復回数とデータ値の組みに置き換えることでデータを圧縮する。例えばaaaなどは3aとして圧縮する。
また、パルス符号変調(PCM)というものもあり、アナログ信号を一定間隔で切り出し、デジタル値に変換、この際のビット数を量子化ビット数という。8ビットであれば0~255の数字に変換される。ここで得られた値を２進符号形式に変換。
デジタル数値への変換を通すことで短縮することになる。
対象となるアナログ信号の最高周波数をfとすると、2f以上の周波数で標本化すれば復元できるよう。なのでサンプルでは周波数の２倍でサンプリングを行うことになる。
１秒間に生成されるデジタルデータはサンプリング周波数×量子化ビット数となるとのこと。
暗号化には、一つの入力値によって一つの出力値が決まるのではなく。入力値と入力された時の状態によって出力値が決まる順序機械がある。
エニグマのようなものか。
有限オートマンはこの順序機械に言語を認識するアルゴリズムを与えた数学的なモデル。
ある言語で記述されたプログラムを実行する際には、その文法に基づいたコンパイルが行われる。
コンパイル処理で行われる、字句解析と構文解析を自動化するためには、それらの規則を適切に定義する必要がある。
字句規則は正規表現を用いて表すことができる。
構文解析は、切り出された字句の文法的正当性を検査する。
ここで行われているのは記述されたスクリプトを機械に認識させるために機械語に対応させる部分のよう。
BNF記法が代表的。
<因子>::=数
<因子>::=数|’(‘<式>’)’
<式>::=<項>|<式><加算演算子><項>
項一つでも式で、項から式になったものに加減演算子、項が続いたら式となる、と解釈できるとのこと。
ここは例文をたくさん読んで図化するしかない。
これらの処理も樹形図ベースなので、図形図の各パートを切り取って最終的な計算結果を導けるようにしていく必要がある。
L1(*,2,3,EX1)などと描かれるように、そもそものEX1=2*3を機械が認識できるよう変換する必要があるよう。
正規表現のメタ記号：
[m-n]:m~nまでの連続した文字の中の1文字を表す
*:直前の正規表現の0回以上の繰り返しを表す。
+:直前の正規表現の1回以上の繰り返しを表す。
?:直前の正規表現が０か１であることを表す。
r1|r2:正規表現r1または正規表現r2であることを表す。
[A-Z]+[0-9]*は英語大文字が1回以上繰り返され、続いて数字が0回以上繰り返されることを表す。
Phpで、電話番号や郵便番号の認証の際に使っていた。
kimi|kami|keamiはk(i|e?a)miと表される。
グラフにおいて頂点はvertex,辺はedgeという。
頂点を結ぶことで変ができる。この際に方向が加えられているものを有向グラフ、加えられていないものを無向グラフという。
グラフを表現する際には、配列、行列、リストなどが用いられる。
モンテカルロ法は乱数を応用して求める解や法則性の近似を得る方法。Πの計算が有名。
