今井研究室　研究室紹介 ２００５年６月２４日

現在の研究 アルゴリズムの可能性と限界の究明 アルゴリズム構築の基礎 実社会へのアルゴリズムの応用 量子計算・情報 計算量理論 計算幾何・代数 離散システム 実社会へのアルゴリズムの応用 交通量解析 ゲームアルゴリズム

博士論文（１） 計算幾何 計算代数 量子計算量 組合せゲーム理論 アレンジメント再構成の組合せ論的複雑度評価（青木 保一） 特徴多様体上のクラスタリング問題について（稲葉 真理） リーマン計算幾何：凸包，ボロノイ図とデローネ型三角形分割 （大西 建輔） 整数計画法による三角形分割の最適化（田島 玲） 三角形分割の組合せ論（竹内 史比古） 計算代数 単模およびLawrence型整数計画問題に対する計算代数的解析 （石関 隆幸） 量子計算量 計算量的観点における量子計算モデルの計算能力（小林 弘忠） 組合せゲーム理論 AND/OR木探索アルゴリズムDf-pnの提案とその応用（長井 歩）

博士論文（２） ゲノム・文字列処理 グラフ理論 ネットワーク 部分文字列の性質に基づく計算機援用大規模生物実験設計 （土井 晃一郎） 文書検索と圧縮の統合-接尾辞ソート、ブロックソート法、接尾辞配列-（定兼 邦彦） 生物配列情報の比較と検索のための高速なアルゴリズムの研究 （渋谷 哲朗） グラフ理論 Tutte多項式の計算アルゴリズムとその応用（関根 京子） リンクベースのWeb上情報発見手法の新しいフレームワーク （浅野 泰仁） ネットワーク ネットワーク通信において通信品質を保証するアルゴリズム（古賀久志）

今井研究室の目標 独力で研究ができるようになる 多くの人と共著の論文が書けるようになる 分かりやすい発表が出来るようになる 人に頼らず自分の力で研究を推進 多くの人と共著の論文が書けるようになる 世界レベルでの共同研究 分かりやすい発表が出来るようになる 人に分かってもらうことが自分の理解につながる どんなに良い研究成果でも人に分かってもらわなければ意味がない

研究室の活動 週1回の研究発表 （メンバーが毎週２人ずつ順に発表） 輪読 外部の研究者との交流、連携 研究会、国際会議での発表 成果だけでなく展望、思考過程を発表 活発な討論 発表の練習 輪読 外部の研究者との交流、連携 研究会、国際会議での発表 論文誌への投稿

環境 研究室 個人用端末、机 計算サーバ プリンタ(カラー、モノクロ)、コピー機 発表用のノートPCとプロジェクタ 311号室、314号室（図書室の隣） 個人用端末、机 PCを購入予定 計算サーバ プリンタ(カラー、モノクロ)、コピー機 発表用のノートPCとプロジェクタ

卒論へ向けて 10月 卒論研究室配属 11月 卒論中間発表１回目 12月 卒論中間発表２回目 卒論要旨提出 1月 卒論執筆 10月　卒論研究室配属 テーマ決定 研究・調査開始 11月 卒論中間発表１回目 内容の具体化 12月　卒論中間発表２回目 　　　　卒論要旨提出 1月　　卒論執筆 　　　　卒論中間発表３回目 2月　卒論完成・提出 　　　卒論発表 さらなる研究 卒論修正・加筆 3月　最終提出 研究会、国際会議での発表 論文誌への投稿

卒論のテーマ 今まで…人から与えられた問題を解いてれば良かった これから…自分で解く課題を探す 卒論のテーマ 各自が興味を持った課題を探す 自分だけが面白いのではなく、他の人にも面白さが説明できることが必要

卒論の進め方 既存研究を調査する 研究の方向性を見極める 自分の研究の新規性と位置づけ 研究の流れを理解する（それまでの研究では実現できなかった課題を克服するものとして次の研究がある） 研究の方向性を見極める 今までの研究の流れで何が問題となっていて、次に何を研究すればいいのか 方向性を間違えてしまったら、どれだけ問題解決能力があっても良い結果は得られない 問題を解く 問題解決能力は今まで十分鍛えられているはず （課題、試験、レポートなど）

研究紹介（計算量理論） 上野　賢哉（修士１年）

計算量理論を研究する意義 計算量クラス間の関係を示すことにより アルゴリズム構築の限界が明らかになる 暗号の安全性の数学的裏づけができる … 計算量理論で評価されてきた研究は、 これらに関して何らかの可能性が示されている （ただ単に非自明な結果が示せればいいってもんじゃない）

