学術情報メディアセンターセミナー 「アルゴリズムと計算量理論」
京都大学学術情報メディアセンターでは、月に一度、各分野でご活躍の講師をお招きし、それぞれの研究開発活動の内容や現在抱えている課題についてご紹介いただき、参加者を含めて広く議論を行う機会として、月例セミナーを開催しています。
6月25日の学術情報メディアセンターセミナーでは、川原純 奈良先端科学技術大学院大学助教および河内亮周 東京工業大学助教をお招きし、ご講演いただきます。
学内外を問わず多数の方の参加をお待ちしております。
日時
2013年6月25日（火曜日） 16時30分～18時30分
場所
京都大学 学術情報メディアセンター 南館2階 202マルチメディア講義室
（お身体の不自由な方にはエレベーターをご利用いただけますので事務室にお申し付けください。）
対象
どなたでも参加いただけます。
参加費用
無料
参加申し込み
不要
プログラム
| 16時30分～17時30分 | |
|---|---|
| 講演題目 | 大規模データ処理のための離散構造処理系 |
| 講演者 | 川原純 奈良先端科学技術大学院大学情報科学研究科助教 |
| 概要 | 本講演では、大規模データ処理のための離散構造処理系、特に、集合族をコンパクトに効率良く表現するためのデータ構造であるゼロサプレス型二分決定グラフ（ZDD）について解説を行う。ZDDを用いると、与えられたグラフの様々な種類の部分グラフを効率良く列挙し、索引化することが可能となる。例えば、15×15グリッドグラフ上の左上隅から右下隅に至るパス227449714676812739631826459327989863387613323440（＝2.27×1047）本を数分で列挙、保存し、それらの中から指定した条件を満たすパスを高速に検索することができる。他にも、全域木やマッチング等に対しても本手法が適用できる。通信ネットワークの信頼性評価や、配電網の構成法等への応用事例も紹介する。 |
| 17時30分～18時30分 | |
| 講演題目 | 回路計算量の不思議 |
| 講演者 | 河内亮周 東京工業大学大学院情報理工学研究科助教 |
| 概要 | 計算機で扱う問題の計算の複雑さを議論するとき、計算量理論は計算機の理論モデルとしてTuring機械をよく扱うが、その他のモデルとして論理回路もしばしば議論の俎上に載せる。論理回路は定義が単純で扱い易く、実際にNP対P予想解決への正攻法の一つが回路計算量（問題を解くのに必要十分な回路サイズ＝素子数）の解析である。その一方で論理回路にはTuring機械にはない謎の計算能力が備わっている。例えば指数サイズ回路は任意の関数（Turing機械が計算不能な関数ですら！）計算でき、また現状では指数時間Turing機械を多項式サイズ回路で模倣できてしまう可能性すら排除できていない。このような謎の能力がどこから来るかを説明し、それをどのように解析していくのか、NP対P予想への最新アプローチの話も織り交ぜながら解説を行いたい。 |
※ 懇親会はありません
問い合わせ
京都大学 学術情報メディアセンター 宮崎修一
TEL： 075-753-7418
E-mail： shuichi＊media.kyoto-u.ac.jp（＊を@に変えてください）
主催
京都大学 学術情報メディアセンター
http://www.media.kyoto-u.ac.jp/