1
00:00:00,000 --> 00:00:10,900

2
00:00:10,900 --> 00:00:15,860
>> SPEAKER 1：すべての権利は​​、これがあります
CS50これを週に5回の終わりです。

3
00:00:15,860 --> 00:00:19,220
そしてその最後の時間を思い出すたち
手の込んだデータを見始めました

4
00:00:19,220 --> 00:00:22,310
解決するために開始した構造
導入を開始した問題、

5
00:00:22,310 --> 00:00:25,640
新たな問題が、このための鍵
スレッドの一種であることが確認された私たち

6
00:00:25,640 --> 00:00:27,940
ノードからノードに行うようになりました。

7
00:00:27,940 --> 00:00:30,085
だから、もちろん、これはあります
単独でリンクされたリスト。

8
00:00:30,085 --> 00:00:31,960
そして単独で連結され、
私が意味するものはそこです

9
00:00:31,960 --> 00:00:33,380
これらのノードとの間に通します。

10
00:00:33,380 --> 00:00:35,890
判明あなたは手の込んだ行うことができます
二重リンクリストのようなもの

11
00:00:35,890 --> 00:00:38,470
あなたは、矢印を持っていることによって
、両方の方向に向かっています

12
00:00:38,470 --> 00:00:40,320
一定の効率化を支援することができます。

13
00:00:40,320 --> 00:00:42,000
しかし、これは問題を解決し？

14
00:00:42,000 --> 00:00:43,500
これは何の問題を解決しましたか？

15
00:00:43,500 --> 00:00:46,620
なぜ我々は月曜日に気にしたのですか？

16
00:00:46,620 --> 00:00:49,820
なぜ、理論的には、我々は月曜日に気にしたのですか？

17
00:00:49,820 --> 00:00:50,630
それは何をするのか？

18
00:00:50,630 --> 00:00:51,950
>> 観客：我々は、動的にサイズを変更することができます。

19
00:00:51,950 --> 00:00:53,740
>> SPEAKER 1：OK、私たちすることができますので、
動的にサイズを変更します。

20
00:00:53,740 --> 00:00:54,710
さてあなたの両方を行います。

21
00:00:54,710 --> 00:00:57,560
だから、これを動的にサイズを変更することができます
データ構造、配列、一方、

22
00:00:57,560 --> 00:01:00,760
リコール、あなたが知っている必要があります
あなたが望むどのくらいのスペース先験的

23
00:01:00,760 --> 00:01:03,870
あなたがもう少し必要な場合は、
スペースは、あなたは運のうち、一種のです。

24
00:01:03,870 --> 00:01:05,560
あなたは、全体の新しい配列を作成する必要があります。

25
00:01:05,560 --> 00:01:07,893
あなたはあなたのすべてを移動する必要があります
一方から他方へのデータ、

26
00:01:07,893 --> 00:01:10,600
最終的には古い配列を解放
することができますし、次に進みます。

27
00:01:10,600 --> 00:01:13,891
どれだけの非常に高価な感じ、非常に
非効率的で、実際には、とすることができます。

28
00:01:13,891 --> 00:01:14,890
しかし、これはすべての良いではありません。

29
00:01:14,890 --> 00:01:18,180
私たちは一つであったどのような価格を支払います
より明白な価格の我々

30
00:01:18,180 --> 00:01:20,550
リンクリストを使用して支払いますか？

31
00:01:20,550 --> 00:01:22,825
>> 観客：我々は、使用する必要があります
それぞれのダブルスペース。

32
00:01:22,825 --> 00:01:25,200
SPEAKER 1：うん、私たちが必要とします
少なくとも2倍くらいのスペースとして。

33
00:01:25,200 --> 00:01:27,700
実際に、私はこの絵の実現しました
少しでも誤解を招きます、

34
00:01:27,700 --> 00:01:32,200
現代の多くでCS50のIDEのため
コンピュータ、ポインタまたはアドレス

35
00:01:32,200 --> 00:01:33,700
実際には4バイトではありません。

36
00:01:33,700 --> 00:01:36,090
それは非常に多くの場合、これらのです
日8バイト、どの

37
00:01:36,090 --> 00:01:38,530
ほとんど底を意味
実際にそこに長方形

38
00:01:38,530 --> 00:01:40,900
二倍の一種であります
私が描いたものとして大きな、

39
00:01:40,900 --> 00:01:44,409
これはあなたが3倍を使用していることを意味
我々はそうでないかもしれませんが、多くのスペース。

40
00:01:44,409 --> 00:01:46,700
今、同時に、私たちはしています
まだバイトを話し、右？

41
00:01:46,700 --> 00:01:49,140
私たちは必ずしも話していません
MBまたはGB、

42
00:01:49,140 --> 00:01:51,000
これらのデータ構造は大きくなる場合を除きます。

43
00:01:51,000 --> 00:01:54,510
>> だから、今日、私たちは検討を開始
我々は、データを探索する方法

44
00:01:54,510 --> 00:01:57,310
より効率的であれば
実際のデータが大きくなります。

45
00:01:57,310 --> 00:02:00,360
しかし、ここでは、正規化してみましょう
最初の操作

46
00:02:00,360 --> 00:02:02,460
あなたはこれらの上で行うことができます
データ構造の種類。

47
00:02:02,460 --> 00:02:04,790
だから、リンクのようなもの
リストは一般的にサポートしています

48
00:02:04,790 --> 00:02:07,514
削除などの操作、
挿入して、検索します。

49
00:02:07,514 --> 00:02:08,639
そして私は何を意味するのですか？

50
00:02:08,639 --> 00:02:11,222
それはちょうど、通常、そのことを意味します
人々がリンクされたリストを使用している場合は、

51
00:02:11,222 --> 00:02:14,287
これらまたは他の誰かが実施しています
削除、挿入等の機能、

52
00:02:14,287 --> 00:02:16,120
そして、することができますので、検索
実際に何かをします

53
00:02:16,120 --> 00:02:18,030
データ構造と便利。

54
00:02:18,030 --> 00:02:20,760
それでは、簡単に見てみましょう
我々が実装する方法で

55
00:02:20,760 --> 00:02:24,530
次のようにリンクされたリストのためのいくつかのコードです。

56
00:02:24,530 --> 00:02:27,885
>> だから、これはいくつかのCコードで、
いなくても完全なプログラム

57
00:02:27,885 --> 00:02:29,260
私は本当にすぐにホイップこと。

58
00:02:29,260 --> 00:02:32,300
これは、ディストリビューションでは、オンラインではありません
コー​​ド、それは実際には実行されませんので。

59
00:02:32,300 --> 00:02:33,790
しかし、私はちょうどしたことに注意しましょう
コメントは言ったと、

60
00:02:33,790 --> 00:02:36,130
ドットドットドット、何かあります
そこに、そこに、何かをドットドットドット。

61
00:02:36,130 --> 00:02:38,410
そして、ちょうど見てみましょう
ジューシーな部分が何でありますか。

62
00:02:38,410 --> 00:02:40,790
だから、ライン3に、
これが今であることを思い出します

63
00:02:40,790 --> 00:02:45,960
我々は最後のノードを宣言提案します
時間、これらの長方形オブジェクトの一つ。

64
00:02:45,960 --> 00:02:48,790
それは、我々はNと呼ぶことにしますint型を持っています
しかし、我々は何もそれを呼び出すことができ、

65
00:02:48,790 --> 00:02:51,920
し、次の構造体と呼ばれるノードの星。

66
00:02:51,920 --> 00:02:55,520
そして、ちょうど明確にするために、その二
行は、行6の上に、それは何ですか？

67
00:02:55,520 --> 00:02:57,930
それが私たちのために何をしているのですか？

68
00:02:57,930 --> 00:03:01,044
それは確かに多く見えるので
いつもの変数よりも不可解。

69
00:03:01,044 --> 00:03:02,740
>> 観客：それは1つの上に移動することができます。

70
00:03:02,740 --> 00:03:04,650
>> SPEAKER 1：それは1つの上に移動することができます。

71
00:03:04,650 --> 00:03:08,580
そして、より正確には
それは、アドレスを格納します

72
00:03:08,580 --> 00:03:11,582
であることを意味していたノードの
意味的に横に、右か？

73
00:03:11,582 --> 00:03:13,540
だから、ことはないだろう
必ずしも何かを移動します。

74
00:03:13,540 --> 00:03:15,290
それだけに起こっています
値を格納

75
00:03:15,290 --> 00:03:17,170
アドレスになるだろう
いくつかの他のノードの、

76
00:03:17,170 --> 00:03:20,810
私たちは構造体を言った理由です
ノードスター、表す星

77
00:03:20,810 --> 00:03:22,370
ポインタまたはアドレス。

78
00:03:22,370 --> 00:03:26,390
[OK]を、今、あなたは我々が持っていると仮定した場合
私たちに利用できるこのN、としましょう

79
00:03:26,390 --> 00:03:29,490
他の誰かが持っていることを前提としてい
整数の全体の束を挿入

80
00:03:29,490 --> 00:03:30,400
リンクされたリストに。

81
00:03:30,400 --> 00:03:35,640
そして、リンクされたリストであること
いくつかの点で指さ

82
00:03:35,640 --> 00:03:39,040
だ変数と呼ばれるリスト
パラメータとして、ここに渡され、

83
00:03:39,040 --> 00:03:43,120
どのように私は行行くのです
14検索を実行しますか？

84
00:03:43,120 --> 00:03:45,990
言い換えれば、私は実装していた場合
その目的は生活の中で機能

85
00:03:45,990 --> 00:03:48,889
その後、int型とを取ることです
リンクリストの始まり、

86
00:03:48,889 --> 00:03:50,430
それは、リンクされたリストへのポインタです。

87
00:03:50,430 --> 00:03:52,992
最初と同じように、私はダビデを誰だと思います
私たちボランティアは、月曜日にありました

88
00:03:52,992 --> 00:03:54,700
彼が指さしました
全体のリンクリスト、

89
00:03:54,700 --> 00:03:57,820
私たちが渡しているかのように、です
ここに私たちの引数としてデビッド。

90
00:03:57,820 --> 00:03:59,990
どのように我々は、このリストを横断については行くのですか？

91
00:03:59,990 --> 00:04:04,640
まあ、それは判明しているにもかかわらず
ポインタは、私たちに今、比較的新しいです

92
00:04:04,640 --> 00:04:07,010
我々は比較的これを行うことができます
素直に。

93
00:04:07,010 --> 00:04:09,500
>> 私は先に行くつもりだと
一時的な変数を宣言しています

94
00:04:09,500 --> 00:04:12,364
慣例によりちょうど起こっています
ポインタ、またはPTRと呼ばれます、

95
00:04:12,364 --> 00:04:14,030
しかし、あなたが欲しいものを呼び出すことができます。

96
00:04:14,030 --> 00:04:16,470
そして、私は初期化す​​るつもりです
そのリストの先頭に。

97
00:04:16,470 --> 00:04:20,050
だから、一種の考えることができ
私と先生先日、

98
00:04:20,050 --> 00:04:23,580
誰かを指すの種類
ボランティアとしての人間の間で。

99
00:04:23,580 --> 00:04:26,470
だから私は、だ一時変数です
ちょうど同じことを指し

100
00:04:26,470 --> 00:04:31,390
私たちは偶然という名前のこと
ボランティアのDavidも指摘されました。

101
00:04:31,390 --> 00:04:35,440
今ポインタがある間
リコールので、nullではありません

102
00:04:35,440 --> 00:04:40,350
そのnullは、いくつかの特別なセンチネル値であり、
、リストの終わりを画定します

103
00:04:40,350 --> 00:04:44,280
私は指していないんだしながら、
私たちの最後のボランティアのように地面

104
00:04:44,280 --> 00:04:47,190
だった、のは先に行ってみましょう
そして次の操作を行います。

105
00:04:47,190 --> 00:04:51,820
pointer--もし、今、私は一種の希望
私たちは学生とやった何をすべきか

106
00:04:51,820 --> 00:04:57,410
ポインタドット次の場合structure--
むしろequals--、ポインタドットNが等しい場合

107
00:04:57,410 --> 00:05:02,290
、変数Nに等しく
に渡されています引数、

108
00:05:02,290 --> 00:05:05,370
その後、私は先に行きたいです
そして、trueを返すと言います。

109
00:05:05,370 --> 00:05:11,020
私は内部の数Nを発見しました
私のリンクリストのノードのいずれか。

110
00:05:11,020 --> 00:05:13,500
しかし、ドットもはや
このコンテキストで動作します、

111
00:05:13,500 --> 00:05:17,260
ポインタは、PTRは、ある理由
確かに、ポインタ、アドレス、

112
00:05:17,260 --> 00:05:20,632
私たちは実際に素晴らしくすることができます
最終的には構文の一部を使用します

113
00:05:20,632 --> 00:05:22,590
作りのようなもの
直感的な感覚と実際

114
00:05:22,590 --> 00:05:27,870
から行くことを意味し、ここで矢印を使用し
そこに整数にそのアドレス。

115
00:05:27,870 --> 00:05:30,160
だから、中に非常に似ています
ドット演算子の精神、

116
00:05:30,160 --> 00:05:33,860
しかし、ポインタはポインタではありませんので、
そして、は実際の構造体自体は、

117
00:05:33,860 --> 00:05:35,380
私たちは、矢印を使用しています。

118
00:05:35,380 --> 00:05:40,620
>> だから私現在のノード、もし
一時変数は、を指しています

119
00:05:40,620 --> 00:05:43,060
N、私は何をしたいのではないですか？

120
00:05:43,060 --> 00:05:45,910
まあ、私のヒトボランティアで
私たちは先日ここで持っていたこと、

121
00:05:45,910 --> 00:05:49,710
私の最初の人間は、一私でない場合
たい、多分二人ではありません

122
00:05:49,710 --> 00:05:52,660
私が欲しい1、第三に、私
移動物理的に維持する必要があります。

123
00:05:52,660 --> 00:05:54,690
同様に、どのように私は、リストをステップ実行しますか？

124
00:05:54,690 --> 00:05:57,470
我々は配列を持っていたとき、あなたを
ちょうど私プラスプラスのようでした。

125
00:05:57,470 --> 00:06:03,660
しかし、この場合にはすればよいです
次に、ポインタ、取得、ポインタを行います。

126
00:06:03,660 --> 00:06:07,580
言い換えると、次のフィールド
左手のすべてのようなものです

127
00:06:07,580 --> 00:06:10,880
その月曜日に私たち人間のボランティア
他のいくつかのノードを指すように使用していました。

128
00:06:10,880 --> 00:06:12,890
それらは彼らの次の隣人でした。

129
00:06:12,890 --> 00:06:17,060
>> だから私はこのリストをステップ実行したい場合は、
私はちょうど私プラスプラスもうできません、

130
00:06:17,060 --> 00:06:20,120
私が代わりに言っています
私、ポインタが、起こっています

131
00:06:20,120 --> 00:06:24,650
どのような次のフィールドに等しくなるようにすることで、
次のフィールドは、次のフィールドがあり、

132
00:06:24,650 --> 00:06:28,350
これらの左手、次のすべて
我々は、ステージ上でポインティング持っていたこと

133
00:06:28,350 --> 00:06:30,000
いくつかの後続の値に。

134
00:06:30,000 --> 00:06:32,590
そして、私が通って取得する場合
その全体の反復、

135
00:06:32,590 --> 00:06:39,330
そして最後に、私が持っていないヌルヒット
見つかったNはまだ、私はfalseを返します。

136
00:06:39,330 --> 00:06:44,100
だからもう一度、私たちはここでやっていることすべて、
少し前画像のとおり、

137
00:06:44,100 --> 00:06:47,840
でポイントすることによって開始されます
おそらく、リストの先頭。

138
00:06:47,840 --> 00:06:50,970
そして、私はチェックし、値であり、
私は9に等しいを探していますか？

139
00:06:50,970 --> 00:06:52,650
もしそうなら、私はtrueを返すと私は終わりです。

140
00:06:52,650 --> 00:06:56,450
そうでない場合、私は私の手を更新し、
ポイントへのAKAのポインタ、

141
00:06:56,450 --> 00:06:59,540
次の矢印の位置にあり、
その後、次の矢印の位置、

142
00:06:59,540 --> 00:07:00,480
そして次。

143
00:07:00,480 --> 00:07:03,770
私は単純に、この配列を歩いています。

144
00:07:03,770 --> 00:07:06,010
>> そこで再び、誰が気に？

145
00:07:06,010 --> 00:07:07,861
これはのための成分である何を？

146
00:07:07,861 --> 00:07:10,360
まあ、我々は導入することを思い出します
スタックの概念、どの

