1
00:00:00,000 --> 00:00:12,040
>> [Musikk spilles]

2
00:00:12,040 --> 00:00:16,460
>> SPEAKER 1: Ok, dette er CS50,
og dette er begynnelsen av uke fire,

3
00:00:16,460 --> 00:00:20,420
og som du kanskje har hørt eller
lese, har verden blitt slutt.

4
00:00:20,420 --> 00:00:23,520
Går alle rundt på internett
har vært kunnskap og bevissthet

5
00:00:23,520 --> 00:00:27,100
av en feil i et program, en
programmeringsspråk kalt Bash.

6
00:00:27,100 --> 00:00:32,729
Dette har vært fantastisk branded
som Shellshock, eller Bash døren,

7
00:00:32,729 --> 00:00:35,485
men artikler som dette
har ikke vært uvanlig.

8
00:00:35,485 --> 00:00:38,807
Og faktisk, mange av dem bringe
tilbake minner Heartbleed,

9
00:00:38,807 --> 00:00:41,640
som du kanskje har lagt merke til i
trykk tilbake denne siste våren, som

10
00:00:41,640 --> 00:00:43,980
var tilsvar ganske dramatisk.

11
00:00:43,980 --> 00:00:47,110
Nå for de av dere her
i dag, hvor mange av dere har,

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

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

14
00:00:51,370 --> 00:00:54,245
Greit, og hvor mange av dere
har datamaskiner 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 det være langt, langt flere hender
opp akkurat nå, av grunner vi skal se.

17
00:01:00,250 --> 00:01:02,580
>> La oss ta en titt på hva som er
pågått i media

18
00:01:02,580 --> 00:01:05,304
og deretter forklare det litt
her for oss teknisk.

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

20
00:01:07,670 --> 00:01:11,250
>> SPEAKER 2: Sikkerhetseksperter har
advarte om at en alvorlig feil kunne

21
00:01:11,250 --> 00:01:15,650
være i ferd med å påvirke hundrevis av
millioner av verdens nettbrukere.

22
00:01:15,650 --> 00:01:20,600
Så hva er egentlig feilen som har vært
kalt Shellshock, og hva gjør det?

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

24
00:01:23,720 --> 00:01:28,910
Vel, er Shellshock også kjent som
Bash bug, programvaren den utnytter.

25
00:01:28,910 --> 00:01:33,230
Hackere bruker viruset til å skanne sårbare
systemer som kjører Linux og Unix

26
00:01:33,230 --> 00:01:36,300
operativsystemer og deretter infisere dem.

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

28
00:01:38,730 --> 00:01:43,460
Dette lar brukere gi kommandoer til å lansere
programmer og funksjoner i programvare

29
00:01:43,460 --> 00:01:45,250
ved å skrive inn tekst.

30
00:01:45,250 --> 00:01:49,980
Det er vanligvis brukt av programmerere, og
bør ikke være åpen for resten av verden,

31
00:01:49,980 --> 00:01:51,590
om Shellshock endrer dette.

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

33
00:01:54,160 --> 00:01:57,910
>> Vel, worringly, enkelte analytikere
advare det kan være en større trussel,

34
00:01:57,910 --> 00:02:01,580
fordi Shellshock gir full
styring av en infisert maskin,

35
00:02:01,580 --> 00:02:06,030
mens Heartbleed bare tillatt
hackere å spionere på datamaskiner.

36
00:02:06,030 --> 00:02:09,130
Det er så alvorlig, det er
vært vurdert en 10 av 10

37
00:02:09,130 --> 00:02:11,900
for alvorlighetsgraden av National
Vulnerability Database.

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

39
00:02:15,530 --> 00:02:20,015
2/3 av alle webservere er på
risiko, inkludert noen Mac-datamaskiner.

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

41
00:02:22,760 --> 00:02:25,600
Vel, må du
lappe systemene nå.

42
00:02:25,600 --> 00:02:29,330
Alle som vertskap for et nettsted som kjører
de berørte operativsystemene

43
00:02:29,330 --> 00:02:31,800
bør iverksette tiltak så snart som mulig.

44
00:02:31,800 --> 00:02:35,390
Alle som har råd til det bør se
til sin overvåking og web-applikasjon

45
00:02:35,390 --> 00:02:37,355
brannmurer for å se etter eventuelle angrep.

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

47
00:02:39,979 --> 00:02:41,770
SPEAKER 3: Verste
som kan skje er

48
00:02:41,770 --> 00:02:45,080
at noen ville skrive kode som
automatisk ville gå og skanne

49
00:02:45,080 --> 00:02:48,280
Internett og vil påvirke
alle disse datamaskinene.

50
00:02:48,280 --> 00:02:50,710
Og når de gjør det, vel,
det verste de kunne gjøre

51
00:02:50,710 --> 00:02:53,300
er det bare å slette alt,
eller stenge nettstedene ned.

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

53
00:02:55,360 --> 00:02:58,300
der vi ville ha ondsinnede mennesker
som bare bestemmer seg for å føre til kaos

54
00:02:58,300 --> 00:03:02,534
ved å bringe systemer ned eller slette
filer, og sånt.

55
00:03:02,534 --> 00:03:05,200
SPEAKER 2: Noen sier dette er en
av de mest vanskelige å måle

56
00:03:05,200 --> 00:03:08,080
bugs i år, og det
kan ta uker eller til og med

57
00:03:08,080 --> 00:03:10,820
måneder for å bestemme dens endelige virkning.

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

59
00:03:12,180 --> 00:03:15,560
>> SPEAKER 1: Så alt dette er sant,
men det morsomme er, nesten alle

60
00:03:15,560 --> 00:03:18,330
av bildene du nettopp så,
med unntak av kanskje tastaturet,

61
00:03:18,330 --> 00:03:20,930
har ingenting å gjøre med
feilen overhodet.

62
00:03:20,930 --> 00:03:23,960
Servere og ledninger og så videre,
Det er liksom tangentially relatert,

63
00:03:23,960 --> 00:03:27,410
men i kjernen er det faktisk ganske
kjent hva som skjer her.

64
00:03:27,410 --> 00:03:30,050
Faktisk, la meg gå inn
vår CS50 apparatet.

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

66
00:03:32,910 --> 00:03:36,020
Og dere har brukt denne,
eller den innebygde versjon derav,

67
00:03:36,020 --> 00:03:39,460
i gedit for å skrive programmer,
skriver kommandoer, og så videre,

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

69
00:03:43,690 --> 00:03:46,890
Dette er Bourne-Again Shell,
som er bare en fancy måte å si,

70
00:03:46,890 --> 00:03:50,220
Dette er et program som har en
blinkende rask, effektivt,

71
00:03:50,220 --> 00:03:51,970
som sitter der og venter
for innspill for deg.

72
00:03:51,970 --> 00:03:53,920
Og det er kommandoen
grensesnitt via hvilke

73
00:03:53,920 --> 00:03:57,650
dere har kjørt kommandoer og
slutt å kompilere og deretter kjører

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

75
00:03:58,400 --> 00:04:01,320
>> Men Bash er også et programmer
språket i det følgende måte.

76
00:04:01,320 --> 00:04:05,460
Du vet at det finnes 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 å implementere dem i Bash.

78
00:04:09,580 --> 00:04:11,420
Nå er vi ikke kommer til å
gå i stor detalj

79
00:04:11,420 --> 00:04:16,089
som å Bash i programmeringsspråk, men
vet, for eksempel, som i øyeblikket,

80
00:04:16,089 --> 00:04:17,607
det er ingen kommando som heter "hei."

81
00:04:17,607 --> 00:04:19,440
Så kan det bli funnet i
en av disse pakker.

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

83
00:04:20,856 --> 00:04:21,870
Spør administratoren.

84
00:04:21,870 --> 00:04:26,030
Men hvis jeg ønsker at det skal være et program
kalt "hallo" i Bash eller på min teksten,

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

86
00:04:30,810 --> 00:04:35,020
men det ser ganske lik en
funksjon, riktignok mangler noen detaljer.

87
00:04:35,020 --> 00:04:38,090
Ingenting ser ut til å skje,
men nå hvis jeg skriver "Hei,"

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

89
00:04:40,960 --> 00:04:44,280
ikke i et annet programmerings
språk, men i Bash seg selv.

90
00:04:44,280 --> 00:04:47,630
>> Nå nøkkelen her er at jeg skrev
navn jeg ønsket å gi denne nye kommandoen

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

92
00:04:50,820 --> 00:04:54,010
Som en side, kan du også gjøre det gøy
ting, og faktisk, selv om Mac OS,

93
00:04:54,010 --> 00:04:55,620
Dette er et program som heter Terminal.

94
00:04:55,620 --> 00:04:58,800
Det kommer innebygd i noens
datamaskin som har en Mac i dette rommet,

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

96
00:05:03,640 --> 00:05:07,110
Og dette er litt tangential,
men det er like gøy.

97
00:05:07,110 --> 00:05:09,715
Jeg ble minnet om denne morgenen,
når du tenker dette gjennom,

98
00:05:09,715 --> 00:05:13,279
av et lite spill jeg pleide å spille
med en av CS50 tidligere TFS

99
00:05:13,279 --> 00:05:16,570
hvor som helst han ville gå bort fra
hans tastatur med skjermen sin ulåst,

100
00:05:16,570 --> 00:05:23,611
Jeg vil utføre en kommando
som dette-- "si hei."

101
00:05:23,611 --> 00:05:26,610
Og nå helst han kom tilbake til sin
tastaturet etter at jeg ryddet skjermen

102
00:05:26,610 --> 00:05:27,985
og han ville sitte ned,
prøve å gjøre noe arbeid,

103
00:05:27,985 --> 00:05:29,250
vise innholdet i hans directory--

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

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
Hei.

108
00:05:32,120 --> 00:05:35,030
>> SPEAKER 1: Så, i rettferdighet,
det var faktisk ikke "hei."

109
00:05:35,030 --> 00:05:36,894
Det var som regel noe
mer beslektet med at--

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

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å hans datamaskin ville

113
00:05:39,320 --> 00:05:42,170
sverger på ham som helst han faktisk
satte seg på hans tastatur.

114
00:05:42,170 --> 00:05:46,265
Og veldig raskt han funnet ut
ikke å forlate sin skjerm ulåst.

115
00:05:46,265 --> 00:05:48,730
Men dette tyder slags
av dumme gøy at du

116
00:05:48,730 --> 00:05:50,210
kan ha med noe sånt som Bash.

117
00:05:50,210 --> 00:05:52,770
Men det er litt mer
alvorlige, for å være sikker på, enn.

118
00:05:52,770 --> 00:05:57,235
Og faktisk, dette er en av de
farligste og mest langvarige feil

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

120
00:05:58,860 --> 00:06:02,060
Denne feilen har eksistert
for noen 20 år,

121
00:06:02,060 --> 00:06:05,780
og du vil bli rammet i løpet av et
øyeblikk av sin relative enkelhet.

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

123
00:06:07,990 --> 00:06:10,448
eier en Mac, bokstavelig talt akkurat nå
når du har din lokket åpent,

124
00:06:10,448 --> 00:06:12,940
du kan prøve å skrive inn i den
program kalt Terminal.

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

126
00:06:15,410 --> 00:06:18,790
for en gangs skyld, trenger Windows-brukere ikke trenger å
bekymre deg for dette spesielle threat--

127
00:06:18,790 --> 00:06:22,310
men de av dere med Mac-maskiner kan skrive
dette inn i et vindu som jeg skal gjøre her,

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

129
00:06:24,210 --> 00:06:28,830
kalt Terminal, som jeg gjør nå,
hvis du ser ordet "sårbare"

130
00:06:28,830 --> 00:06:32,200
datamaskinen er
sårbare for utnytting.

131
00:06:32,200 --> 00:06:33,850
>> Nå hva betyr det egentlig?

132
00:06:33,850 --> 00:06:35,870
Og dette er riktignok
noen ganske gal syntaks,

133
00:06:35,870 --> 00:06:39,050
men la oss i det minste trekke ut
noen av de interessante sider ved.

134
00:06:39,050 --> 00:06:42,567
Så det er noen syntaks som ser
litt kjent, i det minste fra C

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

136
00:06:43,950 --> 00:06:47,550
Jeg ser noen parentes,
semikolon, klammeparentes, og slikt,

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

138
00:06:50,820 --> 00:06:53,580
er egentlig en funksjon
som ikke gjør noe.

139
00:06:53,580 --> 00:06:57,840
Tykktarmen del gjøre ingenting, og
semikolon betyr slutte å gjøre ingenting.

140
00:06:57,840 --> 00:07:00,250
Så innsiden av disse
klammeparentes, det faktum

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

142
00:07:02,440 --> 00:07:05,500
er i hovedsak å opprette
en kommando eller en variabel,

143
00:07:05,500 --> 00:07:09,520
heter x, og tilordne den
at gul bit av koden der.

