1
00:00:00,000 --> 00:00:12,040
>> [REPRODUCCIÓ DE MÚSICA]

2
00:00:12,040 --> 00:00:16,460
>> ALTAVEU 1: Molt bé, això és CS50,
i aquest és el començament de la setmana quatre,

3
00:00:16,460 --> 00:00:20,420
i com vostè pot haver sentit o
llegir, el món ha estat arribant al final.

4
00:00:20,420 --> 00:00:23,520
El anar per tot l'internet
ha estat el coneixement i la consciència

5
00:00:23,520 --> 00:00:27,100
d'un error en un programa, una
llenguatge de programació anomenat Bash.

6
00:00:27,100 --> 00:00:32,729
Aquest ha estat marcat meravellosament
com Shellshock, o la porta Bash,

7
00:00:32,729 --> 00:00:35,485
però articles com aquests
no han estat infreqüents.

8
00:00:35,485 --> 00:00:38,807
I, de fet, molts d'ells porten
records posteriors de Heartbleed,

9
00:00:38,807 --> 00:00:41,640
que vostè pot haver notat en el
comprimir la primavera passada, que

10
00:00:41,640 --> 00:00:43,980
ser igualment bastant dramàtic.

11
00:00:43,980 --> 00:00:47,110
Ara, per a aquells de vostès aquí
avui, quants de vostès tenen,

12
00:00:47,110 --> 00:00:50,330
encara que no entén el que
és tot sobre, sentit parlar de Shellshock?

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

14
00:00:51,370 --> 00:00:54,245
Molt bé, i quants de vostès
tenir equips que són vulnerables?

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

16
00:00:55,680 --> 00:01:00,250
Acceptar, ha d'haver molt, molt més mans
fins ara, per raons que veurem.

17
00:01:00,250 --> 00:01:02,580
>> Fem una ullada al que
estat succeint en els mitjans de comunicació

18
00:01:02,580 --> 00:01:05,304
i després explicar-ho una mica
aquí per a nosaltres tècnicament.

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

20
00:01:07,670 --> 00:01:11,250
>> ALTAVEU 2: Els experts en seguretat tenen
advertit que una greu falla podria

21
00:01:11,250 --> 00:01:15,650
estar a punt d'afectar a centenars de
milions d'usuaris d'Internet del món.

22
00:01:15,650 --> 00:01:20,600
Llavors, què és exactament l'error que ha estat
anomenat Shellshock, i el que fa?

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

24
00:01:23,720 --> 00:01:28,910
Bé, Shellshock també es coneix com el
Bug Bash, el programari que explota.

25
00:01:28,910 --> 00:01:33,230
Els hackers utilitzen virus per escanejar vulnerables
sistemes que Linux i Unix

26
00:01:33,230 --> 00:01:36,300
sistemes operatius i després infectar ells.

27
00:01:36,300 --> 00:01:38,730
Bash és un shell de línia d'ordres.

28
00:01:38,730 --> 00:01:43,460
Això permet que els usuaris dels comandos d'edició per llançar
programes i característiques en el programari

29
00:01:43,460 --> 00:01:45,250
per la introducció de text.

30
00:01:45,250 --> 00:01:49,980
S'utilitza normalment pels programadors, i
no ha d'estar obert a la resta del món,

31
00:01:49,980 --> 00:01:51,590
encara Shellshock canvia això.

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

33
00:01:54,160 --> 00:01:57,910
>> Bé, worringly, alguns analistes
adverteixen que podria ser una amenaça més gran,

34
00:01:57,910 --> 00:02:01,580
perquè Shellshock permet completa
el control d'una màquina infectada,

35
00:02:01,580 --> 00:02:06,030
mentre que només es permet Heartbleed
hackers per espiar en ordinadors.

36
00:02:06,030 --> 00:02:09,130
És tan greu, és
ha classificat octubre 1 sobre 10

37
00:02:09,130 --> 00:02:11,900
de la gravetat per la National
Base de dades de vulnerabilitats.

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

39
00:02:15,530 --> 00:02:20,015
2.3 de tots els servidors web estan en
risc, incloent alguns ordinadors Mac.

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

41
00:02:22,760 --> 00:02:25,600
Bé, assegureu-vos que
apedaçar els seus sistemes ara.

42
00:02:25,600 --> 00:02:29,330
Qualsevol que allotjar un lloc web en funcionament
els sistemes operatius afectats

43
00:02:29,330 --> 00:02:31,800
ha de prendre mesures tan aviat com sigui possible.

44
00:02:31,800 --> 00:02:35,390
Qualsevol que pugui permetre ha de mirar
a la seva aplicació de monitorització i web

45
00:02:35,390 --> 00:02:37,355
tallafocs a tenir en compte qualsevol atac.

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

47
00:02:39,979 --> 00:02:41,770
ALTAVEU 3: El pitjor
que podria passar és

48
00:02:41,770 --> 00:02:45,080
que algú escriuria codi que
aniria automàticament i escanejar

49
00:02:45,080 --> 00:02:48,280
internet i afectaria
tots aquests equips.

50
00:02:48,280 --> 00:02:50,710
I una vegada que ho fan, així,
el pitjor que podien fer

51
00:02:50,710 --> 00:02:53,300
s'acaba d'esborrar tot,
o tancar els llocs de sota.

52
00:02:53,300 --> 00:02:55,360
Així que podríem veure el dany
des d'aquest punt de vista,

53
00:02:55,360 --> 00:02:58,300
on hauríem persones malicioses
que acaba de decidir a causar estralls

54
00:02:58,300 --> 00:03:02,534
portant sistemes avall o eliminar
arxius, i coses com aquestes.

55
00:03:02,534 --> 00:03:05,200
ALTAVEU 2: Alguns diuen que aquesta és una
de les més difícils de mesurar

56
00:03:05,200 --> 00:03:08,080
errors en anys, i que
pot portar setmanes o fins i tot

57
00:03:08,080 --> 00:03:10,820
mesos per determinar el seu impacte final.

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

59
00:03:12,180 --> 00:03:15,560
>> ALTAVEU 1: Així que tot això és cert,
però el curiós és que gairebé tots

60
00:03:15,560 --> 00:03:18,330
de les imatges que acabes de veure,
excepte potser el teclat,

61
00:03:18,330 --> 00:03:20,930
no té res a veure amb
l'error absolut.

62
00:03:20,930 --> 00:03:23,960
Servidors i filferros i així successivament,
És una mena de tangencialment relacionat,

63
00:03:23,960 --> 00:03:27,410
però en el fons és en realitat bastant
familiaritzat el que està passant aquí.

64
00:03:27,410 --> 00:03:30,050
De fet, deixa anar a
nostre aparell CS50.

65
00:03:30,050 --> 00:03:32,910
Déjame anar per davant i maximitzar
la finestra de terminal aquí.

66
00:03:32,910 --> 00:03:36,020
I vostès han estat utilitzant aquest,
o la versió incorporada de la mateixa,

67
00:03:36,020 --> 00:03:39,460
en gedit per escriure programes,
escriure ordres, i així successivament,

68
00:03:39,460 --> 00:03:43,690
i això és en realitat, i té
estat durant setmanes, Bash, B-A-S-H.

69
00:03:43,690 --> 00:03:46,890
Aquest és el Bourne-again shell,
que és només una forma elegant de dir,

70
00:03:46,890 --> 00:03:50,220
aquest és un programa que té un
parpelleig ràpid, eficaç,

71
00:03:50,220 --> 00:03:51,970
que se senti allà esperant
per a l'entrada per a vostè.

72
00:03:51,970 --> 00:03:53,920
I és la comanda
interfície de línia a través del qual

73
00:03:53,920 --> 00:03:57,650
que vostès han estat executant ordres i
en última instància, la compilació i després corrent

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

75
00:03:58,400 --> 00:04:01,320
>> Però Bash és també una programació
idioma en el següent sentit.

76
00:04:01,320 --> 00:04:05,460
Vostè sap que hi ha ordres com
cd i ls i també Clang i altres,

77
00:04:05,460 --> 00:04:09,580
però vostè pot definir els seus propis comandaments
mitjançant la implementació d'ells en Bash.

78
00:04:09,580 --> 00:04:11,420
Ara no anem a
entrar en gran detall

79
00:04:11,420 --> 00:04:16,089
com per colpejar el llenguatge de programació, però
Sabem, per exemple, que en aquest moment,

80
00:04:16,089 --> 00:04:17,607
no hi ha ordre anomenat "hola."

81
00:04:17,607 --> 00:04:19,440
Per tant, es pot trobar a
dos paquets.

82
00:04:19,440 --> 00:04:20,856
No està instal · lat en el meu equip.

83
00:04:20,856 --> 00:04:21,870
Pregunti al seu administrador.

84
00:04:21,870 --> 00:04:26,030
Però si jo vull que hi hagi un programa
anomenat "hola" en Bash o en el meu ràpida,

85
00:04:26,030 --> 00:04:30,810
De fet, puc utilitzar la sintaxi que és
absolutament com C. No és exactament el mateix,

86
00:04:30,810 --> 00:04:35,020
però es veu bastant similar a un
funció, encara que falten alguns detalls.

87
00:04:35,020 --> 00:04:38,090
Res sembla succeir,
però ara si escric "hola"

88
00:04:38,090 --> 00:04:40,960
en realitat es pot escriure una
programa, no en C, no en Java,

89
00:04:40,960 --> 00:04:44,280
no en una altra programació
idioma, però en si Bash.

90
00:04:44,280 --> 00:04:47,630
>> Ara la clau aquí és que vaig escriure el
nomeno jo volia donar a aquest nou ordre,

91
00:04:47,630 --> 00:04:50,820
i els parèntesis són també
simbòlic que això sigui una funció.

92
00:04:50,820 --> 00:04:54,010
Com acotació al marge, també es pot fer la diversió
coses, i de fet, fins i tot en Mac OS,

93
00:04:54,010 --> 00:04:55,620
aquest és un programa que es diu Terminal.

94
00:04:55,620 --> 00:04:58,800
Ve integrat en qualsevol de
equip que té un Mac en aquesta sala,

95
00:04:58,800 --> 00:05:03,640
i es poden fer coses similars a Mac
OS, però es pot anar més enllà d'això.

96
00:05:03,640 --> 00:05:07,110
I això és una mica tangencial,
però és bastant divertit.

97
00:05:07,110 --> 00:05:09,715
Em vaig recordar d'aquest matí,
en pensar en això,

98
00:05:09,715 --> 00:05:13,279
d'un petit joc que solia jugar
amb un dels ex TFS del CS50

99
00:05:13,279 --> 00:05:16,570
mitjançant el qual qualsevol moment anava a allunyar-se
el seu teclat amb la seva pantalla desbloquejat,

100
00:05:16,570 --> 00:05:23,611
M'agradaria executar una ordre
així- "saludar".

101
00:05:23,611 --> 00:05:26,610
I ara ja que tornava al seu
teclat després vaig netejar la pantalla

102
00:05:26,610 --> 00:05:27,985
i s'asseia,
tractar de fer una mica de treball,

103
00:05:27,985 --> 00:05:29,250
llistar el contingut del seu directory--

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

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

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

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

108
00:05:32,120 --> 00:05:35,030
>> ALTAVEU 1: Així que, per ser justos,
que no era en realitat "hola."

109
00:05:35,030 --> 00:05:36,894
En general era una cosa
més semblant a això--

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

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

112
00:05:37,750 --> 00:05:39,320
ALTAVEU 1: --que I would--
pel que el seu equip faria

113
00:05:39,320 --> 00:05:42,170
juro a ell en qualsevol moment que en realitat
va seure al seu teclat.

114
00:05:42,170 --> 00:05:46,265
I molt aviat es va descobrir
no deixar desbloquejat la seva pantalla.

115
00:05:46,265 --> 00:05:48,730
Però això suggereix que l'espècie
divertit estúpid que

116
00:05:48,730 --> 00:05:50,210
pot tenir amb alguna cosa com Bash.

117
00:05:50,210 --> 00:05:52,770
Però és una mica més
greu, sens dubte, que això.

118
00:05:52,770 --> 00:05:57,235
I de fet, aquest és un dels
la majoria dels insectes perillosos i de llarga durada

119
00:05:57,235 --> 00:05:58,860
que realment ha colpejat el món global.

120
00:05:58,860 --> 00:06:02,060
Aquest error ha estat del voltant
durant uns 20 anys,

121
00:06:02,060 --> 00:06:05,780
i seràs colpejat en tan sols un
moment per la seva relativa simplicitat.

122
00:06:05,780 --> 00:06:07,990
>> Així que aquest és un representant
digues que si

123
00:06:07,990 --> 00:06:10,448
posseir un Mac, literalment, en aquest moment
quan vostè té la seva tapa oberta,

124
00:06:10,448 --> 00:06:12,940
pots provar a escriure en aquesta
programa anomenat Terminal.

125
00:06:12,940 --> 00:06:15,410
Terminal està sota
Aplicacions Utilities--

126
00:06:15,410 --> 00:06:18,790
per una vegada, els usuaris de Windows no han de
preocupar-se per això threat-- particular,

127
00:06:18,790 --> 00:06:22,310
però aquells de vostès amb Mac pot escriure
això en una finestra com la que vaig a fer aquí,

128
00:06:22,310 --> 00:06:24,210
i si escriviu
que en aquest programa

129
00:06:24,210 --> 00:06:28,830
anomenada Terminal, com faré ara,
si vostè veu la paraula "vulnerable"

130
00:06:28,830 --> 00:06:32,200
l'equip és
vulnerables a l'explotació.

131
00:06:32,200 --> 00:06:33,850
>> Ara, què significa en realitat?

132
00:06:33,850 --> 00:06:35,870
I això és cert
una sintaxi força boig,

133
00:06:35,870 --> 00:06:39,050
però anem a almenys derramares
alguns dels aspectes interessants.

134
00:06:39,050 --> 00:06:42,567
Així que hi ha una sintaxi que es veu
una mica familiar, almenys des de C

135
00:06:42,567 --> 00:06:43,950
i la programació en general.

136
00:06:43,950 --> 00:06:47,550
Veig alguns parèntesis,
punt i coma, claus, i tal,

137
00:06:47,550 --> 00:06:50,820
però resulta que aquest
estupidesa aquí en groc

138
00:06:50,820 --> 00:06:53,580
és essencialment una funció
això no fa res.

139
00:06:53,580 --> 00:06:57,840
Els mitjans de còlon no fan res, i la
punt i coma significa deixar de fer res.

140
00:06:57,840 --> 00:07:00,250
Així a l'interior d'aquests
claus, el fet

