Mercurial > hg > Members > masakoha > seminar
diff 2015/0609.html @ 29:39f9309334f9
add 0714.html
author | Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 14 Jul 2015 17:23:24 +0900 |
parents | 0bec56f5c23f |
children |
line wrap: on
line diff
--- a/2015/0609.html Tue Jun 09 17:13:09 2015 +0900 +++ b/2015/0609.html Tue Jul 14 17:23:24 2015 +0900 @@ -102,7 +102,7 @@ </tr> <tr> <td><div align="right"> - <name>Masataka Kohagura 2nd, June , 2015</name> + <name>Masataka Kohagura 9th, June , 2015</name> </div></td> </tr> </tr> @@ -111,35 +111,51 @@ <div id="cover"> <h1>研究目的</h1> - <ul> - <li> - 当研究室では並列プログラミングフレームワーク Cerium Task Manager でプログラミングを行っている。 - </li> - <li> - - </li> - <li> - </li> - <li> - </li> - </ul> - </div> - - - <div id="cover"> - <h1>正規表現を有限オートマトンで書いてみる</h1> - 例題 : (a|aa|aaa)*b - <ul> - <object data="images/vector/automata.svg" type="image/svg+xml"></object><br> - </ul> - 非決定性オートマトンから subset Constraction - <ul> - <object data="images/vector/dfa2tosubset.svg" type="image/svg+xml"></object><br> + 正規表現はオートマトンに変換することができ、 そしてオートマトンの受理の問題は Class NC と呼ばれる問題でもある。<br> + この問題は計算機の台数が多ければ多いほど高速化できるという特徴を持ち、並列化に向いている問題といえる。<br> + コンピュータの動作やゲームの動作などの多くの問題はオートマトンの受理問題に落としこむことができるので、この問題を解決すれば様々な問題に対応できるようになる。<br> + 本研究では正規表現を並列処理で実装することによってこの問題を解決し、Class NC に対応するライブラリを作成する。 </ul> </div> <div id="cover"> - <h1>正規表現を有限オートマトンで書いてみる</h1> + <h1>今週のしたこと</h1> + <ul> + <li> + 正規表現の parser を再帰下降法で実装(まだ途中) + </li> + </ul> + </div> + + <div id="cover"> + <h1>BNF記法で正規表現の文法規則を表記してみる</h1> + <ul> + <li> +<literal> ::= [a-z][A-Z][0-9] + </li> + <li> +<characterClass> ::= '['<literal>'-'<literal>']' + </li> + <li> +<string> :: = <literal> | <literal>* + </li> + <li> +<or> ::= '('<regex>'|'<regex>')' + </li> + <li> +<*> ::= <regex>'*' + </li> + <li> +<regex> ::= <literal>|<string>|<or> + </li> + </ul> + + BNF 記法での表現どおりにプログラムを落とし込めば、再帰下降法でうまく実装できそう? + </div> + +<!-- + <div id="cover"> + <h1>今週のしたこと</h1> 例題 : ab(ab)+ <ul> <object data="images/vector/abab.svg" type="image/svg+xml"></object><br> @@ -156,42 +172,7 @@ <object data="images/vector/bitvectorTable.svg" type="image/svg+xml"></object><br> </ul> </div> - - <div id="cover"> - <h1>状態を bit列で表現</h1> - 状態をビットで表現するため、bitSet を実装した。 - - <pre> - <code> - -typedef struct bitInfo { - int arrayNum; - unsigned long *bitContainer; -}BitInfo,*BitInfoPtr; - -void bitSet(BitInfoPtr bi, int bitSetPosition) { - - unsigned long tmp = 1; - int arrayPosition = 0; - - arrayPosition = bitSetPosition / 64; - bitSetPosition = bitSetPosition % 64; - - tmp = tmp << (63 - bitSetPosition); - bi->bitContainer[arrayPosition] = bi->bitContainer[arrayPosition] | tmp; -} - - </code> - </ul> -</pre> - </div> - - - <div id="cover"> - <h1>次にやること</h1> - bitVector を生成するため、正規表現の parser を記述する - </div> - +--> <!-- <div id="cover">