147
00:07:10,360 --> 00:07:15,400
抽象データ型は、それがだ限りにおいてです
Cではない事、それはCS50のことではありません、

148
00:07:15,400 --> 00:07:19,430
それは、このアイデア抽象的なアイデアです
互いの上にものを積み重ねます

149
00:07:19,430 --> 00:07:21,820
すなわち、で実現することができます
さまざまな方法の束。

150
00:07:21,820 --> 00:07:25,600
そして、私たちが提案した一つの方法はしていました
配列、またはリンクされたリストを持ちます。

151
00:07:25,600 --> 00:07:29,570
そしてそれは、その正準判明します
スタックは、少なくとも2つの操作をサポートしています。

152
00:07:29,570 --> 00:07:32,320
そして話題の言葉はに、プッシュされています
スタックに何かをプッシュし、

153
00:07:32,320 --> 00:07:34,770
で、新しいトレイのような
ダイニングホール、またはポップ、

154
00:07:34,770 --> 00:07:39,000
これは、最上位を削除することを意味します
ダイニングでスタックからトレイ

155
00:07:39,000 --> 00:07:41,500
ホール、多分いくつかの
他の操作にも。

156
00:07:41,500 --> 00:07:45,770
では、どのような構造を定義できます
我々は今、スタックを呼び出していること？

157
00:07:45,770 --> 00:07:50,020
>> まあ、我々は必要なのすべてを持っています
私が言うCで私達の処分で、構文、

158
00:07:50,020 --> 00:07:53,830
私のタイプの定義を与えます
スタックの内部構造、

159
00:07:53,830 --> 00:07:58,030
私が言うつもりAの配列であり、
数字、次にサイズの全体の束。

160
00:07:58,030 --> 00:08:00,930
だから、他の言葉で、私がしたい場合
コー​​ドでこれを実現するために、

161
00:08:00,930 --> 00:08:03,830
私が手放すとだけの種類
これは言っていることを描きます。

162
00:08:03,830 --> 00:08:06,317
だから、これは私に与える、と言っています
配列を持っている構造、

163
00:08:06,317 --> 00:08:09,400
私は、能力があるかわかりません
それは私がしたことを明らかにいくつかの定数です

164
00:08:09,400 --> 00:08:10,858
別の場所で定義され、それは大丈夫です。

165
00:08:10,858 --> 00:08:15,260
しかし、それはただ一つだと仮定し、
2つ、3つ、4つ、5。

166
00:08:15,260 --> 00:08:16,700
だから、容量は5です。

167
00:08:16,700 --> 00:08:21,730
私の内側にこの要素
構造は、番号を呼ばれます。

168
00:08:21,730 --> 00:08:24,020
そして、私は1つを必要とします
他の変数明らかに

169
00:08:24,020 --> 00:08:27,814
最初に私が行くよと呼ばれるサイズ
ゼロに初期化される規定します。

170
00:08:27,814 --> 00:08:29,730
何もでがない場合
スタックサイズは、ゼロであります

171
00:08:29,730 --> 00:08:31,420
それは数のゴミ値です。

172
00:08:31,420 --> 00:08:33,450
私はまだそこに何があるかわかりません。

173
00:08:33,450 --> 00:08:36,059
>> だから私はプッシュする場合
スタックに何か、

174
00:08:36,059 --> 00:08:40,780
私は機能プッシュを呼び出すと仮定し、
私は、数50のように、50を押してくださいと言います

175
00:08:40,780 --> 00:08:44,090
あなたはどこを提案します
私は、この配列にそれを描きますか？

176
00:08:44,090 --> 00:08:47,124
5別の可能な答えがあります。

177
00:08:47,124 --> 00:08:48,790
どこで番号50をプッシュしたいですか？

178
00:08:48,790 --> 00:08:51,899
ここでの目的ならば、もう一度、呼び出します
機能プッシュは、引数に渡します

179
00:08:51,899 --> 00:08:52,940
私はそれを置けばいい50の？

180
00:08:52,940 --> 00:08:55,680

181
00:08:55,680 --> 00:08:59,052
ファイブpossible-- 20％の確率で
正しく推測します。

182
00:08:59,052 --> 00:08:59,896
はい？

183
00:08:59,896 --> 00:09:00,740
>> 聴衆：右端。

184
00:09:00,740 --> 00:09:01,990
>> SPEAKER 1：右端。

185
00:09:01,990 --> 00:09:08,359
25％の確率で用意されました
正しく推測します。

186
00:09:08,359 --> 00:09:09,650
だから、実際には罰金になります。

187
00:09:09,650 --> 00:09:12,770
慣例では、私は配列を言いますよ、
当社は通常、左側に開始します

188
00:09:12,770 --> 00:09:14,519
しかし、我々は確かに可能性
右から始まります。

189
00:09:14,519 --> 00:09:17,478
だからここスポイラーは、私はだろう
おそらく、左側にそれを描画しようとして、

190
00:09:17,478 --> 00:09:20,060
ただここで通常の配列のように
私は右に左に行くを開始します。

191
00:09:20,060 --> 00:09:21,780
しかし、あなたが反転することができた場合
算術、罰金。

192
00:09:21,780 --> 00:09:23,060
それはちょうど、従来ではありません。

193
00:09:23,060 --> 00:09:24,880
[OK]を、私は1つをする必要があります
しかし、より変更。

194
00:09:24,880 --> 00:09:27,710
今私は何かをプッシュしたこと
スタックに、次は何？

195
00:09:27,710 --> 00:09:29,400
>> すべての権利、私はサイズを増加する必要があります。

196
00:09:29,400 --> 00:09:32,600
だから私は先にだけ行ってみよう
ゼロであった、これを更新します。

197
00:09:32,600 --> 00:09:35,950
そして代わりに、今、私は行きますよ
値1を入れます。

198
00:09:35,950 --> 00:09:39,460
そして今、私は別のをプッシュするとし
スタックに数51のように。

199
00:09:39,460 --> 00:09:42,680
まあ、私は1つ以上を行う必要があります
サイズ2までです変化。

200
00:09:42,680 --> 00:09:46,100
そして、私は1つ以上をプッシュするとし
61のようなスタックに数、

201
00:09:46,100 --> 00:09:52,530
今私はサイズを更新する必要がある1つ以上の
時間、サイズなどの値3を取得します。

202
00:09:52,530 --> 00:09:54,690
そして今、私はポップを呼び出すとします。

203
00:09:54,690 --> 00:09:57,250
今大会によって、ポップ、
引数を取りません。

204
00:09:57,250 --> 00:10:00,430
スタックでは、全体の
トレイメタファーのポイント

205
00:10:00,430 --> 00:10:03,450
あなたは裁量権を持っていないということです
そのトレイを取りに行くために、すべてのあなたが行うことができます

206
00:10:03,450 --> 00:10:06,330
から最上位の1をポップされています
スタック、という理由だけで。

207
00:10:06,330 --> 00:10:08,010
つまり、このデータ構造が何をするかです。

208
00:10:08,010 --> 00:10:12,250
>> もしそのロジックによるだから私
ポップ、何が外れ言いますか？

209
00:10:12,250 --> 00:10:13,080
だから61。

210
00:10:13,080 --> 00:10:15,402
それでは、実際にコンピュータであり、
メモリに何をするつもり？

211
00:10:15,402 --> 00:10:16,610
何私のコードは何をするのでしょうか？

212
00:10:16,610 --> 00:10:20,330
あなたは何を提案します
私たちは、画面上の変更しますか？

213
00:10:20,330 --> 00:10:23,410
何を変更する必要がありますか？

214
00:10:23,410 --> 00:10:24,960
ごめんなさい？

215
00:10:24,960 --> 00:10:26,334
だから我々は61を取り除きます。

216
00:10:26,334 --> 00:10:27,500
だから私は間違いなくそれを行うことができます。

217
00:10:27,500 --> 00:10:28,640
そして、私は61を取り除くことができます。

218
00:10:28,640 --> 00:10:30,980
そして、他のもの
変更が発生する必要がありますか？

219
00:10:30,980 --> 00:10:33,160
サイズは、おそらく2に戻っています。

220
00:10:33,160 --> 00:10:34,210
そしてそうそれは大丈夫です。

221
00:10:34,210 --> 00:10:36,690
しかし、サイズが数分待ちます
少し前3でした。

222
00:10:36,690 --> 00:10:38,240
ちょうど迅速な健全性チェックをしましょう​​。

223
00:10:38,240 --> 00:10:41,810
我々は、我々の方法を知っていました
61を取り除くしたいですか？

224
00:10:41,810 --> 00:10:42,760
私たちはポップだから。

225
00:10:42,760 --> 00:10:46,450
そして私は、この第2の特性サイズを有します。

226
00:10:46,450 --> 00:10:48,470
>> 私は、ちょっと待って
週2に戻って考えて

227
00:10:48,470 --> 00:10:51,660
私たちは話して始めたとき
これは場所ゼロであったの配列、

228
00:10:51,660 --> 00:10:55,920
これがこの場所だった、場所一つでした
2つのこの場所は三つ、四つであり、

229
00:10:55,920 --> 00:10:58,460
それは次のようになります
サイズの関係

230
00:10:58,460 --> 00:11:02,780
私は削除する要素を
アレイからだけで何のように見えますか？

231
00:11:02,780 --> 00:11:05,120
サイズから1を引きました。

232
00:11:05,120 --> 00:11:07,786
そして、そのためには、どのようにヒトのようです
私たちは、61は最初に来る知っています。

233
00:11:07,786 --> 00:11:09,160
どのようにコンピュータが知っているだろうか？

234
00:11:09,160 --> 00:11:11,701
ときあなたはおそらくあなたのコード、
サイズから1を引いたものをやってみたいです、

235
00:11:11,701 --> 00:11:14,950
そう3マイナス1は2であり、かつ
私たちは61を取り除きたいことを意味します。

236
00:11:14,950 --> 00:11:18,000
そして、我々は確かに更新することができます
そのサイズので、サイズ今

237
00:11:18,000 --> 00:11:20,300
ちょうど3つから2つになります。

238
00:11:20,300 --> 00:11:24,520
そして、ちょうど知識をひけらかすことを、私は行きますよ
右、私は終わりだことを提案しますか？

239
00:11:24,520 --> 00:11:27,660
あなたは直感的に提案しました
正しく私は61を取り除く必要があります。

240
00:11:27,660 --> 00:11:30,700
しかし、私は一種の持っていません
ソートの61の脱却？

241
00:11:30,700 --> 00:11:33,790
私は効果的に忘れてしまいました
ことそれは実際にあります。

242
00:11:33,790 --> 00:11:37,680
あなたが読んだなら、バックPSET4に思います
フォレンジックに関する記事、PDF

243
00:11:37,680 --> 00:11:40,780
私たちは、あなたたちは読んでいたかということ
PSET4今週読み込みます。

244
00:11:40,780 --> 00:11:44,300
これは実際に密接であることを思い出してください
コンピュータフォレンジックの全体的なアイデア。

245
00:11:44,300 --> 00:11:47,820
どのようなコンピュータは一般的にないです
何かがどこにあるか、それだけで、忘れ

246
00:11:47,820 --> 00:11:51,300
それはで行くと好きではありません
それをスクラッチしてみてくださいまたはオーバーライド

247
00:11:51,300 --> 00:11:54,560
0と1とのそれらのビット
またはいくつかの他のランダムパターン

248
00:11:54,560 --> 00:11:56,690
あなたがない限り、自分が意図的にそう。

249
00:11:56,690 --> 00:11:58,930
だからあなたの直感がありました
右のは、61を取り除くましょう。

250
00:11:58,930 --> 00:12:00,650
しかし現実には、我々は気にする必要はありません。

251
00:12:00,650 --> 00:12:04,040
私達はちょうどそれを忘れする必要があります
それが私たちのサイズを変更してあります。

252
00:12:04,040 --> 00:12:05,662
>> 今、このスタックに問題があります。

253
00:12:05,662 --> 00:12:07,620
私は物事をプッシュし続ける場合
スタックに、何の

254
00:12:07,620 --> 00:12:11,167
明らかに起こるだろう
わずかな時間の時間の？

255
00:12:11,167 --> 00:12:12,500
私たちは、スペースが不足するつもりです。

256
00:12:12,500 --> 00:12:13,580
そして、我々は何をしていますか？

257
00:12:13,580 --> 00:12:14,680
私たちは、種類のネジ止めしています。

258
00:12:14,680 --> 00:12:19,000
この実装はできません
使用しているので、私たちは、配列のサイズを変更します

259
00:12:19,000 --> 00:12:21,240
この構文、よろしければ
週2に戻って考えて、

260
00:12:21,240 --> 00:12:23,520
あなたが宣言した後に
アレイのサイズは、

261
00:12:23,520 --> 00:12:26,780
我々はまだどこメカニズムを見ていません
あなたは、配列のサイズを変更することができます。

262
00:12:26,780 --> 00:12:29,020
そして実際、Cはその機能がありません。

263
00:12:29,020 --> 00:12:32,524
あなたが言う場合は私に5を与えます
NTHS、それらを呼び出す番号、

264
00:12:32,524 --> 00:12:33,940
それはあなたがそれを取得するつもりだすべてです。

265
00:12:33,940 --> 00:12:38,790
だから我々は、月曜日のようになりまし持っていますか
解決策を表現する能力

266
00:12:38,790 --> 00:12:42,480
しかし、私達はちょうど微調整する必要があります
私たちのスタックの定義

267
00:12:42,480 --> 00:12:46,840
いくつかのハードコードされた配列されないように、
ちょうどアドレスを格納します。

268
00:12:46,840 --> 00:12:47,890
>> 今、これはなぜですか？

269
00:12:47,890 --> 00:12:51,690
今、私たちはただで快適でなければなりません
私のプログラムが実行されるという事実は、

270
00:12:51,690 --> 00:12:53,730
私はおそらくに行きますよ
人間を依頼する必要があり、

271
00:12:53,730 --> 00:12:55,110
どのように多くの数字あなたが保存したいですか？

272
00:12:55,110 --> 00:12:56,776
そこで入力がどこから来ています。

273
00:12:56,776 --> 00:12:59,140
しかし、私はことを知っていたら、
数、私はちょうどすることができます

274
00:12:59,140 --> 00:13:02,470
与えるように機能するものを使用
私のメモリの塊？

275
00:13:02,470 --> 00:13:03,580
私は、malloc関数を使用することができます。

276
00:13:03,580 --> 00:13:06,710
そして、私は、任意の数を言うことができます
バイト私は、これらのNTHSのために戻って欲しいです。

277
00:13:06,710 --> 00:13:10,910
そして、私が持っているすべてを数字に格納します
この構造体の内部に、ここで可変

278
00:13:10,910 --> 00:13:13,480
何すべきですか？

279
00:13:13,480 --> 00:13:18,440
実際に何に入ります
このシナリオの数字？

280
00:13:18,440 --> 00:13:21,300
うん、最初のポインタ
メモリのチャンクのバイト、

281
00:13:21,300 --> 00:13:24,940
より具体的に、アドレス
それらのバイトの最初の。

282
00:13:24,940 --> 00:13:27,300
それは一つだ場合は問題ではありません
バイトまたは億バイト、

283
00:13:27,300 --> 00:13:28,890
私は最初に気にする必要があります。

284
00:13:28,890 --> 00:13:31,530
そのため何のmalloc保証および
私のオペレーティングシステムの保証、

285
00:13:31,530 --> 00:13:34,170
すなわち、メモリIのチャンクであります
取得するには、それが連続したことになるだろう。

286
00:13:34,170 --> 00:13:35,378
ギャップがあるようにはないだろう。

287
00:13:35,378 --> 00:13:38,576
だから私は、50を求めてしまった場合
バイトまたは1,000バイトとして、

288
00:13:38,576 --> 00:13:40,450
彼らはすべてのことになるだろう
背中合わせにバックアップします。

289
00:13:40,450 --> 00:13:44,500
そして長い間、私はどのように、どのように大きな覚えて
ずっと私は私が知っている必要があり、すべてを求め

290
00:13:44,500 --> 00:13:46,230
最初のそのようなアドレスです。

291
00:13:46,230 --> 00:13:48,660
>> だから今、私たちはコード内の能力を持っています。

292
00:13:48,660 --> 00:13:51,280
いえ、それは私たちを取るために起こっています
これを書くために多くの時間、

293
00:13:51,280 --> 00:13:55,900
私たちは、今ではそのメモリを再割り当て可能性
そこに別のアドレスを格納します

