2008年11月14日 (金)

KMP法とBM法

最近寒くなりましたね・・・最近日も短くなってきて冬が始まるという感じですね.

さて,最近文字列照合のアルゴリズムについて勉強しています.

まず文字列照合の最も単純なアルゴリズムは,テキストと照合させる文字を頭から照合させ,照合が失敗したところでテキストの文字を1文字ずらして検索するという方法です.しかし,このアルゴリズムでは効率が悪いです.そこでもっと効率の良いアルゴリズムとしてKMP法とBM法があります.しかし,このアルゴリズムがまたややこしくて理解するのが大変でした・・・

もっと簡単に理解できないものなんですかね.

| | コメント (0) | トラックバック (0)

2008年11月10日 (月)

半群

今日,某学校の授業で半群を習った.半群とは,集合A(≠Φ)上での2項演算・が結合律を満たす,すなわち (a・b)・c = a・(b・c) が成り立つとき(A,・)は半群という.詳しくは自分で調べて見てください.

その授業で集合{0,1}での2項演算は2^4=16(通り)ありますが,そのなかで半群となるのは8通り存在する.半群かを判定するのは,実際に数値を代入し,結合律が成り立つのかを確認するという作業をしなければならず,非常にめんどくさい(何か良い判定法があるのだろうか・・・)

そこで,プログラミング(C言語)で上の2項演算の16通りのうちどれが半群になっているか調べるものを作成したいと思います.プログラム・結果はそのうち載せたいと思います.

| | コメント (0) | トラックバック (0)

2008年11月 9日 (日)

blogスタート

本日からblogスタートします.(今更ですが・・・)

まぁよろしくお願いします.

| | コメント (0) | トラックバック (0)