計算量クラス 言語 関数 多項式時間 Ｐ ＦＰ 多項式領域 ＰＳＰＡＣＥ ＦＰＳＰＡＣＥ 主流 少数派 文字列の集合のクラス {0, 01, 100, 101, …} {1,11,111,1111,…} {0,10,111,0011,…} 関数のクラス f(x)=y g(x)=y h(x)=y P=PSPACE ⇔ FP=FPSPACE

新規性＝重要性？ 「ＦＰＳＰＡＣＥは今まで他の人が研究して こなかったからこの研究は価値があります」 ↓ 　　　　こなかったからこの研究は価値があります」 　　　　　　　　　　　　↓ 研究したって面白くないと思われて誰も手をつけてこなかっただけ？ 価値があるけど誰も気づかなかった？ 新規性は必要だけど、他の人が研究していない からこの研究は重要だという論法は通用しない

意義ある研究とは ×言語で知られている定理を関数でやってみて似たような結果を得る あたりまえ だったら関数なんかやらないで最初から言語の研究してれば十分 ○言語ではできなかったことが関数だったら可能になることを示す 言語じゃなくて関数を研究することの強みが示せる さらに、それが計算量クラス間の性質の解明などに役立つことを示すことが必要

関数計算量クラスに対する 帰納理論的演算子 ＰからＮＰなど他のクラ スを生成するものを 演算子と呼ぶ ＮＰ＝∃・Ｐ coNP=∀・Ｐ しかし、ＰからＰＳＰＡＣＥ を構築するような演算子 は知られていない 関数計算量の場合は、 これが簡単に作れる FPSPACE= Comp*(BRec(FP)) さらにこの結果から FPがBRecに閉じている⇔P=PSPACE 計算量クラス間の関係を 解明するための可能性

量子計算・量子情報 長谷川 淳(D1)

古典コンピュータの限界と 量子コンピュータの要望 ハードウェアの限界 量子力学に基づく状態，操作 素子の微細化，高速化を行えば いずれ量子効果が現れてくる 量子並列性による計算の高速化 アルゴリズムの限界 例：因数分解は多項式時間 NP完全問題は古典のルートぐらい速い 例：既存の因数分解は指数時間 暗号の安全性の限界 無条件安全な量子暗号 何らかの計算が多項式時間で解けないことが 安全性の根拠 どんな攻撃に対しても安全性が証明 （RSA暗号：因数分解の難しさ）

量子コンピュータ，量子通信の今 量子コンピュータ 量子通信，暗号（既存の光ファイバでの実験） 実用化はまだ先？ 実用化もそう遠くない 量子コンピュータ 2001年12月（IBM） 7 量子ビットの量子コンピュータを用いて15=3×5 の因数分解に成功 2002年9月（ERATO） 1024 量子ビットの半古典的量子フーリエ変換光ファイバ回路実現 量子通信，暗号（既存の光ファイバでの実験） 2003年7月（NEC/ERATO） 単一光子（量子状態）の100kmの伝送に成功 150km超に成功 2005年5月（世界最速の量子暗号鍵配送，NEC/ERATO） 16.3km の実用光ファイバを用いて，生成速度13kbpsでの量子鍵配送に成功

最近の今井研の量子研究 量子計算 領域に制限の付いた量子計算量 隠れ部分群問題を解く量子アルゴリズム 最短ベクトル発見アルゴリズム ノイズの下での量子計算の理論，数値解析 グラフの量子彩色数 量子情報 量子暗号の性能評価 量子誤り訂正符号の構築，性能評価 Bell不等式の列挙，破れの発見 量子情報幾何 量子通信路容量・量子エントロピー

量子誤り訂正符号 量子通信時の情報誤りを防ぐ技術 （量子暗号の安全性にも使われる） 量子CSS符号 [Calderbank ら, 1996] 2種類の古典符号から量子符号を構成 : ビット誤り訂正可能な古典線形符号 ビット 符号化 : ビット誤り訂正可能な古典線形符号 ビット を満たすなら : 量子ビット誤り訂正可能な量子符号 量子ビット

古典LDPC符号を用いた 量子誤り訂正符号の構成 古典LDPC符号 [Gallager, 1969] 検査行列が疎でランダム シャノン限界に漸近する，古典で最良の符号の一つ を古典LDPC符号にすると・・・ ランダムなLDPC符号　　　　　が　　　　　　を満たす確率は 量子CSS符号もシャノン限界に漸近 ランダムな , が の条件を満たす確率は にランダム性をある程度残しつつ，うまい構造を入れる シャノン限界に漸近する量子CSS符号を多項式時間で構成可能

最近の今井研の量子研究と他の分野の関連 量子計算 関連する他の分野 領域に制限の付いた量子計算量 隠れ部分群問題を解く量子アルゴリズム 計算幾何 最短ベクトル発見アルゴリズム ノイズの下での量子計算の理論，数値解析 グラフの量子彩色数 群論 量子情報 グラフ理論 量子暗号の性能評価 量子誤り訂正符号の構築，性能評価 符号理論 Bell不等式の列挙，破れの発見 情報幾何 量子情報幾何 量子通信路容量・量子エントロピー 情報理論

