1
00:00:00,000 --> 00:00:12,040
>> [Muziek]

2
00:00:12,040 --> 00:00:16,460
>> SPEAKER 1: Oke, dit is CS50,
en dit is het begin van week vier,

3
00:00:16,460 --> 00:00:20,420
en zoals je misschien al gehoord of
lezen, is de wereld eindigt.

4
00:00:20,420 --> 00:00:23,520
Gaan al rond het internet
heeft zijn kennis en bewustzijn

5
00:00:23,520 --> 00:00:27,100
van een bug in een programma, een
programmeertaal genaamd Bash.

6
00:00:27,100 --> 00:00:32,729
Dit is prachtig gebrandmerkt
als Shellshock, of de Bash deur,

7
00:00:32,729 --> 00:00:35,485
maar artikelen als deze
zijn niet ongewoon zijn.

8
00:00:35,485 --> 00:00:38,807
En in feite, veel van hen te brengen
herinneringen terug van Heartbleed,

9
00:00:38,807 --> 00:00:41,640
die je misschien al gemerkt hebt in de
Druk afgelopen voorjaar terug, die

10
00:00:41,640 --> 00:00:43,980
was ook tamelijk dramatisch.

11
00:00:43,980 --> 00:00:47,110
Nu van die van jullie hier
vandaag, hoeveel van jullie hebben,

12
00:00:47,110 --> 00:00:50,330
zelfs als je niet begrijpt wat
draait het allemaal om, gehoord van Shellshock?

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

14
00:00:51,370 --> 00:00:54,245
Oke, en hoe velen van jullie
hebben computers die kwetsbaar zijn?

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

16
00:00:55,680 --> 00:01:00,250
OK, er moet veel, veel meer handen
tot nu, om redenen die we zullen zien.

17
00:01:00,250 --> 00:01:02,580
>> Laten we eens kijken naar wat er
is er in de media

18
00:01:02,580 --> 00:01:05,304
en leg het dan een beetje
hier voor ons technisch.

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

20
00:01:07,670 --> 00:01:11,250
>> SPEAKER 2: Security experts hebben
gewaarschuwd dat een ernstige fout kon

21
00:01:11,250 --> 00:01:15,650
ongeveer beïnvloeden honderden
miljoenen van 's werelds webgebruikers.

22
00:01:15,650 --> 00:01:20,600
Dus wat is precies de fout die is geweest
nagesynchroniseerde Shellshock, en wat doet het?

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

24
00:01:23,720 --> 00:01:28,910
Nou, Shellshock is ook bekend als de
Bash bug, de software die het exploiteert.

25
00:01:28,910 --> 00:01:33,230
Hackers gebruiken het virus te scannen kwetsbaar
systemen met Linux en Unix

26
00:01:33,230 --> 00:01:36,300
besturingssystemen en vervolgens te infecteren.

27
00:01:36,300 --> 00:01:38,730
Bash is een command line shell.

28
00:01:38,730 --> 00:01:43,460
Dit stelt gebruikers in kwestie commando's te starten
programma's en functies in de software

29
00:01:43,460 --> 00:01:45,250
door het invoeren van tekst.

30
00:01:45,250 --> 00:01:49,980
Het wordt meestal gebruikt door programmeurs, en
moet niet open voor de buitenwereld,

31
00:01:49,980 --> 00:01:51,590
hoewel Shellshock verandert dat.

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

33
00:01:54,160 --> 00:01:57,910
>> Nou, worringly, sommige analisten
waarschuwen het kan een grotere bedreiging te zijn,

34
00:01:57,910 --> 00:02:01,580
omdat Shellshock is volledige
controle over een besmette machine,

35
00:02:01,580 --> 00:02:06,030
terwijl Heartbleed alleen toegestaan
hackers bespioneren computers.

36
00:02:06,030 --> 00:02:09,130
Het is zo ernstig, het is
is beoordeeld op 10 van de 10

37
00:02:09,130 --> 00:02:11,900
voor de ernst van de Nationale
Vulnerability Database.

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

39
00:02:15,530 --> 00:02:20,015
2/3 van alle webservers zijn op
risico's, waaronder een aantal Mac-computers.

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

41
00:02:22,760 --> 00:02:25,600
Nou, zorg ervoor dat je
patch nu uw systemen.

42
00:02:25,600 --> 00:02:29,330
Iedereen het hosten van een website draaiende
de getroffen besturingssystemen

43
00:02:29,330 --> 00:02:31,800
moet actie zo snel mogelijk te nemen.

44
00:02:31,800 --> 00:02:35,390
Iedereen die zich kan veroorloven het eruit moet zien
om de monitoring en web-applicatie

45
00:02:35,390 --> 00:02:37,355
firewalls om uit te kijken voor eventuele aanslagen.

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

47
00:02:39,979 --> 00:02:41,770
SPEAKER 3: Ergste
dat zou kunnen gebeuren is

48
00:02:41,770 --> 00:02:45,080
dat iemand code zou schrijven dat
zou automatisch gaan scannen

49
00:02:45,080 --> 00:02:48,280
het internet en van invloed zou zijn
al deze computers.

50
00:02:48,280 --> 00:02:50,710
En zodra ze dat goed doen,
het ergste wat ze konden doen

51
00:02:50,710 --> 00:02:53,300
is gewoon alles te verwijderen,
of sluit de sites af.

52
00:02:53,300 --> 00:02:55,360
Dus we konden de schade zien
vanuit dat oogpunt,

53
00:02:55,360 --> 00:02:58,300
waar we kwaadwillende mensen zouden hebben
die alleen maar besluiten om ellende te veroorzaken

54
00:02:58,300 --> 00:03:02,534
door het brengen van systemen naar beneden of verwijderen
bestanden, en dat soort dingen.

55
00:03:02,534 --> 00:03:05,200
SPEAKER 2: Sommigen zeggen dat dit een
van de meest moeilijk te meten

56
00:03:05,200 --> 00:03:08,080
bugs in jaren, en
kan weken duren of zelfs

57
00:03:08,080 --> 00:03:10,820
maanden de tijd om zijn uiteindelijke effect te bepalen.

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

59
00:03:12,180 --> 00:03:15,560
>> SPEAKER 1: Dus dat is allemaal waar,
maar het grappige is, bijna alle

60
00:03:15,560 --> 00:03:18,330
van de beelden zag je gewoon,
behalve misschien het toetsenbord,

61
00:03:18,330 --> 00:03:20,930
heeft niets te maken met
de bug dan ook.

62
00:03:20,930 --> 00:03:23,960
Servers en draden enzovoort,
Het is een soort van zijdelings gerelateerd,

63
00:03:23,960 --> 00:03:27,410
maar in de kern is het eigenlijk best
bekend wat er aan de hand hier.

64
00:03:27,410 --> 00:03:30,050
In feite, laat me gaan in
onze CS50 apparaat.

65
00:03:30,050 --> 00:03:32,910
Laat me ga je gang en het maximaliseren
het terminalvenster hier.

66
00:03:32,910 --> 00:03:36,020
En jullie zijn met behulp van deze,
of de embedded versie daarvan,

67
00:03:36,020 --> 00:03:39,460
in gedit om programma's te schrijven,
typen opdrachten, enzovoorts,

68
00:03:39,460 --> 00:03:43,690
en dit is eigenlijk, en heeft
al weken, Bash, B-A-S-H.

69
00:03:43,690 --> 00:03:46,890
Dit is de Bourne-Again Shell,
dat is gewoon een mooie manier om te zeggen,

70
00:03:46,890 --> 00:03:50,220
Dit is een programma dat is
knippert snel, effectief,

71
00:03:50,220 --> 00:03:51,970
die zit te wachten
voor input voor u.

72
00:03:51,970 --> 00:03:53,920
En het is de opdracht
line interface via welke

73
00:03:53,920 --> 00:03:57,650
jullie hebben gelopen commando's en
uiteindelijk samenstellen en dan loopt

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

75
00:03:58,400 --> 00:04:01,320
>> Maar Bash is ook een programmering
taal de volgende betekenis.

76
00:04:01,320 --> 00:04:05,460
Je weet dat er commando's als
cd en ls en ook kletteren en anderen,

77
00:04:05,460 --> 00:04:09,580
maar je kunt je eigen commando's te definiëren
door de uitvoering ervan in Bash.

78
00:04:09,580 --> 00:04:11,420
Nu zijn we niet van plan om
gaan in groot detail

79
00:04:11,420 --> 00:04:16,089
met betrekking tot de programmeertaal dreun, maar
weet bijvoorbeeld dat op het moment,

80
00:04:16,089 --> 00:04:17,607
er is geen commando genaamd "hallo."

81
00:04:17,607 --> 00:04:19,440
Zodat het kan worden gevonden in
een van deze pakketten.

82
00:04:19,440 --> 00:04:20,856
Het is niet op mijn computer geïnstalleerd.

83
00:04:20,856 --> 00:04:21,870
Vraag uw beheerder.

84
00:04:21,870 --> 00:04:26,030
Maar als ik wil dat er een programma worden
genaamd "hello" in Bash of bij mij prompt,

85
00:04:26,030 --> 00:04:30,810
Ik kan eigenlijk gebruiken syntax dat is
heel graag C. Het is niet helemaal hetzelfde,

86
00:04:30,810 --> 00:04:35,020
maar het ziet er vergelijkbaar met een
functie, zij missen wat details.

87
00:04:35,020 --> 00:04:38,090
Niets lijkt te gebeuren,
maar nu als ik typ "hello"

88
00:04:38,090 --> 00:04:40,960
kan je eigenlijk schrijven
programma niet in C, niet in Java,

89
00:04:40,960 --> 00:04:44,280
niet in een andere programmeertaal
taal, maar in Bash zelf.

90
00:04:44,280 --> 00:04:47,630
>> Nu is de sleutel hier is dat ik schreef het
noem ik wilde deze nieuwe opdracht te geven,

91
00:04:47,630 --> 00:04:50,820
en de haakjes zijn ook
symbolisch voor dit een functie is.

92
00:04:50,820 --> 00:04:54,010
Even terzijde, kun je ook leuk doen
dingen, en in feite, zelfs op Mac OS,

93
00:04:54,010 --> 00:04:55,620
Dit is een programma genaamd Terminal.

94
00:04:55,620 --> 00:04:58,800
Het komt ingebouwd in iemands
computer die een Mac heeft in deze kamer,

95
00:04:58,800 --> 00:05:03,640
en je kunt soortgelijke dingen in Mac doen
OS, maar je kunt meer dan dat gaan.

96
00:05:03,640 --> 00:05:07,110
En dit is een kleine tangentiële,
maar het is wel leuk.

97
00:05:07,110 --> 00:05:09,715
Ik werd vanmorgen herinnerd,
wanneer het denken dit door middel van,

98
00:05:09,715 --> 00:05:13,279
van een klein spel dat ik gebruikt om te spelen
met een van de voormalige TFs CS50's

99
00:05:13,279 --> 00:05:16,570
waarbij elk ogenblik zou hij weglopen
zijn toetsenbord met zijn scherm ontgrendeld,

100
00:05:16,570 --> 00:05:23,611
Ik zou een commando uit te voeren
zoals dit-- "hallo zeggen."

101
00:05:23,611 --> 00:05:26,610
En nu elke keer kwam hij terug naar zijn
toetsenbord nadat Ik schraapte het scherm

102
00:05:26,610 --> 00:05:27,985
en hij zou gaan zitten,
proberen om wat werk te doen,

103
00:05:27,985 --> 00:05:29,250
een lijst van de inhoud van zijn directory--

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

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

108
00:05:32,120 --> 00:05:35,030
>> SPEAKER 1: Dus, in alle eerlijkheid,
het was niet echt "hallo."

109
00:05:35,030 --> 00:05:36,894
Het was meestal iets
meer verwant aan dat--

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

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

112
00:05:37,750 --> 00:05:39,320
SPEAKER 1: --that Ik would--
zodat zijn computer zou

113
00:05:39,320 --> 00:05:42,170
zweren bij hem elke keer als hij daadwerkelijk
ging aan zijn toetsenbord.

114
00:05:42,170 --> 00:05:46,265
En heel snel bedacht hij
geen reactie zijn scherm ontgrendeld.

115
00:05:46,265 --> 00:05:48,730
Maar dit suggereert dat de soort
van domme plezier dat je

116
00:05:48,730 --> 00:05:50,210
kunnen hebben met iets als Bash.

117
00:05:50,210 --> 00:05:52,770
Maar het is een beetje meer
ernstig, om zeker te zijn, dan dat.

118
00:05:52,770 --> 00:05:57,235
En in feite is dit een van de
meest gevaarlijke en langdurige bugs

119
00:05:57,235 --> 00:05:58,860
dat is echt wereldwijd geraakt de wereld.

120
00:05:58,860 --> 00:06:02,060
Deze bug is al
ongeveer 20 jaar

121
00:06:02,060 --> 00:06:05,780
en u zult worden gevonden in slechts een
schip door de relatieve eenvoud.

122
00:06:05,780 --> 00:06:07,990
>> Dit is een representatief
zeg dan, dat als je

123
00:06:07,990 --> 00:06:10,448
het bezit van een Mac, letterlijk op dit moment
wanneer u uw deksel open,

124
00:06:10,448 --> 00:06:12,940
je kunt proberen te typen in dat
programma genaamd Terminal.

125
00:06:12,940 --> 00:06:15,410
Terminal is onder
Toepassingen Utilities--

126
00:06:15,410 --> 00:06:18,790
voor een keer, niet Windows-gebruikers niet hoeven te
zorgen te maken over dit bijzondere threat--

127
00:06:18,790 --> 00:06:22,310
maar die van u met Macs kunt typen
dit in een venster zoals ik hier doe,

128
00:06:22,310 --> 00:06:24,210
en als je typt
dat in dit programma

129
00:06:24,210 --> 00:06:28,830
genaamd Terminal, zoals ik nu doe,
Als u het woord 'kwetsbaar'

130
00:06:28,830 --> 00:06:32,200
uw computer is
kwetsbaar voor uitbuiting.

131
00:06:32,200 --> 00:06:33,850
>> Nu, wat betekent dat eigenlijk?

132
00:06:33,850 --> 00:06:35,870
En dit is weliswaar
sommige behoorlijk gek syntax,

133
00:06:35,870 --> 00:06:39,050
maar laten we in ieder geval trekken uit
aantal interessante aspecten.

134
00:06:39,050 --> 00:06:42,567
Dus er is een aantal syntax die lijkt
een beetje bekend, tenminste C

135
00:06:42,567 --> 00:06:43,950
en het programmeren in het algemeen.

136
00:06:43,950 --> 00:06:47,550
Ik zie een aantal haakjes,
puntkomma, accolades, en dergelijke,

137
00:06:47,550 --> 00:06:50,820
maar het blijkt dat dit
stomme ding hier in het geel

138
00:06:50,820 --> 00:06:53,580
vooral afhankelijk
dat doet niets.