141
00:07:00,250 --> 00:07:02,440
que tinc una igual
signar a l'esquerra, aquesta

142
00:07:02,440 --> 00:07:05,500
és essencialment la creació
una ordre, o una variable,

143
00:07:05,500 --> 00:07:09,520
anomenada x, i assignant-li
que poc groga de codi allà.

144
00:07:09,520 --> 00:07:14,040
Això podria ser alguna cosa així com "eco
hola "o" dir bip "o alguna cosa

145
00:07:14,040 --> 00:07:15,120
similar a això.

146
00:07:15,120 --> 00:07:17,780
Però fixa't si els seus ulls
passejar més a la dreta,

147
00:07:17,780 --> 00:07:22,150
hi ha més en aquesta línia de
només el final d'aquest punt i coma.

148
00:07:22,150 --> 00:07:25,160
"Echo vulnerables", i després
més enllà que hi ha encara més.

149
00:07:25,160 --> 00:07:26,530
Un altre punt i coma, -c festa:.

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

151
00:07:28,120 --> 00:07:34,050
>> Així que conte llarg,
aquesta línia de codi és

152
00:07:34,050 --> 00:07:36,660
suficient per a obligar
un equip que és

153
00:07:36,660 --> 00:07:39,830
vulnerables a fer alguna cosa
que vostè vol que faci,

154
00:07:39,830 --> 00:07:44,290
perquè hi ha un error en el qual Bash
encara Bash havia de deixar de

155
00:07:44,290 --> 00:07:48,980
línies de lectura de comandament de la dreta
allà després del text groc,

156
00:07:48,980 --> 00:07:52,520
per a un 20-plus anys error d'edat,
Bash ha estat en realitat la lectura

157
00:07:52,520 --> 00:07:56,780
més enllà d'aquest punt i coma i bastant
molt fent el que se li diu.

158
00:07:56,780 --> 00:07:59,070
>> Quina és la implicació
que en última instància?

159
00:07:59,070 --> 00:08:01,340
Que acabo de dir "fet hola"
o "eco vulnerables"

160
00:08:01,340 --> 00:08:05,449
però el que si vostè va fer alguna cosa
realment maliciosos, com rm-rf *,

161
00:08:05,449 --> 00:08:07,240
que potser no
alguna vegada ha escrit abans,

162
00:08:07,240 --> 00:08:08,920
i, francament, és probable que
no ha de massa aviat,

163
00:08:08,920 --> 00:08:10,700
perquè es pot fer una
molt de mal amb ella.

164
00:08:10,700 --> 00:08:11,210
Per què?

165
00:08:11,210 --> 00:08:12,990
rm fa què, és clar?

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

167
00:08:14,270 --> 00:08:15,930
* Significa què?

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

169
00:08:16,430 --> 00:08:18,180
Així que és una crida
comodí, pel que significa

170
00:08:18,180 --> 00:08:20,410
esborrar tot en
el directori actual.

171
00:08:20,410 --> 00:08:23,379
-r passa a significar recursiva,
que vol dir que si el que estàs esborrant

172
00:08:23,379 --> 00:08:26,420
és un directori, i dins d'aquí
és altres arxius i altres directoris,

173
00:08:26,420 --> 00:08:28,950
recursiva submergir-se en allà
i esborrar tot això.

174
00:08:28,950 --> 00:08:31,040
I f és el pitjor de tots ells.

175
00:08:31,040 --> 00:08:32,580
Algú sap el que significa -f aquí?

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

177
00:08:33,690 --> 00:08:34,360
Força.

178
00:08:34,360 --> 00:08:37,830
Així forçar mitjans, fins i tot
si això és una mala idea,

179
00:08:37,830 --> 00:08:40,939
fer-ho sense mi que va provocar
per al seu posterior confirmació.

180
00:08:40,939 --> 00:08:43,230
Així que, ja saps, ens riem de
això, però, francament, jo probablement

181
00:08:43,230 --> 00:08:44,972
escrigui això diverses vegades
un dia, perquè la realitat

182
00:08:44,972 --> 00:08:47,210
és que és la manera més ràpida de
suprimir un munt de coses.

183
00:08:47,210 --> 00:08:48,590
Però fins i tot he fet una mica de mal.

184
00:08:48,590 --> 00:08:53,100
>> Però si anés a enganyar a un ordinador
en definir alguna variable estúpid

185
00:08:53,100 --> 00:08:56,810
o funció crida x, però després
enganyar l'ordinador que executi

186
00:08:56,810 --> 00:09:00,030
més enllà dels límits d'aquesta
funció, més enllà d'aquest punt i coma,

187
00:09:00,030 --> 00:09:04,430
que de fet podria enganyar a un ordinador
en l'execució d'alguna cosa com rm-rf

188
00:09:04,430 --> 00:09:07,810
o la comanda Email
o l'ordre Copia.

189
00:09:07,810 --> 00:09:11,400
Qualsevol cosa, literalment, li pot veure amb el
ordinador, si es tracta de l'eliminació d'arxius,

190
00:09:11,400 --> 00:09:15,350
la creació d'arxius, enviament de correu brossa a algú,
atacant a algun servidor de manera remota,

191
00:09:15,350 --> 00:09:17,190
si vostè pot expressar
amb una ordre,

192
00:09:17,190 --> 00:09:19,120
pot enganyar a un ordinador perquè faci això.

193
00:09:19,120 --> 00:09:21,510
>> Ara el que és un exemple de
com es pot fer això?

194
00:09:21,510 --> 00:09:24,300
Bé, hi ha un munt d'ordinadors
al Bash internet en execució.

195
00:09:24,300 --> 00:09:26,390
Tots els usuaris de Mac ens estan entre ells.

196
00:09:26,390 --> 00:09:30,390
Una gran quantitat de servidors Linux es troben entre
ells també, i servidors Unix.

197
00:09:30,390 --> 00:09:32,630
Finestres obté de nou
relativament fora del ganxo

198
00:09:32,630 --> 00:09:34,590
llevat que hi hagi instal · lat
programari especial.

199
00:09:34,590 --> 00:09:37,130
Ara un munt de servidors, per
exemple, per executar servidors web,

200
00:09:37,130 --> 00:09:39,840
i de fet Linux és potser el
més popular sistema operatiu

201
00:09:39,840 --> 00:09:43,060
perquè funcione a ordinadors a Internet
que servir les pàgines web.

202
00:09:43,060 --> 00:09:44,910
Ara bé, com veurem més endavant
en el semestre, quan

203
00:09:44,910 --> 00:09:48,470
s'envia una sol licitud de
seva browser-- Chrome,

204
00:09:48,470 --> 00:09:50,790
Internet Explorer, whatever--
a un servidor remot,

205
00:09:50,790 --> 00:09:53,730
resulta que tot i que
que acaba d'escriure www.example.com,

206
00:09:53,730 --> 00:09:59,590
el teu navegador enviant un missatge
això és una mica més arcà, com aquest.

207
00:09:59,590 --> 00:10:01,239
>> Però noti alguna cosa estranya.

208
00:10:01,239 --> 00:10:03,030
Les dues primeres línies
Jo mai he vist abans,

209
00:10:03,030 --> 00:10:04,904
però que no es veuen
particularment mortal.

210
00:10:04,904 --> 00:10:08,030
Però noto el que jo he robat
per a la tercera línia d'aquí.

211
00:10:08,030 --> 00:10:13,390
Si un intrús fora a enviar un missatge
així des del seu ordinador

212
00:10:13,390 --> 00:10:17,270
a un Mac o vulnerable
servidor Linux vulnerables,

213
00:10:17,270 --> 00:10:21,580
el curiós és que Bash,
que ràpida mica simple comandament,

214
00:10:21,580 --> 00:10:27,450
és omnipresent i és sovint
S'usa per executar essencialment

215
00:10:27,450 --> 00:10:30,020
el contingut d'un
missatge que rep.

216
00:10:30,020 --> 00:10:33,490
I per aquesta lògica, es pot
enganyar a un servidor web, per tant,

217
00:10:33,490 --> 00:10:36,370
enviant una cosa així
User-Agent, que en general

218
00:10:36,370 --> 00:10:38,300
se suposa que és dir el
Nom del teu navegador.

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

220
00:10:42,420 --> 00:10:44,590
és només el navegador d'
forma d'identificar-se a si mateix.

221
00:10:44,590 --> 00:10:46,605
Però si un dels dolents molt
intel · ligentment diu, mm-mm, estic

222
00:10:46,605 --> 00:10:47,930
No diré
el que el meu navegador és,

223
00:10:47,930 --> 00:10:50,888
Estic en comptes d'anar a fer-li arribar aquesta
El críptic d'aspecte amb un rm-rf

224
00:10:50,888 --> 00:10:55,840
* En el mateix, que, literalment, pot enganyar a un
servidor web vulnerable a Internet

225
00:10:55,840 --> 00:10:59,055
perquè executi exactament això en
allà per esborrar tots els arxius.

226
00:10:59,055 --> 00:11:00,930
I, francament, això no és
fins i tot la pitjor part.

227
00:11:00,930 --> 00:11:01,763
Vostè pot fer qualsevol cosa.

228
00:11:01,763 --> 00:11:04,480
Vostè podria començar una distribuïda
atac de denegació de servei

229
00:11:04,480 --> 00:11:07,030
si va enviar aquest missatge a
raïms sencers de servidors web

230
00:11:07,030 --> 00:11:10,256
i després van tenir tots ells descendeixen, per
exemple, en servidors Harvard.edu,

231
00:11:10,256 --> 00:11:12,130
i es pot ordenar d'explosió
els diables d'ells

232
00:11:12,130 --> 00:11:15,490
per un tràfic de xarxa que
desencadenada en contra d'aquest noi dolent.

233
00:11:15,490 --> 00:11:18,760
>> Per tant, conte llarg, gairebé
tots en aquesta sala que és propietari d'un Mac

234
00:11:18,760 --> 00:11:20,240
és vulnerable a aquest.

235
00:11:20,240 --> 00:11:24,100
El costat positiu és que a menys que siguis
executar un servidor web en el seu ordinador portàtil,

236
00:11:24,100 --> 00:11:27,780
i, llevat que hi hagi configurat en realitat
per permetre que alguna cosa així com SSH en ell,

237
00:11:27,780 --> 00:11:28,670
estàs realment segur.

238
00:11:28,670 --> 00:11:31,710
És vulnerable, però no és
un tractant d'entrar al seu ordinador portàtil,

239
00:11:31,710 --> 00:11:33,290
així que vostè pot ordenar d'explicar.

240
00:11:33,290 --> 00:11:36,210
No obstant això, Apple aviat
ser l'actualització d'una solució per a aquest.

241
00:11:36,210 --> 00:11:39,660
El món de Linux ja ha llançat
una sèrie de correccions per Fedora i Ubuntu

242
00:11:39,660 --> 00:11:43,790
i altres versions de Linux, i de fet
si executa l'actualització 50 en l'aparell,

243
00:11:43,790 --> 00:11:45,930
encara que això també serà
actualitzada i corregida.

244
00:11:45,930 --> 00:11:47,764
Però això tampoc té
estat realment vulnerable,

245
00:11:47,764 --> 00:11:49,804
perquè a menys que vostè té
vanament amb l'aparell

246
00:11:49,804 --> 00:11:52,770
i va fer el seu portàtil públicament
accessibles a Internet, que no és

247
00:11:52,770 --> 00:11:54,910
per defecte, que hi hagi
en realitat estat bé perquè

248
00:11:54,910 --> 00:11:56,890
de tallafocs i altres tècniques.

249
00:11:56,890 --> 00:12:01,000
>> Però és un exemple extrem d'un error
que hem viscut per per, literalment, 20

250
00:12:01,000 --> 00:12:04,050
anys, i qui sap si algú
tot aquest temps s'ha sabut d'ella?

251
00:12:04,050 --> 00:12:06,300
I de fet, aquesta és una de
els reptes fonamentals

252
00:12:06,300 --> 00:12:08,690
que veurem més endavant en el
semestre per la seguretat,

253
00:12:08,690 --> 00:12:13,020
és que igual que en el món real,
els bons són a la desavantatge.

254
00:12:13,020 --> 00:12:16,500
Per mantenir els nois dolents, hem de
assegurar-se que cada porta està tancada,

255
00:12:16,500 --> 00:12:20,340
que cada finestra és segur, que
cada punt d'entrada en una llar

256
00:12:20,340 --> 00:12:21,980
és segur per mantenir els nois dolents.

257
00:12:21,980 --> 00:12:26,870
Però el que fa el dolent de la pel · lícula ha de
fer per comprometre realment casa

258
00:12:26,870 --> 00:12:28,200
i robar de vostè?

259
00:12:28,200 --> 00:12:32,574
Ell o ella només ha de trobar un desbloquejat
porta, una finestra trencada o alguna cosa

260
00:12:32,574 --> 00:12:35,240
en aquest sentit, i és la
el mateix a la seguretat informàtica.

261
00:12:35,240 --> 00:12:37,660
Podem escriure a milions de
línies de codi de programació

262
00:12:37,660 --> 00:12:40,570
i gastar centenars o milers
d'hores tractant d'aconseguir correcte,

263
00:12:40,570 --> 00:12:43,370
però si ho fan només una
error en la correcció,

264
00:12:43,370 --> 00:12:47,030
vostè pot posar tot el sistema i
de fet, en aquest cas, la totalitat d'internet

265
00:12:47,030 --> 00:12:48,660
i el món en risc.

266
00:12:48,660 --> 00:12:51,950
>> Així que si voleu aprendre més
sobre això, aneu a aquesta URL aquí.

267
00:12:51,950 --> 00:12:54,450
No hi ha necessitat d'una acció
aquesta nit llevat que estigui

268
00:12:54,450 --> 00:12:57,116
entre els més còmodes que
han estat la gestió de la seva pròpia web

269
00:12:57,116 --> 00:12:59,810
servidor, en aquest cas vostè ha,
de fet, actualitzar el programari.

270
00:12:59,810 --> 00:13:03,244
>> I això també és el títol de
un discurs, i ara un paper,

271
00:13:03,244 --> 00:13:05,410
que ens hem vinculat a la
la pàgina web del curs per avui.

272
00:13:05,410 --> 00:13:07,600
Va ser per un company
anomenat Ken Thompson, qui

273
00:13:07,600 --> 00:13:10,120
va ser l'acceptació d'un molt famós
premi en ciències de la computació,

274
00:13:10,120 --> 00:13:13,495
i ell va donar aquest discurs alguns anys
fa, essencialment sobre el mateix tema.

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

