データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3©2ch.net

**デフォルトの名無しさん転載ダメ©2ch.net** · 2016/06/19(日) 14:47:29.63

このスレッドは天才チンパンジー「アイちゃん」が
言語訓練のために立てたものです。

アイと研究員とのやり取りに利用するスレッドなので、
関係者以外は書きこまないで下さい。

　　　　　　　　　　　　　　　　　　京都大学霊長類研究所

データ構造,アルゴリズム,デザインパターン総合ｽﾚ 2
http://echo.2ch.net/test/read.cgi/tech/1362301811/

【関連スレ】
3Dアルゴリズム全般
http://toro.2ch.net/test/read.cgi/tech/1164171086/
＜集大成＞アルゴリズム大辞典
http://toro.2ch.net/test/read.cgi/tech/1086272325/
アルゴリズム総合スレ in ム板
http://toro.2ch.net/test/read.cgi/tech/1217773415/

アルゴリズムとデータ構造 - Kaneko Lab.
ttp://www.kkaneko.com/adp/algo/index.html
アルゴリズムとデータ構造 - ソースコード探険隊
ttp://www.codereading.com/algo_and_ds/
各種アルゴリズムの C++ による実装 - Spaghetti Source
ttp://www.prefield.com/algorithm/
アルゴリズムとデータ構造 - プログラミングスレまとめ in VIP
ttp://vipprog.net/wiki/algo_and_data_const.html

**デフォルトの名無しさん** · 2017/01/02(月) 12:24:22.04

もっといい評価はありますでしょうか？

**デフォルトの名無しさん** · 2017/01/02(月) 12:28:36.72

判ってるなら効くな

**デフォルトの名無しさん** · 2017/01/02(月) 14:08:15.59

ダイクストラ法の正しさの証明で分かりやすい証明を思いつきました。

発表しましょうか？

**デフォルトの名無しさん** · 2017/01/02(月) 14:21:37.12

どうぞどうぞ

**デフォルトの名無しさん** · 2017/01/02(月) 14:27:23.53

>>227
オーダーについてあんま良くわかってないんだろうけどO((n-1)!) なんて書き方はないよ
もし書いたとして、それはO(n!)と同じもの

**デフォルトの名無しさん** · 2017/01/02(月) 17:55:38.72

>>222
実無限はいろいろ破綻するから可能無限にしておいたほうがいいよ
実数の定義に∞, -∞は入らない
というか，そもそも -∞ というのがおかしい存在

つリーマン球面

**デフォルトの名無しさん** · 2017/01/02(月) 19:04:30.86

なんか正しさの証明を書いてみると簡単なことなのに長くなりますね。
もし、間違っていたら指摘してください。

http://imgur.com/PDx2vmZ.jpg
http://imgur.com/DbMiSz5.jpg

ダイクストラのアルゴリズムは↑のものとします。

**デフォルトの名無しさん** · 2017/01/02(月) 19:05:18.10

節点 s から、ある節点 i への最短経路が存在するとき、その長さを td(i) で表わすことにする。
i への経路、したがって最短経路が存在しないときには、 td(i) = ∞ とする。

ステップ(1)で選ばれる節点 v ∈ V - S に対して、 d(v) = td(v) が成り立つことを数学的帰納法により、以下で証明する。

最初にステップ(1)が実行されるときを考える。
明らかに、 d(s) = td(s) = 0 が成り立つ。

k ≧ 1 とする。
第 1 回目から第 k 回目にステップ(1)が実行されるときに、いつもステップ(1)で選ばれる節点 v ∈ V - S に対して、
d(v) = td(v) が成り立つと仮定する。

**デフォルトの名無しさん** · 2017/01/02(月) 19:05:35.40

第 (k+1) 回目にステップ(1)が実行されるときを考える。
このとき、明らかに #S = k であり、 ∀i ∈ S に対して、 d(i) = td(i) が成り立つ。
第 (k+1) 回目にステップ(1)が実行されるときに選ばれる節点を v ∈ V - S とする。
d(v) = ∞ である場合と d(v) ≠ ∞ である場合で場合分けして考える。