294
00:13:55,900 --> 00:13:59,060
私たちも、大きくなったりしたい場合は、
メモリの小さいチャンク。

295
00:13:59,060 --> 00:14:00,170
だからここにトレードオフに。

296
00:14:00,170 --> 00:14:01,360
今、私たちはダイナミズムを得ます。

297
00:14:01,360 --> 00:14:03,350
我々はまだ持っています
私が主張している連続性。

298
00:14:03,350 --> 00:14:05,881
malloc関数は、私たちを与えるため、
メモリの連続チャンク。

299
00:14:05,881 --> 00:14:08,630
しかし、これは痛みになるだろう
私たちのために首、プログラマー、

300
00:14:08,630 --> 00:14:09,770
実際にアップコードに。

301
00:14:09,770 --> 00:14:10,730
それはちょうどより多くの仕事です。

302
00:14:10,730 --> 00:14:13,930
私たちは、私が何であったかに似たコードを必要とします
ちょっと前に出叩い。

303
00:14:13,930 --> 00:14:16,120
非常になんとか、それは複雑になります。

304
00:14:16,120 --> 00:14:19,520
だから開発者の時間、プログラマ
時間はまだ別のリソースであります

305
00:14:19,520 --> 00:14:22,520
私たちが過ごすために必要かもしれません
新しい機能を得るためにいくつかの時間。

306
00:14:22,520 --> 00:14:24,020
そしてもちろんキューがあります。

307
00:14:24,020 --> 00:14:26,227
我々は、このにはなりません
多くの詳細で1。

308
00:14:26,227 --> 00:14:27,560
しかし、それは心の中で非常に似ています。

309
00:14:27,560 --> 00:14:31,220
私はキューを実装することができ、および
その対応する動作、

310
00:14:31,220 --> 00:14:35,660
エンキューまたはデキュー、追加または削除のような、
それを言うだけ手の込んだ方法です、

311
00:14:35,660 --> 00:14:38,100
エンキューまたはデキュー、次のように。

312
00:14:38,100 --> 00:14:41,170
私はちょうど自分自身の構造体を与えることができます
その再び数のアレイを有し、

313
00:14:41,170 --> 00:14:44,000
その再度サイズを有し、
しかし、なぜ私は今必要なのですか

314
00:14:44,000 --> 00:14:46,940
キューの先頭を追跡するには？

315
00:14:46,940 --> 00:14:50,630
私が知っている必要はありませんでした
私のスタックの正面。

316
00:14:50,630 --> 00:14:53,570
さて、もし私が再び用
ちょうどハードのを聞かせてqueue--

317
00:14:53,570 --> 00:14:57,870
5のようなものとして、それをコーディング
潜在的に、ここで整数。

318
00:14:57,870 --> 00:15:00,940
これは、0個、1個、2個、3個、4です。

319
00:15:00,940 --> 00:15:03,430
これは、になるだろう
もう一度番号を呼ばれます。

320
00:15:03,430 --> 00:15:06,940
そして、これはサイズと呼ばれます。

321
00:15:06,940 --> 00:15:10,056
>> なぜそれが十分ではありません
サイズだけを持っていますか？

322
00:15:10,056 --> 00:15:11,680
さて、上でそれらの同じ番号を押してみましょう。

323
00:15:11,680 --> 00:15:14,220
だから、私はキューに入れられた、または押されpushed--。

324
00:15:14,220 --> 00:15:20,150
今、私は50をエンキューします、その後、
51、次に61、ドットドットドット。

325
00:15:20,150 --> 00:15:21,070
だから、エンキューです。

326
00:15:21,070 --> 00:15:23,176
私は、61、その後50、51をエンキュー。

327
00:15:23,176 --> 00:15:25,050
そして、それは同じに見えます
これまでのスタックに、

328
00:15:25,050 --> 00:15:27,190
除いて私は1つの変更を行う必要があります。

329
00:15:27,190 --> 00:15:33,680
私はこのサイズを更新する必要があるので、私は行きます
ゼロ二から一に今3。

330
00:15:33,680 --> 00:15:35,760
私はどのようにデキューできますか？

331
00:15:35,760 --> 00:15:36,890
何がデキューとどうなりますか？

332
00:15:36,890 --> 00:15:41,950
誰が最初​​にこのリストをオフに来る必要があります
それはアップルストアでのラインですか？

333
00:15:41,950 --> 00:15:42,780
だから50。

334
00:15:42,780 --> 00:15:44,700
だから、ちょっとトリッキーこの時間です。

335
00:15:44,700 --> 00:15:47,880
前回のに対し、それはスーパーでした
ジャストサイズのマイナスいずれかの操作を実行するのは簡単、

336
00:15:47,880 --> 00:15:51,440
私は効果的に私の配列の最後に到達します
数字である場合、それは61を除去します。

337
00:15:51,440 --> 00:15:52,920
しかし、私は61を削除する必要はありません。

338
00:15:52,920 --> 00:15:55,030
私は、50をしたい人
5:00でした

339
00:15:55,030 --> 00:15:56,790
以下のためにラインアップします
新しいiPhoneやその他もろもろ。

340
00:15:56,790 --> 00:16:01,200
そして私は、50を取り除くために
ちょうど、これを行うことができないのですか？

341
00:16:01,200 --> 00:16:02,547
私は50を越えることができます。

342
00:16:02,547 --> 00:16:04,380
しかし、我々はちょうど私達言いました
そう肛門である必要はありません

343
00:16:04,380 --> 00:16:06,330
スクラッチアウトまたはデータを非表示にするように。

344
00:16:06,330 --> 00:16:08,090
それがどこにあるか私達はちょうど忘れることができます。

345
00:16:08,090 --> 00:16:12,330
>> しかし、私は今、私のサイズを変更した場合
2、この十分な情報があります

346
00:16:12,330 --> 00:16:15,711
私のキューに何が起こっているか知っていますか？

347
00:16:15,711 --> 00:16:16,680
あんまり。

348
00:16:16,680 --> 00:16:19,830
私のサイズが2であると同様ですが、
キューは、どこから始めません、

349
00:16:19,830 --> 00:16:22,980
私はまだ持っている場合は特に
メモリのものと同じ番号。

350
00:16:22,980 --> 00:16:24,260
50、51、61。

351
00:16:24,260 --> 00:16:27,090
だから私は覚えておく必要があります
今どこに正面です。

352
00:16:27,090 --> 00:16:29,630
そして、私が提案したように、
そこに、私たちは求めているでしょう

353
00:16:29,630 --> 00:16:33,729
その最初のN番目の前、
値は何だったでしょうか？

354
00:16:33,729 --> 00:16:35,270
ゼロ、リストの始まりに過ぎません。

355
00:16:35,270 --> 00:16:40,876
しかし、今デクリメントに加えて、
大きさは、私たちは前をインクリメント。

356
00:16:40,876 --> 00:16:42,000
今ここで別の問題です。

357
00:16:42,000 --> 00:16:43,030
だから一度、私は続けます。

358
00:16:43,030 --> 00:16:47,520
これは数あるとし
くそ、124、121のように、その後、

359
00:16:47,520 --> 00:16:48,610
私は宇宙の外です。

360
00:16:48,610 --> 00:16:50,390
しかし、私はないんだけど、ちょっと待って。

361
00:16:50,390 --> 00:16:55,630
だから、物語の中で、この時点では、
サイズが1、2であると仮定し、

362
00:16:55,630 --> 00:17:00,370
3、4、そうしたと
サイズは、フロントが1である、4です

363
00:17:00,370 --> 00:17:01,621
そう51は、前面にあります。

364
00:17:01,621 --> 00:17:04,329
私はここで別の番号を入れたいです、
しかし、くそ、私は宇宙の外です。

365
00:17:04,329 --> 00:17:06,710
しかし、私は、右、本当にないんだけど？

366
00:17:06,710 --> 00:17:11,192
私はいくつかをどこに置くことができます
171のような付加価値、？

367
00:17:11,192 --> 00:17:13,400
ええ、私はできるだけの種類
右、そこに戻って？

368
00:17:13,400 --> 00:17:18,161
そして50を横断する、または
ちょうど171でそれを上書きします。

369
00:17:18,161 --> 00:17:20,410
そして、あなたは、なぜ迷っている場合
私たちの数値は、そのようにランダムです

370
00:17:20,410 --> 00:17:24,150
これらは、一般的にコンピュータをとっています
CS50後ハーバード大学の科学コース。

371
00:17:24,150 --> 00:17:27,510
しかし、それは良い最適化しました、
今ので、私はスペースを無駄にしませんよ。

372
00:17:27,510 --> 00:17:30,750
私はまだ覚えておく必要があります
どのように大きなこのことは、合計です。

373
00:17:30,750 --> 00:17:31,500
これは、5つの合計です。

374
00:17:31,500 --> 00:17:33,375
私はしたくないので
51の上書きを開始します。

375
00:17:33,375 --> 00:17:36,260
だから今私はまだ空き容量が不足しています、
前と同じ問題。

376
00:17:36,260 --> 00:17:39,140
しかし、あなたはどのように見ることができるようになりまし
あなたのコードでは、おそらく

377
00:17:39,140 --> 00:17:41,910
もう少しを記述する必要があり
それを実現するために複雑。

378
00:17:41,910 --> 00:17:44,510
そして実際に、どのようなオペレータ
C言語で、おそらくすることができます

379
00:17:44,510 --> 00:17:48,110
あなたは魔法のように、この円形のですか？

380
00:17:48,110 --> 00:17:50,160
うん、モジュロ演算子、
パーセント記号。

381
00:17:50,160 --> 00:17:53,160
だから、キューについての種類のクールなものを、
我々は描画の配列を維持するにもかかわらず、

382
00:17:53,160 --> 00:17:56,520
このような直線として、あなたの場合
一種の湾曲としてこれについて考えます

383
00:17:56,520 --> 00:18:00,341
周りの円として、そしてちょうど
直感的に、それは一種の精神的に動作します

384
00:18:00,341 --> 00:18:01,590
私はもう少しきれいだと思います。

385
00:18:01,590 --> 00:18:05,190
あなたはまだ実装する必要があります
コー​​ド内でそのメンタルモデル。

386
00:18:05,190 --> 00:18:07,550
そうではないこと、ハード、
最終的には、実装するために、

387
00:18:07,550 --> 00:18:12,430
しかし、我々はまだ、かなりsize--を失います
我々はこれを行う場合を除き、サイズを変更する機能。

388
00:18:12,430 --> 00:18:15,310
>> 私たちは、配列の解消を取得する必要があります
単一のポインタと交換し、

389
00:18:15,310 --> 00:18:20,010
して、どこかに私のコードで私が持っています
実際にどのような関数を作成するための呼び出し

390
00:18:20,010 --> 00:18:23,720
配列と呼ばれる番号？

391
00:18:23,720 --> 00:18:26,190
malloc関数、またはいくつかの類似しました
機能、正確に。

392
00:18:26,190 --> 00:18:30,481
スタックやキュー上の任意の質問。

393
00:18:30,481 --> 00:18:30,980
うん？

394
00:18:30,980 --> 00:18:33,657

395
00:18:33,657 --> 00:18:34,240
良い質問。

396
00:18:34,240 --> 00:18:35,830
何モジュロここで使用します。

397
00:18:35,830 --> 00:18:38,520
そこで、一般的に、使用している場合
MOD、あなたはそれを行うだろう

398
00:18:38,520 --> 00:18:40,620
の大きさに
全データ構造。

399
00:18:40,620 --> 00:18:44,120
だから、5または容量のようなもの、であれば
それは一定ですが、おそらく関与しています。

400
00:18:44,120 --> 00:18:47,100
しかし、単にモジュロ5をやって
おそらく、十分ではありません

401
00:18:47,100 --> 00:18:51,380
私たちが知っている必要がありますので、我々を行います
ここかここか、ここで折り返します。

402
00:18:51,380 --> 00:18:54,160
だから、おそらくもいます
関与するするつもり

403
00:18:54,160 --> 00:18:57,220
事の大きさ、または
同様にフロント変数。

404
00:18:57,220 --> 00:19:00,140
だから、比較的ちょうどこのです
単純な算術式、

405
00:19:00,140 --> 00:19:02,000
しかし、モジュロは重要な要素になります。

406
00:19:02,000 --> 00:19:03,330
>> だから短編映画あなたがする場合。

407
00:19:03,330 --> 00:19:05,780
アニメーション一部
他大学の人たち

408
00:19:05,780 --> 00:19:08,060
私たちがしたことをまとめて
この議論のために適合。

409
00:19:08,060 --> 00:19:12,630
それはジャックが学習関与します
キューと統計についての事実。

410
00:19:12,630 --> 00:19:19,010

411
00:19:19,010 --> 00:19:21,890
>> FILM：むかしむかし、
ジャックという名前の男がありました。

412
00:19:21,890 --> 00:19:25,330
それは友達を作るに来たとき、
ジャックはコツがありませんでした。

413
00:19:25,330 --> 00:19:28,220
そこでジャックはに話に行きました
最も人気のある男と彼は知っていました。

414
00:19:28,220 --> 00:19:30,920
彼はルーに行って尋ねた、私は何をしますか？

415
00:19:30,920 --> 00:19:33,400
ルーは彼の友人のを見ました
本当に悩んでいました。

416
00:19:33,400 --> 00:19:36,050
まあ、彼はただ、始まりました
あなたが服を着ているかに見えます。

417
00:19:36,050 --> 00:19:38,680
あなたは、任意の服を持っていません
異なる表情で？

418
00:19:38,680 --> 00:19:39,660
はい、ジャックは言いました。

419
00:19:39,660 --> 00:19:40,840
私は確信しております。

420
00:19:40,840 --> 00:19:43,320
私の家に来て、
私はあなたにそれらを紹介します。

421
00:19:43,320 --> 00:19:44,550
そこで、彼らはジャックのに消えました。

422
00:19:44,550 --> 00:19:47,520
そして、ジャックはルーにボックスを示しました
彼はすべての彼のシャツを保ったところ、

423
00:19:47,520 --> 00:19:49,260
彼のズボン、彼の靴下。

424
00:19:49,260 --> 00:19:52,290
ルーは、私はあなたが持っている参照してください、と述べました
山のすべてのあなたの服。

425
00:19:52,290 --> 00:19:54,870
なぜあなたは、いくつかを着用しません
しばらくの間に一度他の人？

426
00:19:54,870 --> 00:19:58,020
>> ジャックは、言っただけでなく、ときに私
服や靴下を削除し、

427
00:19:58,020 --> 00:20:00,780
私はそれらを洗って置きます
ボックスにそれらを離れて。

428
00:20:00,780 --> 00:20:03,210
そして、次が来ます
朝、最大私はホップ。

429
00:20:03,210 --> 00:20:06,380
私はボックスに移動してもらいます
上から私の服。

430
00:20:06,380 --> 00:20:09,070
ルーはすぐに実現します
ジャックに問題。

431
00:20:09,070 --> 00:20:12,080
彼は、服、CDを保持しました
スタック内の図書。

432
00:20:12,080 --> 00:20:14,420
彼はのために達したとき
読みしたり、着用するもの、

433
00:20:14,420 --> 00:20:17,100
彼はトップの本や下着を選ぶと思います。

434
00:20:17,100 --> 00:20:19,500
そして、彼が行ったときに、彼
すぐに戻ってそれを置くことになります。

435
00:20:19,500 --> 00:20:21,970
戻るには、スタックの一番上に、行くだろう。

436
00:20:21,970 --> 00:20:24,460
私は解決策を知っています、
勝ち誇ったラウド言いました。

437
00:20:24,460 --> 00:20:27,090
あなたがすることを学ぶ必要があります
キューを使用して起動します。

438
00:20:27,090 --> 00:20:29,870
ルーは、ジャックの服を取り、
クローゼットの中にそれらを切りました。

439
00:20:29,870 --> 00:20:32,710
そして、彼は空になった時
ボックスには、彼はそれを投げました。

440
00:20:32,710 --> 00:20:36,500
>> それから彼はジャックの最後に、今、言いました
日、左にあなたの服を置きます

441
00:20:36,500 --> 00:20:37,990
あなたはそれらを片付けるとき。

442
00:20:37,990 --> 00:20:41,300
そして、明日の朝とき
あなたの服を取得し、太陽の光を参照してください。

443
00:20:41,300 --> 00:20:43,440
右に、行の末尾から。

444
00:20:43,440 --> 00:20:44,880
分かりませんの？ルーは言いました。

445
00:20:44,880 --> 00:20:46,370
それはとても素敵になります。

446
00:20:46,370 --> 00:20:49,770
あなたは、一度にすべてを着用しましょう
前に二回何かを着用してください。

