2010年度 情報科学演習Ⅲ 今井研課題説明会 ２０10年４月9日 TexPoint fonts used in EMF. Read the TexPoint manual before you delete this box.: A

今井研究室の研究テーマ アルゴリズム 今井研究室の研究テーマは情報科学の基礎である「アルゴリズム」そのものです。一口にアルゴリズムと言っても、さまざまな側面からの研究があります。

今井研究室の研究テーマ アルゴリズム 基礎理論 計算量 計算量 計算量 最適化 アルゴリズムの速さの解析や、アルゴリズムを適用する問題そのものの解析を行う、計算量、最適化といった側面からの研究や

今井研究室の研究テーマ 現実社会へ の応用 アルゴリズム 基礎理論 計算量 計算量 暗号実装 計算量 計算量 計算量 計算量 生体認証 ゲーム理論 計算量 計算量 計算量 計算量 生体認証 交通量解析 　　　現実社会へ 　　　　　の応用 計算量 最適化 アルゴリズム 基礎理論 結果や考え方を現実社会での問題に応用するという側面からの研究、

今井研究室の研究テーマ 現実社会へ の応用 アルゴリズム 基礎理論 新しい計算の 枠組み 計算量 計算量 暗号実装 計算量 計算量 計算量 ゲーム理論 計算量 計算量 計算量 計算量 生体認証 交通量解析 　　　現実社会へ 　　　　　の応用 計算量 最適化 アルゴリズム 基礎理論 新しい計算の 　　　枠組み 計算量 量子 またこれらの問題を、これまでの計算の枠組みとは異なる量子計算の枠組みで考えるという研究

今井研究室の研究テーマ 現実社会へ の応用 アルゴリズム 基礎理論 新しい計算の 枠組み 数理構造そのもの 計算量 計算量 暗号実装 計算量 ゲーム理論 計算量 計算量 計算量 計算量 生体認証 交通量解析 　　　現実社会へ 　　　　　の応用 計算量 最適化 アルゴリズム 基礎理論 新しい計算の 　　　枠組み 計算量 量子 そしてこれらの研究を支える数理的構造の研究など、今井研究室では基礎から応用、古典から量子まで、幅広い分野に挑戦しています。 計算量 計算量 組合せ論 グラフ理論 計算量 計算量 数理構造そのもの 計算代数 計算幾何

博士論文(1/2) 計算幾何 アレンジメント再構成の組合せ論的複雑度評価（青木 保一，1993） リーマン計算幾何：凸包，ボロノイ図とデローネ型三角形分割 （大西 建輔，1998） 特徴多様体上のクラスタリング問題について（稲葉 真理，1999） 整数計画法による三角形分割の最適化（田島 玲，2000） 三角形分割の組合せ論（竹内 史比古，2001） 多面体的複体のシェリング向き付け： シェラビリティー判定と離散最適化の組合せ構造 （森山園子，2006） 有向マトロイドの実現を与える方法および特徴のある有向マトロイド （中山　裕貴，2007） 計算代数 単模およびLawrence型整数計画問題に対する計算代数的解析 （石関 隆幸，2003） 量子計算 計算量的観点における量子計算モデルの計算能力（小林 弘忠，2002） 資源制約下における量子計算モデルの計算能力（ルガル フランソワ，2006） エンタングルメントコストの解析とホレボ容量の計算（下野 寿之，2006） Bell不等式とカット多面体：量子情報科学と組合せ最適化の結合 （伊藤　剛，2007） － 現実世界の設定下で定量的な安全性を初めて保証したデコイ法量子鍵配送 の理論と実験（長谷川 淳，2008） － 量子状態上のボロノイ図とその量子通信路容量の数値的評価への応用 （加藤 公一，2008） 今井研がどのような研究をしてきたところか知ってもらう 7