(1) d(v) = ∞ である場合。
td(v) ≠ d(v) = ∞ と仮定して矛盾を導く。
td(v) ≠ ∞ であるから、節点 s から節点 v への経路 s = v_0 → v_1 → … → v_(l-1) → v_l = v が存在する。
明らかに、 td(v_0), td(v_1), …, td(v_(l-1)), td(v_l) ≠ ∞ である。
v_0 ∈ S, v_l ∈ V - S であるから、 v_i ∈ S, v_(i+1) ∈ V - S となるような i が存在する。
∀j ∈ V - S に対して、 d(j) = ∞ であるから、 d(v_(i+1)) = ∞ である。また、 v_i ∈ S であるから、
d(v_i) = td(v_i) ≠ ∞ が成り立つ。
v_i がステップ(2)で S に追加されたときのことを考えれば分かるように、 (v_i, v_(i+1)) ∈ E かつ v_(i+1) ∈ V - S であるから、
d(v_(i+1)) = ∞ ということはない。これは矛盾である。
よって、 d(v) = td(v) = ∞ が成り立つ。

**デフォルトの名無しさん** · 2017/01/02(月) 19:05:51.66

(2) d(v) ≠ ∞ である場合。
td(v) ≠ d(v) と仮定して矛盾を導く。
ステップ(2)を考えれば明らかなように、 d(v) ≠ ∞ であるから、節点 s から節点 v への
最短経路 s = v_0 → v_1 → … → v_(l-1) → v_l = v が存在する。
よって、 td(v) ≠ ∞ である。
仮定により、 td(v) ≠ d(v) であるから、 td(v) < d(v) が成り立つ。
v_0 ∈ S, v_l ∈ V - S であるから、 v_i ∈ S, v_(i+1) ∈ V - S となるような i が存在する。
td(v_(i+1)) < d(v_(i+1)) である。なぜなら、もし、そうでないと仮定すると、 d(v_(i+1)) = td(v_(i+1)) であるが、
td(v_(i+1)) ≦ td(v) < d(v) であるから、 d(v_(i+1)) < d(v) となってしまい、ステップ(1)での v の
選ばれ方に矛盾するからである。
v_i ∈ S であるから、 d(v_i) = td(v_i) である。
v_i がステップ(2)で S に追加されたときのことを考えれば分かるように、 (v_i, v_(i+1)) ∈ E かつ v_(i+1) ∈ V - S であるから、
d(v_i) + a_(v_i v_(i+1)) ≧ d(v_(i+1)) である。
一方、明らかに、 td(v_i) + a_(v_i v_(i+1)) = td(v_(i+1)) であるから、
td(v_(i+1)) = td(v_i) + a_(v_i v_(i+1)) = d(v_i) + a_(v_i v_(i+1)) ≧ d(v_(i+1)) となるが、これは矛盾である。
よって、 td(v) = d(v) が成り立つ。

**デフォルトの名無しさん** · 2017/01/02(月) 19:06:08.41

以上より、第 (k+1) 回目にステップ(1)が実行されるときにも、ステップ(1)で選ばれる節点 v ∈ V - S に対して、
d(v) = td(v) が成り立つ。

S に追加される節点はすべて、ステップ(1)で選ばれた節点 v ∈ V - S であり、一度 S に追加された節点 v の d(v) はそれ以後、
変更されないから、ステップ(1)でアルゴリズムが終了したとき、 ∀i ∈ S = V に対して、 d(i) = td(i) が成り立つ。

**デフォルトの名無しさん** · 2017/01/02(月) 19:26:36.14

>>232

ある本では、

正定数 c, n0 が存在して、 n ≧ n0 のとき、 T(n) ≦ c*f(n) であるなら、
T(n) は O(f(n)) であるという

と定義されています。

T(n) = n!
f(n) = n!
g(n) = (n-1)!

とします。

このとき、明らかに、
T(n) は O(f(n)) ですが、
T(n) は O(g(n)) ではありません。

**デフォルトの名無しさん** · 2017/01/02(月) 19:29:54.44

したがって、

O(f(n)) と O(g(n)) は異なります。

**デフォルトの名無しさん** · 2017/01/03(火) 08:33:06.09

この狂人ヤバいなｗ

**デフォルトの名無しさん** · 2017/01/03(火) 08:50:16.82

>>224
>>227

閉路を含まないから、各点を高々1回しか通らない。（端点も）

