1
00:00:00,000 --> 00:00:12,040
>> [Musik spiller]

2
00:00:12,040 --> 00:00:16,460
>> SPEAKER 1: Okay, det er CS50,
og dette er begyndelsen af ​​uge fire,

3
00:00:16,460 --> 00:00:20,420
og som du måske har hørt eller
læse, har verden slutter.

4
00:00:20,420 --> 00:00:23,520
Går alle rundt på internettet
har været viden og bevidsthed

5
00:00:23,520 --> 00:00:27,100
af en fejl i et program, en
programmeringssprog kaldet Bash.

6
00:00:27,100 --> 00:00:32,729
Det har været vidunderligt mærkevarer
som Shellshock eller Bash døren,

7
00:00:32,729 --> 00:00:35,485
men artikler som disse
har ikke været ualmindeligt.

8
00:00:35,485 --> 00:00:38,807
Og i virkeligheden, mange af dem bringe
tilbage minderne om Heartbleed,

9
00:00:38,807 --> 00:00:41,640
som du måske har bemærket i
trykke tilbage denne sidste forår, som

10
00:00:41,640 --> 00:00:43,980
var ligeledes temmelig dramatisk.

11
00:00:43,980 --> 00:00:47,110
Nu er de af jer her
i dag, hvor mange af jer har,

12
00:00:47,110 --> 00:00:50,330
selv hvis du ikke forstår, hvad
det hele handler om, hørt om Shellshock?

13
00:00:50,330 --> 00:00:51,370

14
00:00:51,370 --> 00:00:54,245
Okay, og hvor mange af jer
har computere, som er sårbare?

15
00:00:54,245 --> 00:00:55,680

16
00:00:55,680 --> 00:01:00,250
OK, bør der være langt, langt flere hænder
op lige nu, vi grunde skal se.

17
00:01:00,250 --> 00:01:02,580
>> Lad os tage et kig på, hvad der er
stået på i medierne

18
00:01:02,580 --> 00:01:05,304
og derefter forklare det lidt
her for os teknisk.

19
00:01:05,304 --> 00:01:07,670

20
00:01:07,670 --> 00:01:11,250
>> SPEAKER 2: Sikkerhed eksperter har
advarede om, at en alvorlig fejl kunne

21
00:01:11,250 --> 00:01:15,650
være ved at påvirke hundredvis af
millioner af verdens internetbrugere.

22
00:01:15,650 --> 00:01:20,600
Så hvad er den fejl, der har været
eftersynkroniseret Shellshock, og hvad gør den?

23
00:01:20,600 --> 00:01:23,720

24
00:01:23,720 --> 00:01:28,910
Nå, er Shellshock også kendt som
Bash bug, den software, der udnytter.

25
00:01:28,910 --> 00:01:33,230
Hackere bruger virus til at scanne sårbar
systemer, der kører Linux og Unix

26
00:01:33,230 --> 00:01:36,300
operativsystemer og derefter inficere dem.

27
00:01:36,300 --> 00:01:38,730
Bash er en kommandolinje shell.

28
00:01:38,730 --> 00:01:43,460
Dette lader brugerne sende kommandoer til at lancere
programmer og funktioner i softwaren

29
00:01:43,460 --> 00:01:45,250
ved at skrive i teksten.

30
00:01:45,250 --> 00:01:49,980
Det er typisk bruges af programmører, og
bør ikke være åben over for den øvrige verden,

31
00:01:49,980 --> 00:01:51,590
selvom Shellshock ændrer det.

32
00:01:51,590 --> 00:01:54,160

33
00:01:54,160 --> 00:01:57,910
>> Nå, worringly, nogle analytikere
advare det kunne være en større trussel,

34
00:01:57,910 --> 00:02:01,580
fordi Shellshock tillader fuldstændig
kontrol over en inficeret maskine,

35
00:02:01,580 --> 00:02:06,030
hvorimod Heartbleed kun tilladt
hackere til at spionere på computere.

36
00:02:06,030 --> 00:02:09,130
Det er så alvorligt, det er
blevet klassificeret en 10 ud af 10

37
00:02:09,130 --> 00:02:11,900
til sværhedsgraden af ​​National
Sårbarhed Database.

38
00:02:11,900 --> 00:02:15,530

39
00:02:15,530 --> 00:02:20,015
2/3 af alle web-servere er i
risiko, herunder nogle Mac-computere.

40
00:02:20,015 --> 00:02:22,760

41
00:02:22,760 --> 00:02:25,600
Nå, skal du sørge
lappe dine systemer nu.

42
00:02:25,600 --> 00:02:29,330
Enhver vært for et websted kørende
de berørte operativsystemer

43
00:02:29,330 --> 00:02:31,800
bør træffe foranstaltninger så hurtigt som muligt.

44
00:02:31,800 --> 00:02:35,390
Enhver, der har råd til det skal se
til deres ansøgning overvågning og web

45
00:02:35,390 --> 00:02:37,355
firewalls til at se ud for eventuelle angreb.

46
00:02:37,355 --> 00:02:39,979

47
00:02:39,979 --> 00:02:41,770
SPEAKER 3: Værste
der kan ske, er

48
00:02:41,770 --> 00:02:45,080
at nogen ville skrive kode,
automatisk ville gå og scanne

49
00:02:45,080 --> 00:02:48,280
internettet og ville påvirke
alle disse computere.

50
00:02:48,280 --> 00:02:50,710
Og når de gør det, ja,
det værste de kunne gøre

51
00:02:50,710 --> 00:02:53,300
er bare slette alt,
eller lukke de steder ned.

52
00:02:53,300 --> 00:02:55,360
Så kunne vi se skade
fra det synspunkt,

53
00:02:55,360 --> 00:02:58,300
hvor vi ville have ondsindede personer
der bare beslutte at skabe kaos

54
00:02:58,300 --> 00:03:02,534
ved at bringe systemer ned eller slette
filer, og ting som.

55
00:03:02,534 --> 00:03:05,200
SPEAKER 2: Nogle siger, dette er en
af de mest vanskelige at måle

56
00:03:05,200 --> 00:03:08,080
bugs i år, og det
kan tage uger eller endda

57
00:03:08,080 --> 00:03:10,820
måneder til at bestemme dens endelige effekt.

58
00:03:10,820 --> 00:03:12,180

59
00:03:12,180 --> 00:03:15,560
>> SPEAKER 1: Så alt dette er sandt,
men det sjove er, at næsten alle

60
00:03:15,560 --> 00:03:18,330
af billedsprog, du lige har set,
bortset fra måske tastaturet,

61
00:03:18,330 --> 00:03:20,930
har intet at gøre med
overhovedet bug.

62
00:03:20,930 --> 00:03:23,960
Servere og ledninger og så videre,
Det er lidt tangentielt relateret,

63
00:03:23,960 --> 00:03:27,410
men kernen er det faktisk temmelig
velkendt, hvad der foregår her.

64
00:03:27,410 --> 00:03:30,050
Faktisk, lad mig gå ind
vores CS50 apparatet.

65
00:03:30,050 --> 00:03:32,910
Lad mig gå videre og maksimere
terminalvinduet her.

66
00:03:32,910 --> 00:03:36,020
Og gutter har brugt denne,
eller den integrerede version heraf,

67
00:03:36,020 --> 00:03:39,460
i Gedit med henblik på at skrive programmer,
indtaste kommandoer og så videre,

68
00:03:39,460 --> 00:03:43,690
og dette er faktisk, og har
været i ugevis, Bash, B-A-S-H.

69
00:03:43,690 --> 00:03:46,890
Dette er Bourne-igen shell,
der er bare en fancy måde at sige,

70
00:03:46,890 --> 00:03:50,220
dette er et program, der har en
blinker hurtig, effektiv,

71
00:03:50,220 --> 00:03:51,970
der sidder der venter
for input til dig.

72
00:03:51,970 --> 00:03:53,920
Og det er den kommando
line interface, via hvilken

73
00:03:53,920 --> 00:03:57,650
gutter har kørt kommandoer og
i sidste ende at kompilere og derefter køre

74
00:03:57,650 --> 00:03:58,400
programmer.

75
00:03:58,400 --> 00:04:01,320
>> Men Bash er også et programmeringssprog
sprog i følgende forstand.

76
00:04:01,320 --> 00:04:05,460
Du ved, at der er kommandoer som
cd og ls, og også clang og andre,

77
00:04:05,460 --> 00:04:09,580
men du kan definere dine egne kommandoer
ved at gennemføre dem i Bash.

78
00:04:09,580 --> 00:04:11,420
Nu er vi ikke kommer til at
gå i detaljer

79
00:04:11,420 --> 00:04:16,089
at Bash programmeringssprog, men
ved for eksempel, at i det øjeblik,

80
00:04:16,089 --> 00:04:17,607
der er ingen kommando kaldet "hej."

81
00:04:17,607 --> 00:04:19,440
Så det kan findes i
en af ​​disse pakker.

82
00:04:19,440 --> 00:04:20,856
Det er ikke installeret på min computer.

83
00:04:20,856 --> 00:04:21,870
Spørg din administrator.

84
00:04:21,870 --> 00:04:26,030
Men hvis jeg ønsker, at der skal være et program
kaldet "hej" i bash eller på min prompt,

85
00:04:26,030 --> 00:04:30,810
Jeg kan faktisk bruge syntaks, der er
helt ligesom C. Det er ikke helt det samme,

86
00:04:30,810 --> 00:04:35,020
men det ser temmelig ligner en
funktion, omend mangler nogle detaljer.

87
00:04:35,020 --> 00:04:38,090
Intet synes at ske,
men nu, hvis jeg skriver "hej"

88
00:04:38,090 --> 00:04:40,960
du kan faktisk skrive en
programmet, ikke i C, ikke i Java,

89
00:04:40,960 --> 00:04:44,280
ikke i et andet programmeringssprog
sprog, men i Bash selv.

90
00:04:44,280 --> 00:04:47,630
>> Nu centrale her er, at jeg skrev
navn, jeg ønskede at give denne nye kommando,

91
00:04:47,630 --> 00:04:50,820
og parentes er også
symbolsk for dette er en funktion.

92
00:04:50,820 --> 00:04:54,010
Som en sidebemærkning, kan du også gøre det sjovt
ting, og i virkeligheden, selv på Mac OS

93
00:04:54,010 --> 00:04:55,620
dette er et program kaldet Terminal.

94
00:04:55,620 --> 00:04:58,800
Det kommer indbygget i nogens
computer, der har en Mac i dette rum,

95
00:04:58,800 --> 00:05:03,640
og du kan gøre lignende ting i Mac
OS, men du kan gå mere end det.

96
00:05:03,640 --> 00:05:07,110
Og det er lidt tangential,
men det er lidt sjovt.

97
00:05:07,110 --> 00:05:09,715
Jeg blev mindet i morges,
når tænker dette igennem,

98
00:05:09,715 --> 00:05:13,279
af et lille spil jeg plejede at spille
med en af ​​CS50 tidligere TF'er

99
00:05:13,279 --> 00:05:16,570
hvorved helst, han ville gå væk fra
hans tastatur med sin skærm ulåst,

100
00:05:16,570 --> 00:05:23,611
Jeg vil udføre en kommando
ligesom denne-- "sige hej."

101
00:05:23,611 --> 00:05:26,610
Og nu helst han kom tilbage til sin
tastatur efter jeg ryddet skærmen

102
00:05:26,610 --> 00:05:27,985
og han ville sidde ned,
forsøge at gøre noget arbejde,

103
00:05:27,985 --> 00:05:29,250
vise indholdet af hans directory--

104
00:05:29,250 --> 00:05:29,510
>> [Audio Playback]

105
00:05:29,510 --> 00:05:30,010
>> Hallo.

106
00:05:30,010 --> 00:05:31,621

107
00:05:31,621 --> 00:05:32,120
Hej.

108
00:05:32,120 --> 00:05:35,030
>> SPEAKER 1: Så i retfærdighed,
Det var faktisk ikke "Hej."

109
00:05:35,030 --> 00:05:36,894
Det var normalt noget
mere beslægtet med at--

110
00:05:36,894 --> 00:05:37,560
[Audio Playback]

111
00:05:37,560 --> 00:05:37,750
-Beep.

112
00:05:37,750 --> 00:05:39,320
SPEAKER 1: --that jeg would--
så sin computer ville

113
00:05:39,320 --> 00:05:42,170
sværger på ham som helst, han faktisk
satte sig ved hans tastatur.

114
00:05:42,170 --> 00:05:46,265
Og meget hurtigt han regnet ud
ikke at forlade sin skærm ulåst.

115
00:05:46,265 --> 00:05:48,730
Men dette tyder slags
dumme sjov, som du

116
00:05:48,730 --> 00:05:50,210
kan have med noget som Bash.

117
00:05:50,210 --> 00:05:52,770
Men det er lidt mere
alvorlige, at være sikker på, end det.

118
00:05:52,770 --> 00:05:57,235
Og i virkeligheden, det er en af ​​de
farligste og mest langvarige bugs

119
00:05:57,235 --> 00:05:58,860
der virkelig har ramt verden globalt.

120
00:05:58,860 --> 00:06:02,060
Denne fejl har været omkring
for omkring 20 år,

121
00:06:02,060 --> 00:06:05,780
og du vil blive ramt i blot et
øjeblik af dens relative enkelhed.

122
00:06:05,780 --> 00:06:07,990
>> Så dette er en repræsentant
befaler, at hvis du

123
00:06:07,990 --> 00:06:10,448
ejer en Mac, bogstaveligt talt lige nu
når du har din låget åbent,

124
00:06:10,448 --> 00:06:12,940
du kan prøve at skrive ind i det
program kaldet Terminal.

125
00:06:12,940 --> 00:06:15,410
Terminal er under
Ansøgninger Utilities--

126
00:06:15,410 --> 00:06:18,790
for en gangs skyld, behøver Windows-brugere ikke behøver at
bekymre sig om denne særlige threat--

127
00:06:18,790 --> 00:06:22,310
men dem af jer med Mac-computere kan skrive
dette ind i et vindue som jeg vil gøre her,

128
00:06:22,310 --> 00:06:24,210
og hvis du skriver
at i dette program

129
00:06:24,210 --> 00:06:28,830
kaldet Terminal, ligesom jeg vil gøre nu,
hvis du ser ordet "sårbar"

130
00:06:28,830 --> 00:06:32,200
din computer er
sårbare over for udnyttelse.

131
00:06:32,200 --> 00:06:33,850
>> Nu hvad betyder det egentlig?

132
00:06:33,850 --> 00:06:35,870
Og det er ganske vist
nogle temmelig vanvittigt syntaks,

133
00:06:35,870 --> 00:06:39,050
men lad os i det mindste trække ud
nogle af de interessante aspekter.

134
00:06:39,050 --> 00:06:42,567
Så der er nogle syntaks, der ser
lidt bekendt, i det mindste fra C

135
00:06:42,567 --> 00:06:43,950
og programmering mere generelt.

136
00:06:43,950 --> 00:06:47,550
Jeg ser nogle parenteser,
semikolon, krøllede parenteser, og sådan,

137
00:06:47,550 --> 00:06:50,820
men det viser sig, at dette
dumme ting her i gult