144
00:07:09,520 --> 00:07:14,040
Det kan være noe sånt som "echo
Hallo "eller" si pip "eller noe

145
00:07:14,040 --> 00:07:15,120
beslektet med det.

146
00:07:15,120 --> 00:07:17,780
Men legg merke til om øynene dine
vandre videre til høyre,

147
00:07:17,780 --> 00:07:22,150
det er mer til denne linjen enn
bare enden av det semikolon.

148
00:07:22,150 --> 00:07:25,160
"Echo sårbar", og deretter
utover at det er enda mer.

149
00:07:25,160 --> 00:07:26,530
En annen 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 linjen med kode er

152
00:07:34,050 --> 00:07:36,660
tilstrekkelig for overbevisende
en datamaskin som er

153
00:07:36,660 --> 00:07:39,830
sårbare for å gjøre noe
at du vil den skal gjøre,

154
00:07:39,830 --> 00:07:44,290
fordi det er en bug i Bash der
selv om Bash skulle stoppe

155
00:07:44,290 --> 00:07:48,980
lese linjer med kommandoen rett
der etter den gule teksten,

156
00:07:48,980 --> 00:07:52,520
for en 20-pluss år gamle bug,
Bash har faktisk vært å lese

157
00:07:52,520 --> 00:07:56,780
utover at semikolon og pen
mye gjør det den er fortalt.

158
00:07:56,780 --> 00:07:59,070
>> Så hva er implikasjonen
av det til slutt?

159
00:07:59,070 --> 00:08:01,340
Jeg sa bare "echo hello"
eller "echo sårbar,"

160
00:08:01,340 --> 00:08:05,449
men hva om du gjorde noe
faktisk skadelig, som rm-rf *,

161
00:08:05,449 --> 00:08:07,240
som du kanskje ikke
noen gang har skrevet før,

162
00:08:07,240 --> 00:08:08,920
og ærlig du sannsynligvis
bør ikke for tidlig,

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

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

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

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

167
00:08:14,270 --> 00:08:15,930
* Betyr hva?

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

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

170
00:08:18,180 --> 00:08:20,410
slette alt i
gjeldende katalog.

171
00:08:20,410 --> 00:08:23,379
-r skjer til å bety rekursiv,
som betyr at hvis hva du sletter

172
00:08:23,379 --> 00:08:26,420
er en katalog, og innsiden av det
er andre filer og andre kataloger,

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

174
00:08:28,950 --> 00:08:31,040
Og -f er den verste av dem alle.

175
00:08:31,040 --> 00:08:32,580
Alle vet hva f betyr her?

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

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

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

179
00:08:37,830 --> 00:08:40,939
gjøre det uten å spørre meg
for ytterligere bekreftelse.

180
00:08:40,939 --> 00:08:43,230
Så, vet du, ler vi på
dette, men ærlig, jeg sannsynligvis

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

182
00:08:44,972 --> 00:08:47,210
er det er den raskeste måten å
slette en hel haug med ting.

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

184
00:08:48,590 --> 00:08:53,100
>> Men hvis du skulle lure en datamaskin
til å definere noen dum variabel

185
00:08:53,100 --> 00:08:56,810
eller funksjon kalt x, men da
lure datamaskinen i utføring

186
00:08:56,810 --> 00:09:00,030
utover grensene for det
funksjon, utover at semikolon,

187
00:09:00,030 --> 00:09:04,430
du kan faktisk lure en datamaskin
til å utføre noe sånt rm-rf

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

189
00:09:07,810 --> 00:09:11,400
Noe bokstavelig talt kan du gjøre med
datamaskin, enten det er å slette filer,

190
00:09:11,400 --> 00:09:15,350
skape filer, spamming noen,
angripe noen server eksternt,

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

192
00:09:17,190 --> 00:09:19,120
kan lure en datamaskin til å gjøre det.

193
00:09:19,120 --> 00:09:21,510
>> Nå hva er et eksempel på
hvordan du kan gjøre dette?

194
00:09:21,510 --> 00:09:24,300
Vel, det er mye av datamaskiner
på internett kjører Bash.

195
00:09:24,300 --> 00:09:26,390
Alle av oss Mac-brukere er blant dem.

196
00:09:26,390 --> 00:09:30,390
Mange Linux-servere er blant
dem også, og Unix-servere.

197
00:09:30,390 --> 00:09:32,630
Windows igjen får
relativt av kroken

198
00:09:32,630 --> 00:09:34,590
med mindre du har installert
spesiell programvare.

199
00:09:34,590 --> 00:09:37,130
Nå er en rekke servere, for
eksempel, kjører web-servere,

200
00:09:37,130 --> 00:09:39,840
og faktisk Linux er kanskje det
mest populære operativsystemet

201
00:09:39,840 --> 00:09:43,060
å kjøre på datamaskiner på internett
som tjenestegjør opp websider.

202
00:09:43,060 --> 00:09:44,910
Nå som vi skal se senere
i semesteret, da

203
00:09:44,910 --> 00:09:48,470
du sende en anmodning fra
din 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 seg at selv om
du nettopp har skrevet www.example.com,

206
00:09:53,730 --> 00:09:59,590
Nettleseren din er å sende en melding
som er litt mer uforståelige, som dette.

207
00:09:59,590 --> 00:10:01,239
>> Men legg merke til en litt noe rart.

208
00:10:01,239 --> 00:10:03,030
De to første linjene
Jeg har aldri sett før,

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

210
00:10:04,904 --> 00:10:08,030
Men legg merke til hva jeg har stjålet
for tredje linje her.

211
00:10:08,030 --> 00:10:13,390
Hvis en dårlig fyr var å sende en melding
som dette fra hans eller hennes datamaskin

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

213
00:10:17,270 --> 00:10:21,580
det morsomme er at Bash,
som enkel liten ledeteksten,

214
00:10:21,580 --> 00:10:27,450
er allestedsnærværende, og er ofte
brukt til å hovedsaklig utføre

215
00:10:27,450 --> 00:10:30,020
innholdet i en
melding om at den mottar.

216
00:10:30,020 --> 00:10:33,490
Og den logikken, kan du
lure en web server, derfor

217
00:10:33,490 --> 00:10:36,370
ved å sende noe sånt
User-Agent, som vanligvis

218
00:10:36,370 --> 00:10:38,300
er ment å si
navn på nettleseren din.

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

220
00:10:42,420 --> 00:10:44,590
er bare i nettleseren
måte å identifisere seg selv.

221
00:10:44,590 --> 00:10:46,605
Men hvis en bad guy veldig
kløktig sier, mm-mm, jeg er

222
00:10:46,605 --> 00:10:47,930
ikke tenkt å fortelle deg
hva nettleseren min er,

223
00:10:47,930 --> 00:10:50,888
Jeg i stedet kommer til å sende deg dette
kryptisk-ser ting med en rm-rf

224
00:10:50,888 --> 00:10:55,840
* I det, kan du bokstavelig talt lure en
sårbare web server på internett

225
00:10:55,840 --> 00:10:59,055
til å utføre akkurat det i
der for å slette alle filene.

226
00:10:59,055 --> 00:11:00,930
Og ærlig talt, det er ikke
selv de verste av det.

227
00:11:00,930 --> 00:11:01,763
Du kan gjøre noe.

228
00:11:01,763 --> 00:11:04,480
Du kan starte et distribuert
denial of service angrep

229
00:11:04,480 --> 00:11:07,030
Hvis du sendte denne meldingen til
hele bunter av webservere

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

231
00:11:10,256 --> 00:11:12,130
og du kan sortere på bang
pokker ut av dem

232
00:11:12,130 --> 00:11:15,490
av en nettverkstrafikk som var
ellers utløses av dette dårlig fyr.

233
00:11:15,490 --> 00:11:18,760
>> Så, lang historie kort, nesten
alle i dette rommet som eier en Mac

234
00:11:18,760 --> 00:11:20,240
er utsatt for dette.

235
00:11:20,240 --> 00:11:24,100
The silver lining er at med mindre du er
kjører en webserver på den bærbare datamaskinen,

236
00:11:24,100 --> 00:11:27,780
og med mindre du faktisk har konfigurert
det å tillate noe som SSH inn i det,

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

238
00:11:28,670 --> 00:11:31,710
Det er sårbare, men det er ingen
en prøver å komme inn i den bærbare datamaskinen,

239
00:11:31,710 --> 00:11:33,290
slik at du kan liksom være trygg.

240
00:11:33,290 --> 00:11:36,210
Men Apple vil snart
være å oppdatere en løsning på dette.

241
00:11:36,210 --> 00:11:39,660
Verden av Linux har allerede sluppet
en rekke feilrettinger for Fedora og Ubuntu

242
00:11:39,660 --> 00:11:43,790
og andre versjoner av Linux, og faktisk
hvis du kjører oppdatering 50 i apparatet,

243
00:11:43,790 --> 00:11:45,930
selv det også vil være
oppdatert og korrigert.

244
00:11:45,930 --> 00:11:47,764
Men som også har ikke
virkelig vært sårbar,

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

246
00:11:49,804 --> 00:11:52,770
og gjort den bærbare datamaskinen offentlig
tilgjengelig på internett, som ikke er

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

248
00:11:54,910 --> 00:11:56,890
av brannmur og andre teknikker.

249
00:11:56,890 --> 00:12:01,000
>> Men det er et ekstremt eksempel på en feil
at vi har levd for for bokstavelig talt 20

250
00:12:01,000 --> 00:12:04,050
år, og hvem vet om noen
hele denne tiden har visst om det?

251
00:12:04,050 --> 00:12:06,300
Og faktisk, dette er en av
de grunnleggende utfordringene

252
00:12:06,300 --> 00:12:08,690
at vi får se senere i
semester om sikkerhet,

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

254
00:12:13,020 --> 00:12:16,500
For å holde skurkene ut, må vi
sørge for at alle dører er låst,

255
00:12:16,500 --> 00:12:20,340
at hvert vindu er sikker, at
hvert punkt trer inn i et hjem

256
00:12:20,340 --> 00:12:21,980
er sikkert å holde skurkene ut.

257
00:12:21,980 --> 00:12:26,870
Men hva gjør den slemme må
gjøre for å faktisk kompromittere ditt hjem

258
00:12:26,870 --> 00:12:28,200
og stjele fra deg?

259
00:12:28,200 --> 00:12:32,574
Han eller hun må bare finne en ulåst
dør, en knust vindu, eller noe

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

261
00:12:35,240 --> 00:12:37,660
Vi kan skrive millioner av
linjer med programmeringskode

262
00:12:37,660 --> 00:12:40,570
og bruke hundrevis eller tusenvis
timer prøver å få det riktig,

263
00:12:40,570 --> 00:12:43,370
men hvis du gjør bare én
feil i nøyaktighet,

264
00:12:43,370 --> 00:12:47,030
du kan sette hele systemet og
faktisk i dette tilfelle hele internett

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 har lyst til å lære mer
om dette, kan du gå til denne nettadressen her.

267
00:12:51,950 --> 00:12:54,450
Det er ikke behov for handling
i kveld med mindre du er

268
00:12:54,450 --> 00:12:57,116
blant dem mer komfortable at
har kjørt din egen web

269
00:12:57,116 --> 00:12:59,810
server, i så fall bør du,
faktisk, oppdatere programvaren.

270
00:12:59,810 --> 00:13:03,244
>> Og dette også er tittelen på
en tale, og nå et papir,

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

272
00:13:05,410 --> 00:13:07,600
Det var av en fyr
heter Ken Thompson, som

273
00:13:07,600 --> 00:13:10,120
var imot en svært berømt
award i informatikk,

274
00:13:10,120 --> 00:13:13,495
og han ga denne talen noen år
siden, i hovedsak på samme tema.

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

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

277
00:13:20,520 --> 00:13:23,480
tillit, til slutt,
Programvaren du har fått?

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

279
00:13:26,100 --> 00:13:27,820
og vi har vært kompilering
dem med Clang.

280
00:13:27,820 --> 00:13:31,830
Og til din kunnskap, du har skrevet
noen programmer for CS50 hvor det er

281
00:13:31,830 --> 00:13:35,310
en bakdør slags, det er en måte
som en dårlig fyr, hvis du kjører programmet,

282
00:13:35,310 --> 00:13:37,410
kunne ta over datamaskinen?

283
00:13:37,410 --> 00:13:38,310
Sannsynligvis ikke, ikke sant?

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 ganske små programmer.

286
00:13:41,680 --> 00:13:43,910
Du må være ganske
dårlig hvis du faktisk

287
00:13:43,910 --> 00:13:47,310
gjort hele datamaskinen sårbar
etter å skrive 10 eller 20 linjer med kode,

288
00:13:47,310 --> 00:13:49,690
eller i det minste ikke klar over noen
av sikkerhetsrisikoen.

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

290
00:13:52,023 --> 00:13:54,600
og denne uken er det faktisk
virkelig, virkelig lett