直通の経路が　１
途中でｋ個所を通過する経路が
　(n-2)(n-3)･････(n-k-1) = (n-2)!/(n-k-2)!
だけある。ただし、k≦n-2
よって
a_n = (n-2)!｛1 + 1/1! + 1/2! + … + 1/(n-2)!},

n ≧ 2 のとき、

(n-2)! ≦ (n-2)! * (1 + 1/1! + 1/2! + … + 1/(n-2)!) ≦ e * (n-2)!

したがって、

a_n = Θ((n-2)!)

である。

**デフォルトの名無しさん** · 2017/01/03(火) 08:52:54.04

>>234-238

のダイクストラのアルゴリズムの正しさの証明に間違いはないという
ことでOKですか？

**デフォルトの名無しさん** · 2017/01/03(火) 11:39:58.60

Erik DemaineはMITの歴史上最年少で教授になったという天才だそうですね。

今、そのErik Demaineの2005年のダイクストラのアルゴリズムについての講義を見ています。

見終わったら、講義の要約について書きます。

**デフォルトの名無しさん** · 2017/01/03(火) 13:47:58.01

ダイクストラのアルゴリズム：

01: d[s] ← 0
02: for each v ∈ V - {s}:
03: ■■d[v] ← ∞
04: S ← Φ
05: Q ← V
06: while Q ≠ Φ:
07: ■■u ← ExtractMin(Q)
08: S ← S ∪ {u}
09: for each v ∈ Adj[u]:
10: ■■if d[v] > d[u] + w(u, v):
11: ■■■■d[v] ← d[u] + w(u, v)

**デフォルトの名無しさん** · 2017/01/03(火) 13:49:29.21

Correctness I:

d[v] の初期化の直後、およびLine 11の直後において、
すべての v ∈ V に対して、 d[v] ≧ δ(s, v) が
成り立つ。

証明：
d[v] の初期化の直後には、
d[s] = 0 かつすべての v ∈ S - {v} に対して、d[v] = ∞
が成り立っている。
δ(s, s) = 0 かつすべての v ∈ S に対して、 δ(s, v) ≦ ∞
であるから、d[v] の初期化の直後には、
すべての v ∈ V に対して、 d[v] ≧ δ(s, v) が確かに
成り立っている。

**デフォルトの名無しさん** · 2017/01/03(火) 13:49:56.08

Line 11の直後において、すべての v ∈ V に対して、
d[v] ≧ δ(s, v) が成り立つことを背理法により示す。

Line 11の直後において、 d[v] ≧ δ(s, v) が
成り立たないような v ∈ V が存在するとする。
v をそのような点の中で、最初の点とする。

d[v] < δ(s, v)

d[v] < δ(s, v) ≦ ∞ であるから、
ダイクストラのアルゴリズムのLine 11は少なくとも1回は
実行されているはずである。そのような最後の実行を

d[v] ← d[u] + w(u, v)

とすると、

d[u] + w(u, v) = d[v] < δ(s, v)

が成り立つ。

一方、 d[u] ≧ δ(s, u) であるから、

d[u] + w(u, v) ≧ δ(s, u) + w(u, v)
≧ δ(s, u) + δ(u, v)
≧ δ(s, v)

が成り立つが、これは矛盾である。

**デフォルトの名無しさん** · 2017/01/03(火) 13:51:21.27

Correctness Lemma:
s → … → u → v を s から v への一つの最短路とする。
d[u] = δ(s, u) であるとする。

このとき、Line10-11を実行すると、

d[v] = δ(s, v)

が成り立つ。

証明：
δ(s, v) = w(s → … → u) + w(u, v)
= δ(s, u) + w(u, v)
Correctness Iより、 d[v] ≧ δ(s, v)

(1)Line10-11の実行前に、 d[v] = δ(s, v) である場合。
Line10-11の実行後も d[v] = δ(s, v) である。

(2)Line10-11の実行前に、 d[v] > δ(s, v) である場合。
d[v] > δ(s, v) = δ(s, u) + w(u, v) = d[u] + w(u, v)
Line10-11の実行後は、 d[v] = d[u] + w(u, v) = δ(s, v)
となる。

**デフォルトの名無しさん** · 2017/01/03(火) 13:52:06.64

Correctness II:
ダイクストラのアルゴリズムが終了したとき、
すべての v ∈ V に対して、 d[v] = δ(s, v) が成り立つ。

