2007-04-01から1ヶ月間の記事一覧
Weigen Yan and Yeong-Nan Yeh Theoretical Computer Science Volume 369, Issues 1-3, 15 December 2006, Pages 256-268 http://dx.doi.org/10.1016/j.tcs.2006.09.002 与えられた木にいくつ部分木があるか,という問題. SzekelyとWang (2005) は頂点数nを…
Jianfeng Hou, Guizhen Liu and Jiansheng Cai Theoretical Computer Science Volume 369, Issues 1-3, 15 December 2006, Pages 250-255 http://dx.doi.org/10.1016/j.tcs.2006.08.043 グラフの彩色に関するはなし. 「List Coloring Conjecture」としてよ…
G. Bebek, P. Berenbrink, C. Cooper, T. Friedetzky, J. Nadeau and S.C. Sahinalp Theoretical Computer Science Volume 369, Issues 1-3, 15 December 2006, Pages 239-249 http://dx.doi.org/10.1016/j.tcs.2006.08.045 生命進化の理論モデルに対する理…
Hans Kellerer and Vitaly A. Strusevich Theoretical Computer Science Volume 369, Issues 1-3, 15 December 2006, Pages 230-238 http://dx.doi.org/10.1016/j.tcs.2006.08.030 スケジューリングについて. 1機械で,release dateはなし.このとき,遅れ …
Stephen Travers Theoretical Computer Science Volume 369, Issues 1-3, 15 December 2006, Pages 211-229 http://dx.doi.org/10.1016/j.tcs.2006.08.017 MFCS2004の論文. 整数集合を計算する回路を考えるが,そのゲートは合併を取る操作∪,共通部分を取る…
Farshad Rostamabadi and Mohammad Ghodsi Theoretical Computer Science Volume 369, Issues 1-3, 15 December 2006, Pages 197-210 http://dx.doi.org/10.1016/j.tcs.2006.08.038 地図のラベル付け問題について. 平面上のいくつかの点に一定の大きさの正…
Michael A. Bekos, Michael Kaufmann, Antonios Symvonis and Alexander Wolff Computational Geometry Volume 36, Issue 3, April 2007, Pages 215-236 http://dx.doi.org/10.1016/j.comgeo.2006.05.003Graph Drawing 2004の論文.地図のラベル付け問題に関…
Christian Schindelhauer, Klaus Volbert and Martin Ziegler Computational Geometry Volume 36, Issue 3, April 2007, Pages 197-214 http://dx.doi.org/10.1016/j.comgeo.2006.02.001 ISAAC 2004の論文.盛んに研究されているspannerのはなし.点集合Pに…
Joachim Gudmundsson, Giri Narasimhan and Michiel Smid Computational Geometry Volume 36, Issue 3, April 2007, Pages 183-196 http://dx.doi.org/10.1016/j.comgeo.2006.05.002 地図上の道などはコンピュータ内部で折れ線として表現されているが,例え…
N.G.H. Kruithof and G. Vegter Computational Geometry Volume 36, Issue 3, April 2007, Pages 166-182 http://dx.doi.org/10.1016/j.comgeo.2006.01.003 Edelsbrunnerの定義したskin surfaceの三角形メッシュを作る論文で,skin surfaceの定義に現れるshr…
Mark de Berg, Dan Halperin and Mark Overmars Computational Geometry Volume 36, Issue 3, April 2007, Pages 159-165 http://dx.doi.org/10.1016/j.comgeo.2006.03.002 任意精度のアレンジメントを有限精度のアレンジメントに変換することをsnap roundin…
〆切が今日だと言うことをすっかり忘れていたので,急いで書いて投稿.
毎年同じ実験してるはずなのに,毎年いろいろと準備をし直してるので,大変といえば大変.
「違和感を感じる」という言い方に違和感が. つまり「感」が重なるところに変な印象を持つわけで,おそらく「違和感を持つ」と言った方がすっきりするのでは. 「嫌悪感を感じる」も「嫌悪感を持つ」とか「嫌悪感を催す」といった具合でしょうか.
行って来ました.懐かしい面々と顔を合わせて近況報告や昔話をしたり,とても楽しい時間を過ごしました. 記念文集は自分の担当分をもっとしっかり書けばよかったと若干後悔していますが,他の方の文章は楽しく拝読しました.また,年譜のところに私たちの卒…
さて,上で書いた「誤信」だけども,どうして人々はそのような間違いを犯してしまうんだろうか,と原因を探ってみる.おそらく「単体法は端点最適解を発見する」という知識から出発してしまうからだと思う.単体法が端点最適解を発見することは正しいし,任…
ALGORITHMS 1E作者: Sanjoy Dasgupta Algorithms,Christos H. Papadimitriou Algorithms,Umesh Vazirani Algorithms出版社/メーカー: McGraw-Hill Professional発売日: 2006/09/13メディア: ペーパーバック クリック: 3回この商品を含むブログ (1件) を見る…
「最適解を持つ線形計画問題には,端点最適解が存在する」は誤り. 必ずしも正しくない. Dasgupta, Papadimitriou, Vaziraniの「Algorithms」にはそんな感じで書いてあったけど,誤り.
今回からPowerPointを使い出したけども、それによって学生の理解が進むようになったかはまだ分からない。 でも、いろいろとできる工夫はしてみたい。
やはり演習問題を解くのは楽しい。
明日から本格的に始まる.
E. Dantsin, V. Kreinovich, A. Wolpert SIGACT News, 36(4), pages 103-108, December 2005. Groverのアルゴリズムをそのまま使えば量子的に1.414^nぐらいの時間でSATが解ける,と. なるほど. この論文の目的はそれを他のSATアルゴリズムに適用するという…
離散数学への招待〈上〉作者: J.マトウシェク,J.ネシェトリル,Jir´i Matousek,Jaroslav Nesetril,根上生也,中本敦浩出版社/メーカー: シュプリンガー・フェアラーク東京発売日: 2002/12メディア: 単行本購入: 2人 クリック: 12回この商品を含むブログ (10件)…
自分が全体説明を担当.若干しゃべり過ぎたと思う.そのため少々疲れた.
いろいろなことをするために時間の使い方を大切に.
普段あまり触らないC言語を触っていたけど,どうもイライラしてしまった. 昔Javaで書いたものをCにただ直すだけなのだけど,入出力関係の部分がやけに汚い. 結局解決なかったので,明日に持ち越し. もう嫌になって明日やらないかもしれないけど.
今年度はまとめ役.
お疲れ様でした.
3日間いて、今日急いで帰って来ました。楽しかったですが、なんかどっと疲れたような。
グラフ理論 (Springer‐Verlag GTMシリーズ)作者: R.ディーステル,Reinhard Diestel,根上生也,太田克弘出版社/メーカー: シュプリンガー・フェアラーク東京発売日: 2000/10メディア: 単行本購入: 1人 クリック: 45回この商品を含むブログ (10件) を見る最終章…