第４回研究会（２００６年１１月２５日（土） １４時 〜）講演概要
講演者：
宇野 毅明 氏 （国立情報学研究所）
タイトル：
頻出パターン列挙問題と高速アルゴリズム
概要：与えられたデータベースに多く現れる、ある性質を満たした構造を 全て見つける問題を「頻出パターン発見（列挙）問題」という。 例えば、各項目がある集合の部分集合になっている、つまり 部分集合族であるデータベースから、多くの項目に含まれる 部分集合を見つける、各項目がグラフであるようなデータベースから 多く現れる木構造を見つける、といった問題である。 直感的にも明らかなとおり、この手の問題は指数個の解を持ちうる。 また、実用で用いられるような巨大なデータベースに対しては、 1反復あたりの計算時間が長くなるので、到底実用的なアルゴリズムは 作られないと考えられる。しかし実際には、多くの場合、実用的な アルゴリズムが存在し、実用的な時間で列挙できる。 本講演では、このような実用的なアルゴリズムを構築するための、 モデル構築法、アルゴリズム理論、および実装にかかわる技術 を紹介する。
講演者：
今井 浩 氏 （東京大学・JST ERATO-SORST）
タイトル：
量子情報を数理計画する
概要： 実学としてのORの1つの側面が、社会科学での種々の問題をモデル化してそ れを解く方法を与えることを、実践と理論の両方から目指すものだとすると、 対象を自然科学の問題から採ったORもありうるだろう。ここでは、量子力学を 情報処理システムで活用する量子情報の分野をその対象として、OR的アプロー チを図ることについて考えたい。といっても、実際にできていることは、ORと は全く関係ないようにも見える量子情報の諸問題が、数理計画の諸分野の組合 せ最適化・凸多面体的組合せ論・半定値計画・非線形計画と密接に関係してい ることを見抜いて、量子力学を情報処理の観点から見たときでの色々な知見を 与えるという程度かもしれないが。一方、量子情報での成果が、数理計画への 面白い知見を与えてもいる。講演では、量子情報の基礎は仮定せず最低限を最 初に概観し、上述の成果について数理計画を背景としてもった人に述べるとい うスタンスで紹介したい。
ホーム
Copyright, S@CO All rights reserved, 2006.