証明：
d[v] は v が S に追加された後は、不変である。
よって、 v が S に追加されたときに、
d[v] = δ(s, v) であることを示せばよい。

背理法で示す。
v が S に追加されたときに、 d[v] ≠ δ(s, v) であるような
v ∈ V が存在すると仮定する。
u をそのような点の中で、最初に S に追加された点とする：
d[u] ≠ δ(s, u)
Correctness Iより、
d[u] > δ(s, u)

**デフォルトの名無しさん** · 2017/01/03(火) 13:52:49.71

今、 u が S に追加される直前の状況を考えることにする。
u はまだ S に追加されていないから、 u ∈ Q である。
p を s から u への一つの最短路とすると、 w(p) = δ(s, u) である。
s ∈ S, u ∈ Q であるから、 p 上の辺 (x, y) で x ∈ S, y ∈ Q となる
ような辺が存在する。そのような辺の一つを (x, y) とする。
すると、 p は以下のようになる。
p : s → … → x → y → … → u
x ∈ S であるから、 u に関する仮定より、
d[x] = δ(s, x) が成り立つ。また、明らかに、
s → … → x → y は s から y への一つの最短路であるから、
Correctness Lemmaより、 d[y] = δ(s, y) が成り立つ。
明らかに、 δ(s, y) ≦ δ(s, u) であるから、
d[y] ≦ δ(s, y)
また、Line07を見れば分かるように、
d[u] ≦ d[y] である。
よって、

d[u] ≦ δ(s, u) となるが、これは矛盾である。

**デフォルトの名無しさん** · 2017/01/03(火) 13:55:46.21

Lec 17 | MIT 6.046J / 18.410J Introduction to Algorithms (SMA 5503), Fall 2005
https://youtu.be/xhG2DyCX3uA

**デフォルトの名無しさん** · 2017/01/05(木) 09:16:14.40

アルゴリズムイントロダクションって自明なことをわざわざループ不変量を使ったりして、
証明していて、うざすぎますね。

**デフォルトの名無しさん** · 2017/01/05(木) 09:16:52.73

通常の数学の本なら自明で済ませるようなことをわざわざ証明している。

**デフォルトの名無しさん** · 2017/01/05(木) 09:57:50.61

このバカ、以前も全く同じこと言って暴れたな。

**デフォルトの名無しさん** · 2017/01/05(木) 10:02:39.43

http://hissi.org/read.php/tech/20160422/cGVtVmVaYUg.html
http://hissi.org/read.php/tech/20160612/YkttemlBQ3Y.html
こいつだ。

> って当たり前のことをループ不変とかを使って説明しているよね。はっきりいってくどい。
> ループ不変式とかいうのが出てくるけど、当たり前のことを形式的に証明しているだけで、つまらなすぎる。
> 馬鹿の一つ覚えみたいにループ不変式をつかって証明しようとしている。

これぞ「馬鹿の一つ覚え」である。

**デフォルトの名無しさん** · 2017/01/05(木) 10:44:28.31

数学とコンピュータ科学の区別がつかない厨房だろう

**デフォルトの名無しさん** · 2017/01/05(木) 11:01:45.09

クヌースの本なんかだと妙なくどさはない。

アルゴリズムイントロダクションはメリハリが全くない。
Trivialなこともそうでないことも平等に扱いすぎている。

要するに本を書くセンスがない。

**デフォルトの名無しさん** · 2017/01/05(木) 11:02:52.69

セジウィックとウエインの本のほうがずっとよい。

**デフォルトの名無しさん** · 2017/01/05(木) 11:07:44.54

日本語の本について言及しておく。
例えば、評判のよい茨木俊秀の本。

こんな薄いスカスカの本をよくも恥ずかしげもなく出版するものだとあきれる。

**デフォルトの名無しさん** · 2017/01/05(木) 11:19:31.17

アルゴリズムイントロダクションの悪口を書いたがいいところもある。

例えば、第29章線形計画法。

線形計画法に対しては、Trivialなこともそうでないことも平等に扱うという方針が
向いているように思う。

ただ、アルゴリズムの本に線形計画法を入れる理由が分からない。

整数論的アルゴリズムの章はあまりにも簡単すぎる。
高木貞治の本でも読んだ方がよい。