291
00:13:54,600 --> 00:13:57,980
å være dårlig, og gjøre selv
korte programmer sårbare.

292
00:13:57,980 --> 00:14:02,880
>> Men for nå, minst, skjønner
at spørsmålet blir stilt her

293
00:14:02,880 --> 00:14:04,850
handler om Clang i en kompilator.

294
00:14:04,850 --> 00:14:08,360
Hvorfor har vi vært tillitsfulle Clang
for de siste to eller tre uker?

295
00:14:08,360 --> 00:14:12,650
Hvem er å si at den som skrev Clang
hadde ikke en "hvis" tilstand der

296
00:14:12,650 --> 00:14:17,680
som i hovedsak injisert noen nuller
og de i hvert program det kompilerer

297
00:14:17,680 --> 00:14:21,180
som ville la ham eller henne tilgang
datamaskinen når du sover

298
00:14:21,180 --> 00:14:23,580
og din laptop lokket er åpent
og datamaskinen kjører?

299
00:14:23,580 --> 00:14:24,080
Høyre?

300
00:14:24,080 --> 00:14:28,350
Vi har denne typen ære system rett
nå hvor vi stoler på at Clang er legit.

301
00:14:28,350 --> 00:14:30,000
Du stoler på at apparatet er legit.

302
00:14:30,000 --> 00:14:34,430
Du stoler som bokstavelig talt hvert program
på din Mac eller PC er troverdig.

303
00:14:34,430 --> 00:14:37,510
Og som denne enkle feil antyder,
selv om det ikke er skadelig,

304
00:14:37,510 --> 00:14:40,580
det er absolutt ikke
sannsynlig å være tilfelle.

305
00:14:40,580 --> 00:14:42,350
>> Så du bør være redd som faen.

306
00:14:42,350 --> 00:14:45,560
Ærlig talt, det er ingen enkel
Løsningen på dette annet

307
00:14:45,560 --> 00:14:48,185
enn en slags samfunnsmessig bevissthet
av den økende kompleksiteten

308
00:14:48,185 --> 00:14:50,310
at vi bygger på toppen
av våre datasystemer,

309
00:14:50,310 --> 00:14:53,740
og hvor stadig mer sårbare
vi kan godt være.

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

311
00:14:55,570 --> 00:14:59,889
Så Breakout er problemet satt tre, og
Breakout er et spill fra en svunnen tid

312
00:14:59,889 --> 00:15:02,180
som du kanskje husker, men
for oss i oppgavesettet tre,

313
00:15:02,180 --> 00:15:04,450
det tillater oss å ta
ting sikkerhetskopiere et hakk

314
00:15:04,450 --> 00:15:08,880
slik at når vi skriver programmer,
selv i et terminalvindu som dette,

315
00:15:08,880 --> 00:15:14,670
vi kan faktisk kjøre, til slutt,
grafiske programmer ikke

316
00:15:14,670 --> 00:15:17,800
i motsetning til de vi hadde
tilgang til i Scratch.

317
00:15:17,800 --> 00:15:20,910
Så dette er de ansattes
gjennomføring av Breakout,

318
00:15:20,910 --> 00:15:23,930
som er nettopp dette murstein-breaking
spillet, som du flytte padle tilbake

319
00:15:23,930 --> 00:15:27,590
og tilbake, og du treffer ballen
mot de fargede klosser opp toppen.

320
00:15:27,590 --> 00:15:30,020
Så dette er å bringe oss
slags tilbake til der

321
00:15:30,020 --> 00:15:33,180
vi var i stand til å være svært raskt
med Scratch, og nå med C,

322
00:15:33,180 --> 00:15:35,800
implementere vår egen
grafiske brukergrensesnitt.

323
00:15:35,800 --> 00:15:38,960
>> Men mer enn det, dette
Oppgavesettet representerer den første

324
00:15:38,960 --> 00:15:41,000
der vi gir
deg en haug med kode.

325
00:15:41,000 --> 00:15:43,940
Og faktisk, jeg ta eksplisitt
hensyn til dette, fordi særlig

326
00:15:43,940 --> 00:15:47,090
for de mindre komfortable, dette
oppgavesettet, i hvert fall ved første øyekast,

327
00:15:47,090 --> 00:15:49,170
kommer til å føle seg som
vi har tatt det opp et hakk.

328
00:15:49,170 --> 00:15:51,540
Fordi vi har gitt deg,
for noen av søke

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

330
00:15:54,930 --> 00:15:56,680
og et par kommentarer
si at "å gjøre"

331
00:15:56,680 --> 00:15:58,221
hvor du må fylle ut feltene.

332
00:15:58,221 --> 00:16:00,020
Så ikke så skummelt, men
det er første gang

333
00:16:00,020 --> 00:16:03,370
vi levere du kode som du trenger for å
først lese, forstå og deretter legge til

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

335
00:16:04,290 --> 00:16:05,940
>> Og deretter med Breakout,
vi kommer til å gjøre det samme,

336
00:16:05,940 --> 00:16:08,740
noe som gir deg et par dusin flere linjer
kode som, ærlig, gi deg

337
00:16:08,740 --> 00:16:11,490
mye av rammeverket for
spillet, men stoppe kort

338
00:16:11,490 --> 00:16:14,304
implementere mursteinene
og ballen og padle,

339
00:16:14,304 --> 00:16:15,970
men vi gjennomføre noen andre funksjoner.

340
00:16:15,970 --> 00:16:18,280
Og selv som ved første øyekast, igjen,
spesielt hvis mindre komfortable,

341
00:16:18,280 --> 00:16:21,480
kan virke særlig skremmende og
du tror det er så mange nye funksjoner

342
00:16:21,480 --> 00:16:24,070
du trenger å vikle hjernen din
rundt, og det er sant.

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

344
00:16:26,281 --> 00:16:28,780
Odds er du ikke brukte alle
Brikkene i Scratch.

345
00:16:28,780 --> 00:16:31,120
Odds er du ikke lyst til å vikle
tankene rundt dem alle

346
00:16:31,120 --> 00:16:33,617
fordi alle tok det var en
raskt blikk for å forstå, oh,

347
00:16:33,617 --> 00:16:35,450
det er hva jeg kan gjøre
med at puslespill brikke.

348
00:16:35,450 --> 00:16:38,260
Og ja, i oppgavesettet
3 spec, vil vi peke deg

349
00:16:38,260 --> 00:16:41,370
på dokumentasjonen som vil
introdusere deg til noen nye funksjoner,

350
00:16:41,370 --> 00:16:43,570
og til slutt programmerings
konstruerer du bruker.

351
00:16:43,570 --> 00:16:47,610
Betingelser, løkker,
variabler og funksjoner

352
00:16:47,610 --> 00:16:50,720
vil være identisk
det vi har sett så langt.

353
00:16:50,720 --> 00:16:53,560
>> Så ja, hva vi vil gi
du er noen eksempelkode som

354
00:16:53,560 --> 00:16:56,110
kan du opprette et vindu
som ser ikke ulikt dette,

355
00:16:56,110 --> 00:16:59,540
og slå den til slutt inn
noe helt som dette.

356
00:16:59,540 --> 00:17:02,250
Så dra nytte av CS50,
diskutere arbeidstid og mer,

357
00:17:02,250 --> 00:17:05,290
og ta trøst i det faktum at
mengden med kode du må skrive

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

359
00:17:06,760 --> 00:17:10,359
Den første utfordringen er bare å akklimatisere
deg selv til noen kode vi har skrevet.

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

361
00:17:11,450 --> 00:17:15,810
>> Eventuelle spørsmål om pset3,
Shellshock, eller på annen måte?

362
00:17:15,810 --> 00:17:19,226
>> PUBLIKUM: Det virket som
gå gjennom med Breakout

363
00:17:19,226 --> 00:17:22,154
at koden er nesten
et objekt-orientert stil,

364
00:17:22,154 --> 00:17:24,675
men jeg trodde C var en
objektorientert program.

365
00:17:24,675 --> 00:17:26,050
SPEAKER 1: Et utmerket spørsmål.

366
00:17:26,050 --> 00:17:28,258
Så i å se gjennom
fordelingskode, koden

367
00:17:28,258 --> 00:17:30,180
vi skrev for pset3,
for de som er kjent, det

368
00:17:30,180 --> 00:17:32,230
ser ut som det er en
lite objekt-orientert.

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

370
00:17:33,800 --> 00:17:38,130
Det er en tilnærming til hvordan du
kan gjøre objektorientert kode ved hjelp

371
00:17:38,130 --> 00:17:41,850
et språk som C, men det er
fortsatt slutt prosessuelle.

372
00:17:41,850 --> 00:17:44,900
Det er ingen metoder inne i
variablene, som du ser.

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

374
00:17:46,180 --> 00:17:48,780
Og vi vil se at funksjonen igjen
når vi kommer til PHP og Javascript

375
00:17:48,780 --> 00:17:49,946
mot slutten av semesteret.

376
00:17:49,946 --> 00:17:53,667
Men for nå, tenk på det som
et hint om hva som kommer.

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

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

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

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

381
00:17:59,730 --> 00:18:03,250
Og flette slags var kult i
forstand at den var så mye raskere,

382
00:18:03,250 --> 00:18:07,100
i det minste på grunnlag av flyktige tester
vi gjorde i forrige uke, enn for eksempel boble

383
00:18:07,100 --> 00:18:08,710
sortere, utvalg sortere, innsetting slag.

384
00:18:08,710 --> 00:18:11,780
Og hva var godt for er bare
hvordan konsist og renslig

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

386
00:18:12,810 --> 00:18:15,840
Og hva gjorde vi si det var en øvre
bundet på kjøretiden til flettingen

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
Yeah?

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, ikke sant. n log n.

392
00:18:20,819 --> 00:18:23,776
Og vi vil komme tilbake til hva som
egentlig betyr eller hvor det kommer fra,

393
00:18:23,776 --> 00:18:25,570
men dette var bedre
enn hva driftstid

394
00:18:25,570 --> 00:18:28,440
som vi så for boble
valg og innsetting slag?

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

396
00:18:30,610 --> 00:18:34,650
og selv om det ikke er helt opplagt,
vet at log n er mindre enn n,

397
00:18:34,650 --> 00:18:36,910
så hvis du gjør n ganger
noe mindre enn n,

398
00:18:36,910 --> 00:18:38,680
det kommer til å være mindre enn n squared.

399
00:18:38,680 --> 00:18:40,130
Det er litt av intuisjon 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 raskere, men et tema som startet
å dukke opp i forrige uke var dette kompromisset.

402
00:18:47,000 --> 00:18:49,804
Jeg fikk bedre ytelse
tid klok, men hva

403
00:18:49,804 --> 00:18:52,470
jeg har å bruke på den andre
hånd, for å oppnå det?

404
00:18:52,470 --> 00:18:53,591
>> PUBLIKUM: Minne.

405
00:18:53,591 --> 00:18:54,465
SPEAKER 1: Si det igjen?

406
00:18:54,465 --> 00:18:55,173
PUBLIKUM: Minne.

407
00:18:55,173 --> 00:18:57,040
SPEAKER 1: Memory, eller
plass mer generelt.

408
00:18:57,040 --> 00:18:59,040
Og det var ikke super
åpenbart med våre mennesker,

409
00:18:59,040 --> 00:19:02,240
men husker at våre frivillige
var stepping frem og stepping

410
00:19:02,240 --> 00:19:04,780
tilbake som om det er en rekke
her, og som om det er

411
00:19:04,780 --> 00:19:07,130
en andre rekke her at
de kunne bruke, fordi vi

412
00:19:07,130 --> 00:19:09,080
trengte et sted å fusjonere de folkene.

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

414
00:19:11,480 --> 00:19:13,800
Så fusjonere slags innflytelse
er mer plass, som

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

416
00:19:15,620 --> 00:19:17,410
men oppsiden er at det er mye raskere.

417
00:19:17,410 --> 00:19:20,780
Og ærlig talt, i den virkelige verden plass
disse days-- RAM, harddisk space--

418
00:19:20,780 --> 00:19:25,030
er forholdsvis billig, og slik at det er
ikke nødvendigvis en dårlig ting.

419
00:19:25,030 --> 00:19:28,320
>> Så la oss ta en rask titt, litt
mer metodisk, på hva vi gjorde

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

421
00:19:30,220 --> 00:19:33,260
Så her er de åtte tall og
åtte frivillige vi hadde forrige gang.

422
00:19:33,260 --> 00:19:35,718
Og det første som Merge
Sorter fortalte oss å gjøre var hva?

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

424
00:19:37,010 --> 00:19:38,010
PUBLIKUM: Divide i to.

425
00:19:38,010 --> 00:19:38,663
SPEAKER 1: Si det igjen?

426
00:19:38,663 --> 00:19:39,650
PUBLIKUM: Divide i to.

427
00:19:39,650 --> 00:19:40,610
SPEAKER 1: Divide i to, ikke sant.