博士論文(2/2) ゲームツリー探索 AND/OR木探索アルゴリズムDf-pnの提案とその応用（長井 歩，2002） (美添一樹, 2009) パズル・計算量 　　 －別解問題の計算量解析の統一的手法 (八登崇之, 2009) －論理式サイズ下界に対する強化線形計画限界（上野賢哉, 2010） ゲノム・文字列処理 文書検索と圧縮の統合-接尾辞ソート、ブロックソート法、接尾辞配列- （定兼 邦彦，2000） 部分文字列の性質に基づく計算機援用大規模生物実験設計 （土井 晃一郎，2001） 生物配列情報の比較と検索のための高速なアルゴリズムの研究 （渋谷 哲朗，2002） グラフ理論 Tutte多項式の計算アルゴリズムとその応用（関根 京子，1997） リンクベースのWeb上情報発見手法の新しいフレームワーク （浅野 泰仁，2003） ネットワーク ネットワーク通信において通信品質を保証するアルゴリズム （古賀 久志，2002） 8

修士論文 (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に対応します １週目：テーマ設定 ２週目：中間発表 ３週目：中間発表 ４週目：最終発表 演習の日程ですが 毎週水曜日１時から２１４教室に行います。 都合が悪い場合もflexibleに対応します。 １週目はテーマを設定してもらい、 ２３４週目では研究室のメンバーの前で発表をしてもらいます。 ４週目が最終発表となります。 前もってセミナー担当の自分にメールしてもらえばいきなり１週目からの発表ができます 学期末：真の最終発表（任意） 事前にセミナー担当の橋倉(hashikura@is.s.u-tokyo.ac.jp)に連絡があれば１週目から発表が出来ます

演習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の理解は不可欠

離散数学の授業から(その２) 線形計画問題 単体法… 多面体の辺上を動く 最適解探索 2 2 1 O 1 強多項式時間アルゴリズムの存在は未解決！

演習3の進め方 まず、文献を購読。 2. 最終週までにその発展を考察 テーマ例：多面体のf-vectorの解析 線形計画の多面体的解析 　　 　　　　　　 線形計画の多面体的解析 多面体的組合せ論　　　　 など 2. 最終週までにその発展を考察 　　- 計算機実験 　　　多面体のデータベース [‘10 Miyata, Moriyama, Fukuda] なども利用可能 　　- 論文の結果の拡張　　　　など その他、各自相談に応じてさまざまなテーマに対応します

スッパキットパイサーン ウォラポン(D1), 枝廣正人（客員教授/NEC） Scalable アルゴリズム スッパキットパイサーン　ウォラポン(D1), 枝廣正人（客員教授/NEC）

Multi-Coreがあれば。。。 ⇒ 皆の携帯もMulti-Core(かも） （枝廣 2009年に地球環境大賞、経済産業大臣賞受賞） N ステップの計算 Processor 1 Processor 2 Processor 3 Processor 4 Processor 5 … Processor P P 個の完全に同じプロセッサー N　/　Pステップで完成して幸せです ⇒　皆の携帯もMulti-Core(かも）　 　（枝廣　2009年に地球環境大賞、経済産業大臣賞受賞）

Merge Sort N 個の整数 Sort N/P 個 N/P 個 Sort Sort … N/P 個 Sort O(N/P logN/P) 幸せです! 難しい! 頑張っても O(N logP) N 個のソート済み整数

今井研でやる研究テーマ Sortingアルゴリズム 学習アルゴリズム 検索アルゴリズム グラフアルゴリズム Ex. Map Sort1, AA-Sort2 [1Edahiro, ASP-DAC 2009] [2Inoue, Moriyama, Komatsu, Nakatani, PACT 2007] 学習アルゴリズム Ex. GLVQ [Houlai, Sakai, Edahiro, IEICE Trans. 2009] 検索アルゴリズム Ex. And/Or木の検索 [1Takano, Maekawa, Kasahara, PDCN 2009] グラフアルゴリズム Ex.最短路問題 [Madduri, Bader, Berry, Crobak, ALENEX 2007]

情報学科演習３ 量子計算、量子情報 フランソワ　ルガル（特任講師）

量子コンピューティングの紹介 量子力学の法則に基づく新しい計算パラダイム 様々な応用 量子並列性を用いた高速アルゴリズムの実現 情報理論的に安全な量子暗号の構築など

例：素因数分解 15 = 3 x 5 147573952589676412927 = ？ 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活用 べき乗グラフ ・インターネット, 引用 ・次数分布活用