**デフォルトの名無しさん** · 2017/01/05(木) 11:28:06.54

結論として、ベストな本はクヌースが予定しているTAOCPの要約本ということになる。

**デフォルトの名無しさん** · 2017/01/05(木) 11:29:47.36

結論として4i7P3+nFはNG行き

**デフォルトの名無しさん** · 2017/01/05(木) 11:33:33.85

>>253
自明ほど危ういものは無いんだが

**デフォルトの名無しさん** · 2017/01/05(木) 11:40:35.14

例によって ID:4i7P3+nF が発狂しててﾜﾛﾀ

**デフォルトの名無しさん** · 2017/01/05(木) 11:44:36.30

>>263

では、なぜ、一般に、コンピュータ科学者よりも頭が良いとされる数学者が
自明で済ませることが多いのでしょうか？

もし危ういのなら頭のよい数学者は自明などと書かないはずです。

**デフォルトの名無しさん** · 2017/01/05(木) 11:52:58.57

そんな多くねえよちゃんと論文読め

**デフォルトの名無しさん** · 2017/01/05(木) 12:06:11.36

自明連発する方が馬鹿なのか

**デフォルトの名無しさん** · 2017/01/05(木) 13:09:24.25

>>265
馬鹿丸出し

**デフォルトの名無しさん** · 2017/01/05(木) 13:18:34.40

>一般に、コンピュータ科学者よりも頭が良いとされる数学者が
根拠は？
>自明で済ませることが多いのでしょうか？
数学のコンテキストの話

そもそも証明の意味もコンピュータ科学と数学では違うだろ

**デフォルトの名無しさん** · 2017/01/05(木) 14:56:52.93

なんでバカって本質に関係ないところでギャーギャー騒ぐの？

**デフォルトの名無しさん** · 2017/01/05(木) 14:58:54.44

うむ

**デフォルトの名無しさん** · 2017/01/05(木) 19:46:02.51

アルゴリズムイントロダクションについて、数学が出来る人向けの本だという人がいる。
そして、数学ができない人はセジウィック＆ウエインの本を読めという人がいる。

アルゴリズムイントロダクションが数学的な本だとは全く思わない。数学的な内容については
主に結果だけを書いている。

ただネチネチとアルゴリズムの正しさの証明が書かれているだけのこと。

クヌースの本のように、楽しい本ではない。

**デフォルトの名無しさん** · 2017/01/05(木) 20:37:39.99

>>272
>>270

**デフォルトの名無しさん** · 2017/01/05(木) 22:15:16.24

書評したければ別のところでやれ

**デフォルトの名無しさん** · 2017/01/06(金) 17:19:30.91

再帰の除去についてやり方が詳しく書いてある本を教えてください。

**デフォルトの名無しさん** · 2017/01/06(金) 17:43:03.36

プログラミングコンテストチャレンジブック第2版のp.35
Lake Counting(POJ No.2386)

の解答として、以下のプログラムはあっていますか？

void dfs(i, j, n){
if(i < 0 || i >= N || j < 0 || j >= M){
return;
}
if(field[i][j] != 'W'){
return;
}
if(visit[i][j] == true){
return;
}
visit[i][j] = true;
dfs(i-1, j-1, n+1);
dfs(i-1, j, n+1);
dfs(i-1, j+1, n+1);
dfs(i, j-1, n+1);
dfs(i, j+1, n+1);
dfs(i+1, j-1, n+1);
dfs(i+1, j, n+1);
dfs(i+1, j+1, n+1);

if(n == 0){
count++;
}
return;
}

**デフォルトの名無しさん** · 2017/01/06(金) 18:06:18.89

>>275
えっと
かぅですか？
http://nothingcosmos.blog52.fc2.com/blog-entry-170.html

**デフォルトの名無しさん** · 2017/01/06(金) 18:36:23.48

Wrong Answerになっちゃうんだけど。

**デフォルトの名無しさん** · 2017/01/06(金) 18:38:07.31

例題については正しい答えが計算されるんだけど。

**デフォルトの名無しさん** · 2017/01/06(金) 18:43:00.23

よかったね

**デフォルトの名無しさん** · 2017/01/06(金) 20:15:02.80

>>277

ソースレベルで再帰を除去する方法が知りたいんですが。