276
00:13:18,250 --> 00:13:20,520
La gent que fa la pregunta,
Si realment

277
00:13:20,520 --> 00:13:23,480
confiança, en última instància, la
programari que t'han donat?

278
00:13:23,480 --> 00:13:26,100
Per exemple, tots tenim
estat escrivint programes,

279
00:13:26,100 --> 00:13:27,820
i hem estat recopilant
amb Clang.

280
00:13:27,820 --> 00:13:31,830
I al seu coneixement, has escrit
qualsevol programa de CS50 on hi ha

281
00:13:31,830 --> 00:13:35,310
una porta del darrere de tipus, hi ha una manera
que un tipus dolent, si s'executa el programa,

282
00:13:35,310 --> 00:13:37,410
podria fer-se càrrec del seu equip?

283
00:13:37,410 --> 00:13:38,310
Probablement no, oi?

284
00:13:38,310 --> 00:13:40,180
Mario i cobdiciós, i Crèdit.

285
00:13:40,180 --> 00:13:41,680
Aquests són tots els programes bastant petits.

286
00:13:41,680 --> 00:13:43,910
Vostè hauria de ser bastant
malament si en realitat

287
00:13:43,910 --> 00:13:47,310
fet tot l'equip sigui vulnerable
després d'escriure 10 o 20 línies de codi,

288
00:13:47,310 --> 00:13:49,690
o almenys conscient d'alguns
de les implicacions de seguretat.

289
00:13:49,690 --> 00:13:52,023
Ara dic que en to de burla,
però anem a veure avui

290
00:13:52,023 --> 00:13:54,600
i aquesta setmana és en realitat
molt, molt fàcil

291
00:13:54,600 --> 00:13:57,980
a ser dolent i fer encara
programes curts vulnerables.

292
00:13:57,980 --> 00:14:02,880
>> Però, per ara, almenys, adonar-
que la pregunta que es fa aquí

293
00:14:02,880 --> 00:14:04,850
està a punt Clang en un compilador.

294
00:14:04,850 --> 00:14:08,360
Per què hem estat confiant en Clang
durant els últims dos o tres setmanes?

295
00:14:08,360 --> 00:14:12,650
Qui pot dir que qui va escriure Clang
no tenia un "si" condició en la que hi ha

296
00:14:12,650 --> 00:14:17,680
que essencialment s'injecta alguns zeros
i els en cada programa es compila

297
00:14:17,680 --> 00:14:21,180
això seria deixar que ell o ella l'accés
quan l'equip està adormit

298
00:14:21,180 --> 00:14:23,580
i la seva tapa del portàtil està obert
i l'equip s'executa?

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

300
00:14:24,080 --> 00:14:28,350
Tenim aquest tipus de sistema d'honor dret
ara on confiem que Clang és de fiar.

301
00:14:28,350 --> 00:14:30,000
Vostè confia que l'aparell és de fiar.

302
00:14:30,000 --> 00:14:34,430
Vostè confia que, literalment, tots els programes
al teu Mac o PC és digne de confiança.

303
00:14:34,430 --> 00:14:37,510
I com aquest simple error suggereix,
encara que no és maliciós,

304
00:14:37,510 --> 00:14:40,580
això no és absolutament
probable que sigui el cas.

305
00:14:40,580 --> 00:14:42,350
>> Així que vostè ha de tenir por com l'infern.

306
00:14:42,350 --> 00:14:45,560
Francament, no hi senzill
solució a aquest altre

307
00:14:45,560 --> 00:14:48,185
que una espècie de consciència social
de la complexitat cada vegada més gran

308
00:14:48,185 --> 00:14:50,310
que estem construint a la part superior
dels nostres sistemes informàtics,

309
00:14:50,310 --> 00:14:53,740
i com cada vegada més vulnerables
podríem molt bé ser.

310
00:14:53,740 --> 00:14:55,570
>> Ara, amb això dit, Breakout.

311
00:14:55,570 --> 00:14:59,889
Així Breakout és problema estableix tres, i
Breakout és un joc d'abans

312
00:14:59,889 --> 00:15:02,180
que es pot recordar, però
per a nosaltres en un problema establert tres,

313
00:15:02,180 --> 00:15:04,450
que ens permet prendre
les coses tornin a un nivell superior

314
00:15:04,450 --> 00:15:08,880
de manera que quan estem escrivint programes,
fins i tot en una finestra de terminal com aquest,

315
00:15:08,880 --> 00:15:14,670
en realitat podem executar, en última instància,
no els programes de gràfics

316
00:15:14,670 --> 00:15:17,800
a diferència d'aquells que vam tenir
en l'accés a les ratllades.

317
00:15:17,800 --> 00:15:20,910
Així que aquesta és la dècada dels funcionaris
implementació de Breakout,

318
00:15:20,910 --> 00:15:23,930
que és precisament aquesta trencar maons
joc, que es mou la pala cap enrere

319
00:15:23,930 --> 00:15:27,590
endavant i cap enrere, i colpejar la bola
contra els maons de colors fins a la part superior.

320
00:15:27,590 --> 00:15:30,020
Així que això ens està portant
espècie de tornada a on

321
00:15:30,020 --> 00:15:33,180
hem estat capaços de ser molt ràpid
amb Scratch, i ara amb C,

322
00:15:33,180 --> 00:15:35,800
la implementació de la nostra pròpia
interfícies gràfiques d'usuari.

323
00:15:35,800 --> 00:15:38,960
>> Però més que això, aquest
conjunt de problemes representa la primera

324
00:15:38,960 --> 00:15:41,000
en la que estem donant
que un munt de codi.

325
00:15:41,000 --> 00:15:43,940
I, de fet, els porto explícita
atenció a això, perquè tot

326
00:15:43,940 --> 00:15:47,090
per als menys confortable, aquest
problema configurat, almenys a primera vista,

327
00:15:47,090 --> 00:15:49,170
es va a sentir com
hem portat a un nivell superior.

328
00:15:49,170 --> 00:15:51,540
Com que els hem donat,
per alguns de la cerca

329
00:15:51,540 --> 00:15:54,930
i classificació dels problemes en el conjunt de processadors,
un munt de codi que escrivim,

330
00:15:54,930 --> 00:15:56,680
i un parell de comentaris
que diuen "fer"

331
00:15:56,680 --> 00:15:58,221
on vostè ha de omplir els espais en blanc.

332
00:15:58,221 --> 00:16:00,020
Així que no massa por, però
que és la primera vegada

333
00:16:00,020 --> 00:16:03,370
li estem lliurant codi que vostè necessita
llegir primer, entendre, i després afegir a

334
00:16:03,370 --> 00:16:04,290
i completar-lo.

335
00:16:04,290 --> 00:16:05,940
>> I després, amb Breakout,
farem el mateix,

336
00:16:05,940 --> 00:16:08,740
donant-li unes poques dotzenes més línies
de codi que, francament, li donarà

337
00:16:08,740 --> 00:16:11,490
una gran part del marc per
el joc, però aturar-

338
00:16:11,490 --> 00:16:14,304
de l'aplicació dels maons
i la pilota i la paleta,

339
00:16:14,304 --> 00:16:15,970
però sí implementem algunes altres característiques.

340
00:16:15,970 --> 00:16:18,280
I fins i tot que, a primera vista, de nou,
especialment si menys còmode,

341
00:16:18,280 --> 00:16:21,480
podria semblar especialment difícil i
Creus que hi ha tantes noves funcions

342
00:16:21,480 --> 00:16:24,070
que necessita per embolicar la seva ment
voltant, i això és veritat.

343
00:16:24,070 --> 00:16:26,281
Però tingui en compte, és
absolutament com esgarrapades.

344
00:16:26,281 --> 00:16:28,780
El més probable és que no ha utilitzat totes
les peces del trencaclosques en zero.

345
00:16:28,780 --> 00:16:31,120
El més probable és que no et importava per embolicar
la seva ment al voltant de tots ells

346
00:16:31,120 --> 00:16:33,617
perquè tot el que va fer ser un
ràpida mirada per comprendre, oh,

347
00:16:33,617 --> 00:16:35,450
això és el que puc fer
amb aquesta peça del trencaclosques.

348
00:16:35,450 --> 00:16:38,260
I de fet, en conjunt de problemes
3 spec, anem a assenyalar que

349
00:16:38,260 --> 00:16:41,370
en la documentació que
presentar a algunes funcions noves,

350
00:16:41,370 --> 00:16:43,570
i en última instància la programació
construccions que utilitzi.

351
00:16:43,570 --> 00:16:47,610
Condicions, bucles,
variables i funcions

352
00:16:47,610 --> 00:16:50,720
serà idèntic al
el que hem vist fins ara.

353
00:16:50,720 --> 00:16:53,560
>> Així que de fet, el que donarem
vostè és un codi d'exemple que

354
00:16:53,560 --> 00:16:56,110
li permet crear una finestra
que no es veu a diferència d'aquest,

355
00:16:56,110 --> 00:16:59,540
i en última instància, convertir-lo en
alguna cosa com això.

356
00:16:59,540 --> 00:17:02,250
Així que pren avantatge d'CS50,
discutir hores d'oficina i més,

357
00:17:02,250 --> 00:17:05,290
i consolar-se amb el fet que
la quantitat de codi que ha d'escriure

358
00:17:05,290 --> 00:17:06,760
en realitat no és tant.

359
00:17:06,760 --> 00:17:10,359
El primer repte és només per aclimatar
vostè mateix a algun codi que hem escrit.

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

361
00:17:11,450 --> 00:17:15,810
>> Qualsevol pregunta sobre pset3,
Shellshock, o d'una altra manera?

362
00:17:15,810 --> 00:17:19,226
>> AUDIÈNCIA: Semblava que
anar a través amb Breakout

363
00:17:19,226 --> 00:17:22,154
que el codi és gairebé
un estil orientat a objectes,

364
00:17:22,154 --> 00:17:24,675
però vaig pensar que era un C
programa orientat a objectes.

365
00:17:24,675 --> 00:17:26,050
ALTAVEU 1: Una excel · lent pregunta.

366
00:17:26,050 --> 00:17:28,258
Així que en mirar a través de la
codi de distribució, el codi

367
00:17:28,258 --> 00:17:30,180
escrivim per pset3,
Per a aquells familiaritzats, es

368
00:17:30,180 --> 00:17:32,230
sembla que és un
poc orientat a objectes.

369
00:17:32,230 --> 00:17:33,800
Resposta curta és, ho és.

370
00:17:33,800 --> 00:17:38,130
És una aproximació de com es
podria fer codi orientat a objectes utilitzant

371
00:17:38,130 --> 00:17:41,850
un llenguatge com C, però és
encara en última instància de procediment.

372
00:17:41,850 --> 00:17:44,900
No hi ha mètodes dins d'
les variables, com veuràs.

373
00:17:44,900 --> 00:17:46,180
Però recorda que.

374
00:17:46,180 --> 00:17:48,780
I veurem que la funció de nou
quan arribem a PHP i JavaScript

375
00:17:48,780 --> 00:17:49,946
cap al final del semestre.

376
00:17:49,946 --> 00:17:53,667
Però per ara, pensar-hi com
una pista del que està per venir.

377
00:17:53,667 --> 00:17:54,250
Bona pregunta.

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

379
00:17:56,051 --> 00:17:56,550
Bé.

380
00:17:56,550 --> 00:17:59,730
Així merge sort era com
coses esquerra última vegada.

381
00:17:59,730 --> 00:18:03,250
I fusionar espècie estava fresc a la
sentit que era molt més ràpid,

382
00:18:03,250 --> 00:18:07,100
almenys sobre la base de les proves superficials
que vam fer la setmana passada, que, per exemple, la bombolla

383
00:18:07,100 --> 00:18:08,710
espècie, ordenament per selecció, ordenació per inserció.

384
00:18:08,710 --> 00:18:11,780
I el que era massa net és només
com succinta i netament

385
00:18:11,780 --> 00:18:12,810
pots expressar-ho.

386
00:18:12,810 --> 00:18:15,840
I el que vam dir que era un superior
amb destinació en el temps d'execució de la fusió

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

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

389
00:18:17,633 --> 00:18:18,495
Sí?

390
00:18:18,495 --> 00:18:19,360
>> AUDIÈNCIA: n log n?

391
00:18:19,360 --> 00:18:20,819
>> ALTAVEU 1: n log n, dret. n log n.

392
00:18:20,819 --> 00:18:23,776
I anem a tornar al que
realment significa o d'on ve,

393
00:18:23,776 --> 00:18:25,570
però això era millor
que el que el temps de funcionament

394
00:18:25,570 --> 00:18:28,440
que vam veure durant la bombolla
selecció i ordenació per inserció?

395
00:18:28,440 --> 00:18:30,610
Així que n al quadrat. n al quadrat
és més gran que això,

396
00:18:30,610 --> 00:18:34,650
i encara que no és prou obvi,
sap que log n és menor que n,

397
00:18:34,650 --> 00:18:36,910
així que si vostè ho fa n vegades
una mica menor que n,

398
00:18:36,910 --> 00:18:38,680
que serà menor que n al quadrat.

399
00:18:38,680 --> 00:18:40,130
És una mica d'intuïció allà.

400
00:18:40,130 --> 00:18:42,190
Però paguem un preu per això.

401
00:18:42,190 --> 00:18:47,000
Era més ràpid, però un tema que va començar
emergeixi la setmana passada era aquest sacrifici.

402
00:18:47,000 --> 00:18:49,804
Tinc un millor rendiment
pel que fa a temps, però el que

403
00:18:49,804 --> 00:18:52,470
Per què he de passar per un altre
part, amb la finalitat d'aconseguir això?

404
00:18:52,470 --> 00:18:53,591
>> AUDIÈNCIA: Memòria.

405
00:18:53,591 --> 00:18:54,465
ALTAVEU 1: Digues-ho de nou?

406
00:18:54,465 --> 00:18:55,173
AUDIÈNCIA: Memòria.

407
00:18:55,173 --> 00:18:57,040
ALTAVEU 1: Memòria, o
l'espai de forma més general.

408
00:18:57,040 --> 00:18:59,040
I no era súper
òbvia amb els nostres éssers humans,

409
00:18:59,040 --> 00:19:02,240
però recordar que els nostres voluntaris
van anar donant un pas endavant i pas a pas

410
00:19:02,240 --> 00:19:04,780
cap enrere com si hi ha una matriu
aquí, i com si hi

411
00:19:04,780 --> 00:19:07,130
una segona matriu que aquí
que podrien utilitzar, perquè ens

412
00:19:07,130 --> 00:19:09,080
algun lloc necessària per fusionar aquestes persones.

