研究室と卒業研究の紹介

研究室と卒業研究の紹介
ー 村尾研の場合 ー
コンピュータサイエンスコース
村尾裕一
村尾研究室
 ぬし＝村尾裕一
（むらおひろかず）
 場所＝西9-801．
研究室は 802と803
（敢えて言ってしまおう）
highest level に
居る一人
（西９は８階建て）
 授業：
 コンピュータ・リテラシー
http://w9-802.cs.uec.ac.jp/
 アルゴリズム論第一
 （院）アルゴリズム特論
村尾研究室
研究室公開
 日時
 １１月２２日（日）
 オープンキャンパス（１１〜１６時）の間の随時
 その後１７時位まで
 １１月２６日（木）１６：３０から１時間程
 適宜連絡をしてくれれば随時
 場所：西９－８０２
村尾研究室
卒研に関する概要
 ＵＲＬ
 http://w9-802.cs.uec.ac.jp/
→右側の「卒研配属希望者向け」
 http://w9-802.cs.uec.ac.jp/haizoku/
 題材：
 GPGPUや並列処理の非数値処理への応用
 WEB技術の応用
 数式：正確な計算，描画，検索，…
（数学をやるのでなく処理の題材）
村尾研究室
何を？
または
得意分野
数式
論理式を使って、
コンピュータ上で
事実を表現し証明
記号式の計算
を
（正確な計算）
操るのが WEB上にも
好き・得意
村尾研究室
具体的には
 数式処理や準数値（semi-numerical）処理
（整数計算．暗号とか）の基本アルゴリズム
や実装技術（数値計算は苦手です）
 証明支援システムの応用
 数式の扱いを主体とした、WEB技術の応用．
表示法，検索技法なども
 こういった大規模な処理系を実装するための
ソフトウェア技術
 これらの分野への並列処理、GPU等の活用
 タブレットＰＣとか小間物の活用法
村尾研究室
卒業研究のいろいろ（１）
 ２０１４年度
 置換パズル（ルービックキューブとか）の最
短解のＧＰＵを用いた探索
 数独の難易度
 イラスト中での明暗表現の傾向の定量的抽出
 ２０１３年度
 VR機器（Oculus Rift）を使って
 WebGLの応用・・・ブラウザからGPUを活用
 GPGPU：ウィルス探査、音声圧縮
村尾研究室
卒業研究のいろいろ（１）
 ２０１２年度
 GPGPU：ルービックキューブの最短手順解探索、




数独＝SAT（充足可能性問題）の解法
Android向けソフトウェア：野球のスコアブック、
着せ替え
Google Maps に坂道の情報を
多倍長整数GCDの高速アルゴリズムと実装技術
WEBブラウザでの対話形式による数式の省略表示
 ２０１１年度
 GPGPU：音声圧縮、暗号関連の基本演算（Montgomery
乗算等）
村尾研究室
卒業研究のいろいろ（２）
 ２０１０年度
 GPUを用いたウィルス探査
 ２００９年度
 GPGPU：ファイル圧縮。暗号計算（楕円曲線
暗号、RNS表現におけるMontgomery乗算）
 Googleストリートヴューのパノラマ表示と文
字情報の付加表示
 XML文書間の自動リンク付け
村尾研究室
卒業研究のいろいろ（３）
（まだまだあります）
 マルチコア並列処理：類似画像検索のマルチスレッド化。並
列整列アルゴリズム
 GPGPU：音声圧縮、多項式を要素とする行列の行列式、整数
行列乗算、陰関数の正確描画（PS3,GPU）
 Google Mapsの応用：複数ルートと情報表示、…
 Web技術：動的機構の導入と表示の軽量化。表データの自動
グラフ化（SVG）。Wikiの共通記述言語化。Mash-up(複数サー
ビスの結合)
 数式の検索（類似度による順位付け）
 証明支援システム：関数型言語のプログラムの生成。セキュ
リティプロトコル、GCの正当性等の証明。証明手順を解り易
くするための構造化表示
村尾研究室
卒業研究の紹介
ＧＰＧＰＵ
新たな応用分野の開拓（世界に先駆けて）
←→有効性が既知の応用分野（シミュレーション・高精
度を必要としない数値計算）
 準数値処理・暗号計算・・・多倍長整数計算
 ファイルの圧縮・・・同一パターンの探索〔音
声ファイル：線形予測の後〕
 ウィルス探査・・・シグニチャのパターン
 ルービックキューブの最短手順解（≦20手）の
探索：IDA*(Iter. Deepening A*) ＋表による枝刈り
のアルゴリズム
→ GTC2013@San Jose, ISSAC2015@Bath,England
村尾研究室
卒業研究の紹介
ＷＥＢ系の技術の応用




JavaScriptプログラミング
WebGL, WebCL --- 並列処理・GPUの利用
Ajax, jQuery, mash-up, JSON, SVG, WebGL, …
Google Maps API：地図情報やグラフ表示
XML(特に、数式を表すMathMLや OpenMath)
データの操作, XSL/ XSLT(変換)



数式の XML データの検索法
数式の エディタ BrEdiMa（→ MathUI’06@英国）
数式の省略表示と対話的な表示法の変更（提案）
村尾研究室
卒業研究の紹介
準数値処理：数や式の正確な計算
既存算法の並列化(GPU, マルチスレッド)が主
 基本算法の実現・チューニング
 多倍長整数のRNS表現（回路技術）
 高速化：整数の配列の演算として再構築
 RNS表現：符号判定/大小比較、暗号関連
(Montgomery乗算等)、…
 陰関数(多項式P(x,y)=０)の正確描画
 行列(整数要素)：先ずは乗算、逆行列
村尾研究室
卒業研究の紹介
数式を対象とした...
（前述のとおり）
 検索・データベース
元々は、証明支援システム向けの記述を進めるための
（証明済みの論理式を探す）道具の開発を目指して
 ＸＭＬデータとして
 XSLTによる変換
 データ内に動的な機構 → 表示を対話的に変更
 編集
村尾研究室
言っておきたいこと
 プログラミングは計算機屋でなくてもやる
（←→英語くらいは誰でも喋る）
 大学でやるのなら：処理の対象や方法論に専
門性を（←→日常英会話程度じゃぁ）
「理論＋実践」が大事
力任せでは解けなくても理論の力で容易に
なることも
 背景を知らないとデバッグができない
 但し、理論そのものが？ということも