428
00:19:40,610 --> 00:19:42,818
Dette er veldig minner om
telefonboken, av skillet

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

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

431
00:19:45,640 --> 00:19:48,700
Og så når vi sa, liksom
den venstre halvdel av elementene,

432
00:19:48,700 --> 00:19:49,690
hva gjorde vi neste si?

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

434
00:19:51,210 --> 00:19:54,860
Sortere den venstre halvdelen av den venstre
halvparten, som tillater oss å,

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

436
00:19:57,570 --> 00:20:01,280
>> Hvordan du sortere en liste nå, i do
gul, størrelse to, ved hjelp av Merge Sort?

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

438
00:20:02,330 --> 00:20:04,580
Vel dele den i to,
og sortere den venstre halvdelen.

439
00:20:04,580 --> 00:20:07,100
Og dette var der ting
fikk litt dum kort.

440
00:20:07,100 --> 00:20:10,720
Hvordan du sortere til en liste som er av
størrelse en, 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 sortert.

443
00:20:13,210 --> 00:20:14,200
Du er ferdig.

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

445
00:20:17,300 --> 00:20:21,640
Vel, samme, men nå hva som var
tredje og viktig steg i Merge Sort?

446
00:20:21,640 --> 00:20:24,020
Du måtte fusjonere venstre
halvparten, og den høyre halvdel.

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

448
00:20:26,580 --> 00:20:28,750
Vi bestemte oss for all right,
åpenbart to som kommer først,

449
00:20:28,750 --> 00:20:31,840
så vi satte to i sin
sted, etterfulgt av fire.

450
00:20:31,840 --> 00:20:35,010
Og nå må du slags spole tilbake,
og dette er slags karakteristisk

451
00:20:35,010 --> 00:20:37,570
av en algoritme som Merge
Sorter, spole tilbake i minnet.

452
00:20:37,570 --> 00:20:40,240
Hva var neste linje av historien?

453
00:20:40,240 --> 00:20:41,780
Hva bør jeg fokusere på neste?

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

455
00:20:43,110 --> 00:20:47,350
Den høyre halvdel av venstre
halv, som er seks og åtte.

456
00:20:47,350 --> 00:20:50,320
>> Så la meg bare gå gjennom dette
uten belaboring punktet for mye.

457
00:20:50,320 --> 00:20:53,330
Seks og åtte, deretter seks er
sorteres, er åtte sortert.

458
00:20:53,330 --> 00:20:57,190
Flette dem sammen sånn,
og nå det neste store skrittet

459
00:20:57,190 --> 00:21:00,990
er, selvfølgelig, sortere høyre halvdel fra
den aller første trinn i denne algoritmen.

460
00:21:00,990 --> 00:21:02,870
Så vi fokusere på ett, tre, sju, fem.

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

462
00:21:04,540 --> 00:21:09,400
Den venstre halvdel av at den høyre halvdel av
det, og deretter flette i ett og tre.

463
00:21:09,400 --> 00:21:13,100
Deretter høyre halvdel, deretter til venstre halvdel
av den, så den høyre halvdelen av det.

464
00:21:13,100 --> 00:21:15,985
Flette det inn, og nå hva skritt gjenstår?

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

466
00:21:18,040 --> 00:21:22,460
Flett den store venstre halvdel og den store
høyre halvdel, slik at man går ned der,

467
00:21:22,460 --> 00:21:27,330
så to, så tre, så fire, deretter
fem, så seks, så sju, deretter åtte.

468
00:21:27,330 --> 00:21:31,990
>> Så nå hvorfor er dette til slutt avslørende,
spesielt hvis n og logaritmer flere

469
00:21:31,990 --> 00:21:35,487
vanligvis heller unnslippe deg,
i hvert fall i nyere minne?

470
00:21:35,487 --> 00:21:37,070
Vel, merke høyden på denne tingen.

471
00:21:37,070 --> 00:21:41,230
Vi hadde åtte elementer, og vi
deles den ved to, to, to.

472
00:21:41,230 --> 00:21:44,590
Så log base to av åtte gir oss tre.

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

474
00:21:45,640 --> 00:21:48,540
Og tro meg på at hvis
litt tåkete på det.

475
00:21:48,540 --> 00:21:54,710
Men log base to av åtte er tre,
så vi har gjort tre lag med sammenslåing.

476
00:21:54,710 --> 00:21:57,170
Og når vi slått sammen
elementer, hvor mange elementer

477
00:21:57,170 --> 00:21:58,950
fikk vi se på på hver av de radene?

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

479
00:22:00,212 --> 00:22:01,437
Totalt n, rett?

480
00:22:01,437 --> 00:22:04,020
Fordi å fusjonere den øverste raden,
selv om vi gjorde det stykkevis,

481
00:22:04,020 --> 00:22:05,990
vi til slutt rørte hvert tall en gang.

482
00:22:05,990 --> 00:22:09,054
Og i den andre raden, til
flette disse listene av størrelse to,

483
00:22:09,054 --> 00:22:10,470
vi måtte ta på hvert element en gang.

484
00:22:10,470 --> 00:22:12,690
Og så her virkelig
tydelig i den siste raden,

485
00:22:12,690 --> 00:22:15,430
vi måtte ta på hver av disse
elementer samtidig, men bare en gang,

486
00:22:15,430 --> 00:22:18,400
så her ligger altså vår n log n.

487
00:22:18,400 --> 00:22:21,780
>> Og nå bare for å gjøre ting litt
mer formell for bare et øyeblikk, hvis du

488
00:22:21,780 --> 00:22:24,260
skulle nå analysere dette
på en slags høyere nivå

489
00:22:24,260 --> 00:22:28,340
og prøve å bestemme, godt hvordan
kan du gå om å uttrykke

490
00:22:28,340 --> 00:22:31,780
kjøretiden til denne algoritmen
bare ved å se på det, og ikke

491
00:22:31,780 --> 00:22:33,590
ved hjelp av en contrived eksempel?

492
00:22:33,590 --> 00:22:36,590
Vel, hvor mye tid vil du si en
trinn som dette i gult ville ta,

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

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

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

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

497
00:22:41,450 --> 00:22:44,540
Så jeg ser en, så ett trinn,
kanskje to skritt fordi det er hvis

498
00:22:44,540 --> 00:22:47,110
og deretter gå tilbake, men det er
konstant tid, ikke sant?

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

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

501
00:22:51,480 --> 00:22:54,150
n er størrelsen av tilførselen
så T (n), bare en fancy måte

502
00:22:54,150 --> 00:22:56,330
si driften
tid gitt input av størrelse n

503
00:22:56,330 --> 00:23:00,220
kommer til å være i størrelsesorden
av konstant tid, i O (1).

504
00:23:00,220 --> 00:23:01,970
>> Men ellers, hva om dette?

505
00:23:01,970 --> 00:23:05,660
Hvordan vil du uttrykke
kjøretid på denne gule linjen?

506
00:23:05,660 --> 00:23:06,250
T av hva?

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

508
00:23:09,440 --> 00:23:12,665
Du kan slags jukse her og
svare på spørsmålet mitt syklisk.

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

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

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

512
00:23:18,950 --> 00:23:22,490
Og nå er du slags elvebåttur her og
si, vel, bare sortere venstre halvdel,

513
00:23:22,490 --> 00:23:23,920
og deretter sortere høyre halvdel.

514
00:23:23,920 --> 00:23:27,520
Hvordan kan vi symbolsk representerer
kjøretiden til denne gule linjen?

515
00:23:27,520 --> 00:23:28,020
T av hva?

516
00:23:28,020 --> 00:23:29,360
Hva er størrelsen på innspill?

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 si det?

520
00:23:32,140 --> 00:23:36,449
Og da dette er en annen T (n / 2) og deretter
igjen, hvis jeg slå sammen to sorterte halvdeler,

521
00:23:36,449 --> 00:23:38,615
hvor mange elementer skal jeg
å måtte røre totalt?

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 uttrykke dette,
bare for å være snill av fancy,

525
00:23:42,790 --> 00:23:44,430
som kjøretiden generelt.

526
00:23:44,430 --> 00:23:51,140
T (n) er bare kjøretiden T (n / 2),
pluss T (n / 2), venstre halvdel og høyre halvdel,

527
00:23:51,140 --> 00:23:55,360
pluss O (n), som sannsynligvis er n skritt,
men kanskje, hvis jeg bruker to fingre,

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

529
00:23:57,960 --> 00:24:00,440
Det er noen flere skritt
det er en faktor av n,

530
00:24:00,440 --> 00:24:02,270
slik at vi kan uttrykke dette som dette.

531
00:24:02,270 --> 00:24:05,550
Og det er her nå vil vi punt til
baksiden av våre high school math lærebok

532
00:24:05,550 --> 00:24:10,290
vi er at tilbakefall til slutt
ender opp som tilsvarer dette, n ganger log n,

533
00:24:10,290 --> 00:24:12,530
hvis du faktisk gjør ut
regnestykket mer formelt.

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

535
00:24:13,950 --> 00:24:17,500
En tallmessig med en
hardkodet representativt eksempel

536
00:24:17,500 --> 00:24:21,140
ved hjelp av åtte tall, og en mer
generell titt på hvordan vi kom dit.

537
00:24:21,140 --> 00:24:25,670
Men hva er egentlig interessant her
er, igjen, denne oppfatningen av sykling.

538
00:24:25,670 --> 00:24:26,900
Jeg bruker ikke for løkker.

539
00:24:26,900 --> 00:24:29,860
Jeg er litt definere
noe i forhold til seg selv,

540
00:24:29,860 --> 00:24:31,950
ikke bare med denne
matematisk funksjon,

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

542
00:24:34,860 --> 00:24:38,260
Denne pseudo-kode er rekursiv
i at to av sine linjer

543
00:24:38,260 --> 00:24:42,310
er i hovedsak å fortelle det til å gå
bruker i seg selv til å løse en mindre

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

545
00:24:45,400 --> 00:24:48,820
og igjen før vi spikke det
ned til denne såkalte basistilfelle.

546
00:24:48,820 --> 00:24:52,810
>> Så la oss faktisk tegne et mer overbevisende
take-away fra dette som følger.

547
00:24:52,810 --> 00:24:58,420
La meg gå inn i gedit og ta en
se på noen av dagens kildekode,

548
00:24:58,420 --> 00:24:59,930
spesielt dette eksempelet her.

549
00:24:59,930 --> 00:25:03,709
Sigma 0, som tilsynelatende legger
tallene en gjennom n.

550
00:25:03,709 --> 00:25:05,750
Så la oss se hva som er kjent
og ukjent her.

551
00:25:05,750 --> 00:25:08,690
Først har vi et par
inkluderer, så ikke noe nytt der.

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

553
00:25:09,190 --> 00:25:11,370
Jeg er litt disig på
dette etter noen dager,

554
00:25:11,370 --> 00:25:13,790
men hva gjorde vi si en
prototype av en funksjon er?

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

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

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

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

559
00:25:17,800 --> 00:25:18,883
SPEAKER 1: Vi lanserer den.

560
00:25:18,883 --> 00:25:22,290
Så du underviser Clang, hey,
faktisk ikke implementere dette ennå,

561
00:25:22,290 --> 00:25:25,740
men et sted i denne filen, formodentlig,
kommer til å bli en funksjon som heter hva?

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 bare et løfte om at
det kommer til å se slik ut.

565
00:25:30,540 --> 00:25:33,720
Det kommer til å ta et heltall som
input-- og jeg kan være mer eksplisitt

566
00:25:33,720 --> 00:25:36,570
og si int n --og det er
kommer til å returnere en int,

567
00:25:36,570 --> 00:25:39,900
men semikolon midler, mm, jeg skal komme seg rundt
å implementere dette litt senere.

568
00:25:39,900 --> 00:25:40,989
Igjen er Clang dum.

569
00:25:40,989 --> 00:25:43,280
Det er bare kommer til å vite hva
du forteller det topp til bunn,

570
00:25:43,280 --> 00:25:45,765
så vi må i det minste gi
det et hint om hva som kommer.

571
00:25:45,765 --> 00:25:47,330
>> Nå la oss se på hoved her.

572
00:25:47,330 --> 00:25:50,040
La oss bla nedover her og
se hva hoved gjør.

573
00:25:50,040 --> 00:25:53,780
Det er ikke så lenge av en funksjon, og
faktisk konstruere her er kjent.

574
00:25:53,780 --> 00:25:57,590
Jeg erklærer en variabel n, og deretter
Jeg plage brukeren igjen og igjen

575
00:25:57,590 --> 00:26:01,880
for et positivt heltall ved hjelp getInt,
og bare gå ut av denne sløyfen

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

577
00:26:03,280 --> 00:26:05,670
Gjør Mens, har vi brukt til å
plage brukeren på den måten.

578
00:26:05,670 --> 00:26:06,670
Nå er dette interessant.

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

580
00:26:08,510 --> 00:26:11,420
Jeg tilordne den returverdien
av en funksjon som heter "sigma".