囲碁プログラムの研究 見合いの手の発見を目指して 2005/06/24 美添 一樹 yoshizoe@is.s.u-tokyo.ac.jp

今井研究室の関連研究 組み合わせゲーム理論 パズル/ゲームの計算量の解析 AND/OR木探索アルゴリズムDf-pnの提案とその応用(長井 歩 2002) パズル/ゲームの計算量の解析 “ぷよぷよの全消し判定問題はNP完全” (牟田 2005) “Finding Yozume of Generalized Tsume-Shogi is Exptime-complete” (八登, 瀬田, 伊藤 2005) “Complexity and Completeness of Finding Another Solution and Its Application to Puzzles” (八登, 瀬田 2003)

研究の背景 ゲームプレイングアルゴリズムの進歩 サーチアルゴリズムの進歩によりプログラムが強くなった ゲームツリーサーチ自体の研究 minimax, alphabeta, df-pn, generalized threats search, … 評価関数の研究 ゲームごとに特有の研究 統計的手法、強化学習などの一般的な方法

研究の背景 ゲームプレイングプログラムの歴史 チェッカー : CHINOOK (Jonathan Shaeffer) 1992, 1994にTinsleyと対戦 リバーシ : Logistello (Michael Buro) 1996に世界チャンピオン村上に勝利 チェス : Deep Blue 1997にKasparovに勝利 将棋 :激指、 YSS 、IS将棋、… アマ五段クラス 角落ちでプロ(勝又五段)に勝利

囲碁プログラムの難しさ 現状の囲碁プログラムの強さ このギャップは何から生じるのか? 囲碁では、盤面全体に対する良い評価関数が作れない 死活(詰碁)はすでにプロに近い能力がある 対局すると3級(?)程度 このギャップは何から生じるのか? チェスや将棋の成功は？ 囲碁では、盤面全体に対する良い評価関数が作れない 速く正確な評価関数は囲碁では不可能(と思う) 評価関数 サーチ ＋

現在の囲碁プログラムの手法 盤面全体に対する評価関数を使ってglobalなサーチをしているプログラムはごく少数 「目標別サーチ」を行うのが主流 多数の小目標(sub goal)を設けて、各sub goal向けに手を探索する

囲碁のルール 黒、白交互に交点に石を置いていく 最終的に「地」が大きいほうが勝ち 19x19の盤が普通 「地」とは一方の色の石だけで囲われた範囲のこと

囲碁のルール : 囲んだら取れる ▲のところに黒が打つと、白石を取れる 空点が無くなると取られる つながっている石は一蓮托生になっている 空点のことを、「呼吸点」「ダメ」などと言う つながっている石は一蓮托生になっている 取られるときはまとめて取られる つながっている石の集合を「連」という

囲碁のルール : 着手禁止点と例外 Aに打つと反則 そのまま取られる場所には打てない Bには打って良い 打った瞬間に黒石を取れるから

実戦例 「手談対局V」と私が打った例 これは終局図

目標別サーチ もちろん最終目的は相手より大きい地を確保すること しかしそれでは評価関数が作れない 死活、石取り、連絡/切断、勢力拡大…などの小目標 ”sub goal” に分割 各目標について達成時の評価点を定める 一番高い評価点を得た手を打つ

目標別サーチの弱点 複数の目標に依存関係がある場合 たとえば複数の目的を「見合い」にした手の発見が難しい 「見合い」の手の発見を目指す

見合いの手の例 連絡対連絡 AB間の切断とBC間の切断を同時に狙った手を発見する 現在、考案したアルゴリズムを実装中

見合いの手の例 死活対死活 おまけ 囲碁の分かる人向け 黒Aと打たれてどちらかが死ぬことが分からないプログラムが多い

「離散数学」とその応用 助手　森山園子 平成17年6月24日

マトロイド 行列 グラフ 最適化問題 ネットワーク理論 離散的 自然数の世界 連続的 実数の世界 整数行列 実数行列 無向 有向 整数計画 線形計画 ネットワーク理論 最大流問題 マッチング 最小費用流問題 離散的 自然数の世界 連続的 実数の世界

離散的 自然数の世界 連続的 実数の世界 計算代数 グレブナー 基底 マトロイド 行列 有向 計算幾何 グラフ 最適化問題 多面体 無向 有向 整数行列 実数行列 計算幾何 多面体 グラフ 最適化問題 無向 有向 有向マトロイド 計画 トポロジー 線形計画 線形相補性問題 整数計画 ネットワーク理論 最大流問題 マッチング 最小費用流問題 離散的 自然数の世界 連続的 実数の世界

