たなぞう

 1

Computers and Intractability: A Guide to the Theory of Np-Completeness (Series of Books in the Mathematical Sciences)

著者 : Michael R. Garey,David S. Johnson

出版社：W H Freeman & Co (Sd)

発売日：1979-06

評価 :

完了日 : 2007年06月03日

計算可能な問題の中でも、計算困難とされている問題を紹介している文献。 citeseerによると、最も多くリファレンスされている文献。 ちなみに、2位はIntroduction to algorithms。 困難性や完全性を示すためにreductionを考える際、とても参考になる。

計算幾何関連の話題では、minimum weight triangulationが NP困難かどうかは未解決問題として紹介されているが、2006年に解かれた。 この文献によると、14紹介されている未解決問題のうち残すところ あと2件のみだそうな。

この感想へのコメント

 1

Understanding And Using Linear Programming (Universitext)

著者 : Jiri Matousek,Bernd Gartner

出版社：Springer-Verlag

発売日：2007-01-30

評価 :

完了日 : 2007年06月03日

感想は登録されていません。

この感想へのコメント

 1

Computational Geometry: Algorithms and Applications

著者 : Marc Van Kreveld,Mark Overmars,Otfried Schwarzkopf

出版社：Springer

発売日：2000-02-18

評価 :

完了日 : 2007年06月03日

2007年3月、東京の神保町の古本屋さんで購入。 邦訳は既に持っていたが、とても安かったので購入。 以前より論文を書く際、言いまわしや例文の確認等に重宝しているので、 やはり手元に１冊置いておきたかった。 また、邦訳の方を貸している間、ふと調べたくなっても大丈夫になった。

この感想へのコメント

 1

Extremal Combinatorics: With Applications in Computer Science (Texts in Theoretical Computer Science)

著者 : Stasys Jukna

出版社：Springer

発売日：2001-06-13

評価 :

完了日 : 2006年06月03日

この書籍は、ドイツのDagstuhlで行われたワークショップで薦められ、とても感動した組合せ論のテキストです。

この感想へのコメント

 1

Algorithms

著者 : Sanjoy Dasgupta,Christos Papadimitriou,Umesh Vazirani

出版社：McGraw-Hill Higher Education

発売日：2006-09-15

評価 :

完了日 : 2006年06月03日

感想は登録されていません。

この感想へのコメント

 1

Research Problems in Discrete Geometry

著者 : Peter Brab,William O. J. Moser,Janos Pach

出版社：Springer-Verlag

発売日：2005-11-30

評価 :

完了日 : 2006年06月03日

離散幾何学の未解決問題をまとめた書籍。Paul Erd"os の草案をもとに、著者たちの尽力の賜物。 楽しいのだけれど、少し偏りがみられる。

この感想へのコメント

 1

近似アルゴリズム

著者 : V.V. ヴァジラーニ

出版社：シュプリンガー・フェアラーク東京

発売日：2002-11

評価 :

完了日 : 2006年06月03日

大学院の博士向けの講義のテキストとして使用されていました。 実際は、講義自体英語で行われるため、オリジナルの方が参考図書でした。 Primal-dual theory が易しく解説されていたり、AroraのEuclid Traveling Salesman Problems のPTASなどがエキサイティングで、 とても楽しく近似アルゴリズムのエッセンスを理解することができます。 それから、巻末のOpen Problemsのまとめは、とっても有益です。 ただ惜しむらくは、翻訳の際に混入されたと思われる曖昧さの ひどい箇所が多数見受けられること。オリジナルを当たらないと 理解できない文章がちょっと多いかなぁ。

この感想へのコメント

 1

Handbook Of Data Structures And Applications (Chapman & Hall/Crc Computer and Information Science Series.)

著者 :

出版社：Crc Pr I Llc

発売日：2004-10-15

評価 :

完了日 : 2006年02月03日

2006年2月に購入。 大学の図書館で発見し、内容を確認して、即座にアマゾンで注文する。 データ構造の基本から、より先進的なデータ構造技法に加え、 実際の応用問題に対してデータ構造をどう適用するかが紹介されている。