581
00:26:11,420 --> 00:26:15,200
Jeg vet ikke hva som gjør ennå, men
Jeg husker erklære det for et øyeblikk siden.

582
00:26:15,200 --> 00:26:18,310
Og så er jeg passerer i
verdi som brukeren har skrevet inn, n,

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

584
00:26:20,420 --> 00:26:22,260
Vel la oss bla tilbake
for bare et øyeblikk.

585
00:26:22,260 --> 00:26:28,620
La oss gå videre inn i denne katalogen, gjør
sigma 0, og faktisk kjøre dette programmet

586
00:26:28,620 --> 00:26:30,490
og se hva som skjer.

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

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

589
00:26:40,139 --> 00:26:43,180
som den greske symbolet tilsier, er bare
kommer til å legge opp alle tallene fra

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

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

592
00:26:46,560 --> 00:26:48,830
Så dette skal forhåpentligvis gi meg tre.

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

594
00:26:49,750 --> 00:26:52,690
Og på samme måte, hvis jeg kjører dette igjen
og jeg gir det nummer tre,

595
00:26:52,690 --> 00:26:56,721
det er tre pluss to, så det er
5, pluss 1 bør gi meg seks.

596
00:26:56,721 --> 00:26:59,470
Og så hvis jeg får virkelig sprø og
begynner å skrive i større tall,

597
00:26:59,470 --> 00:27:01,290
det bør gi meg
større og større summer.

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

599
00:27:02,250 --> 00:27:04,010
>> Så hva gjør sigma se ut?

600
00:27:04,010 --> 00:27:05,430
Vel, det er ganske grei.

601
00:27:05,430 --> 00:27:08,940
Det er hvordan vi kan ha implementert
dette for de siste par ukene.

602
00:27:08,940 --> 00:27:11,120
"Int" kommer til å være returtypen.

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

604
00:27:14,330 --> 00:27:15,940
Jeg skal endre det opp toppen.

605
00:27:15,940 --> 00:27:17,340
Så dette er bare en mental helse sjekk.

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

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

608
00:27:19,950 --> 00:27:24,220
Nå erklærer jeg en annen variabel,
sum, initialisere den til null.

609
00:27:24,220 --> 00:27:28,140
Da har jeg dette For sløyfe
itera, tilsynelatende for klarhet,

610
00:27:28,140 --> 00:27:33,810
fra i = 1 på opp til an = m, som er
hva brukeren har skrevet inn, og da jeg

611
00:27:33,810 --> 00:27:35,690
øke summen som dette.

612
00:27:35,690 --> 00:27:37,360
Og deretter returnere summen.

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

614
00:27:38,440 --> 00:27:42,370
En, jeg hevder i min kommentar at dette
unngår faren for en uendelig løkke.

615
00:27:42,370 --> 00:27:45,620
Hvorfor skulle passerer i et negativt tall
indusere, potensielt, 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 aldri nå moh.

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

619
00:27:52,880 --> 00:27:55,880
Men m er gått inn, så la oss
vurdere et enkelt eksempel.

620
00:27:55,880 --> 00:27:58,510
Hvis m er gått i ved
bruker som negativt.

621
00:27:58,510 --> 00:28:00,059
Uavhengig av hoved.

622
00:28:00,059 --> 00:28:01,850
Hoved beskytter oss mot
dette også, så jeg er bare

623
00:28:01,850 --> 00:28:04,680
blir virkelig anal med
sigma å også sørge for

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

625
00:28:06,540 --> 00:28:10,130
Så hvis m er negativ,
noe sånt som negativ en.

626
00:28:10,130 --> 00:28:11,930
Hva kommer til å skje?

627
00:28:11,930 --> 00:28:14,390
Vel, jeg kommer til å
blir initialisert til en,

628
00:28:14,390 --> 00:28:19,060
og da er jeg kommer til å være
mindre enn eller lik m?

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

630
00:28:24,130 --> 00:28:24,765
>> Stand by.

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

632
00:28:26,930 --> 00:28:29,370
Det var-- la oss ikke,
la oss nix denne historien.

633
00:28:29,370 --> 00:28:32,780
Jeg fikk ikke stille det spørsmålet, fordi
risikoen for at jeg berget

634
00:28:32,780 --> 00:28:38,360
ikke kommer til å skje fordi jeg er
alltid kommer være større than-- OK,

635
00:28:38,360 --> 00:28:39,871
Jeg trekker det spørsmålet.

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

637
00:28:40,370 --> 00:28:42,030
La oss fokusere bare på denne delen her.

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

639
00:28:44,210 --> 00:28:48,830
Hvorfor gjorde jeg erklære noen
utenfor loopen?

640
00:28:48,830 --> 00:28:52,010
Notice on line 49 Jeg har
erklært i innsiden av løkken,

641
00:28:52,010 --> 00:28:54,950
men online 48 jeg har
erklærte noen utenfor.

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

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

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

645
00:28:58,734 --> 00:28:59,400
SPEAKER 1: Sure.

646
00:28:59,400 --> 00:29:03,360
Så først og fremst jeg absolutt ikke
ønsker å erklære og initial sum

647
00:29:03,360 --> 00:29:06,130
til null innvendig
sløyfe på hver iterasjon,

648
00:29:06,130 --> 00:29:09,370
fordi dette ville klart beseire den
Hensikten med å summere opp tallene.

649
00:29:09,370 --> 00:29:11,770
Jeg ville holde endre
verdien tilbake til null.

650
00:29:11,770 --> 00:29:17,992
Og også, hva er en annen mer uforståelige
Grunnen til at samme design avgjørelse?

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

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

653
00:29:20,279 --> 00:29:21,070
SPEAKER 1: Nettopp.

654
00:29:21,070 --> 00:29:24,060
Jeg ønsker å få tilgang til det utenfor
av sløyfen altfor på hvilken linje?

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

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

657
00:29:26,400 --> 00:29:29,910
Og basert på vår tommelfingerregel
fra et par forelesninger siden,

658
00:29:29,910 --> 00:29:33,680
variabler er scoped, egentlig, til
klammeparentes som omfatter dem.

659
00:29:33,680 --> 00:29:38,190
Så hvis jeg ikke erklære sum inne
av disse ytre klammeparentes,

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

661
00:29:40,250 --> 00:29:43,160
Sagt på en annen måte, hvis jeg erklærte
sum i her, eller selv innenfor

662
00:29:43,160 --> 00:29:45,410
For loop, jeg kunne ikke tilgang til den i 53.

663
00:29:45,410 --> 00:29:47,150
Den variable ville effektivt være borte.

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

665
00:29:48,579 --> 00:29:50,370
Men nå la oss gå tilbake
og se hva som skjer.

666
00:29:50,370 --> 00:29:51,730
Så sigma blir kalt.

667
00:29:51,730 --> 00:29:55,640
Den legger opp 1 pluss 2, eller 1 pluss 2
pluss 3, og deretter returnerer verdien,

668
00:29:55,640 --> 00:29:59,660
lagrer det i svaret, og printf her
er grunnen til at jeg ser på skjermen.

669
00:29:59,660 --> 00:30:03,079
Så dette er hva vi kaller en iterativ
tilnærming, hvor iterasjon bare

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

671
00:30:03,870 --> 00:30:06,900
En for løkke, en while-loop, en gjøre mens
loop, bare gjør noe nytt

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

673
00:30:08,380 --> 00:30:13,505
>> Men sigma er slag av en ryddig funksjon i
at jeg kunne gjennomføre det annerledes.

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

675
00:30:14,620 --> 00:30:19,120
Hva om dette, noe som
bare for å være litt kult,

676
00:30:19,120 --> 00:30:21,880
la meg virkelig bli kvitt
av mye distraksjon

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

678
00:30:24,380 --> 00:30:27,780
La oss spikke det ned bare
til sine fire kjernelinjer

679
00:30:27,780 --> 00:30:30,410
og bli kvitt all den
kommentarer og klammeparentes.

680
00:30:30,410 --> 00:30:34,334
Dette er en slags halsbrekk
alternativ implementering.

681
00:30:34,334 --> 00:30:37,250
Ok, kanskje ikke tanke blåser,
men det er slags sexy, all right,

682
00:30:37,250 --> 00:30:39,920
å se på dette så mye mer konsist.

683
00:30:39,920 --> 00:30:43,120
Med bare fire linjer med kode,
Jeg først har denne tilregnelighet sjekk.

684
00:30:43,120 --> 00:30:45,732
Hvis m er mindre enn eller lik
null, gjør sigma ingen mening.

685
00:30:45,732 --> 00:30:48,190
Det er bare ment å være i
dette tilfellet for positive tall,

686
00:30:48,190 --> 00:30:50,340
så jeg skal bare
returnere null vilkårlig

687
00:30:50,340 --> 00:30:53,210
slik at vi i det minste har
noen såkalte basistilfelle.

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

689
00:30:54,430 --> 00:30:59,930
Helheten av denne ideen, og legger til
tall fra 1 til n, og m i dette tilfellet

690
00:30:59,930 --> 00:31:02,630
kan gjøres ved slags passerer the buck.

691
00:31:02,630 --> 00:31:04,947
Vel, hva er summen av 1 til m?

692
00:31:04,947 --> 00:31:05,780
Vel, vet du hva?

693
00:31:05,780 --> 00:31:11,949
Det er det samme som summen av m
pluss summen av 1 og m minus en.

694
00:31:11,949 --> 00:31:12,740
Vel vet du hva?

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

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

697
00:31:17,860 --> 00:31:21,415
pluss sigma av 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 just--
dette er som, hvis du er bare

700
00:31:26,012 --> 00:31:28,220
prøver å irritere en venn
og de spør deg et spørsmål,

701
00:31:28,220 --> 00:31:31,344
du slags svare med et spørsmål,
du kan slags holde passerer the buck.

702
00:31:31,344 --> 00:31:34,560
Men kjernen er at hvis du holder
gjør spørsmålet mindre og mindre

703
00:31:34,560 --> 00:31:36,910
og mindre, er du
ikke spør hva som er sigma

704
00:31:36,910 --> 00:31:39,116
n, hva er sigma av
n, hva er sigma av n?

705
00:31:39,116 --> 00:31:40,990
Du spør hva som er
sigma n, hva er sigma

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

707
00:31:42,839 --> 00:31:44,880
Til slutt spørsmålet ditt
kommer til å bli det?

708
00:31:44,880 --> 00:31:50,250
Hva er sigma av en eller
null, noen svært liten verdi,

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

710
00:31:52,220 --> 00:31:54,350
du kommer ikke til å spørre
det samme spørsmålet igjen,

711
00:31:54,350 --> 00:31:55,975
du bare kommer til å si, oh det er null.

712
00:31:55,975 --> 00:31:58,490
Vi er ferdig med å spille denne typen
dum syklisk spill.

713
00:31:58,490 --> 00:32:02,950
>> Så rekursjon er handlingen i programmering
av en funksjon som kaller seg.

714
00:32:02,950 --> 00:32:06,630
Dette programmet, når kompilert og kjøre, er
kommer til å oppføre seg på akkurat samme måte,

715
00:32:06,630 --> 00:32:09,620
men hva er nøkkelen er at innsiden
av en funksjon som heter sigma,

716
00:32:09,620 --> 00:32:13,150
er det en kodelinje hvori
vi kaller oss selv,

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

718
00:32:14,980 --> 00:32:21,160
For eksempel, hva hvis jeg først
utarbeidet denne, så sørg sigma--

719
00:32:21,160 --> 00:32:22,710
gjøre sigma 1 ./sigma-1.

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

721
00:32:25,050 --> 00:32:27,690
Positivt heltall, vær så snill, 50 1275.

722
00:32:27,690 --> 00:32:30,810
Så hva funksjonen ser ut til å
være basert på en test, korrekt.

723
00:32:30,810 --> 00:32:34,917
Men hva hvis jeg får en litt farlig
og slette den såkalte base case,

724
00:32:34,917 --> 00:32:37,750
og bare si, vel jeg bare å lage
denne mer komplisert enn det er.

725
00:32:37,750 --> 00:32:42,450
La oss bare beregne sigma
ved å ta m, og deretter tilsetning

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

727
00:32:44,564 --> 00:32:45,980
Vel, hva kommer til å skje her?

728
00:32:45,980 --> 00:32:47,140
La oss zoome ut.

729
00:32:47,140 --> 00:32:52,920
La oss rekompilere programmet,
lagre det, rekompilere programmet,

730
00:32:52,920 --> 00:33:00,450
og deretter klar ./sigma-en zoomer inn,
skriv positivt heltall please, 50.

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

732
00:33:02,180 --> 00:33:04,430
Hvor mange av dere er villig
å fess opp til å se det?

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

734
00:33:04,950 --> 00:33:06,690
Så dette kan skje for
en rekke grunner,

735
00:33:06,690 --> 00:33:09,148
og ærlig denne uken vi er
i ferd med å gi deg mer av dem.