符号理論・暗号理論 グラフィックス 量子計算 VLSI のレイアウト設計 交通流解析 地理情報処理における配置問題 遺伝子情報解析 隠線処理・3次元物体モデリング 計算代数 グレブナー 基底 マトロイド 量子計算 行列 無向 有向 整数行列 実数行列 計算幾何 多面体 グラフ 最適化問題 無向 有向 トポロジー 有向マトロイド 計画 線形計画 線形相補性問題 整数計画 ネットワーク理論 VLSI のレイアウト設計 最大流問題 マッチング 非常に基本的な構造であるが故に，様々な分野で独自の理論展開がなされてきた 実際，理論的意味でも新しい方向性を得られる しかし，分野の特殊性を生かした研究が発展する一方で，普遍的な理解にかける面もある そこで，統一的な理解を深める意味で，基礎研究の重要性がある 最小費用流問題 交通流解析 地理情報処理における配置問題 遺伝子情報解析 配送計画問題

分野間の「新しい架け橋」を見出す！ 計算代数 グレブナー 基底 マトロイド 行列 有向 計算幾何 グラフ 最適化問題 多面体 無向 有向 整数行列 実数行列 計算幾何 多面体 グラフ 最適化問題 無向 有向 有向マトロイド 計画 トポロジー 線形計画 線形相補性問題 整数計画 ネットワーク理論 [福田・森山・岡本 (2004)] [中山・福田・森山・岡本 (2005)] [中山・森山・福田 (2005)] （準備中） 最大流問題 マッチング 最小費用流問題 分野間の「新しい架け橋」を見出す！

線形計画問題 = 与えられた線形不等式制約のもとで, 線形目的関数 f(x) を最適化する問題 御存知の通り，線形計画とは次のように定義されます。 線形な等式および不等式制約の元で線形目的関数を最適化する解を見つける，という問題です。 幾何的に見れば，制約式と線形目的関数は超平面に対応し，制約式と線形目的関数からこのような超平面配置が得られます。 この制約式で与えられる超平面配置のセルの中で，制約式を満たすセルを「許容領域」と言います。 ここでは，許容領域が有界である場合，つまり凸多面体として得られる場合を考えています。 線形計画問題を解くためには，線形目的関数に対応する超平面をその法線ベクトルに沿って動かして，許容領域の中に最適解を見つけるわけですが，この（線形目的関数に対応する）超平面を動かす過程で，許容領域の枝構造に向き付けを与えることができます。 最適解 許容領域 P = { x | Ax <= b }

？ ＋ － 線形計画 有向マトロイド計画 多面体の基本的性質を応用 線形不等式制約 ＝超平面の半空間 「曲がった」 超平面の半空間 「曲がった」 超平面の半空間 許容領域＝多面体 「曲がった」多面体 線形目的関数　 f(x) 目的関数　 f ＋ － 組合せ構造を一般化 まず最初に，線形目的関数が有界セルのグラフに与える向き付けについて一般化します。 線形目的関数が与える向き付けは，各枝の向き付けをこのように与えることにより定義していました。 ここで得られる向き付けは，超平面配置に存在する直線（1-flat）上の全ての枝の向き付けは H_- から H_+ 方向になっています。 そこで，擬超平面配置において「目的関数が与える向き付け」を，「擬直線上の全ての枝の向き付けは H_- から H_+ 方向である」として定義します。 線形目的関数から得られる有界セルのグラフに対する向き付けは，(1) acyclic (2) USO (3) Holt-Klee 条件の３条件を満たしますが，この目的関数から得られる向き付けは少し異なります。 (2) USO を満たすことは解っていますが，(1) acyclic は満たされません。 (3) Holt-Klee 条件を満たすか否かは，解っていません。 線形計画 有向マトロイド計画 ？ 多面体の基本的性質を応用

擬超平面配置に対して 「双対構造」を提案 ＋ － 有向マトロイド計画 「擬超平面配置」 多面体の双対性 まず最初に，線形目的関数が有界セルのグラフに与える向き付けについて一般化します。 線形目的関数が与える向き付けは，各枝の向き付けをこのように与えることにより定義していました。 ここで得られる向き付けは，超平面配置に存在する直線（1-flat）上の全ての枝の向き付けは H_- から H_+ 方向になっています。 そこで，擬超平面配置において「目的関数が与える向き付け」を，「擬直線上の全ての枝の向き付けは H_- から H_+ 方向である」として定義します。 線形目的関数から得られる有界セルのグラフに対する向き付けは，(1) acyclic (2) USO (3) Holt-Klee 条件の３条件を満たしますが，この目的関数から得られる向き付けは少し異なります。 (2) USO を満たすことは解っていますが，(1) acyclic は満たされません。 (3) Holt-Klee 条件を満たすか否かは，解っていません。 有向マトロイド計画 「擬超平面配置」