情報科学演習Ⅲ
今井研究室 課題説明会
２００５年４月８日
今井研究室の研究
アルゴリズムの可能性と限界の究明
アルゴリズムの構築
量子計算・情報
計算量理論
計算幾何
計算代数
現実世界のモデル化と解析
交通量解析
ネットワークの解析
組み合わせゲーム理論
関連する
研究会・国際会議・プロジェクト
研究会
情報処理学会アルゴリズム研究会
電子情報通信学会コンピュテーション研究会
国際会議
ＳＴＯＣ・ＦＯＣＳ・ＩＣＡＬＰ・ＳＴＡＣＳ・
ＩＳＡＡＣ・ＣＯＣＯＯＮ・…
プロジェクト
ＥＲＡＴＯ 今井量子計算機構
特定領域研究 新世代の計算限界
演習Ⅲでやってもらうこと
研究をするにあたって基本的な方法を身
につける
文献を探す、調べる（図書室、インターネット）
分かりやすく発表する
研究テーマを見つける能力を養う
既存研究のサーベイ
その分野で何が問題となっているか？
何を研究すればよいのか？
演習Ⅲの日程
毎週水曜日13：00から２１４にて行います
１週目 テーマ設定
他の授業等がある場合には別の日程を設定します
各期開始頃にメールで連絡します
テーマが決まっている人は、あらかじめ演習Ⅲ担当者
の上野(kenya@is.‥)まで教えて下さい
質問はメールまたは研究室（３１１・３１４）へ
２週目～４週目 研究の進行状況を発表
演習Ⅲ：研究テーマ
CPU実験の理論計算機科学的な側面
交通流解析
線形計画の一般化：有向マトロイド計画と線形相補性問題
対称性の発見と対称性を利用した計算の高速化
LDPC符号の実装と性能評価
ゲーム・パズルの難しさの解析
量子計算・情報プロジェクト
ＣＰＵ実験の理論計算機科学的な側面
計算量理論∨グラフ描画∨データ圧縮
上野 賢哉（修士１年）
ＣＰＵ実験
論理回路を組み合わせてＣＰＵを作成
コンパイラでプログラムを機械語に変換
回路サイズを小さくしてクロックアップ
実行時間を短くするために最適化
レイトレを自分たちのＣＰＵで動かす
理論計算機科学的な観点から見てみると…
論理回路とチューリングマシン
ＣＰＵ実験
⇒論理回路
計算量理論
⇒チューリングマシン
AND
AND
OR
計算量理論における論理回路
論理回路とチューリングマシンは一見異な
るようで、実は密接に結びついている
論理回路が、計算量理論において非常に
重要な役割を担う
並列計算量など
研究テーマ例
計算量理論における論理回路の研究
ＶＬＳＩフロア計画
２０
３０
１０
１０
１５
研究テーマ例
グラフ描画のアルゴリズムの研究、実装
ＣＰＵの生成において使われているアルゴリズムの調査、
改良（論理回路の最小化、配置問題、配線問題、長方形
詰込問題、…）
レイトレによる画像の生成
物体データ（小さい）
-70.0 35.0 -20.0
20.0 30.0
1 50.0 50.0
255.0
0 1 1 0 20.0 20.0 65.0 0.0 20.0
1.0 1.0 250.0 128.0 210.0 0.0
0 3 1 0 25.0 40.0 70.0 0.0 0.0
1.0 1.0 250.0 128.0 210.0 0.0
0310
0.0 30.0 30.0 0.0 -5.0
-1.0 1.0 250.0 128.0 211.0 0.0
0 1 1 0 20.0 10.0 30.0 0.0 -10.0
1.0 1.0 250.0 128.0 211.0 0.0
…
…
…
レイトレ画像（大きい）
45.0
40.0
0.0
80.0
同じ情報を表現している！
データ圧縮アルゴリズム
アルゴリズム的情報理論
文字列の持つ情報量をそ
れを生成する最小のプロ
グラムとして定式化
例
010101010101010101
⇒Print(’01’)×9
110101011010110111
⇒？？？
究極のデータ圧縮アルゴリズム
与えられた文字列に対してそ
れを生成する最小のプログラ
ムに変換
プログラムサイズを小さくする
コンパイラの最適化
現実的には難しい
⇒最小の文脈自由文法に変換
研究テーマ例
Grammar-based Compressionの最近
の論文の購読
ＢＷ変換、ＬＺＷ法、算術符号といった
データ圧縮アルゴリズムの研究、実装
情報科学演習Ⅲ
---交通流解析--中山 裕貴（博士２年）
柴田 輝之（修士２年）
ITS（Intelligent Transport
System)
最先端の情報通信技術を用いた新しい
交通システム
ナビゲーションシステムの高度化
自動料金収受システム （ETC）
安全運転の支援
交通管理の最適化→旅行時間の推定
道路管理の効率化→道路状況の把握
緊急車両の運行支援
など９つの開発分野（国土交通省）
ＩＴＳ関連の研究分野
公共交通の支援
公共車両優先システム
（PTPS）
バス到着時刻予測システム
車両ではなく、歩行者を
ナビゲーション
（携帯電話の利用）
location-based search
(位置情報サービス)
ある場所について近辺の
情報を得る
センター
車両
車両
車両
路側機
（インフラ）
インフラ整備
（路側機・路車間通信）と
車車間（利用者間）通信
研究の目標
GPSやカーナビゲーションシステムによって
得られた車両の軌跡データを基に、
輸送効率や安全性等を改善するといった、
ドライバー等にとって有益な分析結果を
得るためのアルゴリズムの検討を行う。
車両の軌跡データは、毎秒における車両の
緯度・経度（及び地図上の点）、速度、
進行方位等で構成されている。
新しいシステムを
発案していく
ＧＰＳによる車両軌跡データ
毎秒の軌跡が
地図上に
プロットされる
速度と方位
（0と65536が北、
32768が南）から
左折しているとわかる
16方位
基本的に毎秒
東西約3.09ｍ
南北約2.54ｍの格子点
有効桁は１の位まで
（小数部は常に０）
今までに行われてきた研究の例
同一バス路線を走行している多数の
軌跡データを比較する。
渋滞の始点や終点を判定する。または、
渋滞中であるかどうかの基準を作成する。
（軌跡データに対応するビデオによって、
正解を確認することができます。）
交差点や停留所、料金所といった地点に
おける軌跡データの特徴を読み取る。
ＧＰＳデータの補完を行う。
研究例
停止位置分布の比較と仮説（１）
停留所
左右（実際は前後）
対象の分布を予想
同一経路を走るバスの軌跡データについて、
速度０のものに注目する。
停留所と信号（交差点）では
その分布の特徴に違いがあるだろうか？
ポールは
この辺り？
研究例
停止位置分布の比較と仮説（２）
交差点
同一経路を走るバスの軌跡データについて、
速度０のものに注目する。
停留所と信号（交差点）では
その分布の特徴に違いがあるだろうか？
停止線の予想
車両の列ができる
待ち台数をポアソン
分布から予想
研究例
渋滞中の速度変化
５分間の平均だったら？
直前１ｋｍの平均だったら？
基準値（閾値）は？
最高速度が低い
走行時間が短い
線形計画の一般化：
有向マトロイド計画と線形相補性問題
森山 園子（助手）,中山 裕貴（博士２年）
{moriso,nak-den}@is.s.u-tokyo.ac.jp
線形計画問題の一般化
線形計画問題
２つの方向での一般化
線形相補性問題
w1…wn
z1…zn
I
-M
有向マトロイド計画
q
forall i, wizi=0
4
1 f
(+0+0 ++)
3
2
g
(0++0 ++)
線形相補性問題
(Linear Complementarity Problem)
線形計画問題を主・双対の両面から見る
線形相補性問題は線形計画問題を含む
有向マトロイド計画
(Oriented Matroid Program)
有向マトロイドとは、マトロイドに符号を付加したもの
半球上の各領域を、コベクトルで表す 符号の集合：
各制約について、対応する超平面より
具体的な値の情報は抜け落ちる
正（負）の側にあれば+(-)、超平面上なら0
全制約を満たしつつ、最適なコサーキットに辿り着くまで
コベクトルの合成(=pivot選択) を繰り返す
(+0+0 ++)
4
の台集合
1
f
g
OPT (0++0 ++)
の台集合
3
2
課題の例
今回あげた２つの一般化について、論文の講読を行う
２つの一般化の共通点、相違点は・・・？
余裕があれば実装なども
他に最適化問題・マトロイド関係でやりたいことがあれば、
それも歓迎します
二次計画問題など、様々な最適化問題の解法
有向マトロイドの実現可能性 etc…
対称性の発見と
対称性を利用した計算の高速化
伊藤剛志 （博士2年）
[email protected]
対称性と計算効率
例: SAT の解を全部求める
普通に解こうとすると 23=8 通りの可能性
人手で解くなら・・・・・・
x と y と z は同じ立場だから、実質 4 通りの可能性
• 0 個が真の場合 ×
• 1 個が真の場合 ×
• 2 個が真の場合 ○ (x,y,z)=(F,T,T), (T,F,T), (T,T,F)
• 3 個が真の場合 ○ (x,y,z)=(T,T,T)
インスタンスの対称性
節
C1
リテラル
置換
xy
C23
xy
yx
C32
yx
z
z
で不変
グラフを変えない置換の全体: 自己同型群
自己同型群の計算: 今のところ多項式時間では無理
ただし多くの場合に実用的に使えるアルゴリズムが存在
対称性の利用: symmetry
breaking
対称な解のうち一方だけが残るように条件を追加
→ 探索空間が小さくなり高速化
困難な点: 対称性の発見・利用のためにかかる時間
演習の内容
対称性の発見と利用の
どちらかについて文献講読
その他自由に、例えば
• SAT 以外の問題 （列挙問題など）
• アルゴリズムの実装
• アルゴリズムの提案
講読文献の例
P.T. Darga, M.H. Liffiton, K.A. Sakallah and
I.L. Markov:
Exploiting structure in symmetry detection for CNF,
In Proc. 41st Design Automation Conf. (DAC’04),
pp. 530–534, 2004.
http://vlsicad.eecs.umich.edu/BK/SAUCY/
F.A. Aloul, K.A. Sakallah and I.L. Markov:
Efficient symmetry breaking for boolean satisfiability,
in Proc. 18th Int. Joint Conf. on Artificial Intelligence
(IJCAI’03), pp. 271–282, 2003.
http://www.eecs.umich.edu/~faloul/Papers/
faloul_ijcai03.pdf
LDPC符号の実装と性能評価
長谷川 淳（博士1年）
[email protected]
誤り訂正符号
通信路で生じた誤りを受信側で訂正する技術
無線，有線，光・磁気記録システムで使用
例（1ビットを3ビットに符号化，1誤り訂正[3,1]符号）
符号化
送信側
0
復号化
通信
000
情報0を送りたい 符号化： 0 を 000 に
1 を 111 に
010
000
0
誤り訂正：000 か 111 に
近い方に訂正
受信側
誤り訂正符号の遷移
多項式時間復号アルゴリズムの構成が難しい
これまでの主流：代数に基づく
連接符号（リード・ソロモン符号）
次世代符号：ランダム性と特殊な復号法
LDPC符号 + sum-product 復号法
衛星デジタル・テレビ放送（DVB-S2）で採用
ターボ符号 + ターボ復号法
第3世代携帯電話「FOMA」などで採用
LDPC（Low Density Parity Check）
符号[Gallager, 1963]
[n,k]正則LDPC符号
n-k行n列の検査行列Hの
どの列のハミング重みも定数wc，
どの行のハミング重みもwrな
ランダムな符号
1の個数がO(n)個
特徴
例：[12,6]正則LDPC符号
wc=2, wr=4
111100000000
000011110000
000000001111
H
110000010100
000010101001
001101000010
十分長いnに対して，シャノン限界（伝送レートの上限）に近い
性能を発揮
様々な符号長，符号化率の符号を容易に構成可能
sum-product復号法により，線形時間で復号可能
sum-product復号法は並列実装にも適している
演習3の課題
LDPC符号の実装
パラメータ nによる伝送率比較
2通りの構成法(Gallager, Mackay)による比較
復号化アルゴリズムの工夫
ターボ符号やリード・ソロモン符号との性能比較
演習3テーマ
ゲーム・パズルの「難しさ」の解析
組合せ的ゲーム・パズルの計算量
1人ゲーム
(パズル）
手数が
多項式程度
手数が
指数的
お絵描きロジック
スリザーリンク
NP 完全
倉庫番
ラッシュアワー
PSPACE完全
2人ゲーム
オセロ
PSPACE完全
将棋
チェス
指数時間完全
課題案(1)
ゲーム・パズルの「計算量」の解析
「あのゲーム（パズル）の計算量が知りたい！」
そのゲームの計算量を調べる
そのゲームの特別な場合の計算量を調べる
そのゲームの別解問題の計算量を調べる
課題案(2)
組合せゲームの解析の数学的理論
ニム（三山崩し）は簡単に解析できる
ある局面が先手必勝 ⇔
各山のサイズのビット XOR が 0 でない
Grundy-Sprague の理論：
全ての非党派的ゲームはニムに変換できる
この理論および関連研究の文献を読む
課題案(3)
その他諸々
計算量理論に頼らないゲームの難しさ
(面白さ）の評価
パズルに関して何か・・・
計算量理論に関して何か・・・
量子計算・量子情報プロジェクト
フランソワ・長谷川・乾・西鳥羽
情報処理技術のトレンドと量子情報処理展望
量子計算
量子暗号
(1) 現代暗号の安全性の限界
(1) 現在の情報処理の原理的限界
技術の進歩による解読の危険性
スパコン
ﾎﾟｽﾄ地球
ｼﾐｭﾚｰﾀ
(2)高いネットワークセキュリティ要求
・行政・防衛等での機密情報通信
・高額な電子商取引
・医療・遺伝子情報のオンライン化 etc.
単一光子の量子状態に符号化し、
無条件安全性を保証する量子暗号
65TFLOPS
政府機関
量子NW
(2) 超高速計算への要求
・環境、気象、分子設計（製薬）、構造解析、・・
社会的・産業的インパクト
Ex.たんぱく質
構造解析
大学・研究機関
量子並列性を用いた
桁違いに高速な量子ｺﾝﾋﾟｭｰﾀ
Q
医療機関
企業
・装置の巨大化
・電力の増大
・LSIの速度限界
PFLOPS
量子ネットワーク
住基ネットDB・
サーバなど
超高速化への壁：
微細加工の限界
Q
量子分散処理
匿名リーダ選挙の量子分散アルゴリズム
背景
•コンピュータネットワークの自律分散 ⇒ 匿名リーダ選挙問題が基本
古典計算で既知の事実
• 有限時間かつ誤り無しの古典計算で解くことは不可能 (不可能性証明存在)
匿名リーダ選挙問題
計算機同士でリーダ役を自律的に選出
通信・計算
ネット
ワーク
Tani, Kobayashi,
Matsumoto (ERATO 2005)
匿名リーダ選挙問題を、
有限時間かつ誤り無しで解く
量子ｱﾙｺﾞﾘｽﾞﾑを開発
失敗確率
本手法
ネット
ワーク
(量子ｱﾙｺﾞﾘｽﾞﾑ）
この時刻にリーダ
が必ず決定
従来手法
（非量子ｱﾙｺﾞﾘｽﾞﾑ）
リーダ
経過時間
この研究の面白さ
• 量子計算の存在理由：
– 「古典計算で不可能なことを 量子計算で可能にする」
これを具現化、量子計算研究のraison d’etreたりうる
• 日本発の量子アルゴリズム
– こういったことも国際レベルで大切
演習IIIテーマ
– 原論文をヒントに、小規模パス・リング・完全グラフ等で匿名リーダ選挙を誤
差なしで実現する量子プロトコルを開発する
（K2, K3の場合も十分に面白いー回路最適化に通じる)
• S. Tani, H. Kobayashi and K. Matsumoto: Exact Quantum Algorithms for the
Leader Election Problem. Lecture Notes in Computer Science, Vol.3404
(2005), pp.581-592. (今井研OBです)
• その他：量子計算・量子情報に関する研究
– 最短格子ベクトル問題への量子アルゴリズムによる挑戦
– 量子誤り訂正符号の設計 ー LDPC符号プロジェクトと関係
© Copyright 2024 ExpyDoc