447
00:20:49,770 --> 00:20:52,670
そして、キュー内のすべてと
彼のクローゼットや棚で、

448
00:20:52,670 --> 00:20:55,160
ジャックは感じ始め
自分自身の非常に確認してください。

449
00:20:55,160 --> 00:20:59,720
ルーへのすべてのおかげで、
彼の素晴らしいキュー。

450
00:20:59,720 --> 00:21:01,220
SPEAKER 1：すべての権利、それは愛らしいです。

451
00:21:01,220 --> 00:21:05,920

452
00:21:05,920 --> 00:21:10,080
だから何が本当に起こってきました
今ボンネットの下に？

453
00:21:10,080 --> 00:21:12,370
我々はポインタを持っていること、
我々はmalloc関数を持っていること、

454
00:21:12,370 --> 00:21:15,680
我々は、作成する能力を持っていること
自分のためにメモリのチャンク

455
00:21:15,680 --> 00:21:16,344
動的に。

456
00:21:16,344 --> 00:21:18,510
だから、これは絵たちです
ちょうど先日垣間見。

457
00:21:18,510 --> 00:21:21,180
私たちは本当に住むませんでした
その上に、この絵

458
00:21:21,180 --> 00:21:24,180
下に続いています
今週間のフード。

459
00:21:24,180 --> 00:21:27,050
そして、これはただ表し、
私たちが描いた四角形、

460
00:21:27,050 --> 00:21:28,180
コンピュータのメモリ。

461
00:21:28,180 --> 00:21:31,850
そして多分あなたのコンピュータ、またはCS50
IDは、メモリやRAMのギガバイトを持っています

462
00:21:31,850 --> 00:21:33,050
または2ギガバイトまたは4。

463
00:21:33,050 --> 00:21:34,450
それは本当に問題ではありません。

464
00:21:34,450 --> 00:21:37,240
お使いのオペレーティングシステム
WindowsやMac OSのやLinux、

465
00:21:37,240 --> 00:21:41,120
基本的に、あなたのプログラムが可能に
それがアクセス権を持つことを考えて

466
00:21:41,120 --> 00:21:42,982
全体に
コンピュータのメモリ、

467
00:21:42,982 --> 00:21:45,440
あなたが実行されている可能性があっても
一度に複数のプログラム。

468
00:21:45,440 --> 00:21:46,990
だから実際には、それが実際に動作しません。

469
00:21:46,990 --> 00:21:49,448
しかし、それは幻想のようなものです
あなたのプログラムのすべてに与えられました。

470
00:21:49,448 --> 00:21:53,110
だから、RAMの2ギグ、これを持っていた場合
コンピュータはそれを考えるかもしれない方法です。

471
00:21:53,110 --> 00:21:57,110
>> 今偶然、これらのいずれか
物事、メモリのこれらのセグメントの一つ、

472
00:21:57,110 --> 00:21:58,350
スタックと呼ば​​れています。

473
00:21:58,350 --> 00:22:01,680
そして、実際には任意の時間
これまで書き込みコードで

474
00:22:01,680 --> 00:22:05,900
あなたが求めていること
インスタンスメインための機能、。

475
00:22:05,900 --> 00:22:08,410
いつでも私がしたことを思い出してください
描かれたコンピュータのメモリ、

476
00:22:08,410 --> 00:22:10,640
私はいつも一種の描画します
ここでは、長方形の半分

477
00:22:10,640 --> 00:22:12,520
そして、話を気にしないでください
上記の何について。

478
00:22:12,520 --> 00:22:15,980
主が呼び出されたとき、私は主張するため、
あなたは、このメモリのスライバーを取得すること

479
00:22:15,980 --> 00:22:16,970
それはここでダウンしました。

480
00:22:16,970 --> 00:22:20,650
そして、メイン関数を呼び出された場合
スワップのように、よくスワップがここに入ります。

481
00:22:20,650 --> 00:22:23,720
そして、それはそれだ、判明します
どこに終わるです。

482
00:22:23,720 --> 00:22:26,277
スタックと呼ば​​れるもので、
コンピュータのメモリの内部。

483
00:22:26,277 --> 00:22:28,360
今一日の終わりに、
これはただのアドレスです。

484
00:22:28,360 --> 00:22:30,680
これは、バイトゼロのようなものです
バイト1、バイト2億円となりました。

485
00:22:30,680 --> 00:22:33,130
しかし、あなたはそれについて考える場合
この長方形のオブジェクトとして、

486
00:22:33,130 --> 00:22:35,130
すべての我々は、すべてをやっています
我々は関数を呼び出す時です

487
00:22:35,130 --> 00:22:37,180
メモリの新しいスライスを重ねます。

488
00:22:37,180 --> 00:22:41,700
我々は、スライスその機能を与えています
で動作するように、独自のメモリ。

489
00:22:41,700 --> 00:22:44,490
>> そして今、これが重要であることを思い出してください。

490
00:22:44,490 --> 00:22:46,400
私たちがしなければ持っているため、
スワップのようなもの

491
00:22:46,400 --> 00:22:51,610
AとBなど、および2つのローカル変数
私たちは、1と2からこれらの値を変更

492
00:22:51,610 --> 00:22:55,130
2と1、リコールへ
スワップを返すときに、

493
00:22:55,130 --> 00:22:58,330
それは、このスライスかのようです
メモリのちょうどなくなっています。

494
00:22:58,330 --> 00:23:00,080
実際に、それはまだです
そこフォレンジック。

495
00:23:00,080 --> 00:23:01,940
そして、何かが実際にそこにまだあります。

496
00:23:01,940 --> 00:23:05,410
しかし、概念的に、それは同様です
けれどもそれは完全に逝ってしまいました。

497
00:23:05,410 --> 00:23:10,910
それで主は、作業のいずれかを知りません。
それは、そのスワップ機能に行われていました

498
00:23:10,910 --> 00:23:14,890
それは実際にそれらに渡された場合を除き
ポインタまたは参照によって引数を指定します。

499
00:23:14,890 --> 00:23:17,790
さて、根本的な解決策
スワップでその問題に

500
00:23:17,790 --> 00:23:19,970
アドレスによってで物事を通過します。

501
00:23:19,970 --> 00:23:23,250
しかし、それは何も、結局のところ
その部分の上に続いてき

502
00:23:23,250 --> 00:23:26,330
すべてのこの時間は、長方形の
まだより多くのメモリアップがあります。

503
00:23:26,330 --> 00:23:28,790
そして、ときに動的に
メモリを割り当て、

504
00:23:28,790 --> 00:23:32,020
それは、のGetStringの内側にいるのですか
我々はCS50であなたのために行ってきました

505
00:23:32,020 --> 00:23:34,710
ライブラリー、または君たち場合
malloc関数を呼び出すと尋ねます

506
00:23:34,710 --> 00:23:37,950
のチャンクのためのオペレーティングシステム
メモリは、それがスタックから付属していません。

507
00:23:37,950 --> 00:23:40,960
それは別の場所から来ています
お使いのコンピュータのメモリに

508
00:23:40,960 --> 00:23:42,220
それは、ヒープと呼ばれています。

509
00:23:42,220 --> 00:23:43,430
そして、それは何が違うのではありません。

510
00:23:43,430 --> 00:23:44,285
これは、同じRAMです。

511
00:23:44,285 --> 00:23:45,160
これは、同じメモリです。

512
00:23:45,160 --> 00:23:49,080
それはアップちょうどRAMです
そこの代わりに、ダウンここに。

513
00:23:49,080 --> 00:23:50,750
>> そしてそうそれは何を意味するのでしょうか？

514
00:23:50,750 --> 00:23:53,650
さて、あなたのコンピュータがある場合は
メモリの有限量

515
00:23:53,650 --> 00:23:57,450
スタックので、育っています
話し、ヒープ、に従ってします

516
00:23:57,450 --> 00:23:59,349
この矢印に、ダウン成長しています。

517
00:23:59,349 --> 00:24:01,140
言い換えれば、すべての
時間あなたはmalloc関数を呼び出し、

518
00:24:01,140 --> 00:24:03,430
あなたのスライスを与えられています
メモリの上から、

519
00:24:03,430 --> 00:24:06,630
多分少し低い、その後少し
下、あなたはmalloc関数を呼び出すたびに、

520
00:24:06,630 --> 00:24:10,100
ヒープは、それは使用ですが、
成長の一種です、

521
00:24:10,100 --> 00:24:11,950
ものに近づく成長？

522
00:24:11,950 --> 00:24:13,382
スタック。

523
00:24:13,382 --> 00:24:14,840
だから、これは良いアイデアのように見えるのでしょうか？

524
00:24:14,840 --> 00:24:18,420

525
00:24:18,420 --> 00:24:22,140
それは本当にはっきりしていない場合は、私は、意味します
あなた場合にのみ、あなたは他に何を行うことができます

526
00:24:22,140 --> 00:24:23,910
メモリの有限量を持っています。

527
00:24:23,910 --> 00:24:25,200
しかし、これは確かに悪いです。

528
00:24:25,200 --> 00:24:27,920
これら2矢印が上にあります
互いのためのコースをクラッシュ。

529
00:24:27,920 --> 00:24:31,930
>> そして、それはその悪いやつ、人々が判明
プログラミングに特に優れています、

530
00:24:31,930 --> 00:24:36,140
コンピュータに侵入しようとすると、
この現実を利用することができます。

531
00:24:36,140 --> 00:24:38,290
実際には、のは、考えてみましょう
少しスニペット。

532
00:24:38,290 --> 00:24:41,350
だから、これはあなたが読むことができる例であり、
ウィキペディアでより詳細に示します。

533
00:24:41,350 --> 00:24:43,100
私たちはであなたを指します
記事であれば好奇心。

534
00:24:43,100 --> 00:24:45,650
しかし、攻撃が一般的にあります
バッファオーバーフローとして知られていること

535
00:24:45,650 --> 00:24:49,570
人間である限りのために存在していました
操作する能力を持っていました

536
00:24:49,570 --> 00:24:53,120
特にC言語で、コンピュータのメモリ、
だから、これは非常に任意のプログラムです、

537
00:24:53,120 --> 00:24:55,130
しかしそれでは、ボトムアップからそれを読んでみましょう。

538
00:24:55,130 --> 00:24:57,650
ARGCチャースターARGVにメイン。

539
00:24:57,650 --> 00:24:59,830
だから、かかるプログラムです
コマンドライン引数。

540
00:24:59,830 --> 00:25:03,620
そして、すべての主は明らかに呼び出しがあるん
この関数は、簡単のためにFを呼び出します。

541
00:25:03,620 --> 00:25:04,610
そして、それは何に渡しますか？

542
00:25:04,610 --> 00:25:05,490
1のARGV。

543
00:25:05,490 --> 00:25:09,320
だから、Fに入るものは何でも
単語は、ユーザーが入力したことです

544
00:25:09,320 --> 00:25:11,500
後のプロンプトで
まったくプログラムの名前。

545
00:25:11,500 --> 00:25:15,730
シーザーやVigenereようなので、多くの、どの
あなたはARGVにやって思い出すかもしれません。

546
00:25:15,730 --> 00:25:16,680
>> だから、Fは何ですか？

547
00:25:16,680 --> 00:25:19,760
Fは文字列を取り込み、
その唯一の引数として、

548
00:25:19,760 --> 00:25:22,100
char型のスターAKA、同じ
事、文字列として。

549
00:25:22,100 --> 00:25:24,920
そして、それは任意に呼ばれています
この例では、バー。

550
00:25:24,920 --> 00:25:27,710
そして、char型のC 12、
ただ普通の言葉で、

551
00:25:27,710 --> 00:25:31,750
私たちのためにやって文字Cブラケット12は何ですか？

552
00:25:31,750 --> 00:25:33,440
それは何をするのか？

553
00:25:33,440 --> 00:25:36,490
具体的には、メモリの割り当て
12文字のための12バイト。

554
00:25:36,490 --> 00:25:36,990
その通りです。

555
00:25:36,990 --> 00:25:40,000
そして、最後の行は、攪拌し、
コピーは、おそらく見ていませんでした。

556
00:25:40,000 --> 00:25:43,360
これは文字列のコピーです
その目的は生活の中で機能

557
00:25:43,360 --> 00:25:48,160
その第二引数をコピーすることです
最初の引数に、

558
00:25:48,160 --> 00:25:51,190
だけまで
一定のバイト数。

559
00:25:51,190 --> 00:25:53,860
だから、3番目の引数は、言います
あなたはどのように多くのバイトをコピーする必要がありますか？

560
00:25:53,860 --> 00:25:56,720
バーの長さは、
何で入力したユーザー。

561
00:25:56,720 --> 00:25:59,320
のと内容
バー、その文字列、されています

562
00:25:59,320 --> 00:26:02,330
Cで指さメモリにコピー

563
00:26:02,330 --> 00:26:04,060
>> だから、これは一種の愚かなようで、それはあります。

564
00:26:04,060 --> 00:26:06,300
それは不自然な例ですが、
それは代表的です

565
00:26:06,300 --> 00:26:10,100
攻撃ベクトルのクラスの、
プログラムを攻撃する方法です。

566
00:26:10,100 --> 00:26:15,050
すべては、ユーザーならば罰金と良いです
11文字の言葉でタイプ

567
00:26:15,050 --> 00:26:18,040
または少ない、プラスバックスラッシュゼロ。

568
00:26:18,040 --> 00:26:22,830
何よりものユーザーが、タイプの場合
11または12または20または50文字？

569
00:26:22,830 --> 00:26:25,090
どうするつもりこのプログラムは何ですか？

570
00:26:25,090 --> 00:26:29,360
潜在的にワンセグ障害。それは起こっています
盲目的アップバーのすべてをコピーします

571
00:26:29,360 --> 00:26:31,750
で、その長さに
バーで文字通りすべてのもの、

572
00:26:31,750 --> 00:26:36,307
C.しかし、Cで指摘アドレスに
唯一の先制12バイトとして与えています。

573
00:26:36,307 --> 00:26:37,640
しかし、追加のチェックはありません。

574
00:26:37,640 --> 00:26:38,700
条件がない場合はありません。

575
00:26:38,700 --> 00:26:40,580
ここでチェックエラーはありません。

576
00:26:40,580 --> 00:26:43,270
>> だから、このプログラムは何ですか
何をするつもりは、やみくもにあります

577
00:26:43,270 --> 00:26:45,750
他に一つのことをコピーします。

578
00:26:45,750 --> 00:26:47,880
そして、私たちはこれを描く場合
絵のように、ここです

579
00:26:47,880 --> 00:26:49,860
メモリ空間のちょうどスライバー。

580
00:26:49,860 --> 00:26:53,470
だから私たちは、一番下に気付きます
ローカル変数のバーを持っています。

581
00:26:53,470 --> 00:26:57,330
store--ために起こっているので、ポインタ
だと地元の引数ではなく

582
00:26:57,330 --> 00:26:58,672
文字列のバーを保存するために行きます。

583
00:26:58,672 --> 00:27:00,380
そして、ちょうど気づきます
それ以上のスタックで、

584
00:27:00,380 --> 00:27:02,505
なぜならあなたが尋ねるたびに
スタック上のメモリのため、

585
00:27:02,505 --> 00:27:04,310
それは少し行きます
それ以上の絵、

586
00:27:04,310 --> 00:27:06,270
私たちはそこに12バイトを持っていることに気づきます。

587
00:27:06,270 --> 00:27:10,690
左上1は、Cブラケットゼロであり、
右下の1は、Cブラケット11です。

588
00:27:10,690 --> 00:27:12,870
それはどれだけのコンピュータです
それをレイアウトする予定。

589
00:27:12,870 --> 00:27:18,300
だから直感的に、バーはより多くを持っている場合
含めた合計で12文字、より

590
00:27:18,300 --> 00:27:25,790
バックスラッシュゼロであり、
12またはCブラケット12は行くつもり？

591
00:27:25,790 --> 00:27:28,440
かここ12日です
文字または13日文字、

592
00:27:28,440 --> 00:27:30,900
百文字に行きます
絵に終わるには？

593
00:27:30,900 --> 00:27:33,400
上または下に？

594
00:27:33,400 --> 00:27:36,300
>> 右、たとえ理由
スタック自体は、上方に成長します

595
00:27:36,300 --> 00:27:39,590
あなたは中のものを入れてしたら
それ、それ、設計上の理由から、

596
00:27:39,590 --> 00:27:41,294
上から下にメモリを置きます。

597
00:27:41,294 --> 00:27:44,460
あなたは12以上のバイトを持っているのであれば、
あなたがバーを上書きする開始するつもりです。