Cache-oblivious, kinetic, dynamic graphsなど比較的新しいパラダイムも 網羅されている。 39章のo(log n)探索は、結構最近はやりの研究テーマの一つである word-RAM モデルの説明を行っている。 私信としては、hash tableの章節がとても興味深かった。 ロビンフッドやカッコーなど、 変な冠がついているhashingがたくさんある。 とにかくcuckoo hashingはとても簡潔なのだけど効率も良いので、 確認がてら見てみたら良いと思う。

ただ、索引が無いので不明な用語を引くというような 辞書的な利用ができない。ページ番号も通しではなく、 各章ごとで閉じているので、何となく嫌だ。 ハンドブックという割に重いのもちょっと嫌だ。 でも、ページ数の割に値段がお手ごろだと思う。

表紙のPQ-treeはグラフの平面性判定で利用されるデータ構造。 その他多くのグラフクラスの認識でも重要な役割を担ったりする。

この感想へのコメント

 0

はみだし幾何学 (岩波科学ライブラリー (18))

著者 : 徳山 豪

出版社：岩波書店

発売日：1994-12

評価 :

完了日 : 2005年08月27日

感想は登録されていません。

この感想へのコメント

 1

岩波講座 応用数学〈5〉

著者 :

出版社：岩波書店

発売日：1993-09

評価 :

完了日 : 2005年06月04日

後ろ半分が計算幾何学の内容のダイジェスト。

この感想へのコメント

 1

Visual Computing: Geometry, Graphics, And Vision (Graphics Series)

著者 : Frank Nielsen

出版社：Charles River Media

発売日：2005-07-15

評価 :

完了日 : 2005年06月03日

コンピュータグラフィクス関連の書籍ですが、基礎となる幾何学的なフレームワークなどを丁寧に解説している点が特筆すべき点かもしれません。 この書籍は、computer science のメーリングリストで知り、 当時少しグラフィクス関係に興味があったので購入しました。 決め手は著者がFrackさんだったことが大きいです。 Frankさんは、大学に講演しに来たのをきっかけで知り、 カナダでの国際会議でタクシーに便乗させて頂いたりしました。 とても日本語が上手でやさしいフランス人で、 SoCGのvideo/multimedia comitteeだったりします。

この感想へのコメント

 1

Geometry And Topology for Mesh Generation (Cambridge Monographs on Applied and Computational Mathematics)

著者 : Herbert Edelsbrunner

出版社：Cambridge University Press

発売日：2006-01-31

評価 :

完了日 : 2005年02月07日

感想は登録されていません。

この感想へのコメント

 1

Spatial Tessallations - Concepts & Applications of Voronoi Diagrams 2e (E-Book)

著者 : Okabe

出版社：John Wiley & Sons Inc

発売日： 

評価 :

完了日 : 2004年08月27日

いろいろなVoronoi図なんかを楽しく勉強できます。先生にねだって買ってもらって、すっごく熱心に読みました。ボロボロになってしまったので、自分でも購入しました。

この感想へのコメント

 1

データ構造とアルゴリズム

著者 : 杉原 厚吉

出版社：共立出版

発売日：2001-12

評価 :

完了日 : 2004年07月27日

このテキストは、後輩と二人で行った輪講（夏休みゼミ）で使用した。 輪講は予定通り４週間程度で終えることができた。
学部生向けのテキスト。非常に内容が簡潔に纏められていて読みやすい。 章ごとの関連フローも分かりやすくて担当範囲を配分する一助も担う。 計算幾何の話題にもふれている点が特筆すべき点だと思う。

この感想へのコメント

 1

組合せ幾何学のアルゴリズム

著者 : Herbert Edelsbrunner,今井 浩

出版社：共立出版

発売日：1995-02

評価 :

完了日 : 2004年06月03日

少しハードルが高い。集合論や多面体についてきちんとしてからだと、とっても楽しく読めると思う。

この感想へのコメント

 1

グラフ理論入門

著者 : R.J. ウィルソン

出版社：近代科学社

発売日：2001-10

評価 :

完了日 : 2003年06月03日

