diff 2015/0728.html @ 31:5789a3236295

add 0728
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Tue, 21 Jul 2015 19:58:36 +0900
parents 2015/0714.html@8c0e9991bf65
children
line wrap: on
line diff
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/2015/0728.html	Tue Jul 21 19:58:36 2015 +0900
@@ -0,0 +1,276 @@
+<!DOCTYPE html>
+<html>
+<head>
+  <meta http-equiv="content-type" content="text/html;charset=utf-8"> 
+  <title>seminar</title>
+
+<!-- 
+   Notes on CSS media types used:
+ 
+   1) projection -> slideshow mode (display one slide at-a-time; hide all others)
+   2) screen     -> outline mode (display all slides-at-once on screen) 
+   3) print      -> print (and print preview)
+  
+   Note: toggle between projection/screen (that is, slideshow/outline) mode using t-key
+
+   Questions, comments?
+   - send them along to the mailinglist/forum online @ http://groups.google.com/group/webslideshow    
+-->
+
+<!-- styles  -->
+<style media="screen,projection">
+
+html,
+body,
+.presentation { margin: 0; padding: 0; }
+
+.slide { display: none;
+         position: absolute;
+         top: 0; left: 0; 
+         margin: 0;
+         border: none;
+         padding: 2% 4% 0% 4%;         /* css note: order is => top right bottom left  */
+         -moz-box-sizing: border-box;
+         -webkit-box-sizing: border-box;
+         box-sizing: border-box;
+         width: 100%; height: 100%;    /* css note: lets use border-box; no need to add padding+border to get to 100% */
+         overflow-x: hidden; overflow-y: auto;
+         z-index: 2;
+       }
+
+.slide.current { display: block; }  /* only display current slide in projection mode */
+
+.slide .stepcurrent { color: black; }
+.slide .step        { color: silver; } /* or hide next steps e.g. .step { visibility: hidden; } */
+
+.slide {
+/*
+  background-image: -webkit-linear-gradient(top, blue, aqua, blue, aqua);
+  background-image: -moz-linear-gradient(top, blue, aqua, blue, aqua);
+*/
+}
+</style>
+
+<style media="screen">
+.slide             { border-top: 1px solid #888; }
+.slide:first-child { border: none;  }
+</style>
+
+<style media="print">
+.slide    { page-break-inside: avoid; }
+.slide h1 { page-break-after:  avoid; }
+.slide ul { page-break-inside: avoid; }
+</style>
+
+
+<!-- add js lib (jquery) -->
+<script src="js/jquery-1.7.min.js"></script>
+
+<!-- S6 JS -->
+<script src="js/jquery.slideshow.js"></script>
+<script src="js/jquery.slideshow.counter.js"></script>
+<script src="js/jquery.slideshow.controls.js"></script>
+<script>
+  $(document).ready( function() {
+    Slideshow.init();
+    
+    // Example 2: Start Off in Outline Mode
+    // Slideshow.init( { mode: 'outline' } );
+    
+    // Example 3: Use Custom Transition
+    // Slideshow.transition = transitionScrollUp;
+    // Slideshow.init();
+
+    // Example 4: Start Off in Autoplay Mode with Custom Transition
+    // Slideshow.transition = transitionScrollUp;
+    // Slideshow.init( { mode: 'autoplay' } );
+  } );
+</script>
+
+</head>
+<body>
+
+<div class="presentation">
+
+  <div class='slide cover'>
+  <table width="90%" height="90%" border="0" align="center">
+  <tr>
+  <td><div align="center">
+      <h1>Cerium 上での正規表現の実装</h1>
+      </div>
+  </td>
+  </tr>
+      <tr>
+      <td><div align="right">
+          <name>Masataka Kohagura 14th, July , 2015</name>
+      </div></td>
+      </tr>
+  </tr>
+  </table>
+  </div>
+
+  <div id="cover">
+    <h1>研究目的</h1>
+    正規表現はオートマトンに変換することができ、 そしてオートマトンの受理の問題は Class NC と呼ばれる問題でもある。<br>
+    この問題は計算機の台数が多ければ多いほど高速化できるという特徴を持ち、並列化に向いている問題といえる。<br>
+    コンピュータの動作やゲームの動作などの多くの問題はオートマトンの受理問題に落としこむことができるので、この問題を解決すれば様々な問題に対応できるようになる。<br>
+    本研究では正規表現を並列処理で実装することによってこの問題を解決し、Class NC に対応するライブラリを作成する。
+        </ul>
+  </div>
+
+  <div id="cover">
+    <h1>したこと</h1>
+    characterClass 以外を実装
+
+  </div>
+
+  <div id="cover">
+    <h1>BNF記法で正規表現の文法規則を表記してみる</h1>
+    <ul>
+    <li>
+&lt;literal&gt; ::= [a-z][A-Z][0-9]
+    </li>
+    <li>
+&lt;characterClass&gt; ::= '['&lt;literal&gt;'-'&lt;literal&gt;']'
+    </li>
+    <li>
+&lt;string&gt; :: = &lt;literal&gt; | &lt;literal&gt;*
+    </li>
+    <li>
+&lt;or&gt; ::= '('&lt;regex&gt;'|'&lt;regex&gt;')'
+    </li>
+    <li>
+&lt;*&gt; ::= &lt;regex&gt;'*'
+    </li>
+    <li>
+&lt;regex&gt; ::= &lt;literal&gt;|&lt;string&gt;|&lt;or&gt;
+    </li>
+    </ul>
+&lt;or&gt; が '|' とグループ化の '('')' とまだ分解できるので、&lt;or&gt; を &lt;or&gt; と &lt;group&gt; に分割
+  </div>
+
+  <div id="cover">
+    <h1>BNF記法で正規表現の文法規則を表記してみる(修正後)</h1>
+    <ul>
+    <li>
+&lt;literal&gt; ::= [a-z][A-Z][0-9]
+    </li>
+    <li>
+&lt;characterClass&gt; ::= '['&lt;literal&gt;'-'&lt;literal&gt;']'
+    </li>
+    <li>
+&lt;string&gt; :: = &lt;literal&gt; | &lt;literal&gt;*
+    </li>
+    <li>
+<font color=red>&lt;group&gt; ::= '('&lt;regex&gt;')' &lt;- 追加</font>
+    </li>
+    <li>
+<font color=blue>&lt;or&gt; ::= &lt;regex&gt;'|'&lt;regex&gt; &lt;- 修正</font>
+    </li>
+    <li>
+&lt;*&gt; ::= &lt;regex&gt;'*'
+    </li>
+    <li>
+&lt;regex&gt; ::= &lt;literal&gt;|&lt;string&gt;|&lt;or&gt;
+    </li>
+    </ul>
+  </div>
+
+  <div id="cover">
+    <h1>問題点</h1>
+    <p>正規表現 a*b の tree 構造(本当はこうなってほしい)</p>
+
+    <object data="images/vector/aastabtrue.svg" type="image/svg+xml"></object><br>
+    <p>正規表現 a*b の tree 構造(現状)</p>
+    <object data="images/vector/aastabfalse.svg" type="image/svg+xml"></object><br>
+  </div>
+
+  <div id="cover">
+    <h1>問題点</h1>
+    <p>正規表現 a tree 構造(現状)</p>
+    <object data="images/vector/aonly.svg" type="image/svg+xml"></object><br>
+    <p>原因は string()</p>
+
+    <pre>
+    <code>
+NodePtr string() {
+    char c = *ptr;
+    NodePtr n = NULL;
+    if (isLiteral(c)) {
+        n = createNode(0,literal(),string());
+    } else {
+        n = createNode(0,0,0);
+    }
+    return n;
+}
+    </code>
+    </pre>
+    <p>string なのか literal なのか判断しないで createNode をしてる</p>
+  </div>
+
+  <div id="cover">
+    <h1>これからすること</h1>
+    <ul>
+    <li>
+    tree 生成の修正
+    </li>
+    <li>
+    tree を見やすく表示
+    </li>
+    </ul>
+  </div>
+
+
+<!--
+  <div id="cover">
+    <h1>今週のしたこと</h1>
+    例題 : ab(ab)+
+        <ul>
+            <object data="images/vector/abab.svg" type="image/svg+xml"></object><br>
+        </ul>
+        テキストが abab の途中で分割される場合を考える
+        <ul>
+            <object data="images/vector/ababautomata.svg" type="image/svg+xml"></object><br>
+        </ul>
+        分割されたファイルの1コ前の終わりが状態(3)の場合で、分割されたファイルの先頭が b の場合状態(4)に遷移して受理される。(正規表現にマッチする)
+        <ul>
+            <object data="images/vector/ababtable.svg" type="image/svg+xml"></object><br>
+        </ul>
+        <ul>
+            <object data="images/vector/bitvectorTable.svg" type="image/svg+xml"></object><br>
+        </ul>
+  </div>
+-->
+
+<!--
+  <div id="cover">
+    <h1>prog</h1>
+    <ul>
+    <li>
+
+    </li>
+
+    <pre>
+    <code>
+typedef struct SDL_AudioSpec {
+    int freq;          /** DSP frequency samples per second */
+    Uint16 format;     /** Audio data format */
+    Uint8  channels;   /** Number of channels: 1 mono, 2 stereo */
+    Uint8  silence;    /** Audio buffer silence value (calculated) */
+    Uint16 samples;    /** Audio buffer size in samples (power of 2) */
+    Uint16 padding;    /** Necessary for some compile environments */
+    Uint32 size;       /** Audio buffer size in bytes (calculated) */
+    void (SDLCALL *callback)(void *userdata, Uint8 *stream, int len);
+    void  *userdata;
+} SDL_AudioSpec;
+    </code>
+    </pre>
+    <img src="./images/sqrWave.png" width="50%" height="">
+    </ul>
+  </div>
+
+-->
+
+</div> <!-- presentation -->
+</body>
+</html>