598
00:27:44,460 --> 00:27:47,280
今ではバグですが、それはです
本当に大したこと。

599
00:27:47,280 --> 00:27:51,130
ありますので、しかし、それは、大したことです
メモリで起こってより多くのもの。

600
00:27:51,130 --> 00:27:53,074
どのように我々はかもしれないので、ここです
明確にするために、ハロー置きます。

601
00:27:53,074 --> 00:27:54,490
私は、プロンプトにハローで入力した場合。

602
00:27:54,490 --> 00:27:59,330
H-E-L-L-Oバックスラッシュゼロ、内終わります
これらの12バイトは、我々は超安全です。

603
00:27:59,330 --> 00:28:00,330
すべては順調です。

604
00:28:00,330 --> 00:28:03,020
しかし、私は何かを入力した場合
長く、潜在的にそれはです

605
00:28:03,020 --> 00:28:05,860
バースペースに忍び込むつもり。

606
00:28:05,860 --> 00:28:08,405
しかし、さらに悪いことに、それはターン
すべてのこの時間外に、

607
00:28:08,405 --> 00:28:11,530
我々はについて話したことがないにもかかわらず、
これは、スタックが他のもののために使用されます。

608
00:28:11,530 --> 00:28:13,560
これは、ローカル変数だけではありません。

609
00:28:13,560 --> 00:28:15,100
>> Cは非常に低レベルの言語です。

610
00:28:15,100 --> 00:28:17,810
そして、それ一種の密か
また、スタックを使用しています

611
00:28:17,810 --> 00:28:21,260
ときに覚えておきます
関数は、何と呼ばれています

612
00:28:21,260 --> 00:28:26,040
アドレスは、前の関数であります
それは戻って、その関数にジャンプすることができます。

613
00:28:26,040 --> 00:28:29,980
だから、メインの呼び出しはの間で、交換時
物事がスタックにプッシュ

614
00:28:29,980 --> 00:28:34,380
ローカル変数だけを交換していません、
またはその引数、また密かにプッシュ

615
00:28:34,380 --> 00:28:37,510
スタック上に表されるように
ここで赤スライスすることにより、

616
00:28:37,510 --> 00:28:40,520
物理的にメインのアドレスであります
コンピュータのメモリで、

617
00:28:40,520 --> 00:28:44,180
コンピュータは、交換が行われたときにそのよう
私は主に戻って行く必要がある知っています

618
00:28:44,180 --> 00:28:46,760
main関数の実行を終了します。

619
00:28:46,760 --> 00:28:51,960
これは、今危険であるかの理由
こんにちはよりよく、より内のユーザーの種類、

620
00:28:51,960 --> 00:28:57,030
ユーザーの入力が上書きしてしまうような
または、その赤い部分が上書きされます

621
00:28:57,030 --> 00:28:59,820
論理的であれば、コンピュータの
やみくもと仮定しよう

622
00:28:59,820 --> 00:29:03,830
その赤いスライス内のバイトがあること
それは返す必要があります先の住所、

623
00:29:03,830 --> 00:29:09,020
敵がどのようであれば十分にスマートまたは
バイトのシーケンスを置くには十分に幸運

624
00:29:09,020 --> 00:29:13,450
そこアドレスのように見えること、
それはコードのアドレスです

625
00:29:13,450 --> 00:29:18,730
彼または彼女はコンピュータを望んでいます
代わりに、メインの実行するには？

626
00:29:18,730 --> 00:29:21,670
>> 言い換えれば、どのような場合
ユーザは、プロンプトで入力しています

627
00:29:21,670 --> 00:29:23,850
ただものではありません
こんにちは、無害のように

628
00:29:23,850 --> 00:29:28,210
実際には同等のコードです
このすべてのユーザーのファイルを削除するには？

629
00:29:28,210 --> 00:29:30,060
それとも私に自分のパスワードを電子メールで送信！

630
00:29:30,060 --> 00:29:31,940
それとも自分のロギングを開始
キーストロークは、右？

631
00:29:31,940 --> 00:29:34,920
方法があり、今日は明記しましょう
彼らはハローないだけで入力できること

632
00:29:34,920 --> 00:29:36,711
世界や自分の名前、
彼らは基本的にできました

633
00:29:36,711 --> 00:29:39,570
コー​​ド、ゼロに渡し、
もの、そのコンピュータ

634
00:29:39,570 --> 00:29:43,450
コー​​ドと住所の両方のミス。

635
00:29:43,450 --> 00:29:48,950
もし、やや抽象的にいえそう
十分な敵対コード内のユーザーの種類

636
00:29:48,950 --> 00:29:52,330
私たちはここのように一般化するだろうと
A. Aは、攻撃や敵です。

637
00:29:52,330 --> 00:29:53,140
だから悪いもの。

638
00:29:53,140 --> 00:29:55,306
私たちは気にしません
数字または0または1

639
00:29:55,306 --> 00:29:59,470
今日、あなたは、終わること
その赤い部分が上書きされ、

640
00:29:59,470 --> 00:30:01,580
バイトの順序に注意してください。

641
00:30:01,580 --> 00:30:05,020
O 835 Cゼロ8ゼロ。

642
00:30:05,020 --> 00:30:08,960
そして今ここにWikipediaの記事など
あなたは今、実際に起動した場合、提案しています

643
00:30:08,960 --> 00:30:12,460
お使いのコンピュータの中でバイトを標識
メモリは、Wikipediaの記事は何ですか

644
00:30:12,460 --> 00:30:19,060
提案は、どのような場合のアドレス、ということです
その左上のバイトの80 C 0 3508です。

645
00:30:19,060 --> 00:30:22,200
>> 換言すれば、悪者がある場合
自分のコードで十分にスマート

646
00:30:22,200 --> 00:30:26,650
実際にここ数を入れています
コー​​ドのアドレスに対応します

647
00:30:26,650 --> 00:30:29,180
彼または彼女は注入しました
コンピュータに、あなた

648
00:30:29,180 --> 00:30:31,050
コンピュータをだますことができます
何もしてへ。

649
00:30:31,050 --> 00:30:34,140
、ファイルの削除電子メールで送信
物事、あなたのトラフィックを盗聴、

650
00:30:34,140 --> 00:30:36,710
文字通り何でもすることができ
コンピュータに注入しました。

651
00:30:36,710 --> 00:30:39,220
だからバッファオーバーフロー
その中核に攻撃

652
00:30:39,220 --> 00:30:43,530
ただ愚かな、愚かです
その配列のオーバーライド

653
00:30:43,530 --> 00:30:45,840
その境界が確認されていませんでした。

654
00:30:45,840 --> 00:30:48,850
そして、これは超危険は何かということです
そして、同時に超強力

655
00:30:48,850 --> 00:30:52,560
C言語で私たちが実際に持っているということです
メモリ内の任意の場所へのアクセス。

656
00:30:52,560 --> 00:30:55,320
それは私たち次第だ、プログラマー、
元のコードを書く人

657
00:30:55,320 --> 00:30:59,330
いずれかのくその長さをチェックします
私たちが操作している配列。

658
00:30:59,330 --> 00:31:00,750
だから明確にする、修正は何ですか？

659
00:31:00,750 --> 00:31:03,190
私たちはこれにロールバックする場合
コー​​ド、私はいけません

660
00:31:03,190 --> 00:31:08,000
バーの長さを変更し、どのような
他に私がチェックすべきですか？

661
00:31:08,000 --> 00:31:10,620
他に何私がやるべきこと
完全にこの攻撃を防ぎますか？

662
00:31:10,620 --> 00:31:14,110
私はただやみくもに言いたくありません
あなたは多くのバイトとしてコピーする必要があること

663
00:31:14,110 --> 00:31:16,140
バーの長さです。

664
00:31:16,140 --> 00:31:18,910
私が言いたい、としてコピー
バーにあるように多くのバイト

665
00:31:18,910 --> 00:31:24,090
割り当てられたまで
メモリ、最大12。

666
00:31:24,090 --> 00:31:27,450
だから私は、条件の場合のいくつかの種類を必要とします
それは、バーの長さをチェックし、

667
00:31:27,450 --> 00:31:32,800
それが12を超える場合は、我々だけでハードコード
可能な最大距離として12。

668
00:31:32,800 --> 00:31:35,910
それ以外の場合は、いわゆるバッファ
オーバーフロー攻撃が発生する可能性があります。

669
00:31:35,910 --> 00:31:38,451
これらのスライドの下部には、
あなたはより多くを読み興味があれば

670
00:31:38,451 --> 00:31:41,200
実際のオリジナル記事です。
あなたが見てみたいと思います。

671
00:31:41,200 --> 00:31:44,550
>> しかし、今、価格の中
こちらで負担することは非効率でした。

672
00:31:44,550 --> 00:31:46,680
だから、それは簡単でした
どのローレベルの外観

673
00:31:46,680 --> 00:31:49,709
問題は、今、我々が発生する可能性が
コンピュータのメモリにアクセスすることができます。

674
00:31:49,709 --> 00:31:51,750
しかし、別の問題、我々
すでに月曜日につまずい

675
00:31:51,750 --> 00:31:53,800
ただ非効率でした
リンクリストの。

676
00:31:53,800 --> 00:31:56,019
我々は戻って線形時間にしています。

677
00:31:56,019 --> 00:31:57,560
私たちは、もはや連続した配列を有していません。

678
00:31:57,560 --> 00:31:58,980
我々は、ランダムアクセスを持っていません。

679
00:31:58,980 --> 00:32:00,710
私たちは、角括弧表記を使用することはできません。

680
00:32:00,710 --> 00:32:04,590
我々は文字通り、whileループを使用する必要があります
私は少し前に書いたような。

681
00:32:04,590 --> 00:32:09,740
しかし、月曜日に、私たちができることを主張しました
効率の領域に戻ってクリープ

682
00:32:09,740 --> 00:32:13,040
何かを達成
対数多分、または最高のまだ、

683
00:32:13,040 --> 00:32:16,120
だ多分何か
一定の時間、いわゆる。

684
00:32:16,120 --> 00:32:19,840
それでは、どのよう我々は、これらの新しいを使用していることを行うことができます
ツール、これらのアドレス、これらのポインタ、

685
00:32:19,840 --> 00:32:22,210
そして、私たち自身のものをスレッド？

686
00:32:22,210 --> 00:32:23,960
まあ、あるとし
ここで、これらがたくさんあり​​ます

687
00:32:23,960 --> 00:32:27,170
我々はに格納する数字の
効率的なデータ構造と検索。

688
00:32:27,170 --> 00:32:30,960
私たちは絶対に週に巻き戻すことができます
2、配列にこれらを投げます、

689
00:32:30,960 --> 00:32:33,150
バイナリ検索を使って検索します。

690
00:32:33,150 --> 00:32:34,040
分割統治。

691
00:32:34,040 --> 00:32:37,720
そして、実際にあなたが書きました
PSET3でバイナリ検索、

692
00:32:37,720 --> 00:32:40,100
どこに検索プログラムを実施しました。

693
00:32:40,100 --> 00:32:40,890
しかし、あなたは何を知っています。

694
00:32:40,890 --> 00:32:45,060
より多くの種類があります
これを行うための賢い方法。

695
00:32:45,060 --> 00:32:47,390
それはもう少しです
おそらくそれは、洗練されたと

696
00:32:47,390 --> 00:32:50,830
なぜバイナリ私たちが見ることができます
検索はとてもはるかに高速です。

697
00:32:50,830 --> 00:32:52,980
まずは、ご紹介しましょう
ツリーの概念。

698
00:32:52,980 --> 00:32:54,730
どれでも中かかわらず
現実の木の種類の

699
00:32:54,730 --> 00:32:57,730
コンピュータの世界では、このように育ちます
彼らは一種の下方への成長科学

700
00:32:57,730 --> 00:33:00,830
あなたが持っている家系図のような
あなたの祖父母や偉大な祖父母

701
00:33:00,830 --> 00:33:04,580
またはその他もろもろトップ、家長でと
家族の女家長、​​一つだけ

702
00:33:04,580 --> 00:33:07,930
以下のいわゆるルート、ノード、
その子供がいるが、

703
00:33:07,930 --> 00:33:11,442
その子であるその下に、または
より一般的にはその子孫。

704
00:33:11,442 --> 00:33:13,400
そして、誰もがぶら下がっ
家族の底

705
00:33:13,400 --> 00:33:16,070
であることに加え、ツリー、
家族の中で最年少、

706
00:33:16,070 --> 00:33:19,520
また、単に一般的にすることができます
ツリーのリーフと呼ばれます。

707
00:33:19,520 --> 00:33:21,800
>> だから、これはちょうど束であります
単語と定義

708
00:33:21,800 --> 00:33:25,790
コンピュータのツリーと呼ばれるもののために
科学、家系図のようにずっと。

709
00:33:25,790 --> 00:33:28,770
しかし、愛好家の化身があります
木の、そのうちの1つ

710
00:33:28,770 --> 00:33:30,780
二分探索木と呼ばれています。

711
00:33:30,780 --> 00:33:34,380
そして、あなたのことができいじめるの種類
このことは何を離れて。

712
00:33:34,380 --> 00:33:37,180
まあ、それはどのような意味でのバイナリですか？

713
00:33:37,180 --> 00:33:41,455
どこにバイナリがここから来たのでしょうか？

714
00:33:41,455 --> 00:33:41,955
ごめんなさい？

715
00:33:41,955 --> 00:33:45,961

716
00:33:45,961 --> 00:33:47,210
それはどちらかそれほどではありませんか。

717
00:33:47,210 --> 00:33:52,000
これは、各ノードが全くあることがよりです
二つ以上の子どもたちが、私たちはここを参照してくださいよう。

718
00:33:52,000 --> 00:33:54,990
一般的に、tree--と
あなたの両親や祖父母

719
00:33:54,990 --> 00:33:57,640
など、多くの子供を持つことができますか
孫彼らが実際に必要として、

720
00:33:57,640 --> 00:34:00,820
そのため、インスタンスのためにそこに我々は3を持っています
その右手ノードオフ子どもたち、

721
00:34:00,820 --> 00:34:05,480
しかし、バイナリツリーで、ノードが持っています
最大で0個、1個、または2人の子供。

722
00:34:05,480 --> 00:34:08,496
そして、それは、素晴らしい特性です
それは2でキャップだ場合ので、

723
00:34:08,496 --> 00:34:10,620
私たちのことができるようにするつもりです
小さなログベース2を取得

724
00:34:10,620 --> 00:34:11,975
アクションは最終的にここで起こって。

725
00:34:11,975 --> 00:34:13,350
だから我々は、対数何かを持っています。

726
00:34:13,350 --> 00:34:14,558
しかし、現時点でその上より。

727
00:34:14,558 --> 00:34:19,810
探索木の数であることを意味
配置など左側の子のこと

728
00:34:19,810 --> 00:34:22,429
値は、ルートよりも大きいです。

729
00:34:22,429 --> 00:34:26,010
そして、その右の子です
ルートよりも大きいです。

730
00:34:26,010 --> 00:34:29,290
つまり、のいずれかをとる場合
ノード、この写真のサークル、

731
00:34:29,290 --> 00:34:31,840
その左側に見えます
子供とその右の子、

732
00:34:31,840 --> 00:34:34,739
最初は、より小さくなければなりません
第二は、より大きくする必要があります。

733
00:34:34,739 --> 00:34:36,159
それで正気は55をご確認ください。

734
00:34:36,159 --> 00:34:37,780
これは、子供が33で残っています。

735
00:34:37,780 --> 00:34:38,620
それはより少ないです。

736
00:34:38,620 --> 00:34:40,929
55、その右の子は77です。

737
00:34:40,929 --> 00:34:41,783
それはより大きいです。

738
00:34:41,783 --> 00:34:43,199
そして、それは再帰的な定義です。

739
00:34:43,199 --> 00:34:46,480
私たちはそれらの一つ一つをチェックすることができます
ノードと同じパターン開催します。

740
00:34:46,480 --> 00:34:49,389
>> だからでの素敵なものです
二分探索木であります

741
00:34:49,389 --> 00:34:52,204
その一つは、我々はそれを実装することができます
構造体で、これだけが好きです。

742
00:34:52,204 --> 00:34:54,620
そして、私たちが投げているにもかかわらず、
あなたに構造の多く、

743
00:34:54,620 --> 00:34:56,560
彼らは多少です
直感的な今うまくいけば。

744
00:34:56,560 --> 00:35:00,570
構文は、まだ確かに難解です
しかし、この内のノードの内容