139
00:06:53,580 --> 00:06:57,840
De dubbele punt betekent niets doen, en de
puntkomma betekent stoppen met niets doen.

140
00:06:57,840 --> 00:07:00,250
Dus binnen deze
accolades, het feit

141
00:07:00,250 --> 00:07:02,440
dat ik een gelijke
teken naar links, dit

142
00:07:02,440 --> 00:07:05,500
hoofdzaak creëren
een commando of een variabele

143
00:07:05,500 --> 00:07:09,520
genaamd x, en het toewijzen van het
dat gele stukje code daar.

144
00:07:09,520 --> 00:07:14,040
Dat zou iets als "echo te zijn
hallo "of" zeggen piep "of iets

145
00:07:14,040 --> 00:07:15,120
vergelijkbaar met die.

146
00:07:15,120 --> 00:07:17,780
Maar let op als je ogen
dwalen verder naar rechts,

147
00:07:17,780 --> 00:07:22,150
er is meer aan deze lijn dan
alleen het einde van die puntkomma.

148
00:07:22,150 --> 00:07:25,160
"Echo kwetsbaar," en dan
verder dan dat er nog meer.

149
00:07:25,160 --> 00:07:26,530
Een andere puntkomma, bash-c :.

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

151
00:07:28,120 --> 00:07:34,050
>> Zo lang verhaal kort,
deze regel code is

152
00:07:34,050 --> 00:07:36,660
voldoende om dwingende
een computer die is

153
00:07:36,660 --> 00:07:39,830
kwetsbaar iets te doen
dat u wilt doen,

154
00:07:39,830 --> 00:07:44,290
omdat er een bug in Bash waarbij
hoewel Bash moest stoppen

155
00:07:44,290 --> 00:07:48,980
lezen van regels van het commando rechts
er na de gele tekst,

156
00:07:48,980 --> 00:07:52,520
voor een 20-plus jaar oude bug,
Bash is eigenlijk al het lezen

157
00:07:52,520 --> 00:07:56,780
verder dan dat puntkomma en mooi
veel te doen wat het wordt verteld.

158
00:07:56,780 --> 00:07:59,070
>> Dus wat is de implicatie
van dat uiteindelijk?

159
00:07:59,070 --> 00:08:01,340
Ik zei gewoon "echo hello"
of "echo kwetsbaar,"

160
00:08:01,340 --> 00:08:05,449
maar wat als je iets deed
eigenlijk kwaadaardige, zoals rm-rf *,

161
00:08:05,449 --> 00:08:07,240
die je misschien niet
hebben voordat ooit getypt,

162
00:08:07,240 --> 00:08:08,920
en eerlijk gezegd heb je waarschijnlijk
moet niet te vroeg,

163
00:08:08,920 --> 00:08:10,700
omdat je een kunt doen
veel schade mee.

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

165
00:08:11,210 --> 00:08:12,990
rm doet wat, natuurlijk?

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

167
00:08:14,270 --> 00:08:15,930
* Betekent wat?

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

169
00:08:16,430 --> 00:08:18,180
Het is dus een zogenaamd
wild card, dus betekent

170
00:08:18,180 --> 00:08:20,410
alles verwijderen
de huidige directory.

171
00:08:20,410 --> 00:08:23,379
-r gebeurt recursieve te betekenen,
wat betekent dat als wat je te verwijderen

172
00:08:23,379 --> 00:08:26,420
is een directory, en de binnenkant van daar
is andere bestanden en andere mappen,

173
00:08:26,420 --> 00:08:28,950
recursief induiken er
en dat alles wissen.

174
00:08:28,950 --> 00:08:31,040
En f is de ergste van allemaal.

175
00:08:31,040 --> 00:08:32,580
Iedereen weet wat -f betekent hier?

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

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

178
00:08:34,360 --> 00:08:37,830
Dus dwingen middelen, zelfs
als dit een slecht idee,

179
00:08:37,830 --> 00:08:40,939
doe het zonder te vragen mij
voor verdere bevestiging.

180
00:08:40,939 --> 00:08:43,230
Dus, weet je, we lachen bij
dit, maar eerlijk gezegd, ik waarschijnlijk

181
00:08:43,230 --> 00:08:44,972
typt u deze meerdere keren
een dag, omdat de realiteit

182
00:08:44,972 --> 00:08:47,210
is het is de snelste manier om
een hele hoop dingen moeten verwijderen.

183
00:08:47,210 --> 00:08:48,590
Maar ook heb ik wat schade gedaan.

184
00:08:48,590 --> 00:08:53,100
>> Maar als je naar een computer te misleiden
in het definiëren van enkele domme variabele

185
00:08:53,100 --> 00:08:56,810
of functie genaamd x, maar
tricking de computer in te voeren

186
00:08:56,810 --> 00:09:00,030
buiten de grenzen van deze
functie, dan dat puntkomma,

187
00:09:00,030 --> 00:09:04,430
je zou inderdaad kunnen verleiden een computer
in iets uitvoeren als rm-rf

188
00:09:04,430 --> 00:09:07,810
of de e-mail commando
of de opdracht Kopiëren.

189
00:09:07,810 --> 00:09:11,400
Even wat letterlijk je kunt doen met de
computer, of het nu het verwijderen van bestanden,

190
00:09:11,400 --> 00:09:15,350
aanmaken van bestanden, spammen iemand,
aanvallende enkele server op afstand,

191
00:09:15,350 --> 00:09:17,190
als je het kan uitdrukken
met een opdracht, je

192
00:09:17,190 --> 00:09:19,120
kan een computer te verleiden tot dat te doen.

193
00:09:19,120 --> 00:09:21,510
>> Nu, wat is een voorbeeld van
hoe je dit zou kunnen doen?

194
00:09:21,510 --> 00:09:24,300
Nou, er is heel veel computers
op het internet lopen Bash.

195
00:09:24,300 --> 00:09:26,390
Ieder van ons Mac-gebruikers zijn onder hen.

196
00:09:26,390 --> 00:09:30,390
Een groot aantal Linux-servers behoren tot
ze net zo goed, en Unix servers.

197
00:09:30,390 --> 00:09:32,630
Windows opnieuw krijgt
relatief de haak

198
00:09:32,630 --> 00:09:34,590
tenzij u hebt geïnstalleerd
speciale software.

199
00:09:34,590 --> 00:09:37,130
Nu veel servers,
bijvoorbeeld om webservers,

200
00:09:37,130 --> 00:09:39,840
en in feite Linux is misschien wel de
meest populaire besturingssysteem

201
00:09:39,840 --> 00:09:43,060
te draaien op computers op het internet
die zijn waar je van webpagina's.

202
00:09:43,060 --> 00:09:44,910
Nu zoals we zullen later zien
in het semester, toen

203
00:09:44,910 --> 00:09:48,470
u een verzoek uit te sturen
uw browser-- Chrome,

204
00:09:48,470 --> 00:09:50,790
Internet Explorer, whatever--
naar een externe server,

205
00:09:50,790 --> 00:09:53,730
blijkt dat hoewel
je net getypt www.example.com,

206
00:09:53,730 --> 00:09:59,590
Uw browser is het verzenden van een bericht
dat is een beetje meer mysterieuze, zoals deze.

207
00:09:59,590 --> 00:10:01,239
>> Maar let een beetje iets vreemds.

208
00:10:01,239 --> 00:10:03,030
De eerste twee regels
Ik heb nog nooit eerder gezien,

209
00:10:03,030 --> 00:10:04,904
maar ze zien er niet uit
bijzonder bedreigend.

210
00:10:04,904 --> 00:10:08,030
Maar let op wat ik heb gestolen
voor de derde regel hier.

211
00:10:08,030 --> 00:10:13,390
Als een slechte kerel was om een ​​bericht te sturen
als deze uit zijn of haar computer

212
00:10:13,390 --> 00:10:17,270
om een ​​kwetsbare Mac of een
kwetsbare Linux-server,

213
00:10:17,270 --> 00:10:21,580
het grappige is dat Bash,
dat eenvoudige kleine opdrachtprompt

214
00:10:21,580 --> 00:10:27,450
alomtegenwoordig en is vaak
gebruikte in wezen te voeren

215
00:10:27,450 --> 00:10:30,020
de inhoud van een
boodschap die het ontvangt.

216
00:10:30,020 --> 00:10:33,490
En door die logica, kunt u
truc een webserver derhalve

217
00:10:33,490 --> 00:10:36,370
door iets verzenden als
User-Agent, die meestal

218
00:10:36,370 --> 00:10:38,300
wordt verondersteld om het te zeggen
naam van je browser.

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

220
00:10:42,420 --> 00:10:44,590
is gewoon je browser
manier om zichzelf te identificeren.

221
00:10:44,590 --> 00:10:46,605
Maar als een slechte kerel zeer
slim zegt, mm-mm, ik ben

222
00:10:46,605 --> 00:10:47,930
niet van plan om u te vertellen
wat mijn browser is,

223
00:10:47,930 --> 00:10:50,888
Ik ga in plaats daarvan ga je deze sturen
cryptisch uitziende ding met een rm-rf

224
00:10:50,888 --> 00:10:55,840
* In het, kunt u letterlijk een truc
kwetsbare webserver op het internet

225
00:10:55,840 --> 00:10:59,055
in het uitvoeren van precies dat in
er voor het verwijderen van alle bestanden.

226
00:10:59,055 --> 00:11:00,930
En eerlijk gezegd, dat is niet
zelfs de ergste.

227
00:11:00,930 --> 00:11:01,763
Je kunt alles doen.

228
00:11:01,763 --> 00:11:04,480
Je zou kunnen beginnen met een gedistribueerde
denial of service-aanval

229
00:11:04,480 --> 00:11:07,030
Als u dit bericht verzonden naar
hele trossen van webservers

230
00:11:07,030 --> 00:11:10,256
en dan hadden ze allemaal afstammen, voor
bijvoorbeeld op Harvard.edu servers,

231
00:11:10,256 --> 00:11:12,130
en u kunt sorteren van bang
heck uit hen

232
00:11:12,130 --> 00:11:15,490
een netwerkverkeer dat was
anders wordt veroorzaakt door deze slechte kerel.

233
00:11:15,490 --> 00:11:18,760
>> Dus, lang verhaal kort, bijna
iedereen in deze kamer, die eigenaar is van een Mac

234
00:11:18,760 --> 00:11:20,240
is kwetsbaar voor dit.

235
00:11:20,240 --> 00:11:24,100
De zilveren voering is dat, tenzij je
het runnen van een webserver op uw laptop,

236
00:11:24,100 --> 00:11:27,780
en tenzij je hebt eigenlijk geconfigureerd
het om iets als SSH toelaten in het,

237
00:11:27,780 --> 00:11:28,670
je bent echt veilig.

238
00:11:28,670 --> 00:11:31,710
Het is kwetsbaar, maar er is geen
men probeert te krijgen in uw laptop,

239
00:11:31,710 --> 00:11:33,290
dus je kunt een soort van gerust zijn.

240
00:11:33,290 --> 00:11:36,210
Echter, Apple zal binnenkort
zijn het bijwerken van een oplossing voor dit.

241
00:11:36,210 --> 00:11:39,660
De wereld van Linux heeft al vrijgegeven
een aantal fixes voor Fedora en Ubuntu

242
00:11:39,660 --> 00:11:43,790
andere versies en Linux, en inderdaad
Als u Update 50 draaien in het apparaat,

243
00:11:43,790 --> 00:11:45,930
zelfs dat ook wordt
geactualiseerd en gecorrigeerd.

244
00:11:45,930 --> 00:11:47,764
Dat is ook niet
echt kwetsbaar geweest,

245
00:11:47,764 --> 00:11:49,804
want als je hebt
gesleuteld aan het apparaat

246
00:11:49,804 --> 00:11:52,770
en maakte je laptop in het openbaar
toegankelijk op het internet, die niet is

247
00:11:52,770 --> 00:11:54,910
standaard, je hebt
eigenlijk prima omdat geweest

248
00:11:54,910 --> 00:11:56,890
van firewalling en andere technieken.

249
00:11:56,890 --> 00:12:01,000
>> Maar het is een extreem voorbeeld van een bug
dat we hebben geleefd voor letterlijk 20

250
00:12:01,000 --> 00:12:04,050
jaar, en wie als iemand weet
al die tijd heeft geweten?

251
00:12:04,050 --> 00:12:06,300
En in feite is dit een van
de fundamentele uitdagingen

252
00:12:06,300 --> 00:12:08,690
dat we later zullen zien in de
semester over de veiligheid,

253
00:12:08,690 --> 00:12:13,020
is dat net als in de echte wereld,
de good guys zijn in het nadeel.

254
00:12:13,020 --> 00:12:16,500
Om de slechteriken te houden, moeten we
Zorg ervoor dat elke deur is op slot,

255
00:12:16,500 --> 00:12:20,340
dat elk raam is veilig, dat
elk punt van binnenkomst in een huis

256
00:12:20,340 --> 00:12:21,980
veilig is om de slechteriken te houden.

257
00:12:21,980 --> 00:12:26,870
Maar wat doet de bad guy te
doen om daadwerkelijk een compromis uw huis

258
00:12:26,870 --> 00:12:28,200
en stelen van je?

259
00:12:28,200 --> 00:12:32,574
Hij of zij heeft gewoon een unlocked vinden
deur, een gebroken raam, of iets

260
00:12:32,574 --> 00:12:35,240
in die richting, en het is de
hetzelfde in computerbeveiliging.

261
00:12:35,240 --> 00:12:37,660
We kunnen miljoenen schrijven
regels programmeercode

262
00:12:37,660 --> 00:12:40,570
en spenderen honderden of duizenden
uren proberen om het juist te krijgen,

263
00:12:40,570 --> 00:12:43,370
maar als je gewoon een
fout in de juistheid,

264
00:12:43,370 --> 00:12:47,030
U kunt het hele systeem te zetten en
zelfs in dit geval volledig Internet

265
00:12:47,030 --> 00:12:48,660
en de wereld in gevaar.

266
00:12:48,660 --> 00:12:51,950
>> Dus als je wilt om meer te leren
over dit, ga dan naar deze URL hier.

267
00:12:51,950 --> 00:12:54,450
Er is geen noodzaak voor actie
vanavond tenzij je

268
00:12:54,450 --> 00:12:57,116
onder hen meer comfortabel dat
zijn het runnen van uw eigen web-

269
00:12:57,116 --> 00:12:59,810
server, in welk geval u zou mogen,
in feite, update uw software.

270
00:12:59,810 --> 00:13:03,244
>> En dit is ook de titel van
een toespraak, en nu een papier,

271
00:13:03,244 --> 00:13:05,410
dat we hebben gekoppeld aan de
website cursus voor vandaag.

272
00:13:05,410 --> 00:13:07,600
Het was door een collega
genaamd Ken Thompson, die

273
00:13:07,600 --> 00:13:10,120
was het aanvaarden van een zeer bekende
onderscheiding in de informatica,

