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

データ構造,アルゴリ� ..

85:デフォルトの名無しさん
22/09/26 20:52:32.58 Sp/QOOjd.net
英語だけどイラスト付きで分かりやすく書いてある
URLﾘﾝｸ(medium.com)

86:デフォルトの名無しさん
22/09/26 21:50:30.08 cqAm7B1L.net
>>85
ありがとうございました。

87:デフォルトの名無しさん
22/10/17 16:05:05.43 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:デフォルトの名無しさん
22/10/17 17:01:23.13 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:デフォルトの名無しさん
22/11/12 19:54:31.16 xCg5uX6U.net
アルゴリズムの学習で、ツリー構造のデータ詮索とか学習してるのだが。
一般的にデータってリレーショナルデータベースとか、
プログラムで利用するなら配列とかでしょ。
ツリー構造のデータってそんなあるの？

90:デフォルトの名無しさん
22/11/12 20:16:08.76 WvbeP05G.net
ファイルシステムとかHTMLとかいくらでもある

91:デフォルトの名無しさん
22/11/12 21:18:58.24 EqzcHwUy.net
XML

92:デフォルトの名無しさん
22/11/12 23:06:22.44 Y42oI462.net
パイ毛　パイ毛　パイ毛～

93:デフォルトの名無しさん
22/11/12 23:15:39.39 mqwguCdy.net
データ詮索ワロタ

94:デフォルトの名無しさん
23/04/30 19:23:01.90 dQsz62eN.net
こんなスレが埋もれてるなんて信じられん
お前らもっとアルゴリズム刻めよ

95:デフォルトの名無しさん
23/05/03 01:15:28.00 ZUlTYoGm.net
ニューラルネットワークでデータを詮索してみるか

96:デフォルトの名無しさん
23/05/27 13:47:32.62 dQE1+1Te.net
デザインパターンは廃れたよな

97:デフォルトの名無しさん
23/05/28 16:34:40.65 pV4wEcmO.net
エディタとかDBとか巨大外部リソースとのやりとりに関してのアルゴリズムはまだまだ再考の余地があると思う

98:デフォルトの名無しさん
23/06/28 16:50:44.07 BVdlIcNn.net
漠∞！！！！
戸∞！！！！！
廷∞！！！！！！
与∞！！！！！！！
合∞！！！！！！！！
山∞！！！！！！！！！
α∞！！！！！！！！
野∞！！！！！！！！

99:デフォルトの名無しさん
23/10/13 19:28:46.40 ANHPZuQm.net
では教育してやろう。”本当のオタク”の萌えに対する論理戦というものを……

100:デフォルトの名無しさん
23/10/29 09:40:11.61 nlAlD3dC.net
マージソートのmidの導出ですが
mid=(left+right+1)//2
ではなく
mid=(left+right)//2
なのはなぜでしょうか

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

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

101:デフォルトの名無しさん
23/10/29 09:40:36.19 nlAlD3dC.net
マージソートのmidの導出ですが
mid=(left+right+1)//2
ではなく
mid=(left+right)//2
なのはなぜでしょうか

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

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

102:デフォルトの名無しさん
23/12/23 10:34:22.20 9iMk1h5v.net
プログラムを最近勉強し始めたのですが二分探索木や赤黒木みたいなデータ構造って現場でも実際に使われているのですか？

103:デフォルトの名無しさん
23/12/23 13:21:36.77 ppz7uSBz.net
必要になったことはないなあ、連想配列はハッシュテーブルの方が速いし
ソートが必要ならリストを使う

104:デフォルトの名無しさん
23/12/23 16:14:31.33 mgbjvOvz.net
やっぱり使わないですよねぇ
今朝からAVL木練習してるんだけど、
やはり回転とかの作業分だけハッシュテーブルに比べると圧倒的に遅いんだよなぁ
当たり前だけど。

105:デフォルトの名無しさん
23/12/23 16:22:46.85 ppz7uSBz.net
永続化データ構造は作りやすいから.NETのイミュータブルコレクションでは使われてるよ