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