736
00:33:09,148 --> 00:33:11,780
Men i dette tilfellet, kan du prøve
å resonnere bakover

737
00:33:11,780 --> 00:33:14,430
hva kan ha skjedd her?

738
00:33:14,430 --> 00:33:17,400
Segmentering feil, sist vi sa
tid, henviser til et segment av minnet.

739
00:33:17,400 --> 00:33:18,690
Noe dårlig skjedde.

740
00:33:18,690 --> 00:33:21,550
Men hva var det
mekanisk som gikk galt

741
00:33:21,550 --> 00:33:25,000
her på grunn av fjerning min
av det såkalte basis tilfellet

742
00:33:25,000 --> 00:33:26,870
der jeg returnerte hardkodet verdi?

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

744
00:33:28,970 --> 00:33:30,460
Hva tror du gikk galt?

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

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

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ørsmål.

750
00:33:37,550 --> 00:33:39,508
Så størrelsen av antallet
at jeg var summere opp

751
00:33:39,508 --> 00:33:41,920
ble så stor at det overgikk
størrelsen på plass i minnet.

752
00:33:41,920 --> 00:33:44,640
God idé, men ikke fundamentalt
kommer til å føre til krasj.

753
00:33:44,640 --> 00:33:48,230
Som kan føre til heltall overløp,
hvor de biter bare snu

754
00:33:48,230 --> 00:33:51,760
og da vi feil en virkelig stor
nummer for som et negativt tall,

755
00:33:51,760 --> 00:33:53,260
men det i seg selv vil ikke føre til krasj.

756
00:33:53,260 --> 00:33:55,509
Fordi på slutten av
dag en int er fortsatt 32 bits.

757
00:33:55,509 --> 00:33:57,640
Du kommer ikke til å
uhell stjele 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
Yeah.

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

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

762
00:34:00,551 --> 00:34:02,300
SPEAKER 1: Metoden
aldri slutter å kjøre,

763
00:34:02,300 --> 00:34:06,658
og faktisk det kaller seg igjen
og igjen og igjen og igjen

764
00:34:06,658 --> 00:34:08,449
og igjen, og ingen av
disse funksjonene noensinne

765
00:34:08,449 --> 00:34:13,310
føre fordi deres eneste linje av
kode kaller seg selv igjen og igjen

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

767
00:34:14,219 --> 00:34:16,080
Og hva er egentlig
skjer her, og nå er vi

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

769
00:34:18,100 --> 00:34:20,899
La meg gå over til en
bilde for bare et øyeblikk.

770
00:34:20,899 --> 00:34:22,940
Dette er et bilde, som
vil til slutt kjøttet ut

771
00:34:22,940 --> 00:34:26,336
i mer detalj, av hva som skjer
innsiden av datamaskinens minne.

772
00:34:26,336 --> 00:34:28,460
Og det viser seg at på
bunnen av dette bildet

773
00:34:28,460 --> 00:34:29,709
er noe som kalles stabelen.

774
00:34:29,709 --> 00:34:31,920
Dette er en del av
minne, en mengde RAM,

775
00:34:31,920 --> 00:34:33,920
det er bare brukt noen gang
en funksjon kalles.

776
00:34:33,920 --> 00:34:36,239
Hver gang du, en programmerer,
kalle en funksjon,

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

778
00:34:38,860 --> 00:34:41,920
griper en haug av bytes, kanskje en
kilobyte, kanskje noen få megabyte

779
00:34:41,920 --> 00:34:44,590
minne, hendene dem
til deg, og deretter lar

780
00:34:44,590 --> 00:34:47,650
du kjører din funksjon ved hjelp
Uansett variablene du trenger.

781
00:34:47,650 --> 00:34:50,699
Og hvis du da ringe en annen
funksjon og en annen funksjon,

782
00:34:50,699 --> 00:34:53,590
du får en annen bit av minne
og en annen bit av minne.

783
00:34:53,590 --> 00:34:57,090
>> Og ja, hvis disse grønne skuffer
fra Annenberg representerer dette minnet,

784
00:34:57,090 --> 00:34:59,870
her er hva som skjer den første
gang du ringer funksjon sigma.

785
00:34:59,870 --> 00:35:04,510
Det er som å sette et brett som dette
på hva som er utgangspunktet en tom stabelen.

786
00:35:04,510 --> 00:35:07,142
Men så hvis den skuffen
kaller seg, så å si,

787
00:35:07,142 --> 00:35:08,850
ringer en annen forekomst
av sigma, det er

788
00:35:08,850 --> 00:35:11,640
som å spørre operativsystemet,
ooh, trenger litt mer minne,

789
00:35:11,640 --> 00:35:12,520
gi meg den.

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

791
00:35:14,840 --> 00:35:18,030
Men det som er nøkkelen her er at
den første skuffen er der fortsatt,

792
00:35:18,030 --> 00:35:20,620
fordi han har påberopt seg denne annen skuff.

793
00:35:20,620 --> 00:35:23,500
Nå i mellomtiden, sigma kaller sigma,
det er som å be om mer minne.

794
00:35:23,500 --> 00:35:25,830
Blir stablet på over her.

795
00:35:25,830 --> 00:35:29,350
sigma kaller sigma, det er en annen
skuffen som blir stablet på her.

796
00:35:29,350 --> 00:35:32,942
Og hvis du fortsetter å gjøre dette,
til slutt, hva slags kart denne visuelle

797
00:35:32,942 --> 00:35:35,525
på det kartet, hva som kommer til
skje med bunken med skuffer?

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

799
00:35:37,480 --> 00:35:41,160
Det kommer til å overstige beløpet
minne maskinen har.

800
00:35:41,160 --> 00:35:45,790
Og så snart denne grønne skuffen
overskrider den horisontale linje

801
00:35:45,790 --> 00:35:49,410
ovenfor stack og over at ordet haugen,
som vi vil komme tilbake 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
Haugen er en annen
segment av minne,

804
00:35:52,810 --> 00:35:55,190
og hvis du lar disse
skuffer haug og haug på,

805
00:35:55,190 --> 00:35:57,800
du kommer til å overstige
ditt eget segment av minne,

806
00:35:57,800 --> 00:36:00,420
og et program er faktisk kommer til å krasje.

807
00:36:00,420 --> 00:36:02,930
>> Nå som en side, denne ideen
av rekursjon derfor

808
00:36:02,930 --> 00:36:06,500
tydelig kan føre til problemer, men
det er ikke nødvendigvis en dårlig ting.

809
00:36:06,500 --> 00:36:08,840
Fordi vurdere, etter
alt, how-- og kanskje

810
00:36:08,840 --> 00:36:11,700
dette tar litt tid å venne
å --how elegant eller hvor enkelt

811
00:36:11,700 --> 00:36:14,890
at gjennomføringen av sigma var.

812
00:36:14,890 --> 00:36:17,440
Og vi kommer til å bruke
rekursjon så mye i CS50,

813
00:36:17,440 --> 00:36:20,780
men i CS51, og virkelig noen klasse
hvor du manipulere datastrukturer

814
00:36:20,780 --> 00:36:23,640
som trær, eller familietrær,
som har noen hierarki,

815
00:36:23,640 --> 00:36:26,000
det er super, super nyttig.

816
00:36:26,000 --> 00:36:29,750
Nå, som en side, slik at du
som aspirerende dataforskere

817
00:36:29,750 --> 00:36:33,180
er kjent med noen av Googles
inne vitser, hvis du går til Google

818
00:36:33,180 --> 00:36:36,345
og du ser opp hva som er
definisjon av, si, rekursjon, inn.

819
00:36:36,345 --> 00:36:40,208

820
00:36:40,208 --> 00:36:41,110
Uh-he.

821
00:36:41,110 --> 00:36:42,670
Som en side, trakk jeg opp noen.

822
00:36:42,670 --> 00:36:45,470
Dette var som 10 minutter av
sommel i morges.

823
00:36:45,470 --> 00:36:52,890
Hvis du også Google "skjevt", varsel
ved å vippe hodet slightly--

824
00:36:52,890 --> 00:36:55,120
og så dette er kanskje
mest fryktelig av alt

825
00:36:55,120 --> 00:36:57,286
siden noen brukt som
sin dag å implementere denne

826
00:36:57,286 --> 00:36:59,880
noen år ago-- kommer på.

827
00:36:59,880 --> 00:37:01,140

828
00:37:01,140 --> 00:37:04,540
Oh, det er wait-- en bug.

829
00:37:04,540 --> 00:37:08,410

830
00:37:08,410 --> 00:37:11,410
>> Så kjøres på en av
verdens største nettsteder

831
00:37:11,410 --> 00:37:13,510
er disse dumme små påskeegg.

832
00:37:13,510 --> 00:37:16,690
De sannsynligvis forbruke
nontrivial antall linjer med kode

833
00:37:16,690 --> 00:37:19,280
akkurat slik at vi kan ha
små morsomme ting som det.

834
00:37:19,280 --> 00:37:22,140
Men minst nå får du
noen av disse inne vitser.

835
00:37:22,140 --> 00:37:28,330
>> Nå la oss ta en titt på noen av de
hvite løgner vi har vært å fortelle i det siste,

836
00:37:28,330 --> 00:37:30,707
og begynner å skrelle tilbake
noen lag teknisk

837
00:37:30,707 --> 00:37:32,790
slik at du virkelig forstår
hva som har skjedd på

838
00:37:32,790 --> 00:37:34,860
og du kan forstå
noen av truslene,

839
00:37:34,860 --> 00:37:38,060
som Shellshock, som
har nå begynt å bli

840
00:37:38,060 --> 00:37:41,110
på i forkant av alles
oppmerksomhet, i det minste i mediet.

841
00:37:41,110 --> 00:37:45,810
Så her er en veldig enkel funksjon
som returnerer ingenting, ugyldig.

842
00:37:45,810 --> 00:37:46,790
Dens navn er swap.

843
00:37:46,790 --> 00:37:50,880
Det tar i to variabler
og den returnerer ingenting.

844
00:37:50,880 --> 00:37:52,260
Tar i a og b.

845
00:37:52,260 --> 00:37:53,337
Så en rask demonstrasjon.

846
00:37:53,337 --> 00:37:54,170
Vi tok opp disse.

847
00:37:54,170 --> 00:37:56,100
Vi kan like godt ta litt
pause her for bare et øyeblikk

848
00:37:56,100 --> 00:37:57,250
og har noe å drikke.

849
00:37:57,250 --> 00:38:00,120
Hvis noen ikke vil ha noe imot å bli med
meg opp her for bare et øyeblikk.

850
00:38:00,120 --> 00:38:01,830
Hva med deg i rødbrun skjorte?

851
00:38:01,830 --> 00:38:02,335
Kom opp.

852
00:38:02,335 --> 00:38:04,060

853
00:38:04,060 --> 00:38:05,260
Bare én dag.

854
00:38:05,260 --> 00:38:06,251
Takk, skjønt.

855
00:38:06,251 --> 00:38:08,000
Greit, og vi har
kommer opp hvem her?

856
00:38:08,000 --> 00:38:08,660
Hva heter du?

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 opp.

860
00:38:10,370 --> 00:38:11,460

861
00:38:11,460 --> 00:38:13,850
Så Laura, veldig enkel utfordring i dag.

862
00:38:13,850 --> 00:38:14,704

863
00:38:14,704 --> 00:38:15,370
Hyggelig å møte yo.

864
00:38:15,370 --> 00:38:16,410

865
00:38:16,410 --> 00:38:16,910
Greit.

866
00:38:16,910 --> 00:38:21,179
Så vi har litt melk over her og
vi har litt appelsinjuice over her

867
00:38:21,179 --> 00:38:23,345
og noen kopper som vi
lånt fra Annenberg i dag.

868
00:38:23,345 --> 00:38:24,178
>> SPEAKER 4: Borrowed.

869
00:38:24,178 --> 00:38:27,240
SPEAKER 1: Og kommer til å gå videre
og gi deg et halvt glass av denne.

870
00:38:27,240 --> 00:38:28,250

871
00:38:28,250 --> 00:38:28,800
Greit.

872
00:38:28,800 --> 00:38:30,750
Og vi vil gi deg halv
et glass melk.

873
00:38:30,750 --> 00:38:31,905

874
00:38:31,905 --> 00:38:35,890
Oh, og bare slik at du kan
huske hva dette var,

875
00:38:35,890 --> 00:38:38,860
Jeg husket å bringe
dette opp og på i dag.

876
00:38:38,860 --> 00:38:42,030

877
00:38:42,030 --> 00:38:42,530
Ok.

878
00:38:42,530 --> 00:38:45,470
Hvis du ikke har noe imot det, la oss se, vi
kan sette 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 blir verden fra Lauras øyne.

881
00:38:48,710 --> 00:38:49,210
Greit.

882
00:38:49,210 --> 00:38:53,820
Så målet ditt, gitt to kopper
flytende her, melk og appelsinjuice,