274
00:13:10,120 --> 00:13:13,495
en hij gaf deze toespraak een aantal jaren
geleden, in wezen op hetzelfde onderwerp.

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

276
00:13:18,250 --> 00:13:20,520
Vragen mensen de vraag,
moet je echt

277
00:13:20,520 --> 00:13:23,480
vertrouwen, uiteindelijk, de
software die u hebt gekregen?

278
00:13:23,480 --> 00:13:26,100
Bijvoorbeeld, we hebben allemaal
het schrijven van programma's,

279
00:13:26,100 --> 00:13:27,820
en we hebben het samenstellen
ze met Clang.

280
00:13:27,820 --> 00:13:31,830
En om je kennis, je hebt geschreven
alle programma's voor CS50 waar er

281
00:13:31,830 --> 00:13:35,310
een achterdeur van soorten, is een weg
dat een slechte kerel, als het runnen van uw programma,

282
00:13:35,310 --> 00:13:37,410
over uw computer zou kunnen nemen?

283
00:13:37,410 --> 00:13:38,310
Waarschijnlijk niet, toch?

284
00:13:38,310 --> 00:13:40,180
Mario en Gulzig, en Credit.

285
00:13:40,180 --> 00:13:41,680
Dit zijn allemaal vrij kleine programma's.

286
00:13:41,680 --> 00:13:43,910
Je zou mooi zijn
slecht als je eigenlijk

287
00:13:43,910 --> 00:13:47,310
maakte je hele computer kwetsbaar
na het schrijven van 10 of 20 regels code,

288
00:13:47,310 --> 00:13:49,690
of althans niet bewust van enige
van de gevolgen voor de beveiliging.

289
00:13:49,690 --> 00:13:52,023
Nu zeg ik dat schertsend,
maar we gaan vandaag zien

290
00:13:52,023 --> 00:13:54,600
en deze week is het eigenlijk
echt, echt makkelijk

291
00:13:54,600 --> 00:13:57,980
slecht te zijn en zelfs
korte programma's kwetsbaar.

292
00:13:57,980 --> 00:14:02,880
>> Maar voor nu, op zijn minst, realiseren
dat de vraag hier wordt gevraagd

293
00:14:02,880 --> 00:14:04,850
ongeveer Clang in een compiler.

294
00:14:04,850 --> 00:14:08,360
Waarom hebben wij vertrouwen Clang
voor de afgelopen twee of drie weken?

295
00:14:08,360 --> 00:14:12,650
Wie zegt dat wie schreef Clang
niet over een "als" toestand er

296
00:14:12,650 --> 00:14:17,680
dat hoofdzakelijk geïnjecteerde sommige nullen
en die in elk programma compileert

297
00:14:17,680 --> 00:14:21,180
dat zou laten hem of haar de toegang
uw computer wanneer u slaapt

298
00:14:21,180 --> 00:14:23,580
en uw laptop deksel open
en uw computer aanstaat?

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

300
00:14:24,080 --> 00:14:28,350
Wij hebben dit soort van eer systeem recht
nu waar we vertrouwen erop dat Clang is legit.

301
00:14:28,350 --> 00:14:30,000
U erop vertrouwen dat het apparaat is legit.

302
00:14:30,000 --> 00:14:34,430
Je vertrouwt dat letterlijk elk programma
op uw Mac of pc is betrouwbaar.

303
00:14:34,430 --> 00:14:37,510
En als deze eenvoudige bug doet vermoeden,
zelfs als het niet kwaadaardig is,

304
00:14:37,510 --> 00:14:40,580
dat is absoluut niet
waarschijnlijk het geval.

305
00:14:40,580 --> 00:14:42,350
>> Dus moet je bang als de hel zijn.

306
00:14:42,350 --> 00:14:45,560
Eerlijk gezegd, er is geen eenvoudige
oplossing die andere

307
00:14:45,560 --> 00:14:48,185
dan een soort van maatschappelijke bewustwording
de toenemende complexiteit

308
00:14:48,185 --> 00:14:50,310
dat we bouwen op de top
van onze computersystemen,

309
00:14:50,310 --> 00:14:53,740
en hoe steeds kwetsbaarder
we kunnen heel goed zijn.

310
00:14:53,740 --> 00:14:55,570
>> Nu met dat gezegd, Breakout.

311
00:14:55,570 --> 00:14:59,889
Dus Breakout is probleem set drie, en
Breakout is een spel van weleer

312
00:14:59,889 --> 00:15:02,180
dat je nog wel herinneren, maar
voor ons in probleem set drie,

313
00:15:02,180 --> 00:15:04,450
Het stelt ons in staat om te nemen
dingen back-up een inkeping

314
00:15:04,450 --> 00:15:08,880
zodat wanneer we schrijven programma's,
zelfs in een Terminal-venster als dit,

315
00:15:08,880 --> 00:15:14,670
kunnen we eigenlijk lopen, uiteindelijk,
grafische programma's niet

316
00:15:14,670 --> 00:15:17,800
in tegenstelling tot die we hadden
toegang tot in Scratch.

317
00:15:17,800 --> 00:15:20,910
Dus dit is het personeel
uitvoering van Breakout,

318
00:15:20,910 --> 00:15:23,930
dat is alleen deze baksteen-brekende
spel, dat je je peddel terug te gaan

319
00:15:23,930 --> 00:15:27,590
en weer, en je de bal raakt
tegen die gekleurde stenen boven.

320
00:15:27,590 --> 00:15:30,020
Dus dit brengt ons
soort terug naar waar

321
00:15:30,020 --> 00:15:33,180
We konden heel snel
met Scratch, en nu met C,

322
00:15:33,180 --> 00:15:35,800
de uitvoering van onze eigen
grafische gebruikersinterfaces.

323
00:15:35,800 --> 00:15:38,960
>> Maar meer dan dat, deze
probleem set is de eerste

324
00:15:38,960 --> 00:15:41,000
waarin we geven
u een bos van code.

325
00:15:41,000 --> 00:15:43,940
En in feite, ik breng expliciete
aandacht, want vooral

326
00:15:43,940 --> 00:15:47,090
voor degenen die minder comfortabel, dit
probleem stellen, althans op het eerste gezicht,

327
00:15:47,090 --> 00:15:49,170
gaat om het gevoel dat
we hebben het gemaakt tot een inkeping.

328
00:15:49,170 --> 00:15:51,540
Omdat we je hebben gegeven,
voor sommige zoekterm

329
00:15:51,540 --> 00:15:54,930
en sorteren problemen in de PSET,
een bos van code die we schreven,

330
00:15:54,930 --> 00:15:56,680
en een paar reacties
die zeggen "te doen,"

331
00:15:56,680 --> 00:15:58,221
waar je de lege plekken op te vullen.

332
00:15:58,221 --> 00:16:00,020
Dus niet te eng, maar
het is de eerste keer

333
00:16:00,020 --> 00:16:03,370
wij overhandigen u code die je nodig hebt om
eerst te lezen, te begrijpen en vervolgens toe te voegen aan

334
00:16:03,370 --> 00:16:04,290
en vul het in.

335
00:16:04,290 --> 00:16:05,940
>> En dan met Breakout,
we gaan om hetzelfde te doen,

336
00:16:05,940 --> 00:16:08,740
waardoor u een paar dozijn meer lijnen
van de code die, eerlijk gezegd, geef je

337
00:16:08,740 --> 00:16:11,490
veel van het kader voor
het spel, maar stoppen met korte

338
00:16:11,490 --> 00:16:14,304
van de uitvoering van de bakstenen
en de bal en de peddel,

339
00:16:14,304 --> 00:16:15,970
maar we voeren een aantal andere functies.

340
00:16:15,970 --> 00:16:18,280
En zelfs dat op het eerste gezicht, weer,
vooral als minder comfortabel,

341
00:16:18,280 --> 00:16:21,480
lijkt vooral ontmoedigend en
je denkt dat er zoveel nieuwe functies

342
00:16:21,480 --> 00:16:24,070
je nodig hebt om je geest te wikkelen
rond, en dat is waar.

343
00:16:24,070 --> 00:16:26,281
Maar houd in gedachten, het is
heel graag Scratch.

344
00:16:26,281 --> 00:16:28,780
Kans groot dat u niet al te gebruiken
de puzzelstukjes in Scratch.

345
00:16:28,780 --> 00:16:31,120
Kans groot dat u niet de zorg in te pakken
je geest om ze allemaal

346
00:16:31,120 --> 00:16:33,617
omdat al duurde het was een
snelle blik om te begrijpen, oh,

347
00:16:33,617 --> 00:16:35,450
dat is wat ik kan doen
met dat puzzelstukje.

348
00:16:35,450 --> 00:16:38,260
En inderdaad, in het probleem te stellen
3 spec, zullen wij u wijzen

349
00:16:38,260 --> 00:16:41,370
op de documentatie die zal
u kennismaken met een aantal nieuwe functies,

350
00:16:41,370 --> 00:16:43,570
en uiteindelijk de programmering
construeert u gebruikt.

351
00:16:43,570 --> 00:16:47,610
Condities, loops,
variabelen en functies

352
00:16:47,610 --> 00:16:50,720
identiek zal zijn
wat we tot nu toe hebben gezien.

353
00:16:50,720 --> 00:16:53,560
>> Dus inderdaad, wat we zullen geven
u is wat voorbeeldcode die

354
00:16:53,560 --> 00:16:56,110
Hiermee kunt u een venster te maken
dat ziet er niet veel anders dan deze,

355
00:16:56,110 --> 00:16:59,540
en uiteindelijk om te zetten in
iets heel graag dit.

356
00:16:59,540 --> 00:17:02,250
Dus profiteren van de CS50,
bespreken kantooruren en meer,

357
00:17:02,250 --> 00:17:05,290
en gerustgesteld dat
de hoeveelheid code die je hebt om te schrijven

358
00:17:05,290 --> 00:17:06,760
is eigenlijk niet zo heel veel.

359
00:17:06,760 --> 00:17:10,359
De eerste uitdaging is juist om te acclimatiseren
uzelf op een code die we hebben geschreven.

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

361
00:17:11,450 --> 00:17:15,810
>> Heeft u vragen over pset3,
Shellshock, of anderszins?

362
00:17:15,810 --> 00:17:19,226
>> Publiek: Het leek
gaan door met Breakout

363
00:17:19,226 --> 00:17:22,154
dat de code is bijna
een object-georiënteerde stijl,

364
00:17:22,154 --> 00:17:24,675
maar ik dacht dat C was een
object-georiënteerd programma.

365
00:17:24,675 --> 00:17:26,050
SPEAKER 1: Een goede vraag.

366
00:17:26,050 --> 00:17:28,258
Dus op zoek via de
distributie code, de code

367
00:17:28,258 --> 00:17:30,180
we schreven voor pset3,
voor degenen die bekend zijn, is het

368
00:17:30,180 --> 00:17:32,230
ziet eruit alsof het een
weinig objectgeoriënteerde.

369
00:17:32,230 --> 00:17:33,800
Korte antwoord is, het is.

370
00:17:33,800 --> 00:17:38,130
Het is een benadering van de manier waarop u
misschien objectgeoriënteerde code doen met behulp van

371
00:17:38,130 --> 00:17:41,850
een taal zoals C, maar het is
uiteindelijk toch procedureel.

372
00:17:41,850 --> 00:17:44,900
Er zijn geen methoden binnenin
de variabelen, zoals u zult zien.

373
00:17:44,900 --> 00:17:46,180
Maar het doet denken aan dat.

374
00:17:46,180 --> 00:17:48,780
En we zullen die functie weer te zien
als we in PHP en JavaScript

375
00:17:48,780 --> 00:17:49,946
tegen het einde van het semester.

376
00:17:49,946 --> 00:17:53,667
Maar voor nu, denk aan het als
een hint van wat er komen gaat.

377
00:17:53,667 --> 00:17:54,250
Goede vraag.

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

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

380
00:17:56,550 --> 00:17:59,730
Dus samenvoegen soort was hoe we
linkse dingen laatste tijd.

381
00:17:59,730 --> 00:18:03,250
En samenvoegen soort was koel in de
zin dat het zo veel sneller,

382
00:18:03,250 --> 00:18:07,100
ten minste op basis van het vluchtig testen
we hebben vorige week, dan, zeg, bel

383
00:18:07,100 --> 00:18:08,710
soort, selectie sorteren, insertion sort.

384
00:18:08,710 --> 00:18:11,780
En wat was te netjes is gewoon
hoe bondig en netjes

385
00:18:11,780 --> 00:18:12,810
je kunt het uit te drukken.

386
00:18:12,810 --> 00:18:15,840
En wat hebben we zeggen het was een bovenste
gebonden aan de looptijd van de merge

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

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
>> PUBLIEK: n log n?

391
00:18:19,360 --> 00:18:20,819
>> SPEAKER 1: n log n, rechts. n log n.

392
00:18:20,819 --> 00:18:23,776
En we terug naar wat die komen
werkelijk betekent of waar die vandaan komt,

393
00:18:23,776 --> 00:18:25,570
maar dit was beter
dan looptijd

394
00:18:25,570 --> 00:18:28,440
die we zagen voor de bubble
selectie en insertion sort?

395
00:18:28,440 --> 00:18:30,610
Zo n kwadraat. n kwadraat
is groter dan dit,

396
00:18:30,610 --> 00:18:34,650
en ook al is het niet helemaal duidelijk,
weten dat log n kleiner is dan n,

397
00:18:34,650 --> 00:18:36,910
dus als je n keer
iets kleiner dan n,

398
00:18:36,910 --> 00:18:38,680
het gaat om minder dan n kwadraat zijn.

399
00:18:38,680 --> 00:18:40,130
Het is een beetje van intuïtie daar.

400
00:18:40,130 --> 00:18:42,190
Maar we betaalden een prijs voor.

401
00:18:42,190 --> 00:18:47,000
Het was sneller, maar een thema dat begon
vorige week naar voren was deze afweging.

402
00:18:47,000 --> 00:18:49,804
Ik heb betere prestaties
tijd verstandig, maar wat

403
00:18:49,804 --> 00:18:52,470
had ik moeten besteden aan de andere
de hand, om te bereiken dat?

404
00:18:52,470 --> 00:18:53,591
>> PUBLIEK: Memory.

405
00:18:53,591 --> 00:18:54,465
SPEAKER 1: Zeg nog eens?

406
00:18:54,465 --> 00:18:55,173
PUBLIEK: Memory.

407
00:18:55,173 --> 00:18:57,040
SPEAKER 1: Geheugen, of
ruimte meer in het algemeen.

408
00:18:57,040 --> 00:18:59,040
En het was niet super
duidelijk onze mensen,

409
00:18:59,040 --> 00:19:02,240
maar herinneren dat onze vrijwilligers
werden naar voren stapt en intensivering

410
00:19:02,240 --> 00:19:04,780
terug alsof er een scala
hier en alsof er