745
00:35:00,570 --> 00:35:02,786
context--我々は保ちます
単語のノードを使用して、

746
00:35:02,786 --> 00:35:04,910
それは長方形ですか
画面または円に、

747
00:35:04,910 --> 00:35:08,970
それだけでいくつかの一般的なコンテナですが、
以下のような木のこの場合、

748
00:35:08,970 --> 00:35:11,780
私たちが見て、私たちは整数を必要とします
各ノードで

749
00:35:11,780 --> 00:35:15,460
そして私は指す2つのポインタを必要とします
左の子と右の子に、

750
00:35:15,460 --> 00:35:16,590
それぞれ。

751
00:35:16,590 --> 00:35:20,730
それはですので、どのようにかもしれません
構造体のそれを実装します。

752
00:35:20,730 --> 00:35:22,315
そして、どのように私は、コードでそれを実装するのでしょうか？

753
00:35:22,315 --> 00:35:26,730
さて、素早くてみましょう
この小さな例を見てみましょう。

754
00:35:26,730 --> 00:35:29,820
それは機能していないのですが、私はしました
コピーされ、その構造体を貼り付けました。

755
00:35:29,820 --> 00:35:33,510
そして、もしバイナリのための私の機能
探索木は、検索と呼ばれ、

756
00:35:33,510 --> 00:35:36,980
これは2つの引数を取り、
整数Nとポインタ

757
00:35:36,980 --> 00:35:41,400
ツリーのノードなので、ポインタへ
またはツリーのルートへのポインタ、

758
00:35:41,400 --> 00:35:43,482
どのように私は、Nを探して行くのですか？

759
00:35:43,482 --> 00:35:45,440
さて、最初に、私はだから
ポインタを扱います、

760
00:35:45,440 --> 00:35:46,750
私は健全性チェックをするつもりです。

761
00:35:46,750 --> 00:35:54,279
ツリーがヌルに等しい等しい場合、Nは
このツリー内のか、このツリー内の？

762
00:35:54,279 --> 00:35:55,070
それは右、することはできませんか？

763
00:35:55,070 --> 00:35:56,870
私はヌル過ぎだ場合は、
そこには何もありません。

764
00:35:56,870 --> 00:35:59,230
私かもしれないとしても、単に
やみくもにはfalseを返すと言います。

765
00:35:59,230 --> 00:36:04,050
あなたが私に何を与えていない場合、私は確かにすることはできません
他のN.だから、私は可能性のある番号を検索

766
00:36:04,050 --> 00:36:04,750
今確認？

767
00:36:04,750 --> 00:36:12,830
私はよく、他のNがある場合を言うつもりです
ツリーノードにあるものは何でも未満

768
00:36:12,830 --> 00:36:16,300
私はN値を渡してきたこと。

769
00:36:16,300 --> 00:36:20,270
言い換えれば、私は数あれば
N、探して、ノードよりも小さいです

770
00:36:20,270 --> 00:36:21,340
私は見ていていること。

771
00:36:21,340 --> 00:36:23,190
そして、ノードは、私が探しています
ツリーと呼ばれているで、

772
00:36:23,190 --> 00:36:26,370
そして、前の例からリコール
ポインタの値を取得するには、

773
00:36:26,370 --> 00:36:28,310
私は矢印の表記法を使用します。

774
00:36:28,310 --> 00:36:35,960
Nツリー矢印未満であれば
Nは、私は概念的に左に行きたいです。

775
00:36:35,960 --> 00:36:38,590
どのように私は左サーチし表現するのですか？

776
00:36:38,590 --> 00:36:41,560
これがある場合は、明確にするために、
問題の画像、

777
00:36:41,560 --> 00:36:44,612
私は、その最上位に合格してきました
それが下を向いています矢印。

778
00:36:44,612 --> 00:36:45,570
それは私の木のポインタです。

779
00:36:45,570 --> 00:36:48,060
私は、ツリーのルートを指しています。

780
00:36:48,060 --> 00:36:52,100
そして、私はのために、と言う探しています
数44、任意に。

781
00:36:52,100 --> 00:36:55,300
44以下であります
明らかに55よりも大きいですか？

782
00:36:55,300 --> 00:36:56,360
だから、より少ないです。

783
00:36:56,360 --> 00:36:58,760
だから、この条件に該当する場合。

784
00:36:58,760 --> 00:37:03,981
だから、概念的に、私はに何をしたいです
私は44を探している場合は、次の検索？

785
00:37:03,981 --> 00:37:04,480
うん？

786
00:37:04,480 --> 00:37:08,310

787
00:37:08,310 --> 00:37:11,100
>> まさに、私がしたいです
左の子を検索し、

788
00:37:11,100 --> 00:37:12,789
またはこの画像の左部分木。

789
00:37:12,789 --> 00:37:14,830
そして実際に、私を通します
ここに絵ダウン

790
00:37:14,830 --> 00:37:17,770
ちょっと、以来、
私はこれを傷つけることはできません。

791
00:37:17,770 --> 00:37:21,150
私は55で、ここで起動した場合、および
私が知っている値44

792
00:37:21,150 --> 00:37:23,180
にあるため、私は探しています
左は、それはようなものです

793
00:37:23,180 --> 00:37:26,010
中で電話帳を引き裂くような
半分または半分にツリーを引き裂きます。

794
00:37:26,010 --> 00:37:29,660
私はもう気にする必要はありません
ツリーのこの全体の半分。

795
00:37:29,660 --> 00:37:33,270
そして、まだ、不思議の観点から
構造、こっち、この事

796
00:37:33,270 --> 00:37:36,682
、33で始まること自体
二分探索木です。

797
00:37:36,682 --> 00:37:39,890
ため、私は前の単語が再帰言っ
確かに、これは、そのデータ構造であります

798
00:37:39,890 --> 00:37:41,707
定義によって再帰的です。

799
00:37:41,707 --> 00:37:44,540
あなたはこののツリーを持っている可能性があります
大きいが、その子供たちの一人一人

800
00:37:44,540 --> 00:37:46,870
ほんの少し小さいツリーを表しています。

801
00:37:46,870 --> 00:37:50,910
代わりに、それはおじいちゃんであることの
または、今はちょうどママおばあちゃんの

802
00:37:50,910 --> 00:37:54,300
or--私はお母さんないsay--することはできません
またはお父さん、それは奇妙なことだろう。

803
00:37:54,300 --> 00:37:59,000
そこに二人の子供の代わりに
兄と兄弟のようになります。

804
00:37:59,000 --> 00:38:01,120
家系の新世代。

805
00:38:01,120 --> 00:38:02,900
しかし、構造的に、それは同じ考えです。

806
00:38:02,900 --> 00:38:06,790
そして、それは私が機能を持つ判明します
これで私は二分探索を検索することができます

807
00:38:06,790 --> 00:38:07,290
木。

808
00:38:07,290 --> 00:38:08,680
それは、検索と呼ばれています。

809
00:38:08,680 --> 00:38:17,870
私は木の矢印左側にNを検索
他のNの値よりも大きい場合

810
00:38:17,870 --> 00:38:18,870
ことを私は現在でよ。

811
00:38:18,870 --> 00:38:20,800
少し前の話で55。

812
00:38:20,800 --> 00:38:23,780
私はと呼ばれる機能を持っています
検索私はすることができます

813
00:38:23,780 --> 00:38:29,660
Nこれを通過して、再帰的に検索
サブツリーだけリターン

814
00:38:29,660 --> 00:38:30,620
何でもその答え。

815
00:38:30,620 --> 00:38:33,530
他の私はここにいくつかの最終的なベースケースを持っています。

816
00:38:33,530 --> 00:38:35,310
>> 最後のケースは何ですか？

817
00:38:35,310 --> 00:38:36,570
ツリーは、どちらかnullです。

818
00:38:36,570 --> 00:38:39,980
私はどちらかを探していた値であります
それより小さいかそれよりも大きいです

819
00:38:39,980 --> 00:38:42,610
またはそれに等しいです。

820
00:38:42,610 --> 00:38:44,750
そして、私は同じと言うことができます
等しく、しかし論理的にそれはです

821
00:38:44,750 --> 00:38:46,500
ちょうどここに、他の言うのと同等。

822
00:38:46,500 --> 00:38:49,150
だから、本当の私は何かを見つける方法です。

823
00:38:49,150 --> 00:38:51,710
だから、うまくいけば、これは
さらに説得力のある例

824
00:38:51,710 --> 00:38:54,900
愚かなシグマ関数より
私たちは、戻っていくつかの講義を行いました

825
00:38:54,900 --> 00:38:58,360
どこにループを使用するのも簡単でした
1からすべての数字をカウントアップします

826
00:38:58,360 --> 00:39:02,390
データ構造を持つ。ここでNに
自身が再帰的であること

827
00:39:02,390 --> 00:39:07,050
我々は今、定義され、再帰的に描かれました
自分自身を表現する能力を持っています

828
00:39:07,050 --> 00:39:09,780
コー​​ド自体は再帰的です。

829
00:39:09,780 --> 00:39:12,580
だから、これはここにまったく同じコードです。

830
00:39:12,580 --> 00:39:14,400
>> だから我々は、他のどのような問題を解決することができますか？

831
00:39:14,400 --> 00:39:18,160
離れてからだからクイックステップ
ちょっと木。

832
00:39:18,160 --> 00:39:20,130
ここではドイツのフラグは、たとえば、あります。

833
00:39:20,130 --> 00:39:22,020
そして、明らかにありま​​す
このフラグのパターン。

834
00:39:22,020 --> 00:39:23,811
そして、たくさんのがあります
世界のフラグいます

835
00:39:23,811 --> 00:39:27,560
点では、このような単純なされています
その色やパターンの。

836
00:39:27,560 --> 00:39:31,930
これは以下のように格納されていると仮定する
.GIF、またはJPEG、ビットマップ、またはpingを実行、

837
00:39:31,930 --> 00:39:34,240
グラフィカルファイル形式
これであなたは、精通しています

838
00:39:34,240 --> 00:39:36,460
私たちがしているそのうちのいくつか
PSET4で一緒に遊ん。

839
00:39:36,460 --> 00:39:41,550
これは、保存する価値は思えません
黒画素、黒画素、黒画素、

840
00:39:41,550 --> 00:39:44,790
ドット、ドット、ドット、の全体の束
最初の走査線用の黒画素、

841
00:39:44,790 --> 00:39:47,430
その後または行の全体の束
同じ、その後、全体の束

842
00:39:47,430 --> 00:39:49,530
同じ、およびその後の
赤色画素の全体の束、

843
00:39:49,530 --> 00:39:53,020
その後、赤色画素、赤色画素、全体
黄色ピクセルの束、黄色、右？

844
00:39:53,020 --> 00:39:55,050
>> ここで、このような非効率性があります。

845
00:39:55,050 --> 00:39:59,040
どのように直感的にあなたのだろう
ドイツの旗を圧縮

846
00:39:59,040 --> 00:40:01,320
ファイルとして、それを実装する場合は？

847
00:40:01,320 --> 00:40:04,940
どのような情報のように、私たちがすることはできません
ために、ディスク上に保存する気に

848
00:40:04,940 --> 00:40:08,040
私達のファイルサイズが等から減少させます
キロバイト、何かにメガバイト

849
00:40:08,040 --> 00:40:09,430
小さいですか？

850
00:40:09,430 --> 00:40:13,130
ここで冗長性があります
ここで明確にするには？

851
00:40:13,130 --> 00:40:13,880
君に何ができただろうか？

852
00:40:13,880 --> 00:40:14,380
うん？

853
00:40:14,380 --> 00:40:21,380

854
00:40:21,380 --> 00:40:21,970
その通りです。

855
00:40:21,970 --> 00:40:24,550
なぜではなく、覚えています
すべてのくそピクセルの色

856
00:40:24,550 --> 00:40:28,200
ちょうどあなたがPSET4でやっているような
ビットマップのファイル形式と、

857
00:40:28,200 --> 00:40:32,060
なぜあなたは単に表すものではありません
例えば、画素の左端の列、

858
00:40:32,060 --> 00:40:35,370
黒画素の束、束
赤、黄の束の、

859
00:40:35,370 --> 00:40:39,210
して、ちょうど何とかエンコード
繰り返しのアイデアこの100回

860
00:40:39,210 --> 00:40:41,020
または、この千回繰り返しますか？

861
00:40:41,020 --> 00:40:43,430
どこに100または1,000です
ちょうど整数、あなたので、

862
00:40:43,430 --> 00:40:47,290
ただ一つの番号で逃げることができます
代わりに何百、何千もの

863
00:40:47,290 --> 00:40:48,270
追加のピクセル。

864
00:40:48,270 --> 00:40:50,990
そして実際、それはどのように我々です
ドイツの旗を圧縮することができます。

865
00:40:50,990 --> 00:40:51,490
と

866
00:40:51,490 --> 00:40:53,470
フランス国旗について今度は何なの？

867
00:40:53,470 --> 00:40:58,930
のいくつかの並べ替えとリトル
頭の体操、どのフラグ

868
00:40:58,930 --> 00:41:01,040
ディスクの詳細を圧縮することができますか？

869
00:41:01,040 --> 00:41:05,720
ドイツのフラグまたはフランス語
フラグ、我々はそのアプローチを取る場合はどうなりますか？

870
00:41:05,720 --> 00:41:08,490
ドイツの旗、ありますので、
より水平冗長。

871
00:41:08,490 --> 00:41:12,190
そして設計により、多くのグラフィックファイル
フォーマットは確かに走査線として機能します

872
00:41:12,190 --> 00:41:12,830
水平。

873
00:41:12,830 --> 00:41:14,674
彼らは仕事ができます
垂直方向に、ちょうど人間性

874
00:41:14,674 --> 00:41:17,090
決め年前、我々はよ
一般的に物事の行を考えます

875
00:41:17,090 --> 00:41:18,880
列で行の代わりに列で。

876
00:41:18,880 --> 00:41:20,820
だから、実際にあなたがいた場合
ファイルを見て

877
00:41:20,820 --> 00:41:24,670
ドイツの旗の大きさとフランス
フラグ、限り解像度があるとして、

878
00:41:24,670 --> 00:41:27,530
同じ、同じ幅
高さ、この1

879
00:41:27,530 --> 00:41:31,580
ここでは、大きくなるとしているあなたのために
自分自身を3回繰り返す必要があります。

880
00:41:31,580 --> 00:41:35,570
あなたは青、繰り返しを指定する必要があります
自分では、白、赤、自分自身を繰り返します

881
00:41:35,570 --> 00:41:36,740
自分自身を繰り返します。

882
00:41:36,740 --> 00:41:39,000
あなたはすべて行くことができません
右への道。

883
00:41:39,000 --> 00:41:41,200
また余談として、作るために
圧縮をクリア

884
00:41:41,200 --> 00:41:43,910
これらのであれば、どこにでもあります
video--あなたからの4つのフレーム

885
00:41:43,910 --> 00:41:45,890
その映画を思い出すかもしれません
またはビデオは、一般的です

886
00:41:45,890 --> 00:41:47,286
毎秒29または30フレームのように。

887
00:41:47,286 --> 00:41:50,410
それはあなたの小さなフリップブックのようなものです
ちょうど画像、画像、画像、画像を参照してください、

888
00:41:50,410 --> 00:41:54,410
画像それがどのように見えるので、ちょうど超高速
画面上の俳優が移動しています。

889
00:41:54,410 --> 00:41:57,130
ここで熊蜂のです
花の束の一番上。

890
00:41:57,130 --> 00:41:59,790
そして、それは一種のかもしれませんが
最初の一目で確認するのは難しいです、

891
00:41:59,790 --> 00:42:04,020
に移動する唯一のもの
この映画は、蜂です。

892
00:42:04,020 --> 00:42:06,880
>> 何保管についてのダムです
ビデオは非圧縮しますか？

893
00:42:06,880 --> 00:42:11,420
これは、ビデオを保存するために、廃棄物のようなものです
4ほぼ同一の画像のようなもの

894
00:42:11,420 --> 00:42:13,670
のみ限り蜂がどこにあるかのように異なります。

895
00:42:13,670 --> 00:42:16,280
あなたは、ほとんどを捨てることができます
その情報の

896
00:42:16,280 --> 00:42:20,190
そして、だけ覚えて、例えば、
最初のフレームと最後のフレーム、

897
00:42:20,190 --> 00:42:22,180
あなたがしている場合はキーフレーム
これまでに、単語を聞きました

898
00:42:22,180 --> 00:42:24,337
わずかに格納
蜂があるミドル。

899
00:42:24,337 --> 00:42:26,170
そして、あなたがする必要はありません
、ピンクのすべてを保存します

