データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4

1 ：デフォルトの名無しさん：2020/01/27(月) 22:28:35 ID:yq8WVV9K.net

【前スレ】
データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3
https://mevius.5ch.net/test/read.cgi/tech/1466315249/

【関連スレ】
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

56 ：デフォルトの名無しさん：2021/10/25(月) 11:24:00.83 ID:vmRZrQEp.net

まるちんこ

57 ：デフォルトの名無しさん：2021/10/25(月) 12:10:28.14 ID:Ex1ycVpJ.net

以下のような感じで証明できないですかね？

タスク T のポイントを p(T) で表すことにする。

貪欲法によって選ばれたタスク列を

T_1, T_2, …, T_n

とする。

S := {(S_1, S_2, …, S_k) | 1 ≦ k ≦ n, S_i は第i日に行うタスク, p(S_1 + … + S_k) > p(T_1 + … + T_k)}

S が空集合ではないとして矛盾を導く。

(S_1, S_2, …, S_l) を長さが最小の S の元とする。

p(S_1) + … + p(S_{l-1}) ≦ p(T_1) + … + p(T_{l-1})

58 ：デフォルトの名無しさん：2021/10/25(月) 16:58:37.64 ID:Ex1ycVpJ.net

Introduction to Algorithms 3rd Editionがくどすぎて読みにくい。

59 ：デフォルトの名無しさん：2021/10/26(火) 11:19:31.94 ID:CwYCZWUI.net

タスク T のポイントを p(T) で表すことにする。

貪欲法によって選ばれたタスク列を

T_1, T_2, …, T_n

とする。

S := {k | 1 ≦ k ≦ n, 第1日目から第k日目の間に得られるポイントの合計の最大値 > p(T_1) + … + p(T_k)} が空集合ではないと仮定して矛盾を導く。

k_0 := min S とおく。

第1日目から第k_0日目の間に得られるポイントの合計の最大値を達成するタスク列を

S_1, S_2, …, S_{k_0} とする。

仮定により、

p(S_1) = p(T_1)
p(S_2) = p(T_2)
…
p(S_{k_0-1}) = p(T_{k_0-1})
p(S_{k_0}) > p(T_{k_0})

が成り立つ。

60 ：デフォルトの名無しさん：2021/10/26(火) 11:33:36.58 ID:CwYCZWUI.net

このとき、長さ n のタスク列 S_1, S_2, …, S_{k_0-1}, R_{k_0}, R_{k_0+1}, …, R_{n} で

p(R_{k_0}) = p(T_{k_0})
p(R_{k_0+1}) = p(T_{k_0+1})
…
p(R_{n}) = p(T_{n})

を満たすようなものが存在することは明らかである。

このタスク列 S_1, S_2, …, S_{k_0-1}, R_{k_0}, R_{k_0+1}, …, R_{n} も貪欲法によって選ばれうるタスク列である。

ところが、タスク列 S_1, S_2, …, S_{k_0-1}, R_{k_0}, R_{k_0+1}, …, R_{n} は第k_0日において、 p(S_{k_0}) > p(T_{k_0}) = p(R_{k_0}) であるにもかかわらず、
タスク S_{k_0} を選択しないタスク列であるから、このタスク列は貪欲法によって選ばれうるタスク列ではない。

これは矛盾である。

よって、 S は空集合である。

61 ：デフォルトの名無しさん：2021/10/31(日) 19:17:33.86 ID:BY7qrcrb.net

https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_c

↓途中の段階で最終的に得られる互いの幸福度の総和をどうやって彼らは知るのでしょうか？


ただし、彼らはともに、「最終的に自分が得る幸福度の総和」から「最終的に相手が得る幸福度の総和」を引いた値を最大化するように料理を選びます。

このとき、「最終的に高橋くんが得る幸福度の総和」から「最終的に青木さんが得る幸福度の総和」を引いた値はいくつになるでしょうか？

62 ：デフォルトの名無しさん：2021/11/02(火) 10:37:08.97 ID:px0qcy1y.net

>>61
https://www.youtube.com/watch?v=SsB8VfxgZwQ

63 ：デフォルトの名無しさん：2021/11/02(火) 13:38:39.49 ID:RQoewYsN.net

『Introduction to Algorithms 3rd Edition』よりも『Algorithm Design』のほうがずっといい本だと思うのですが、どうですか？

64 ：デフォルトの名無しさん：2021/11/03(水) 18:42:32.00 ID:K+j19pQn.net

https://i.imgur.com/EqwQfdx.jpg

