学術情報メディアセンターセミナー 「アルゴリズムと計算量理論」
掲載
開催日時
京都大学学術情報メディアセンターでは，月に一度，各分野でご活躍の講師をお招きし，それぞれの研究開発活動の内容や現在抱えている課題についてご紹介いただき，参加者を含めて広く議論を行う機会として，月例セミナーを開催しております．
１０月２５日の学術情報メディアセンターセミナーでは，京都大学次世代研究者育成センター 特定教授 の 上野賢哉 氏，京都大学大学院情報学研究科 助教 の 玉置卓 氏をお招きし，ご講演いただきます．
学内外を問わず多数の方の参加をお待ちしております．
| 日時 | 2011年10月25日（火曜日） 16時30分～18時30分 |
| 会場 | 京都大学 学術情報メディアセンター南館 2階 202マルチメディア講義室 |
| 参加費用 | 不要 |
| 参加申し込み | 不要 |
| 主催 | 京都大学 学術情報メディアセンター |
| お問い合わせ | 京都大学 学術情報メディアセンター 宮崎 修一 電話番号：075-753-7418（内線7418） E-mail：shuichi 画像
|
| プログラム | 16時30分～17時30分 講演者：上野賢哉（京都大学次世代研究者育成センター 特定助教） 講演題目：論理式の複雑さを明らかにする理論 講演概要：論理式は計算理論のいたるところに現れる基本的な計算模型であり，その構造的複雑さを解明することは，算法の並列化に対する限界を示唆するなど，計算量理論における最重要課題の一つとなっている．本講演では，論理式の複雑さを明らかにするための理論的枠組みについて，その背景や古典的手法から始め，最新の取り組みに至るまでを解説する． 17時30分～18時30分 講演者：玉置 卓（京都大学大学院情報学研究科 助教） 講演題目：指数時間厳密アルゴリズム 講演概要：実用上現れる最適化問題の多くは，多項式時間で厳密に解くことが難しい．そのような計算困難問題に対して，多項式時間で「近似解」を求める近似アルゴリズム，「指数時間」で厳密解を求める厳密アルゴリズム，の二種類のアプローチが存在する．本講演では，近年急速に研究が進んでいる後者のアプローチ，厳密アルゴリズムを取り上げ，その背景や基本的な結果を紹介する． |