データ構造,アルゴリズム,デザインパターン総合スレ 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のイミュータブルコレクションでは使われてるよ
33 KB
新着レスの表示
掲示板に戻る
全部
前100
次100
最新50
read.cgi ver.24052200
本文 スレッドタイトル 投稿者