411
00:19:04,780 --> 00:19:07,130
een tweede array hier dat
ze kunnen gebruiken, omdat we

412
00:19:07,130 --> 00:19:09,080
broodnodige ergens naar die mensen samen te voegen.

413
00:19:09,080 --> 00:19:11,480
We konden niet alleen ruilen hen op zijn plaats.

414
00:19:11,480 --> 00:19:13,800
Dus samenvoegen soort hefboomwerking
meer ruimte, die

415
00:19:13,800 --> 00:19:15,620
we niet nodig met
de andere algoritmen,

416
00:19:15,620 --> 00:19:17,410
maar het voordeel is dat het veel sneller.

417
00:19:17,410 --> 00:19:20,780
En eerlijk gezegd, in de echte wereld de ruimte
deze dagen-- RAM, een harde schijf ruimtebesparing

418
00:19:20,780 --> 00:19:25,030
is relatief goedkoop en dus dat
niet per se een slechte zaak.

419
00:19:25,030 --> 00:19:28,320
>> Dus laten we eens een snelle blik, een beetje
meer methodisch, naar wat we deden

420
00:19:28,320 --> 00:19:30,220
en waarom we vonden het een n log n.

421
00:19:30,220 --> 00:19:33,260
Dus hier zijn de acht nummers en de
acht vrijwilligers hadden we de vorige keer.

422
00:19:33,260 --> 00:19:35,718
En het eerste wat samenvoegen
Sorteer vertelde ons te doen was wat?

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

424
00:19:37,010 --> 00:19:38,010
PUBLIEK: Verdeel in twee.

425
00:19:38,010 --> 00:19:38,663
SPEAKER 1: Zeg nog eens?

426
00:19:38,663 --> 00:19:39,650
PUBLIEK: Verdeel in twee.

427
00:19:39,650 --> 00:19:40,610
SPEAKER 1: Verdeel in twee, rechts.

428
00:19:40,610 --> 00:19:42,818
Dit doet sterk denken aan
het telefoonboek van de kloof

429
00:19:42,818 --> 00:19:44,220
en verover meer in het algemeen.

430
00:19:44,220 --> 00:19:45,640
Dus hebben we gekeken naar de linker helft.

431
00:19:45,640 --> 00:19:48,700
En toen we eenmaal gezegd, een soort
de linkerhelft van de elementen,

432
00:19:48,700 --> 00:19:49,690
wat hebben we volgende zeggen?

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

434
00:19:51,210 --> 00:19:54,860
Sorteer de linkerhelft van de linker
de helft, wat ons toeliet om,

435
00:19:54,860 --> 00:19:57,570
Na verdelen in twee,
focus op vier en twee.

436
00:19:57,570 --> 00:20:01,280
>> Hoe maak je nu een lijst te sorteren, in
geel, van de grootte van twee, met behulp van Merge Sort?

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

438
00:20:02,330 --> 00:20:04,580
Goed verdeel het in tweeën,
en sorteren van de linker helft.

439
00:20:04,580 --> 00:20:07,100
En dit was waar dingen
kreeg een beetje dom kort.

440
00:20:07,100 --> 00:20:10,720
Hoe maak je een lijst die is van afstand
maat one, als dit nummer vier hier?

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

442
00:20:12,330 --> 00:20:13,210
Het is opgelost.

443
00:20:13,210 --> 00:20:14,200
U bent klaar.

444
00:20:14,200 --> 00:20:17,300
>> Maar hoe maak je een lijst van de gekozen afstand
maat one wanneer het de nummer twee?

445
00:20:17,300 --> 00:20:21,640
Nou, hetzelfde, maar nu wat was de
derde en de belangrijkste stap in het Merge Sort?

446
00:20:21,640 --> 00:20:24,020
Je moest naar links samenvoegen
de helft en de rechter helft.

447
00:20:24,020 --> 00:20:26,580
En als we dat deden, keken we
bij vier, hebben we gekeken naar twee.

448
00:20:26,580 --> 00:20:28,750
We besloten al goed,
uiteraard twee staat voorop,

449
00:20:28,750 --> 00:20:31,840
dus hebben we twee in haar
plaats, gevolgd door vier.

450
00:20:31,840 --> 00:20:35,010
En nu moet je soort terugspoelen,
en dit is een soort van karakteristieke

451
00:20:35,010 --> 00:20:37,570
van een algoritme zoals Merge
Sorteren, terugspoelen in het geheugen.

452
00:20:37,570 --> 00:20:40,240
Wat was de volgende regel van het verhaal?

453
00:20:40,240 --> 00:20:41,780
Wat moet ik richten op de volgende stap?

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

455
00:20:43,110 --> 00:20:47,350
De rechterhelft van de linker
de helft, dat is zes en acht.

456
00:20:47,350 --> 00:20:50,320
>> Dus laat me gewoon stap door dit
zonder belaboring het punt te veel.

457
00:20:50,320 --> 00:20:53,330
Zes en acht, dan zes is
gesorteerd acht wordt gesorteerd.

458
00:20:53,330 --> 00:20:57,190
Meng ze samen als dat,
en nu is de volgende grote stap

459
00:20:57,190 --> 00:21:00,990
is natuurlijk, sorteren de rechterhelft van
de eerste stap van dit algoritme.

460
00:21:00,990 --> 00:21:02,870
Dus richten we ons op een, drie, zeven, vijf.

461
00:21:02,870 --> 00:21:04,540
We hebben toen gericht op de linker helft.

462
00:21:04,540 --> 00:21:09,400
De linkerhelft van dat de rechterhelft van
dat, en vervolgens samen te voegen in een en drie.

463
00:21:09,400 --> 00:21:13,100
Dan is de rechter helft, dan is de helft naar links
ervan, dan is de rechter helft van het.

464
00:21:13,100 --> 00:21:15,985
Samenvoegen in, en wat nu stap blijft?

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

466
00:21:18,040 --> 00:21:22,460
Voeg de grote linker helft en de grote
rechter helft, dus men gaat daar beneden,

467
00:21:22,460 --> 00:21:27,330
dan twee, dan drie, dan vier, dan
vijf dan zes, dan zeven, dan acht.

468
00:21:27,330 --> 00:21:31,990
>> Dus nu waarom is dit uiteindelijk het openbaren,
vooral als n en logaritmen meer

469
00:21:31,990 --> 00:21:35,487
algemeen vrij ontsnappen u,
althans in de recente geschiedenis?

470
00:21:35,487 --> 00:21:37,070
Nou, let op de hoogte van deze zaak.

471
00:21:37,070 --> 00:21:41,230
We hadden acht elementen, en we
gedeeld door twee, twee, twee.

472
00:21:41,230 --> 00:21:44,590
Dus log basis van twee van de acht geeft ons drie.

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

474
00:21:45,640 --> 00:21:48,540
En geloof me op dat als
een beetje vaag over dat.

475
00:21:48,540 --> 00:21:54,710
Maar log basis twee van de acht is drie,
dus we hebben drie lagen samenvoegen gedaan.

476
00:21:54,710 --> 00:21:57,170
En als we gefuseerd
elementen, hoeveel elementen

477
00:21:57,170 --> 00:21:58,950
hebben we naar op elk van die rijen?

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

479
00:22:00,212 --> 00:22:01,437
Een totaal van n, toch?

480
00:22:01,437 --> 00:22:04,020
Omdat aan de bovenste rij samenvoegen,
ook al deden we het stukje bij beetje,

481
00:22:04,020 --> 00:22:05,990
we uiteindelijk raakte elk nummer een keer.

482
00:22:05,990 --> 00:22:09,054
En in de tweede rij, naar
samenvoegen die lijsten van de grootte van twee,

483
00:22:09,054 --> 00:22:10,470
we moesten elk element een keer aanraken.

484
00:22:10,470 --> 00:22:12,690
En dan is hier echt
duidelijk in de laatste rij,

485
00:22:12,690 --> 00:22:15,430
We moesten elk van die raken
elementen eenmaal, maar slechts eenmaal,

486
00:22:15,430 --> 00:22:18,400
dus hierin ligt dan onze n log n.

487
00:22:18,400 --> 00:22:21,780
>> En nu alleen maar om dingen een beetje te maken
meer formele voor slechts een moment, als je

488
00:22:21,780 --> 00:22:24,260
waren om dit nu te analyseren
een soort hogere

489
00:22:24,260 --> 00:22:28,340
en proberen om te beslissen, hoe goed
zou je gaan over het uiten van

490
00:22:28,340 --> 00:22:31,780
de looptijd van dit algoritme
gewoon door er naar te kijken en niet

491
00:22:31,780 --> 00:22:33,590
met behulp van een gekunsteld voorbeeld?

492
00:22:33,590 --> 00:22:36,590
Nou, hoeveel tijd zou je zeggen een
stap als dit in het geel zou nemen,

493
00:22:36,590 --> 00:22:37,173
als n <2 terug?

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

495
00:22:38,840 --> 00:22:39,830
Dat is een grote O van wat?

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

497
00:22:41,450 --> 00:22:44,540
Dus ik ben het zien van een, dus een stap,
misschien twee stappen, want het is als

498
00:22:44,540 --> 00:22:47,110
en dan terug te keren, maar het is
constante tijd, toch?

499
00:22:47,110 --> 00:22:49,960
Dus we zeiden O (1), en dat is
hoe ik dit zal uiten.

500
00:22:49,960 --> 00:22:51,480
T, gewoon looptijd.

501
00:22:51,480 --> 00:22:54,150
n is de grootte van de ingang,
dus T (n), gewoon een mooie manier

502
00:22:54,150 --> 00:22:56,330
zeggen de running
tijd bepaalde input van grootte n

503
00:22:56,330 --> 00:23:00,220
gaat worden in de orde
van constante tijd, in O (1).

504
00:23:00,220 --> 00:23:01,970
>> Maar voor de rest, hoe zit dit?

505
00:23:01,970 --> 00:23:05,660
Hoe zou u drukken de
looptijd van deze gele lijn?

506
00:23:05,660 --> 00:23:06,250
T van wat?

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

508
00:23:09,440 --> 00:23:12,665
U kunt soort cheat hier en
antwoord op mijn vraag cyclisch.

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

510
00:23:14,770 --> 00:23:17,900
Als de looptijd in
algemeen zijn we gewoon zeggen is T (n).

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

512
00:23:18,950 --> 00:23:22,490
En nu bent u soort hier punteren en
zeggen, nou ja, gewoon afstand de linker helft,

513
00:23:22,490 --> 00:23:23,920
en vervolgens sorteert de rechter helft.

514
00:23:23,920 --> 00:23:27,520
Hoe kunnen we symbolisch vertegenwoordigen
de looptijd van deze gele lijn?

515
00:23:27,520 --> 00:23:28,020
T van wat?

516
00:23:28,020 --> 00:23:29,360
Wat is de grootte van de input?

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

518
00:23:30,510 --> 00:23:31,057
n meer dan twee.

519
00:23:31,057 --> 00:23:32,140
Waarom heb ik niet gewoon zeggen dat?

520
00:23:32,140 --> 00:23:36,449
En dan is dit nog een T (n / 2) en vervolgens
nogmaals, als ik het samenvoegen van twee gesorteerde helften,

521
00:23:36,449 --> 00:23:38,615
hoeveel elementen ga ik
moeten raken totaal?

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
Dus ik kan dit uit te drukken,
gewoon soort van fancy,

525
00:23:42,790 --> 00:23:44,430
als de lopende tijd in het algemeen.

526
00:23:44,430 --> 00:23:51,140
T (n) is gewoon de looptijd van T (n / 2),
plus T (n / 2), linkerhelft en rechterhelft,

527
00:23:51,140 --> 00:23:55,360
plus O (n), die waarschijnlijk n trappen,
maar misschien, als ik met twee vingers,

528
00:23:55,360 --> 00:23:57,960
het is twee keer zoveel
stappen, maar het is lineair.

529
00:23:57,960 --> 00:24:00,440
Het is een aantal stappen
dat is een factor van n,

530
00:24:00,440 --> 00:24:02,270
dus we kunnen dit uit te drukken als deze.

531
00:24:02,270 --> 00:24:05,550
En dit is waar nu zullen we punter naar de
achterkant van onze middelbare school mathhandboek

532
00:24:05,550 --> 00:24:10,290
we zijn dat herhaling uiteindelijk
eindigt gelijk dit, n keer log n,

533
00:24:10,290 --> 00:24:12,530
als je eigenlijk doen uit
de wiskunde meer formeel.

534
00:24:12,530 --> 00:24:13,950
>> Dus dat is gewoon twee perspectieven.

535
00:24:13,950 --> 00:24:17,500
Een numeriek met een
hard-coded representatief voorbeeld

536
00:24:17,500 --> 00:24:21,140
behulp van acht cijfers en een
algemene kijk op hoe we daar aankwamen.

537
00:24:21,140 --> 00:24:25,670
Maar wat echt interessant hier
is, nogmaals, dit begrip van het wielrennen.

538
00:24:25,670 --> 00:24:26,900
Ik maak geen gebruik van loops.

539
00:24:26,900 --> 00:24:29,860
Ik ben soort van het definiëren van
iets wat op zich

540
00:24:29,860 --> 00:24:31,950
niet alleen met dit
wiskundige functie,

541
00:24:31,950 --> 00:24:34,860
maar ook in termen van deze pseudo-code.

542
00:24:34,860 --> 00:24:38,260
Deze pseudo-code is recursieve
dat twee van de lijnen

543
00:24:38,260 --> 00:24:42,310
is in wezen het vertellen om te gaan
Gebruik zelf een kleinere oplossen

544
00:24:42,310 --> 00:24:45,400
probleem van kleinere omvang,
en vervolgens weer

545
00:24:45,400 --> 00:24:48,820
en weer, totdat we whittle het
neer op deze zogenaamde basisscenario.

546
00:24:48,820 --> 00:24:52,810
>> Dus laten we eigenlijk trek een meer dwingende
take-away van deze als volgt.

547
00:24:52,810 --> 00:24:58,420
Laat me gaan in gedit en neem een
kijken naar een aantal van de huidige broncode,

548
00:24:58,420 --> 00:24:59,930
in het bijzonder dit voorbeeld hier.

549
00:24:59,930 --> 00:25:03,709
Sigma 0, die blijkbaar toevoegt
de nummers een tot en met n.

550
00:25:03,709 --> 00:25:05,750
Dus laten we eens kijken wat er bekend
en onbekende hier.

551
00:25:05,750 --> 00:25:08,690
Eerst hebben we een paar
omvat, dus niets nieuws.

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

553
00:25:09,190 --> 00:25:11,370
Ik ben een beetje vaag op
dit na een paar dagen,

554
00:25:11,370 --> 00:25:13,790
maar wat hebben we zeggen een
prototype van een functie is?

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

556
00:25:15,099 --> 00:25:16,015
PUBLIEK: [onverstaanbaar].

557
00:25:16,015 --> 00:25:16,905
SPEAKER 1: Wat is dat?

