Proof - Intro to Algorithms Udacity English Japanese

Proof - Intro to AlgorithmsYouTube↗ IA↗(long shot)
Education 1.1K views 2 likes 4 dislikes 23 Feb 2015

Udacity 651K subscribers United States YouTube↗

Click to Play Video

So the first thing to observe is that no non-tree edge can be a bridge.

次にお話しするのは非ツリーエッジがブリッジになり得るということです

They have to be the green edges not the red edges, and why is that?

しかしブリッジの条件は緑のエッジのはずです

Well, the red edges are the ones that get added for a node that had already been reached by some other path.

赤のエッジは他のパスですでに到達できるノードをつないでいます

So the red edges can't be bridge edges it's because deleting the red edge--the node

なので赤のエッジはブリッジにはなり得ませんもし2点を結ぶ

from both sides of these were reachable from the beginning some other way.

赤のエッジを消しても他のパスで到達できるからです

Next, we can test whether or not a given node is in the subtree rooted at--at some node W,

次に与えられたノードがwのサブツリーに含まれるかどうかを調べてみましょう

pretty simply using the numbers that we've already calculated.

方法は簡単ですでに計算した数を使います

Post order of W, the number of descendants of W, and the high and low values and why is that.

wの後行順、wの子孫数、最大値、最小値ですなぜでしょうか?

So when we go to do the post ordering at W, we go it down here,

wを後行順にたどるには下に行って

we number somebody, then we number everybody, then we number W itself.

すべてに番号を振ってからwに番号を振ります

The post order number of everyone in here has to be less than the post order of the value of W

すべての番号はwの後行順の値より小さくなければなりません

but the total number of numbers in these set they're all--they're all continuous, they're all in order

しかしすべての番号は連続しているので番号の合計数は

and the total of numbers--numbers in this set is blue is the number of descendants.

子孫の数である青になります

So black minus blue is one smaller than the smallest number in this collection.

そして黒と青の差はサブツリーの中の最小数より1小さい数です

That property is kind of obvious, perhaps, but we were almost there.

この性質は自明だと思いますが続けましょう

The only way that this edge is not a bridge is if there's some non tree edge

このエッジがブリッジにならない唯一の場合は

that takes us out somehow and connects to something else in the tree.

ある非ツリーエッジがこのサブツリー外のノードとつながっている場合です

Now what would happen to the H value or the L value if we had one of these edges.

そういったエッジがあった時最大値や最小値はどうなるでしょうか

Remember the H value and the L value were defined specifically to be well, you follow a bunch of green edges and then you follow one red edge.

最大値と最小値の定義は多くの緑のエッジと1本の赤のエッジでなされます

Well, if a red edge takes us to in a sort of in the left of this tree, then the in order value is going to be

もし赤のエッジで左のツリーに行くと中間順の値は

outside of this range and it pretty good will be too small and that we'll tell us

このレンジの外になるのでかなり小さくなります

that we've link to something outside to the left.

それによって左のツリーとつながっていることが分かります

If we link to something outside to the right then the H number is going to be bigger than

右のツリーとつながっている場合は最大値が

the in order value of W and similarly if we hop up to high that same thing happens it's because

wの中間順の値より大きくなります最大値が上がっても同じことが起きます

that the blobs in here, the nodes in this blob all have exactly the values in here.

なぜならこのツリー内のノードの値は厳密だからです

Anything that connects outside of their is going to

それ以外のノードとつながっている場合は

cause either the H value or the L value to pop outside of this range.

最大値や最小値がこのレンジを超えるのです

So with those values in hand, we have a very easy test to see whether or not

そのためこの値を見れば赤のエッジがグラフを

there's some red edge that will actually connect up the graph in a way

つないでいるかどうかを簡単にテストできます

that this is no longer a bridge and that's all we need to do.

この場合これはブリッジではなくなります

Now in the homework, I'm going to ask you to actually carry out this test on a real graph.

では宿題としてこのテストを実際にコード化して行ってみてください

Actually code it up and it's not terrible but it is a little bit tricky.

難しくはないと思いますが少し複雑です

You have to be very careful to figure out how to compute the post order values

慎重に後行順の値、子孫数、最大値最小値を計算しながらも

the number of descendants H and L without taking a lot of running time in the graph.

あまり実行時間がかからないように気をつけてください

Really needs to be able to do it essentially with one or two sweeps through the set of all the nodes and edges in the graphs.

グラフを1～2回往復する程度でできるようになりましょう

But you can do it--I have confidence.

皆さんなら大丈夫です

Similar videos:

Top K Code - Intro to Algorithms
Udacity
722 views 2 likes 0 dislikes 19 Jul 2012100% match

Electrified Wolverine Claws: HOW DEADLY ARE THEY?
Hacksmith Industries
10.6M views 132.8K likes 3.8K dislikes 02 Mar 201764% match