138
00:06:50,820 --> 00:06:53,580
er i det væsentlige en funktion
det gør ingenting.

139
00:06:53,580 --> 00:06:57,840
Tyktarmen midler gøre ingenting, og det
semikolon betyder stoppe med at gøre ingenting.

140
00:06:57,840 --> 00:07:00,250
Så indersiden af ​​disse
krøllede parenteser, det faktum,

141
00:07:00,250 --> 00:07:02,440
at jeg har en lige
underskrive til venstre, dette

142
00:07:02,440 --> 00:07:05,500
er hovedsagelig at skabe
en kommando, eller en variabel,

143
00:07:05,500 --> 00:07:09,520
kaldet x, og tildele den
den gule smule kode der.

144
00:07:09,520 --> 00:07:14,040
Det kunne være noget lignende "ekko
hej "eller" siger bip "eller noget

145
00:07:14,040 --> 00:07:15,120
beslægtet med.

146
00:07:15,120 --> 00:07:17,780
Men bemærk hvis dine øjne
vandre længere til højre,

147
00:07:17,780 --> 00:07:22,150
der er mere til denne linje end
bare slutningen af ​​denne semikolon.

148
00:07:22,150 --> 00:07:25,160
"Echo sårbar" og derefter
ud over at der er endnu mere.

149
00:07:25,160 --> 00:07:26,530
Andet semikolon, bash -c :.

150
00:07:26,530 --> 00:07:28,120

151
00:07:28,120 --> 00:07:34,050
>> Så lang historie kort,
denne linje kode er

152
00:07:34,050 --> 00:07:36,660
tilstrækkelig til overbevisende
en computer, der er

153
00:07:36,660 --> 00:07:39,830
sårbare over for at gøre noget
at du vil have det at gøre,

154
00:07:39,830 --> 00:07:44,290
fordi der er en fejl i Bash hvorved
selvom Bash skulle stoppe

155
00:07:44,290 --> 00:07:48,980
læsning kommandoveje ret
der efter den gule tekst,

156
00:07:48,980 --> 00:07:52,520
for en 20-plus år gamle fejl,
Bash har faktisk været at læse

157
00:07:52,520 --> 00:07:56,780
ud over dette semikolon og temmelig
meget at gøre, hvad det er fortalt.

158
00:07:56,780 --> 00:07:59,070
>> Så hvad er konsekvenserne
af denne i sidste ende?

159
00:07:59,070 --> 00:08:01,340
Jeg sagde bare "echo hej"
eller "ekko sårbare,"

160
00:08:01,340 --> 00:08:05,449
men hvad nu hvis du gjorde noget
faktisk ondsindet, ligesom rm -rf *

161
00:08:05,449 --> 00:08:07,240
som du måske ikke
nogensinde har skrevet før,

162
00:08:07,240 --> 00:08:08,920
og helt ærligt du sandsynligvis
bør ikke for tidligt,

163
00:08:08,920 --> 00:08:10,700
fordi du kan gøre en
masse skade med den.

164
00:08:10,700 --> 00:08:11,210
Hvorfor?

165
00:08:11,210 --> 00:08:12,990
rm gør hvad, selvfølgelig?

166
00:08:12,990 --> 00:08:14,270
Fjerner.

167
00:08:14,270 --> 00:08:15,930
* Betyder hvad?

168
00:08:15,930 --> 00:08:16,430
Alle.

169
00:08:16,430 --> 00:08:18,180
Så det er en såkaldt
wild card, så det betyder

170
00:08:18,180 --> 00:08:20,410
slette alt i
den aktuelle mappe.

171
00:08:20,410 --> 00:08:23,379
r sker forstås rekursiv
hvilket betyder, hvis det, du sletter

172
00:08:23,379 --> 00:08:26,420
er en mappe, og inde i der
er andre filer og andre mapper,

173
00:08:26,420 --> 00:08:28,950
rekursivt dykke ned der
og slette alt dette.

174
00:08:28,950 --> 00:08:31,040
Og -f er den værste af dem alle.

175
00:08:31,040 --> 00:08:32,580
Enhver ved, hvad -f betyder her?

176
00:08:32,580 --> 00:08:33,690

177
00:08:33,690 --> 00:08:34,360
Kraft.

178
00:08:34,360 --> 00:08:37,830
Så tvinge midler, selv
hvis det er en dårlig idé,

179
00:08:37,830 --> 00:08:40,939
gøre det uden at spørge mig
for yderligere bekræftelse.

180
00:08:40,939 --> 00:08:43,230
Så, du ved, vi griner
dette, men helt ærligt, jeg sandsynligvis

181
00:08:43,230 --> 00:08:44,972
skriver dette flere gange,
en dag, fordi virkeligheden

182
00:08:44,972 --> 00:08:47,210
er det er den hurtigste måde at
slette en hel masse ting.

183
00:08:47,210 --> 00:08:48,590
Men selv jeg har gjort nogle skader.

184
00:08:48,590 --> 00:08:53,100
>> Men hvis du var til at narre en computer
i fastlæggelsen nogle dumme variabel

185
00:08:53,100 --> 00:08:56,810
eller funktion kaldet x, men derefter
narre computeren i fuldbyrdelsesstaten

186
00:08:56,810 --> 00:09:00,030
ud over grænserne for at
funktion ud over at semikolon,

187
00:09:00,030 --> 00:09:04,430
du kunne faktisk narre en computer
til udførelse af noget som rm -rf

188
00:09:04,430 --> 00:09:07,810
eller e-mail-kommandoen
eller kommandoen Kopier.

189
00:09:07,810 --> 00:09:11,400
Alt bogstaveligt du kan gøre med den
computer, uanset om det er at slette filer,

190
00:09:11,400 --> 00:09:15,350
oprette filer, spamming nogen,
angribe nogle server eksternt,

191
00:09:15,350 --> 00:09:17,190
hvis du kan udtrykke det
med en kommando, du

192
00:09:17,190 --> 00:09:19,120
kan narre en computer, til at gøre det.

193
00:09:19,120 --> 00:09:21,510
>> Nu, hvad der er et eksempel på
hvordan du kan gøre dette?

194
00:09:21,510 --> 00:09:24,300
Tja, der er en masse computere
på internettet kører Bash.

195
00:09:24,300 --> 00:09:26,390
Alle os Mac-brugere er blandt dem.

196
00:09:26,390 --> 00:09:30,390
En masse af Linux-servere er blandt
dem så godt, og Unix-servere.

197
00:09:30,390 --> 00:09:32,630
Windows får igen
relativt off the hook

198
00:09:32,630 --> 00:09:34,590
medmindre du har installeret
speciel software.

199
00:09:34,590 --> 00:09:37,130
Nu er en masse servere for
Eksempelvis køre webservere,

200
00:09:37,130 --> 00:09:39,840
og i virkeligheden Linux er måske den
mest populære operativsystem

201
00:09:39,840 --> 00:09:43,060
til at køre på computere på internettet
der tjener op websider.

202
00:09:43,060 --> 00:09:44,910
Nu da vi vil se senere
i semestret, når

203
00:09:44,910 --> 00:09:48,470
du sende en anmodning fra
Deres browser-- Chrome,

204
00:09:48,470 --> 00:09:50,790
Internet Explorer whatever--
til en ekstern server,

205
00:09:50,790 --> 00:09:53,730
det viser sig, at selvom
du lige har skrevet www.example.com,

206
00:09:53,730 --> 00:09:59,590
din browser sender en besked
, der er lidt mere mystisk, som denne.

207
00:09:59,590 --> 00:10:01,239
>> Men bemærk lidt noget mærkeligt.

208
00:10:01,239 --> 00:10:03,030
De første to linier
Jeg har aldrig set før,

209
00:10:03,030 --> 00:10:04,904
men de ser ikke
særlig truende.

210
00:10:04,904 --> 00:10:08,030
Men mærke til, hvad jeg har stjålet
for tredje linje her.

211
00:10:08,030 --> 00:10:13,390
Hvis en slem fyr var at sende en besked
som denne fra hans eller hendes computer

212
00:10:13,390 --> 00:10:17,270
til en sårbar Mac eller en
sårbar Linux server,

213
00:10:17,270 --> 00:10:21,580
det sjove er, at Bash,
at simpel lille kommandoprompt

214
00:10:21,580 --> 00:10:27,450
er allestedsnærværende og er ofte
brugt til i det væsentlige at udføre

215
00:10:27,450 --> 00:10:30,020
indholdet af en
budskab, som det modtager.

216
00:10:30,020 --> 00:10:33,490
Og ved denne logik, kan du
narre en web-server, derfor,

217
00:10:33,490 --> 00:10:36,370
ved at sende noget lignende
User-Agent, som normalt

218
00:10:36,370 --> 00:10:38,300
formodes at sige
Navn på din browser.

219
00:10:38,300 --> 00:10:42,420
User-Agent Chrome, User-Agent Internet
Explorer, User-Agent Firefox, dette

220
00:10:42,420 --> 00:10:44,590
er bare din browser
måde at identificere sig selv.

221
00:10:44,590 --> 00:10:46,605
Men hvis en slem fyr meget
behændigt siger, mm mm, er jeg

222
00:10:46,605 --> 00:10:47,930
vil ikke fortælle dig
hvad min browser er,

223
00:10:47,930 --> 00:10:50,888
Jeg stedet vil sende dig dette
kryptisk udseende ting med en rm -rf

224
00:10:50,888 --> 00:10:55,840
* I det, kan du bogstaveligt talt narre en
sårbar webserver på internettet

225
00:10:55,840 --> 00:10:59,055
i udførelsen af ​​netop dette i
der for at slette alle filerne.

226
00:10:59,055 --> 00:11:00,930
Og helt ærligt, det er ikke
selv den værste af det.

227
00:11:00,930 --> 00:11:01,763
Du kan gøre noget.

228
00:11:01,763 --> 00:11:04,480
Du kunne starte en distribueret
denial of service angreb

229
00:11:04,480 --> 00:11:07,030
Hvis du har sendt denne besked til
hele klaser af webservere

230
00:11:07,030 --> 00:11:10,256
og derefter havde dem alle ned for
eksempel på Harvard.edu servere

231
00:11:10,256 --> 00:11:12,130
og du kan sortere bang
dælen ud af dem

232
00:11:12,130 --> 00:11:15,490
af en netværkstrafik, der var
ellers udløst af denne dårlige fyr.

233
00:11:15,490 --> 00:11:18,760
>> Så lang historie kort, næsten
alle i dette rum, der ejer en Mac

234
00:11:18,760 --> 00:11:20,240
er sårbare over for denne.

235
00:11:20,240 --> 00:11:24,100
Sølv foring er, at medmindre du er
kører en webserver på din bærbare computer,

236
00:11:24,100 --> 00:11:27,780
og medmindre du rent faktisk har konfigureret
den til at tillade noget SSH ind i det,

237
00:11:27,780 --> 00:11:28,670
du er faktisk sikker.

238
00:11:28,670 --> 00:11:31,710
Det er sårbare, men der er ingen
ene forsøger at komme ind i din bærbare computer,

239
00:11:31,710 --> 00:11:33,290
så du kan slags forvisset.

240
00:11:33,290 --> 00:11:36,210
Dog vil Apple snart
være at opdatere en rettelse til dette.

241
00:11:36,210 --> 00:11:39,660
En verden af ​​Linux har allerede udgivet
en række rettelser til Fedora og Ubuntu

242
00:11:39,660 --> 00:11:43,790
og andre versioner af Linux, og faktisk
hvis du kører update 50 i apparatet,

243
00:11:43,790 --> 00:11:45,930
selv der vil også være
opdateret og korrigeret.

244
00:11:45,930 --> 00:11:47,764
Men det er også ikke har
rigtig været sårbare,

245
00:11:47,764 --> 00:11:49,804
fordi medmindre du har
puslede med apparatet

246
00:11:49,804 --> 00:11:52,770
og lavet din bærbare offentligt
tilgængelige på internettet, hvilket ikke er

247
00:11:52,770 --> 00:11:54,910
som standard, har du
faktisk været fint, fordi

248
00:11:54,910 --> 00:11:56,890
af firewall og andre teknikker.

249
00:11:56,890 --> 00:12:01,000
>> Men det er et ekstremt eksempel på en fejl
at vi har levet for bogstaveligt 20

250
00:12:01,000 --> 00:12:04,050
år, og hvem ved, hvis nogen
al denne tid har kendt til det?

251
00:12:04,050 --> 00:12:06,300
Og i virkeligheden, det er en af
de fundamentale udfordringer

252
00:12:06,300 --> 00:12:08,690
at vi vil se senere i
semester om sikkerhed,

253
00:12:08,690 --> 00:12:13,020
er, at ligesom i den virkelige verden,
de gode fyre er på den ulempe.

254
00:12:13,020 --> 00:12:16,500
For at holde de slemme fyre ud, er vi nødt til at
sørge for, at alle døre er låst,

255
00:12:16,500 --> 00:12:20,340
at hvert vindue er sikkert, at
hvert punkt indrejse i et hjem

256
00:12:20,340 --> 00:12:21,980
er sikkert at holde de slemme fyre ud.

257
00:12:21,980 --> 00:12:26,870
Men hvad betyder den dårlige fyr er nødt til at
gøre til rent faktisk at kompromittere dit hjem

258
00:12:26,870 --> 00:12:28,200
og stjæle fra dig?

259
00:12:28,200 --> 00:12:32,574
Han eller hun bare har at finde en ulåst
dør, en brudt vindue, eller noget

260
00:12:32,574 --> 00:12:35,240
langs disse linjer, og det er den
samme ting i computersikkerhed.

261
00:12:35,240 --> 00:12:37,660
Vi kan skrive millioner af
linjer programkode

262
00:12:37,660 --> 00:12:40,570
og bruge hundredvis eller tusindvis
af timer forsøger at få det rigtige,

263
00:12:40,570 --> 00:12:43,370
men hvis du laver bare en
fejl i korrekthed,

264
00:12:43,370 --> 00:12:47,030
du kan sætte hele systemet og
faktisk i dette tilfælde hele internettet

265
00:12:47,030 --> 00:12:48,660
og verden i fare.

266
00:12:48,660 --> 00:12:51,950
>> Så hvis du gerne vil vide mere
om dette, skal du gå til denne URL her.

267
00:12:51,950 --> 00:12:54,450
Der er ikke behov for handling
i aften, medmindre du er

268
00:12:54,450 --> 00:12:57,116
blandt dem mere komfortable at
har kørt din egen hjemmeside

269
00:12:57,116 --> 00:12:59,810
server, i hvilket tilfælde du bør,
i virkeligheden, opdatere din software.

270
00:12:59,810 --> 00:13:03,244
>> Og det er også titlen på
en tale, og nu et papir,

271
00:13:03,244 --> 00:13:05,410
at vi har linket på
kursets hjemmeside for dag.

272
00:13:05,410 --> 00:13:07,600
Det var af en kollega
opkaldt Ken Thompson, der

273
00:13:07,600 --> 00:13:10,120
var at acceptere en meget berømt
award i datalogi,

274
00:13:10,120 --> 00:13:13,495
og han gav denne tale nogle år
siden, hovedsagelig på samme emne.

275
00:13:13,495 --> 00:13:18,250

