ラベル 社内勉強会 の投稿を表示しています。 すべての投稿を表示
ラベル 社内勉強会 の投稿を表示しています。 すべての投稿を表示

2013年5月23日木曜日

「0がn個続いたあと1がn個続く」を正規表現にできるか?

こんにちは。前回に引き続きたぬきです。
週次LTの担当ということで、計算機科学の基礎を紹介してみました。

切り口として、正規表現まわりをやってみることにしました。Uzabaseは情報プラットフォームサービスSPEEDAを展開しており、どのエンジニアもデータベース周りの知識を持っているため、正規表現は慣れ親しんだものの１つであるからです。

具体的な問題として、「0がn個続いたあとに1がn個続く」を正規表現にできるか？をテーマとしました。

お話の流れとしては、(1) 正規表現は有限オートマトンに変換可能、(2) 有限オートマトンには必要条件がある、(3) 上述の問題は有限オートマトンの必要条件を満たさず、正規表現にはできない、という流れです。

ポンピング補題
オートマトンの復習および「(1) 正規表現は有限オートマトンに変換可能」については、文章よりスライドを見てもらえば十分かと思いますが、「(2) 有限オートマトンには必要条件がある」「(3) 上述の問題は有限オートマトンの必要条件を満たさず、正規表現にはできない」については口頭で話した部分を補足したいと思います。

(2) 有限オートマトンの必要条件のひとつに、ポンピング補題というものがあります。ある有限オートマトンの状態数をpとすると、そのオートマトンに認識される（受領される）文字列のうちp以上の長さの文字列は必ずポンピング補題の3条件を満たします。

条件のうちの1番目「各i≧0についてx(y^i)z∈A」についてもう少し意味を補足しましょう。まずAはある有限オートマトンが認識する（受領する）文字列の集合です。また、x(y^i)zとは、文字列xの後に文字列yが0回以上繰り返し続き、最後に文字列zがあるということです。つまり、1番目の条件は、ある有限オートマトンに認識される文字列は必ず、x(y^i)z∈Aを満たす文字列x, y, zにわけられるという意味になります。

ポンピング補題の証明は、スライドに記述した迷路のような図でも直感的に理解できるかもしれませんが、より詳しい証明は後述の本を御覧ください。

さて(3)に入り、「0がn個続いたあとに1がn個続く」がポンピング補題を満たすか調べてみましょう。もし「0がn個……」を満たす有限オートマトンがあるとすれば、その条件を満たす文字列で長さp以上のものはすべてポンピング補題を満たすはずです。

ここで、0がp個続いたあとに1がp個続く文字列sを考えてみましょう。sは明らかに「0がn個……」を満たします。またsは長さp以上なのでポンピング補題も満たすはずです。つまり「各i≧0についてx(y^i)z∈A」も満たすはずですが、どんなyならばそんな条件を満たすでしょうか？

 実はその条件を満たすyは存在しません。もしyが0からだけ成るとすると、i≧2では文字列に含まれる1の数よりも0の数が多くなってしまい、Aに含まれることができません。yが1からだけ成るとしても同様です。あとはyが0と1から成った場合だけですが、この場合、yが連続すれば0の前に1が出てきてしまうため、やはりAに含まれることができません。よって、いかなるyも条件を満たしません。

 以上のことから背理法により、「0がn個……」は有限オートマトンでないことが示されました。よって「0がn個……」は正規表現にできません。

まとめ
LTの時間的な制約から正確な定義などを説明せずに話を進めてしまいましたが、正確な定義や証明を理解していくと、とてもシンプルかつ奥深い世界に触れることができます。スライド内でも簡単に紹介していますが、下記の本がオススメです。
投稿者 時刻: 1 件のコメント:
ラベル: ,

2013年2月6日水曜日

ネットワークについて

k-kawaguchiこと川口と申します。
技術チーム定例社内研修会にて、ネットワークについて発表しました。


投稿者 時刻: 0 件のコメント:
ラベル:

2013年1月7日月曜日

アルゴリズムって何だ


私はさんさです。

アルゴリズムとはよくいわれるものの、それって実際どんなものだ