413
00:19:09,080 --> 00:19:11,480
No podíem canviar al seu lloc.

414
00:19:11,480 --> 00:19:13,800
Així fusionar espècie de palanquejament
és més espai, la qual cosa

415
00:19:13,800 --> 00:19:15,620
que no era necessari amb
els altres algoritmes,

416
00:19:15,620 --> 00:19:17,410
però l'avantatge és que és molt més ràpid.

417
00:19:17,410 --> 00:19:20,780
I, francament, a l'espai del món real
aquests RAM dies--, disc dur espai--

418
00:19:20,780 --> 00:19:25,030
és relativament barat, i pel que és
no és necessàriament una cosa dolenta.

419
00:19:25,030 --> 00:19:28,320
>> Així que anem a fer una ullada ràpida, una mica
més metòdicament, en el que vam fer

420
00:19:28,320 --> 00:19:30,220
i per què vam dir que va ser n log n.

421
00:19:30,220 --> 00:19:33,260
Així que aquí hi ha els vuit nombres i la
vuit voluntaris que tenien l'última vegada.

422
00:19:33,260 --> 00:19:35,718
I el primer que Merge
Ordenar ens va dir que fer era què?

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

424
00:19:37,010 --> 00:19:38,010
AUDIÈNCIA: Divideix en dues.

425
00:19:38,010 --> 00:19:38,663
ALTAVEU 1: Digues-ho de nou?

426
00:19:38,663 --> 00:19:39,650
AUDIÈNCIA: Divideix en dues.

427
00:19:39,650 --> 00:19:40,610
ALTAVEU 1: Dividir en dos, dreta.

428
00:19:40,610 --> 00:19:42,818
Això recorda molt a
la guia telefònica, de divisió

429
00:19:42,818 --> 00:19:44,220
i conquerir de manera més general.

430
00:19:44,220 --> 00:19:45,640
Així que busquem en la meitat esquerra.

431
00:19:45,640 --> 00:19:48,700
I llavors un cop vam dir, una espècie
la meitat esquerra dels elements,

432
00:19:48,700 --> 00:19:49,690
¿Què vam fer juntament diem?

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

434
00:19:51,210 --> 00:19:54,860
Ordenar la meitat esquerra de l'esquerra
la meitat, la qual cosa ens va permetre,

435
00:19:54,860 --> 00:19:57,570
després de dividir en dos,
centrar en quatre-dos.

436
00:19:57,570 --> 00:20:01,280
>> Com ordenar una llista ara, en
groc, de mida 2, utilitzant Combinar Ordenar?

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

438
00:20:02,330 --> 00:20:04,580
Bé dividir per la meitat,
i ordenar la meitat esquerra.

439
00:20:04,580 --> 00:20:07,100
I aquest era el lloc on les coses
es va posar una mica breument estúpid.

440
00:20:07,100 --> 00:20:10,720
Com ordenar una llista que és de
mida d'un, com aquest número quatre en aquesta llista?

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

442
00:20:12,330 --> 00:20:13,210
Està ordenada.

443
00:20:13,210 --> 00:20:14,200
Ha acabat.

444
00:20:14,200 --> 00:20:17,300
>> Però llavors, ¿com ordenar una llista de
mida d'un quan és el número dos?

445
00:20:17,300 --> 00:20:21,640
Bé, el mateix, però ara el que va ser la
tercer i el pas clau en Merge Ordenar?

446
00:20:21,640 --> 00:20:24,020
Calia combinar l'esquerra
la meitat i la meitat dreta.

447
00:20:24,020 --> 00:20:26,580
I una vegada que ho vam fer, ens vam mirar
a les quatre, ens fixem en dos.

448
00:20:26,580 --> 00:20:28,750
Decidim bé,
òbviament ha dos que passi primer,

449
00:20:28,750 --> 00:20:31,840
així que vam posar dos al seu
lloc, seguit per quatre.

450
00:20:31,840 --> 00:20:35,010
I ara has de tipus de rebobinat,
i això és una espècie de característica

451
00:20:35,010 --> 00:20:37,570
d'un algorisme com Merge
Ordena, rebobinar en la memòria.

452
00:20:37,570 --> 00:20:40,240
Quina va ser la següent línia de la història?

453
00:20:40,240 --> 00:20:41,780
Què hauria d'estar centrat en el proper?

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

455
00:20:43,110 --> 00:20:47,350
La meitat dreta de l'esquerra
mitjana, que és de sis-vuit.

456
00:20:47,350 --> 00:20:50,320
>> Així que permetin-me simplement un pas a través d'aquesta
sense picar el punt massa.

457
00:20:50,320 --> 00:20:53,330
Sis i vuit, a continuació, sis és
ordenats, vuit s'ordena.

458
00:20:53,330 --> 00:20:57,190
Combinar junts d'aquesta manera,
i ara el proper gran pas

459
00:20:57,190 --> 00:21:00,990
està, per descomptat, ordenar la meitat dreta des
el primer pas d'aquest algorisme.

460
00:21:00,990 --> 00:21:02,870
Així que ens centrem en un, tres, set, cinc.

461
00:21:02,870 --> 00:21:04,540
Després ens centrem en la meitat esquerra.

462
00:21:04,540 --> 00:21:09,400
La meitat esquerra que, la meitat dreta
això i, a continuació, es fonen en un i tres.

463
00:21:09,400 --> 00:21:13,100
Llavors la meitat dreta, després a l'esquerra la meitat
d'ell, llavors la meitat dreta de la mateixa.

464
00:21:13,100 --> 00:21:15,985
Combinar en, i ara el que queda pas?

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

466
00:21:18,040 --> 00:21:22,460
Combinar la gran meitat esquerra i la gran
meitat dreta, de manera que un es posa allà,

467
00:21:22,460 --> 00:21:27,330
després dos, després tres, després quatre, després
cinc, després sis, després set, després vuit.

468
00:21:27,330 --> 00:21:31,990
>> Així que ara per què s'està revelant en última instància,
especialment si n i logaritmes més

469
00:21:31,990 --> 00:21:35,487
en general, més aviat escapar,
almenys en els últims temps?

470
00:21:35,487 --> 00:21:37,070
Bé, fixa't en l'altura d'aquesta cosa.

471
00:21:37,070 --> 00:21:41,230
Vam tenir vuit elements, i ens
dividit per dos, per dos, per dos.

472
00:21:41,230 --> 00:21:44,590
Així que la base ingressi dues de les vuit ens dóna 3.

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

474
00:21:45,640 --> 00:21:48,540
I confia en mi que si
una mica nebulós sobre això.

475
00:21:48,540 --> 00:21:54,710
Però el registre de base de dos de vuit és tres,
pel que hem fet tres capes de fusió.

476
00:21:54,710 --> 00:21:57,170
I quan ens fusionem
elements, el nombre d'elements

477
00:21:57,170 --> 00:21:58,950
ens veiem en cadascuna de les files?

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

479
00:22:00,212 --> 00:22:01,437
Un total de n, oi?

480
00:22:01,437 --> 00:22:04,020
A causa de la fusió de la fila superior,
tot i que ho vam fer a poc a poc,

481
00:22:04,020 --> 00:22:05,990
que en última instància, toquem cada número una vegada.

482
00:22:05,990 --> 00:22:09,054
I a la segona fila, a
fusionar aquestes llistes de mida 2,

483
00:22:09,054 --> 00:22:10,470
vam haver de tocar cada element una vegada.

484
00:22:10,470 --> 00:22:12,690
I llavors aquí realment
clarament a l'última fila,

485
00:22:12,690 --> 00:22:15,430
vam haver de tocar cada un dels
elements d'una vegada, però només una vegada,

486
00:22:15,430 --> 00:22:18,400
així que en aquest document es troba, llavors, el nostre n log n.

487
00:22:18,400 --> 00:22:21,780
>> I ara només per fer les coses una mica
més formal per a un moment, si

488
00:22:21,780 --> 00:22:24,260
estaven ara a analitzar aquest
en una mena de major nivell

489
00:22:24,260 --> 00:22:28,340
i tractar de decidir, així com
podries anar en expressar

490
00:22:28,340 --> 00:22:31,780
el temps d'execució d'aquest algorisme
només mirant a ella i no

491
00:22:31,780 --> 00:22:33,590
utilitzant un exemple artificiós?

492
00:22:33,590 --> 00:22:36,590
Bé, quant de temps li diries a
pas com aquest en groc prendria,

493
00:22:36,590 --> 00:22:37,173
si n <2 volta?

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

495
00:22:38,840 --> 00:22:39,830
Aquesta és una gran O de què?

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

497
00:22:41,450 --> 00:22:44,540
Així que jo estic veient un, així que un pas,
potser dos passos perquè és si

498
00:22:44,540 --> 00:22:47,110
i després tornar, però és
constant de temps, oi?

499
00:22:47,110 --> 00:22:49,960
Així que vam dir O (1), i això és
com vaig a expressar això.

500
00:22:49,960 --> 00:22:51,480
T, acaba de ser temps d'execució.

501
00:22:51,480 --> 00:22:54,150
n és la mida de l'entrada,
així que T (n), només una forma elegant

502
00:22:54,150 --> 00:22:56,330
de dir el funcionament
temps d'entrada donat de grandària n

503
00:22:56,330 --> 00:23:00,220
serà de l'ordre
de constant de temps, a O (1).

504
00:23:00,220 --> 00:23:01,970
>> Però d'altra banda, ¿què passa amb això?

505
00:23:01,970 --> 00:23:05,660
Com expressar la
moment d'aquesta línia groga corrent?

506
00:23:05,660 --> 00:23:06,250
T ¿de què?

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

508
00:23:09,440 --> 00:23:12,665
Pot tipus de trampes aquí i
respondre a la meva pregunta de forma cíclica.

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

510
00:23:14,770 --> 00:23:17,900
Així que si el temps de funcionament en
en general ens limitem a dir és T (n).

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

512
00:23:18,950 --> 00:23:22,490
I ara vostè està mena de batea aquí i
dient, bé, només ordenar la meitat esquerra,

513
00:23:22,490 --> 00:23:23,920
i després ordenar la meitat dreta.

514
00:23:23,920 --> 00:23:27,520
Com podríem representar simbòlicament
el temps d'execució d'aquesta línia groga?

515
00:23:27,520 --> 00:23:28,020
T ¿de què?

516
00:23:28,020 --> 00:23:29,360
Quina és la mida de l'entrada?

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

518
00:23:30,510 --> 00:23:31,057
n més de dos.

519
00:23:31,057 --> 00:23:32,140
Per què no m'acaba de dir això?

520
00:23:32,140 --> 00:23:36,449
I llavors aquest és un altre T (n / 2) i després
de nou, si puc combinar dues meitats ordenades,

521
00:23:36,449 --> 00:23:38,615
quants elements vaig
a haver de tocar total de?

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
Així que puc expressar això,
només per ser una mica de fantasia,

525
00:23:42,790 --> 00:23:44,430
com el temps de funcionament en general.

526
00:23:44,430 --> 00:23:51,140
T (n) és el temps de durada de T (n / 2),
més de T (n / 2), la meitat esquerra i la meitat dreta,

527
00:23:51,140 --> 00:23:55,360
a més d'O (n), que és probablement n passos,
però potser, si estic fent servir dos dits,

528
00:23:55,360 --> 00:23:57,960
que és el doble que
passos, però és lineal.

529
00:23:57,960 --> 00:24:00,440
És cert nombre de passos
això és un factor de n,

530
00:24:00,440 --> 00:24:02,270
pel que podríem expressar això com aquesta.

531
00:24:02,270 --> 00:24:05,550
I aquí és on ara anem a Punt a la
part posterior del nostre llibre de text de matemàtiques de l'escola secundària

532
00:24:05,550 --> 00:24:10,290
estem que la recurrència en última instància
acaba igualant això, n log n vegades,

533
00:24:10,290 --> 00:24:12,530
si vostè fa realment fora
els càlculs de manera més formal.

534
00:24:12,530 --> 00:24:13,950
>> Així que això és només dos punts de vista.

535
00:24:13,950 --> 00:24:17,500
Una numèricament amb un
dur amb codi d'exemple representatiu

536
00:24:17,500 --> 00:24:21,140
amb vuit números i una més
cop d'ull general a la forma en què vam arribar allà.

537
00:24:21,140 --> 00:24:25,670
Però el que és realment interessant aquí
és, de nou, aquesta noció de ciclisme.

538
00:24:25,670 --> 00:24:26,900
No estic fent servir per bucles.

539
00:24:26,900 --> 00:24:29,860
Sóc una mena de definició
alguna cosa en termes de si mateix,

540
00:24:29,860 --> 00:24:31,950
no només amb aquesta
funció matemàtica,

541
00:24:31,950 --> 00:24:34,860
sinó també en termes d'aquest pseudo codi.

542
00:24:34,860 --> 00:24:38,260
Aquesta pseudo codi és recursiva
en què dos de les seves línies

543
00:24:38,260 --> 00:24:42,310
està essencialment dient que es vagi
utilitzi a si mateix per resoldre un menor

544
00:24:42,310 --> 00:24:45,400
problema de mida més petita,
i després una altra vegada i una altra

545
00:24:45,400 --> 00:24:48,820
i una altra vegada fins que reduir gradualment cap
a aquest anomenat cas base.

546
00:24:48,820 --> 00:24:52,810
>> Així que anem a dibuixar una realitat més convincent
per portar de la següent manera.

547
00:24:52,810 --> 00:24:58,420
Déjame anar a gedit i prenc un
veure algunes de codi font actual,

548
00:24:58,420 --> 00:24:59,930
en particular, aquest exemple aquí.

549
00:24:59,930 --> 00:25:03,709
Sigma 0, que aparentment afegeix
els números de l'u al n.

550
00:25:03,709 --> 00:25:05,750
Així que anem a veure el que és familiar
i desconegut aquí.

551
00:25:05,750 --> 00:25:08,690
En primer lloc tenim un parell de
inclou, així que res de nou.

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

553
00:25:09,190 --> 00:25:11,370
Estic una mica confusa en
això després de pocs dies,

554
00:25:11,370 --> 00:25:13,790
però ho vam dir 1
prototip d'una funció és?

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

556
00:25:15,099 --> 00:25:16,015
AUDIÈNCIA: [inaudible].

557
00:25:16,015 --> 00:25:16,905
ALTAVEU 1: Què és això?

558
00:25:16,905 --> 00:25:17,800
AUDIÈNCIA: Anunciem ella.

559
00:25:17,800 --> 00:25:18,883
ALTAVEU 1: Anunciem ella.