276
00:13:18,250 --> 00:13:20,520
Beder folk spørgsmålet,
bør du virkelig

277
00:13:20,520 --> 00:13:23,480
tillid i sidste ende
software, du har fået?

278
00:13:23,480 --> 00:13:26,100
For eksempel, vi alle har
været at skrive programmer,

279
00:13:26,100 --> 00:13:27,820
og vi har kompilere
dem med Dunk.

280
00:13:27,820 --> 00:13:31,830
Og til din viden, du har skrevet
eventuelle programmer for CS50, hvor der er

281
00:13:31,830 --> 00:13:35,310
en bagdør slags, er der en vej
at en slem fyr, hvis der kører dit program,

282
00:13:35,310 --> 00:13:37,410
kunne overtage din computer?

283
00:13:37,410 --> 00:13:38,310
Sandsynligvis ikke, vel?

284
00:13:38,310 --> 00:13:40,180
Mario, og grådige, og Credit.

285
00:13:40,180 --> 00:13:41,680
Disse er alle temmelig små programmer.

286
00:13:41,680 --> 00:13:43,910
Du er nødt til at være temmelig
dårligt, hvis du rent faktisk

287
00:13:43,910 --> 00:13:47,310
gjort hele din computer sårbar
efter at skrive 10 eller 20 linjer kode,

288
00:13:47,310 --> 00:13:49,690
eller mindst uvidende om nogle
af de sikkerhedsmæssige konsekvenser.

289
00:13:49,690 --> 00:13:52,023
Nu siger jeg, at facetiously,
men vi kommer til at se i dag

290
00:13:52,023 --> 00:13:54,600
og i denne uge er det faktisk
virkelig, virkelig nemt

291
00:13:54,600 --> 00:13:57,980
at være dårligt og gøre endnu
korte programmer sårbare.

292
00:13:57,980 --> 00:14:02,880
>> Men for nu, i det mindste indse
at spørgsmålet bliver stillet her

293
00:14:02,880 --> 00:14:04,850
er omkring Clang i en compiler.

294
00:14:04,850 --> 00:14:08,360
Hvorfor har vi tillidsfuldt Dunk
i de sidste to eller tre uger?

295
00:14:08,360 --> 00:14:12,650
Hvem er at sige, at den, der skrev Dunk
havde ikke en "hvis" betingelse derinde

296
00:14:12,650 --> 00:14:17,680
at stort injiceres nogle nuller
og dem ind i ethvert program kompileres

297
00:14:17,680 --> 00:14:21,180
der ville lade ham eller hende adgang
din computer, når du sover

298
00:14:21,180 --> 00:14:23,580
og din laptop låg er åbent
og din computer kører?

299
00:14:23,580 --> 00:14:24,080
Right?

300
00:14:24,080 --> 00:14:28,350
Vi har denne form for ære system ret
nu hvor vi har tillid til, at Dunk er legit.

301
00:14:28,350 --> 00:14:30,000
Du har tillid til, at apparatet er legit.

302
00:14:30,000 --> 00:14:34,430
Du har tillid til, at bogstaveligt talt hver program
på din Mac eller pc er troværdig.

303
00:14:34,430 --> 00:14:37,510
Og da denne enkle fejl antyder,
selv om det ikke er skadeligt,

304
00:14:37,510 --> 00:14:40,580
Det er absolut ikke
sandsynligvis vil være tilfældet.

305
00:14:40,580 --> 00:14:42,350
>> Så du skal være bange som helvede.

306
00:14:42,350 --> 00:14:45,560
Helt ærligt, der er ingen enkel
anden løsning på dette

307
00:14:45,560 --> 00:14:48,185
end en slags samfundsmæssig bevidsthed
af den stigende kompleksitet

308
00:14:48,185 --> 00:14:50,310
at vi bygger oven
af vores edb-systemer,

309
00:14:50,310 --> 00:14:53,740
og hvor mere sårbar
Vi kan meget vel være.

310
00:14:53,740 --> 00:14:55,570
>> Nu med det sagt, Breakout.

311
00:14:55,570 --> 00:14:59,889
Så Breakout er problemet indstille tre, og
Breakout er et spil fra gårsdagens

312
00:14:59,889 --> 00:15:02,180
at du måske husker, men
for os i problemet indstille tre,

313
00:15:02,180 --> 00:15:04,450
det giver os mulighed for at tage
tingene tilbage op et hak

314
00:15:04,450 --> 00:15:08,880
så når vi skriver programmer,
selv i et Terminal vindue som dette,

315
00:15:08,880 --> 00:15:14,670
vi kan faktisk køre, i sidste ende,
grafiske programmer, som ikke

316
00:15:14,670 --> 00:15:17,800
i modsætning til dem, vi havde
adgang til i Scratch.

317
00:15:17,800 --> 00:15:20,910
Så dette er personalets
gennemførelse af Breakout,

318
00:15:20,910 --> 00:15:23,930
der er netop denne mursten-breaking
spil, at du flytter din padle tilbage

319
00:15:23,930 --> 00:15:27,590
og tilbage, og du rammer bolden
mod de farvede klodser op øverst.

320
00:15:27,590 --> 00:15:30,020
Så dette bringer os
slags tilbage til hvor

321
00:15:30,020 --> 00:15:33,180
Vi var i stand til meget hurtigt at være
med Scratch, og nu med C,

322
00:15:33,180 --> 00:15:35,800
implementere vores egen
grafiske brugergrænseflader.

323
00:15:35,800 --> 00:15:38,960
>> Men mere end det, det
problem sæt repræsenterer den første

324
00:15:38,960 --> 00:15:41,000
hvor vi giver
dig en masse kode.

325
00:15:41,000 --> 00:15:43,940
Og i virkeligheden, jeg bringe eksplicit
opmærksom på dette, fordi især

326
00:15:43,940 --> 00:15:47,090
for de mindre komfortabel, dette
problem indstillet, i hvert fald ved første øjekast,

327
00:15:47,090 --> 00:15:49,170
kommer til at føle sig som
vi har taget det op et hak.

328
00:15:49,170 --> 00:15:51,540
Fordi vi har givet dig,
for nogle af søgningen

329
00:15:51,540 --> 00:15:54,930
og sortering problemer i pset,
en masse kode, som vi skrev,

330
00:15:54,930 --> 00:15:56,680
og et par bemærkninger
at sige "at gøre,"

331
00:15:56,680 --> 00:15:58,221
hvor du er nødt til at udfylde de tomme felter.

332
00:15:58,221 --> 00:16:00,020
Så ikke alt for skræmmende, men
det er første gang

333
00:16:00,020 --> 00:16:03,370
vi afleverer dig kode, som du har brug for at
først læse, forstå og derefter tilføje til

334
00:16:03,370 --> 00:16:04,290
og fuldføre den.

335
00:16:04,290 --> 00:16:05,940
>> Og derefter med Breakout,
vi kommer til at gøre det samme,

336
00:16:05,940 --> 00:16:08,740
giver dig et par dusin flere linier
kode, som helt ærligt, giver dig

337
00:16:08,740 --> 00:16:11,490
en masse af rammerne for
spillet, men stopper kort

338
00:16:11,490 --> 00:16:14,304
gennemføre de mursten
og bolden og pagaj,

339
00:16:14,304 --> 00:16:15,970
men vi gennemføre nogle andre funktioner.

340
00:16:15,970 --> 00:16:18,280
Og selv som ved første øjekast, igen,
især hvis mindre behagelig,

341
00:16:18,280 --> 00:16:21,480
kan virke særligt skræmmende og
du tror, ​​der er så mange nye funktioner

342
00:16:21,480 --> 00:16:24,070
du nødt til at pakke dit sind
rundt, og det er sandt.

343
00:16:24,070 --> 00:16:26,281
Men husk, det er
helt ligesom Scratch.

344
00:16:26,281 --> 00:16:28,780
Odds er du ikke bruge alle
puslespilsbrikker i bunden.

345
00:16:28,780 --> 00:16:31,120
Odds er du ikke pleje at ombryde
dit sind omkring dem alle

346
00:16:31,120 --> 00:16:33,617
fordi alle tog det var en
hurtigt blik til at forstå, åh,

347
00:16:33,617 --> 00:16:35,450
det er, hvad jeg kan gøre
med denne brik.

348
00:16:35,450 --> 00:16:38,260
Og ja, i problem sæt
3 spec, vil vi pege dig

349
00:16:38,260 --> 00:16:41,370
på den dokumentation, der vil
introducere dig til nogle nye funktioner,

350
00:16:41,370 --> 00:16:43,570
og i sidste ende programmering
konstruerer du bruger.

351
00:16:43,570 --> 00:16:47,610
Betingelser, loops,
variable og funktioner

352
00:16:47,610 --> 00:16:50,720
vil være identisk med
hvad vi har set hidtil.

353
00:16:50,720 --> 00:16:53,560
>> Så ja, hvad vi vil give
du er nogle eksempler på kode, der

354
00:16:53,560 --> 00:16:56,110
Her kan du oprette et vindue
der ser ikke ulig det,

355
00:16:56,110 --> 00:16:59,540
og i sidste ende gøre det til
noget helt ligesom dette.

356
00:16:59,540 --> 00:17:02,250
Så drage fordel af CS50,
diskutere kontortid og mere,

357
00:17:02,250 --> 00:17:05,290
og tage trøst i det faktum, at
mængden af ​​kode du skal skrive

358
00:17:05,290 --> 00:17:06,760
er faktisk ikke så meget.

359
00:17:06,760 --> 00:17:10,359
Den første udfordring er bare at akklimatisere
dig selv til noget kode, vi har skrevet.

360
00:17:10,359 --> 00:17:11,450

361
00:17:11,450 --> 00:17:15,810
>> Eventuelle spørgsmål om pset3,
Shellshock, eller på anden måde?

362
00:17:15,810 --> 00:17:19,226
>> PUBLIKUM: Det virkede som
går igennem med Breakout

363
00:17:19,226 --> 00:17:22,154
at koden er næsten
et objekt-orienteret stil,

364
00:17:22,154 --> 00:17:24,675
men jeg troede AC var en
objektorienteret program.

365
00:17:24,675 --> 00:17:26,050
SPEAKER 1: En fremragende spørgsmål.

366
00:17:26,050 --> 00:17:28,258
Så kigge gennem
fordeling kode, koden

367
00:17:28,258 --> 00:17:30,180
skrev vi til pset3,
For dem bekendt, er det

368
00:17:30,180 --> 00:17:32,230
ligner det er en
lille objekt-orienteret.

369
00:17:32,230 --> 00:17:33,800
Korte svar er, det er.

370
00:17:33,800 --> 00:17:38,130
Det er en tilnærmelse af, hvordan du
kan gøre objektorienteret kode ved hjælp

371
00:17:38,130 --> 00:17:41,850
et sprog som C, men det er
stadig i sidste ende proceduremæssige.

372
00:17:41,850 --> 00:17:44,900
Der er ingen metoder inde i
de variabler, som du kan se.

373
00:17:44,900 --> 00:17:46,180
Men det minder om det.

374
00:17:46,180 --> 00:17:48,780
Og vi vil se, at funktionen igen
når vi kommer til PHP og JavaScript

375
00:17:48,780 --> 00:17:49,946
mod slutningen af ​​semesteret.

376
00:17:49,946 --> 00:17:53,667
Men for nu, så tænk på det som
en antydning af, hvad der er at komme.

377
00:17:53,667 --> 00:17:54,250
Godt spørgsmål.

378
00:17:54,250 --> 00:17:56,051

379
00:17:56,051 --> 00:17:56,550
Okay.

380
00:17:56,550 --> 00:17:59,730
Så fusionere slags var, hvordan vi
venstre ting sidste gang.

381
00:17:59,730 --> 00:18:03,250
Og flette slags var cool i
forstand, at det var så meget hurtigere,

382
00:18:03,250 --> 00:18:07,100
mindst baseret på overfladisk test
vi gjorde i sidste uge, end fx boble

383
00:18:07,100 --> 00:18:08,710
sortere, udvælgelse sortere, indsættelse slags.

384
00:18:08,710 --> 00:18:11,780
Og hvad var sirlige også er bare
hvordan kortfattet og rent

385
00:18:11,780 --> 00:18:12,810
du kan udtrykke det.

386
00:18:12,810 --> 00:18:15,840
Og hvad gjorde vi sige, det var en øvre
bundet på køretiden for merge

387
00:18:15,840 --> 00:18:16,340
sortere?

388
00:18:16,340 --> 00:18:17,633

389
00:18:17,633 --> 00:18:18,495
Ja?

390
00:18:18,495 --> 00:18:19,360
>> PUBLIKUM: n log n?

391
00:18:19,360 --> 00:18:20,819
>> SPEAKER 1: n log n, til højre. n log n.

392
00:18:20,819 --> 00:18:23,776
Og vi vil komme tilbage til, hvad det
egentlig betyder, eller hvor der kommer fra,

393
00:18:23,776 --> 00:18:25,570
men dette var bedre
end hvad køretid

394
00:18:25,570 --> 00:18:28,440
som vi oplevede for boble
udvælgelse og indsættelse slags?

395
00:18:28,440 --> 00:18:30,610
Så n potens. n kvadreret
er større end dette,

396
00:18:30,610 --> 00:18:34,650
og selvom det ikke er helt indlysende,
ved, at log n er mindre end n,

397
00:18:34,650 --> 00:18:36,910
så hvis du gør n gange
noget mindre end n,

398
00:18:36,910 --> 00:18:38,680
det kommer til at være mindre end n potens.

399
00:18:38,680 --> 00:18:40,130
Det er lidt af intuition der.

400
00:18:40,130 --> 00:18:42,190
Men vi betalte en pris for dette.

401
00:18:42,190 --> 00:18:47,000
Det var hurtigere, men et tema, der startede
at dukke op i sidste uge var denne afvejning.

402
00:18:47,000 --> 00:18:49,804
Jeg fik bedre ydeevne
tidsmæssigt, men hvad

403
00:18:49,804 --> 00:18:52,470
jeg er nødt til at bruge på den anden
hånd, for at opnå det?

404
00:18:52,470 --> 00:18:53,591
>> Publikum: Hukommelse.

405
00:18:53,591 --> 00:18:54,465
SPEAKER 1: Sig det igen?

406
00:18:54,465 --> 00:18:55,173
Publikum: Hukommelse.

407
00:18:55,173 --> 00:18:57,040
SPEAKER 1: Hukommelse, eller
plads mere generelt.

408
00:18:57,040 --> 00:18:59,040
Og det var ikke super
indlysende med vores mennesker,

409
00:18:59,040 --> 00:19:02,240
men minder om, at vores frivillige
stepping frem og træde

410
00:19:02,240 --> 00:19:04,780
tilbage, som om der er et array
her, og som om der er

411
00:19:04,780 --> 00:19:07,130
en anden gruppe her at
de kunne bruge, fordi vi

412
00:19:07,130 --> 00:19:09,080
tiltrængt sted at fusionere disse folk.

413
00:19:09,080 --> 00:19:11,480
Vi kunne ikke bare bytte dem på plads.

414
00:19:11,480 --> 00:19:13,800
Så fusionere slags gearing
er mere plads, hvilket