558
00:25:16,905 --> 00:25:17,800
PUBLIEK: We kondigen het.

559
00:25:17,800 --> 00:25:18,883
SPEAKER 1: We kondigen het.

560
00:25:18,883 --> 00:25:22,290
Dus u geeft Clang, hey,
dit eigenlijk niet de uitvoering nog,

561
00:25:22,290 --> 00:25:25,740
maar ergens in dit bestand, vermoedelijk,
zal worden een functie genaamd wat?

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
En dit is slechts een belofte dat
het gaat er als volgt uitzien.

565
00:25:30,540 --> 00:25:33,720
Het gaat om een ​​geheel getal te nemen als
input-- en ik kan meer expliciet worden

566
00:25:33,720 --> 00:25:36,570
en zeggen: int n --en het is
gaan naar een int terug te keren,

567
00:25:36,570 --> 00:25:39,900
maar puntkomma middelen, mm, ik zal rond te krijgen
om de uitvoering van dit een beetje later.

568
00:25:39,900 --> 00:25:40,989
Nogmaals, Clang is dom.

569
00:25:40,989 --> 00:25:43,280
Het is alleen maar om te weten wat
u vertellen boven naar beneden,

570
00:25:43,280 --> 00:25:45,765
dus we moeten in ieder geval geven
het een hint van wat er komen gaat.

571
00:25:45,765 --> 00:25:47,330
>> Laten we nu eens kijken naar de belangrijkste hier.

572
00:25:47,330 --> 00:25:50,040
Laten scroll hier naar beneden en
zien wat de belangrijkste aan het doen is.

573
00:25:50,040 --> 00:25:53,780
Het is niet zo lang van een functie, en
in feite het construct hier bekend.

574
00:25:53,780 --> 00:25:57,590
Ik verklaar een variabele n, en dan
Ik steeds weer lastig vallen van de gebruiker

575
00:25:57,590 --> 00:26:01,880
voor een positief geheel getal met behulp getInt,
en enige uitgang uit deze lus

576
00:26:01,880 --> 00:26:03,280
zodra de gebruiker heeft voldaan.

577
00:26:03,280 --> 00:26:05,670
Do While, hebben we gebruikt om te
pesten de gebruiker op die manier.

578
00:26:05,670 --> 00:26:06,670
Nu is dit interessant.

579
00:26:06,670 --> 00:26:08,510
Ik verklaar een int genaamd "antwoord."

580
00:26:08,510 --> 00:26:11,420
Ik wijs het de return waarde
van een functie genaamd "sigma".

581
00:26:11,420 --> 00:26:15,200
Ik weet niet wat dat nog doet, maar
Ik herinner me verklaren het even geleden.

582
00:26:15,200 --> 00:26:18,310
En dan ga ik langs bij de
waarde die de gebruiker heeft ingevoerd in, n,

583
00:26:18,310 --> 00:26:20,420
en vervolgens verslag ik het antwoord.

584
00:26:20,420 --> 00:26:22,260
Nou laten we terugbladeren
voor slechts een moment.

585
00:26:22,260 --> 00:26:28,620
Laten we verder gaan in deze map, maken
sigma 0, en eigenlijk dit programma uit te voeren

586
00:26:28,620 --> 00:26:30,490
en zie wat er gebeurt.

587
00:26:30,490 --> 00:26:35,930
Dus als ik ga je gang en rennen
dit programma ./sigma-0,

588
00:26:35,930 --> 00:26:40,139
en ik typ in een positieve
integer als twee, Sigma,

589
00:26:40,139 --> 00:26:43,180
als het Griekse symbool aangeeft, is slechts
naar alle nummers optellen

590
00:26:43,180 --> 00:26:44,320
nul tot twee.

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

592
00:26:46,560 --> 00:26:48,830
Dus dit moet hopelijk geef me 3.

593
00:26:48,830 --> 00:26:49,750
Dat is alles wat het doet.

594
00:26:49,750 --> 00:26:52,690
En op dezelfde manier, als ik weer lopen deze
en ik geef het de nummer drie,

595
00:26:52,690 --> 00:26:56,721
dat is 3 plus 2, dus dat is
5, plus 1 moet mij geven 6.

596
00:26:56,721 --> 00:26:59,470
En dan als ik echt gek en
Typ in grote aantallen,

597
00:26:59,470 --> 00:27:01,290
het zou mij
groter en groter sommen.

598
00:27:01,290 --> 00:27:02,250
Dus dat is alles.

599
00:27:02,250 --> 00:27:04,010
>> Dus wat doet sigma eruit?

600
00:27:04,010 --> 00:27:05,430
Nou, het is vrij eenvoudig.

601
00:27:05,430 --> 00:27:08,940
Het is hoe we zouden kunnen hebben geïmplementeerd
dit voor de afgelopen paar weken.

602
00:27:08,940 --> 00:27:11,120
"Int" gaat naar de return type zijn.

603
00:27:11,120 --> 00:27:14,330
Sigma is de naam, en het duurt
een variabele m in plaats van n.

604
00:27:14,330 --> 00:27:15,940
Ik zal boven veranderen up.

605
00:27:15,940 --> 00:27:17,340
Dan is dit gewoon een sanity check.

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

607
00:27:18,430 --> 00:27:19,950
We zullen zien waarom in een moment.

608
00:27:19,950 --> 00:27:24,220
Nu verklaar ik een andere variabele,
sum, initialiseren op nul.

609
00:27:24,220 --> 00:27:28,140
Dan heb ik deze For-lus
iteratie, blijkbaar voor de duidelijkheid,

610
00:27:28,140 --> 00:27:33,810
van i = 1 op tot een = m, welke
wat de gebruiker heeft ingevoerd in, en dan heb ik

611
00:27:33,810 --> 00:27:35,690
verhoog de som als deze.

612
00:27:35,690 --> 00:27:37,360
En dan terug de som.

613
00:27:37,360 --> 00:27:38,440
>> Dus een paar vragen.

614
00:27:38,440 --> 00:27:42,370
One, eis ik in mijn reactie dat dit
vermijdt risico van een oneindige lus.

615
00:27:42,370 --> 00:27:45,620
Waarom zou passeren in een negatief getal
veroorzaken, wat kan een oneindige lus?

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

617
00:27:49,396 --> 00:27:51,290
>> PUBLIEK: Je zult nooit m bereiken.

618
00:27:51,290 --> 00:27:52,880
>> SPEAKER 1: Reik nooit m.

619
00:27:52,880 --> 00:27:55,880
Maar m wordt doorgegeven in, dus laten we
een eenvoudig voorbeeld beschouwen.

620
00:27:55,880 --> 00:27:58,510
Als m wordt gevoerd door de
gebruiker als negatieve.

621
00:27:58,510 --> 00:28:00,059
Ongeacht het belangrijkste.

622
00:28:00,059 --> 00:28:01,850
Belangrijkste beschermt ons tegen
dit ook, dus ik ben gewoon

623
00:28:01,850 --> 00:28:04,680
het zijn echt anale met
sigma om er ook voor zorgen

624
00:28:04,680 --> 00:28:06,540
dat de input niet kan negatief zijn.

625
00:28:06,540 --> 00:28:10,130
Als m is negatief,
iets als negatieve.

626
00:28:10,130 --> 00:28:11,930
Wat gaat er gebeuren?

627
00:28:11,930 --> 00:28:14,390
Nou, ik zal
geïnitialiseerd om een,

628
00:28:14,390 --> 00:28:19,060
en vervolgens ik zal worden
minder dan of gelijk aan 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
Dat was-- laten we niet,
laten we nix dit verhaal.

633
00:28:29,370 --> 00:28:32,780
Ik heb niet gevraagd die vraag, omdat
het risico dat ik een verwijzing naar

634
00:28:32,780 --> 00:28:38,360
gaat niet gebeuren omdat i
altijd zal groter zijn than-- OK,

635
00:28:38,360 --> 00:28:39,871
Ik intrekken die vraag.

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

637
00:28:40,370 --> 00:28:42,030
Laten we ons alleen richten op dit deel hier.

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

639
00:28:44,210 --> 00:28:48,830
Waarom heb ik verklaren wat
buiten de lus?

640
00:28:48,830 --> 00:28:52,010
Notice on line 49 Ik heb
i verklaarde binnenkant van de lus,

641
00:28:52,010 --> 00:28:54,950
maar online 48 Ik heb
verklaarde een aantal buiten.

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

643
00:28:55,695 --> 00:28:56,611
PUBLIEK: [onverstaanbaar].

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

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

646
00:28:59,400 --> 00:29:03,360
Dus in de eerste plaats doe ik zeker niet
willen verklaren en initialiseren som

647
00:29:03,360 --> 00:29:06,130
nul binnen de
lus op elke iteratie,

648
00:29:06,130 --> 00:29:09,370
omdat dit duidelijk zou de nederlaag van de
doel van een opsomming van de nummers.

649
00:29:09,370 --> 00:29:11,770
Ik zou blijven veranderen
de waarde weer op nul.

650
00:29:11,770 --> 00:29:17,992
En ook, wat is een andere, meer arcane
reden voor hetzelfde ontwerp beslissing?

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

652
00:29:18,954 --> 00:29:20,279
>> PUBLIEK: [onverstaanbaar].

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

654
00:29:21,070 --> 00:29:24,060
Ik wil het buiten toegang
van de lus te op welke lijn?

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

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

657
00:29:26,400 --> 00:29:29,910
En op basis van onze vuistregel
van een paar colleges geleden,

658
00:29:29,910 --> 00:29:33,680
variabelen worden scoped, echt, om de
accolades die ze omvatten.

659
00:29:33,680 --> 00:29:38,190
Dus als ik geen som binnenkant verklaren
van deze uiterlijke accolades,

660
00:29:38,190 --> 00:29:40,250
Ik kan het niet gebruiken in lijn 53.

661
00:29:40,250 --> 00:29:43,160
Anders gezegd, als ik verklaard
som in hier, of zelfs binnen de

662
00:29:43,160 --> 00:29:45,410
Lus, kon ik niet tot het in 53.

663
00:29:45,410 --> 00:29:47,150
De variabele zou effectief worden gegaan.

664
00:29:47,150 --> 00:29:48,579
Dus een paar redenen daar.

665
00:29:48,579 --> 00:29:50,370
Maar laten we nu eens terug te gaan
en zie wat er gebeurt.

666
00:29:50,370 --> 00:29:51,730
Dus sigma wordt aangeroepen.

667
00:29:51,730 --> 00:29:55,640
Het voegt up 1 en 2, of 1 plus 2
plus 3, en dan geeft de waarde,

668
00:29:55,640 --> 00:29:59,660
slaat deze op in antwoord, en printf hier
Daarom zie ik op het scherm.

669
00:29:59,660 --> 00:30:03,079
Dus dit is wat we een iteratief zullen noemen
aanpak, waarbij iteratie net

670
00:30:03,079 --> 00:30:03,870
betekent het gebruik van een lus.

671
00:30:03,870 --> 00:30:06,900
Een For-lus, een While-lus, een Do Terwijl
lus, net weer iets te doen

672
00:30:06,900 --> 00:30:08,380
en opnieuw en opnieuw.

673
00:30:08,380 --> 00:30:13,505
>> Maar sigma is een soort van een nette functie in
dat ik kon het anders uit te voeren.

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

675
00:30:14,620 --> 00:30:19,120
Hoe zit het met deze, die
gewoon wel cool zijn,

676
00:30:19,120 --> 00:30:21,880
laat me echt te ontdoen
van veel afleiding

677
00:30:21,880 --> 00:30:24,380
omdat deze functie
is eigenlijk heel simpel.

678
00:30:24,380 --> 00:30:27,780
Laten Whittle het neer net
om de vier kern-lijnen

679
00:30:27,780 --> 00:30:30,410
en zich te ontdoen van alle
commentaar en accolades.

680
00:30:30,410 --> 00:30:34,334
Dit is een soort van een mind-blowing
alternatieve implementatie.

681
00:30:34,334 --> 00:30:37,250
Oke, misschien niet erg-blowing,
maar het is een beetje sexier, oke,

682
00:30:37,250 --> 00:30:39,920
om te kijken naar deze zo veel beknopter.

683
00:30:39,920 --> 00:30:43,120
Met slechts vier regels code,
Ik heb eerst dit sanity check.

684
00:30:43,120 --> 00:30:45,732
Als m kleiner is dan of gelijk aan
nul, sigma heeft geen zin.

685
00:30:45,732 --> 00:30:48,190
Het is alleen de bedoeling om in
dit geval voor positieve getallen,

686
00:30:48,190 --> 00:30:50,340
dus ik ga gewoon
nul willekeurig terug

687
00:30:50,340 --> 00:30:53,210
zodat we in ieder geval hebben
sommige zogenaamde basisscenario.

688
00:30:53,210 --> 00:30:54,430
>> Maar hier is het mooie.

689
00:30:54,430 --> 00:30:59,930
Het geheel van dit idee, het toevoegen van de
getallen van 1 tot n, en m in casu

690
00:30:59,930 --> 00:31:02,630
kan worden gedaan door het soort van passeren van de bok.

691
00:31:02,630 --> 00:31:04,947
Nou, wat is de som van 1 tot en met m?

692
00:31:04,947 --> 00:31:05,780
Nou, weet je wat?

693
00:31:05,780 --> 00:31:11,949
Het is dezelfde als de som van m
plus de som van 1 tot m minus 1.

694
00:31:11,949 --> 00:31:12,740
Nou weet je wat?

695
00:31:12,740 --> 00:31:13,940
Wat is sigma van m min 1?

696
00:31:13,940 --> 00:31:17,860
Nou, als je soort van deze te volgen
logisch, het is hetzelfde als m minus 1

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

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

699
00:31:22,480 --> 00:31:26,012
Dus je kan soort alleen--
dit is als, als je gewoon

700
00:31:26,012 --> 00:31:28,220
proberen om een ​​vriend te ergeren
en ze je een vraag stellen,

701
00:31:28,220 --> 00:31:31,344
je soort antwoorden met een vraag,
kun je soort te houden passeren van de bok.

702
00:31:31,344 --> 00:31:34,560
Maar wat is de belangrijkste is dat als je blijft
waardoor de vraag kleiner

703
00:31:34,560 --> 00:31:36,910
en kleiner, je bent
niet vragen wat is sigma

704
00:31:36,910 --> 00:31:39,116
n, wat is sigma van
n, wat is sigma van n?

705
00:31:39,116 --> 00:31:40,990
Je vraagt ​​wat er
sigma van n, wat is sigma

706
00:31:40,990 --> 00:31:42,839
van n minus 1, wat is sigma van n min 2?

707
00:31:42,839 --> 00:31:44,880
Uiteindelijk uw vraag
wat gaat worden?

708
00:31:44,880 --> 00:31:50,250
Wat sigma van een of
nul, een zeer kleine waarde,

709
00:31:50,250 --> 00:31:52,220
en zodra je
krijgen dat je vriend,