560
00:25:18,883 --> 00:25:22,290
Així que vostè està ensenyant Clang, hey,
no l'aplicació real d'això encara,

561
00:25:22,290 --> 00:25:25,740
però en algun lloc d'aquest arxiu, presumiblement,
serà una funció anomenada què?

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
I això és només una promesa que
que tindrà aquest aspecte.

565
00:25:30,540 --> 00:25:33,720
Va a prendre un sencer com
Entrada-- i puc ser més explícit

566
00:25:33,720 --> 00:25:36,570
i dir int n --i és
va a tornar un int,

567
00:25:36,570 --> 00:25:39,900
però mig punt i coma, mm, arribaré al voltant de
a la implementació d'aquest una mica més tard.

568
00:25:39,900 --> 00:25:40,989
Una vegada més, Clang és tonto.

569
00:25:40,989 --> 00:25:43,280
Només va a saber el que
li dius que a dalt a baix,

570
00:25:43,280 --> 00:25:45,765
així que hem de donar almenys
és un indici del que està per venir.

571
00:25:45,765 --> 00:25:47,330
>> Ara donem una ullada a principal aquí.

572
00:25:47,330 --> 00:25:50,040
Anem a desplaçar-se fins aquí i
veure el principal està fent.

573
00:25:50,040 --> 00:25:53,780
No és que a llarg d'una funció, i
de fet, el constructe aquí és familiar.

574
00:25:53,780 --> 00:25:57,590
Declaro una variable n, i després
Em molesten a l'usuari una vegada i una altra

575
00:25:57,590 --> 00:26:01,880
per a un enter positiu utilitzant getInt,
i única sortida d'aquest bucle

576
00:26:01,880 --> 00:26:03,280
una vegada que l'usuari ha complert.

577
00:26:03,280 --> 00:26:05,670
Do While, que hem utilitzat per
molestar a l'usuari d'aquesta manera.

578
00:26:05,670 --> 00:26:06,670
Ara això és interessant.

579
00:26:06,670 --> 00:26:08,510
Declaro 1 int anomenada "resposta".

580
00:26:08,510 --> 00:26:11,420
Assigno que el valor de retorn
d'una funció anomenada "sigma".

581
00:26:11,420 --> 00:26:15,200
No sé el que això fa encara, però
Recordo que declara que fa un moment.

582
00:26:15,200 --> 00:26:18,310
I llavors jo estic passant al
valor que l'usuari va escriure en, n,

583
00:26:18,310 --> 00:26:20,420
i després informe la resposta.

584
00:26:20,420 --> 00:26:22,260
Bé, anem a retrocedir
només per un moment.

585
00:26:22,260 --> 00:26:28,620
Seguirem endavant en aquest directori, fan
sigma 0, i en realitat executar aquest programa

586
00:26:28,620 --> 00:26:30,490
i veure què passa.

587
00:26:30,490 --> 00:26:35,930
Així que si segueixo endavant i córrer
aquest programa, ./sigma-0,

588
00:26:35,930 --> 00:26:40,139
i escric en un positiu
sencer com dos, Sigma,

589
00:26:40,139 --> 00:26:43,180
com el símbol grec ho indica, és només
va a sumar tots els números de l'

590
00:26:43,180 --> 00:26:44,320
zero en un màxim de dos.

591
00:26:44,320 --> 00:26:46,560
Així 0 més 1 més 2.

592
00:26:46,560 --> 00:26:48,830
Així que espero que aquest ha donar-me 3.

593
00:26:48,830 --> 00:26:49,750
Això és tot el que està fent.

594
00:26:49,750 --> 00:26:52,690
I de la mateixa manera, si se m'acaba el missatge
i li dono el número tres,

595
00:26:52,690 --> 00:26:56,721
això és 3 més 2, pel que és
5, més 1 em hauria de donar juny.

596
00:26:56,721 --> 00:26:59,470
I després, si em poso molt boig i
comença a escriure en nombres més grans,

597
00:26:59,470 --> 00:27:01,290
em hauria de donar
sumes cada vegada més grans.

598
00:27:01,290 --> 00:27:02,250
Així que això és tot.

599
00:27:02,250 --> 00:27:04,010
>> Llavors, què sigma sembla?

600
00:27:04,010 --> 00:27:05,430
Bé, és bastant senzill.

601
00:27:05,430 --> 00:27:08,940
És la forma en què podríem haver implementat
això per a l'últim parell de setmanes.

602
00:27:08,940 --> 00:27:11,120
"Int" serà el tipus de retorn.

603
00:27:11,120 --> 00:27:14,330
Sigma és el nom, i es necessita
una variable m en lloc de n.

604
00:27:14,330 --> 00:27:15,940
Canviaré que a sobre de la tapa.

605
00:27:15,940 --> 00:27:17,340
Llavors això és només una prova de seny.

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

607
00:27:18,430 --> 00:27:19,950
Veurem per què en un moment.

608
00:27:19,950 --> 00:27:24,220
Ara declaro altra variable,
suma, inicialitzar a zero.

609
00:27:24,220 --> 00:27:28,140
Llavors tinc aquest bucle For
iteració, pel que sembla, per a major claredat,

610
00:27:28,140 --> 00:27:33,810
des de i = 1 fins a en un = m, que és
qualsevol que sigui l'usuari va escriure en, i després em

611
00:27:33,810 --> 00:27:35,690
incrementar la suma d'aquesta manera.

612
00:27:35,690 --> 00:27:37,360
I a continuació, tornar la suma.

613
00:27:37,360 --> 00:27:38,440
>> Així que un parell de preguntes.

614
00:27:38,440 --> 00:27:42,370
Un, em diuen al meu comentari que aquesta
evita el risc d'un bucle infinit.

615
00:27:42,370 --> 00:27:45,620
Per què hauria de passar en un nombre negatiu
induir, potencialment, un bucle infinit?

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

617
00:27:49,396 --> 00:27:51,290
>> AUDIÈNCIA: Vostè mai arribarà a m.

618
00:27:51,290 --> 00:27:52,880
>> ALTAVEU 1: Mai arribar m.

619
00:27:52,880 --> 00:27:55,880
Però m es passa, així que anem a
considerar un exemple senzill.

620
00:27:55,880 --> 00:27:58,510
Si m es passa pel
usuari com un negatiu.

621
00:27:58,510 --> 00:28:00,059
Independentment de principal.

622
00:28:00,059 --> 00:28:01,850
Principal ens protegeix de
això també, així que estic sol

623
00:28:01,850 --> 00:28:04,680
sent molt anal amb
sigma també assegurar-

624
00:28:04,680 --> 00:28:06,540
que l'entrada no pot ser negatiu.

625
00:28:06,540 --> 00:28:10,130
Així que si m és negatiu,
una mena de cosa negativa.

626
00:28:10,130 --> 00:28:11,930
¿Què passarà?

627
00:28:11,930 --> 00:28:14,390
Bé, va a
que aquest s'inicia a un,

628
00:28:14,390 --> 00:28:19,060
i després em serà
menys d'o igual a m?

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

630
00:28:24,130 --> 00:28:24,765
>> Col·locar.

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

632
00:28:26,930 --> 00:28:29,370
Això fue-- no anem,
anem a Nix aquesta història.

633
00:28:29,370 --> 00:28:32,780
Jo no vaig demanar aquesta pregunta, perquè
el risc que al·ludeixo

634
00:28:32,780 --> 00:28:38,360
no passarà perquè i és
sempre va ser major Acceptar què--,

635
00:28:38,360 --> 00:28:39,871
Em retracte de què es tracti.

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

637
00:28:40,370 --> 00:28:42,030
Anem a centrar-nos només en aquesta part aquí.

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

639
00:28:44,210 --> 00:28:48,830
Per què em declaro alguns
fora del bucle?

640
00:28:48,830 --> 00:28:52,010
Avís sobre la línia 49 no tinc
i declarada dins del bucle,

641
00:28:52,010 --> 00:28:54,950
però en línia 48 que he
declarat alguns de fora.

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

643
00:28:55,695 --> 00:28:56,611
AUDIÈNCIA: [inaudible].

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

645
00:28:58,734 --> 00:28:59,400
ALTAVEU 1: Segur.

646
00:28:59,400 --> 00:29:03,360
Així que, abans de res, jo per descomptat no ho faig
voler declarar i inicialitzar suma

647
00:29:03,360 --> 00:29:06,130
a zero a l'interior de la
bucle en cada iteració,

648
00:29:06,130 --> 00:29:09,370
perquè això aniria en contra de la claredat
propòsit de resumir els números.

649
00:29:09,370 --> 00:29:11,770
M'agradaria mantenir el canvi
el valor a zero.

650
00:29:11,770 --> 00:29:17,992
I també, el que és una altra més arcana
raó d'aquesta mateixa decisió de disseny?

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

652
00:29:18,954 --> 00:29:20,279
>> AUDIÈNCIA: [inaudible].

653
00:29:20,279 --> 00:29:21,070
ALTAVEU 1: Exactament.

654
00:29:21,070 --> 00:29:24,060
Vull accedir-hi fora
del bucle massa en quina línia?

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

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

657
00:29:26,400 --> 00:29:29,910
I sobre la base de la nostra regla d'or
des de fa un parell de conferències,

658
00:29:29,910 --> 00:29:33,680
variables que estan en l'àmbit, de veritat, a la
claus que ells abasten.

659
00:29:33,680 --> 00:29:38,190
Així que si no declaro suma dins
d'aquestes claus exteriors,

660
00:29:38,190 --> 00:29:40,250
Jo no ho puc fer servir en la línia 53.

661
00:29:40,250 --> 00:29:43,160
Dit d'una altra manera, si jo vaig declarar
suma aquí, o fins i tot dins la

662
00:29:43,160 --> 00:29:45,410
Per bucle, no podia accedir-hi en el 53.

663
00:29:45,410 --> 00:29:47,150
La variable efectivament s'hauria anat.

664
00:29:47,150 --> 00:29:48,579
Així que un parell de raons allà.

665
00:29:48,579 --> 00:29:50,370
Però ara anem a tornar
i veure què passa.

666
00:29:50,370 --> 00:29:51,730
Així sigma es diu.

667
00:29:51,730 --> 00:29:55,640
Se suma 1 més 2 o 1 més 2
més 3, i després retorna el valor,

668
00:29:55,640 --> 00:29:59,660
emmagatzema en resposta, i printf aquí
és pel que estic veient a la pantalla.

669
00:29:59,660 --> 00:30:03,079
Així que això és el que anem a trucar a un procés iteratiu
enfocament, on iteració només

670
00:30:03,079 --> 00:30:03,870
significa utilitzar un bucle.

671
00:30:03,870 --> 00:30:06,900
Un bucle For, un bucle while, un Do While
bucle, simplement fer alguna cosa nova

672
00:30:06,900 --> 00:30:08,380
i una i altra vegada.

673
00:30:08,380 --> 00:30:13,505
>> Però sigma és una espècie de funció ordenada en
que podria posar en pràctica de manera diferent.

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

675
00:30:14,620 --> 00:30:19,120
Què passa amb això, que
només per ser una mena de fresc,

676
00:30:19,120 --> 00:30:21,880
permetin-me realment desfaig
d'una gran quantitat de distracció

677
00:30:21,880 --> 00:30:24,380
perquè aquesta funció
és realment molt simple.

678
00:30:24,380 --> 00:30:27,780
Anem a reduir gradualment cap avall just
els seus quatre línies bàsiques

679
00:30:27,780 --> 00:30:30,410
i desfer-se de tota la
comentaris i claus.

680
00:30:30,410 --> 00:30:34,334
Aquesta és una espècie de lucinant
implementació alternativa.

681
00:30:34,334 --> 00:30:37,250
Està bé, potser no lucinant,
però és una mica més sexy, d'acord,

682
00:30:37,250 --> 00:30:39,920
veure aquesta molt més succinta.

683
00:30:39,920 --> 00:30:43,120
Amb només quatre línies de codi,
La primera vegada que tinc aquesta prova de seny.

684
00:30:43,120 --> 00:30:45,732
Si m és menor que o igual a
zero, sigma no té sentit.

685
00:30:45,732 --> 00:30:48,190
Només se suposa que és en
aquest cas per als nombres positius,

686
00:30:48,190 --> 00:30:50,340
així que només vaig a
tornar zero arbitràriament

687
00:30:50,340 --> 00:30:53,210
de manera que almenys tenim
alguns anomenat cas base.

688
00:30:53,210 --> 00:30:54,430
>> Però aquí hi ha la bellesa.

689
00:30:54,430 --> 00:30:59,930
La totalitat d'aquesta idea, afegint la
números de l'1 al n, m, o en aquest cas,

690
00:30:59,930 --> 00:31:02,630
es pot fer per la classe de passar la pilota.

691
00:31:02,630 --> 00:31:04,947
Bé, quina és la suma d'1 a m?

692
00:31:04,947 --> 00:31:05,780
Bé, saps què?

693
00:31:05,780 --> 00:31:11,949
És el mateix que la suma de m
més la suma d'1 m d'almenys 1.

694
00:31:11,949 --> 00:31:12,740
Doncs saps què?

695
00:31:12,740 --> 00:31:13,940
Què hi ha de sigma m almenys 1?

696
00:31:13,940 --> 00:31:17,860
Bé, si segueix aquest tipus de
lògicament, és el mateix que m almenys 1

697
00:31:17,860 --> 00:31:21,415
a més de sigma m almenys 2.

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

699
00:31:22,480 --> 00:31:26,012
Així que vostè pot tipus de sol--
això és com, si ets

700
00:31:26,012 --> 00:31:28,220
tractant de molestar a un amic
i et fan una pregunta,

701
00:31:28,220 --> 00:31:31,344
que classe de respondre amb una pregunta,
vostè pot tipus de mantenir fugir d'estudi.

702
00:31:31,344 --> 00:31:34,560
Però el que és clau és que si es manté
fent la pregunta més i més petita

703
00:31:34,560 --> 00:31:36,910
i més petit, vostè és
no demanar el que és sigma

704
00:31:36,910 --> 00:31:39,116
de n, el que és de sigma
n, el que és sigma de n?

705
00:31:39,116 --> 00:31:40,990
Li estàs preguntant quin és
sigma de n, el que és sigma

706
00:31:40,990 --> 00:31:42,839
n de menys 1, el que és de sigma n almenys 2?

707
00:31:42,839 --> 00:31:44,880
Eventualment la seva pregunta
serà què?

708
00:31:44,880 --> 00:31:50,250
Què és la sigma d'un o
zero, un valor molt petit,