↑は、Dijkstraのアルゴリズムの擬似コードですが、これって間違っていますよね？

Sに付け加えられるvに対してのみd[v]を計算しています。

65 ：デフォルトの名無しさん：2021/11/03(水) 19:10:00.22 ID:p70BP33u.net

追加される時点で最短距離が決定するから問題ないと思うが。

66 ：デフォルトの名無しさん：2021/11/03(水) 19:38:24.24 ID:K+j19pQn.net

>>65
ありがとうございました。
あ、d'[v]のほうは更新され続けるんですね。
そして、最後に、Sに入れられるときに、d[v]に確定したd'[v]の値を入れているんですね。
dなんて使わずにd'だけでいいのにと思います。

67 ：デフォルトの名無しさん：2022/03/05(土) 12:18:28.50 ID:c2cv6ICZ.net

https://i.imgur.com/SLWsXcA.jpg

68 ：デフォルトの名無しさん：2022/03/05(土) 18:15:22.85 ID:2/qEYPh4.net

>>67
グロ

69 ：デフォルトの名無しさん：2022/04/09(土) 22:56:02.65 ID:NDf9sYGT.net

頭では分かってるつもりなんだけど
どうしても実際にはif , switchのオンパレードになっちゃんだよな

特に仕事だと、学術論的なことでぐずぐずハマってたら
なにやってんだってはなしになることが多い

70 ：デフォルトの名無しさん：2022/08/31(水) 20:45:30.79 ID:CIcCYvEQ.net

『アルゴリズム実技検定公式テキスト』という本に以下の最長パスの問題の出題と解答が書いてあります．

https://atcoder.jp/contests/dp/tasks/dp_g

解説を読むと，この問題を解くのに，トポロジカルソートが重要だと書いてあります．

71 ：デフォルトの名無しさん：2022/08/31(水) 20:52:44.34 ID:CIcCYvEQ.net

解答は以下のような感じです：

length(v)を点vからの最長パスの長さとします．

v → w_1
v → w_2
…
v → w_n

という辺があるとき，length(v) = max{length(w_1), …, length(w_n)}
とメモ化再帰により計算する．（深さ優先探索を使う．）

この解答のどこでトポロジカルソートの考えが使われているのかが分かりません．

72 ：デフォルトの名無しさん：2022/08/31(水) 20:55:47.47 ID:CIcCYvEQ.net

入次数が0の点達からメモ化再帰（深さ優先探索）を行っています．

73 ：デフォルトの名無しさん：2022/08/31(水) 20:58:25.24 ID:CIcCYvEQ.net

https://ideone.com/LvMx0h

例えば，上のプログラムのような感じです．

74 ：デフォルトの名無しさん：2022/09/01(木) 09:35:46.60 ID:NAQLmVKw.net

入字数0の点が最長パスの始点候補だから、トポロジカルソートしたら始点から終点までの経路上の辺の長さをを足し合わせていけばいい

75 ：デフォルトの名無しさん：2022/09/04(日) 06:43:45.43 ID:x0sSmgMe.net

でもトポロジカルソートしていないですよね．プログラムを見ると．

76 ：デフォルトの名無しさん：2022/09/18(日) 14:40:45.95 ID:suxGffYa.net

C++の連結リスト(list)の削除に必要な計算量がO(1)であると大槻の本に書いてあるのですが、
削除したい要素を探すのにO(N)必要だと思います。

これって単に、指定した位置の要素を削除するという操作だからO(1)ということですか？

77 ：デフォルトの名無しさん：2022/09/18(日) 15:28:50.46 ID:69Jy4am9.net

知らね。前後の文脈含めてなんて書いてあるの？

78 ：デフォルトの名無しさん：2022/09/19(月) 12:07:14.08 ID:yWkM0kBX.net

>>76
そう
指定した位置というか指定したノードだけど

79 ：デフォルトの名無しさん：2022/09/20(火) 01:12:54.08 ID:zbB+YFPz.net

>>75
トポロジカルソートが重要かはよくわからんけど
状態空間も遷移の考えもほとんど同じじゃん

80 ：デフォルトの名無しさん：2022/09/26(月) 15:08:47.03 ID:cqAm7B1L.net

比較に基づくソートの最悪の入力に対する実行時間の下限がΩ(n * log(n))であることの証明が分かりません。

81 ：デフォルトの名無しさん：2022/09/26(月) 15:13:01.77 ID:cqAm7B1L.net

決定木で説明しますが、その説明が分かりません。