900
00:42:26,170 --> 00:42:28,330
そして青、及び
緑の値も同様に。

901
00:42:28,330 --> 00:42:31,200
だから、これはのみということです
圧縮はどこにでもあります。

902
00:42:31,200 --> 00:42:34,900
それは私たちがよく使うテクニックです
または許可されて、これらの日のために取ります。

903
00:42:34,900 --> 00:42:38,750
>> しかし、どのようにテキストを圧縮していますか？

904
00:42:38,750 --> 00:42:40,450
どのようにテキストを圧縮して行くのですか？

905
00:42:40,450 --> 00:42:45,410
さて、文字のそれぞれに
ASCIIは1バイト、または8ビットです。

906
00:42:45,410 --> 00:42:47,360
そして、それは一種のダム、右ですか？

907
00:42:47,360 --> 00:42:51,160
あなたはおそらく、Aを入力しているため
EとIとOとUたくさん

908
00:42:51,160 --> 00:42:55,270
より頻繁に、WまたはQまたはZ様より、
で、言語に応じて

909
00:42:55,270 --> 00:42:56,610
あなたは確かに書いています。

910
00:42:56,610 --> 00:42:59,600
そして、なぜ我々が使用しています
すべての文字のための8ビット、

911
00:42:59,600 --> 00:43:02,040
少なくとも含みます
人気の文字、右？

912
00:43:02,040 --> 00:43:05,300
以下のためのより少ないビットを使用しないのはなぜ
超人気の手紙、

913
00:43:05,300 --> 00:43:07,760
Eのように、物事はあなたが推測します
運命の輪の最初の、

914
00:43:07,760 --> 00:43:10,450
そして、のために多くのビットを使用します
あまり人気の手紙？

915
00:43:10,450 --> 00:43:10,950
なぜ？

916
00:43:10,950 --> 00:43:13,130
私達はちょうどしようとしているため、
あまり頻繁にそれらを使用しています。

917
00:43:13,130 --> 00:43:15,838
>> まあ、それはそこに持っていることが判明
これを行うために作られた試みであっ。

918
00:43:15,838 --> 00:43:18,630
そして、あなたはグレードからリコール場合
学校や高校、モールス信号。

919
00:43:18,630 --> 00:43:20,400
モールス信号は、ドットを持っています
ダッシュができること

920
00:43:20,400 --> 00:43:24,270
ワイヤに沿っとして送信
ある種の音や信号。

921
00:43:24,270 --> 00:43:25,930
しかし、モールス信号はスーパークリーンです。

922
00:43:25,930 --> 00:43:29,010
これは、バイナリシステムのようなものです
あなたは、ドットやダッシュを持っています。

923
00:43:29,010 --> 00:43:30,977
しかし、あなたは、例えば、2つのドットが表示された場合。

924
00:43:30,977 --> 00:43:33,810
それとも、オペレータに戻ってと思われる場合
誰がビープ音​​、ビープ音、ビープ音のようになり、

925
00:43:33,810 --> 00:43:36,760
ビープ音、少しトリガーを打ちます
それは、信号を送信し、

926
00:43:36,760 --> 00:43:40,360
あなたならば、受信者は、2を受け取り、
ドットは、あなたがどの​​ようなメッセージを受信しましたか？

927
00:43:40,360 --> 00:43:43,490
完全に任意。

928
00:43:43,490 --> 00:43:44,450
>> 私？

929
00:43:44,450 --> 00:43:45,060
私？

930
00:43:45,060 --> 00:43:47,500
または何about--またはI？

931
00:43:47,500 --> 00:43:49,570
多分それはちょうど2つのEの右でしたか？

932
00:43:49,570 --> 00:43:52,480
したがって、この問題があります
モールスでデコード可能の

933
00:43:52,480 --> 00:43:54,890
コー​​ド、それによってない限り
あなたのメッセージを送信した人

934
00:43:54,890 --> 00:43:59,510
実際にそのようにあなたが並べ替えることができます一時停止
参照または文字間のギャップを聞き、

935
00:43:59,510 --> 00:44:02,990
それだけに十分ではありません
0と1のストリームを送信し、

936
00:44:02,990 --> 00:44:05,610
ドットやダッシュや、
曖昧さがありますので。

937
00:44:05,610 --> 00:44:08,640
Eは単一のドットであるので、あなたの場合
2つのドットを参照するか、2つのドットを聞き、

938
00:44:08,640 --> 00:44:11,254
多分それは2つの電子のですか多分それは1 I.です

939
00:44:11,254 --> 00:44:13,670
だから我々はのシステムを必要とします
それよりももう少し賢いです。

940
00:44:13,670 --> 00:44:16,851
だから、男の名前ハフマン年
前まさにこの思い付きました。

941
00:44:16,851 --> 00:44:18,600
だから我々はちょうどつもりです
チラッを取ります

942
00:44:18,600 --> 00:44:20,114
どのように木はこれに密接な関係がある。

943
00:44:20,114 --> 00:44:22,530
これはいくつかあるとし
あなたが送信する愚かなメッセージ、

944
00:44:22,530 --> 00:44:26,342
ただ、A、B、CのDのとEのから構成され、
しかし、冗長性の多くはここにあります。

945
00:44:26,342 --> 00:44:27,550
これは、英語であることを意味していません。

946
00:44:27,550 --> 00:44:28,341
これは、暗号化されていません。

947
00:44:28,341 --> 00:44:30,540
それはちょうど愚かなメッセージです
繰り返しの多いです。

948
00:44:30,540 --> 00:44:34,010
ですから、実際にすべてのアウトカウント場合
A、Bの、Cの、Dの、およびEの、ここです

949
00:44:34,010 --> 00:44:34,890
周波数。

950
00:44:34,890 --> 00:44:37,800
文字の20％です
手紙の45％

951
00:44:37,800 --> 00:44:39,660
Eさん、3他の周波数です。

952
00:44:39,660 --> 00:44:41,960
我々は、手動であっカウントアップ
ちょうど数学をしました。

953
00:44:41,960 --> 00:44:44,579
>> だから、ことが判明
ハフマン、いくつかの時間前に、

954
00:44:44,579 --> 00:44:46,620
あなたが知っている、ことを実現
何を、私は建物を起動した場合

955
00:44:46,620 --> 00:44:51,172
木、または木の森、あなたがする場合は、
次のように、私は次の操作を行うことができます。

956
00:44:51,172 --> 00:44:53,880
私はそれぞれにノードを与えるつもりです
私が気に手紙の

957
00:44:53,880 --> 00:44:55,530
私は保存するつもりです
そのノードの内部

958
00:44:55,530 --> 00:44:58,610
浮動小数点として周波数
値は、またはあなたは、あまりにも、Nそれを使用することができます

959
00:44:58,610 --> 00:45:00,210
しかし、我々はちょうどここにフロートを使用します。

960
00:45:00,210 --> 00:45:03,100
そして、そのアルゴリズム
彼は提案しますということです

961
00:45:03,100 --> 00:45:07,210
単一ノードのこの森を取ります
木なので、超短木、

962
00:45:07,210 --> 00:45:11,920
そしてあなたがそれらを接続開始します
新しいグループ、新しい両親​​、可能ならば。

963
00:45:11,920 --> 00:45:16,150
そして、あなたが選択することによってこれを行います
一度に2最小周波数。

964
00:45:16,150 --> 00:45:18,110
だから私は、10％と10％を取りました。

965
00:45:18,110 --> 00:45:19,090
私は、新しいノードを作成します。

966
00:45:19,090 --> 00:45:20,910
そして、私は20％の新しいノードを呼び出します。

967
00:45:20,910 --> 00:45:22,750
>> どの二つのノード私は次の組み合わせ？

968
00:45:22,750 --> 00:45:23,810
それは少しあいまいです。

969
00:45:23,810 --> 00:45:26,643
だから、いくつかのコーナーケースがあります
検討したが、かなりのものを維持するために、

970
00:45:26,643 --> 00:45:29,300
私は20％を選択するつもりです - 
私は今、子供たちを無視します。

971
00:45:29,300 --> 00:45:33,640
私は20％を選択するつもりだと
15％と、2つの新しいエッジを描きます。

972
00:45:33,640 --> 00:45:35,624
そして今、これは、2つのノード
私は論理的に結合するのですか？

973
00:45:35,624 --> 00:45:38,540
すべての子を無視し、すべての
孫は、ちょうど根を見て

974
00:45:38,540 --> 00:45:39,070
今。

975
00:45:39,070 --> 00:45:42,220
私は、どの2つのノードが一緒に結ぶのですか？

976
00:45:42,220 --> 00:45:44,530
ポイント2と0.35。

977
00:45:44,530 --> 00:45:45,890
だから私は、2つの新しいエッジを描画してみましょう。

978
00:45:45,890 --> 00:45:47,570
そして、私は唯一の左を持っています。

979
00:45:47,570 --> 00:45:48,650
だからここツリーです。

980
00:45:48,650 --> 00:45:51,160
そして、それは意図的に描かれています
種類のかわいい探すために、

981
00:45:51,160 --> 00:45:55,870
しかし、エッジが持っていることに気づきます
また、0と1のラベル付けされて。

982
00:45:55,870 --> 00:45:59,510
だから、左エッジのすべてがゼロであります
任意に、しかし、一貫して。

983
00:45:59,510 --> 00:46:01,170
すべての権利エッジはものです。

984
00:46:01,170 --> 00:46:05,070
>> そしてそうホフマンは、提案されているもの
あなたはBを表現したい場合は、

985
00:46:05,070 --> 00:46:10,080
数66を表すのではなく、
8全ビットであるアスキー、

986
00:46:10,080 --> 00:46:13,360
あなたは何、ちょうど店を知っています
パターンゼロ、ゼロ、ゼロ、

987
00:46:13,360 --> 00:46:17,030
ゼロ、それはパスだから
私のツリーから、氏ハフマンの木、

988
00:46:17,030 --> 00:46:18,600
ルートからリーフまで。

989
00:46:18,600 --> 00:46:20,970
あなたが保存したい場合は
Eは、対照的に、しないでください

990
00:46:20,970 --> 00:46:26,290
E.を表す8ビットを送信します
代わりに、ビットのどのパターンを送信しますか？

991
00:46:26,290 --> 00:46:26,890
1。

992
00:46:26,890 --> 00:46:30,410
そして、これがあるのいいものです
そのEは最も人気のある文字です、

993
00:46:30,410 --> 00:46:32,340
あなたが使用しています
それのための最短のコード。

994
00:46:32,340 --> 00:46:34,090
次の最も人気のあります
手紙はそれのように見えます

995
00:46:34,090 --> 00:46:37,380
A.だったので、どのように多くのビット
彼はそのために使用して提案したのですか？

996
00:46:37,380 --> 00:46:38,270
ゼロ、1。

997
00:46:38,270 --> 00:46:41,060
>> そして、それは実現していますので、
今のところ、この木のように

998
00:46:41,060 --> 00:46:43,350
私はあります規定しましょう
モールスのように曖昧ません

999
00:46:43,350 --> 00:46:46,090
コー​​ド、すべての理由
あなたが気に手紙

1000
00:46:46,090 --> 00:46:48,780
これらのエッジの端部にあります。

1001
00:46:48,780 --> 00:46:50,580
だから、ただ一つです
木の応用。

1002
00:46:50,580 --> 00:46:52,538
これはis--と私は波よ
どのようにこの時私の手

1003
00:46:52,538 --> 00:46:55,570
C構造体としてこれを実装する場合があります。

1004
00:46:55,570 --> 00:46:58,260
私達はちょうど結合する必要があります
記号、文字のような、

1005
00:46:58,260 --> 00:46:59,910
左右での周波数。

1006
00:46:59,910 --> 00:47:02,510
しかし、ここでは、2つを見てみましょう
最後の例あなたはよ

1007
00:47:02,510 --> 00:47:06,070
後にはかなり慣れます
問題でクイズゼロが5に設定します。

1008
00:47:06,070 --> 00:47:09,210
>> そのようにデータ構造が存在します
ハッシュテーブルとして知られています。

1009
00:47:09,210 --> 00:47:12,247
そして、ハッシュテーブルは一種のです
それはバケツを持っていることで冷却し​​ます。

1010
00:47:12,247 --> 00:47:14,830
そして、4バケットがあると仮定し
ここでは、わずか4空白。

1011
00:47:14,830 --> 00:47:20,830
ここでは、カードのデッキだと、ここにあります
クラブ、スペード、クラブ、ダイヤモンド、クラブ、

1012
00:47:20,830 --> 00:47:25,960
ダイヤモンド、クラブ、ダイヤモンド、
clubs--ので、これはランダムです。

1013
00:47:25,960 --> 00:47:30,330
ハーツ、hearts--ので、私はよ
ここではすべての入力をbucketizing。

1014
00:47:30,330 --> 00:47:32,430
ハッシュテーブルのニーズ
あなたの入力を見て、

1015
00:47:32,430 --> 00:47:34,850
して、一定に入れ
あなたが見たものに基づいて配置します。

1016
00:47:34,850 --> 00:47:35,600
それはアルゴリズムです。

1017
00:47:35,600 --> 00:47:37,980
そして、私はスーパーを使用していました
簡単な目視アルゴリズム。

1018
00:47:37,980 --> 00:47:40,030
最も難しい部分はありました
写真は何であったか覚えて。

1019
00:47:40,030 --> 00:47:41,590
そして、合計4つのものがあります。

1020
00:47:41,590 --> 00:47:45,440
>> 今スタックは、成長しました
ここでは意図的な設計上のものです。

1021
00:47:45,440 --> 00:47:46,540
しかし、私は他に何を行う可能性がありますか？

1022
00:47:46,540 --> 00:47:49,080
だから、実際にここで私たちが持っています
古い学校の試験の本の束。

1023
00:47:49,080 --> 00:47:51,240
の束と仮定
学生の名前はここにあります。

1024
00:47:51,240 --> 00:47:52,570
ここで大きなハッシュテーブルです。

1025
00:47:52,570 --> 00:47:54,867
代わりに、バケットが4つの、
私が持っている、のは、26をしましょう​​。

1026
00:47:54,867 --> 00:47:57,950
そして、我々は26を借りに行きたくありませんでした
外[からのもの？アネンバーグ？]ので、

1027
00:47:57,950 --> 00:48:00,289
ここで表す5です
〜Zのそして私の場合

1028
00:48:00,289 --> 00:48:03,580
その名で始まり、学生を参照してください、
私はそこに彼または彼女のクイズを置くつもりです。

1029
00:48:03,580 --> 00:48:08,850
誰かがCで始まる場合、あそこ、
A--実際に、それを行うにはしたくありませんでした。

1030
00:48:08,850 --> 00:48:10,060
Bは、ここを乗り越えます。

1031
00:48:10,060 --> 00:48:13,390
だから私は、AとBとCを持っていると
今ここに他の生徒です。

1032
00:48:13,390 --> 00:48:16,212
このハッシュ・テーブルがある場合
配列で実装、

1033
00:48:16,212 --> 00:48:17,920
私は種類のネジ止めています
この時点で、右？

1034
00:48:17,920 --> 00:48:19,510
私は一種のこのどこかに配置する必要があります。

1035
00:48:19,510 --> 00:48:24,380
>> だから私はこの問題を解決することができます一つの方法はすべて、あります
右、Aがビジー状態である、Bがビジーである、Cがビジー状態です。

1036
00:48:24,380 --> 00:48:28,880
私は、だからDに彼を置くつもりです
最初、私はランダム瞬時にアクセスを持っています

1037
00:48:28,880 --> 00:48:31,064
学生のためのバケットのそれぞれに。

1038
00:48:31,064 --> 00:48:33,230
しかし、今では、委譲のようなものです
何かリニアに、

1039
00:48:33,230 --> 00:48:36,750
私は誰かを検索する場合のため
名前がAで始まる、私はここで確認してください。

1040
00:48:36,750 --> 00:48:38,854
しかし、これはAでない場合
私が探している学生、

1041
00:48:38,854 --> 00:48:41,520
私は種類のチェックを開始する必要があります
バケツ、私がやったので、

1042
00:48:41,520 --> 00:48:44,530
ソートの直線的でした
データ構造を調べます。

1043
00:48:44,530 --> 00:48:47,710
ちょうど見えるというのが愚かな方法
最初に使用可能な開口部のために、

1044
00:48:47,710 --> 00:48:51,850
そして、、いわば、プランBと置きます
この場合、またはプランD、値

1045
00:48:51,850 --> 00:48:53,340
その場所に代わりに。