709
00:31:50,250 --> 00:31:52,220
i tan aviat com es
aconseguir que, al seu amic,

710
00:31:52,220 --> 00:31:54,350
no va a demanar
la mateixa pregunta de nou,

711
00:31:54,350 --> 00:31:55,975
només direm, oh és zero.

712
00:31:55,975 --> 00:31:58,490
Hem acabat de jugar aquest tipus
de joc cíclic estúpid.

713
00:31:58,490 --> 00:32:02,950
>> Així que la recursivitat és l'acte en la programació
d'una funció que es fa dir.

714
00:32:02,950 --> 00:32:06,630
Aquest programa, quan es compila i s'executa, és
es comportarà de la mateixa manera,

715
00:32:06,630 --> 00:32:09,620
però el que és clau és que a l'interior
d'una funció anomenada sigma,

716
00:32:09,620 --> 00:32:13,150
hi ha una línia de codi en el qual
que anomenem nosaltres mateixos,

717
00:32:13,150 --> 00:32:14,980
que normalment seria dolent.

718
00:32:14,980 --> 00:32:21,160
Per exemple, què passa si jo primer
compilat aquesta, així que sigma--

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

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

721
00:32:25,050 --> 00:32:27,690
Enter positiu, si us plau, 50 1275.

722
00:32:27,690 --> 00:32:30,810
Així que el que la funció sembla
ser, basat en una prova, correcta.

723
00:32:30,810 --> 00:32:34,917
Però el que si em fa una mica perillós
i eliminar l'anomenat cas base,

724
00:32:34,917 --> 00:32:37,750
i acabo de dir, bé, jo només estic fent
això més complicat del que és.

725
00:32:37,750 --> 00:32:42,450
Anem a computar el sigma
prenent m i després afegint

726
00:32:42,450 --> 00:32:44,564
en sigma de m menys un?

727
00:32:44,564 --> 00:32:45,980
Bé, què passarà aquí?

728
00:32:45,980 --> 00:32:47,140
Anem a allunyar.

729
00:32:47,140 --> 00:32:52,920
Anem a tornar a compilar el programa,
guardar, tornar a compilar el programa,

730
00:32:52,920 --> 00:33:00,450
i llavors llest ./sigma-1 el zoom,
introduir enter positiu favor, 50.

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

732
00:33:02,180 --> 00:33:04,430
Quants de vostès estan disposats
a confessar a veure això?

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

734
00:33:04,950 --> 00:33:06,690
Així que això pot succeir per
una sèrie de raons,

735
00:33:06,690 --> 00:33:09,148
i, francament, aquesta setmana estem
a punt de donar-li més d'ells.

736
00:33:09,148 --> 00:33:11,780
Però en aquest cas, proveu
per raonar cap enrere

737
00:33:11,780 --> 00:33:14,430
el que podria haver passat aquí?

738
00:33:14,430 --> 00:33:17,400
Decisió de segmentació, vam dir última
temps, es refereix a un segment de memòria.

739
00:33:17,400 --> 00:33:18,690
Una cosa dolent ha passat.

740
00:33:18,690 --> 00:33:21,550
Però què era
mecànicament que va sortir malament

741
00:33:21,550 --> 00:33:25,000
aquí per la meva retirada
que l'anomenat cas base,

742
00:33:25,000 --> 00:33:26,870
on vaig tornar un valor codificat?

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

744
00:33:28,970 --> 00:33:30,460
Què creus que va sortir malament?

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

746
00:33:31,219 --> 00:33:32,135
>> AUDIÈNCIA: [inaudible].

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

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

749
00:33:36,970 --> 00:33:37,550
Bona pregunta.

750
00:33:37,550 --> 00:33:39,508
Així que la mida del nombre
que estava resumint

751
00:33:39,508 --> 00:33:41,920
posar tan gran que supera
la mida de l'espai de memòria.

752
00:33:41,920 --> 00:33:44,640
Bona idea, però no fonamentalment
causarà un accident.

753
00:33:44,640 --> 00:33:48,230
Això podria causar desbordament de sencers,
on els bits només voltegen

754
00:33:48,230 --> 00:33:51,760
i després confonem 1 molt gran
nombre com per un nombre negatiu,

755
00:33:51,760 --> 00:33:53,260
però que en si no va a causar un accident.

756
00:33:53,260 --> 00:33:55,509
Com que al final de l'
dia 1 int és encara 32 bits.

757
00:33:55,509 --> 00:33:57,640
No va a
robar accidentalment una mica 33a.

758
00:33:57,640 --> 00:33:58,431
Però un bon pensament.

759
00:33:58,431 --> 00:33:58,984
Sí.

760
00:33:58,984 --> 00:33:59,900
>> AUDIÈNCIA: [inaudible].

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

762
00:34:00,551 --> 00:34:02,300
ALTAVEU 1: El mètode
mai deixa de córrer,

763
00:34:02,300 --> 00:34:06,658
i vet aquí que es diu de nou
i una i altra vegada i una altra

764
00:34:06,658 --> 00:34:08,449
i una altra vegada, i cap d'
aquestes funcions cada vegada

765
00:34:08,449 --> 00:34:13,310
acabar perquè la seva única línia d'
codi si mateixa diu una i una altra vegada

766
00:34:13,310 --> 00:34:14,219
i una altra vegada.

767
00:34:14,219 --> 00:34:16,080
I el que és realment
passant aquí, i ara ens

768
00:34:16,080 --> 00:34:18,100
pot dibuixar aquest tipus d'il • lustracions.

769
00:34:18,100 --> 00:34:20,899
Déjame anar a un
foto per un moment.

770
00:34:20,899 --> 00:34:22,940
Aquesta és una imatge, que
eventualment donar cos a

771
00:34:22,940 --> 00:34:26,336
amb més detall, del que està passant
dins de la memòria de l'equip.

772
00:34:26,336 --> 00:34:28,460
I resulta que en
la part inferior d'aquesta imatge

773
00:34:28,460 --> 00:34:29,709
és una cosa que es diu la pila.

774
00:34:29,709 --> 00:34:31,920
Es tracta d'un tros de
memòria, un tros de memòria RAM,

775
00:34:31,920 --> 00:34:33,920
això és només utilitzen qualsevol moment
una funció és cridada.

776
00:34:33,920 --> 00:34:36,239
Cada vegada que, un programador,
cridar a una funció,

777
00:34:36,239 --> 00:34:38,860
el sistema operatiu, com
Mac OS, Windows, o Linux,

778
00:34:38,860 --> 00:34:41,920
agafa un grapat de bytes, potser un
pocs kilobytes, potser pocs megabytes

779
00:34:41,920 --> 00:34:44,590
de la memòria, els lliura
a vostè i, a continuació, li permet

780
00:34:44,590 --> 00:34:47,650
executa la seva funció utilitzant
el variables que vostè necessita.

781
00:34:47,650 --> 00:34:50,699
I si després trucar a un altre
la funció i l'altra funció,

782
00:34:50,699 --> 00:34:53,590
li dóna una altra llesca de memòria
i una altra llesca de memòria.

783
00:34:53,590 --> 00:34:57,090
>> I de fet, si aquestes safates verds
de Annenberg representar aquesta memòria,

784
00:34:57,090 --> 00:34:59,870
això és el que passa el primer
vegada que es cridi a la funció sigma.

785
00:34:59,870 --> 00:35:04,510
És com posar una safata com aquesta
en el que és inicialment una pila buida.

786
00:35:04,510 --> 00:35:07,142
Però llavors, si aquesta safata
diu a si mateix, per així dir-ho,

787
00:35:07,142 --> 00:35:08,850
trucar a una altra instància
de sigma, això és

788
00:35:08,850 --> 00:35:11,640
com preguntar el sistema operatiu,
ooh, necessitarà una mica més de memòria,

789
00:35:11,640 --> 00:35:12,520
dóna'm això.

790
00:35:12,520 --> 00:35:14,840
I llavors s'apilen en la part superior.

791
00:35:14,840 --> 00:35:18,030
Però el que és clau aquí és que
la primera safata està encara allà,

792
00:35:18,030 --> 00:35:20,620
perquè ell va invocar aquesta segona safata.

793
00:35:20,620 --> 00:35:23,500
Ara mentrestant, sigma diuen sigma,
això és com demanar més memòria.

794
00:35:23,500 --> 00:35:25,830
Obté apilats per aquí.

795
00:35:25,830 --> 00:35:29,350
sigma cridar sigma, aquesta és una altra
safata que aconsegueix apilats a aquí.

796
00:35:29,350 --> 00:35:32,942
I si segueixes fent això,
finalment, una mena de mapa d'aquesta visual

797
00:35:32,942 --> 00:35:35,525
a aquesta carta, el que va a
ocórrer amb la pila de safates?

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

799
00:35:37,480 --> 00:35:41,160
Es va a excedir la quantitat
de memòria l'equip té.

800
00:35:41,160 --> 00:35:45,790
I tan aviat com aquesta safata verda
excedeix la línia horitzontal

801
00:35:45,790 --> 00:35:49,410
per sobre de la pila i per sobre d'aquesta paraula munt,
que anem a tornar en el futur,

802
00:35:49,410 --> 00:35:50,410
això és una mala cosa.

803
00:35:50,410 --> 00:35:52,810
El munt és una diferent
segment de la memòria,

804
00:35:52,810 --> 00:35:55,190
i si deixes que aquests
safates de pila i pila en,

805
00:35:55,190 --> 00:35:57,800
vostè va a superar
el seu propi segment de la memòria,

806
00:35:57,800 --> 00:36:00,420
i un programa està de fet va a estavellar.

807
00:36:00,420 --> 00:36:02,930
>> Ara com un part, aquesta idea
de la recursió, per tant,

808
00:36:02,930 --> 00:36:06,500
pot conduir a problemes clarament, però
no és necessàriament una mala cosa.

809
00:36:06,500 --> 00:36:08,840
A causa de considerar, després d'
tot, i potser com--

810
00:36:08,840 --> 00:36:11,700
això pren algun temps acostumar-
a --¿Com elegant o el simple

811
00:36:11,700 --> 00:36:14,890
que l'aplicació de sigma va ser.

812
00:36:14,890 --> 00:36:17,440
I no utilitzarem
recursivitat gairebé res en CS50,

813
00:36:17,440 --> 00:36:20,780
però en CS51, i realment qualsevol classe
on es manipulen estructures de dades

814
00:36:20,780 --> 00:36:23,640
com arbres o arbres de la família,
que tenen certa jerarquia,

815
00:36:23,640 --> 00:36:26,000
és super, super útil.

816
00:36:26,000 --> 00:36:29,750
Ara, com un a part, de manera que vostè
com a aspirants a científics de la computació

817
00:36:29,750 --> 00:36:33,180
estan familiaritzats amb alguns de Google
bromes internes, si vostè va a Google

818
00:36:33,180 --> 00:36:36,345
i vostè mira cap amunt el que és la
definició de, per exemple, la recursivitat, escriviu.

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
Com acotació al marge, em vaig aturar uns pocs.

822
00:36:42,670 --> 00:36:45,470
Això va ser com de 10 minuts de
la dilació d'aquest matí.

823
00:36:45,470 --> 00:36:52,890
Si també Google "torta" avís
inclinant el cap slightly--

824
00:36:52,890 --> 00:36:55,120
i llavors aquest és potser
més atroç de tots

825
00:36:55,120 --> 00:36:57,286
ja que algú va passar com
el seu dia de l'aplicació d'aquesta

826
00:36:57,286 --> 00:36:59,880
alguns anys ago-- anem.

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

828
00:37:01,140 --> 00:37:04,540
Oh, espera-- això és un error.

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

830
00:37:08,410 --> 00:37:11,410
>> Així que s'executa en un dels
majors llocs web del món

831
00:37:11,410 --> 00:37:13,510
són aquests estúpids petits ous de Pasqua.

832
00:37:13,510 --> 00:37:16,690
Probablement consumeixen una
nombre no trivial de línies de codi

833
00:37:16,690 --> 00:37:19,280
només perquè puguem tenir
petites coses divertides com aquestes.

834
00:37:19,280 --> 00:37:22,140
Però almenys ara vostè aconsegueix
algunes d'aquestes bromes.

835
00:37:22,140 --> 00:37:28,330
>> Ara donem una ullada a alguns dels
blanc es troba que hem estat dient en els últims temps,

836
00:37:28,330 --> 00:37:30,707
i començar a pelar
algunes capes tècnicament

837
00:37:30,707 --> 00:37:32,790
de manera que vostè realment entén
el que ha estat passant

838
00:37:32,790 --> 00:37:34,860
i es pot entendre
algunes de les amenaces,

839
00:37:34,860 --> 00:37:38,060
com Shellshock, que
Ara han començat a convertir-se en

840
00:37:38,060 --> 00:37:41,110
a l'avantguarda de tot el món de
atenció, almenys en els mitjans de comunicació.

841
00:37:41,110 --> 00:37:45,810
Així que aquí és una funció molt simple
que retorna res, el buit.

842
00:37:45,810 --> 00:37:46,790
El seu nom és d'intercanvi.

843
00:37:46,790 --> 00:37:50,880
Es necessita en dues variables
i no torna res.

844
00:37:50,880 --> 00:37:52,260
Presa en ai b.

845
00:37:52,260 --> 00:37:53,337
Així que una demostració ràpida.

846
00:37:53,337 --> 00:37:54,170
Vam portar aquests.

847
00:37:54,170 --> 00:37:56,100
Pot ser que també prengui una mica
trencar aquí per un moment

848
00:37:56,100 --> 00:37:57,250
i tenir una mica d'alguna cosa per beure.

849
00:37:57,250 --> 00:38:00,120
Si a algú no li importaria unir-se
em fins aquí per un moment.

850
00:38:00,120 --> 00:38:01,830
Què tal si a la camisa marró?

851
00:38:01,830 --> 00:38:02,335
Anem amunt.

852
00:38:02,335 --> 00:38:04,060

853
00:38:04,060 --> 00:38:05,260
Només la d'avui.

854
00:38:05,260 --> 00:38:06,251
Gràcies, però.

855
00:38:06,251 --> 00:38:08,000
Molt bé, i tenim
ve que aquí?

856
00:38:08,000 --> 00:38:08,660
Quin és el teu nom?

857
00:38:08,660 --> 00:38:09,360
>> ALTAVEU 4: Laura.

858
00:38:09,360 --> 00:38:09,740
>> ALTAVEU 1: Laura.

859
00:38:09,740 --> 00:38:10,370
Anem amunt.

860
00:38:10,370 --> 00:38:11,460

