情報科学演習Ⅲ 今井研究室 研究室紹介 2004年４月９日 今井研究室について 研究テーマ 情報科学の基本的な理論となる アルゴリズム論 アルゴリズムの設計による問題の解析 離散数学等の手法 計算量の解析 理論から応用、実用へ →アルゴリズムが適用できる場面を 自分で見つけていく。 現在の研究 量子計算/量子情報理論 交通流解析（ITS:高度交通システムの検討） 多項式の因数分解 ネットワーク 多面体/マトロイド 計算代数 速度分布図による交差点・バス停留所の識別 計算幾何/計算位相 ERATO（今井量子計算機構プロジェクト）との連携 量子計算量、量子通信、量子暗号 TCP/IPの振る舞いの解析 組合せゲーム理論 計算量解析/パズル問題の自動作成 研究テーマ間の関連 量子計算 量子情報理論 文字列処理 マッチング 車両の 同定 車両軌跡 の比較 交通流解析 古典理論 群論 多面体 の解析 計算幾何 計算代数 組合せ論 ゲーム理論 グラフ理論 ネットワーク 演習Ⅲ研究テーマ 交通流解析 計算代数とその応用 グレブナー基底 量子計算/量子情報 COMPUTATIONAL GROUP THEORY --- Towards Quantum Computing 量子情報における加法性問題 有向マトロイド計画 交通の円滑化に役立つアルゴリズムの発案 超平面にトポロジカルな変形を施した擬超平面を用いた，線形計画の一般化 対称性のある凸多面体に関する計算 --- 量子情報への展開 その他、取り組みたい題目を挙げていただければ応援･協力します。 演習Ⅲ：研究と発表 毎週水曜日13：00から102号室にて行います。 （他の授業等がある場合には別の日程を設定します） １週目 テーマ設定 （各期開始頃にメールで連絡します。） ２週目以降 研究の進行状況を発表 質問等は演習Ⅲ担当者の柴田（[email protected]）に メールで連絡をお願いします。 研究室（311・314）へお越しいただいても構いません。 研究室ホームページ：http://www-imai.is.s.u-tokyo.ac.jp/index-j.html ERATOホームページ：http://www.qci.jst.go.jp/ 情報科学演習Ⅲ ---交通流解析--中山 裕貴（博士１年） 山田 崇（修士２年） 柴田 輝之（修士１年） ITS（Intelligent Transport System) 最先端の情報通信技術を用いた新しい交 通システム ナビゲーションシステムの高度化 自動料金収受システム （ETC） 交通管理の最適化→旅行時間の推定 道路管理の効率化→道路状況の把握 緊急車両の運行支援 など９つの開発分野（国土交通省） 住友電工と共同研究を行っています 研究の目標 GPSやカーナビゲーションシステムによっ て得られた車両の軌跡データを基に、輸送 効率や安全性等を改善するアルゴリズム の検討を行う。 新しいシステムを 発案していく 車両の軌跡データは、毎秒における車両の 緯度・経度（及び地図上の点）、速度、進行方位等で構成されている。 具体的なテーマ 渋滞の始点や終点を判定する。または、渋 滞中であるかどうかの基準を作成する。 （軌跡データに対応するビデオによって、正解を確認する ことができます。） 同一経路を走行している多数の軌跡デー タを比較する。 交差点や停留所、料金所といった地点に おける軌跡データの特徴を読み取る。 ＧＰＳによる車両軌跡データ 毎秒の軌跡が地図上に プロットされる 速度と方位 （0と65536が北、 32768が南）から 左折しているとわかる 渋滞中の速度変化 ５分間の平均だったら？ 直前１ｋｍの平均だったら？ 基準値（閾値）は？ 最高速度が低い 走行時間が短い 停止位置分布の比較 例：同一経路を走るバスの軌跡データ（90回分）について、速度０のものに注目 信号（交差点）と停留所では分布の特徴に違いがあるだろうか？ 情報科学演習III --- 計算代数とその応用 --中山 裕貴（博士１年） ベック 和穂エリック（修士２年） 計算代数とは 多項式の因数分解 連立方程式の求解 多項式のGCDの計算 等を、高速・正確に計算する手法を考える 応用 ･･･ 符号理論、整数計画問題、 イデアルの準素分解 etc… 多項式の因数分解 （特に多変数の場合）難しい 従来のアルゴリズム Berlekampの方法（有限体上での分解） Lattice Reductionによる方法 上２つを組み合わせた、Hoeijによる 新しいアルゴリズムの提案 （これについての論文を講読してもらう予定） グレブナー基底 多項式イデアルの良い生成元 連立方程式の解を逐次的に計算 f ( x, y , z ) 0 応用分野： f ( x, y , z ) 0 1 2 g1 ( x, y, z ) 0 g 2 ( y, z ) 0 g3 ( z) 0 f 3 ( x, y , z ) 0 イデアルの準素分解 Ideal membership問題 （多項式 g を、多項式 f1 ,, f n を用いて g h1 f1 hn f n と表せるか？） グレブナー基底が有用 演習３の内容（例） 計算代数に関するテキスト・論文の購読 因数分解アルゴリズム[Hoeij 2000] Comprehensive グレブナー基底 [Suzuki et al. 2003] アルゴリズムの実装・評価 （余裕があれば） 予備知識はあまり必要としません 他に何かやりたいことがあれば、 それをやるのも歓迎します 情報科学演習III：量子計算 Francois Le Gall（博士２年） 長谷川淳（修士２年） 量子計算 一回の演算で複数の古典の結果が得られる f x y f ( x) f ( y ) 指数の 記号列の重ね合わせ 観測 得られる情報は一つだけ（ｆ（ｗ）） そこで欲しい情報を得る工夫をする 観測 f ( x) f ( y ) 工夫 最終状態 量子計算の力 Shorの因数分解アルゴリズム 多項式時間で整数の因数分解が可能 RSA暗号を破れる可能性あり 量子計算が注目されている 今井研での量子計算 研究分野 量子アルゴリズム 構築 シミュレーション 量子暗号 量子情報 演習IIIの課題 論文を読んで、知見を深める 演習３の研究課題の例：量子計算と群論 隠れ部分群問題（HSP) 入力：群G、Gの部分群Hへのオラクルアクセス 問題：Hを多項式時間で求める • Shorの素因数分解アルゴリズムはHSPのSpecial case (G Z n ) • 正２面体群上のHSPが解けるなら格子問題を解くことができる。 • 正２面体群上のHSPの場合、テクニックや結果が多いが効率の いいアルゴリズムが知られていない。 課題：計算群論 ー量子アルゴリズムに向けて一 正２面体群 Dn について 定義：正ｎ角形を自分自身に移す運動全体のつくる群 位数：２ｎ （ ｎ 回転 ＋ ｎ 対称変換 ） 例： n=4 s1 s2 r s3 r 3 / 2 s4 r r / 2 r / 2 (r / 2 ) 2 r / 2 Id ４対称変換 r3 / 2 r / 2 r / 2 r / 2 (r / 2 )3 Id (r / 2 )0 ４回転（Idを含む） s1 (r / 2 )i 0 i 3 (r / 2 )i 0 i 3 (1, i ) 0 i 3 (0, i ) 0 i 3 D4 Z 2 Z 4 (a, b) a Z 2 , b Z 4 一般的に、 Dn Z 2 Z n (a, b) a Z 2 , b Z n その群上の和は？ 半直和 (a, i) (a, j ) (a a mod 2, i j mod n) (a, i) (a, j ) (a a mod 2, i j mod n) if a 1 if a 0 ( Z 2 Z n , ) ( Dn , ) 演習３課題の例: • ( Z3 Z n , ) ， ( Z 4 Z n , ) , ．．．の構造？ • ( Z 2 Z n , ) のように、幾何的な意味がある？ 計算群論のソフト （GAP, …)の使用 • （課題の理由：大事な問題がそんな群上のHSPに帰着する可能性あり 量子コンピュータで解ける可能性あり） 有向マトロイド計画 森山 園子 2004年度 情報科学演習Ⅲ April 9, 2004 線形計画 (Linear Programming) x3 1 線形計画の許容領域 ＝半空間の共通部分として 与えられる凸多面体 O min x1 + 2x2 + 3x3 s.t. x1 + 2x3 ≦3 x2 + 2x3 ≦2 x1, x2, x3 ≧0 2 x2 (1,0,1) 3 目的関数を減少させる方向で 凸多面体の頂点を辿り x1 目的関数を最小化する頂点を探索 (3,2,0) 超平面 擬超平面 超平面 hyperplane 擬超平面 pseudohyperplane 目的関数の振る舞い 線形計画 常に Acyclic 有向マトロイド計画 Cyclic になる場合有り 課題内容 • 有向マトロイド計画の基礎を学ぶ • 関連論文を読む • 既存プログラムを拡張する – OMLIB [Finschi & Fukuda (2001)] – Oma-win [Bokowski (1999)] Encyclopedia of Mathematics and Its Applications 46 “Oriented matroids (Second Edition)” 情報科学演習III 対称な多面体の凸包計算と 量子情報処理への展開 伊藤剛志（今井研 博士1年） 対称性とアルゴリズム 対称性が高速化の役に立つ例 右のグラフで、ある頂点から 出発して全部の頂点を ちょうど1度ずつ通る道 （ハミルトン道）を求める どこから出発しても同じ なので、すべての出発点を 試すのは無駄 凸包問題 凸多面体の表現を変換する問題 連立不等式 頂点集合 凸包問題の困難さ 次元 頂点数 次元 時間 が高くなると指数的に時間がかかる 入力が対称な場合で重要なケースがよくある • カット多面体 • 線形順序多面体 対称性を利用して高速化できないか? 量子情報処理への展開 • 量子計算: 量子状態特有の性質を使った計 算 • エンタングルメント • 超並列性 • Bell 不等式 – 量子状態がエンタングルメントを持つかどうかを 検査するための式 – ある対称性の高い高次元の凸多面体の不等式 表現を求めると見つかる 他の研究分野との関連 計算幾何 凸包問題 量子情報処理 Bell 不等式 計算群論 対称性を取り扱う道具 演習IIIの内容 • 関連文献の講読 – 対称性を見つけるアルゴリズム （グラフ自己同型問題など） – 対称性を利用した探索 – 凸包問題のアルゴリズム – 群論 など
© Copyright 2024 ExpyDoc
