FC2ブログ

30分でできる日記

ぐらふ

(Th)
rを根とする整数重みの最小重み全域有効木問題の解は、存在するのならばどの枝eもweight(e)個以下しか含まれないような(重複を許す)r-cut列の長さの最大値に等しい

Fulkersonさんの示した命題(@1974)だそうだが、命題と証明のオラクルっぷりに思わず吹いた。TarjanさんやらEdmondsさんやら、グラフ理論やってる人には何か常人には見えないものが見えているようにしか見えない。

スポンサーサイト



  1. 2006/10/11(水) 00:32:53|
  2. プログラミング|
  3. トラックバック:0|
  4. コメント:0

ふぃぼなっち

よんどころない事情のためにfibonacci heapについて勉強していたわけですが、fibonacci heapって別にfibonacciさんが考えたわけではないんですね(Fredman M. L. & Tarjan R. E. (1987). Fibonacci heaps and their uses in improved network optimization algorithms.)。
まあ、fibonacciさんは12,13世紀頃の人間なんだから当然なわけですが。

どうも計算量の解析時にfibonacci数が使われることが由来のようだが、教科書の解説は論文と解析方法が違うからなのか、そんなものは出てきていないように見える。かといってわざわざ論文を引っ張ってくるのも面倒なので、教科書にも馬鹿には見えない文字で書かれてあった、と納得して次へ進むことにした。

  1. 2006/10/07(土) 17:50:14|
  2. プログラミング|
  3. トラックバック:0|
  4. コメント:0

P*U 2801 Knockdown

どんなにつらい問題でも、ライブラリとSample Input/Outputがあれば何とかなるということを思い知った。

まあ、結果的には外心の公式とか必要なかったのでライブラリは意味なかったわけですが。

  1. 2006/09/17(日) 16:49:15|
  2. プログラミング|
  3. トラックバック:0|
  4. コメント:0

MPI

申請してないので無理だろうなー、と思いつつわざわざ大学に行ってcspにログインしたら、
案の定homeディレクトリが作られてなかったので仕方なくノートPC一台で走らせることに。

あれこれと弄った末とりあえず動いたのだが、一台のマシンの中でせっせと動くMPIプログラムがなんだかとても不憫に思えて仕方なかった。しかしMPIの通信性能といっても何をどう測れば良いものか。。

  1. 2006/09/13(水) 18:13:16|
  2. プログラミング|
  3. トラックバック:0|
  4. コメント:0

OIBH

ttp://oibh.kuye.cn/download/oibh/oopc1.pdf
Problem E : Legendary Pokemon

ttp://oibh.kuye.cn/download/oibh/orpc.pdf
Problem A : Adventure of Super Mario
Problem D : DDR King

ひどい問題を見た。

  1. 2006/09/05(火) 14:28:12|
  2. プログラミング|
  3. トラックバック:0|
  4. コメント:0

| ホーム | 次のページ