2010年度 情報科学演習Ⅲ 今井研課題説明会 ２０10年４月9日 今井研究室の研究テーマ アルゴリズム 今井研究室の研究テーマ 計算量 計算量 最適化 基礎理論 アルゴリズム 今井研究室の研究テーマ 計算量 暗号実装 ゲーム理論 計算量 計算量 生体認証 交通量解析 計算量 計算量 計算量 最適化 基礎理論 アルゴリズム 現実社会へ の応用 今井研究室の研究テーマ 計算量 暗号実装 ゲーム理論 計算量 計算量 生体認証 交通量解析 計算量 計算量 計算量 最適化 アルゴリズム 基礎理論 量子 計算量 現実社会へ の応用 新しい計算の 枠組み 今井研究室の研究テーマ 計算量 暗号実装 ゲーム理論 計算量 計算量 生体認証 交通量解析 計算量 計算量 計算量 最適化 アルゴリズム 基礎理論 量子 計算量 計算量 組合せ論 グラフ理論 計算量 計算量 計算代数 計算幾何 計算量 現実社会へ の応用 新しい計算の 枠組み 数理構造そのもの 博士論文(1/2) • • • 計算幾何 – アレンジメント再構成の組合せ論的複雑度評価（青木 保一，1993） – リーマン計算幾何：凸包，ボロノイ図とデローネ型三角形分割 （大西 建輔，1998） – 特徴多様体上のクラスタリング問題について（稲葉 真理，1999） – 整数計画法による三角形分割の最適化（田島 玲，2000） – 三角形分割の組合せ論（竹内 史比古，2001） – 多面体的複体のシェリング向き付け： シェラビリティー判定と離散最適化の組合せ構造 （森山園子，2006） – 有向マトロイドの実現を与える方法および特徴のある有向マトロイド （中山 裕貴，2007） 計算代数 – 単模およびLawrence型整数計画問題に対する計算代数的解析 （石関 隆幸，2003） 量子計算 – 計算量的観点における量子計算モデルの計算能力（小林 弘忠，2002） – 資源制約下における量子計算モデルの計算能力（ルガル フランソワ，2006） – エンタングルメントコストの解析とホレボ容量の計算（下野 寿之，2006） – Bell不等式とカット多面体：量子情報科学と組合せ最適化の結合 （伊藤 剛，2007） － 現実世界の設定下で定量的な安全性を初めて保証したデコイ法量子鍵配送 の理論と実験（長谷川 淳，2008） － 量子状態上のボロノイ図とその量子通信路容量の数値的評価への応用 （加藤 公一，2008） 博士論文(2/2) • • • • • ゲームツリー探索 – AND/OR木探索アルゴリズムDf-pnの提案とその応用（長井 歩，2002） – 分岐因子が一様な探索空間のためのAND-OR木探索アルゴリズム (美添一樹, 2009) パズル・計算量 －別解問題の計算量解析の統一的手法 (八登崇之, 2009) －論理式サイズ下界に対する強化線形計画限界（上野賢哉, 2010） ゲノム・文字列処理 – 文書検索と圧縮の統合-接尾辞ソート、ブロックソート法、接尾辞配列（定兼 邦彦，2000） – 部分文字列の性質に基づく計算機援用大規模生物実験設計 （土井 晃一郎，2001） – 生物配列情報の比較と検索のための高速なアルゴリズムの研究 （渋谷 哲朗，2002） グラフ理論 – Tutte多項式の計算アルゴリズムとその応用（関根 京子，1997） – リンクベースのWeb上情報発見手法の新しいフレームワーク （浅野 泰仁，2003） ネットワーク – ネットワーク通信において通信品質を保証するアルゴリズム （古賀 久志，2002） 修士論文 (1/2) • • 離散数学・計算幾何 – 最小包含球問題から得られるCube グラフの向きづけ（西鳥羽 二郎，2007） – Angular Voronoi Diagram の退化（牟田 秀俊，2008） – マトロイドの向き付けの計算解析及び離散幾何における接続関係の問題への応用 （松本宜丈, 2009） – 半正定値計画法による有向マトロイドの構造解析 （宮田 洋行，2009） – Periodic graph の幾何構造の解析およびその高速アルゴリズムへの応用（夫 紀恵, 2010） – 実データに基づくhuman network とcitation graph の解析（奥田 諒介, 2010） 計算量理論 – Ｌ対Ｐ問題の折り返し対アクセス問題への関連付けとそれらの組み合わせ構造（上 野 賢哉，2007） 修士論文 (2/2) • • 暗号理論 – Final Round 攻撃対策のなされたAES に対するキャッシュタイミング攻撃 （永岡 悟，2008） – 量子攻撃耐性と平均的困難性を備えた生体暗号システム （小島 晃司, 2009) 量子計算 – 可解群に対する多項式時間量子アルゴリズム（乾 義文，2007） – 二分NAND式木上の量子ウォークアルゴリズムの解析（鈴木 真吾, 2008） – 2-Prover 1-Round Game としてのベル不等式における最大量子破れ （高橋 敏明，2008） – ２部グラフ上での量子ウォーク探索アルゴリズムのデコヒーレンスの影響の解析 (徳田 優, 2009) 演習の内容 研究について 自分で考える ことを身につける • 研究のための基礎訓練 – 文献を探す、調べる – 分かりやすい発表 • テーマを自力で見つける能力 – 何を研究すればよいのか？ – なぜその研究が必要か？ • もちろん質問は歓迎 – メールor研究室（一度研究室に来て雰囲気を知る こともお勧めします） – 今井研セミナーの見学も歓迎 日程 • 毎週水曜日13：30から236にて – 都合が悪い場合はflexibleに対応します １週目：テーマ設定 ２週目：中間発表 ３週目：中間発表 ４週目：最終発表 学期末：真の最終発表（任意） 事前にセミナー担当の橋倉([email protected]) に連絡があれば１週目から発表が出来ます 演習III研究テーマ • 離散数学・計算幾何 • Scalable アルゴリズム • 量子計算、量子情報 この他希望があれば 対応します 質問はメールまたは研究室(311,314)まで 離散数学(グラフ理論)・ 計算幾何 夫(D1), 宮田(D2), 田沼(D2) グラフ理論 • グラフ = 様々な構造の抽象化 – Network – ウェブのリンク・被リンク、論文の引用・被引用 – 分子・結晶を作る原子の隣接構造 • グラフ上の問題を解決するアルゴリズム→様々な 応用 – 最短経路問題→Network Routing, Car Navigation – クラスタリング→ウェブ・論文誌のコミュニティ検出 • 多くの、高速なアルゴリズム, online等、新しいもの 高速アルゴリズムのための一手法: グラフの幾何的対象への変換 離散構造としてのグラフ グラフ上での最 近接点問題 基本的問題 応用多数 幾何的対象 L1距離空間での 最近接点問題 高速な幾何 アルゴリズム 目指すもの: 幾何アプローチによる高速アルゴリズム on Graphs 幾何的対象 離散構造としての グラフ 結晶格子グラフ 拡張 解決 グラフ理論的手法で の解析 l1ノルム等距 離埋め込み 新たな幾何アルゴリズム • Voronoi図 • 結晶格子下でも動くア •適用可能グラフ少 ルゴリズム • 高次元化, curse • 双曲幾何アルゴリズム of dimensions [Indyk, Matoušek 2004] 演習IIIの進め方 • 論文を読み、基礎的な手法を学ぶ – １～２週くらい – 幾何アルゴリズム・グラフ解析アルゴリズム初歩 – 何をやれば、一つ課題を解決できるかというのを 見つけるのを目的に • 把握したら、解決を試みる – やったことをわかりやすく発表するのも目標 離散数学(多面体) 宮田洋行(D2) 青島良一(M1) 多面体とは？ 有限個の半空間の共通部分で有界なもの 離散数学、計算幾何における最も基本的な対象の一つ -Voronoi図などを含むさまざまなデータ構造の基本要素、 線形計画、多面体的組合せ論、・・・ 多面体を理解することで、それらさまざまな対象に対し、 効率的なアルゴリズム設計、計算量評価が可能になる 離散数学の授業から(その１) 3-連結平面グラフGの頂点数、枝数、面数を それぞれv,e,f とおくと、 v-e+f = 2 (オイラーの公式) 2e≧3f, 2e≧3v 多面体では？ 3次元多面体Pの0,1,2次元の面(頂点、辺、面) の数をそれぞれf0,f1,f2 とおくと、 f0-f1+f2 = 2 2f1≧3f2, 2f1≧3f0 f=(f0,f1,f2) を f-vectorという どのようなf-vectorがありうるか？ (多面体の複雑性) 実は、 ・ (f0,f1,f2)が3次元多面体のf-vector ⇔ f0-f1+f2 = 2 2f1≧3f2, 2f1≧3f0 を満たす自然数 [1906, Steinitz] d次元では？ ・オイラーの公式f0-f1+f2+…+(-1)d-1fd-1 = 2 は相変わらず成立 ・不等式も少しだが知られている。 ・成り立つ不等式の列挙は未解決 - 多面体が関連する問題の計算量評価にf-vectorの理解は不可欠 離散数学の授業から(その２) 線形計画問題 Maximize: x1 2 x2 3 x3 単体法… 多面体の辺上を動く 最適解探索 x3 2 Subject t o : x1 , x2 , x3 0 x1 x2 x3 2 x x 1 1 2 x2 2 1 3 1 , ,0 2 2 O 1 強多項式時間アルゴリズムの存在は未解決！ x1 演習3の進め方 1. まず、文献を購読。 テーマ例：多面体のf-vectorの解析 線形計画の多面体的解析 多面体的組合せ論 など 2. 最終週までにその発展を考察 - 計算機実験 多面体のデータベース [‘10 Miyata, Moriyama, Fukuda] なども利用可能 - 論文の結果の拡張 など その他、各自相談に応じてさまざまなテーマに対応します Scalable アルゴリズム スッパキットパイサーン ウォラポン(D1), 枝廣正人（客員教授/NEC） Multi-Coreがあれば。。。 N ステップの計算 Processor 1 Processor 2 Processor 3 Processor 4 Processor 5 … Processor P P 個の完全に同じプロセッサー N / Pステップで完成して幸せです ⇒ 皆の携帯もMulti-Core(かも） （枝廣 2009年に地球環境大賞、経済産業大臣賞受賞） Merge Sort N 個の整数 N/P 個 N/P 個 … N/P 個 Sort Sort Sort Sort N 個のソート済み整数 O(N/P logN/P) 幸せです! 難しい! 頑張っても O(N logP) 今井研でやる研究テーマ Sortingアルゴリズム Ex. Map Sort1, AA-Sort2 学習アルゴリズム Ex. GLVQ [1Edahiro, ASP-DAC 2009] [2Inoue, Moriyama, Komatsu, Nakatani, PACT 2007] [Houlai, Sakai, Edahiro, IEICE Trans. 2009] 検索アルゴリズム グラフアルゴリズム Ex. And/Or木の検索 Ex.最短路問題 [1Takano, Maekawa, Kasahara, PDCN 2009] [Madduri, Bader, Berry, Crobak, ALENEX 2007] 情報学科演習３ 量子計算、量子情報 フランソワ ルガル（特任講師） 量子コンピューティングの紹介 • 量子力学の法則に基づく新しい計算パラダイム • 様々な応用 – 量子並列性を用いた高速アルゴリズムの実現 – 情報理論的に安全な量子暗号の構築など 例：素因数分解 15 = 3 x 5 147573952589676412927 = 193707721 x 761838257287 ？ • 従来のアルゴリズムでは、指数時間かかってしまう • 多項式時間で解ける量子アルゴリズムが存在する！ Peter Shorによって１９９４年に提案された 量子コンピュータが実現すれば、RSA暗号が解読できる！ RSA暗号 例：素因数分解 15 = 3 x 5 147573952589676412927 = 193707721 x 761838257287 • 従来のアルゴリズムでは、指数時間かかってしまう • 多項式時間で解ける量子アルゴリズムが存在する！ Peter Shorによって１９９４年に提案された 量子コンピュータが実現すれば、RSA暗号が解読できる！ • 対策：量子暗号 (不確定性原理により情報理論的に安全) ?？ ? ? 量子暗号 今井研での研究活動 量子アルゴリズム 量子計算 量子情報 素因数分解 代数的問題 探索問題 量子回路 量子ウォーク 量子情報幾何 量子通信 量子計算量理論 対話的証明 通信計算量 領域計算量 量子非局所性 ベル不等式 量子ゲーム 量子暗号 量子系のシミュレーション 量子テレポーテーション 演習３の課題（量子を選択した方へ） • 論文を購読し、発表してもらう • 発展の考察や独自の発想も大歓迎 卒論のテーマになるかも 予備知識が要らない 量子ならどのテーマでも対応します • テーマの例 – – – – 量子アルゴリズム（素因数分解、代数的問題など） 量子暗号の仕組み 量子ゲーム 量子通信路の情報伝達 最短路検索: 前処理で高速検索可能に カーナビ ・事前計算の活用 ・実時間交通情報対応 インターネット ナビゲーション ・社会ネットワーク 検索時間・サイズの トレードオフ 計算量解析 ・通信計算量より Christian Sommer, Elad Verbin, and Wei Yu: Distance Oracles for Sparse Graphs. FOCS 2009 - 50th Annual IEEE Symposium on Foundations of Computer Science, pp. 703-712. 道路ネットワーク べき乗グラフ ・平面的に近い―幾何 ・graph Voronoi活用 ・インターネット, 引用 ・次数分布活用
© Copyright 2024 ExpyDoc
