1. ホーム
  2. インフォメーション
  3. イベント・講習会
  4. 学術情報メディアセンターセミナー「アルゴリズムと計算量理論」

コンテンツ

イベント・講習会

学術情報メディアセンターセミナー「アルゴリズムと計算量理論」

2013年4月26日(金曜日)掲載


 京都大学学術情報メディアセンターでは,月に一度,各分野でご活躍の講師をお招きし,それぞれの研究開発活動の内容や現在抱えている課題についてご紹介いただき,参加者を含めて広く議論を行う機会として,月例セミナーを開催しております.
 6月25日の学術情報メディアセンターセミナーでは,奈良先端科学技術大学院大学の川原純 氏および東京工業大学の河内 亮周氏をお招きし,ご講演いただきます.
 学内外を問わず多数の方の参加をお待ちしております.

日時 2013年6月25日(火曜日) 16時30分~18時30分
会場 京都大学 学術情報メディアセンター南館 2階 202マルチメディア講義室
http://www.media.kyoto-u.ac.jp/ja/access/#s_bldg
参加費用 不要
参加申し込み 不要
主催 京都大学 学術情報メディアセンター
お問い合わせ 京都大学 学術情報メディアセンター 宮崎 修一
電話番号:075-753-7418
E-mail:shuichimedia.kyoto-u.ac.jp
プログラム

16時30分~17時30分
講 演 者:川原 純(奈良先端科学技術大学院大学 情報科学研究科 助教)
講演題目:「大規模データ処理のための離散構造処理系」
講演概要:本講演では,大規模データ処理のための離散構造処理系,特に,集合族をコンパクトに効率良く表現するためのデータ構造であるゼロサプレス型二分決定グラフ (ZDD) について解説を行う.ZDDを用いると,与えられたグラフの様々な種類の部分グラフを効率良く列挙し,索引化することが可能となる.例えば,15 × 15 グリッドグラフ上の左上隅から右下隅に至るパス227449714676812739631826459327989863387613323440(= 2.27 × 1047)本を数分で列挙,保存し,それらの中から指定した条件を満たすパスを高速に検索することができる.他にも,全域木やマッチング等に対しても本手法が適用できる.通信ネットワークの信頼性評価や,配電網の構成法等への応用事例も紹介する.

17時30分~18時30分
講 演 者:河内 亮周(東京工業大学 大学院情報理工学研究科 助教)
講演題目:「回路計算量の不思議」
講演概要:計算機で扱う問題の計算の複雑さを議論するとき,計算量理論は計算機の理論モデルとしてTuring機械をよく扱うが,その他のモデルとして論理回路もしばしば議論の俎上に載せる.論理回路は定義が単純で扱い易く,実際にNP対P予想解決への正攻法の一つが回路計算量(問題を解くのに必要十分な回路サイズ=素子数)の解析である.その一方で論理回路にはTuring機械にはない謎の計算能力が備わっている.例えば指数サイズ回路は任意の関数(Turing機械が計算不能な関数ですら!)計算でき,また現状では指数時間Turing機械を多項式サイズ回路で模倣できてしまう可能性すら排除できていない.このような謎の能力がどこから来るかを説明し,それをどのように解析していくのか,NP対P予想への最新アプローチの話も織り交ぜながら解説を行いたい.

イベント・講習会トップへ戻る

 

Copyright © Institute for Information Management and Communication, Kyoto University, all rights reserved.