読者です 読者をやめる 読者になる 読者になる

アルゴリズムデザインの勉強会

某数理計画系であっているので、参加させてもらっている。教材はこれ。

アルゴリズムデザイン

アルゴリズムデザイン

  • 作者: Jon Kleinberg,Eva Tardos,浅野孝夫,浅野泰仁,小野孝男,平田富夫
  • 出版社/メーカー: 共立出版
  • 発売日: 2008/07/10
  • メディア: 単行本
  • 購入: 10人 クリック: 421回
  • この商品を含むブログ (51件) を見る
今日やったところは5.4章の「最近点対の発見」というところ。二次元空間に点がn個与えられたときに距離が一番短かい点対を発見しようというやつです。アルゴリズム自体は分かったような気がするんだけど*1、漸近的な記法のところがむしろ分かっていない感じだった(先週取り扱ったらしいけど、僕は今週から参加)。\Theta(n)とか\Omega(n)の区別がまずついていないので、来週までにこの辺を理解しておきたい。学類の計算機科学ではO(n)とかしか出てきてないからなあ。
数学的基礎とデータ構造 (アルゴリズムイントロダクション)の4章くらいまでのところを読むとなんとか行けるかなーという感じがしているので、夜にちょっと読んだ。まずは全体像を。

*1:実装してみないと。。。