**デフォルトの名無しさん** · 2017/01/06(金) 20:22:33.43

秋葉らのプログラムでもWrong Answerになっていまします。

入出力の問題のようですね。

**デフォルトの名無しさん** · 2017/01/06(金) 20:27:59.50

入出力の問題ってやっかいですね。
出力がどうなっているかとかPOJでは調べられないんですか？

**デフォルトの名無しさん** · 2017/01/06(金) 20:41:27.59

なんなんだろう？

scanf,printfを使っていたらダメだったのが、cinとcoutにしたらOKになった。

**デフォルトの名無しさん** · 2017/01/08(日) 12:26:37.82

F(p, n, r) の計算量を教えてください。

n: 整数
p, r: 整数配列（インデックス0からn-1）

F(p, n, r):
■■if r[n] ≧ 0:
■■■■return r[n]
■■if n == 0:
■■■■q = 0
■■else:
■■■■q = -∞
■■■■for i = 1 to n:
■■■■■■q = max(q, p[i] + F(p, n-i, r))
■■r[n] = q
■■return q

**デフォルトの名無しさん** · 2017/01/08(日) 12:31:27.73

O(n^2)

**デフォルトの名無しさん** · 2017/01/08(日) 12:32:34.98

>>285
ここで解説されてる
http://echo.2ch.net/test/read.cgi/tech/1363854937/

**デフォルトの名無しさん** · 2017/01/08(日) 13:51:15.22

>>286-287

ありがとうございます。

でも解説されていませんね。

**デフォルトの名無しさん** · 2017/01/08(日) 13:57:19.77

どうやって計算量を見積もるんですか？

何を単位にするんですか？

**デフォルトの名無しさん** · 2017/01/08(日) 14:06:13.08

T(n)
=
c1 + c2 * n + T(n-1) + … + T(0)
=
c1 + c2 * n + T(n-1) + c3*(n-1)

と解けばいいんですかね？

**デフォルトの名無しさん** · 2017/01/08(日) 14:07:36.75

T(n) = c1 + c2*n + T(n-1)
T(0) = c3

この漸化式の解を求めればいいんですかね？

**デフォルトの名無しさん** · 2017/01/08(日) 14:12:15.21

T(n)
=
[T(n) - T(n-1)] + [T(n-2) - T(n-3)] + … + [T(1) - T(0)] + T(0)
=
[c1 + c2*n] + [c1 + c2*(n-1)] + … + [c1 + c2*1] + c3
=
c1*n + c2*(1/2)*n*(n+1) + c3
=
Θ(n^2)

おお、あってるっぽいですね。

**デフォルトの名無しさん** · 2017/01/08(日) 14:20:56.92

>>290-292
は我ながら明解な解答ですが、

教科書では、以下のように導出しています。
この導出がよく分からないのですが。

「以前に解かれている部分問題を解くための再帰は直ちに戻るので、Fは
各部分問題をただ1度だけ解く。この手続きはサイズが0,1,....,nの部分問題
を解く。サイズがnの部分問題を解くために、for文がn回繰り返される。したがって、
Fの再帰呼び出し全体における、このfor文の繰り返し回数は等差数列を形成し、
総繰り返し回数はΘ(n^2)となる。」

**デフォルトの名無しさん** · 2017/01/08(日) 14:26:56.39

あーあ、分かりました。

T(n)
=
c1 + c2 * n + T(n-1) + … + T(0)
=
c1 + c2 * n + T(n-1) + c3*(n-1)

このあたりのことを言っているんですね。

**デフォルトの名無しさん** · 2017/01/08(日) 14:27:53.04

馬鹿には無理

**デフォルトの名無しさん** · 2017/01/08(日) 14:28:32.97

>>289

for文の繰り返し回数＝計算量ですね。

**デフォルトの名無しさん** · 2017/01/08(日) 14:29:42.72

結局自分ですべて解決してしまいました。

**デフォルトの名無しさん** · 2017/01/08(日) 17:12:11.39

よくやった
褒美として自分専用のスレを立てる権利をやろう

**デフォルトの名無しさん** · 2017/01/08(日) 18:45:26.96

命名ID:E98VLsZは俺様

**デフォルトの名無しさん** · 2017/01/08(日) 20:55:21.87

