view 2015/0512.html @ 48:1306b24dc707 default tip

fix
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Wed, 24 Feb 2016 22:23:31 +0900
parents ef709768b9cf
children
line wrap: on
line source

<!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 12th, May , 2015</name>
      </div></td>
      </tr>
  </tr>
  </table>
  </div>

  <div id="cover">
    <h1>研究目的</h1>
        <ul>
            <li>
            当研究室では並列プログラミングフレームワーク Cerium Task Manager でプログラミングを行っている。
            </li>
            <li>

            </li>
            <li>
            </li>
            <li>
            </li>
        </ul>
  </div>

  <div id="cover">
    <h1>正規表現について</h1>
        <ul>
            <li>
            文字列の一部をパターン化して表現する手法
            </li>
            <li>
            文章からあるパターン文字列を検索したいときに使用する <br>
            (e.g. 「ed」が末尾に含まれる英単語を検索する場合 : .*ed)<br>
            . (ピリオド) : 改行コード以外の任意の1文字<br>
            * : 直前の文字の 0 回以上の繰返し
            </li>
        </ul>
  </div>

  <div id="cover">
    <h1>オートマトンについて</h1>
        <ul>
            <li>
            入力に対して内部の状況に応じた処理を行う結果を出力する仮想的な自動機械の概念
            </li>
            <li>
            正規表現はオートマトンで表現することができる。
            </li>
            <li>
            非決定性有限オートマトン NFA(Non-deterministic Finite Automaton)と、非決定性有限オートマトンDFA(Deterministic Finite Automaton)が存在する。
            </li>
            <li>
            非決定性有限オートマトン : 1つの入力に対して複数の遷移先が存在する
            </li>
        <object data="images/vector/nfa.svg" type="image/svg+xml"></object>
            <li>
            決定性有限オートマトン : 1つの入力に対して遷移先が1つだけ
            </li>
        <object data="images/vector/dfa.svg" type="image/svg+xml"></object>

        </ul>
  </div>

  <div id="cover">
    <h1>正規表現の基本三演算</h1>
        <ul>
            <li>
            正規表現は「連接」「選択」「繰返し」の演算が備えられている<br>
            R,S という 2 つの正規表現が存在すると仮定する。<br>
            <b>連接 「RS」</b>: R の直後に S が続くパターン<br>
            <ul>(e.g.) RS, RRS, RSS, RRSS, ...<br></ul>
            <object data="images/vector/rensetsu.svg" type="image/svg+xml"></object><br>
            <b>選択 「R|S」</b>: R もしくは S が出現するパターン<br>
            <ul>(e.g.) R, S, RS, ...<br></ul>
            <object data="images/vector/sentaku.svg" type="image/svg+xml"></object><br>
            <b>繰返し 「R*S」</b>: 「*」の直前(R)が 0 回以上出現するパターン<br>
            <ul>(e.g.) S, RS, RRS, RRRS, ...</ul><br>
            <object data="images/vector/star.svg" type="image/svg+xml"></object><br>
            </li>
            <li>
            基本三演算は結合順位が存在する<br>
            <ul>繰返し &gt; 連接 &gt; 選択</ul>
            </li>
        </ul>
  </div>

  <div id="cover">
    <h1>正規表現の他の演算</h1>
        <ul>
            <li>
            <b>「R+S」</b>: 「+」の直前のパターンが 1 回以上出現するパターン<br>
            <ul>(e.g.) RS, RRS, RRRS, ...</ul>
            <ul>R+S ≡ R(R*)S</ul>
            </li>
            <li>
            <li>
            <b>「R?S」</b>: 「?」の直前のパターンが 0 or 1 回出現するパターン<br>
            <ul>(e.g.) S, RS</ul>
            </li>
            <li>
            <b>「R{1,3}」</b>: 「{}」の直前のパターンが 1 〜 3 回出現するパターン<br>
            <ul>(e.g.) R, RR, RRR</ul>
            </li>
            <li>
            <b>「R{1,}」</b>: 「{}」の直前のパターンが 1 回以上出現するパターン<br>
            <ul>(e.g.) R, RR, RRR, ...</ul>
            <ul>R+S ≡ R(R*)S ≡ R{1,}S</ul>
            </li>
        </ul>
  </div>

  <div id="cover">
    <h1>実装について</h1>
    まずは基本三演算を実装していく。
    <ul>
        <li>
        R*(T|S)U をオートマトンで表現してみる
        </li>
        <object data="images/vector/rtsu-automaton.svg" type="image/svg+xml"></object>
        <li>
        状態と入力に対する遷移先、遷移したかどうかフラグで管理する。
        </li>
    <pre>
    <code>
typedef struct Automaton {
    int state;
    unsigned char input_char;
    int next_state;
    bool next_state;
};
    </code>
</pre>
        <object data="images/vector/rtsu-automatondata.svg" type="image/svg+xml"></object>
    </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>
    </ul>
</pre>
    <img src="./images/sqrWave.png" width="50%" height="">
  </div>

-->

</div> <!-- presentation -->
</body>
</html>