415
00:19:13,800 --> 00:19:15,620
vi behøvede ikke med
de andre algoritmer,

416
00:19:15,620 --> 00:19:17,410
men opadrettede er, at det er meget hurtigere.

417
00:19:17,410 --> 00:19:20,780
Og helt ærligt, i den virkelige verden plads
disse days-- ram, harddisk space--

418
00:19:20,780 --> 00:19:25,030
er relativt billige, og så det er
ikke nødvendigvis en dårlig ting.

419
00:19:25,030 --> 00:19:28,320
>> Så lad os tage et hurtigt kig, lidt
mere metodisk, hvad vi gjorde

420
00:19:28,320 --> 00:19:30,220
og hvorfor vi sagde, at det var n log n.

421
00:19:30,220 --> 00:19:33,260
Så her er de otte numre, og det
otte frivillige, vi havde sidste gang.

422
00:19:33,260 --> 00:19:35,718
Og den første ting, Merge
Sorter fortalte os at gøre, var hvad?

423
00:19:35,718 --> 00:19:37,010

424
00:19:37,010 --> 00:19:38,010
Publikum: Opdel i to.

425
00:19:38,010 --> 00:19:38,663
SPEAKER 1: Sig det igen?

426
00:19:38,663 --> 00:19:39,650
Publikum: Opdel i to.

427
00:19:39,650 --> 00:19:40,610
SPEAKER 1: Opdel i to, til højre.

428
00:19:40,610 --> 00:19:42,818
Dette er meget minder om
telefonbogen, i kløft

429
00:19:42,818 --> 00:19:44,220
og erobre mere generelt.

430
00:19:44,220 --> 00:19:45,640
Så vi kiggede på den venstre halvdel.

431
00:19:45,640 --> 00:19:48,700
Og så når vi sagde, sortere
den venstre halvdel af elementerne,

432
00:19:48,700 --> 00:19:49,690
hvad gjorde vi næste sige?

433
00:19:49,690 --> 00:19:51,210

434
00:19:51,210 --> 00:19:54,860
Sortere den venstre halvdel af den venstre
halvdelen, hvilket tillod os at,

435
00:19:54,860 --> 00:19:57,570
efter deling i to,
fokusere på fire og to.

436
00:19:57,570 --> 00:20:01,280
>> Hvordan du sortere en liste nu, i
gul, størrelse to, ved hjælp Flet Sort?

437
00:20:01,280 --> 00:20:02,330

438
00:20:02,330 --> 00:20:04,580
Nå opdele det på midten,
og sortere den venstre halvdel.

439
00:20:04,580 --> 00:20:07,100
Og det var, hvor tingene
fik lidt dum kortvarigt.

440
00:20:07,100 --> 00:20:10,720
Hvordan du sortere en liste, der er af
Størrelse One, som dette nummer fire her?

441
00:20:10,720 --> 00:20:12,330

442
00:20:12,330 --> 00:20:13,210
Det er ordnet.

443
00:20:13,210 --> 00:20:14,200
Du er færdig.

444
00:20:14,200 --> 00:20:17,300
>> Men hvordan kan du sortere en liste over
Størrelse One når det er nummer to?

445
00:20:17,300 --> 00:20:21,640
Nå, samme ting, men nu hvad var
tredje og afgørende skridt i Merge Sortér?

446
00:20:21,640 --> 00:20:24,020
Du havde at fusionere venstre
halvdelen og højre halvdel.

447
00:20:24,020 --> 00:20:26,580
Og når vi gjorde det, vi kiggede
på fire, vi kiggede på to.

448
00:20:26,580 --> 00:20:28,750
Vi besluttede okay,
naturligvis to kommer først,

449
00:20:28,750 --> 00:20:31,840
så vi sætte to i sin
sted, efterfulgt af fire.

450
00:20:31,840 --> 00:20:35,010
Og nu er du nødt til at slags spole tilbage,
og dette er slags karakteristiske

451
00:20:35,010 --> 00:20:37,570
af en algoritme som Merge
Sorter, spole tilbage i hukommelsen.

452
00:20:37,570 --> 00:20:40,240
Hvad var den næste linje af historien?

453
00:20:40,240 --> 00:20:41,780
Hvad skal jeg fokusere på næste?

454
00:20:41,780 --> 00:20:43,110

455
00:20:43,110 --> 00:20:47,350
Den højre halvdel af den venstre
halvdelen, hvilket er seks og otte.

456
00:20:47,350 --> 00:20:50,320
>> Så lad mig bare gå gennem denne
uden belaboring punktet for meget.

457
00:20:50,320 --> 00:20:53,330
Seks og otte, så seks er
sorteret, otte er sorteret.

458
00:20:53,330 --> 00:20:57,190
Flet dem sammen på den måde,
og nu er den næste store skridt

459
00:20:57,190 --> 00:21:00,990
er naturligvis sortere højre halvdel fra
det allerførste skridt i denne algoritme.

460
00:21:00,990 --> 00:21:02,870
Så vi fokuserer på en, tre, syv, fem.

461
00:21:02,870 --> 00:21:04,540
Vi derefter fokusere på den venstre halvdel.

462
00:21:04,540 --> 00:21:09,400
Den venstre halvdel af det, den højre halvdel af
det, og derefter flette i én og tre.

463
00:21:09,400 --> 00:21:13,100
Så den højre halvdel, derefter til venstre halvdel
af det, så den højre halvdel af det.

464
00:21:13,100 --> 00:21:15,985
Flet det i, og hvad nu skridt tilbage?

465
00:21:15,985 --> 00:21:18,040

466
00:21:18,040 --> 00:21:22,460
Flet den store venstre halvdel og den store
højre halvdel, så man går dernede,

467
00:21:22,460 --> 00:21:27,330
derefter to, så tre, så fire, så
fem, så seks og derefter syv, derefter otte.

468
00:21:27,330 --> 00:21:31,990
>> Så nu, hvorfor er dette i sidste ende afslører,
især hvis n og logaritmer mere

469
00:21:31,990 --> 00:21:35,487
generelt hellere slippe dig,
i hvert fald i nyere tid?

470
00:21:35,487 --> 00:21:37,070
Nå, mærke højden af ​​denne ting.

471
00:21:37,070 --> 00:21:41,230
Vi havde otte elementer, og vi
delte det med to, og to, med to.

472
00:21:41,230 --> 00:21:44,590
Så log basis to af otte giver os tre.

473
00:21:44,590 --> 00:21:45,640

474
00:21:45,640 --> 00:21:48,540
Og tro mig på, at hvis
lidt diset på det.

475
00:21:48,540 --> 00:21:54,710
Men log basis to af otte er tre,
så vi har gjort tre lag af sammenlægning.

476
00:21:54,710 --> 00:21:57,170
Og da vi fusionerede
elementer, hvor mange elementer

477
00:21:57,170 --> 00:21:58,950
vi se på på hver af disse rækker?

478
00:21:58,950 --> 00:22:00,212

479
00:22:00,212 --> 00:22:01,437
I alt n, right?

480
00:22:01,437 --> 00:22:04,020
Fordi at fusionere den øverste række,
selvom vi gjorde det stykkevis,

481
00:22:04,020 --> 00:22:05,990
vi rørt i sidste ende hvert nummer en gang.

482
00:22:05,990 --> 00:22:09,054
Og i anden række, at
flette disse lister af størrelse to,

483
00:22:09,054 --> 00:22:10,470
vi var nødt til at røre hvert element én gang.

484
00:22:10,470 --> 00:22:12,690
Og så virkelig her
tydeligt i den sidste række,

485
00:22:12,690 --> 00:22:15,430
vi var nødt til at røre ved hver af disse
elementer én gang, men kun én gang,

486
00:22:15,430 --> 00:22:18,400
så heri ligger, så vores n log n.

487
00:22:18,400 --> 00:22:21,780
>> Og nu bare for at gøre tingene lidt
mere formelle for bare et øjeblik, hvis du

488
00:22:21,780 --> 00:22:24,260
skulle nu analysere dette
ved en slags højere niveau

489
00:22:24,260 --> 00:22:28,340
og forsøge at beslutte, godt, hvordan
kan du gå om at udtrykke

490
00:22:28,340 --> 00:22:31,780
køretiden for denne algoritme
bare ved at kigge på det og ikke

491
00:22:31,780 --> 00:22:33,590
ved hjælp af en kunstig eksempel?

492
00:22:33,590 --> 00:22:36,590
Nå, hvor meget tid ville du sige en
træde som denne i gul ville tage,

493
00:22:36,590 --> 00:22:37,173
hvis n <2 gengæld?

494
00:22:37,173 --> 00:22:38,840

495
00:22:38,840 --> 00:22:39,830
Det er en stor O i hvad?

496
00:22:39,830 --> 00:22:41,450

497
00:22:41,450 --> 00:22:44,540
Så jeg ser en, så et skridt,
måske to trin, fordi det er hvis

498
00:22:44,540 --> 00:22:47,110
og derefter vende tilbage, men det er
konstant tid, ikke?

499
00:22:47,110 --> 00:22:49,960
Så vi sagde O (1), og det er
hvordan jeg skal udtrykke dette.

500
00:22:49,960 --> 00:22:51,480
T, bare være køretid.

501
00:22:51,480 --> 00:22:54,150
n er størrelsen af ​​input,
så T (n), bare en fancy måde

502
00:22:54,150 --> 00:22:56,330
sige drift
tid givet input af størrelse n

503
00:22:56,330 --> 00:23:00,220
vil være af størrelsesordenen
konstant tid, i O (1).

504
00:23:00,220 --> 00:23:01,970
>> Men ellers, hvad med det her?

505
00:23:01,970 --> 00:23:05,660
Hvordan vil du beskrive
køretid for denne gule linje?

506
00:23:05,660 --> 00:23:06,250
T i hvad?

507
00:23:06,250 --> 00:23:09,440

508
00:23:09,440 --> 00:23:12,665
Du kan slags snyde her og
besvare mit spørgsmål cyklisk.

509
00:23:12,665 --> 00:23:14,770

510
00:23:14,770 --> 00:23:17,900
Så hvis køretiden i
Generelt siger vi bare er T (n).

511
00:23:17,900 --> 00:23:18,950

512
00:23:18,950 --> 00:23:22,490
Og nu er du slags punting her og
sige, godt, bare sortere den venstre halvdel,

513
00:23:22,490 --> 00:23:23,920
og derefter sortere den højre halvdel.

514
00:23:23,920 --> 00:23:27,520
Hvordan kan vi symbolsk
køretiden for denne gule linje?

515
00:23:27,520 --> 00:23:28,020
T i hvad?

516
00:23:28,020 --> 00:23:29,360
Hvad er størrelsen af ​​input?

517
00:23:29,360 --> 00:23:30,510

518
00:23:30,510 --> 00:23:31,057
n over to.

519
00:23:31,057 --> 00:23:32,140
Hvorfor kan jeg ikke bare sige det?

520
00:23:32,140 --> 00:23:36,449
Og så er det en anden T (n / 2) og derefter
igen, hvis jeg flette to sorterede halvdele,

521
00:23:36,449 --> 00:23:38,615
hvor mange elementer skal jeg hen
nødt til at røre ved alt?

522
00:23:38,615 --> 00:23:39,780

523
00:23:39,780 --> 00:23:40,320
n.

524
00:23:40,320 --> 00:23:42,790
Så jeg kan udtrykke dette,
bare for at være slags fancy,

525
00:23:42,790 --> 00:23:44,430
som køretiden i almindelighed.

526
00:23:44,430 --> 00:23:51,140
T (n) er blot køretiden for T (n / 2),
plus T (n / 2), venstre halvdel og højre halvdel,

527
00:23:51,140 --> 00:23:55,360
plus O (n), som er sandsynligvis n trin,
men måske, hvis jeg bruger to fingre,

528
00:23:55,360 --> 00:23:57,960
det er dobbelt så mange
trin, men det er lineær.

529
00:23:57,960 --> 00:24:00,440
Det er nogle antal trin
det er en faktor af n,

530
00:24:00,440 --> 00:24:02,270
så vi kan udtrykke dette som dette.

531
00:24:02,270 --> 00:24:05,550
Og det er her, vi nu vil punt til
bagsiden af ​​vores high school math lærebog

532
00:24:05,550 --> 00:24:10,290
vi er at tilbagefald i sidste ende
ender svarende dette n gange log n,

533
00:24:10,290 --> 00:24:12,530
hvis du rent faktisk gør ud
math mere formelt.

534
00:24:12,530 --> 00:24:13,950
>> Så det er kun to perspektiver.

535
00:24:13,950 --> 00:24:17,500
En numerisk med en
hard-kodet repræsentativt eksempel

536
00:24:17,500 --> 00:24:21,140
hjælp otte numre, og en mere
generel kig på, hvordan vi fik der.

537
00:24:21,140 --> 00:24:25,670
Men hvad der er virkelig interessant her
er, igen, denne forestilling om cykling.

538
00:24:25,670 --> 00:24:26,900
Jeg bruger ikke efter sløjfer.

539
00:24:26,900 --> 00:24:29,860
Jeg er lidt at definere
noget i form af sig selv,

540
00:24:29,860 --> 00:24:31,950
ikke kun med denne
matematisk funktion,

541
00:24:31,950 --> 00:24:34,860
men også i form af denne pseudo kode.

542
00:24:34,860 --> 00:24:38,260
Denne pseudokode er rekursive
i, at to af dens linjer

543
00:24:38,260 --> 00:24:42,310
hovedsagelig fortæller det til at gå
benytte sig at løse et mindre

544
00:24:42,310 --> 00:24:45,400
Problemet med mindre størrelse,
og derefter igen og igen

545
00:24:45,400 --> 00:24:48,820
og igen, indtil vi skære det
ned til denne såkaldte base case.

546
00:24:48,820 --> 00:24:52,810
>> Så lad os faktisk tegne en mere overbevisende
take-away fra det som følger.

547
00:24:52,810 --> 00:24:58,420
Lad mig gå ind i gedit og tage en
se på nogle af dagens kildekode,

548
00:24:58,420 --> 00:24:59,930
især dette eksempel her.

549
00:24:59,930 --> 00:25:03,709
Sigma 0, hvilket tilsyneladende tilføjer
numrene en gennem n.

550
00:25:03,709 --> 00:25:05,750
Så lad os se, hvad der er velkendt
og ukendte her.

551
00:25:05,750 --> 00:25:08,690
Først har vi et par
omfatter, så intet nyt der.

552
00:25:08,690 --> 00:25:09,190
Prototype.

553
00:25:09,190 --> 00:25:11,370
Jeg er lidt diset på
dette efter få dage,

554
00:25:11,370 --> 00:25:13,790
men hvad gjorde vi sige en
prototype af en funktion er?

555
00:25:13,790 --> 00:25:15,099

556
00:25:15,099 --> 00:25:16,015
Publikum: [uhørligt].

557
00:25:16,015 --> 00:25:16,905
SPEAKER 1: Hvad er det?

558
00:25:16,905 --> 00:25:17,800
PUBLIKUM: Vi annoncere det.

559
00:25:17,800 --> 00:25:18,883
SPEAKER 1: Vi offentliggør det.