プログラミングコンテストチャレンジブック

p.45 Best Cow Lineっていう問題の解答のプログラムって無駄がありますよね。

この本を難しいという人がいますが、そんなに難しいですかね？

**デフォルトの名無しさん** · 2017/01/08(日) 22:46:42.12

プログラミングコンテストチャレンジブック
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
最強最速アルゴリズマー養成講座

この3冊に共通していることですが、日本語が下手ですよね。

一番ひどいのが

最強最速アルゴリズマー養成講座

ですね。

**デフォルトの名無しさん** · 2017/01/08(日) 22:50:51.06

一番面白いのは、

プログラミングコンテストチャレンジブック

だと思いますけど、例えば、貪欲法でなぜうまくいくのかの証明が書いてないですね。

**デフォルトの名無しさん** · 2017/01/08(日) 22:51:13.67

ここはプログラミング問題集書評のスレなの？

**デフォルトの名無しさん** · 2017/01/09(月) 06:08:00.57

>>301
うむ
日本語下手なのはもちろん英語も下手みたいだな

**デフォルトの名無しさん** · 2017/01/09(月) 06:09:36.68

頭の使い方が下手というかそもそも頭が不自由なんだろう

**デフォルトの名無しさん** · 2017/01/09(月) 10:59:50.63

アルゴリズムイントロダクションの練習問題15.1-3の解答って以下であっていますか？

BOTTOM-UP-CUT-ROD(p, c, n)
1 r[0..n] を新しい配列とする
2 r[0] = 0
3 for j = 1 to n
4 ■■q = -∞
5 ■■for i = 1 to j-1
6 ■■■■q = maxx(q, p[i] + r[j-i] - c)
7 ■■q = max(q, p[j])
8 ■■r[j] = q
9 return r[n]

**デフォルトの名無しさん** · 2017/01/09(月) 11:02:45.57

15.1-2

反例

p[1] = 1
p[2] = 5
p[3] = 7

**デフォルトの名無しさん** · 2017/01/09(月) 13:21:16.77

F_0 = 0
F_1 = 1
F_i = F_(i-1) + F_(i-2) (i≧2)

F_n を O(n) 時間で計算する動的計画アルゴリズムを設計せよ。
対応する部分問題グラフを描け。
このグラフにはいくつの頂点と辺が存在するか？

↑はアルゴリズムイントロダクションの練習問題15.1-5なんですけど、
なんか簡単すぎるようにみえるんですけど、落とし穴があるんですかね？

なんでΘ(n)じゃなくてO(n)と書いてあるんですかね？

**デフォルトの名無しさん** · 2017/01/09(月) 13:34:48.26

配列を使わないとDPとは言えないですか？
配列いらないですよね。
でもi = 0～nに対して、F[i]が求まるという意味はありますね。

F[0] = 0
F[1] = 1
for i = 2 to n
■■F[n] = F[n-1] + F[n-2]

明らかにΘ(n)ですよね。

部分問題グラフは以下ですよね：

http://imgur.com/WUQMG8R.jpg

#V = n + 1
#E = 2*(n - 1)

ですね。

**デフォルトの名無しさん** · 2017/01/09(月) 13:37:23.94

あ、ひっかけがありましたね。
訂正します：

n > 0 のとき、

#V = n + 1
#E = 2*(n - 1)

n = 0 のとき

#V = n + 1
#E = 0

ですね。

**デフォルトの名無しさん** · 2017/01/09(月) 15:27:31.58

アルゴリズムイントロダクションに、以下の事実を1955年にRobbinsが発見したと書いてあります。

--------------------------------------------
すべての n ≧ 1 に対して

n! = sqrt(2*π*n) * (n/e)^n * exp(α_n)

と書ける。

ただし、 1/(12*n+1) < α_n < 1/(12*n)
--------------------------------------------

本当にこんな比較的簡単にみえる結果が1955年という比較的最近になって発見された
のでしょうか？

**デフォルトの名無しさん** · 2017/01/09(月) 15:37:47.20

>>308
フィボナッチだろ
√5が出て来る公式
O(1)になるかも試練が

**デフォルトの名無しさん** · 2017/01/09(月) 15:46:27.18