82 ：デフォルトの名無しさん：2022/09/26(月) 15:53:07.65 ID:Dh3HDIpo.net

そうか

83 ：デフォルトの名無しさん：2022/09/26(月) 16:07:33.81 ID:cqAm7B1L.net

比較に基づく任意のソートアルゴリズムに対して、その決定木って作れますか？

84 ：デフォルトの名無しさん：2022/09/26(月) 18:12:30.08 ID:cqAm7B1L.net

決定木の各ノードである2つの要素のペアの大小関係が決まりますが、その情報を利用しない場合にはどうなりますか？

85 ：デフォルトの名無しさん：2022/09/26(月) 20:52:32.58 ID:Sp/QOOjd.net

英語だけどイラスト付きで分かりやすく書いてある
https://medium.com/enjoy-algorithm/lower-bound-of-comparison-sorting-c3e2225e3419

86 ：デフォルトの名無しさん：2022/09/26(月) 21:50:30.08 ID:cqAm7B1L.net

>>85
ありがとうございました。

87 ：デフォルトの名無しさん：2022/10/17(月) 16:05:05.43 ID:BBjAlznw.net

命題2.4：
始点 s から各頂点へ最短路が存在すると仮定する。このとき、 s を根とする
有向全域木 T が存在して、 T における s から頂点 v への有向路は、 s から
頂点 v への最短路となっている。

証明：
始点 s から各頂点 v への最短路（の枝集合）を P_v とし、 T = ∪_{v ∈ V} P_v とおく。
定理2.3と命題2.2より、 P_v は単純有向路としてよい。 T の要素数がちょうど n - 1 であれば、
これは有向全域木であり、各頂点への最短路を含む。一方、 T の要素数が n 以上の場合は、
以下の手順で最短路を繰り返し修正することにより、所望の有向全域木を求めることができる。
T の要素数が n 以上と仮定する。このとき、ある頂点 v_* ∈ V - {s} が存在して、 T の中には
v_* に向かう枝が2つ以上ある。
…

v_* に向かう枝が2つ以上あることの証明ですが、どのような証明が典型的なものと考えられますか？

証明：
T を無向グラフと考えたとき、 T は連結であり、 #T = n だから無向閉路が存在する。
T の作り方から s に向かう枝は存在しないから、 s はこの無向閉路上にはない。
仮に、上の v_* が存在しないと仮定する。
v を 上の無向閉路上の任意の頂点とする。 T の定義により、 T の中には v へ向かう枝が存在するが、
仮定により、そのような枝は唯一つしか存在しない。ゆえに、この無向閉路を有向グラフとして考えた
とき、有向閉路である。

T の作り方から、 s から v への有向路が存在する。
ところが、 s は上の有向閉路には含まれないからこれは矛盾である。

88 ：デフォルトの名無しさん：2022/10/17(月) 17:01:23.13 ID:BBjAlznw.net

もっと分かりやすく書き直しました：

命題2.4：
始点 s から各頂点へ最短路が存在すると仮定する。このとき、 s を根とする
有向全域木 T が存在して、 T における s から頂点 v への有向路は、 s から
頂点 v への最短路となっている。

証明：
始点 s から各頂点 v への最短路（の枝集合）を P_v とし、 T = ∪_{v ∈ V} P_v とおく。
定理2.3と命題2.2より、 P_v は単純有向路としてよい。 T の要素数がちょうど n - 1 であれば、
これは有向全域木であり、各頂点への最短路を含む。一方、 T の要素数が n 以上の場合は、
以下の手順で最短路を繰り返し修正することにより、所望の有向全域木を求めることができる。
T の要素数が n 以上と仮定する。このとき、ある頂点 v_* ∈ V - {s} が存在して、 T の中には
v_* に向かう枝が2つ以上ある。
…

v_* に向かう枝が2つ以上あることの証明ですが、どのような証明が典型的なものと考えられますか？

証明：
T を無向グラフと考えたとき、 T は連結であり、 #T = n だから無向閉路が存在する。
仮に、上の v_* が存在しないと仮定する。
v を上の無向閉路上の任意の頂点とする。 T の定義により、 T の中には v へ向かう枝が存在するが、
仮定により、そのような枝は唯一つしか存在しない。ゆえに、この無向閉路を有向グラフとして考えた
とき、有向閉路である。この有向閉路を C とする。 T の作り方から s に向かう枝は存在しないから、
s は C 上にはない。