そんな勉強会を先日開きました。

アルゴリズムとは

Al Khwarizmiというイラクらへんの人が由来。
彼は科学者であり、数学、天文学などの多くの分野において業績を残したそうだ。
ちなみに「アル」はアラビア語の定冠詞である。アラビア語由来の単語に「アル」で始まる物が多いのはそのため。他にも
  • アルデバラン (Aldebaran)
  • アルタイル (Altair)
  • アルカイダ (Al Qaeda)
  • アルジャジーラ (Al Jazeera)
  • アルコール (Alcohol) 英語発音はアルコホールである、注意しよう

現在の用法

もっぱらコンピュータ業界で念仏のように唱えられるアルゴリズムだが、辞書によると
  1. もとは算用数字を用いた筆算のこと
  2. 計算や問題を解決するための手順、方式。特にコンピューターのプログラムに適用可能な手続き
出典 三省堂 大辞林
コンピュータでは適切な解を得るための手順を意味することが多い。
数学でもユークリッドの互除法や、エラトステネスの篩(ふるい)なんかは聞いたことがあったとしたら、それもアルゴリズム

よいアルゴリズムとわるいアルゴリズム

一般的によいアルゴリズムと呼ばれるのは以下の条件を満たしていることが多い。いや、満たしているべきだ。
  • 意図する結果が得られること
  • 計算時間、計算量が少なくすむこと
  • 同じ作業の繰り返しでできること
  • 使い方が限定されないこと
とりわけ重視されるのが計算時間、計算量が少なくすむことであり、この指標としてO記法なんてものが使われる。

O記法(オーダー記法)

ランダウの記号なんて別名があったりするが、ドヤ顔でいっても何もならない。実行されるアルゴリズムが、どれほどの時間、記憶領域を使用するかを評価するものである。
よく見るのは
  • O(1)
  • O(n)
  • O(n2)
  • O(n * log2n)

Oってどうやって求めるの

難しい話はさておき、このオーダーってどうやって求めるの？という話、なんと以下のようにするだけでできるのである。
  1. 計算量を示す式の最大次数に着目する
  2. 最大次数の係数を無視する
  3. Oとカッコをつけてやる
例：(1/6)(2n3 + 3n2 + n)という計算量があったとする
ちなみに自然数の二乗の値のnまでの和の式である。
  1. (1/6)(2n3) ... 最大次数以外はいらない
  2. n3 ... 係数はいらない
  3. O(n3)
最大次数などという呼び方をしたが、実際には計算量の中で一番増加の割合が大きなものを示したものともいえる。

ソート

アルゴリズムの例として挙げられるものといえばソートそれだけ種類が多く、計算量にも違いがあるからだ。
ここでは以下のソートについて、計算量やアルゴリズムを交えて説明する。
  • バブルソート
  • マージソート
  • クイックソート
  • ボゴソート

バブルソート

隣接交換法なんて名前がある。 一般人にトランプを渡して番号通りになるようにソートして、というとたいていこれか選択ソートをする、というぐらい誰でも思いつきそうな一般的なソート。
  • 平均計算時間はO(n2)
  • 安定ソート
安定ソートが何かわからないあなたはwikipedia。 アルゴリズムは単純明快である。
  1. n番目の要素が、n + 1番目より大きければいれかえる
  2. 1.を最初から最後まで行う
  3. 2.を要素の数だけくりかえす
コードにするとこんな感じ 
var bubbleSort = function(numbers) {
    var i = 0;
    var j = 0;
    var length = numbers.length;
    var temp = 0;

    for(i = 0; i < length - 1; i++) {
        for(j = 0; j < length - i - 1; j++) {
            if(numbers[j] > numbers[j + 1]) {
                swap(numbers, j, j + 1);
            }
        }
    }
};
隣り合う要素の交換が行われるため、隣接交換法と呼ばれたり、大きな数字が右側に移動していくさまが泡のようだからバブルソートなんて呼ばれているわけである。

マージソート

要素を分割、統合しながらソートする。安定した早さでソートできる。
  • 平均計算時間はO(nlog2n)
  • 分割、統合のしかた次第で安定ソートになる
  • javaのソートはこれを使用している