1046
00:48:53,340 --> 00:48:56,470
あなたがきた場合、これはちょうどようにあります
26場所となしの学生を持って

1047
00:48:56,470 --> 00:49:00,600
名前のQまたはZ、またはのようなもので
ことは、少なくともあなたは、スペースを使用しています。

1048
00:49:00,600 --> 00:49:03,140
>> しかし、我々はすでに、より多くのを見てきました
ここに巧妙なソリューションは、右？

1049
00:49:03,140 --> 00:49:04,870
あなたの代わりに何をするだろう
あなたは衝突を持っている場合はどうなりますか？

1050
00:49:04,870 --> 00:49:06,670
二人が持っている場合
何だろう名A、

1051
00:49:06,670 --> 00:49:09,160
賢く以上となっています
ちょうどより直感的なソリューション

1052
00:49:09,160 --> 00:49:12,840
DがあることになっているAを入れて？

1053
00:49:12,840 --> 00:49:14,810
なぜ私は行っていません
[外？アネンバーグ？]、

1054
00:49:14,810 --> 00:49:19,960
malloc関数、他のノードのように、それを置きます
ここで、その後、ここで学生ということに置きます。

1055
00:49:19,960 --> 00:49:22,120
私は基本的に持っているように、
配列のいくつかの種類、

1056
00:49:22,120 --> 00:49:25,590
または私たちがしているように、多分よりエレガント
リンクリストを見るために開始。

1057
00:49:25,590 --> 00:49:29,520
>> だからハッシュテーブルは構造体であります
それは、ちょうどこのようになります。

1058
00:49:29,520 --> 00:49:33,900
しかし、より巧みに、あなたが何かと呼ばれます
別々の連鎖、それによってハッシュテーブル

1059
00:49:33,900 --> 00:49:38,340
非常に単純にアレイの各々は、あります
その要素数ではありません、

1060
00:49:38,340 --> 00:49:40,470
それ自体は、リンクされたリストです。

1061
00:49:40,470 --> 00:49:45,080
あなたは超高速アクセスを得るようにするには
ここにあなたの価値をハッシュを決めます。

1062
00:49:45,080 --> 00:49:48,059
多くのカードの例と同様に、
私は超迅速な意思決定をしました。

1063
00:49:48,059 --> 00:49:49,600
ハーツダイヤモンドはここに、ここに行きます。

1064
00:49:49,600 --> 00:49:52,180
ここでは同じ、Aは、ここに行きます
DはBはここに、ここに行きます。

1065
00:49:52,180 --> 00:49:55,740
だから、超高速ルックアップ、および場合
あなたはケースに遭遇してしまいました

1066
00:49:55,740 --> 00:49:59,429
あなたが持っている衝突、2
同じ名前の人たち、よくして

1067
00:49:59,429 --> 00:50:00,970
あなたはそれらをリンク開始します。

1068
00:50:00,970 --> 00:50:03,900
そして多分あなたはそれらをソートしておきます
アルファベット順に、多分あなたはしないでください。

1069
00:50:03,900 --> 00:50:05,900
しかし、少なくとも今はダイナミズムを持っています。

1070
00:50:05,900 --> 00:50:10,250
だから、一方で我々は、超高速の持っています
一定時間、および線形時間の種類

1071
00:50:10,250 --> 00:50:14,110
これらのリンクリスト場合関与
少し長くなるが開始されます。

1072
00:50:14,110 --> 00:50:16,880
>> だから、愚かなこの種の、
マニアックなジョーク年前。

1073
00:50:16,880 --> 00:50:19,590
CS50ハック - ソンでは、
学生はチェックインの際、

1074
00:50:19,590 --> 00:50:22,040
いくつかのTFまたはCA毎年
それは我慢し面白いと思っ

1075
00:50:22,040 --> 00:50:27,772
このような記号、それだけ
あなたの名前がAで始まる場合を意味し、

1076
00:50:27,772 --> 00:50:28,870
この道を行きます。

1077
00:50:28,870 --> 00:50:31,110
あなたの名前が開始された場合
Bで、this-- [OK]を移動し、

1078
00:50:31,110 --> 00:50:33,290
それは多分、後学期で面白いです。

1079
00:50:33,290 --> 00:50:36,420
しかし、別のがあります
あまりにも、これを行う方法。

1080
00:50:36,420 --> 00:50:37,410
バックそれに来ます。

1081
00:50:37,410 --> 00:50:38,600
>> したがって、この構造があります。

1082
00:50:38,600 --> 00:50:40,420
そして、これが私たちの最後です
今日のための構造、

1083
00:50:40,420 --> 00:50:42,400
これはトライと呼ばれるものです。

1084
00:50:42,400 --> 00:50:47,140
何らかの理由で短いT-R-I-E、
検索のために、それはトライと呼ばれています。

1085
00:50:47,140 --> 00:50:51,389
だから、トライは別の興味深いです
これらのアイデアの多くのアマルガム。

1086
00:50:51,389 --> 00:50:52,930
それは、今まで見てきた木、です。

1087
00:50:52,930 --> 00:50:54,180
これは、二分探索木ではありません。

1088
00:50:54,180 --> 00:50:58,410
それは、子どもの任意の数の木です
トライの子供のが、各

1089
00:50:58,410 --> 00:51:00,090
配列です。

1090
00:51:00,090 --> 00:51:04,790
サイズの配列、言う、26または多分27
あなたはハイフネーションされた名前をサポートする場合

1091
00:51:04,790 --> 00:51:06,790
または人の名前でアポストロフィ。

1092
00:51:06,790 --> 00:51:08,280
>> そしてこれは、データ構造です。

1093
00:51:08,280 --> 00:51:10,290
そして、あなたは上から見ると
下に、あなたの場合のように

1094
00:51:10,290 --> 00:51:13,710
であり、そこにトップノード、Mを見て
そこに一番左のものを指し、

1095
00:51:13,710 --> 00:51:17,665
次いで、A、X、W、E、Lは、Lが、これはです
任意にそのちょうどデータ構造

1096
00:51:17,665 --> 00:51:19,120
人の名前を記憶しています。

1097
00:51:19,120 --> 00:51:25,720
そして、マクスウェルはちょうど次によって保存されています
配列への配列への配列のパス。

1098
00:51:25,720 --> 00:51:30,050
トライは約しかし、驚くべきものです
リンクリストのに対し、さらには、その

1099
00:51:30,050 --> 00:51:34,520
アレイは、私たちが今まで得てきた最高です
線形時間または対数時間探し

1100
00:51:34,520 --> 00:51:35,600
誰かアップ。

1101
00:51:35,600 --> 00:51:40,530
トライのこのデータ構造で、もし
私のデータ構造は、その内の1つの名前を持っています

1102
00:51:40,530 --> 00:51:43,720
私はマクスウェルを探しています、私はよ
かなり迅速に彼を見つけるつもり。

1103
00:51:43,720 --> 00:51:47,910
私は、M-A-X-W-E-L-Lを探します。もし
このデータ構造は、対照的に、

1104
00:51:47,910 --> 00:51:51,830
あるかどうか、Nは、万人である場合
このデータ構造100万名、

1105
00:51:51,830 --> 00:51:57,100
マクスウェルはまだあることを行っています
ただ、M-A-X-W-E-L-Lの後に発見

1106
00:51:57,100 --> 00:51:58,090
ステップ。

1107
00:51:58,090 --> 00:52:01,276
そしてDavid-- D-A-V-I-Dの手順を実行します。

1108
00:52:01,276 --> 00:52:03,400
言い換えれば、構築することにより、
データ構造

1109
00:52:03,400 --> 00:52:07,240
そのすべてが、これらの配列のすべてを、持って
それ自体は、ランダムアクセスをサポート

1110
00:52:07,240 --> 00:52:11,090
私は人々ののを見て開始することができます
な時間の量を使用して名前

1111
00:52:11,090 --> 00:52:14,340
ない数に比例
データ構造内のものの、

1112
00:52:14,340 --> 00:52:16,330
百既存の名前のように。

1113
00:52:16,330 --> 00:52:20,135
それを見つけるために私を要する時間
M-A-X-W-E-L-Lこのデータ構造であります

1114
00:52:20,135 --> 00:52:22,260
比例せずに
データ構造のサイズは、

1115
00:52:22,260 --> 00:52:25,930
しかし、名前の長さ。

1116
00:52:25,930 --> 00:52:28,440
そして現実的に
私たちが見上げている名前

1117
00:52:28,440 --> 00:52:29,970
長いクレイジーになるだろうことはありません。

1118
00:52:29,970 --> 00:52:32,600
たぶん誰かが10文字を持っています
、20文字の名前です。

1119
00:52:32,600 --> 00:52:33,900
それは右、確かに有限ですか？

1120
00:52:33,900 --> 00:52:37,110
地球上の人間が誰ですか
可能な限り長い名前を持っています、

1121
00:52:37,110 --> 00:52:39,920
しかし、その名前は一定であります
値の長さは、右？

1122
00:52:39,920 --> 00:52:41,980
それは、いかなる意味においても変化しません。

1123
00:52:41,980 --> 00:52:45,090
だから、このように、我々はしました
データ構造を達成し

1124
00:52:45,090 --> 00:52:47,800
それは、一定の時間ルックアップです。

1125
00:52:47,800 --> 00:52:50,670
これは、ステップ数を取るん
入力の長さに応じて、

1126
00:52:50,670 --> 00:52:54,250
しかし、名前の数ではありません
データ構造です。

1127
00:52:54,250 --> 00:52:58,700
だから我々は、名前の数を倍増場合
億から20億に来年、

1128
00:52:58,700 --> 00:53:03,720
マクスウェルを見つけること取るために起こっています
7つのステップの正確な同じ数

1129
00:53:03,720 --> 00:53:04,650
彼を見つけることができます。

1130
00:53:04,650 --> 00:53:08,810
そして、私たちは達成しているように見えます
時間を実行している私たちの聖杯。

1131
00:53:08,810 --> 00:53:10,860
>> だから、迅速な発表のカップル。

1132
00:53:10,860 --> 00:53:11,850
クイズゼロが来ています。

1133
00:53:11,850 --> 00:53:14,600
コー​​スのウェブサイト上でその上のその他の
日の次のカップルを超えます。

1134
00:53:14,600 --> 00:53:17,120
月曜日のそれは休日ですlecture--
ここでハーバード大学の月曜日に。

1135
00:53:17,120 --> 00:53:18,850
これは、ニューヘブンではありません
私たちはクラスを取っています

1136
00:53:18,850 --> 00:53:20,310
月曜日の講義のためのニューヘブンに。

1137
00:53:20,310 --> 00:53:22,550
すべてが撮影されます
そして、、いつものように、ライブストリーミング

1138
00:53:22,550 --> 00:53:24,900
しかし、今日は終了してみましょう
30秒のクリップで

1139
00:53:24,900 --> 00:53:26,910
「ディープ思考」と呼ばれます
祈るファーナム、これによって、

1140
00:53:26,910 --> 00:53:30,850
土曜日昨年触発されました
ナイト・ライブの「ディープ思考」

1141
00:53:30,850 --> 00:53:35,700
ジャック・ハンディ、これによって、
今の意味を確認する必要があります。

1142
00:53:35,700 --> 00:53:38,810
>> FILM：そして今、「ディープ
祈るファーナムによって思考」。

1143
00:53:38,810 --> 00:53:42,100

1144
00:53:42,100 --> 00:53:42,870
ハッシュテーブル。

1145
00:53:42,870 --> 00:53:45,940

1146
00:53:45,940 --> 00:53:47,660
>> SPEAKER 1：すべての権利、それは今のところこれだけです。

1147
00:53:47,660 --> 00:53:48,805
私たちは来週お会いしましょう​​。

1148
00:53:48,805 --> 00:53:55,380

1149
00:53:55,380 --> 00:53:56,680
>> DOUG：アクションでそれを見るために。

1150
00:53:56,680 --> 00:53:58,304
それでは、今それを見てみましょう。

1151
00:53:58,304 --> 00:53:59,890
そこでここでは、我々は、ソートされていない配列を持っています。

1152
00:53:59,890 --> 00:54:04,860
>> IAN：ダグ、あなたが先に行くことができますし、再起動
ちょうど1秒これでお願いします。

1153
00:54:04,860 --> 00:54:08,562
すべての権利は​​、カメラがそのように、展開しています
あなたは準備ができているときはいつでも、アクション、ダグ、OK？

1154
00:54:08,562 --> 00:54:11,020
DOUG：すべての権利なので、私たち
ここでソートされていない配列である必要があります。

1155
00:54:11,020 --> 00:54:13,960
そして、私はすべての要素を着色しました
それが実際にあることを示すために赤、

1156
00:54:13,960 --> 00:54:14,460
ソートされていません。

1157
00:54:14,460 --> 00:54:17,960
そこで、まず私たちが行うことを思い出してください
私たちは、アレイの左半分を並べ替えるです。

1158
00:54:17,960 --> 00:54:20,630
その後、我々は権利を並べ替えます
配列の半分。

1159
00:54:20,630 --> 00:54:22,830
そして、YA-DA、YA-DA、YA-DA、
私たちはそれらを一緒にマージされます。

1160
00:54:22,830 --> 00:54:24,520
そして、我々は完全にソートされた配列を持っています。

1161
00:54:24,520 --> 00:54:25,360
だから、働くマージソート方法です。

1162
00:54:25,360 --> 00:54:27,109
>> IAN：おっ、おっ、おっ、
カット、カット、カット、カットします。

1163
00:54:27,109 --> 00:54:30,130
ダグ、あなただけのYA-DAことはできませんが、YA-DA、
YA-DA、マージソートを通してあなたの方法。

1164
00:54:30,130 --> 00:54:31,970
>> DOUG：私はちょうどでした。

1165
00:54:31,970 --> 00:54:32,832
それは大丈夫です。

1166
00:54:32,832 --> 00:54:33,540
私たちは行ってもいいです。

1167
00:54:33,540 --> 00:54:34,760
ちょうどローリングを維持しましょう​​。

1168
00:54:34,760 --> 00:54:35,380
とにかく、

1169
00:54:35,380 --> 00:54:37,800
>> IAN：あなたは説明する必要があります
それより完全にそれよりも。

1170
00:54:37,800 --> 00:54:39,999
それはちょうど十分ではありません。

1171
00:54:39,999 --> 00:54:41,790
DOUG：イアン、私たちにはありません
1に戻って行く必要があります。

1172
00:54:41,790 --> 00:54:42,350
それは大丈夫です。

1173
00:54:42,350 --> 00:54:45,690
とにかく、我々はmerge--を続ける場合
イアンは、我々は撮影の真ん中にいます。

1174
00:54:45,690 --> 00:54:46,612
>> IAN：私は知っています。

1175
00:54:46,612 --> 00:54:49,320
そして、私たちはただYA-DAことはできませんが、YA-DA、
プロセス全体を通してYA-DA、。

1176
00:54:49,320 --> 00:54:52,200
あなたはどのように説明する必要があります
両者を一緒にマージされます。

1177
00:54:52,200 --> 00:54:53,570
>> DOUG：しかし、我々はすでにしました
説明方法2 sides--

1178
00:54:53,570 --> 00:54:55,321
>> IAN：あなただけ示してきました
それらマージ配列。

1179
00:54:55,321 --> 00:54:56,486
DOUG：彼らは、プロセスを知っています。

1180
00:54:56,486 --> 00:54:57,172
彼らはいいですよ。

1181
00:54:57,172 --> 00:54:58,380
私たちは、その上に10回行ってきました。

1182
00:54:58,380 --> 00:55:00,330
>> IAN：あなたはちょうどその上にスキップ。

1183
00:55:00,330 --> 00:55:03,360
私たちは、1に戻るつもりだ、あなた
あなたYA-DA、YA-DAそれ以上のことはできません。

1184
00:55:03,360 --> 00:55:05,480
1つ前に、すべての権利。

1185
00:55:05,480 --> 00:55:07,833
>> DOUG：私は戻って行かなければなりません
スライドのすべてを？

1186
00:55:07,833 --> 00:55:08,332
我が神よ。

1187
00:55:08,332 --> 00:55:11,008

1188
00:55:11,008 --> 00:55:13,004
これは6回目、イアンのようなものです。

1189
00:55:13,004 --> 00:55:13,940
それは大丈夫です。

1190
00:55:13,940 --> 00:55:15,200
>> IAN：すべての権利。

1191
00:55:15,200 --> 00:55:16,590
あなたは〜を用意する？

1192
00:55:16,590 --> 00:55:17,400
グレート。

1193
00:55:17,400 --> 00:55:18,950
アクション。