560
00:25:18,883 --> 00:25:22,290
Så du underviser Dunk, hey,
faktisk ikke at gennemføre dette endnu,

561
00:25:22,290 --> 00:25:25,740
men et eller andet sted i denne fil, formodentlig
vil være en funktion kaldet hvad?

562
00:25:25,740 --> 00:25:26,930

563
00:25:26,930 --> 00:25:27,540
Sigma.

564
00:25:27,540 --> 00:25:30,540
Og dette er blot et løfte om, at
det kommer til at se sådan ud.

565
00:25:30,540 --> 00:25:33,720
Det kommer til at tage et heltal som
input-- og jeg kan være mere eksplicit

566
00:25:33,720 --> 00:25:36,570
og sige int n DET-- det er
vil returnere en int,

567
00:25:36,570 --> 00:25:39,900
men semikolon midler, mm, jeg får rundt
at gennemføre dette lidt senere.

568
00:25:39,900 --> 00:25:40,989
Igen Clang er stum.

569
00:25:40,989 --> 00:25:43,280
Det er kun kommer til at vide, hvad
du fortælle det top til bund,

570
00:25:43,280 --> 00:25:45,765
så vi er nødt til i det mindste give
det en antydning af, hvad der er at komme.

571
00:25:45,765 --> 00:25:47,330
>> Lad os nu se på vigtigste her.

572
00:25:47,330 --> 00:25:50,040
Lad os rulle ned her og
se hvad main gør.

573
00:25:50,040 --> 00:25:53,780
Det er ikke så længe for en funktion, og
faktisk konstruktionen her er velkendte.

574
00:25:53,780 --> 00:25:57,590
Jeg erklærer en variabel n, og derefter
Jeg plager brugeren igen og igen

575
00:25:57,590 --> 00:26:01,880
til et positivt heltal ved hjælp getInt,
og kun udgang ud af denne løkke

576
00:26:01,880 --> 00:26:03,280
når brugeren har opfyldt.

577
00:26:03,280 --> 00:26:05,670
Gør Mens vi har brugt til
forpeste brugeren på den måde.

578
00:26:05,670 --> 00:26:06,670
Nu er det interessant.

579
00:26:06,670 --> 00:26:08,510
Jeg erklærer en int kaldet "svar".

580
00:26:08,510 --> 00:26:11,420
Jeg tildeler det returværdien
af en funktion kaldet "sigma".

581
00:26:11,420 --> 00:26:15,200
Jeg ved ikke, hvad der gør endnu, men
Jeg husker at erklære det for et øjeblik siden.

582
00:26:15,200 --> 00:26:18,310
Og så jeg passerer i
værdi, som brugeren har indtastet, n,

583
00:26:18,310 --> 00:26:20,420
og så skal jeg rapportere svaret.

584
00:26:20,420 --> 00:26:22,260
Jamen så lad os rulle tilbage
for bare et øjeblik.

585
00:26:22,260 --> 00:26:28,620
Lad os gå videre ind i denne mappe, gør
sigma 0, og faktisk køre dette program

586
00:26:28,620 --> 00:26:30,490
og se hvad der sker.

587
00:26:30,490 --> 00:26:35,930
Så hvis jeg gå videre og køre
dette program ./sigma-0,

588
00:26:35,930 --> 00:26:40,139
og jeg skriver i en positiv
heltal som to, Sigma,

589
00:26:40,139 --> 00:26:43,180
som den græske symbol antyder, er bare
kommer til at tilføje op alle de tal fra

590
00:26:43,180 --> 00:26:44,320
nul på op til to.

591
00:26:44,320 --> 00:26:46,560
Så 0 plus 1 plus 2.

592
00:26:46,560 --> 00:26:48,830
Så dette vil forhåbentlig give mig 3.

593
00:26:48,830 --> 00:26:49,750
Det er alt den gør.

594
00:26:49,750 --> 00:26:52,690
Og på samme måde, hvis jeg køre dette igen
og jeg give det et nummer tre,

595
00:26:52,690 --> 00:26:56,721
der er 3 plus 2, så det er
5 plus 1 skulle give mig 6.

596
00:26:56,721 --> 00:26:59,470
Og så hvis jeg får virkelig skøre og
begynde at skrive i større tal,

597
00:26:59,470 --> 00:27:01,290
det bør give mig
større og større beløb.

598
00:27:01,290 --> 00:27:02,250
Så det er alt.

599
00:27:02,250 --> 00:27:04,010
>> Så hvad betyder sigma se ud?

600
00:27:04,010 --> 00:27:05,430
Tja, det er temmelig ligetil.

601
00:27:05,430 --> 00:27:08,940
Det er, hvordan vi kunne have gennemført
dette for de sidste par uger.

602
00:27:08,940 --> 00:27:11,120
"Int" kommer til at være en tilbagevenden type.

603
00:27:11,120 --> 00:27:14,330
Sigma er navnet, og det tager
en variabel m i stedet for n.

604
00:27:14,330 --> 00:27:15,940
Jeg vil ændre det op toppen.

605
00:27:15,940 --> 00:27:17,340
Så er dette blot en tilregnelighed check.

606
00:27:17,340 --> 00:27:18,430

607
00:27:18,430 --> 00:27:19,950
Vi vil se, hvorfor i et øjeblik.

608
00:27:19,950 --> 00:27:24,220
Nu Jeg erklærer en anden variabel,
sum, initialisere den til nul.

609
00:27:24,220 --> 00:27:28,140
Så jeg har denne For-løkke
iteration, tilsyneladende for klarhed,

610
00:27:28,140 --> 00:27:33,810
fra i = 1 på op til = m, hvilket er
hvad brugeren har skrevet i, og så er jeg

611
00:27:33,810 --> 00:27:35,690
øg beløb som denne.

612
00:27:35,690 --> 00:27:37,360
Og derefter returnere beløb.

613
00:27:37,360 --> 00:27:38,440
>> Så et par spørgsmål.

614
00:27:38,440 --> 00:27:42,370
En, jeg hævder i min kommentar, at dette
undgår risikoen for en uendelig løkke.

615
00:27:42,370 --> 00:27:45,620
Hvorfor skulle passere i et negativt tal
fremkalde potentielt en uendelig løkke?

616
00:27:45,620 --> 00:27:49,396

617
00:27:49,396 --> 00:27:51,290
>> Publikum: Du vil aldrig nå meter.

618
00:27:51,290 --> 00:27:52,880
>> SPEAKER 1: Aldrig nå m.

619
00:27:52,880 --> 00:27:55,880
Men m er gået i, så lad os
Overvej et simpelt eksempel.

620
00:27:55,880 --> 00:27:58,510
Hvis m er gået ind af
brugeren som negativ.

621
00:27:58,510 --> 00:28:00,059
Uanset main.

622
00:28:00,059 --> 00:28:01,850
Vigtigste beskytter os mod
dette også, så jeg er bare

623
00:28:01,850 --> 00:28:04,680
bliver virkelig anal med
sigma også sikre

624
00:28:04,680 --> 00:28:06,540
at input ikke kan være negativ.

625
00:28:06,540 --> 00:28:10,130
Så hvis m er negativ,
noget som negativ.

626
00:28:10,130 --> 00:28:11,930
Hvad kommer til at ske?

627
00:28:11,930 --> 00:28:14,390
Nå, jeg går til
bliver initialiseret til en,

628
00:28:14,390 --> 00:28:19,060
og så er jeg kommer til at være
mindre end eller lig med m?

629
00:28:19,060 --> 00:28:24,130

630
00:28:24,130 --> 00:28:24,765
>> Standby.

631
00:28:24,765 --> 00:28:26,930

632
00:28:26,930 --> 00:28:29,370
Det var-- lad os ikke,
lad os nix denne historie.

633
00:28:29,370 --> 00:28:32,780
Jeg spurgte ikke, at spørgsmål, fordi
risikoen for, at jeg hentyder til

634
00:28:32,780 --> 00:28:38,360
kommer ikke til at ske, fordi jeg er
altid vil være større than-- OK,

635
00:28:38,360 --> 00:28:39,871
Jeg trække det spørgsmål.

636
00:28:39,871 --> 00:28:40,370
OK.

637
00:28:40,370 --> 00:28:42,030
Lad os kun fokusere på denne del her.

638
00:28:42,030 --> 00:28:44,210

639
00:28:44,210 --> 00:28:48,830
Hvorfor gjorde jeg erklære nogle
uden for loop?

640
00:28:48,830 --> 00:28:52,010
Meddelelse om linje 49 Jeg har
erklæret i indersiden af ​​løkken,

641
00:28:52,010 --> 00:28:54,950
men online 48 Jeg har
erklæret nogle uden.

642
00:28:54,950 --> 00:28:55,695
Ja.

643
00:28:55,695 --> 00:28:56,611
Publikum: [uhørligt].

644
00:28:56,611 --> 00:28:58,734

645
00:28:58,734 --> 00:28:59,400
SPEAKER 1: Selvfølgelig.

646
00:28:59,400 --> 00:29:03,360
Så først og fremmest jeg bestemt ikke
ønsker at erklære og initialisere sum

647
00:29:03,360 --> 00:29:06,130
til nul inde i
løkke på hver iteration

648
00:29:06,130 --> 00:29:09,370
fordi dette klart vil besejre
Formålet opsummering tallene.

649
00:29:09,370 --> 00:29:11,770
Jeg ville holde skiftende
værdien tilbage til nul.

650
00:29:11,770 --> 00:29:17,992
Og også, hvad er en anden mere mystisk
Grunden til det samme design beslutning?

651
00:29:17,992 --> 00:29:18,954
Ja.

652
00:29:18,954 --> 00:29:20,279
>> Publikum: [uhørligt].

653
00:29:20,279 --> 00:29:21,070
SPEAKER 1: Præcis.

654
00:29:21,070 --> 00:29:24,060
Jeg vil have adgang til det udenfor
af løkken også på hvilken linje?

655
00:29:24,060 --> 00:29:25,390

656
00:29:25,390 --> 00:29:26,400
Den 53.

657
00:29:26,400 --> 00:29:29,910
Og baseret på vores tommelfingerregel
fra et par forelæsninger siden,

658
00:29:29,910 --> 00:29:33,680
variabler virkefelt, virkelig, til
krøllede parenteser, der omfatter dem.

659
00:29:33,680 --> 00:29:38,190
Så hvis jeg ikke erklære sum inde
af disse ydre krøllede parenteser,

660
00:29:38,190 --> 00:29:40,250
Jeg kan ikke bruge det på linje 53.

661
00:29:40,250 --> 00:29:43,160
Sagt på en anden måde, hvis jeg erklærede
sum i her, eller endog inden for

662
00:29:43,160 --> 00:29:45,410
For-løkke, kunne jeg ikke få adgang til det i 53.

663
00:29:45,410 --> 00:29:47,150
Den variable vil reelt være væk.

664
00:29:47,150 --> 00:29:48,579
Så et par grunde der.

665
00:29:48,579 --> 00:29:50,370
Men lad os nu gå tilbage
og se hvad der sker.

666
00:29:50,370 --> 00:29:51,730
Så sigma bliver kaldt.

667
00:29:51,730 --> 00:29:55,640
Det tilføjer op 1 plus 2 eller 1 plus 2
plus 3 og derefter returnerer værdien,

668
00:29:55,640 --> 00:29:59,660
gemmer det i svar, og printf her
er derfor, jeg ser på skærmen.

669
00:29:59,660 --> 00:30:03,079
Så dette er hvad vi vil kalde en iterativ
tilgang, hvor iteration bare

670
00:30:03,079 --> 00:30:03,870
: anvendelse af en løkke.

671
00:30:03,870 --> 00:30:06,900
En for-løkke, en while-løkke, en skal mens
loop, bare gør noget igen

672
00:30:06,900 --> 00:30:08,380
og igen og igen.

673
00:30:08,380 --> 00:30:13,505
>> Men Sigma er sådan en pæn funktion i
at jeg kunne gennemføre det anderledes.

674
00:30:13,505 --> 00:30:14,620

675
00:30:14,620 --> 00:30:19,120
Hvad med dette, hvilket
bare for at være lidt cool,

676
00:30:19,120 --> 00:30:21,880
lad mig virkelig slippe
af en masse distraktion

677
00:30:21,880 --> 00:30:24,380
fordi denne funktion
er faktisk ganske enkel.

678
00:30:24,380 --> 00:30:27,780
Lad os skære det ned lige
til sine fire centrale linjer

679
00:30:27,780 --> 00:30:30,410
og slippe af med alle de
kommentarer og krøllede parenteser.

680
00:30:30,410 --> 00:30:34,334
Det er lidt af en mind-blowing
alternativ implementering.

681
00:30:34,334 --> 00:30:37,250
Okay, måske ikke mind-blowing,
men det er lidt mere sexet, okay,

682
00:30:37,250 --> 00:30:39,920
at se på dette så meget mere kortfattet.

683
00:30:39,920 --> 00:30:43,120
Med blot fire linjer kode,
Jeg først har denne tilregnelighed check.

684
00:30:43,120 --> 00:30:45,732
Hvis m er mindre end eller lig med
nul, Sigma giver ingen mening.

685
00:30:45,732 --> 00:30:48,190
Det er kun meningen at være i
dette tilfældet for positive tal,

686
00:30:48,190 --> 00:30:50,340
så jeg bare til
returnere nul vilkårligt

687
00:30:50,340 --> 00:30:53,210
så vi i det mindste have
nogle såkaldt base case.

688
00:30:53,210 --> 00:30:54,430
>> Men her er det skønhed.

689
00:30:54,430 --> 00:30:59,930
Hele denne idé, tilføjer den
tal fra 1 til n eller m i denne sag,

690
00:30:59,930 --> 00:31:02,630
kan gøres ved slags lade sorteper.

691
00:31:02,630 --> 00:31:04,947
Nå, hvad er summen af ​​1 til m?

692
00:31:04,947 --> 00:31:05,780
Tja, ved du hvad?

693
00:31:05,780 --> 00:31:11,949
Det er det samme som summen af ​​m
plus summen af ​​1 m minus 1.

694
00:31:11,949 --> 00:31:12,740
Jamen ved du hvad?

695
00:31:12,740 --> 00:31:13,940
Hvad er sigma af m minus 1?

696
00:31:13,940 --> 00:31:17,860
Tja, hvis du slags følge denne
logisk, det er det samme som m minus 1

697
00:31:17,860 --> 00:31:21,415
plus sigma af m minus 2.

698
00:31:21,415 --> 00:31:22,480

699
00:31:22,480 --> 00:31:26,012
Så du kan slags bare--
dette er ligesom, hvis du bare

700
00:31:26,012 --> 00:31:28,220
forsøger at irritere en ven
og de beder dig et spørgsmål,

701
00:31:28,220 --> 00:31:31,344
du slags reagere med et spørgsmål,
du kan slags holde passerer sorteper.

702
00:31:31,344 --> 00:31:34,560
Men hvad er afgørende, er, at hvis du holder
at spørgsmålet mindre og mindre

703
00:31:34,560 --> 00:31:36,910
og mindre, er du
ikke spørge, hvad der er sigma

704
00:31:36,910 --> 00:31:39,116
af n, hvad er sigma af
n, hvad er sigma af n?

