 |
|
情報オリンピック ２００８春合宿 講義概要
|
2008年3月12日
情報オリンピック日本委員会
- ３月２０日（木）
- 講師： 泉 祐介 先生
- 東京工業大学大学院情報理工学研究科計算工学専攻・博士課程
- ACM-ICPC World Final 出場者
- タイトル： STL を使ってみよう (仮題)
- 概要： C++では，STL(Standard Template Library)と呼ばれるライブラリが標準機能として提供されています．特に可変長配列，マップ(連想配列)，集合などといった「コンテナ」と呼ばれるクラスの一群は，短い時間でプログラムを作ることが要求される場面では，特に重宝します．本講義では，STLの機能の中でも，特にプログラミング・コンテストで利用されることの多いものに焦点を当てます．説明および実習を通じて，その便利さを感じてもらうことが本講義の目的です．
なお，講義に際しては，C++のチュートリアルを設ける，また, Javaの標準クラスに関する説明を入れるなどして，C++以外の言語を使用する参加者が不利にならないよう配慮したいと思います．
- ３月２１日（金）
- 講師： 河内 亮周 先生
- 東京工業大学大学院情報理工学研究科数理・計算科学専攻・助教
- 電子情報通信学会情報ｾｷｭﾘﾃｨｼﾝﾎﾟｼﾞｳﾑ論文賞受賞(2006)
- タイトル： 計算量理論入門 〜NP vs. P予想を解決して100万ドルをゲットしよう！〜
- 概要： 2000年にアメリカのクレイ数学研究所は数学上の重要な７つの未解決問題に懸賞金100万ドルをかけました．そのうちの一つに「NP vs. P 予想」という問題があります．これは「計算量理論」と呼ばれる情報科学の基礎分野における重要な問題なのですが，それほど深い専門的な知識がなくても理解することが可能です．この講義では計算量理論の触りからスタートして「NP vs. P 予想」が理解できるところまでの解説をします．また，計算量理論の最先端についても前提知識無しでも理解できるように解説したいと思います．
- ３月２２日（土）
- 講師： 守谷 純之介 先生
- Yahoo! Japan
- タイトル： 情報検索の基礎 −WEB検索システムを支えるアルゴリズム−
- 概要： 巨大なWEB検索システムを概観し，実際にWEB検索システムを設計します．設計においては，WEB検索システムにて
・ どのように基礎的なアルゴリズムが使用されているか
・ どのようなアルゴリズムが必要とされているか
を中心とし，各アルゴリズムの利点や問題点を明らかにしたいと思います．
教材として，以下を参考にする予定です：
Introduction to Information Retrieval, www-csli.stanford.edu/~hinrich/information-retrieval-book.html
- ３月２３日（日）
- 講師： 小林 悠 先生
- 株式会社アクセラートジャパン・代表取締役
- IOI1996 ハンガリー大会 日本代表
- タイトル： IOI with 関数型言語
- 概要： プログラミング言語には手続き型言語と関数型言語という2つの大きな潮流があります．IOIでは手続き型言語しか使えません．それにも関わらず，問題は関数型言語の発想で作られている物が多数あります．
動的計画法は，その基本は漸化式であり，漸化式は再帰です．関数型言語は再帰が基本となっています．関数型言語の「再帰」「リスト」「参照透過性」という発想に慣れることにより，問題はより解きやすくなります．
今回は，関数型言語の1つであるScalaを使って，予選や本選の問題を使って，みんなで関数型言語で問題を解いてみようと思います．
- ３月２４日（月） 表彰式記念講演
- 講師： 伊藤毅志 先生
- 電気通信大学情報工学科・助教
- タイトル： コンピュータに思考ゲームをさせる試み 〜コンピュータ将棋・囲碁の最前線〜
- 概要： 「コンピュータに思考ゲームをさせる」という試みは、コンピュータが生まれる100年も前からアイディアの段階で考えられてきました。そして、コンピュータが誕生すると同時にチェスをプレーするコンピュータを作る！という目的を実現するために非常にたくさんの研究と実装が行われました。その成果が実った出来事が、1997年のニューヨークで起こります。
ＩＢＭのモンスターマシン「ディープブルー」は、当時の世界チャンピオン・カスパロフ氏に２勝１敗３引き分けで勝利します。このニュースは、世界を駆け巡り、人工知能研究の一つの大きな成果として語られることとなります。
本講演では、まず、コンピュータで思考ゲームを行うという試みについて、情報科学的な位置づけと歴史的な流れについて概観します。そして、チェスに続く形で行われているコンピュータ将棋、コンピュータ囲碁の挑戦について紹介します。どちらの分野もこの数年、非常に注目を集める技術が現れています。
コンピュータ将棋では、一昨年前にBonanzaというプログラムが世界コンピュータ将棋選手権に初出場・初優勝を果たし、その手法に大変注目があつまりました。評価関数の自動学習と全幅探索の手法は画期的なものでした。
また、コンピュータ囲碁の分野でも、一昨年前に現れたフランスの MoGo, CrazyStone が新しい手法で世界を驚かせました。これらのプログラムは、モンテカルロ法をゲーム木探索に応用したＵＣＴと呼ばれるアルゴリズムを提唱し、この分野に一つの大きなブレークスルーをもたらしています。
これらの簡単な技術的な解説を行うと共に、コンピュータで思考ゲームを扱う楽しさを感じていただける講演を行います。