情報オリンピック 夏季セミナー２００８ 概要

• 日時 2008年8月25日（月）〜28日（木）
  　
• 場所 株式会社ＮＴＴデータ駒場研修センター（東京都目黒区）
  　
• 宿泊 こまばエミナース
  　
• 参加者 21名
  　
• スケジュール

   
      8月25日 (月)
        15:00         集合・受付開始
        15:30〜18:00  打ち合わせ・班決め，セミナー(1)
        18:00〜19:30  夕食
        19:30〜21:30  セミナー(2)
        
      8月26日 (火)
         9:00〜12:00  講義(1)   
                      谷 聖一 先生「Kolmogorov 記述量入門」
        12:00〜13:00  昼食
        13:00〜18:00  セミナー(3)
        18:00〜19:30  夕食
        19:30〜21:30  セミナー(4)
        
      8月27日 (水)
         9:00〜12:00  セミナー(5)
        12:00〜13:00  昼食
        13:00〜14:30  講義(2)  
                      北内 啓 氏「コンピュータでテキストを扱う 〜テキスト処理のための基礎技術〜」
        14:30〜16:00
        16:00〜18:00  セミナー(6)
        18:00〜19:30  夕食
        19:30〜21:30  セミナー(7)
    
      8月28日 (木)
         9:00〜12:00  発表会(1)
        12:00〜13:00  昼食
        13:00〜15:00  発表会(2)
        15:00         解散
  

  
  
• セミナーで使用したテキスト
  1. 『アルゴリズムデザイン』
  2. 『組合せ最適化-理論とアルゴリズム』
  3. 『コンピュータ・ジオメトリ―計算幾何学:アルゴリズムと応用』
  4. 『ゲーム開発者のためのAI入門』
  5. 『ハッカーのたのしみ ― 本物のプログラマはいかにして問題を解くか』
  
  
  
• グループ毎の発表タイトル
  1. 「アルゴリズムデザイン」グループ
     • グリーディアルゴリズム
     • 分割統治
     • NP問題
     • NP困難問題に対するグリーディアルゴリズム
     • NP困難問題に対する局所探索アルゴリズム
  2. 「組合せ最適化-理論とアルゴリズム」グループ
     • 最大フロー問題
  3. 「コンピュータ・ジオメトリ―計算幾何学:アルゴリズムと応用」グループ
     • 線分交差のアルゴリズム
     • 美術館問題
     • 最小包含円
     • ボロノイ図
     • ロボット移動経路探索
  4. 「ゲーム開発者のためのAI入門」グループ
     • 人間くさいAI （ファジー集合・ニューラルネット入門）
     • ニューラルネットについて（石取りゲーム）
     • ニューラルネット（学習精度のシミュレーション）
     • A*アルゴリズム（障害物を回避しつつ最短経路を探す）
  5. 「ハッカーのたのしみ ― 本物のプログラマはいかにして問題を解くか」グループ
     • ビット演算とその応用
     • 多倍長演算とビット演算
     • グレイコードとその応用
  
  
• 講義概要
  • 8月26日 (火)　9:00〜12:00
  • 講師　谷 聖一 先生（日本大学）
  • タイトル　「Kolmogorov 記述量入門」
  • 講義概要
    　文字 0 と 1 を使ってできる長さ25の二つの文字列

    1111111111111111111111111
    1010011100101011010000100

    を見比べると，直感的に両者の規則性は異なります．例えば，確率を使ってこれらを区別しようとしても，公正なコイントスを25回独立に繰り返して生成される系列がこれらの文字列と一致する確率は，どちらも 1/2^{25} と同じになってしまいますので，うまく区別できません．
    　Kolmogorov 記述量は，このような有限文字列の規則性を表すことを目指した指標の一つで，文字列 s の Kolmogorov 記述量は，s を生成する最小のプログラムのサイズで定義されます．Kolmogorov 記述量には，それ自体に計算可能性や文字列の圧縮可能性と関連していろいろと面白い性質があり，また，様々な応用が知られています．
    　本講義では，前半で Kolmogorov 記述量に関する基本性質を紹介して，後半ではKolmogorov 記述量の応用例の一つとして類似性判定に対する応用を紹介します．

  • 8月27日 (水)　13:00〜14:30
  • 講師　北内 啓 氏（NTTデータ 技術開発本部 ビジネスインテリジェンス推進センター）
  • タイトル　「コンピュータでテキストを扱う 〜テキスト処理のための基礎技術〜」
  • 講義概要
    　コンピュータはもともと「計算機」という名の通り、数値計算を高速に実行するための機械として開発されました。現在では画像や音声などあらゆる種類のデータを処理することが可能となり、その中でもテキスト（文字列）は様々な場面で頻繁に利用されています。
    　本講義では、コンピュータでテキストを処理する際に必要となる主な技術について、そのアルゴリズムやプログラムにおける利用方法を解説します。さらに、自然言語（日本語のように人間が使う言葉）を処理する技術について、実際にどのように世の中の役に立っているかという応用例を交えながら紹介したいと思います。