710
00:31:52,220 --> 00:31:54,350
je bent niet van plan om te vragen
dezelfde vraag weer,

711
00:31:54,350 --> 00:31:55,975
je bent gewoon gaat zeggen, oh het is nul.

712
00:31:55,975 --> 00:31:58,490
We zijn klaar met het spelen van dit soort
domme cyclische spel.

713
00:31:58,490 --> 00:32:02,950
>> Dus recursie is de handeling in de programmering
van een functie oproepen zelf.

714
00:32:02,950 --> 00:32:06,630
Dit programma worden opgesteld en beheerd, is
gaat gedragen precies dezelfde manier

715
00:32:06,630 --> 00:32:09,620
maar wat is de belangrijkste is dat de binnenkant
van een functie genaamd sigma,

716
00:32:09,620 --> 00:32:13,150
er is een regel code, waarin
we onszelf noemen,

717
00:32:13,150 --> 00:32:14,980
die normaal zou zijn slecht.

718
00:32:14,980 --> 00:32:21,160
Bijvoorbeeld, wat als ik voor het eerst
Dit samengesteld, dus zorg sigma--

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

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

721
00:32:25,050 --> 00:32:27,690
Positief geheel getal, dan kunt u, 50 1275.

722
00:32:27,690 --> 00:32:30,810
Wat de functie lijkt
zijn, op basis van een test, correct.

723
00:32:30,810 --> 00:32:34,917
Maar wat als ik een beetje gevaarlijk
en de zogenaamde base case verwijderen,

724
00:32:34,917 --> 00:32:37,750
en gewoon zeggen, nou ik ben gewoon het maken van
dit ingewikkelder dan het is.

725
00:32:37,750 --> 00:32:42,450
Laten we berekenen de sigma
door middel m en vervolgens toevoegen

726
00:32:42,450 --> 00:32:44,564
in sigma m van minus een?

727
00:32:44,564 --> 00:32:45,980
Nou ja, wat gaat hier gebeuren?

728
00:32:45,980 --> 00:32:47,140
Laten we uitzoomen.

729
00:32:47,140 --> 00:32:52,920
Laten we opnieuw compileren van het programma,
opslaan, opnieuw compileren van het programma,

730
00:32:52,920 --> 00:33:00,450
en dan klaar ./sigma-1 in te zoomen,
voer positief geheel getal neem, 50.

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

732
00:33:02,180 --> 00:33:04,430
Hoeveel van jullie zijn bereid
te bekennen om te zien dat?

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

734
00:33:04,950 --> 00:33:06,690
Dus kan dit gebeuren voor
een aantal redenen,

735
00:33:06,690 --> 00:33:09,148
en eerlijk gezegd deze week zijn we
over om u meer van hen geven.

736
00:33:09,148 --> 00:33:11,780
Maar in dit geval, probeer dan
achteruit redeneren

737
00:33:11,780 --> 00:33:14,430
wat zou hier zijn gebeurd?

738
00:33:14,430 --> 00:33:17,400
Segmentatie fout, we zei vorige
Hiermee wordt bedoeld dat een segment van het geheugen.

739
00:33:17,400 --> 00:33:18,690
Iets ergs gebeurd.

740
00:33:18,690 --> 00:33:21,550
Maar wat was het
mechanisch dat mis ging

741
00:33:21,550 --> 00:33:25,000
hier vanwege mijn verwijdering
van die zogenaamde base case,

742
00:33:25,000 --> 00:33:26,870
waar ik terug een hard-coded waarde?

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

744
00:33:28,970 --> 00:33:30,460
Wat denk je dat er mis ging?

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

746
00:33:31,219 --> 00:33:32,135
>> PUBLIEK: [onverstaanbaar].

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
Goede vraag.

750
00:33:37,550 --> 00:33:39,508
Dus de omvang van het aantal
dat ik een opsomming van

751
00:33:39,508 --> 00:33:41,920
werd zo groot dat het overtrof
de grootte van het geheugen.

752
00:33:41,920 --> 00:33:44,640
Goed idee, maar niet fundamenteel
gaan naar een crash veroorzaken.

753
00:33:44,640 --> 00:33:48,230
Dat zou integer overflow veroorzaken,
waar de bits gewoon omdraaien

754
00:33:48,230 --> 00:33:51,760
en dan verwarren we een echt grote
nummer voor als een negatief getal,

755
00:33:51,760 --> 00:33:53,260
maar die zelf niet leiden tot een crash.

756
00:33:53,260 --> 00:33:55,509
Want aan het eind van de
dag een int is nog steeds 32 bits.

757
00:33:55,509 --> 00:33:57,640
Je gaat niet naar
ongeluk stelen een 33 bit.

758
00:33:57,640 --> 00:33:58,431
Maar een goede gedachte.

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

760
00:33:58,984 --> 00:33:59,900
>> PUBLIEK: [onverstaanbaar].

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

762
00:34:00,551 --> 00:34:02,300
SPEAKER 1: De methode
nooit stopt,

763
00:34:02,300 --> 00:34:06,658
en inderdaad hij zich opnieuw oproepen
en opnieuw en opnieuw en opnieuw

764
00:34:06,658 --> 00:34:08,449
en weer, en geen van
deze functies ooit

765
00:34:08,449 --> 00:34:13,310
afronden omdat hun enige lijn van
code roept zichzelf opnieuw en opnieuw

766
00:34:13,310 --> 00:34:14,219
en weer.

767
00:34:14,219 --> 00:34:16,080
En wat is echt
hier gebeurt, en nu zijn we

768
00:34:16,080 --> 00:34:18,100
kan soort trekken dit picturaal.

769
00:34:18,100 --> 00:34:20,899
Laat me gaan naar een
foto voor slechts een moment.

770
00:34:20,899 --> 00:34:22,940
Dit is een beeld, dat
zal uiteindelijk invulling

771
00:34:22,940 --> 00:34:26,336
in meer detail, van wat er gaande is
binnenkant van het geheugen van uw computer.

772
00:34:26,336 --> 00:34:28,460
En het blijkt dat op
de onderkant van deze foto

773
00:34:28,460 --> 00:34:29,709
is iets genaamd de stapel.

774
00:34:29,709 --> 00:34:31,920
Dit is een stuk van
geheugen, een brok van RAM,

775
00:34:31,920 --> 00:34:33,920
dat is gewoon ieder moment gebruikt
een functie wordt aangeroepen.

776
00:34:33,920 --> 00:34:36,239
Elke keer dat je een programmeur,
noemen een functie,

777
00:34:36,239 --> 00:34:38,860
het besturingssysteem, zoals
Mac OS, Windows of Linux,

778
00:34:38,860 --> 00:34:41,920
grijpt een stelletje bytes, misschien een
paar kilobytes, misschien enkele megabytes

779
00:34:41,920 --> 00:34:44,590
van het geheugen, geeft ze
aan u, en dan laat

780
00:34:44,590 --> 00:34:47,650
u uw functie uitgevoerd met behulp van
wat variabelen die je nodig hebt.

781
00:34:47,650 --> 00:34:50,699
En als je dan nog bellen
functie en andere functie,

782
00:34:50,699 --> 00:34:53,590
u een ander stukje van het geheugen krijgen
en een segment van het geheugen.

783
00:34:53,590 --> 00:34:57,090
>> En inderdaad, indien deze groene trays
uit Annenberg representeren dat het geheugen,

784
00:34:57,090 --> 00:34:59,870
hier is wat er gebeurt de eerste
keer dat je belt functie sigma.

785
00:34:59,870 --> 00:35:04,510
Het is als het zetten van een bak als deze
op wat in eerste instantie een lege stack.

786
00:35:04,510 --> 00:35:07,142
Maar dan, als die lade
noemt zich, om zo te zeggen,

787
00:35:07,142 --> 00:35:08,850
bellen naar een andere instantie
Sigma, dat

788
00:35:08,850 --> 00:35:11,640
als het vragen van het besturingssysteem,
ooh, hebben behoefte aan een beetje meer geheugen,

789
00:35:11,640 --> 00:35:12,520
Geef me dat.

790
00:35:12,520 --> 00:35:14,840
En dan wordt het opgestapeld op bovenop.

791
00:35:14,840 --> 00:35:18,030
Maar wat is de belangrijkste hier is dat
de eerste lade is er nog steeds,

792
00:35:18,030 --> 00:35:20,620
omdat hij aangeroepen deze tweede lade.

793
00:35:20,620 --> 00:35:23,500
Nu ondertussen sigma bel sigma,
dat is hetzelfde als vragen voor meer geheugen.

794
00:35:23,500 --> 00:35:25,830
Wordt opgestapeld op hier.

795
00:35:25,830 --> 00:35:29,350
sigma sigma noemen, dat is een ander
lade die hier wordt opgestapeld op.

796
00:35:29,350 --> 00:35:32,942
En als je blijft dit doen,
uiteindelijk, soort kaart deze visuele

797
00:35:32,942 --> 00:35:35,525
om die kaart, wat er gaat
gebeuren met de stapel bakken?

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

799
00:35:37,480 --> 00:35:41,160
Het gaat om het bedrag niet te boven
van het geheugen van uw computer.

800
00:35:41,160 --> 00:35:45,790
En zodra deze groene bak
boven de horizontale lijn

801
00:35:45,790 --> 00:35:49,410
boven stack en vooral dat woord hoop,
waar we op terug zal komen in de toekomst,

802
00:35:49,410 --> 00:35:50,410
dat is een slechte zaak.

803
00:35:50,410 --> 00:35:52,810
De hoop is een ander
segment van het geheugen,

804
00:35:52,810 --> 00:35:55,190
en als je deze laat
trays stapel en stapel op,

805
00:35:55,190 --> 00:35:57,800
je gaat overtreffen
zelf segment van het geheugen,

806
00:35:57,800 --> 00:36:00,420
en een programma wordt inderdaad gaat crashen.

807
00:36:00,420 --> 00:36:02,930
>> Nu nog even terzijde, dit idee
recursie derhalve

808
00:36:02,930 --> 00:36:06,500
Duidelijk leiden tot problemen, maar
het is niet noodzakelijk een slechte zaak.

809
00:36:06,500 --> 00:36:08,840
Omdat overwegen, na
alle, how-- en misschien

810
00:36:08,840 --> 00:36:11,700
Dit is wel even wennen
om --hoe elegant of hoe eenvoudig

811
00:36:11,700 --> 00:36:14,890
dat de uitvoering van sigma was.

812
00:36:14,890 --> 00:36:17,440
En we gaan niet te gebruiken
recursie al te veel in CS50,

813
00:36:17,440 --> 00:36:20,780
maar in CS51, en echt elke klasse
waar je data structuren te manipuleren

814
00:36:20,780 --> 00:36:23,640
zoals bomen, of stambomen,
dat wat hiërarchie

815
00:36:23,640 --> 00:36:26,000
het is super, super handig.

816
00:36:26,000 --> 00:36:29,750
Nu, als een terzijde, zodat u
als aspirant-informatici

817
00:36:29,750 --> 00:36:33,180
vertrouwd zijn met een aantal van Google's
inside jokes, als je naar Google

818
00:36:33,180 --> 00:36:36,345
en je kijkt wat er de
definitie van, zeg, recursie, in te voeren.

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

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

821
00:36:41,110 --> 00:36:42,670
Even terzijde, ik trok een paar.

822
00:36:42,670 --> 00:36:45,470
Dit was net 10 minuten van
uitstelgedrag vanmorgen.

823
00:36:45,470 --> 00:36:52,890
Als u ook Google "scheef", bericht
door het kantelen van je hoofd slightly--

824
00:36:52,890 --> 00:36:55,120
en dan deze is misschien wel
afschuwelijkste van alle

825
00:36:55,120 --> 00:36:57,286
omdat iemand doorgebracht als
hun dag de uitvoering van dit

826
00:36:57,286 --> 00:36:59,880
enkele jaren ago-- branden.

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

828
00:37:01,140 --> 00:37:04,540
Oh, wait-- dat is een bug.

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

830
00:37:08,410 --> 00:37:11,410
>> Dus lopen op een van de
grootste websites ter wereld

831
00:37:11,410 --> 00:37:13,510
zijn die stomme kleine paaseieren.

832
00:37:13,510 --> 00:37:16,690
Ze consumeren waarschijnlijk
triviale aantal regels code

833
00:37:16,690 --> 00:37:19,280
gewoon zo dat we kunnen hebben
kleine leuke dingen als dat.

834
00:37:19,280 --> 00:37:22,140
Maar in ieder geval nu je krijgt
sommige van die inside jokes.

835
00:37:22,140 --> 00:37:28,330
>> Laten we nu eens een kijkje nemen op een aantal van de
White Lies we al te vertellen van een te late,

836
00:37:28,330 --> 00:37:30,707
en beginnen afpellen
sommige lagen technisch

837
00:37:30,707 --> 00:37:32,790
zodat je echt begrijpt
wat is er aan de hand

838
00:37:32,790 --> 00:37:34,860
en je kunt begrijpen
een aantal van de bedreigingen,

839
00:37:34,860 --> 00:37:38,060
zoals Shellshock, dat
zijn nu begonnen te worden

840
00:37:38,060 --> 00:37:41,110
op de voorgrond van ieders
aandacht, althans in de media.

841
00:37:41,110 --> 00:37:45,810
Dus hier is een erg eenvoudige functie
die terugkeert niets, leegte.

842
00:37:45,810 --> 00:37:46,790
Zijn naam is swap.

843
00:37:46,790 --> 00:37:50,880
Het duurt in twee variabelen
en het geeft niets.

844
00:37:50,880 --> 00:37:52,260
Neemt in a en b.

845
00:37:52,260 --> 00:37:53,337
Dus een korte demo.

846
00:37:53,337 --> 00:37:54,170
We brachten deze up.

847
00:37:54,170 --> 00:37:56,100
We kunnen net zo goed een beetje
breek hier maar voor een moment

848
00:37:56,100 --> 00:37:57,250
en hebben een beetje iets te drinken.

849
00:37:57,250 --> 00:38:00,120
Als iemand het niet erg mee
me hier voor slechts een moment.

850
00:38:00,120 --> 00:38:01,830
Hoe zit je in de kastanjebruin shirt?

851
00:38:01,830 --> 00:38:02,335
Kom maar naar boven.

852
00:38:02,335 --> 00:38:04,060

853
00:38:04,060 --> 00:38:05,260
Gewoon de een vandaag.

854
00:38:05,260 --> 00:38:06,251
Dank je wel, dat wel.

855
00:38:06,251 --> 00:38:08,000
Oke, en we hebben
komen die hier?

856
00:38:08,000 --> 00:38:08,660
Wat is je naam?

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 maar naar boven.

860
00:38:10,370 --> 00:38:11,460

861
00:38:11,460 --> 00:38:13,850
Dus Laura, zeer eenvoudige uitdaging vandaag.

862
00:38:13,850 --> 00:38:14,704

