3月25日(木)午後13:00-16:00 
理論計算機科学の最前線

座長 五十嵐善英(群馬大)

講師  蓮沼徹(京大）　hasunuma@kuamp.kyoto-u.ac.jp
演題  de Bruijn ネットワークの構造的性質について

概要  超並列計算機はプロセッサを頂点、プロセッサ間のリンクを辺と
      見ることによりグラフとしてモデル化され、そのモデル化されたグラフ
      は超並列計算機の相互結合網と呼ばれる。
      超並列計算機上の諸問題（情報散布、耐故障性等）は、しばしば相互結合網
      のグラフ構造的性質（独立全域木、連結度等）としてとらえることができる。
      本チュートリアルでは、超並列計算機の相互結合網として知られている
      de Bruijn ネットワーク及びその関連ネットワークのグラフ構造的性質
      に関してこれまでに知られている結果を紹介する。

講師  天野一幸(東北大) ama@ecei.tohoku.ac.jp
演題  比較器回路網を用いたソーティングとマージング

概要  いかに少ないコストでソーティング，或いはマージングを行なうかという
      問題は，基本的かつ重要な問いゆえに古くから多くの研究がなされてきた．
      本講演では，obliviousなアルゴリズムに対応する計算モデルである
      比較器回路網を用いてのソーティング，マージングに焦点をあてる．
      現在のところ，ソーティングについてはAjtai, KomlosとSzemeredi(以下AKS)
      のアルゴリズムが，マージングについてはBatcherのアルゴリズムが
      それぞれ(理論的には)決定版とされるが，AKSアルゴリズムは実用的という
      には程遠く，また，Batcherのアルゴリズムに関してもその最適性の証明など
      幾つもの問題を残している．
      本講演では，これらの問題に関する昨今の研究動向について概説する．

講師  岩田覚(阪大)  iwata@sys.es.osaka-u.ac.jp

演題  劣モジュラ流アルゴリズムの現状と課題

概要  劣モジュラ流は, 効率的に解ける多くの組合せ最適化問題を含む重要な
      モデルであり, Edmonds--Giles (1977) において初めて定式化された. 
      ネットワークの最小費用流問題, ポリマトロイドの交わり問題, 有向グラフ
      の強連結化問題等が, この枠組に入る. 近年のネットワーク・フロー・アル
      ゴリズムの進展において登場してきた新しい技法を劣モジュラ流問題の解法に
      導入することによって, 広範囲の組合せ最適化問題を効率的に解く汎用解法を
      開発しようとする試みについて, 最新の状況を解説する.