アルゴリズム
  1. 要素をn分割する(一般的にはn = 2)
  2. 1. を繰り返し、分割できなくなるまで分割する
  3. それらをマージする。マージの際にソートする
ただし、このソートには弱点があり、一時的に配列を別の場所に記憶しなければならない。
速度はそこそこである一方、記憶領域は消費するソートといえる。 
var mergeSort = function(numbers) {
    var sort = function(start, end) {
        var i = 0;
        var j = 0;
        var k = 0;
        var temp = [];

        if(start >= end) {
            return;
        }

        var mid = Math.floor((start + end) / 2);
        sort(Math.floor(start), mid);
        sort(mid + 1, Math.floor(end));
        for(i = start; i <= mid; i++) {
            temp[i] = numbers[i];
        }
        for(i = mid + 1, j = end; i <= end; i++, j--) {
            temp[i] = numbers[j];
        }
        i = start;
        j = end;
        for(k = start; k <= end; k++) {
            if(temp[i] <= temp[j]) {
                numbers[k] = temp[i];
                i++;
            }
            else {
                numbers[k] = temp[j];
                j--;
            }
        }
    };
    sort(0, numbers.length - 1);
};

クイックソート

その名の通り早いソート、ただし弱点があり、遅くなるとバブルソートと大して変わらない。
  • 平均計算時間はO(nlog2n)
  • 安定ソート*ではない*
アルゴリズム
  1. 要素の中から基準値を決める(ピボット、要素数/2番目の値が選ばれることが多い)
  2. 基準値より左側に小さい値を、大きい値を右側に入れ替えるように移動する
  3. 1., 2.を再帰的に繰り返す
このアルゴリズムの説明よりも、コードを見た方が早いと思う。 
var quickSort = function(numbers) {
    var sort = function(start, end) {
        var pivot = numbers[Math.floor((start + end) / 2)];
        var i = start;
        var j = end;

        while(true) {
            while(numbers[i] < pivot) {
                i++;
            }
            while(pivot < numbers[j]) {
                j--;
            }
            if(i >= j) {
                break;
            }
            swap(numbers, i, j);
            i++;
            j--;
        }
        if(start < i - 1) {
            sort(start, i - 1);
        }
        if(j + 1 < end) {
            sort(j + 1,end);
        }
    };

    sort(0, numbers.length - 1);
};

ボゴソート

とにかく遅くてダメなソート。バブルソート以下。
一般人にトランプを渡して番号通りになるようにソートして、といっても誰もやったことがないほどのソート。
  • 平均計算時間はO(n * n!)
  • 安定ソートではない
アルゴリズム
  1. 要素をシャッフルする
  2. 要素がソートされていたら終了、されていない場合は1. をくりかえす
ソートしろといっているのにいきなりシャッフルするのがこのソートのすばらしいところである。 
var bogoSort = function(numbers) {
    var shuffle = function(array) {
        var i = 0;
        var length = array.length;

        for(i = 0; i < length; i++) {
            var pos = Math.floor(Math.random() * (array.length - i)  + i);
            swap(array, i, pos);
        }
    };

    var isAscending = function(array) {
        var i = 0;
        var length = array.length;

        for(i = 0; i < length - 1; i++) {
            if(array[i] > array[i + 1]) {
                return false;
            }
        }
        return true;
    };
    var sort = function() {
        while(true) {
            if(isAscending(numbers)) {
                return;
            }
            shuffle(numbers);
        }
    }

    sort();
};

グラフで見る

計算量をグラフで比較するとこんな感じである。
縦軸がy, 横軸がxとなってしまっているが、件数xが増えるとどのぐらい計算量の目安が増えるかというのがよくわかる。
特にボゴソート(赤線)、君は真っ先に天を目指しすぎだ。

ソートをグラフィカルに見る

Jsdo.itにヨサゲなソートをしてくれるものがあったので紹介。
http://jsdo.it/norahiko/oxIy/fullscreen
ボゴソートのクソっぷりを満喫してほしい。
今回はここまで
投稿者 時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)