883
00:38:53,820 --> 00:38:58,370
er bytte de to innholdet slik at
appelsinjuice går inn i melkekoppen

884
00:38:58,370 --> 00:39:00,710
og melken går over i
appelsinjuice cup.

885
00:39:00,710 --> 00:39:02,359
>> SPEAKER 4: Må jeg få en annen cup?

886
00:39:02,359 --> 00:39:05,650
SPEAKER 1: Jeg er så glad for at du spurte, men
det ville ha vært mye bedre opptak

887
00:39:05,650 --> 00:39:06,710
hvis du ikke hadde spurt.

888
00:39:06,710 --> 00:39:10,620
Men ja, kan vi tilby deg en tredje
kopp som er tom, selvfølgelig.

889
00:39:10,620 --> 00:39:11,120
Greit.

890
00:39:11,120 --> 00:39:12,300
Så bytte ut innholdet 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
Veldig bra.

895
00:39:21,305 --> 00:39:23,121

896
00:39:23,121 --> 00:39:24,745
Du gjør dette bemerkelsesverdig nøye.

897
00:39:24,745 --> 00:39:26,970

898
00:39:26,970 --> 00:39:28,655
Og trinn tre.

899
00:39:28,655 --> 00:39:30,390

900
00:39:30,390 --> 00:39:31,350
Greit.

901
00:39:31,350 --> 00:39:31,930
Utmerket.

902
00:39:31,930 --> 00:39:33,930
En stor applaus
ville være bra for Laura.

903
00:39:33,930 --> 00:39:36,500

904
00:39:36,500 --> 00:39:37,000
Greit.

905
00:39:37,000 --> 00:39:40,790
Vi har en liten avskjedsgave
for deg, men la meg ta disse.

906
00:39:40,790 --> 00:39:42,620
Takk så mye.

907
00:39:42,620 --> 00:39:46,170
Så et enkelt eksempel, skjønt,
å vise at hvis du gjør

908
00:39:46,170 --> 00:39:48,300
ønsker å bytte ut innholdet
av to beholdere,

909
00:39:48,300 --> 00:39:52,360
eller la oss kalle dem variabler,
du trenger noen midlertidig lagring

910
00:39:52,360 --> 00:39:56,710
å arrangere et av innholdet i så
at du faktisk kan gjøre swap.

911
00:39:56,710 --> 00:40:01,790
Så ja, denne kildekoden her oppe i
C er representativ for akkurat det.

912
00:40:01,790 --> 00:40:06,340
Hvis appelsinjuice var en og melken
var b, og vi ønsket å bytte de to,

913
00:40:06,340 --> 00:40:08,990
du kan prøve noe kreativt
ved å helle en til den andre,

914
00:40:08,990 --> 00:40:11,031
men som sannsynligvis ikke ville
ende spesielt godt.

915
00:40:11,031 --> 00:40:15,260
Og så bruker vi en tredje kopp, samtale
det tmp, T-M-P av konvensjonen,

916
00:40:15,260 --> 00:40:19,370
og sette innholdet i
OJ i det, så bytte en kopp,

917
00:40:19,370 --> 00:40:22,610
deretter sette OJ inn i
opprinnelige cup, og dermed

918
00:40:22,610 --> 00:40:25,320
oppnå, akkurat som
Laura gjorde, swap.

919
00:40:25,320 --> 00:40:26,850
>> Så la oss gjøre akkurat det.

920
00:40:26,850 --> 00:40:30,110
La meg gå videre og åpne
opp et eksempel som er

921
00:40:30,110 --> 00:40:32,720
faktisk kalt "no
bytte ", fordi dette ikke er

922
00:40:32,720 --> 00:40:36,180
som rett og slett gjort som du kanskje tror.

923
00:40:36,180 --> 00:40:41,190
Så i dette programmet, legge merke til at
Jeg bruker stdio.h, vår gamle venn.

924
00:40:41,190 --> 00:40:43,130
Jeg har prototypen
for swap opp der, som

925
00:40:43,130 --> 00:40:45,450
betyr gjennomføringen er
trolig ned nedenfor,

926
00:40:45,450 --> 00:40:48,050
og la oss se hva denne hoved
Programmet kommer til å gjøre for meg.

927
00:40:48,050 --> 00:40:52,020
Jeg først erklære int x blir
en, og int y får to.

928
00:40:52,020 --> 00:40:54,930
Så tenker på dem som OJ
og melk, henholdsvis.

929
00:40:54,930 --> 00:40:57,100
Og da jeg bare har en
printf si x er dette

930
00:40:57,100 --> 00:41:00,120
og y er dette, så jeg kan
visuelt se hva som skjer.

931
00:41:00,120 --> 00:41:03,810
Så jeg har printf hevde
at jeg bytte de to,

932
00:41:03,810 --> 00:41:07,100
og da jeg skrive ut en
hevder at de er byttet,

933
00:41:07,100 --> 00:41:09,300
og jeg skrive ut x og y igjen.

934
00:41:09,300 --> 00:41:13,010
Så her nede i swap er
nøyaktig hva Laura gjorde,

935
00:41:13,010 --> 00:41:16,240
og akkurat det vi så på
skjermen et øyeblikk siden.

936
00:41:16,240 --> 00:41:19,380
>> Så la oss gå videre og
bli dypt skuffet.

937
00:41:19,380 --> 00:41:24,690
Gjør ingen swap, og kjøre uten swap,
zoomer inn på produksjonen her.

938
00:41:24,690 --> 00:41:28,320
Skriv inn x er 1, y er 2, bytte byttet.

939
00:41:28,320 --> 00:41:32,700
x er fortsatt 1, og y er fremdeles 2.

940
00:41:32,700 --> 00:41:37,630
Så selv om, ærlig, dette ser
nøyaktig like, om enn mer teknisk,

941
00:41:37,630 --> 00:41:40,730
hva Laura gjorde, ikke synes å fungere.

942
00:41:40,730 --> 00:41:42,130
Så hvorfor er det?

943
00:41:42,130 --> 00:41:46,630
Vel, det viser seg at når
vi skrive et program som dette

944
00:41:46,630 --> 00:41:51,590
som har både hoved, uthevet her,
og deretter en annen funksjon, som swap,

945
00:41:51,590 --> 00:41:54,230
uthevet her, som
det kaller, verden

946
00:41:54,230 --> 00:41:57,030
ser litt noe sånt
Disse skuffene et øyeblikk siden.

947
00:41:57,030 --> 00:42:00,440
Når hoved først blir kalt,
det er som å spørre operativsystem

948
00:42:00,440 --> 00:42:04,030
for litt minne for eventuelle lokale
variabler som x og y som har hoved,

949
00:42:04,030 --> 00:42:05,660
og de ender opp akkurat der.

950
00:42:05,660 --> 00:42:10,920
Men hvis hoved samtaler bytte, og hoved
går å bytte to argumenter, a og b,

951
00:42:10,920 --> 00:42:16,410
appelsinjuice og melk, er det ikke som
late appelsinjuice og melk

952
00:42:16,410 --> 00:42:17,500
til Laura.

953
00:42:17,500 --> 00:42:21,300
For en datamaskin gjør, er det
passerer kopier av appelsinjuice

954
00:42:21,300 --> 00:42:27,110
og kopier av melk til Laura, slik at
hva som er i siste instans innsiden av denne skuffen

955
00:42:27,110 --> 00:42:32,510
er verdien en og to, eller OJ
og melk, men kopier av disse,

956
00:42:32,510 --> 00:42:34,790
slik at på dette punktet
i historien, det

957
00:42:34,790 --> 00:42:36,930
er OJ og melk i hver av disse skuffene.

958
00:42:36,930 --> 00:42:39,260
Det er en en og en to
i hver av disse skuffene,

959
00:42:39,260 --> 00:42:41,720
og swap-funksjonen faktisk fungerer.

960
00:42:41,720 --> 00:42:46,090
Det er å bytte dem inne
av den nest øverste skuffen,

961
00:42:46,090 --> 00:42:48,147
men at swapping har ingen innvirkning.

962
00:42:48,147 --> 00:42:49,980
Og basert på bare noen
grunnleggende prinsipp vi har

963
00:42:49,980 --> 00:42:52,970
snakket om før, og faktisk
bare noen få minutter siden, hva

964
00:42:52,970 --> 00:42:58,770
kan forklare hvorfor endring
a og b innsiden av swap

965
00:42:58,770 --> 00:43:05,560
har ingen effekt på x og y, selv om
Jeg passerte x og y til swap-funksjonen.

966
00:43:05,560 --> 00:43:08,750
Hva er stikkordet her at
kanskje éntrådet 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: Return.

970
00:43:13,335 --> 00:43:14,085
SPEAKER 1: Gå tilbake?

971
00:43:14,085 --> 00:43:14,590
Ikke tilbake.

972
00:43:14,590 --> 00:43:15,895
La oss gå med en annen.

973
00:43:15,895 --> 00:43:16,395
Hva er det?

974
00:43:16,395 --> 00:43:17,080
>> PUBLIKUM: [uhørlig].

975
00:43:17,080 --> 00:43:20,000
>> SPEAKER 1: OK, så return-- vi kunne
gjøre retur arbeid i historien,

976
00:43:20,000 --> 00:43:21,914
men det er en enda 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 tar omfang.

980
00:43:24,300 --> 00:43:27,290
Så omfanget, huske hvor
vår x og y deklarert.

981
00:43:27,290 --> 00:43:30,840
De er erklært inne
av hoved rett opp her.

982
00:43:30,840 --> 00:43:33,200
a og b, i mellomtiden, er
effektivt erklærte

983
00:43:33,200 --> 00:43:35,930
innsiden av swap, ikke helt i
klammeparentes, men likevel

984
00:43:35,930 --> 00:43:37,690
i det generelle området av swap.

985
00:43:37,690 --> 00:43:40,560
Og så ja, a og b
bare eksisterer innenfor denne skuffen

986
00:43:40,560 --> 00:43:44,850
fra Annenberg, dette
andre del av kode.

987
00:43:44,850 --> 00:43:49,500
Så vi faktisk endre kopien, men
det er egentlig ikke alle som nyttig.

988
00:43:49,500 --> 00:43:52,190
>> Så la oss ta en titt på
dette litt lavere nivå.

989
00:43:52,190 --> 00:43:55,430
Jeg kommer til å gå tilbake til
Source Directory,

990
00:43:55,430 --> 00:43:58,330
og jeg kommer til å først
zoome inn her, og bare

991
00:43:58,330 --> 00:44:02,290
for å bekrefte at jeg er i dette
større terminalvindu,

992
00:44:02,290 --> 00:44:04,430
Programmets fortsatt oppfører seg som det.

993
00:44:04,430 --> 00:44:06,840
Anta nå at dette
er ikke tilsiktet.

994
00:44:06,840 --> 00:44:10,090
Klart jeg ville bytte til
arbeid, så det føles som en bug.

995
00:44:10,090 --> 00:44:12,780
Nå kunne jeg begynne å legge en
Mange printf-tallet til min kode,

996
00:44:12,780 --> 00:44:16,010
skrive ut x over her, y løpet
her, en over her, b over her.

997
00:44:16,010 --> 00:44:18,220
Men ærlig talt, det er nok det
du har gjort for et par uker

998
00:44:18,220 --> 00:44:20,190
nå, i kontortiden
og hjemme når du arbeider

999
00:44:20,190 --> 00:44:22,150
på psets prøver å finne noen bugs.

1000
00:44:22,150 --> 00:44:25,560
Men du vil se, hvis du ikke allerede har,
det problemet satt tre introduserer deg

1001
00:44:25,560 --> 00:44:31,630
til en kommando som heter GDB,
hvor GDB, GNU debugger,

1002
00:44:31,630 --> 00:44:34,040
har selv en hel haug med
funksjoner som faktisk kan

1003
00:44:34,040 --> 00:44:38,160
la oss forstå situasjoner
som dette, men mer overbevisende,

1004
00:44:38,160 --> 00:44:39,940
løse problemer og finne bugs.

1005
00:44:39,940 --> 00:44:40,940
Så jeg kommer til å gjøre dette.

1006
00:44:40,940 --> 00:44:44,770
I stedet for ./noswap, jeg er i stedet
kommer til å kjøre GDB ./noswap.

1007
00:44:44,770 --> 00:44:47,410

1008
00:44:47,410 --> 00:44:51,200
Med andre ord, jeg kommer til å kjøre min
programmet ikke i Bash, vår nye venn

1009
00:44:51,200 --> 00:44:51,850
i dag.

1010
00:44:51,850 --> 00:44:53,970
Jeg kommer til å kjøre min
program noswap inne

1011
00:44:53,970 --> 00:44:56,900
av dette andre programmet heter
GDB, som er en debugger, som

1012
00:44:56,900 --> 00:45:01,035
er et program som er utviklet for å hjelpe
dere mennesker finne og fjerne bugs.