T の作り方から、 s から v への有向路 P が存在する。
s は C 上にはなく、 v は C 上にあることに注意する。
P 上の頂点で最初に C 上の頂点ともなる頂点を w とする。
w は s とは異なるから、 P 上には、 w の直前の頂点 u が存在する。u は w についての仮定から、
C 上の頂点ではない。 w は C 上の頂点であるから、 w へ向かう C 上の枝が存在する。
以上から、 w へ向かう少なくとも2つ以上の枝が存在することになる。 これは矛盾である。

89 ：デフォルトの名無しさん：2022/11/12(土) 19:54:31.16 ID:xCg5uX6U.net

アルゴリズムの学習で、ツリー構造のデータ詮索とか学習してるのだが。
一般的にデータってリレーショナルデータベースとか、
プログラムで利用するなら配列とかでしょ。
ツリー構造のデータってそんなあるの？

90 ：デフォルトの名無しさん：2022/11/12(土) 20:16:08.76 ID:WvbeP05G.net

ファイルシステムとかHTMLとかいくらでもある

91 ：デフォルトの名無しさん：2022/11/12(土) 21:18:58.24 ID:EqzcHwUy.net

XML

92 ：デフォルトの名無しさん：2022/11/12(土) 23:06:22.44 ID:Y42oI462.net

パイ毛　パイ毛　パイ毛〜

93 ：デフォルトの名無しさん：2022/11/12(土) 23:15:39.39 ID:mqwguCdy.net

データ詮索ワロタ

94 ：デフォルトの名無しさん：2023/04/30(日) 19:23:01.90 ID:dQsz62eN.net

こんなスレが埋もれてるなんて信じられん
お前らもっとアルゴリズム刻めよ

95 ：デフォルトの名無しさん：2023/05/03(水) 01:15:28.00 ID:ZUlTYoGm.net

ニューラルネットワークでデータを詮索してみるか

96 ：デフォルトの名無しさん：2023/05/27(土) 13:47:32.62 ID:dQE1+1Te.net

デザインパターンは廃れたよな

97 ：デフォルトの名無しさん：2023/05/28(日) 16:34:40.65 ID:pV4wEcmO.net

エディタとかDBとか巨大外部リソースとのやりとりに関してのアルゴリズムはまだまだ再考の余地があると思う

98 ：デフォルトの名無しさん：2023/06/28(水) 16:50:44.07 ID:BVdlIcNn.net

漠∞！！！！
戸∞！！！！！
廷∞！！！！！！
与∞！！！！！！！
合∞！！！！！！！！
山∞！！！！！！！！！
α∞！！！！！！！！
野∞！！！！！！！！

99 ：デフォルトの名無しさん：2023/10/13(金) 19:28:46.40 ID:ANHPZuQm.net

では教育してやろう。”本当のオタク”の萌えに対する論理戦というものを……

100 ：デフォルトの名無しさん：2023/10/29(日) 09:40:11.61 ID:nlAlD3dC.net

マージソートのmidの導出ですが
mid=(left+right+1)//2
ではなく
mid=(left+right)//2
なのはなぜでしょうか

この1行で正しくソートできないのです

pythonで勉強中の超初心者です
よろしくお願いします

101 ：デフォルトの名無しさん：2023/10/29(日) 09:40:36.19 ID:nlAlD3dC.net

マージソートのmidの導出ですが
mid=(left+right+1)//2
ではなく
mid=(left+right)//2
なのはなぜでしょうか

この1行で正しくソートできないのです

pythonで勉強中の超初心者です
よろしくお願いします

102 ：デフォルトの名無しさん：2023/12/23(土) 10:34:22.20 ID:9iMk1h5v.net

プログラムを最近勉強し始めたのですが二分探索木や赤黒木みたいなデータ構造って現場でも実際に使われているのですか？

103 ：デフォルトの名無しさん：2023/12/23(土) 13:21:36.77 ID:ppz7uSBz.net

必要になったことはないなあ、連想配列はハッシュテーブルの方が速いし
ソートが必要ならリストを使う

104 ：デフォルトの名無しさん：2023/12/23(土) 16:14:31.33 ID:mgbjvOvz.net

やっぱり使わないですよねぇ
今朝からAVL木練習してるんだけど、
やはり回転とかの作業分だけハッシュテーブルに比べると圧倒的に遅いんだよなぁ
当たり前だけど。

105 ：デフォルトの名無しさん：2023/12/23(土) 16:22:46.85 ID:ppz7uSBz.net

永続化データ構造は作りやすいから.NETのイミュータブルコレクションでは使われてるよ