705
00:31:39,116 --> 00:31:40,990
Du spørger, hvad er
sigma af n, hvad er sigma

706
00:31:40,990 --> 00:31:42,839
af n minus 1, hvad er sigma af n minus 2?

707
00:31:42,839 --> 00:31:44,880
Til sidst dit spørgsmål
kommer til at blive, hvad?

708
00:31:44,880 --> 00:31:50,250
Hvad er sigma af en eller
nul, et meget lille værdi,

709
00:31:50,250 --> 00:31:52,220
og så snart du
få det, din ven,

710
00:31:52,220 --> 00:31:54,350
du ikke kommer til at spørge
det samme spørgsmål igen,

711
00:31:54,350 --> 00:31:55,975
du vil bare sige, åh, det er nul.

712
00:31:55,975 --> 00:31:58,490
Vi er færdig med at spille denne slags
dumme cykliske spil.

713
00:31:58,490 --> 00:32:02,950
>> Så rekursion er den handling i programmeringen
for en funktion kalder sig.

714
00:32:02,950 --> 00:32:06,630
Dette program, der udarbejdes og løbe, er
kommer til at opføre sig på nøjagtig samme måde,

715
00:32:06,630 --> 00:32:09,620
men hvad er nøglen er, at inde
af en funktion kaldet sigma

716
00:32:09,620 --> 00:32:13,150
der er en linje af kode, hvor
Vi kalder os selv,

717
00:32:13,150 --> 00:32:14,980
som normalt ville være dårligt.

718
00:32:14,980 --> 00:32:21,160
For eksempel, hvad nu hvis jeg først
kompileret dette, så gør sigma--

719
00:32:21,160 --> 00:32:22,710
at sigma 1 ./sigma-1.

720
00:32:22,710 --> 00:32:25,050

721
00:32:25,050 --> 00:32:27,690
Positivt heltal, please, 50 1275.

722
00:32:27,690 --> 00:32:30,810
Så hvad funktionen synes at
være baseret på en test korrekt.

723
00:32:30,810 --> 00:32:34,917
Men hvad nu hvis jeg får en lidt farlig
og slette den såkaldte base case,

724
00:32:34,917 --> 00:32:37,750
og bare sige, godt jeg bare gøre
dette mere kompliceret, end det er.

725
00:32:37,750 --> 00:32:42,450
Lad os bare beregne sigma
ved at tage m, og derefter tilsætte

726
00:32:42,450 --> 00:32:44,564
i sigma af m minus en?

727
00:32:44,564 --> 00:32:45,980
Nå, hvad der kommer til at ske her?

728
00:32:45,980 --> 00:32:47,140
Lad os zoome ud.

729
00:32:47,140 --> 00:32:52,920
Lad os kompilere programmet,
gemme det, rekompilere programmet

730
00:32:52,920 --> 00:33:00,450
og derefter klar ./sigma-1 zoome ind,
indtaste positivt heltal venligst, 50.

731
00:33:00,450 --> 00:33:02,180

732
00:33:02,180 --> 00:33:04,430
Hvor mange af jer er villige
at Fess op til at se det?

733
00:33:04,430 --> 00:33:04,950
>> OK.

734
00:33:04,950 --> 00:33:06,690
Så dette kan ske for
en række årsager,

735
00:33:06,690 --> 00:33:09,148
og helt ærligt i denne uge er vi
ved at give dig flere af dem.

736
00:33:09,148 --> 00:33:11,780
Men i dette tilfælde, så prøv
at ræsonnere baglæns

737
00:33:11,780 --> 00:33:14,430
hvad der kunne være sket her?

738
00:33:14,430 --> 00:33:17,400
Segmenteringsfejl, vi sagde sidste
tid, henviser til et segment af hukommelse.

739
00:33:17,400 --> 00:33:18,690
Noget slemt er sket.

740
00:33:18,690 --> 00:33:21,550
Men hvad var det
mekanisk, der gik galt

741
00:33:21,550 --> 00:33:25,000
her på grund af min udsendelse
af denne såkaldte base case,

742
00:33:25,000 --> 00:33:26,870
hvor jeg vendte tilbage en hard-kodet værdi?

743
00:33:26,870 --> 00:33:28,970

744
00:33:28,970 --> 00:33:30,460
Hvad tror du der gik galt?

745
00:33:30,460 --> 00:33:31,219
Ja.

746
00:33:31,219 --> 00:33:32,135
>> Publikum: [uhørligt].

747
00:33:32,135 --> 00:33:36,387

748
00:33:36,387 --> 00:33:36,970
SPEAKER 1: Ah.

749
00:33:36,970 --> 00:33:37,550
Godt spørgsmål.

750
00:33:37,550 --> 00:33:39,508
Så størrelsen af ​​det antal
at jeg var opsummering

751
00:33:39,508 --> 00:33:41,920
fik så store, at det overskred
størrelsen af ​​den hukommelse.

752
00:33:41,920 --> 00:33:44,640
God idé, men ikke fundamentalt
kommer til at forårsage et nedbrud.

753
00:33:44,640 --> 00:33:48,230
Det kan forårsage heltalsoverløb,
hvor de bits bare vendes

754
00:33:48,230 --> 00:33:51,760
og så vi forveksler en virkelig stor
nummer som et negativt tal,

755
00:33:51,760 --> 00:33:53,260
men at selv ikke vil forårsage et styrt.

756
00:33:53,260 --> 00:33:55,509
Fordi i slutningen af
dag en int er stadig 32 bit.

757
00:33:55,509 --> 00:33:57,640
Du kommer ikke til
uheld stjæle en 33. bit.

758
00:33:57,640 --> 00:33:58,431
Men en god tanke.

759
00:33:58,431 --> 00:33:58,984
Ja.

760
00:33:58,984 --> 00:33:59,900
>> Publikum: [uhørligt].

761
00:33:59,900 --> 00:34:00,551

762
00:34:00,551 --> 00:34:02,300
SPEAKER 1: Metoden
aldrig stoppet,

763
00:34:02,300 --> 00:34:06,658
og ja det kalder sig igen
og igen og igen og igen

764
00:34:06,658 --> 00:34:08,449
og igen, og ingen af
disse funktioner nogensinde

765
00:34:08,449 --> 00:34:13,310
færdig, fordi deres eneste linje af
kode kalder sig selv igen og igen

766
00:34:13,310 --> 00:34:14,219
og igen.

767
00:34:14,219 --> 00:34:16,080
Og hvad der er virkelig
sker her, og nu har vi

768
00:34:16,080 --> 00:34:18,100
kan slags tegne dette billedligt.

769
00:34:18,100 --> 00:34:20,899
Lad mig gå over til en
billede for bare et øjeblik.

770
00:34:20,899 --> 00:34:22,940
Dette er et billede, der
i sidste ende vil konkretisere

771
00:34:22,940 --> 00:34:26,336
mere detaljeret, hvad der foregår på
indersiden af ​​din computers hukommelse.

772
00:34:26,336 --> 00:34:28,460
Og det viser sig, at der på
bunden af ​​dette billede

773
00:34:28,460 --> 00:34:29,709
er noget, der hedder stakken.

774
00:34:29,709 --> 00:34:31,920
Dette er et stykke
hukommelse, en luns af RAM,

775
00:34:31,920 --> 00:34:33,920
der er bare brugt nogen tid
en funktion kaldes.

776
00:34:33,920 --> 00:34:36,239
Hver gang du, en programmør,
kalde en funktion,

777
00:34:36,239 --> 00:34:38,860
operativsystemet, ligesom
Mac OS, Windows eller Linux,

778
00:34:38,860 --> 00:34:41,920
griber en flok bytes, måske en
kilobytes, måske få megabyte

779
00:34:41,920 --> 00:34:44,590
hukommelse, hænder dem
til dig, og derefter lader

780
00:34:44,590 --> 00:34:47,650
du kører din funktion ved hjælp
uanset variabler, du har brug for.

781
00:34:47,650 --> 00:34:50,699
Og hvis du så kalde en anden
funktion og en anden funktion,

782
00:34:50,699 --> 00:34:53,590
du får en anden skive hukommelse
og en anden skive hukommelse.

783
00:34:53,590 --> 00:34:57,090
>> Og ja, hvis disse grønne bakker
fra Annenberg repræsenterer den hukommelse,

784
00:34:57,090 --> 00:34:59,870
her er hvad der sker den første
gang du kalder funktionen sigma.

785
00:34:59,870 --> 00:35:04,510
Det er ligesom at sætte en bakke som denne
på hvad der er i første omgang en tom stak.

786
00:35:04,510 --> 00:35:07,142
Men derefter, hvis denne bakke
kalder sig selv, så at sige,

787
00:35:07,142 --> 00:35:08,850
ringer til en anden instans
Sigma, der er

788
00:35:08,850 --> 00:35:11,640
som at bede operativsystemet,
ooh, har brug for lidt mere hukommelse,

789
00:35:11,640 --> 00:35:12,520
Giv mig den.

790
00:35:12,520 --> 00:35:14,840
Og så det bliver stablet på på toppen.

791
00:35:14,840 --> 00:35:18,030
Men hvad er nøglen her, er, at
den første bakke er der stadig,

792
00:35:18,030 --> 00:35:20,620
fordi han påberåbt sig denne anden bakke.

793
00:35:20,620 --> 00:35:23,500
Nu mellemtiden sigma kalder sigma
det er ligesom at bede om mere hukommelse.

794
00:35:23,500 --> 00:35:25,830
Gets stablet på herovre.

795
00:35:25,830 --> 00:35:29,350
sigma kalder sigma, det er en anden
bakke, der bliver stablet på her.

796
00:35:29,350 --> 00:35:32,942
Og hvis du bliver ved med at gøre dette,
i sidste ende, at slags kort denne visuelle

797
00:35:32,942 --> 00:35:35,525
for det pågældende kort, hvad der kommer til
ske med stablen af ​​bakker?

798
00:35:35,525 --> 00:35:37,480

799
00:35:37,480 --> 00:35:41,160
Det kommer til at overstige det beløb,
hukommelse din computer har.

800
00:35:41,160 --> 00:35:45,790
Og så snart denne grønne bakke
overstiger den vandrette linje

801
00:35:45,790 --> 00:35:49,410
over stakken og over ordet dynge,
som vi vil vende tilbage til i fremtiden,

802
00:35:49,410 --> 00:35:50,410
det er en dårlig ting.

803
00:35:50,410 --> 00:35:52,810
Den bunke er en anden
segment af hukommelse,

804
00:35:52,810 --> 00:35:55,190
og hvis du lader disse
bakker bunke og bunke på,

805
00:35:55,190 --> 00:35:57,800
du kommer til at overskride
dit eget segment af hukommelse,

806
00:35:57,800 --> 00:36:00,420
og et program er faktisk kommer til at gå ned.

807
00:36:00,420 --> 00:36:02,930
>> Nu som en sidebemærkning, denne idé
rekursion derfor

808
00:36:02,930 --> 00:36:06,500
kan tydeligt føre til problemer, men
det er ikke nødvendigvis en dårlig ting.

809
00:36:06,500 --> 00:36:08,840
Fordi overveje, efter
alt hvordan-- og måske

810
00:36:08,840 --> 00:36:11,700
det tager lidt tid at vænne
til-hvor elegant eller hvordan enkle

811
00:36:11,700 --> 00:36:14,890
at gennemførelsen af ​​sigma var.

812
00:36:14,890 --> 00:36:17,440
Og vi kommer ikke til at bruge
rekursion så meget i CS50,

813
00:36:17,440 --> 00:36:20,780
men i CS51, og virkelig enhver klasse
hvor du manipulerer datastrukturer

814
00:36:20,780 --> 00:36:23,640
som træer, eller stamtræer,
at have en vis hierarki

815
00:36:23,640 --> 00:36:26,000
det er super, super nyttige.

816
00:36:26,000 --> 00:36:29,750
Nu, som en sidebemærkning, så du
som håbefulde dataloger

817
00:36:29,750 --> 00:36:33,180
er bekendt med nogle af Googles
interne jokes, hvis du går til Google

818
00:36:33,180 --> 00:36:36,345
og du ser op, hvad er det
definition af, siger, rekursion, indtast.

819
00:36:36,345 --> 00:36:40,208

820
00:36:40,208 --> 00:36:41,110
Uh-huh.

821
00:36:41,110 --> 00:36:42,670
Som en sidebemærkning, jeg trak op et par stykker.

822
00:36:42,670 --> 00:36:45,470
Dette var ligesom 10 minutter af
tøven i morges.

823
00:36:45,470 --> 00:36:52,890
Hvis du også Google "skævt", bekendtgørelse
ved at vippe dit hoved slightly--

824
00:36:52,890 --> 00:36:55,120
og så denne ene er måske
mest grusomme af alle

825
00:36:55,120 --> 00:36:57,286
da en person brugt ligesom
deres dag gennemførelse af denne

826
00:36:57,286 --> 00:36:59,880
nogle år ago-- komme videre.

827
00:36:59,880 --> 00:37:01,140

828
00:37:01,140 --> 00:37:04,540
Åh, wait-- det er en fejl.

829
00:37:04,540 --> 00:37:08,410

830
00:37:08,410 --> 00:37:11,410
>> Så kører på en af ​​de
verdens største hjemmesider

831
00:37:11,410 --> 00:37:13,510
er disse dumme små påskeæg.

832
00:37:13,510 --> 00:37:16,690
De forbruger sandsynligvis en
nontrivial antal linjer kode

833
00:37:16,690 --> 00:37:19,280
bare så vi kan få
lidt sjov ting.

834
00:37:19,280 --> 00:37:22,140
Men i det mindste nu får du
nogle af disse inde vittigheder.

835
00:37:22,140 --> 00:37:28,330
>> Lad os nu tage et kig på nogle af de
White Lies vi har fortalt for sent,

836
00:37:28,330 --> 00:37:30,707
og begynde at skrælle tilbage
nogle lag teknisk

837
00:37:30,707 --> 00:37:32,790
så du virkelig forstår
hvad der er foregået på

838
00:37:32,790 --> 00:37:34,860
og du kan forstå
nogle af de trusler,

839
00:37:34,860 --> 00:37:38,060
Ligesom Shellshock, at
er nu begyndt at blive

840
00:37:38,060 --> 00:37:41,110
på forkant med alles
vægt, i det mindste i medierne.

841
00:37:41,110 --> 00:37:45,810
Så her er en meget simpel funktion
der returnerer ingenting, ugyldige.

842
00:37:45,810 --> 00:37:46,790
Dens navn er swap.

843
00:37:46,790 --> 00:37:50,880
Det tager i to variabler
og det returnerer ingenting.

844
00:37:50,880 --> 00:37:52,260
Tager i a og b.

845
00:37:52,260 --> 00:37:53,337
Så en hurtig demonstration.

846
00:37:53,337 --> 00:37:54,170
Vi bragte dem op.

847
00:37:54,170 --> 00:37:56,100
Vi kan lige så godt tage lidt
pause her for et øjeblik

848
00:37:56,100 --> 00:37:57,250
og har lidt noget at drikke.

849
00:37:57,250 --> 00:38:00,120
Hvis nogen ikke har noget imod at tilslutte
mig op her for et øjeblik.

850
00:38:00,120 --> 00:38:01,830
Hvad med dig i rødbrun skjorte?