863
00:38:14,704 --> 00:38:15,370
Leuk om yo te ontmoeten.

864
00:38:15,370 --> 00:38:16,410

865
00:38:16,410 --> 00:38:16,910
Oke.

866
00:38:16,910 --> 00:38:21,179
Dus we hebben wat melk hier en
we hebben een aantal sinaasappelsap hier

867
00:38:21,179 --> 00:38:23,345
en een aantal koppen dat we
geleend van Annenberg vandaag.

868
00:38:23,345 --> 00:38:24,178
>> SPEAKER 4: Borrowed.

869
00:38:24,178 --> 00:38:27,240
SPEAKER 1: En gaan om verder te gaan
en geven u een half glas van dit.

870
00:38:27,240 --> 00:38:28,250

871
00:38:28,250 --> 00:38:28,800
Oke.

872
00:38:28,800 --> 00:38:30,750
En wij sturen u de helft geven
een glas van de melk.

873
00:38:30,750 --> 00:38:31,905

874
00:38:31,905 --> 00:38:35,890
Oh, en het gewoon zo dat je kunt
herinneren wat dit was,

875
00:38:35,890 --> 00:38:38,860
Ik herinnerde me te brengen
dit op en op vandaag.

876
00:38:38,860 --> 00:38:42,030

877
00:38:42,030 --> 00:38:42,530
Oke.

878
00:38:42,530 --> 00:38:45,470
Als je het niet erg, laten we eens kijken, we
kunt ze over je eigen bril

879
00:38:45,470 --> 00:38:46,560
als je wilt.

880
00:38:46,560 --> 00:38:48,710
Dit zal de wereld vanuit de ogen van Laura zijn.

881
00:38:48,710 --> 00:38:49,210
Oke.

882
00:38:49,210 --> 00:38:53,820
Dus je doel, gegeven twee kopjes
vloeibare hier, melk en jus d'orange,

883
00:38:53,820 --> 00:38:58,370
is wisselen de twee inhoud, zodat de
sinaasappelsap gaat in de melk cup

884
00:38:58,370 --> 00:39:00,710
en de melk gaat in
het sinaasappelsap cup.

885
00:39:00,710 --> 00:39:02,359
>> SPEAKER 4: Krijg ik nog een kopje?

886
00:39:02,359 --> 00:39:05,650
SPEAKER 1: Ik ben zo blij dat je vroeg, dat wel
het zou veel beter materiaal zijn geweest

887
00:39:05,650 --> 00:39:06,710
als je het niet had gevraagd.

888
00:39:06,710 --> 00:39:10,620
Maar ja, we kunnen u een derde te bieden
kopje dat is natuurlijk leeg.

889
00:39:10,620 --> 00:39:11,120
Oke.

890
00:39:11,120 --> 00:39:12,300
Zo wisselen de inhoud daar.

891
00:39:12,300 --> 00:39:16,100

892
00:39:16,100 --> 00:39:17,050
Erg leuk.

893
00:39:17,050 --> 00:39:20,390

894
00:39:20,390 --> 00:39:21,305
Zeer goed.

895
00:39:21,305 --> 00:39:23,121

896
00:39:23,121 --> 00:39:24,745
Je doet dit opvallend voorzichtig.

897
00:39:24,745 --> 00:39:26,970

898
00:39:26,970 --> 00:39:28,655
En stap drie.

899
00:39:28,655 --> 00:39:30,390

900
00:39:30,390 --> 00:39:31,350
Oke.

901
00:39:31,350 --> 00:39:31,930
Excellent.

902
00:39:31,930 --> 00:39:33,930
Een groot applaus
zou goed zijn voor Laura zijn.

903
00:39:33,930 --> 00:39:36,500

904
00:39:36,500 --> 00:39:37,000
Oke.

905
00:39:37,000 --> 00:39:40,790
We hebben een klein afscheidscadeau
voor u, maar laat ik deze nemen.

906
00:39:40,790 --> 00:39:42,620
Dank je wel.

907
00:39:42,620 --> 00:39:46,170
Dus een simpel voorbeeld, maar,
om aan te tonen dat als je dat doet

908
00:39:46,170 --> 00:39:48,300
willen de inhoud te wisselen
van twee containers,

909
00:39:48,300 --> 00:39:52,360
of laten we noemen hen variabelen,
u een aantal tijdelijke opslag nodig

910
00:39:52,360 --> 00:39:56,710
een van de inhoud fase in zo
dat je eigenlijk kan doen de swap.

911
00:39:56,710 --> 00:40:01,790
Dus inderdaad, deze bron code hier in
C representatief is precies dat.

912
00:40:01,790 --> 00:40:06,340
Als het sinaasappelsap was een en de melk
was b, en we wilden wisselen van de twee,

913
00:40:06,340 --> 00:40:08,990
je zou iets creatiefs te proberen
door gieten in elkaar,

914
00:40:08,990 --> 00:40:11,031
maar dat zou waarschijnlijk niet
end bijzonder goed.

915
00:40:11,031 --> 00:40:15,260
En dus hebben we een derde beker, call gebruiken
het tmp, T-M-P volgens afspraak,

916
00:40:15,260 --> 00:40:19,370
en doe de inhoud van het
PB in dat, dan is ruilen een kopje,

917
00:40:19,370 --> 00:40:22,610
zet dan de PB in de
originele beker, waardoor

918
00:40:22,610 --> 00:40:25,320
bereiken, precies zoals
Laura deed, de swap.

919
00:40:25,320 --> 00:40:26,850
>> Dus laten we het doen precies dat.

920
00:40:26,850 --> 00:40:30,110
Laat me gaan en openen
van een voorbeeld dat

921
00:40:30,110 --> 00:40:32,720
eigenlijk heet "geen
wisselen, "want dit is niet

922
00:40:32,720 --> 00:40:36,180
zo eenvoudig gedaan als je zou denken.

923
00:40:36,180 --> 00:40:41,190
Dus in dit programma, merken dat
Ik gebruik stdio.h, onze oude vriend.

924
00:40:41,190 --> 00:40:43,130
Ik heb het prototype
voor swap daarboven, die

925
00:40:43,130 --> 00:40:45,450
betekent dat de uitvoering van
waarschijnlijk beneden,

926
00:40:45,450 --> 00:40:48,050
en laten we zien wat deze belangrijkste
programma gaat doen voor mij.

927
00:40:48,050 --> 00:40:52,020
Ik voor het eerst verklaar int x krijgt
een, en int y krijgt twee.

928
00:40:52,020 --> 00:40:54,930
Dus denk aan die als PB
en melk, respectievelijk.

929
00:40:54,930 --> 00:40:57,100
En dan heb ik gewoon een
printf zeggen x is dit

930
00:40:57,100 --> 00:41:00,120
en y is dit, zodat ik kan
visueel te zien wat er gaande is.

931
00:41:00,120 --> 00:41:03,810
Dan heb ik printf claimen
dat ik het omwisselen van de twee,

932
00:41:03,810 --> 00:41:07,100
en vervolgens afdrukken ik uit een
beweren dat ze verwisseld,

933
00:41:07,100 --> 00:41:09,300
en print ik x en y weer.

934
00:41:09,300 --> 00:41:13,010
Dus hier in swap is
precies wat Laura deed,

935
00:41:13,010 --> 00:41:16,240
en precies wat we zagen op
het scherm een ​​moment geleden.

936
00:41:16,240 --> 00:41:19,380
>> Dus laten we verder gaan en
erg teleurgesteld.

937
00:41:19,380 --> 00:41:24,690
Maak geen swap, en lopen geen swap,
inzoomen op de output hier.

938
00:41:24,690 --> 00:41:28,320
Voer x is 1, y 2, swapping verwisseld.

939
00:41:28,320 --> 00:41:32,700
x is nog 1 en y is momenteel nog 2.

940
00:41:32,700 --> 00:41:37,630
Dus hoewel, eerlijk gezegd, dit ziet er
precies willen, zij het meer technisch,

941
00:41:37,630 --> 00:41:40,730
wat Laura deed, leek niet te werken.

942
00:41:40,730 --> 00:41:42,130
Dus waarom is dat?

943
00:41:42,130 --> 00:41:46,630
Nou, het blijkt dat wanneer
we schrijven een programma als dit

944
00:41:46,630 --> 00:41:51,590
dat is zowel de belangrijkste, benadrukt hier,
en dan een andere functie, zoals swap,

945
00:41:51,590 --> 00:41:54,230
hier uitgelicht, die
roept hij, de wereld

946
00:41:54,230 --> 00:41:57,030
ziet er een beetje iets als
deze laden een moment geleden.

947
00:41:57,030 --> 00:42:00,440
Als belangrijkste eerste wordt genoemd,
dat is hetzelfde als vragen besturingssysteem

948
00:42:00,440 --> 00:42:04,030
voor een beetje van het geheugen voor elke lokale
variabelen zoals x en y die de belangrijkste is,

949
00:42:04,030 --> 00:42:05,660
en ze eindigen daar.

950
00:42:05,660 --> 00:42:10,920
Maar als belangrijkste gesprekken wisselen, en de belangrijkste
gaat om twee argumenten, a en b wisselen,

951
00:42:10,920 --> 00:42:16,410
jus d'orange en melk, het is niet alsof
het overhandigen van het sinaasappelsap en de melk

952
00:42:16,410 --> 00:42:17,500
Laura.

953
00:42:17,500 --> 00:42:21,300
Wat een computer doet, is het
passeert exemplaren van het jus d'orange

954
00:42:21,300 --> 00:42:27,110
en kopieën van de melk aan Laura, zodat
wat is uiteindelijk de binnenkant van deze lade

955
00:42:27,110 --> 00:42:32,510
is de waarde een en twee, of PB
en melk, maar kopieën daarvan,

956
00:42:32,510 --> 00:42:34,790
zodat op dit punt
in het verhaal, is er

957
00:42:34,790 --> 00:42:36,930
is PB en melk in elk van deze schalen.

958
00:42:36,930 --> 00:42:39,260
Er is een een en een twee
in elk van deze trays,

959
00:42:39,260 --> 00:42:41,720
en de swap-functie is inderdaad werkt.

960
00:42:41,720 --> 00:42:46,090
Het is binnenin ruilt ze
van de tweede bovenste lade,

961
00:42:46,090 --> 00:42:48,147
maar dat swapping heeft geen invloed.

962
00:42:48,147 --> 00:42:49,980
En op basis van slechts enkele
basisprincipe we hebben

963
00:42:49,980 --> 00:42:52,970
gesproken over vroeger, en inderdaad
slechts een paar minuten geleden, wat

964
00:42:52,970 --> 00:42:58,770
zou kunnen verklaren waarom het veranderen
a en b binnenkant van swap

965
00:42:58,770 --> 00:43:05,560
heeft geen effect op x en y, hoewel
Ik passeerde x en y om de swap-functie.

966
00:43:05,560 --> 00:43:08,750
Wat is hier het sleutelwoord dat
misschien simplistisch uit te leggen?

967
00:43:08,750 --> 00:43:11,250

968
00:43:11,250 --> 00:43:12,627
Ik denk dat ik hoorde het hier?

969
00:43:12,627 --> 00:43:13,335
PUBLIEK: Return.

970
00:43:13,335 --> 00:43:14,085
SPEAKER 1: Return?

971
00:43:14,085 --> 00:43:14,590
Niet meer terug.

972
00:43:14,590 --> 00:43:15,895
Laten we gaan met een andere.

973
00:43:15,895 --> 00:43:16,395
Wat is dat?

974
00:43:16,395 --> 00:43:17,080
>> PUBLIEK: [onverstaanbaar].

975
00:43:17,080 --> 00:43:20,000
>> SPEAKER 1: OK, dus return-- we konden
maken rendement werk in het verhaal,

976
00:43:20,000 --> 00:43:21,914
maar er is een nog eenvoudiger verklaring.

977
00:43:21,914 --> 00:43:22,580
PUBLIEK: Scope.

978
00:43:22,580 --> 00:43:23,288
SPEAKER 1: Scope.

979
00:43:23,288 --> 00:43:24,300
Ik zal strekking te nemen.

980
00:43:24,300 --> 00:43:27,290
Dus scope, herinneren waar
onze x en y aangegeven.

981
00:43:27,290 --> 00:43:30,840
Ze zijn binnen verklaard
van de belangrijkste hier naar boven.

982
00:43:30,840 --> 00:43:33,200
a en b, ondertussen zijn
effectief verklaard

983
00:43:33,200 --> 00:43:35,930
binnenkant van de swap, niet helemaal in
de accolades maar nog steeds

984
00:43:35,930 --> 00:43:37,690
in de algemene ruimte van de swap.

985
00:43:37,690 --> 00:43:40,560
En inderdaad, a en b
bestaan ​​alleen op deze lade

986
00:43:40,560 --> 00:43:44,850
van Annenberg, deze
tweede stuk code.

987
00:43:44,850 --> 00:43:49,500
Dus we inderdaad het veranderen van de kopie, maar
dat is helemaal niet zo behulpzaam.

988
00:43:49,500 --> 00:43:52,190
>> Dus laten we eens een kijkje nemen op
deze iets lager niveau.

989
00:43:52,190 --> 00:43:55,430
Ik ga om terug te gaan naar
de Source Directory,

990
00:43:55,430 --> 00:43:58,330
en ik ga eerst
opnieuw in hier, en net

991
00:43:58,330 --> 00:44:02,290
om te bevestigen dat ik in deze
groter terminal venster,

992
00:44:02,290 --> 00:44:04,430
het programma is nog steeds gedragen als dat.

993
00:44:04,430 --> 00:44:06,840
Stel nu dat deze
is geen opzet.

994
00:44:06,840 --> 00:44:10,090
Het is duidelijk dat ik wilde swap aan
werk, dus het voelt als een bug.

995
00:44:10,090 --> 00:44:12,780
Nu kon ik beginnen met het toevoegen van een
Veel printf om mijn code,

996
00:44:12,780 --> 00:44:16,010
printen x hier, y dan
hier, een meer dan hier, b dan hier.

997
00:44:16,010 --> 00:44:18,220
Maar eerlijk gezegd, dat is waarschijnlijk wat
je hebt gedaan voor een paar weken

998
00:44:18,220 --> 00:44:20,190
nu, in het kantoor uren
en thuis bij het werken

999
00:44:20,190 --> 00:44:22,150
Op psets proberen om wat bugs te vinden.

1000
00:44:22,150 --> 00:44:25,560
Maar je zult zien, als je dat nog niet hebt,
dat probleem set drie introduceert u

1001
00:44:25,560 --> 00:44:31,630
een commando genaamd GDB,
waar GDB, GNU debugger,

1002
00:44:31,630 --> 00:44:34,040
heeft zelf een hele hoop
functies die daadwerkelijk kan

1003
00:44:34,040 --> 00:44:38,160
laat ons situaties begrijpen
als dit, maar meer meeslepend,