修士1回の秋頃購入。 実際、グラフ理論に関する講義を受講する機会が無く、 独学用のテキストとして購入。 一つ一つの定理をきちんと証明しながら、 軽やかに進んでいく。読みやすい。 図を多用し理解を促している点も特筆すべき点だと思う。

グラフ理論の研究を行っていくのであれば、 このテキストで準備をしてから、 ディーステルのグラフ理論に入るのが得策なのかなぁ。

この感想へのコメント

 1

離散構造とアルゴリズム〈1〉

著者 :

出版社：近代科学社

発売日：1992-07

評価 :

完了日 : 2003年06月03日

徳山先生の計算幾何の解説と、逆探索の章節が興味深かった。

この感想へのコメント

 1

Davenport-Schinzel Sequences and Their Geometric Applications

著者 : Micha Sharir,Pankaj K. Agarwal

出版社：Cambridge Univ Pr (Sd)

発売日：1995-05

評価 :

完了日 : 2003年06月03日

Davenport-Schinzel列と、その組合せ幾何学への応用についてまとめられています。 DS列は、アレンジメントの組合せ複雑度を解析する際、とても強力ですが、結構難解です。が、大好きです。

当時、大学の合同ゼミで使用していたKozenのテキストで、 TarjanたちのUnion-Findのヒューリスティクスの解析を担当しました。 ここでは、amortized analysisやAckermann関数の関数的逆などのキーワードが、とても刺激的でした。 修士1回生の夏休みを潰して比較的熱心に勉強しました。 このゼミの際、指導教官の先生が「Ackermann関数が出てくるのは、 union-find以外にDavenport-Schinzel sequenceが有名だよね。」というお話がありました。 それで調べてみたら、離散・計算幾何学にとても関係深く、勇み足でしたが購入しました。 1万円を超える書籍を購入したのは初めてでした。 それから、洋書という点でも初めてでした。

実際、(n, 3)-DS列の最長列の長さのタイトな上界の証明は、難解でしたがとても楽しく勉強できました。 自習した当時は、その理解はおぼろげでしたが、だいぶ後で SeidelのAckermann関数の解釈に関する資料を見て、再び証明を見直すとちょっと理解が深まります。 それでもやっぱり、Ackermann関数が出てくる解析はとても難しいです。 例えば、Erik DemaineたちのOpen Problem Projectにもある、 "Voronoi diagram of moving points"なんかは、 その最たるものかもしれません。 一方で、(n, 2)-DS列はとても理解が簡単でいろいろ応用もあります。 長さ2n-3の(n-1, 2)-DS列と凸n角形の三角形分割の全単射や、 DS列を使った耳定理の証明などはちょっぴり感動的です。

この感想へのコメント

 1

The Design and Analysis of Algorithms (Texts and Monographs in Computer Science)

著者 : Dexter C. Kozen

出版社：Springer

発売日：1992-01

評価 :

完了日 : 2002年06月03日

ちょっぴり高度なアルゴリズムの教科書。 修士1回のときの合同ゼミのテキストで使用。 各章一つ代表的な問題を取り上げ、 約４から６ページにまとめてあり、ゼミの担当配分が容易。 宿題や演習なども豊富にあり、それぞれのトピックスの理解を助ける。 ただ、かなり行間を読む力を要求してくるので、 それなりの覚悟と知識が必要だと思う。 当時のゼミはかなり紛糾し、 staff諸氏に泣かされた担当者も数知れずいた。 ある種、センスが問われるゼミだったと振り返って思う。

取り扱っている問題自体は非常に有名な問題ばかりで、 1990年代前後の代表的な結果が包括的にまとめられている。 第2章でいきなりマトロイドが出てきたり、 planar separator theoremを解説しているテキストはこれだけだと思う。データ構造、計算量、PRAMモデル、ネットワークフロー、その他諸々 かなりマニアックなテーマがひしめき合っている感じの印象を受けます。

この感想へのコメント

 1

Algorithmic Geometry

著者 : Jean-Daniel Boissonnat,Mariette Yvinec

出版社：Cambridge Univ Pr (Txp)

発売日：2001-02-15

評価 :

完了日 : 2002年01月03日

Amazonで初めて買った本。洋書の専門書ってこんなに簡単に購入できるんだ、と感動した。

この感想へのコメント