| 発表言語 |
日本語
|
| 開催日 |
2013年04月24日 14時40分
|
| 終了日 |
2013年04月24日 15時40分
|
| 開催場所 | 京都大学数理解析研究所420大会議室 |
| セミナー名 | 大談話会 |
| タイトル |
Dualizing Monotone Boolean Functions |
| 分野 |
代数
幾何
解析
その他
|
| 講演者名 | 牧野 和久 |
| 講演者所属 | 京大・数理研 |
| 概要 | 本講演では, 情報化社会において計算，アルゴリズムが如何に重要であるかを
述べると共に，
講演者がこれまで取り組んできた問題のひとつである単調論理関数の双対化問題
を紹介する．
単調論理関数の双対化問題とは，与えられた単調な論理和形から等価な論理積
形を求める問題である．
この双対化問題は，数理計画，人工知能，データベース，分散システム，
学習理論など様々な分野に現れる数多くの重要かつ実用的な問題と（多項式時間
還元の意味で）等価であることが知られている．
現在までのところ，Fredman-Khachiyan による準多項式時間アルゴリズムが知ら
れているが，多項式時間アルゴリズムが存在するかどうか未解決のままである．
本講演では，この双対化問題の歴史や最近の話題について紹介する．また，関連
する多面体の端点列挙の話題についても述べる． |
| 備考 | プログラム
14：40-15：40 牧野 和久氏（420号室）
15：40-16：30 Tea Break（110号室）
16：30-17：30 浅岡 正幸氏（420号室）
◆ 多数のご来聴をお待ちしております．
◆ とくに院生の出席を歓迎します． |
| リンク | http://www.kurims.kyoto-u.ac.jp/ja/seminar/danwakai.html |