>>311
　　　　　　r　‐､
　　　　　　| ○ | 　　　　　　　　r‐‐､
　　　　　_,;ﾄ - ｲ、　　　　　　∧l☆│∧ 　良い子の諸君！
　　　（⌒`　　　 ⌒ヽ　　　/,､,,ﾄ.-ｲ/,､ l 　
　　　　|ヽ　 ~~⌒γ ⌒ ）　r'⌒　｀!´ `⌒）よく頭のおかしい数学者気取りのバカが
　　　│　ヽー―'^ー-'　（ ⌒γ ⌒~~　/　「誰も気付かなかった事を発見したことを発表」とほざくが
　　　│　　〉　　　 |│　　|｀ー^ｰ― r'　| 大抵それは「先人が思いついたけどあえて発表しなかった」ことだ
　　　│　/───|　|　　|/　| 　l　　ﾄ､ | 　王道が何故面白いか理解できない人間に面白い話は
　　　|　 irｰ-､ｰ　,}　|　　　 / 　　　　i　作れないぞ！
　　　| /　　　｀X´　ヽ　　 / 　入　　|

**デフォルトの名無しさん** · 2017/01/10(火) 20:16:10.65

アルゴリズムイントロダクションが難しいという人がいますけど、
この本は馬鹿丁寧に書かれていますよね。

いわゆる「書きすぎ」ですね。

「書きすぎ」れば分かりやすくなると思い込んでいますね、著者らは。

**デフォルトの名無しさん** · 2017/01/10(火) 20:19:42.26

http://hissi.org/read.php/tech/20160614/U2lCYS9zNTM.html

マジ基地だな。壊れたレコードかよ。

**デフォルトの名無しさん** · 2017/01/13(金) 21:58:42.65

プログラミング言語のパーサーってどういう仕組みで動いてるんですか？
文字列をトークンの配列に分ける
特定のパターンにマッチするトークンの部分集合をひとまとめにして新しいトークンに置き換える
再帰的に同じ事を繰り返す
こんな感じ？

**デフォルトの名無しさん** · 2017/01/13(金) 22:37:46.17

>>316
Java 再帰下降構文解析超入門
http://qiita.com/7shi/items/64261a67081d49f941e3

ビジュアル構文解析
http://www.csg.ci.i.u-tokyo.ac.jp/~ichikawa/visual_parsing.pdf

**デフォルトの名無しさん** · 2017/01/14(土) 00:10:28.40

>>317
これ考えた奴は天才だな

**デフォルトの名無しさん** · 2017/01/16(月) 17:57:37.27

Lisperか
BNF

**デフォルトの名無しさん** · 2017/01/19(木) 09:40:05.52

https://chrome.google.com/webstore/detail/%E3%81%AF%E3%81%A6%E3%81%AAng/mbgdnfmdelffjdhkdggilmphfdihnmcj?hl=ja

**デフォルトの名無しさん** · 2017/05/14(日) 13:16:07.97

類似スレ検索とかのアルゴリズムって何がいいのかな？
編集距離とか数字部分のマスキングくらいしか浮かばない
形態素解析して要素の一致率とかもあるみたいだけど、スレタイみたいな短い文字じゃ弱そう

**デフォルトの名無しさん** · 2017/05/14(日) 13:20:48.12

むしろ短くて重要な単語が多いスレタイこそ一致率うまく働きそうか
毎回評価してたら検索速度悪そうだけど

**デフォルトの名無しさん** · 2017/05/14(日) 13:56:17.84

Baka ha sinanakya
Naoranai
Fucky ou

**デフォルトの名無しさん** · 2017/05/26(金) 14:08:00.89

アルゴリズムイントロダクション

当たり前のことを定理などとよんで回りくどく証明していますね。

なんなんですか？この本。

例えば、p.506定理22.9とか。

**デフォルトの名無しさん** · 2017/05/26(金) 19:39:06.33

当たり前のことを2chで指摘して回りくどくdisっていますね。
なんなんですか？あなた。
例えば、 >>324 とか。

**デフォルトの名無しさん** · 2017/05/26(金) 21:10:54.45

>>324
当たり前が何故当たり前なのかを知るのは割と重要だが。

**デフォルトの名無しさん** · 2017/05/26(金) 22:50:21.07

>>324

しかも「証明」が長い。当たり前のことを長々と書いている。
その「証明」自体も意外性ゼロ。