Antes de insultar a BTS, por favor mira esto | REACCIÓN
Boladeando
31.7K views 3.7K likes 21 dislikes 15 Nov 202063% match

RECICLAR LOS ENVASES DE TUBO. Recycle the packaging of tube.
LOS TRUCOS DE JULIETA.
437.4K views 0 likes 0 dislikes 12 Dec 201362% match

DIY Como UNIR malla ROMBO ( metal desplegado ) #herreriasinsecretos
Leo Besson
7K views 357 likes 8 dislikes 26 Sep 202062% match

실버버튼 언박싱하는데 섹시한 옷을 입고 나타났더니 남친반응이...ㅋㅋㅋㅋ
Mini and Hwany M.H. Couple
25.6K views 691 likes 12 dislikes 26 Oct 202061% match

Cactus Cutting PROPAGATION! - Try this at home!
Expedition Homestead
156K views 1K likes 127 dislikes 12 Mar 201761% match

Chinese soldiers stole important information at enemy positions, but were found when leaving
ShengshiDrama
1.7K views 18 likes 2 dislikes 09 Apr 202061% match

Soldadora MIG con ARGON Funciona ?? #herreriasinsecretos
Leo Besson
1.1K views 106 likes 3 dislikes 25 Nov 202061% match

0 views 0 likes 0 dislikes 04 Jun 202661% match

0 views 0 likes 0 dislikes 04 Jun 202661% match

FOGONERO o Asador !! , súper completo !! #locosxelasado
Leo Besson
15.1K views 336 likes 5 dislikes 23 Dec 202061% match

Solo Bushcraft camping, how to build a viking hut - Search and cook wild food from the jungle Ep.3

157K views 2.5K likes 105 dislikes 01 Feb 202161% match

Why Mechanics Charge So Much to Fix Your Car
Scotty Kilmer
423K views 8.4K likes 313 dislikes 18 Jul 201761% match

Trying viral gymnastics TIKTOKS | Paula Murillo

2K views 0 likes 0 dislikes 19 Jun 202061% match

Нурминский Валим / Mexican Reaction To Russian Rap
Tiny M.A.
11.4K views 219 likes 29 dislikes 21 Sep 201961% match

Cleaning and maintenance of a pond for bettas
Don Miguel Betta
143.2K views 1.9K likes 69 dislikes 28 Jan 201761% match

Billie Eilish, ROSALÍA - Lo Vas A Olvidar (Official Music Video) | REACTION 🇪🇸ES | Allan Cardoso
Allan Cardoso
10.5K views 499 likes 21 dislikes 21 Jan 202161% match

0 views 0 likes -1 dislikes 04 Jun 202661% match

Kde všade sme sa dostali nepozorovane ?? Nová nemocnica - Košice
DYG MORE
24.5K views 786 likes 27 dislikes 06 Oct 202061% match

How to Use Any Camera For Filmmaking
DSLRguide
667.6K views 13.7K likes 315 dislikes 30 May 201561% match

Comment perdre rapidement la graisse du ventre en utilisant de l'ail - Remèdes naturels
Rose Moony
214K views 0 likes 0 dislikes 28 Apr 201961% match

Construction container - Soudure partie 2 - Renforcement de la structure - J + 6
Kerworkshop
18.6K views 542 likes 2 dislikes 13 Nov 202061% match

20 LB of Slime - DIY Giant Slime
CrazyRussianHacker
1.8M views 69.4K likes 2K dislikes 23 Feb 201761% match

EX101x - 6.2 - Can we fix it
DelftX Data Analysis to the MAX
8.2K views 0 likes 0 dislikes 11 May 201560% match

胖哥车坏了心情很郁闷，小杜晚餐炒河粉，胖哥彤彤都吃嗨了~【小杜生活日】
Fat brother has Du
21.9K views 575 likes 12 dislikes 29 Oct 202060% match

THE DIVISION [# 50] (subtitle) GLOBAL EVENT 5 "BLACKOUT" IS EXTENDED!
blue
1.2K views 29 likes 1 dislikes 27 Apr 201860% match

二哥家帶的臘豬蹄，再燉個豬臉肉，小雨和金老師吃得嘴角流油！【市民朱小雨】
Citizen Zhu Xiaoyu
46.9K views 1.2K likes 39 dislikes 05 Jan 202160% match

iPhone 11 Pro Cambiar Tapa de Cristal
MovilOne Mobile repair
17.1K views 290 likes -1 dislikes 21 Oct 202060% match

Extreme Cleaning DIRTY WHEELS *Satisfying Car Detailing*
Stauffer Garage
219.9K views 5.7K likes 552 dislikes 03 May 202060% match

Settings Privacy About Contact Donate