851
00:38:01,830 --> 00:38:02,335
Kom op.

852
00:38:02,335 --> 00:38:04,060

853
00:38:04,060 --> 00:38:05,260
Blot én dag.

854
00:38:05,260 --> 00:38:06,251
Tak, selv om.

855
00:38:06,251 --> 00:38:08,000
Okay, og vi har
kommer op der her?

856
00:38:08,000 --> 00:38:08,660
Hvad er dit navn?

857
00:38:08,660 --> 00:38:09,360
>> SPEAKER 4: Laura.

858
00:38:09,360 --> 00:38:09,740
>> SPEAKER 1: Laura.

859
00:38:09,740 --> 00:38:10,370
Kom op.

860
00:38:10,370 --> 00:38:11,460

861
00:38:11,460 --> 00:38:13,850
Så Laura, meget enkel udfordring i dag.

862
00:38:13,850 --> 00:38:14,704

863
00:38:14,704 --> 00:38:15,370
Rart at møde yo.

864
00:38:15,370 --> 00:38:16,410

865
00:38:16,410 --> 00:38:16,910
Okay.

866
00:38:16,910 --> 00:38:21,179
Så vi har nogle mælk herover og
vi har nogle appelsinsaft herovre

867
00:38:21,179 --> 00:38:23,345
og nogle kopper, vi
lånt fra Annenberg dag.

868
00:38:23,345 --> 00:38:24,178
>> SPEAKER 4: Lånt.

869
00:38:24,178 --> 00:38:27,240
SPEAKER 1: Og kommer til at gå videre
og give dig et halvt glas dette.

870
00:38:27,240 --> 00:38:28,250

871
00:38:28,250 --> 00:38:28,800
Okay.

872
00:38:28,800 --> 00:38:30,750
Og vi vil give dig halvdelen
et glas mælk.

873
00:38:30,750 --> 00:38:31,905

874
00:38:31,905 --> 00:38:35,890
Åh, og bare så du kan
huske, hvad det var ligesom,

875
00:38:35,890 --> 00:38:38,860
Jeg huskede at bringe
dette op og på i dag.

876
00:38:38,860 --> 00:38:42,030

877
00:38:42,030 --> 00:38:42,530
Okay.

878
00:38:42,530 --> 00:38:45,470
Hvis du ikke har noget imod, lad os se, vi
kan sætte dem over dine egne briller

879
00:38:45,470 --> 00:38:46,560
hvis du vil.

880
00:38:46,560 --> 00:38:48,710
Dette vil være den verden fra Lauras øjne.

881
00:38:48,710 --> 00:38:49,210
Okay.

882
00:38:49,210 --> 00:38:53,820
Så dit mål, da to kopper
flydende her, mælk og appelsinjuice,

883
00:38:53,820 --> 00:38:58,370
er bytte de to indholdet, så det
appelsinjuice går i mælken kop

884
00:38:58,370 --> 00:39:00,710
og mælken går i
appelsinsaft kop.

885
00:39:00,710 --> 00:39:02,359
>> SPEAKER 4: Får jeg en kop?

886
00:39:02,359 --> 00:39:05,650
SPEAKER 1: Jeg er så glad for du spurgte, selv om
det ville have været meget bedre optagelser

887
00:39:05,650 --> 00:39:06,710
hvis du ikke havde spurgt.

888
00:39:06,710 --> 00:39:10,620
Men ja, kan vi tilbyde dig en tredje
kop, der er tom, selvfølgelig.

889
00:39:10,620 --> 00:39:11,120
Okay.

890
00:39:11,120 --> 00:39:12,300
Så bytte indholdet der.

891
00:39:12,300 --> 00:39:16,100

892
00:39:16,100 --> 00:39:17,050
Very nice.

893
00:39:17,050 --> 00:39:20,390

894
00:39:20,390 --> 00:39:21,305
Meget godt.

895
00:39:21,305 --> 00:39:23,121

896
00:39:23,121 --> 00:39:24,745
Du gør dette bemærkelsesværdigt omhyggeligt.

897
00:39:24,745 --> 00:39:26,970

898
00:39:26,970 --> 00:39:28,655
Og trin tre.

899
00:39:28,655 --> 00:39:30,390

900
00:39:30,390 --> 00:39:31,350
Okay.

901
00:39:31,350 --> 00:39:31,930
Fremragende.

902
00:39:31,930 --> 00:39:33,930
Et stort bifald
ville være godt for Laura.

903
00:39:33,930 --> 00:39:36,500

904
00:39:36,500 --> 00:39:37,000
Okay.

905
00:39:37,000 --> 00:39:40,790
Vi har en lille afskedsgave
for dig, men lad mig tage dem.

906
00:39:40,790 --> 00:39:42,620
Tak så meget.

907
00:39:42,620 --> 00:39:46,170
Så et simpelt eksempel, selv om,
at vise, at hvis du gør

908
00:39:46,170 --> 00:39:48,300
vil bytte indholdet
af to containere,

909
00:39:48,300 --> 00:39:52,360
eller lad os kalde dem variabler,
du har brug for nogle midlertidige opbevaring

910
00:39:52,360 --> 00:39:56,710
at iscenesætte et af indholdet i så
at du rent faktisk kan gøre swappen.

911
00:39:56,710 --> 00:40:01,790
Så ja, denne kildekode op her i
C er repræsentativt for netop dette.

912
00:40:01,790 --> 00:40:06,340
Hvis appelsinsaft var og mælken
var B, og vi ønskede at bytte de to,

913
00:40:06,340 --> 00:40:08,990
du kunne prøve noget kreativt
ved at hælde en i den anden,

914
00:40:08,990 --> 00:40:11,031
men det sandsynligvis ikke ville
ende særlig godt.

915
00:40:11,031 --> 00:40:15,260
Og så bruger vi en tredje kop, opkald
det tmp, T-M-P af konventionen,

916
00:40:15,260 --> 00:40:19,370
og sætte indholdet af
EFT i det, så bytte en kop,

917
00:40:19,370 --> 00:40:22,610
derefter sætte EFT i
oprindelige kop, hvorved

918
00:40:22,610 --> 00:40:25,320
nå, præcis som
Laura gjorde, swappen.

919
00:40:25,320 --> 00:40:26,850
>> Så lad os gøre netop dette.

920
00:40:26,850 --> 00:40:30,110
Lad mig gå videre og åbne
op et eksempel, der er

921
00:40:30,110 --> 00:40:32,720
faktisk kaldt "nej
swap ", fordi det ikke er

922
00:40:32,720 --> 00:40:36,180
som blot gjort, som du måske tror.

923
00:40:36,180 --> 00:40:41,190
Så i dette program, bemærk at
Jeg bruger stdio.h, vores gamle ven.

924
00:40:41,190 --> 00:40:43,130
Jeg har prototypen
til swap deroppe, som

925
00:40:43,130 --> 00:40:45,450
betyder dens gennemførelse er
sandsynligvis ned nedenfor,

926
00:40:45,450 --> 00:40:48,050
og lad os se hvad denne hoved
Programmet kommer til at gøre for mig.

927
00:40:48,050 --> 00:40:52,020
Jeg først erklære int x får
en, og int y får to.

928
00:40:52,020 --> 00:40:54,930
Så tænk på dem som EFT
og mælk, hhv.

929
00:40:54,930 --> 00:40:57,100
Og så er jeg bare have en
printf siger x er dette

930
00:40:57,100 --> 00:41:00,120
og y er det, bare så jeg kan
visuelt se, hvad der foregår.

931
00:41:00,120 --> 00:41:03,810
Så jeg har printf hævder
at jeg bytte de to,

932
00:41:03,810 --> 00:41:07,100
og så vil jeg udskrive en
hævder, at de er byttet,

933
00:41:07,100 --> 00:41:09,300
og jeg udskrive x og y igen.

934
00:41:09,300 --> 00:41:13,010
Så hernede i swap er
præcis, hvad Laura gjorde,

935
00:41:13,010 --> 00:41:16,240
og præcis hvad vi så på
skærmen et øjeblik siden.

936
00:41:16,240 --> 00:41:19,380
>> Så lad os gå videre og
blive hårdt skuffet.

937
00:41:19,380 --> 00:41:24,690
Gør nogen swap, og køre nogen swap,
zoomer ind på outputtet her.

938
00:41:24,690 --> 00:41:28,320
Indtast x er 1, y er 2, bytte byttes.

939
00:41:28,320 --> 00:41:32,700
x er stadig 1, og y er stadig 2.

940
00:41:32,700 --> 00:41:37,630
Så selvom ærligt, det ser
præcis gerne, omend mere teknisk,

941
00:41:37,630 --> 00:41:40,730
hvad Laura gjorde, ikke synes at arbejde.

942
00:41:40,730 --> 00:41:42,130
Så hvorfor er det?

943
00:41:42,130 --> 00:41:46,630
Tja, det viser sig, at når
vi skriver et program som dette

944
00:41:46,630 --> 00:41:51,590
der har både hoved, fremhævet her,
og derefter en anden funktion, ligesom swap,

945
00:41:51,590 --> 00:41:54,230
fremhævet her, som
det opfordrer verden

946
00:41:54,230 --> 00:41:57,030
ser lidt noget lignende
disse bakker et øjeblik siden.

947
00:41:57,030 --> 00:42:00,440
Når vigtigste først bliver kaldt,
det er som at spørge styresystem

948
00:42:00,440 --> 00:42:04,030
for lidt hukommelse til enhver lokal
variabler som x og y som vigtigste har,

949
00:42:04,030 --> 00:42:05,660
og de ender dér.

950
00:42:05,660 --> 00:42:10,920
Men hvis de vigtigste opkald bytte, og de vigtigste
passerer at bytte to argumenter, a og b,

951
00:42:10,920 --> 00:42:16,410
appelsinjuice og mælk, det er ikke som
rakte appelsinsaft og mælk

952
00:42:16,410 --> 00:42:17,500
Laura.

953
00:42:17,500 --> 00:42:21,300
Hvad en computer gør, er det
passerer kopier af appelsinsaft

954
00:42:21,300 --> 00:42:27,110
og kopier af mælken til Laura, så der
hvad der er i sidste ende inde i denne bakke

955
00:42:27,110 --> 00:42:32,510
er værdien et og to eller EFT
og mælk, men kopier heraf,

956
00:42:32,510 --> 00:42:34,790
således at der på dette punkt
i historien, der

957
00:42:34,790 --> 00:42:36,930
er EFT og mælk i hver af disse bakker.

958
00:42:36,930 --> 00:42:39,260
Der er en en og en to
i hver af disse bakker,

959
00:42:39,260 --> 00:42:41,720
og swap-funktionen er faktisk fungerer.

960
00:42:41,720 --> 00:42:46,090
Det er at bytte dem inde
af det andet øverste bakke,

961
00:42:46,090 --> 00:42:48,147
men at swapping har ingen indvirkning.

962
00:42:48,147 --> 00:42:49,980
Og baseret på blot nogle
grundlæggende princip, vi har

963
00:42:49,980 --> 00:42:52,970
talte om før, og faktisk
blot et par minutter siden, hvad

964
00:42:52,970 --> 00:42:58,770
kan forklare, hvorfor skiftende
a og b indersiden af ​​swap

965
00:42:58,770 --> 00:43:05,560
har ingen effekt på x og y, selv om
Jeg passerede x og y til swap-funktionen.

966
00:43:05,560 --> 00:43:08,750
Hvad er nøgleordet her, at
måske simplistisk forklare?

967
00:43:08,750 --> 00:43:11,250

968
00:43:11,250 --> 00:43:12,627
Jeg tror, ​​jeg hørte det her?

969
00:43:12,627 --> 00:43:13,335
Publikum: Retur.

970
00:43:13,335 --> 00:43:14,085
SPEAKER 1: Return?

971
00:43:14,085 --> 00:43:14,590
Ikke vende tilbage.

972
00:43:14,590 --> 00:43:15,895
Lad os gå med en anden.

973
00:43:15,895 --> 00:43:16,395
Hvad er det?

974
00:43:16,395 --> 00:43:17,080
>> Publikum: [uhørligt].

975
00:43:17,080 --> 00:43:20,000
>> SPEAKER 1: OK, så return-- vi kunne
gøre tilbagevenden arbejde i historien,

976
00:43:20,000 --> 00:43:21,914
men der er en endnu enklere forklaring.

977
00:43:21,914 --> 00:43:22,580
Publikum: Scope.

978
00:43:22,580 --> 00:43:23,288
SPEAKER 1: Scope.

979
00:43:23,288 --> 00:43:24,300
Jeg tager rækkevidde.

980
00:43:24,300 --> 00:43:27,290
Så rækkevidde, huske, hvor
vores x og y er erklæret.

981
00:43:27,290 --> 00:43:30,840
De er erklæret inde
af de vigtigste lige heroppe.

982
00:43:30,840 --> 00:43:33,200
a og b, i mellemtiden, er
effektivt erklæret

983
00:43:33,200 --> 00:43:35,930
indersiden af ​​swap, ikke helt i
de krøllede parenteser, men stadig

984
00:43:35,930 --> 00:43:37,690
i det generelle område af swap.

985
00:43:37,690 --> 00:43:40,560
Og så ja, a og b
kun eksistere inden denne bakke

986
00:43:40,560 --> 00:43:44,850
fra Annenberg dette
anden luns af kode.

987
00:43:44,850 --> 00:43:49,500
Så vi er faktisk at ændre kopien, men
det er ikke virkelig alt, nyttige.

988
00:43:49,500 --> 00:43:52,190
>> Så lad os tage et kig på
denne lidt lavere niveau.

989
00:43:52,190 --> 00:43:55,430
Jeg har tænkt mig at gå tilbage til
Source Directory,

990
00:43:55,430 --> 00:43:58,330
og jeg har tænkt mig at først
zoome ind her, og bare

991
00:43:58,330 --> 00:44:02,290
at bekræfte, at jeg er i dette
større terminal vindue,

992
00:44:02,290 --> 00:44:04,430
Programmets stadig opfører sig sådan.

993
00:44:04,430 --> 00:44:06,840
Antag nu, at dette
er ikke tilsigtet.

994
00:44:06,840 --> 00:44:10,090
Klart jeg ville swap til
arbejde, så det føles som en fejl.

995
00:44:10,090 --> 00:44:12,780
Nu kunne jeg begynde at tilføje en
masse printf er til min kode,

996
00:44:12,780 --> 00:44:16,010
udskrivning ud x herovre, iy over
her, en herovre, B herovre.

997
00:44:16,010 --> 00:44:18,220
Men helt ærligt, det er hvad sandsynligvis
du har gjort for et par uger

998
00:44:18,220 --> 00:44:20,190
nu, i kontortiden
og hjemme, når du arbejder

999
00:44:20,190 --> 00:44:22,150
på psets forsøger at finde nogle bugs.

1000
00:44:22,150 --> 00:44:25,560
Men du vil se, hvis du ikke allerede har,
dette problem indstille tre introducerer dig

1001
00:44:25,560 --> 00:44:31,630
til en kommando kaldet GDB,
hvor GDB, GNU debugger,

1002
00:44:31,630 --> 00:44:34,040
har selv en hel masse
funktioner, der kan faktisk