861
00:38:11,460 --> 00:38:13,850
Així que la Laura, molt simple desafiament d'avui.

862
00:38:13,850 --> 00:38:14,704

863
00:38:14,704 --> 00:38:15,370
Encantat de conèixer jo.

864
00:38:15,370 --> 00:38:16,410

865
00:38:16,410 --> 00:38:16,910
Bé.

866
00:38:16,910 --> 00:38:21,179
Així que tenim una mica de llet aquí i
tenim una mica de suc de taronja per aquí

867
00:38:21,179 --> 00:38:23,345
i algunes tasses que ens
pres d'Annenberg avui.

868
00:38:23,345 --> 00:38:24,178
>> ALTAVEU 4: Borrowed.

869
00:38:24,178 --> 00:38:27,240
ALTAVEU 1: I seguirà endavant
i li donarà la meitat d'un got d'això.

870
00:38:27,240 --> 00:38:28,250

871
00:38:28,250 --> 00:38:28,800
Bé.

872
00:38:28,800 --> 00:38:30,750
I li donarem la meitat
un got de llet.

873
00:38:30,750 --> 00:38:31,905

874
00:38:31,905 --> 00:38:35,890
Ah, i perquè pugui
recordi com era això,

875
00:38:35,890 --> 00:38:38,860
Vaig recordar de portar
això i en l'actualitat.

876
00:38:38,860 --> 00:38:42,030

877
00:38:42,030 --> 00:38:42,530
Bé.

878
00:38:42,530 --> 00:38:45,470
Si no t'importa, anem a veure, ens
pot posar-los en les seves pròpies ulleres

879
00:38:45,470 --> 00:38:46,560
si vols.

880
00:38:46,560 --> 00:38:48,710
Aquest serà el món des dels ulls de Laura.

881
00:38:48,710 --> 00:38:49,210
Bé.

882
00:38:49,210 --> 00:38:53,820
Així que el seu objectiu, li van donar dues tasses de
líquid aquí, llet i suc de taronja,

883
00:38:53,820 --> 00:38:58,370
s'intercanviï els dos continguts de manera que el
suc de taronja va a la tassa de llet

884
00:38:58,370 --> 00:39:00,710
i la llet entra en
la tassa de suc de taronja.

885
00:39:00,710 --> 00:39:02,359
>> ALTAVEU 4: Tinc una altra tassa?

886
00:39:02,359 --> 00:39:05,650
ALTAVEU 1: Estic tan bo que ho preguntes, encara que
hauria estat molt millor material d'arxiu

887
00:39:05,650 --> 00:39:06,710
si no haguessis preguntat.

888
00:39:06,710 --> 00:39:10,620
Però sí, podem oferir-li una tercera
got que està buida, és clar.

889
00:39:10,620 --> 00:39:11,120
Bé.

890
00:39:11,120 --> 00:39:12,300
Així que canviar el contingut allà.

891
00:39:12,300 --> 00:39:16,100

892
00:39:16,100 --> 00:39:17,050
Molt agradable.

893
00:39:17,050 --> 00:39:20,390

894
00:39:20,390 --> 00:39:21,305
Molt bona.

895
00:39:21,305 --> 00:39:23,121

896
00:39:23,121 --> 00:39:24,745
Estàs fent això amb molta cura.

897
00:39:24,745 --> 00:39:26,970

898
00:39:26,970 --> 00:39:28,655
I el tercer pas.

899
00:39:28,655 --> 00:39:30,390

900
00:39:30,390 --> 00:39:31,350
Bé.

901
00:39:31,350 --> 00:39:31,930
Excel · lent.

902
00:39:31,930 --> 00:39:33,930
Un gran aplaudiment
seria bo per a Laura.

903
00:39:33,930 --> 00:39:36,500

904
00:39:36,500 --> 00:39:37,000
Bé.

905
00:39:37,000 --> 00:39:40,790
Tenim un petit regal de comiat
per a vostè, però vull aprofitar aquests.

906
00:39:40,790 --> 00:39:42,620
Moltes gràcies.

907
00:39:42,620 --> 00:39:46,170
Així, un exemple senzill, però,
per demostrar que si ho fa

908
00:39:46,170 --> 00:39:48,300
voler canviar el contingut
de dos contenidors,

909
00:39:48,300 --> 00:39:52,360
o anem a anomenar les variables,
necessites una mica d'emmagatzematge temporal

910
00:39:52,360 --> 00:39:56,710
per organitzar un dels continguts en la
que en realitat es pot fer el canvi.

911
00:39:56,710 --> 00:40:01,790
Així que de fet, el codi font aquí a
C és representant d'exactament això.

912
00:40:01,790 --> 00:40:06,340
Si el suc de taronja era una i la llet
era b, i volíem canviar els dos,

913
00:40:06,340 --> 00:40:08,990
vostè podria intentar alguna cosa creativa
mitjançant l'abocament d'una a l'altra,

914
00:40:08,990 --> 00:40:11,031
però que probablement no ho faria
acabar particularment bé.

915
00:40:11,031 --> 00:40:15,260
I pel que utilitzar una tassa tercera, anomenada
que tmp, T-M-P per convenció,

916
00:40:15,260 --> 00:40:19,370
i posar el contingut del
DO que, a continuació, intercanviar una tassa,

917
00:40:19,370 --> 00:40:22,610
a continuació, posar la DO en el
tassa original, d'aquesta manera

918
00:40:22,610 --> 00:40:25,320
aconseguir, exactament com
Laura va fer, el bescanvi.

919
00:40:25,320 --> 00:40:26,850
>> Així que farem exactament això.

920
00:40:26,850 --> 00:40:30,110
Déjame anar endavant i obrir
fins a un exemple que és

921
00:40:30,110 --> 00:40:32,720
diu en realitat "no
canviar, "perquè això no és

922
00:40:32,720 --> 00:40:36,180
com un simple fet com vostè podria pensar.

923
00:40:36,180 --> 00:40:41,190
Així que en aquest programa, observi que
Estic usant stdio.h, el nostre vell amic.

924
00:40:41,190 --> 00:40:43,130
Tinc el prototip
per swap allà dalt, que

925
00:40:43,130 --> 00:40:45,450
significa l'aplicació de
probablement per sota,

926
00:40:45,450 --> 00:40:48,050
i anem a veure el que aquest principal
programa farà per mi.

927
00:40:48,050 --> 00:40:52,020
La primera vegada que declaro int x
un, i int i aconsegueix dues.

928
00:40:52,020 --> 00:40:54,930
Així que pensar en aquells com DO
i llet, respectivament.

929
00:40:54,930 --> 00:40:57,100
I llavors jo només tinc un
printf dient x és aquesta

930
00:40:57,100 --> 00:41:00,120
i i és això, perquè jo pugui
veure visualment el que està passant.

931
00:41:00,120 --> 00:41:03,810
Després he printf reclamant
que estic intercanviant els dos,

932
00:41:03,810 --> 00:41:07,100
i després imprimeixo 1
afirmen que estan intercanviats,

933
00:41:07,100 --> 00:41:09,300
i jo imprimeixo x i i una altra.

934
00:41:09,300 --> 00:41:13,010
Així que aquí a intercanvi és
exactament el que va fer Laura,

935
00:41:13,010 --> 00:41:16,240
i és exactament el que vam veure en
la pantalla fa un moment.

936
00:41:16,240 --> 00:41:19,380
>> Així que seguirem endavant i
molt decebut.

937
00:41:19,380 --> 00:41:24,690
No ens swap, i executar sense swap,
fer zoom sobre la sortida d'aquí.

938
00:41:24,690 --> 00:41:28,320
Introduïu x és 1, i és 2, intercanviant intercanviat.

939
00:41:28,320 --> 00:41:32,700
x és encara 1, i i és encara 2.

940
00:41:32,700 --> 00:41:37,630
Així que, encara que, francament, això sembla
exactament igual, encara que de forma més tècnica,

941
00:41:37,630 --> 00:41:40,730
Laura ho va fer, no sembla funcionar.

942
00:41:40,730 --> 00:41:42,130
Llavors per què és això?

943
00:41:42,130 --> 00:41:46,630
Bé, resulta que quan
escrivim un programa com aquest

944
00:41:46,630 --> 00:41:51,590
que té tant principal, lloc de relleu aquí,
i després una altra funció, a canvi,

945
00:41:51,590 --> 00:41:54,230
ressaltat aquí, la qual cosa
que crida, el món

946
00:41:54,230 --> 00:41:57,030
es veu una mica d'alguna cosa com
aquestes safates fa un moment.

947
00:41:57,030 --> 00:42:00,440
Quan principal primer es torna a cridar,
això és com preguntar sistema operatiu

948
00:42:00,440 --> 00:42:04,030
per una mica de memòria per a qualsevol local de
variables com x i i que té principal,

949
00:42:04,030 --> 00:42:05,660
i acaben aquí.

950
00:42:05,660 --> 00:42:10,920
Però si les trucades principals d'intercanvi, i principal
passa a intercanviar dos arguments, a i b,

951
00:42:10,920 --> 00:42:16,410
suc de taronja i la llet, que no és com
lliurant-li el suc de taronja i la llet

952
00:42:16,410 --> 00:42:17,500
a Laura.

953
00:42:17,500 --> 00:42:21,300
Què fa un ordinador, és
passa còpies del suc de taronja

954
00:42:21,300 --> 00:42:27,110
i còpies de la llet a Laura, pel que
el que és en última instància dins d'aquesta safata

955
00:42:27,110 --> 00:42:32,510
és el valor d'un i dos, o DO
i llet, però les còpies dels mateixos,

956
00:42:32,510 --> 00:42:34,790
de manera que en aquest punt
en la història, hi ha

957
00:42:34,790 --> 00:42:36,930
és DO i la llet en cadascuna d'aquestes safates.

958
00:42:36,930 --> 00:42:39,260
Hi ha un ui un dos
en cadascuna d'aquestes safates,

959
00:42:39,260 --> 00:42:41,720
i la funció d'intercanvi és de fet treballant.

960
00:42:41,720 --> 00:42:46,090
Els està intercanviant l'interior
de la segona safata superior,

961
00:42:46,090 --> 00:42:48,147
però que l'intercanvi no té impacte.

962
00:42:48,147 --> 00:42:49,980
I basant-se algunes
principi bàsic que hem

963
00:42:49,980 --> 00:42:52,970
parlat abans, i de fet
Fa tan sols uns minuts, el que

964
00:42:52,970 --> 00:42:58,770
podria explicar per què el canvi
a i b a l'interior de bescanvi

965
00:42:58,770 --> 00:43:05,560
no té efecte en x i y, encara que
Vaig passar x i i per a la funció d'intercanvi.

966
00:43:05,560 --> 00:43:08,750
Quina és la paraula clau aquí que
podria explicar de manera simplista?

967
00:43:08,750 --> 00:43:11,250

968
00:43:11,250 --> 00:43:12,627
Crec que he sentit aquí?

969
00:43:12,627 --> 00:43:13,335
AUDIÈNCIA: Retorn.

970
00:43:13,335 --> 00:43:14,085
ALTAVEU 1: Retorn?

971
00:43:14,085 --> 00:43:14,590
No tornar.

972
00:43:14,590 --> 00:43:15,895
Anirem amb una altra.

973
00:43:15,895 --> 00:43:16,395
Què és això?

974
00:43:16,395 --> 00:43:17,080
>> AUDIÈNCIA: [inaudible].

975
00:43:17,080 --> 00:43:20,000
>> ALTAVEU 1: OK, així que vam poder return--
fer que el treball de retorn en la història,

976
00:43:20,000 --> 00:43:21,914
però hi ha una explicació encara més simple.

977
00:43:21,914 --> 00:43:22,580
AUDIÈNCIA: Àmbit d'aplicació.

978
00:43:22,580 --> 00:43:23,288
ALTAVEU 1: Àmbit d'aplicació.

979
00:43:23,288 --> 00:43:24,300
Prendré abast.

980
00:43:24,300 --> 00:43:27,290
Així abast, recordar on
nostra xiy declarats.

981
00:43:27,290 --> 00:43:30,840
Estan declaren dins
de principal fins aquí.

982
00:43:30,840 --> 00:43:33,200
A i B, per la seva banda, estan
declarat efectivament

983
00:43:33,200 --> 00:43:35,930
dins de swap, no del tot a
les claus, però encara

984
00:43:35,930 --> 00:43:37,690
en l'àrea general de swap.

985
00:43:37,690 --> 00:43:40,560
I així de fet, a i b
només existeixen dins d'aquesta safata

986
00:43:40,560 --> 00:43:44,850
d'Annenberg, aquest
segon tros de codi.

987
00:43:44,850 --> 00:43:49,500
Així que estem de fet el canvi de la còpia, però
això no és realment tan útil.

988
00:43:49,500 --> 00:43:52,190
>> Així que donem una ullada a
aquest nivell una mica més baix.

989
00:43:52,190 --> 00:43:55,430
Vaig a tornar a
El directori d'origen,

990
00:43:55,430 --> 00:43:58,330
i jo vaig a primer
zoom aquí, i només

991
00:43:58,330 --> 00:44:02,290
per confirmar que estic en aquesta
finestra de terminal més gran,

992
00:44:02,290 --> 00:44:04,430
el programa encara s'està comportant així.

993
00:44:04,430 --> 00:44:06,840
Suposem ara que aquest
no és intencional.

994
00:44:06,840 --> 00:44:10,090
Clarament volia intercanvi per
treball, així que se sent com una bestiola.

995
00:44:10,090 --> 00:44:12,780
Ara podia començar a afegir un
molta printf d'al meu codi,

996
00:44:12,780 --> 00:44:16,010
imprimir x aquí, i sobre
aquí, un aquí, b per aquí.

997
00:44:16,010 --> 00:44:18,220
Però, francament, això és probablement el que
que has estat fent durant un parell de setmanes

998
00:44:18,220 --> 00:44:20,190
ara, en horari d'oficina
ia la casa quan es treballa

999
00:44:20,190 --> 00:44:22,150
en conjunts de processadors tractant de trobar alguns errors.

1000
00:44:22,150 --> 00:44:25,560
Però vas a veure, si no ho ha fet,
aquest problema es van establir tres que introdueix

1001
00:44:25,560 --> 00:44:31,630
a una ordre anomenat GDB,
on GDB, GNU debugger,

1002
00:44:31,630 --> 00:44:34,040
té en si un munt de
característiques que realment pot

1003
00:44:34,040 --> 00:44:38,160
anem a entendre situacions
com aquest, però més convincent,

1004
00:44:38,160 --> 00:44:39,940
resoldre problemes i trobar errors.