1004
00:44:38,160 --> 00:44:39,940
problemen op te lossen en vinden van bugs.

1005
00:44:39,940 --> 00:44:40,940
Dus ik ga dit doen.

1006
00:44:40,940 --> 00:44:44,770
In plaats van ./noswap, ik ben in plaats
gaat GDB ./noswap lopen.

1007
00:44:44,770 --> 00:44:47,410

1008
00:44:47,410 --> 00:44:51,200
Met andere woorden, ik ga lopen mijn
programma niet in Bash, onze nieuwe vriend

1009
00:44:51,200 --> 00:44:51,850
vandaag.

1010
00:44:51,850 --> 00:44:53,970
Ik ga lopen mijn
programma noswap binnenkant

1011
00:44:53,970 --> 00:44:56,900
van deze andere programma genaamd
GDB, een debugger die

1012
00:44:56,900 --> 00:45:01,035
is een programma dat is ontworpen om te helpen
Jullie mensen te vinden en te verwijderen bugs.

1013
00:45:01,035 --> 00:45:03,410
Dus als ik hit Run hier, er is
een gruwelijke hoeveelheid tekst

1014
00:45:03,410 --> 00:45:04,868
dat je echt nooit meer te lezen.

1015
00:45:04,868 --> 00:45:07,290
Het is in wezen een afleiding
vanaf de prompt, waar

1016
00:45:07,290 --> 00:45:10,030
Ik ga naar Control-L hit
om op te staan ​​aan de top daar.

1017
00:45:10,030 --> 00:45:11,800
Dit is de GDB prompt.

1018
00:45:11,800 --> 00:45:15,550
Als ik wil dit programma draaien nu,
als deze kleine spiekbriefje op vandaag

1019
00:45:15,550 --> 00:45:21,860
slide suggereert, Run is de eerste
beveelt dat we bedoeld om te introduceren.

1020
00:45:21,860 --> 00:45:25,150
En ik ga gewoon om te typen
aanloop hier binnenkant van GDB,

1021
00:45:25,150 --> 00:45:26,811
en inderdaad het liep mijn programma.

1022
00:45:26,811 --> 00:45:29,310
Nu is er een aantal extra
uitgangen van het scherm als dit,

1023
00:45:29,310 --> 00:45:31,910
maar dat is GDB gewoon anale
en vertel ons wat er aan de hand.

1024
00:45:31,910 --> 00:45:34,451
Je hoeft niet echt zorgen te maken
over deze gegevens op dit moment.

1025
00:45:34,451 --> 00:45:36,890
Maar wat is echt cool over
GDB, als ik dit again--

1026
00:45:36,890 --> 00:45:42,100
Controle-L wist de screen-- laat me gaan
gang en het type "break belangrijkste," aldus,

1027
00:45:42,100 --> 00:45:45,743
als ik druk op Enter, het instellen van wat is
riep een breekpunt bij noswap.c,

1028
00:45:45,743 --> 00:45:51,270
lijn 16, waar GDB
bedacht mijn programma eigenlijk

1029
00:45:51,270 --> 00:45:53,070
is, mijn functie eigenlijk is.

1030
00:45:53,070 --> 00:45:55,070
Dit zullen we negeren voor nu
maar dat is het adres

1031
00:45:55,070 --> 00:45:57,310
in geheugen dat speciaal van deze functie.

1032
00:45:57,310 --> 00:46:00,240
Dus als ik nu typ Uitvoeren,
merken wat is cool hier.

1033
00:46:00,240 --> 00:46:05,650
Mijn programma breekt op de lijn I
vertelde GDB om uitvoering te pauzeren bij.

1034
00:46:05,650 --> 00:46:09,850
Dus ik hoef niet te veranderen nu mijn code,
voeg wat printf's, opnieuw compileren, herhaling

1035
00:46:09,850 --> 00:46:13,300
het, veranderen, voeg wat printf's,
opslaan, opnieuw compileren, voer het uit.

1036
00:46:13,300 --> 00:46:18,100
Ik kan gewoon lopen via mijn programma
stap voor stap voor stap menselijke snelheid,

1037
00:46:18,100 --> 00:46:20,880
niet op Intel-inside soort snelheid.

1038
00:46:20,880 --> 00:46:24,580
>> Dus nu zien deze lijn
verschijnt hier, en als ik terug te gaan

1039
00:46:24,580 --> 00:46:27,800
om mijn programma in gedit,
merken dat dat eigenlijk

1040
00:46:27,800 --> 00:46:29,280
de eerste regel van de code.

1041
00:46:29,280 --> 00:46:31,240
Er is lijn 16 in gedit.

1042
00:46:31,240 --> 00:46:34,610
Er is lijn 16 binnen GDB, en zelfs
hoewel dit zwart-wit-interface

1043
00:46:34,610 --> 00:46:37,760
is lang niet zo gebruiksvriendelijk
vriendelijke, betekent dit

1044
00:46:37,760 --> 00:46:41,680
dat leiding 16 niet werd uitgevoerd
nog niet, maar het is over te zijn.

1045
00:46:41,680 --> 00:46:46,220
Dus inderdaad, als ik het type afdruk
x, niet printf, alleen printen x,

1046
00:46:46,220 --> 00:46:50,730
Ik krijg een aantal nep waarde er van nul,
omdat x is nog niet geïnitialiseerd.

1047
00:46:50,730 --> 00:46:54,760
Dus ik ga volgende te typen, of, als u
wenst te worden fancy, gewoon n voor de volgende.

1048
00:46:54,760 --> 00:46:59,090
Maar toen ik het type naast gaan, nu
merkt het op gaat om lijn 17.

1049
00:46:59,090 --> 00:47:02,840
Dus logisch, als ik heb uitgevoerd
lijn 16 en ik nu typ druk x,

1050
00:47:02,840 --> 00:47:03,640
wat moet ik zien?

1051
00:47:03,640 --> 00:47:04,970

1052
00:47:04,970 --> 00:47:05,520
Een.

1053
00:47:05,520 --> 00:47:07,820
>> En nu is dit weliswaar verwarrend.

1054
00:47:07,820 --> 00:47:11,260
$ 2 is gewoon een mooie manier om, als je
later wilt verwijzen naar die waarde,

1055
00:47:11,260 --> 00:47:12,510
je kunt zeggen "dollarteken twee."

1056
00:47:12,510 --> 00:47:13,480
Het is als een terugverwijzing.

1057
00:47:13,480 --> 00:47:14,570
Maar voor nu, gewoon negeren.

1058
00:47:14,570 --> 00:47:17,070
Wat interessant is, is wat er
aan de rechterkant van het gelijkteken.

1059
00:47:17,070 --> 00:47:21,000
En nu als ik volgende weer typen
en af ​​te drukken y, moet ik zie 2.

1060
00:47:21,000 --> 00:47:23,870
Ik kan nu ook afdrukken
x weer, en eerlijk gezegd,

1061
00:47:23,870 --> 00:47:27,130
als ik word een beetje in de war over
waar ik ben, kan ik de lijst voor de lijst typt

1062
00:47:27,130 --> 00:47:30,590
en gewoon zien wat context rond
het punt dat ik ben eigenlijk op.

1063
00:47:30,590 --> 00:47:35,180
En nu ik kan typen
next, en er is x 1.

1064
00:47:35,180 --> 00:47:36,300
Typ nu ik volgende.

1065
00:47:36,300 --> 00:47:37,710
Oh, y 2.

1066
00:47:37,710 --> 00:47:40,750
En nogmaals, het is verwarrend,
omdat de uitgang GDB's

1067
00:47:40,750 --> 00:47:43,044
wordt vermengd met mijn eigen vermogen.

1068
00:47:43,044 --> 00:47:45,710
Maar als je in het achterhoofd te houden, door
blik heen en weer op uw code

1069
00:47:45,710 --> 00:47:47,740
of buiten het leggen het kant
elkaar misschien, zult u

1070
00:47:47,740 --> 00:47:51,020
zie dat echt ik ben gewoon
het doorlopen van mijn programma.

1071
00:47:51,020 --> 00:47:54,620
>> Maar let op wat er daarna gebeurt, letterlijk.

1072
00:47:54,620 --> 00:47:56,380
Hier is lijn 22.

1073
00:47:56,380 --> 00:48:01,315
Laat me gaan er overheen, waardoor bewegen op
tot 23, en als ik afdrukken x nu, nog een.

1074
00:48:01,315 --> 00:48:03,890
En als ik afdrukken y nu, nog een.

1075
00:48:03,890 --> 00:48:05,820
Dit is geen nuttige oefening.

1076
00:48:05,820 --> 00:48:07,450
Dus laten we dit opnieuw te doen.

1077
00:48:07,450 --> 00:48:10,069
Laat me terug te gaan naar de
top en het type run weer.

1078
00:48:10,069 --> 00:48:12,110
En het is te zeggen dat de programma
dat is waarin fouten worden opgespoord

1079
00:48:12,110 --> 00:48:14,109
is al begonnen,
gestart vanaf het begin.

1080
00:48:14,109 --> 00:48:15,420
Ja, laten we dit opnieuw doen.

1081
00:48:15,420 --> 00:48:22,000
En deze keer laten we het nu doen,
next, next, next, next,

1082
00:48:22,000 --> 00:48:24,180
maar nu dingen interessant.

1083
00:48:24,180 --> 00:48:27,760
Nu wil ik de stap naar
swap, dus ik typ niet naast.

1084
00:48:27,760 --> 00:48:34,380
Ik typ stap, en nu merken
heeft mij sprong naar noswap.c lijn 33.

1085
00:48:34,380 --> 00:48:37,240
Als ik terug naar gedit, wat is lijn 33?

1086
00:48:37,240 --> 00:48:40,500
Dat is de eerste werkelijke
regel code binnenkant van swap.

1087
00:48:40,500 --> 00:48:44,150
Dat is leuk, want nu kan ik
soort rondneuzen en nieuwsgierig

1088
00:48:44,150 --> 00:48:46,052
over wat er gaande is echt daar.

1089
00:48:46,052 --> 00:48:46,760
Laat me printen 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
Waarom heeft tmp hebben een aantal
gek, nep garbage waarde?

1093
00:48:51,438 --> 00:48:54,579

1094
00:48:54,579 --> 00:48:56,120
Publiek: Het is niet geïnitialiseerd.

1095
00:48:56,120 --> 00:48:57,150
SPEAKER 1: Het is niet geïnitialiseerd.

1096
00:48:57,150 --> 00:49:00,270
En inderdaad, als je een programma uit te voeren,
je krijgt een hele hoop geheugen

1097
00:49:00,270 --> 00:49:03,392
door het besturingssysteem, maar u
hebben geen waarden geïnitialiseerd,

1098
00:49:03,392 --> 00:49:05,600
dus wat stukjes je bent
hier te zien, ook al is het

1099
00:49:05,600 --> 00:49:07,770
deze gekke grote negatieve
nummer, betekent alleen

1100
00:49:07,770 --> 00:49:10,750
dat dat zijn de overblijfselen van
aantal eerdere gebruik van die RAM,

1101
00:49:10,750 --> 00:49:13,050
ook al heb ik niet
mezelf nog nodig had.

1102
00:49:13,050 --> 00:49:17,086
Dus nu ga ik verder en het type te gaan
naast, en als ik nu typ druk tmp

1103
00:49:17,086 --> 00:49:17,835
wat moet ik zien?

1104
00:49:17,835 --> 00:49:19,570

1105
00:49:19,570 --> 00:49:23,360
Ongeacht de waarde van een was,
a is het eerste argument, net

1106
00:49:23,360 --> 00:49:25,550
als x is de eerste
ding wordt doorgegeven in,

1107
00:49:25,550 --> 00:49:30,450
zodat een en x moet hetzelfde zijn,
dus afdrukken tmp moet me nog een af ​​te drukken.

1108
00:49:30,450 --> 00:49:36,360
>> Dus wat zie je in probleem set
drie is een tutorial van soorten op GDB,

1109
00:49:36,360 --> 00:49:40,020
maar beseffen dat dit het begin is
van een blik op een instrument dat daadwerkelijk zal

1110
00:49:40,020 --> 00:49:42,774
u te helpen problemen op te lossen
dus veel effectiever.

1111
00:49:42,774 --> 00:49:44,690
Wat we uiteindelijk
gaan doen op woensdag

1112
00:49:44,690 --> 00:49:48,180
is beginnen te schillen terug een paar lagen
en verwijder enkele zijwieltjes.

1113
00:49:48,180 --> 00:49:50,496
Dat ding heet string die
we hebben gebruikt voor enige tijd,

1114
00:49:50,496 --> 00:49:53,370
we gaan langzaam dat weg te nemen
van u en beginnen te praten over

1115
00:49:53,370 --> 00:49:55,725
iets meer esoterisch
bekend als char *,

1116
00:49:55,725 --> 00:49:59,550
maar we gaan deze mooie doen en
eerst zachtjes terwijl pointers,

1117
00:49:59,550 --> 00:50:02,730
als ze worden opgeroepen, kunnen sommige doen
zeer slechte dingen als misbruikt,

1118
00:50:02,730 --> 00:50:06,040
door te kijken naar een beetje claymation uit
onze vriend Nick Parlante van Stanford

1119
00:50:06,040 --> 00:50:09,670
Universiteit, een professor in de computer
wetenschap die samen dit voorbeeld zetten

1120
00:50:09,670 --> 00:50:11,075
van wat er deze woensdag komen.

1121
00:50:11,075 --> 00:50:12,196

1122
00:50:12,196 --> 00:50:13,400
>> [VIDEO AFSPELEN]

1123
00:50:13,400 --> 00:50:13,900
He, Binky.

1124
00:50:13,900 --> 00:50:14,930

1125
00:50:14,930 --> 00:50:15,780
Wakker worden.

1126
00:50:15,780 --> 00:50:17,240
Het is tijd voor pointer plezier.

1127
00:50:17,240 --> 00:50:18,260

1128
00:50:18,260 --> 00:50:19,350
>> Wat is dat?

1129
00:50:19,350 --> 00:50:21,150
Meer informatie over pointers?

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 VIDEO AFSPELEN]

1133
00:50:23,730 --> 00:50:25,396
SPEAKER 1: Dat wacht u op woensdag.

1134
00:50:25,396 --> 00:50:26,440
We zullen je dan zien.

1135
00:50:26,440 --> 00:50:27,106
[VIDEO AFSPELEN]

1136
00:50:27,106 --> 00:50:30,420
-En Nu, Deep Thoughts,
door Daven Farnham.

1137
00:50:30,420 --> 00:50:33,980

1138
00:50:33,980 --> 00:50:35,900
>> Waarom leren we C?

1139
00:50:35,900 --> 00:50:36,785
Waarom niet A +?

1140
00:50:36,785 --> 00:50:38,550

1141
00:50:38,550 --> 00:50:40,910
>> [Lachen]

1142
00:50:40,910 --> 00:50:42,160
>> [END VIDEO AFSPELEN]