1003
00:44:34,040 --> 00:44:38,160
lad os forstå situationer
som dette, men mere overbevisende,

1004
00:44:38,160 --> 00:44:39,940
løse problemer og finde fejl.

1005
00:44:39,940 --> 00:44:40,940
Så jeg har tænkt mig at gøre dette.

1006
00:44:40,940 --> 00:44:44,770
I stedet for ./noswap, jeg er i stedet
kommer til at køre GDB ./noswap.

1007
00:44:44,770 --> 00:44:47,410

1008
00:44:47,410 --> 00:44:51,200
Med andre ord, vil jeg køre min
programmet ikke i bash, vores nye ven

1009
00:44:51,200 --> 00:44:51,850
dag.

1010
00:44:51,850 --> 00:44:53,970
Jeg har tænkt mig at køre min
program noswap inde

1011
00:44:53,970 --> 00:44:56,900
af dette andet program kaldet
GDB, hvilket er en debugger, som

1012
00:44:56,900 --> 00:45:01,035
er et program, der er designet til at hjælpe
I mennesker finde og fjerne fejl.

1013
00:45:01,035 --> 00:45:03,410
Så hvis jeg ramte Køre her, der er
en grusom mængde tekst

1014
00:45:03,410 --> 00:45:04,868
at du virkelig aldrig nødt til at læse.

1015
00:45:04,868 --> 00:45:07,290
Det er hovedsagelig en distraktion
fra prompt, som

1016
00:45:07,290 --> 00:45:10,030
Jeg har tænkt mig at ramme Ctrl-L
at komme op på toppen er der.

1017
00:45:10,030 --> 00:45:11,800
Dette er GDB-prompten.

1018
00:45:11,800 --> 00:45:15,550
Hvis jeg ønsker at køre dette program nu,
da denne lille snyde ark på dagens

1019
00:45:15,550 --> 00:45:21,860
dias antyder, Run er den første
kommandoer, vi betød at indføre.

1020
00:45:21,860 --> 00:45:25,150
Og jeg bare at skrive
køre op her inde i GDB,

1021
00:45:25,150 --> 00:45:26,811
og ja det kørte mit program.

1022
00:45:26,811 --> 00:45:29,310
Nu er der nogle ekstra
udgange af skærmen som dette,

1023
00:45:29,310 --> 00:45:31,910
men det er GDB blot er anal
og fortæller os, hvad der foregår.

1024
00:45:31,910 --> 00:45:34,451
Du behøver ikke virkelig nødt til at bekymre sig
om disse oplysninger lige nu.

1025
00:45:34,451 --> 00:45:36,890
Men hvad er virkelig cool om
GDB, hvis jeg gør det igen--

1026
00:45:36,890 --> 00:45:42,100
Ctrl-L rydder screen-- lade mig gå
fremad og type "bryde hoved," derved,

1027
00:45:42,100 --> 00:45:45,743
når jeg trykker på Enter, indstilling, hvad der er
kaldet en pause punkt noswap.c,

1028
00:45:45,743 --> 00:45:51,270
linie 16, hvilket er hvor GDB
regnet ud mit program faktisk

1029
00:45:51,270 --> 00:45:53,070
er min funktion faktisk er.

1030
00:45:53,070 --> 00:45:55,070
Dette vil vi ignorere for nu
men det er den adresse

1031
00:45:55,070 --> 00:45:57,310
i hukommelsen specifikt om denne funktion.

1032
00:45:57,310 --> 00:46:00,240
Så nu når jeg skriver løbe,
mærke til, hvad der er køligt her.

1033
00:46:00,240 --> 00:46:05,650
Mit program bryder på den linje, jeg
fortalte GDB at holde pause udførelse på.

1034
00:46:05,650 --> 00:46:09,850
Så jeg behøver ikke at nu ændre min kode,
tilføje nogle printf s, rekompilere det, skal du køre

1035
00:46:09,850 --> 00:46:13,300
det, ændre, tilføje nogle printf s,
gemme det, rekompilere det, køre den.

1036
00:46:13,300 --> 00:46:18,100
Jeg kan bare gå gennem mit program
trin for trin for trin ved menneskelig hastighed,

1037
00:46:18,100 --> 00:46:20,880
ikke på Intel-inside slags hastighed.

1038
00:46:20,880 --> 00:46:24,580
>> Så nu mærke til denne linje
vises her, og hvis jeg gå tilbage

1039
00:46:24,580 --> 00:46:27,800
til mit program i gedit,
bemærke, at det er faktisk

1040
00:46:27,800 --> 00:46:29,280
den allerførste linje kode.

1041
00:46:29,280 --> 00:46:31,240
Der er linie 16 i gedit.

1042
00:46:31,240 --> 00:46:34,610
Der er linie 16 i GDB, og selv
selv om denne sorte og hvide grænseflade

1043
00:46:34,610 --> 00:46:37,760
er ikke nær så bruger
børn, betyder dette

1044
00:46:37,760 --> 00:46:41,680
denne linje 16 er ikke udført
endnu, men det handler om at være.

1045
00:46:41,680 --> 00:46:46,220
Så ja, hvis jeg skriver print
x, ikke printf, bare tryk x,

1046
00:46:46,220 --> 00:46:50,730
Jeg får nogle falske værdi der på nul,
da x ikke er blevet initialiseret endnu.

1047
00:46:50,730 --> 00:46:54,760
Så jeg har tænkt mig at skrive næste, eller, hvis du
ønsker at være fancy, bare n Til næste.

1048
00:46:54,760 --> 00:46:59,090
Men når jeg skriver næste komme ind, nu
bemærke det går videre til linie 17.

1049
00:46:59,090 --> 00:47:02,840
Så logisk, hvis jeg har henrettet
linie 16 og jeg nu skriver print x,

1050
00:47:02,840 --> 00:47:03,640
hvad skal jeg se?

1051
00:47:03,640 --> 00:47:04,970

1052
00:47:04,970 --> 00:47:05,520
One.

1053
00:47:05,520 --> 00:47:07,820
>> Og nu er det ganske vist forvirrende.

1054
00:47:07,820 --> 00:47:11,260
$ 2 er bare en fancy måde, hvis du
ønsker at henvise til denne værdi senere,

1055
00:47:11,260 --> 00:47:12,510
du kan sige "dollartegn to."

1056
00:47:12,510 --> 00:47:13,480
Det er ligesom en back reference.

1057
00:47:13,480 --> 00:47:14,570
Men for nu, bare ignorere det.

1058
00:47:14,570 --> 00:47:17,070
Det interessante er, hvad der er
på højre side af lighedstegnet.

1059
00:47:17,070 --> 00:47:21,000
Og nu, hvis jeg skriver næste gang
og udskrive y, skal jeg se 2.

1060
00:47:21,000 --> 00:47:23,870
Jeg kan nu også udskrive
x igen, og helt ærligt,

1061
00:47:23,870 --> 00:47:27,130
hvis jeg får lidt forvirret med hensyn til
hvor jeg er, kan jeg skrive liste for liste

1062
00:47:27,130 --> 00:47:30,590
og bare se nogle sammenhæng omkring
det punkt er jeg faktisk på.

1063
00:47:30,590 --> 00:47:35,180
Og nu kan jeg skrive
næste, og der x er 1.

1064
00:47:35,180 --> 00:47:36,300
Nu skriver jeg næste.

1065
00:47:36,300 --> 00:47:37,710
Åh, y er 2.

1066
00:47:37,710 --> 00:47:40,750
Og igen, det er forvirrende,
fordi GDB produktion

1067
00:47:40,750 --> 00:47:43,044
bliver blandet med min egen produktion.

1068
00:47:43,044 --> 00:47:45,710
Men hvis du huske på, ved
kigger frem og tilbage på din kode

1069
00:47:45,710 --> 00:47:47,740
eller om det ud side
side måske, vil du

1070
00:47:47,740 --> 00:47:51,020
se, at jeg virkelig er bare
stepping gennem mit program.

1071
00:47:51,020 --> 00:47:54,620
>> Men mærke til, hvad der sker næste, bogstaveligt talt.

1072
00:47:54,620 --> 00:47:56,380
Her er linie 22.

1073
00:47:56,380 --> 00:48:01,315
Lad mig gå over det, og derved bevæger sig på
til 23, og hvis jeg udskriver x nu, stadig en.

1074
00:48:01,315 --> 00:48:03,890
Og hvis jeg udskrive y nu, stadig en.

1075
00:48:03,890 --> 00:48:05,820
Så dette er ikke en nyttig øvelse.

1076
00:48:05,820 --> 00:48:07,450
Så lad os gentage denne.

1077
00:48:07,450 --> 00:48:10,069
Lad mig gå tilbage op til
top og type køre igen.

1078
00:48:10,069 --> 00:48:12,110
Og det siger programmet
der bliver fejlrettet

1079
00:48:12,110 --> 00:48:14,109
er allerede begyndt,
startede fra begyndelsen.

1080
00:48:14,109 --> 00:48:15,420
Ja, lad os gøre det igen.

1081
00:48:15,420 --> 00:48:22,000
Og denne gang lad os gøre næste,
næste, næste, næste, næste,

1082
00:48:22,000 --> 00:48:24,180
men nu tingene bliver interessante.

1083
00:48:24,180 --> 00:48:27,760
Nu vil jeg træde ind
swap, så kan jeg ikke skrive det næste.

1084
00:48:27,760 --> 00:48:34,380
Jeg skriver skridt, og nu mærke til det
har sprunget mig til noswap.c linje 33.

1085
00:48:34,380 --> 00:48:37,240
Hvis jeg går tilbage til gedit, hvad er linje 33?

1086
00:48:37,240 --> 00:48:40,500
Det er den første egentlige
linje kode inde i swap.

1087
00:48:40,500 --> 00:48:44,150
Hvilket er rart, fordi jeg nu kan
slags poke rundt og få nysgerrige

1088
00:48:44,150 --> 00:48:46,052
om, hvad der foregår i sandhed derinde.

1089
00:48:46,052 --> 00:48:46,760
Lad mig udskrive tmp.

1090
00:48:46,760 --> 00:48:47,770

1091
00:48:47,770 --> 00:48:48,800
Whoa.

1092
00:48:48,800 --> 00:48:51,438
Hvorfor tmp har nogle
skøre, fup skrald værdi?

1093
00:48:51,438 --> 00:48:54,579

1094
00:48:54,579 --> 00:48:56,120
PUBLIKUM: Det er ikke blevet initialiseret.

1095
00:48:56,120 --> 00:48:57,150
SPEAKER 1: Det er ikke blevet initialiseret.

1096
00:48:57,150 --> 00:49:00,270
Og ja, når du kører et program,
du er givet en hel bunke af hukommelse

1097
00:49:00,270 --> 00:49:03,392
af operativsystemet, men du
har ikke initialiseret nogle værdier,

1098
00:49:03,392 --> 00:49:05,600
så uanset bit du
se her, selvom det er

1099
00:49:05,600 --> 00:49:07,770
denne vanvittige stor negativ
nummer, betyder bare,

1100
00:49:07,770 --> 00:49:10,750
at det er de rester fra
nogle tidligere brug af denne RAM,

1101
00:49:10,750 --> 00:49:13,050
selvom jeg har ikke
selv havde brug for det endnu.

1102
00:49:13,050 --> 00:49:17,086
Så nu har jeg tænkt mig at gå videre og typen
næste, og hvis jeg nu skriver print tmp

1103
00:49:17,086 --> 00:49:17,835
hvad skal jeg se?

1104
00:49:17,835 --> 00:49:19,570

1105
00:49:19,570 --> 00:49:23,360
Uanset værdien af ​​en var
a er det første argument, bare

1106
00:49:23,360 --> 00:49:25,550
Ligesom x var den første
ting bliver vedtaget i,

1107
00:49:25,550 --> 00:49:30,450
så en og x skal være den samme,
så udskrive TMP bør udskrive mig en.

1108
00:49:30,450 --> 00:49:36,360
>> Så hvad du vil se i problem sæt
tre er en tutorial slags på GDB,

1109
00:49:36,360 --> 00:49:40,020
men indse, at dette er begyndelsen
af et kig på et værktøj, der vil faktisk

1110
00:49:40,020 --> 00:49:42,774
hjælpe dig med at løse problemer
så meget mere effektivt.

1111
00:49:42,774 --> 00:49:44,690
Hvad vi er i sidste ende
kommer til at gøre på onsdag

1112
00:49:44,690 --> 00:49:48,180
er begynde at skrælle et par lag
og fjerne nogle støttehjul.

1113
00:49:48,180 --> 00:49:50,496
Denne ting kaldet streng,
vi har brugt i nogen tid,

1114
00:49:50,496 --> 00:49:53,370
vi vil langsomt tage det væk
fra dig og begynde at tale om

1115
00:49:53,370 --> 00:49:55,725
noget mere esoterisk
kendt som char *,

1116
00:49:55,725 --> 00:49:59,550
men vi vil gøre dette nice og
først svagt, selvom pegepinde,

1117
00:49:59,550 --> 00:50:02,730
som de kaldes, kan gøre nogle
meget dårlige ting hvis de misbruges,

1118
00:50:02,730 --> 00:50:06,040
ved at se på en lille claymation fra
vores ven Nick Parlante fra Stanford

1119
00:50:06,040 --> 00:50:09,670
University, professor i computer
videnskab, der tilsammen denne forhåndsvisning

1120
00:50:09,670 --> 00:50:11,075
af, hvad der er at komme denne onsdag.

1121
00:50:11,075 --> 00:50:12,196

1122
00:50:12,196 --> 00:50:13,400
>> [VIDEOAFSPILNING]

1123
00:50:13,400 --> 00:50:13,900
Hey, Binky.

1124
00:50:13,900 --> 00:50:14,930

1125
00:50:14,930 --> 00:50:15,780
Vågn op.

1126
00:50:15,780 --> 00:50:17,240
Det er tid til pointer sjov.

1127
00:50:17,240 --> 00:50:18,260

1128
00:50:18,260 --> 00:50:19,350
>> Hvad er det?

1129
00:50:19,350 --> 00:50:21,150
Lær om pointers?

1130
00:50:21,150 --> 00:50:22,050
Åh, goody!

1131
00:50:22,050 --> 00:50:22,897

1132
00:50:22,897 --> 00:50:23,730
[END VIDEO PLAYBACK]

1133
00:50:23,730 --> 00:50:25,396
SPEAKER 1: der venter dig på onsdag.

1134
00:50:25,396 --> 00:50:26,440
Vi vil se dig derefter.

1135
00:50:26,440 --> 00:50:27,106
[VIDEOAFSPILNING]

1136
00:50:27,106 --> 00:50:30,420
-Og Nu, dybe tanker,
af Daven Farnham.

1137
00:50:30,420 --> 00:50:33,980

1138
00:50:33,980 --> 00:50:35,900
>> Hvorfor lærer vi C?

1139
00:50:35,900 --> 00:50:36,785
Hvorfor ikke A +?

1140
00:50:36,785 --> 00:50:38,550

1141
00:50:38,550 --> 00:50:40,910
>> [Latter]

1142
00:50:40,910 --> 00:50:42,160
>> [END VIDEO PLAYBACK]