1005
00:44:39,940 --> 00:44:40,940
Així que vaig a fer això.

1006
00:44:40,940 --> 00:44:44,770
En lloc de ./noswap, estic al seu lloc
va a córrer GDB ./noswap.

1007
00:44:44,770 --> 00:44:47,410

1008
00:44:47,410 --> 00:44:51,200
En altres paraules, vaig a dirigir la meva
programa no en Bash, el nostre nou amic

1009
00:44:51,200 --> 00:44:51,850
avui en dia.

1010
00:44:51,850 --> 00:44:53,970
Vaig a portar el meu
programa noswap interior

1011
00:44:53,970 --> 00:44:56,900
d'aquest altre programa anomenat
GDB, que és un depurador, que

1012
00:44:56,900 --> 00:45:01,035
és un programa que està dissenyat per ajudar a
que els éssers humans trobar i eliminar errors.

1013
00:45:01,035 --> 00:45:03,410
Així que si copejo Executeu aquí, hi ha
una quantitat atroç de text

1014
00:45:03,410 --> 00:45:04,868
que realment no ha de llegir.

1015
00:45:04,868 --> 00:45:07,290
Bàsicament es tracta d'una distracció
des del símbol, que

1016
00:45:07,290 --> 00:45:10,030
Vaig a colpejar Control-L
aixecar-se en la part superior existeix.

1017
00:45:10,030 --> 00:45:11,800
Aquest és el símbol del BGF.

1018
00:45:11,800 --> 00:45:15,550
Si vull executar aquest programa ara,
com aquesta petita full de trucs en l'actualitat de

1019
00:45:15,550 --> 00:45:21,860
diapositiva suggereix, Run és la primera
Les comandes que ens referíem a introduir.

1020
00:45:21,860 --> 00:45:25,150
I jo només vaig a escriure
córrer fins aquí dins de GDB,

1021
00:45:25,150 --> 00:45:26,811
i de fet va funcionar meu programa.

1022
00:45:26,811 --> 00:45:29,310
Ara hi ha una mica de addicional
sortides de la pantalla com aquesta,

1023
00:45:29,310 --> 00:45:31,910
però això és només estar GDB anal
i ens diu el que està passant.

1024
00:45:31,910 --> 00:45:34,451
Segur que no ha de preocupar
sobre aquests detalls ara mateix.

1025
00:45:34,451 --> 00:45:36,890
Però el que és realment bo d'
GDB, si faig això nou--

1026
00:45:36,890 --> 00:45:42,100
Control-L refusa el screen-- em deixis anar
per davant i el tipus "trencar principal", per tant,

1027
00:45:42,100 --> 00:45:45,743
quan pols Enter, establint el que és
anomenat un punt d'inflexió en noswap.c,

1028
00:45:45,743 --> 00:45:51,270
línia 16, que és on GDB
descobert el meu programa de realitat

1029
00:45:51,270 --> 00:45:53,070
És a dir, la meva funció és en realitat.

1030
00:45:53,070 --> 00:45:55,070
Aquesta ignorarem per ara
però aquesta és l'adreça d'

1031
00:45:55,070 --> 00:45:57,310
específicament en la memòria d'aquesta funció.

1032
00:45:57,310 --> 00:46:00,240
Així que ara quan em escrigui Executar,
notar el que està bé aquí.

1033
00:46:00,240 --> 00:46:05,650
El meu programa es trenca en la línia I
dit GDB per aturar l'execució en.

1034
00:46:05,650 --> 00:46:09,850
Així que no he de canviar ara el meu codi,
afegir alguns printf, recompilar, torneu a executar

1035
00:46:09,850 --> 00:46:13,300
ella, canviar, afegir alguns printf,
guardar, compilar, executar-lo.

1036
00:46:13,300 --> 00:46:18,100
Jo només puc caminar a través del meu programa
pas a pas a pas a la velocitat humana,

1037
00:46:18,100 --> 00:46:20,880
no en Intel-inside tipus de velocitat.

1038
00:46:20,880 --> 00:46:24,580
>> Així que ara compta aquesta línia
apareix aquí, i si torno

1039
00:46:24,580 --> 00:46:27,800
al meu programa a gedit,
adonar que això és en realitat

1040
00:46:27,800 --> 00:46:29,280
la primera línia de codi.

1041
00:46:29,280 --> 00:46:31,240
Hi línia 16 a gedit.

1042
00:46:31,240 --> 00:46:34,610
Hi línia 16 dins del BGF, i fins i tot
encara que aquesta interfície blanc i negre

1043
00:46:34,610 --> 00:46:37,760
no és tan d'usuari
amable, això significa

1044
00:46:37,760 --> 00:46:41,680
aquesta línia 16 no s'ha executat
encara, però està a punt de ser.

1045
00:46:41,680 --> 00:46:46,220
Així que de fet, si escric d'impressió
x, no printf, només print x,

1046
00:46:46,220 --> 00:46:50,730
Em surt algun valor fals no de zero,
perquè x no s'ha inicialitzat encara.

1047
00:46:50,730 --> 00:46:54,760
Així que vaig a escriure a continuació, o, si
vull ser presumptuós, N per al proper.

1048
00:46:54,760 --> 00:46:59,090
Però quan introdueixo següent entro, ara
compte es passa a la línia 17.

1049
00:46:59,090 --> 00:47:02,840
Així que, lògicament, si he executat
línia 16 i ara escric print x,

1050
00:47:02,840 --> 00:47:03,640
¿Què he de veure?

1051
00:47:03,640 --> 00:47:04,970

1052
00:47:04,970 --> 00:47:05,520
Una.

1053
00:47:05,520 --> 00:47:07,820
>> I ara això és certament confús.

1054
00:47:07,820 --> 00:47:11,260
$ 2 és només una forma elegant de, si
vulgui fer referència a aquest valor més endavant,

1055
00:47:11,260 --> 00:47:12,510
es pot dir "signe de dòlar 2."

1056
00:47:12,510 --> 00:47:13,480
És com una referència cap enrere.

1057
00:47:13,480 --> 00:47:14,570
Però per ara, simplement ho ignoren.

1058
00:47:14,570 --> 00:47:17,070
L'interessant és el que hi ha
a la dreta del signe igual.

1059
00:47:17,070 --> 00:47:21,000
I ara si escric la propera vegada
i d'impressió i, he de veure 2.

1060
00:47:21,000 --> 00:47:23,870
També puc ara imprimir
x de nou, i, francament,

1061
00:47:23,870 --> 00:47:27,130
si m'estic posant una mica confós pel que fa a
on sóc, puc tipus de llista per a la llista

1062
00:47:27,130 --> 00:47:30,590
i només veure una mica de context al voltant
El punt que estic realment en.

1063
00:47:30,590 --> 00:47:35,180
I ara puc escriure
següent, i no és x 1.

1064
00:47:35,180 --> 00:47:36,300
Ara escric següent.

1065
00:47:36,300 --> 00:47:37,710
Oh, i és 2.

1066
00:47:37,710 --> 00:47:40,750
I de nou, és confús,
perquè la producció del BGF

1067
00:47:40,750 --> 00:47:43,044
està sent barrejat amb la meva pròpia producció.

1068
00:47:43,044 --> 00:47:45,710
Però si es té en compte, per
mirant cap enrere i cap endavant en el seu codi

1069
00:47:45,710 --> 00:47:47,740
o pel qual es fora del costat
al costat potser, vostè

1070
00:47:47,740 --> 00:47:51,020
veig que en realitat només sóc
passant a través del meu programa.

1071
00:47:51,020 --> 00:47:54,620
>> Però adonar-se del que passa a continuació, literalment.

1072
00:47:54,620 --> 00:47:56,380
Aquí hi ha la línia 22.

1073
00:47:56,380 --> 00:48:01,315
Déjame anar sobre ell, movent així el
a 23, i si imprimeixo x ara, segueix sent un.

1074
00:48:01,315 --> 00:48:03,890
I si imprimeixo i ara, segueix sent un.

1075
00:48:03,890 --> 00:48:05,820
Així que això no és un exercici útil.

1076
00:48:05,820 --> 00:48:07,450
Així que anem a refer aquest.

1077
00:48:07,450 --> 00:48:10,069
Permetin-me tornar a la
superior i tipus d'execució de nou.

1078
00:48:10,069 --> 00:48:12,110
I està dient que el programa
que està sent depurat

1079
00:48:12,110 --> 00:48:14,109
ha començat ja,
començat des del principi.

1080
00:48:14,109 --> 00:48:15,420
Sí, farem això de nou.

1081
00:48:15,420 --> 00:48:22,000
I aquesta vegada ho farem la propera,
següent, següent, següent, següent,

1082
00:48:22,000 --> 00:48:24,180
però ara les coses es posen interessants.

1083
00:48:24,180 --> 00:48:27,760
Ara vull entrar en
intercanvi, així que no em escrigui a continuació.

1084
00:48:27,760 --> 00:48:34,380
Escric pas, i ara notar
m'ha saltat a la línia noswap.c 33.

1085
00:48:34,380 --> 00:48:37,240
Si torno a gedit, el que és la línia 33?

1086
00:48:37,240 --> 00:48:40,500
Aquesta és la primera real
línia de codi dins de swap.

1087
00:48:40,500 --> 00:48:44,150
La qual cosa és bo, perquè ara puc
tipus de furgar i sentir curiositat

1088
00:48:44,150 --> 00:48:46,052
pel que fa al que està passant realment en aquest país.

1089
00:48:46,052 --> 00:48:46,760
Permetin-me imprimeixo 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
Per què tmp té alguna
, El valor de les escombraries falsa boig?

1093
00:48:51,438 --> 00:48:54,579

1094
00:48:54,579 --> 00:48:56,120
AUDIÈNCIA: No s'ha inicialitzat.

1095
00:48:56,120 --> 00:48:57,150
ALTAVEU 1: No s'ha inicialitzat.

1096
00:48:57,150 --> 00:49:00,270
I de fet, quan s'executa un programa,
et donen un munt de memòria

1097
00:49:00,270 --> 00:49:03,392
pel sistema operatiu, però
no han inicialitzat cap valor,

1098
00:49:03,392 --> 00:49:05,600
així que el que els bits que ets
veient aquí, tot i que és

1099
00:49:05,600 --> 00:49:07,770
aquest gran negatiu boig
nombre, només significa

1100
00:49:07,770 --> 00:49:10,750
que aquests són les restes de
cert ús anterior que la memòria RAM,

1101
00:49:10,750 --> 00:49:13,050
encara que jo no tinc
jo ho necessitava encara.

1102
00:49:13,050 --> 00:49:17,086
Així que ara vaig a seguir endavant i tipus
següent, i si ara escric tmp d'impressió,

1103
00:49:17,086 --> 00:49:17,835
¿Què he de veure?

1104
00:49:17,835 --> 00:49:19,570

1105
00:49:19,570 --> 00:49:23,360
Qualsevol que sigui el valor d'una era,
a és el primer argument, només

1106
00:49:23,360 --> 00:49:25,550
com x ser la primera
El que es passa a,

1107
00:49:25,550 --> 00:49:30,450
de manera que una i X ha de ser el mateix,
així imprimir tmp em deu imprimir un.

1108
00:49:30,450 --> 00:49:36,360
>> Així que el que vostè veurà en el conjunt de problemes
3 és un tutorial de classes en GDB,

1109
00:49:36,360 --> 00:49:40,020
però s'adonen que aquest és el començament
d'un cop d'ull a una eina que ho farà realitat

1110
00:49:40,020 --> 00:49:42,774
ajudar a resoldre problemes
de manera molt més eficaç.

1111
00:49:42,774 --> 00:49:44,690
El que estem en última instància
farem el dimecres

1112
00:49:44,690 --> 00:49:48,180
es començarà a pelar unes poques capes
i eliminar algunes rodes d'entrenament.

1113
00:49:48,180 --> 00:49:50,496
Aquesta cadena cosa crida que
que hem utilitzat durant algun temps,

1114
00:49:50,496 --> 00:49:53,370
anem a prendre a poc a poc que fos
de vostè i començar a parlar de

1115
00:49:53,370 --> 00:49:55,725
una mica més esotèricament
conegut com char *,

1116
00:49:55,725 --> 00:49:59,550
però ho farem bé i
suaument al principi, tot i que els punters,

1117
00:49:59,550 --> 00:50:02,730
com se'ls anomena, es pot fer una mica de
coses molt dolentes si s'abusa,

1118
00:50:02,730 --> 00:50:06,040
mirant una mica d'animació amb plastilina
nostre amic Nick Parlant de Stanford

1119
00:50:06,040 --> 00:50:09,670
Universitat, professor a l'ordinador
la ciència que va armar aquesta vista prèvia

1120
00:50:09,670 --> 00:50:11,075
del que està per venir aquest dimecres.

1121
00:50:11,075 --> 00:50:12,196

1122
00:50:12,196 --> 00:50:13,400
>> [REPRODUCCIÓ DE VÍDEO]

1123
00:50:13,400 --> 00:50:13,900
Escolta, Binky.

1124
00:50:13,900 --> 00:50:14,930

1125
00:50:14,930 --> 00:50:15,780
Despertar.

1126
00:50:15,780 --> 00:50:17,240
És temps per a la diversió punter.

1127
00:50:17,240 --> 00:50:18,260

1128
00:50:18,260 --> 00:50:19,350
>> Què és això?

1129
00:50:19,350 --> 00:50:21,150
Aprendre sobre els punters?

1130
00:50:21,150 --> 00:50:22,050
Que bé!

1131
00:50:22,050 --> 00:50:22,897

1132
00:50:22,897 --> 00:50:23,730
[FI REPRODUCCIÓ DE VÍDEO]

1133
00:50:23,730 --> 00:50:25,396
ALTAVEU 1: Que l'espera el dimecres.

1134
00:50:25,396 --> 00:50:26,440
Ens veiem llavors.

1135
00:50:26,440 --> 00:50:27,106
[REPRODUCCIÓ DE VÍDEO]

1136
00:50:27,106 --> 00:50:30,420
-I Ara, pensaments profunds,
per Daven Farnham.

1137
00:50:30,420 --> 00:50:33,980

1138
00:50:33,980 --> 00:50:35,900
>> Per què estem aprenent C?

1139
00:50:35,900 --> 00:50:36,785
Per què no A +?

1140
00:50:36,785 --> 00:50:38,550

1141
00:50:38,550 --> 00:50:40,910
>> [Rialles]

1142
00:50:40,910 --> 00:50:42,160
>> [FI REPRODUCCIÓ DE VÍDEO]