| MARCOS DANIEL VILLAGRA | Ｍ２ | 中島 康彦 | 関 浩之 | 嶋田 創 | 中田 尚 | |
|
発表題目：Hitting Times of Quantum Walks on Lines and Grids
発表概要：There is an increasing interest in the design of quantum algorithms using the quantum walk paradigm. Generally, making quantum algorithms is a difficult task, and using this framework seems to be a very promising approach. Quantum walks were defined in analogy to classical random walks and Markov chains, and it is expected to have the same success for the design and analysis of quantum algorithms. Classically, for random walks and Markov chain based search algorithms, the main complexity metric is the hitting time. It is commonly defined as the average number of steps to find a set of marked vertices on a graph, and it is directly related to the running time of randomized algorithms. In the same sense, we can define a similar notion of average hitting time for quantum walks, but this turned out to be delicate. Care has to be taken in order to define a proper notion of hitting time. In this work we study one such notion termed One-Shot Hitting Time and concentrate only in discrete-time walks. This research is divided in two parts: i) lines and, ii) 2-dimensional grids. For the first part, we propose a walk using a coin operator with phase parameters in charge of tuning the standard deviation of the induced probability distribution on the line. Closed-form formulas for time evolution of the walk were deducted using a saddle point method for asymptotic approximation, and to this end as in previous work, Fourier analysis was applied to simplify the study. We also describe the asymptotics by showing the weak convergence of the walk for large time. These results give a precise description of one-shot hitting times for lines. For the second part, the analysis mentioned above cannot be used due to the high complexity of the resulting formulas. Therefore we concentrate on bounding the hitting time and the probability of hitting an arbitrary node on the grid. On a 2-dimensional grid of size n it is proved, using the models of Coined and Markov chain quantum walks, an O(√n) hitting time with bounded error success probability for the former and unbounded error success probability for the latter. These results have potential algorithmic applications in spatial search and quantum network routing. | ||||||
| 溝口 宜良 | Ｍ２ | 関 浩之 | 松本 裕治 | 楫 勇一 | ||
|
発表題目：確率プロファイルを用いた形式文法SMCFGに基づくncRNA２次構造予測
発表概要： 生物配列のひとつであるncRNAの機能はその２次構造と相関を持つと言われている。しかし、多くのncRNAはその１次構造が知られているものの、２次構造は未知である。そこで既知の１次構造から２次構造を予測する２次構造予測が重要となる。そのアプローチのひとつとして形式文法の構文解析技術を用いた予測法が提案されている。確率多重文脈自由文法SMCFGは、文法の規則に確率を付与するとともにシュードノット構造も予測できるよう、文脈自由文法CFGを拡張したものである。 本研究では、SMCFGに基づく構造予測において、マルチプルアラインメントを施した予測対象であるncRNAファミリーのみから規則の確率値、つまり、確率プロファイルを算出する方法を提案する。発表者の従来研究では予測対象が最大2本であったのに対し、任意の本数の予測が可能である。また、確率値算出においても２次構造が既知のファミリーを必要としない利点もある。本発表では、実装した提案手法が、既知の２次構造を必要とする従来研究と同程度の予測精度を持つことを実データによる実験結果で示し、その有効性を述べる。 | ||||||
| 尾崎 龍 | Ｍ２ | 藤原 秀雄 | 関 浩之 | 井上 美智子 | ||
|
発表題目：マルチコアプロセッサ環境におけるアルゴリズムの高速化の研究
発表概要：近年一般のPC向けにも普及しているマルチコアプロセッサでは、従来の並列計算とは違い、キャッシュミスがボトルネックとなる。現在行われている研究の多くは、ソートや行列計算等、１種類の巨大データを扱うものである。そこで、本研究では複数種類の巨大データを扱う場合として、特に故障シミュレータの並列アルゴリズムを対象としてキャッシュ効率を踏まえたアルゴリズムを実装しつつ評価する。 | ||||||
| 松原 裕貴 | Ｄ２ | 加藤 博一 | 中島 康彦 | 宮崎 純 | ||
|
発表題目：CPUキャッシュを有効利用した並列時系列パターンマイニングアルゴリズム Cache-conscious parallel PAID の提案
発表概要：時系列パターンマイニングはデータベース全体に対し非常に多くのアクセスを繰り返す傾向がある。そのため、CPUキャッシュでのアクセスレイテンシが発生しやすいと考えられる。 本研究では並列化及びCPUキャッシュの有効利用による処理速度の向上を目的とし、データ構造やアクセス手法等の改良方法の提案を行う。 | ||||||