1013
00:45:01,035 --> 00:45:03,410
Så hvis jeg treffer Kjør her, det er
en fryktelig mengde tekst

1014
00:45:03,410 --> 00:45:04,868
at du egentlig aldri trenger å lese.

1015
00:45:04,868 --> 00:45:07,290
Det er egentlig en distraksjon
fra teksten, som

1016
00:45:07,290 --> 00:45:10,030
Jeg kommer til å treffe Kontroll-L
å komme opp på toppen der.

1017
00:45:10,030 --> 00:45:11,800
Dette er GDB prompt.

1018
00:45:11,800 --> 00:45:15,550
Hvis jeg ønsker å kjøre dette programmet nå,
som denne lille jukselapp på dagens

1019
00:45:15,550 --> 00:45:21,860
lysbilde antyder, Run er den første
kommandoer som vi mente å innføre.

1020
00:45:21,860 --> 00:45:25,150
Og jeg bare kommer til å skrive
løpe opp her inne i GDB,

1021
00:45:25,150 --> 00:45:26,811
og faktisk det kjørte mitt program.

1022
00:45:26,811 --> 00:45:29,310
Nå er det noen ekstra
utgangene på skjermen som dette,

1023
00:45:29,310 --> 00:45:31,910
men det er GDB bare å være anal
og fortelle oss hva som skjer.

1024
00:45:31,910 --> 00:45:34,451
Du trenger egentlig ikke å bekymre deg
om disse detaljene akkurat nå.

1025
00:45:34,451 --> 00:45:36,890
Men hva er egentlig kult om
GDB, hvis jeg gjør dette igjen--

1026
00:45:36,890 --> 00:45:42,100
Kontroll-L klarner screen-- la meg gå
videre og type "bryte viktigste," dermed,

1027
00:45:42,100 --> 00:45:45,743
når jeg trykker Enter, sette hva som er
kalt en pause punkt på noswap.c,

1028
00:45:45,743 --> 00:45:51,270
linje 16, som er der GDB
funnet ut mitt program faktisk

1029
00:45:51,270 --> 00:45:53,070
er, min funksjon faktisk er.

1030
00:45:53,070 --> 00:45:55,070
Dette vil vi se bort for nå
men det er adressen

1031
00:45:55,070 --> 00:45:57,310
i minnet spesielt for denne funksjonen.

1032
00:45:57,310 --> 00:46:00,240
Så nå når jeg skriver kjørt,
legge merke til hva som er kult her.

1033
00:46:00,240 --> 00:46:05,650
Min program bryter ved linjen I
fortalte GDB å stanse henrettelsen på.

1034
00:46:05,650 --> 00:46:09,850
Så jeg trenger ikke å nå endre min kode,
legge til noen printf-tallet, rekompilere det, reprise

1035
00:46:09,850 --> 00:46:13,300
det, endre, legge til noen printf-tallet,
lagre det, rekompilere den, kjøre den.

1036
00:46:13,300 --> 00:46:18,100
Jeg kan bare gå gjennom mitt program
skritt for skritt for skritt ved human hastighet

1037
00:46:18,100 --> 00:46:20,880
ikke på Intel-inside slags hastighet.

1038
00:46:20,880 --> 00:46:24,580
>> Så nå merker denne linjen
vises her, og hvis jeg går tilbake

1039
00:46:24,580 --> 00:46:27,800
mitt program i gedit,
legge merke til at det faktisk er

1040
00:46:27,800 --> 00:46:29,280
den aller første linje med kode.

1041
00:46:29,280 --> 00:46:31,240
Det er linje 16 i gedit.

1042
00:46:31,240 --> 00:46:34,610
Det er ledningen 16 i GDB, og selv
om denne svarte og hvite grensesnitt

1043
00:46:34,610 --> 00:46:37,760
er ikke på langt nær så bruker
vennlig, betyr dette

1044
00:46:37,760 --> 00:46:41,680
at linjen 16 har ikke blitt utført
ennå, men det handler om å være.

1045
00:46:41,680 --> 00:46:46,220
Så ja hvis jeg skriver print
x, ikke printf, bare print x,

1046
00:46:46,220 --> 00:46:50,730
Jeg får noen falsk verdi der på null,
fordi x er ikke klargjort ennå.

1047
00:46:50,730 --> 00:46:54,760
Så jeg kommer til å skrive neste, eller, hvis du
ønsker å være fancy, bare n for neste.

1048
00:46:54,760 --> 00:46:59,090
Men når jeg skriver dette oppgir nå
merker det går videre til linje 17.

1049
00:46:59,090 --> 00:47:02,840
Så logisk, hvis jeg har henrettet
linje 16 og jeg nå skriver print x,

1050
00:47:02,840 --> 00:47:03,640
hva bør 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 nå er dette riktignok forvirrende.

1054
00:47:07,820 --> 00:47:11,260
$ 2 er bare en fancy måte, hvis du
ønsker å referere til denne verdien senere,

1055
00:47:11,260 --> 00:47:12,510
du kan si "dollar sign to."

1056
00:47:12,510 --> 00:47:13,480
Det er som en back referanse.

1057
00:47:13,480 --> 00:47:14,570
Men for nå, bare ignorere det.

1058
00:47:14,570 --> 00:47:17,070
Det interessante er hva som er
på høyre side av likhetstegnet.

1059
00:47:17,070 --> 00:47:21,000
Og nå hvis jeg skriver neste gang
og print y, skal jeg se 2.

1060
00:47:21,000 --> 00:47:23,870
Jeg kan også nå skrive ut
x igjen, og ærlig,

1061
00:47:23,870 --> 00:47:27,130
hvis jeg får en litt 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 noen sammenheng rundt
poenget er jeg faktisk på.

1063
00:47:30,590 --> 00:47:35,180
Og nå kan jeg skrive
neste, og det x er 1.

1064
00:47:35,180 --> 00:47:36,300
Nå skriver jeg neste.

1065
00:47:36,300 --> 00:47:37,710
Oh, er y 2.

1066
00:47:37,710 --> 00:47:40,750
Og igjen, det er forvirrende,
fordi GDB utgang

1067
00:47:40,750 --> 00:47:43,044
blir blandes med min egen utgang.

1068
00:47:43,044 --> 00:47:45,710
Men hvis du huske på, ved
skotter frem og tilbake på koden din

1069
00:47:45,710 --> 00:47:47,740
eller legge det ut siden
ved side kanskje, vil du

1070
00:47:47,740 --> 00:47:51,020
se at egentlig er jeg bare
stepping gjennom mitt program.

1071
00:47:51,020 --> 00:47:54,620
>> Men legg merke til hva som skjer videre, bokstavelig talt.

1072
00:47:54,620 --> 00:47:56,380
Her er linje 22.

1073
00:47:56,380 --> 00:48:01,315
La meg gå over den, og dermed går videre
til 23, og hvis jeg skriver ut x nå, fortsatt en.

1074
00:48:01,315 --> 00:48:03,890
Og hvis jeg skriver ut y nå, fortsatt 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å la oss gjenta dette.

1077
00:48:07,450 --> 00:48:10,069
La meg gå tilbake til
topp og type løp igjen.

1078
00:48:10,069 --> 00:48:12,110
Og det sier programmet
som blir feilsøkt

1079
00:48:12,110 --> 00:48:14,109
har startet allerede,
startet fra begynnelsen.

1080
00:48:14,109 --> 00:48:15,420
Ja, la oss gjøre dette igjen.

1081
00:48:15,420 --> 00:48:22,000
Og denne gangen la oss gjøre videre,
neste, neste, neste, neste,

1082
00:48:22,000 --> 00:48:24,180
men nå ting blir interessant.

1083
00:48:24,180 --> 00:48:27,760
Nå ønsker jeg å gå inn
swap, så jeg ikke skriver neste.

1084
00:48:27,760 --> 00:48:34,380
Jeg skriver skritt, og nå merke det
har hoppet meg til noswap.c linje 33.

1085
00:48:34,380 --> 00:48:37,240
Hvis jeg går tilbake til gedit, hva er linje 33?

1086
00:48:37,240 --> 00:48:40,500
Det er den første faktiske
kodelinje innsiden av swap.

1087
00:48:40,500 --> 00:48:44,150
Som er fint, for nå kan jeg
slags rote rundt og få nysgjerrig

1088
00:48:44,150 --> 00:48:46,052
om hva som skjer virkelig i det.

1089
00:48:46,052 --> 00:48:46,760
La meg skrive 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 noen
gal, falsk søppel verdi?

1093
00:48:51,438 --> 00:48:54,579

1094
00:48:54,579 --> 00:48:56,120
PUBLIKUM: Det har ikke blitt initialisert.

1095
00:48:56,120 --> 00:48:57,150
SPEAKER 1: Det har ikke blitt initialisert.

1096
00:48:57,150 --> 00:49:00,270
Og ja, når du kjører et program,
du får en hel haug med minne

1097
00:49:00,270 --> 00:49:03,392
av operativsystemet, men du
har ikke initialisert noen verdier,

1098
00:49:03,392 --> 00:49:05,600
Så uansett hva biter du er
ser her, selv om det er

1099
00:49:05,600 --> 00:49:07,770
denne sprø stor negativ
nummer, betyr bare

1100
00:49:07,770 --> 00:49:10,750
at de er restene fra
noen tidligere bruk av RAM,

1101
00:49:10,750 --> 00:49:13,050
selv om jeg har ikke
meg selv trengte det ennå.

1102
00:49:13,050 --> 00:49:17,086
Så nå kommer jeg til å gå videre og type
neste, og hvis jeg nå skriver print tmp,

1103
00:49:17,086 --> 00:49:17,835
hva bør jeg se?

1104
00:49:17,835 --> 00:49:19,570

1105
00:49:19,570 --> 00:49:23,360
Når verdien av en var,
a er det første argumentet, bare

1106
00:49:23,360 --> 00:49:25,550
som x var den første
ting blir vedtatt i,

1107
00:49:25,550 --> 00:49:30,450
slik at en og x bør være den samme,
så ut tmp bør skrive meg en.

1108
00:49:30,450 --> 00:49:36,360
>> Så hva du vil se i Oppgavesettet
tre er en tutorial av former på GDB,

1109
00:49:36,360 --> 00:49:40,020
men innser at dette er begynnelsen
av en titt på et verktøy som faktisk vil

1110
00:49:40,020 --> 00:49:42,774
hjelpe deg med å løse problemer
så mye mer effektivt.

1111
00:49:42,774 --> 00:49:44,690
Hva vi er i siste instans
kommer til å gjøre på onsdag

1112
00:49:44,690 --> 00:49:48,180
er begynner å skrelle tilbake et par lag
og fjerne noen trening hjul.

1113
00:49:48,180 --> 00:49:50,496
Den tingen kalt streng som
vi har brukt på en stund,

1114
00:49:50,496 --> 00:49:53,370
vi kommer til å sakte ta det bort
fra deg og begynne å snakke om

1115
00:49:53,370 --> 00:49:55,725
noe mer esoterisk
kjent som char *,

1116
00:49:55,725 --> 00:49:59,550
men vi kommer til å gjøre dette hyggelig og
forsiktig først, selv om pekere,

1117
00:49:59,550 --> 00:50:02,730
som de kalles, kan gjøre noen
veldig dårlige ting hvis misbrukt,

1118
00:50:02,730 --> 00:50:06,040
ved å se på en liten leireanimasjon fra
vår venn Nick Parlante fra Stanford

1119
00:50:06,040 --> 00:50:09,670
University, en professor i data
vitenskap som satt sammen denne forhåndsvisningen

1120
00:50:09,670 --> 00:50:11,075
av hva som kommer denne onsdagen.

1121
00:50:11,075 --> 00:50:12,196

1122
00:50:12,196 --> 00:50:13,400
>> [VIDEOAVSPILLING]

1123
00:50:13,400 --> 00:50:13,900
-Hei, Binky.

1124
00:50:13,900 --> 00:50:14,930

1125
00:50:14,930 --> 00:50:15,780
Våkn opp.

1126
00:50:15,780 --> 00:50:17,240
Det er tid for pekeren moro.

1127
00:50:17,240 --> 00:50:18,260

1128
00:50:18,260 --> 00:50:19,350
>> Hva er det?

1129
00:50:19,350 --> 00:50:21,150
Lær om pekere?

1130
00:50:21,150 --> 00:50:22,050
Oh, goody!

1131
00:50:22,050 --> 00:50:22,897

1132
00:50:22,897 --> 00:50:23,730
[END VIDEOAVSPILLING]

1133
00:50:23,730 --> 00:50:25,396
SPEAKER 1: som venter deg på onsdag.

1134
00:50:25,396 --> 00:50:26,440
Vi får se deg da.

1135
00:50:26,440 --> 00:50:27,106
[VIDEOAVSPILLING]

1136
00:50:27,106 --> 00:50:30,420
-Og Nå, dype tanker,
av 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 VIDEOAVSPILLING]