1
00:00:00,000 --> 00:00:12,040
>> [GIOCO MUSICA]

2
00:00:12,040 --> 00:00:16,460
>> SPEAKER 1: Va bene, questo è CS50,
e questo è l'inizio della quarta settimana,

3
00:00:16,460 --> 00:00:20,420
e come si può avere sentito o
lettura, il mondo è stato per finire.

4
00:00:20,420 --> 00:00:23,520
Andando in tutto il Internet
è stata la conoscenza e la consapevolezza

5
00:00:23,520 --> 00:00:27,100
di un bug in un programma, un
linguaggio di programmazione chiamato Bash.

6
00:00:27,100 --> 00:00:32,729
Questo è stato meravigliosamente bollato
come Shellshock, o la porta Bash,

7
00:00:32,729 --> 00:00:35,485
ma articoli come questi
non sono stati infrequenti.

8
00:00:35,485 --> 00:00:38,807
E infatti, molti di loro portano
ricordi indietro di Heartbleed,

9
00:00:38,807 --> 00:00:41,640
che avrete notato in
premere di nuovo la scorsa primavera, che

10
00:00:41,640 --> 00:00:43,980
era ugualmente abbastanza drammatico.

11
00:00:43,980 --> 00:00:47,110
Ora, di quelli di voi qui
oggi, come molti di voi hanno,

12
00:00:47,110 --> 00:00:50,330
anche se non si capisce che cosa
è tutta una questione, sentito parlare di Shellshock?

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

14
00:00:51,370 --> 00:00:54,245
Va bene, e come molti di voi
avere i computer che sono vulnerabili?

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

16
00:00:55,680 --> 00:01:00,250
OK, ci dovrebbe essere molto, molto più mani
fino adesso, per ragioni che vedremo.

17
00:01:00,250 --> 00:01:02,580
>> Diamo uno sguardo a ciò che è
accaduto in media

18
00:01:02,580 --> 00:01:05,304
e poi spiegare un po '
qui per noi tecnicamente.

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

20
00:01:07,670 --> 00:01:11,250
>> SPEAKER 2: Gli esperti di sicurezza hanno
avvertito che un grave difetto potrebbe

21
00:01:11,250 --> 00:01:15,650
essere sul punto di influenzare centinaia di
milioni di utenti web di tutto il mondo.

22
00:01:15,650 --> 00:01:20,600
Così che cosa è esattamente il bug che è stato
doppiato Shellshock, e che cosa fa?

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

24
00:01:23,720 --> 00:01:28,910
Beh, Shellshock è anche conosciuto come il
Bash bug, il software sfrutta.

25
00:01:28,910 --> 00:01:33,230
Gli hacker utilizzano il virus per la scansione vulnerabilità
sistemi che eseguono Linux e Unix

26
00:01:33,230 --> 00:01:36,300
sistemi operativi e quindi li infettano.

27
00:01:36,300 --> 00:01:38,730
Bash è una shell a riga di comando.

28
00:01:38,730 --> 00:01:43,460
Ciò consente di impartire comandi agli utenti di lanciare
Programmi e funzionalità nel software

29
00:01:43,460 --> 00:01:45,250
digitando nel testo.

30
00:01:45,250 --> 00:01:49,980
È in genere utilizzato dai programmatori, e
non dovrebbe essere aperta al resto del mondo,

31
00:01:49,980 --> 00:01:51,590
se Shellshock che cambia.

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

33
00:01:54,160 --> 00:01:57,910
>> Beh, worringly, alcuni analisti
avvertire che potrebbe essere una minaccia più grande,

34
00:01:57,910 --> 00:02:01,580
Shellshock perché permette una completa
controllo di una macchina infetta,

35
00:02:01,580 --> 00:02:06,030
considerando Heartbleed solo permesso
hacker per spiare i computer.

36
00:02:06,030 --> 00:02:09,130
E 'così grave, è
stato valutato a 10 su 10

37
00:02:09,130 --> 00:02:11,900
per gravità dal National
Vulnerability Database.

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

39
00:02:15,530 --> 00:02:20,015
2/3 di tutti i server web sono a
rischio, tra cui alcuni computer Macintosh.

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

41
00:02:22,760 --> 00:02:25,600
Beh, assicuratevi di
patchare i sistemi ora.

42
00:02:25,600 --> 00:02:29,330
Chiunque l'hosting di un sito web in esecuzione
i sistemi operativi interessati

43
00:02:29,330 --> 00:02:31,800
dovrebbe intervenire il più presto possibile.

44
00:02:31,800 --> 00:02:35,390
Chiunque può permetterselo dovrebbe apparire
alla loro applicazione e monitoraggio web

45
00:02:35,390 --> 00:02:37,355
firewall per guardare fuori per tutti gli attacchi.

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

47
00:02:39,979 --> 00:02:41,770
SPEAKER 3: cosa peggiore
che potrebbe accadere è

48
00:02:41,770 --> 00:02:45,080
che qualcuno avrebbe scritto un codice che
sarebbe andare a eseguire automaticamente la scansione

49
00:02:45,080 --> 00:02:48,280
Internet e inciderebbe
tutti questi computer.

50
00:02:48,280 --> 00:02:50,710
E una volta che lo fanno, bene,
la cosa peggiore che potessero fare

51
00:02:50,710 --> 00:02:53,300
è solo cancellare tutto,
o chiudere i siti verso il basso.

52
00:02:53,300 --> 00:02:55,360
Così abbiamo potuto vedere i danni
da questo punto di vista,

53
00:02:55,360 --> 00:02:58,300
dove avremmo persone malintenzionati
che solo decidere di provocare il caos

54
00:02:58,300 --> 00:03:02,534
da sistemi di abbattere o cancellare
file, e cose del genere.

55
00:03:02,534 --> 00:03:05,200
SPEAKER 2: Alcuni dicono che questo è uno
dei più difficili da misurare

56
00:03:05,200 --> 00:03:08,080
bug in anni, ed è
può richiedere settimane o addirittura

57
00:03:08,080 --> 00:03:10,820
mesi per determinare l'impatto finale.

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

59
00:03:12,180 --> 00:03:15,560
>> SPEAKER 1: Quindi tutto questo è vero,
ma la cosa divertente è, quasi tutti

60
00:03:15,560 --> 00:03:18,330
delle immagini che hai appena visto,
eccetto forse per la tastiera,

61
00:03:18,330 --> 00:03:20,930
non ha nulla a che fare con
il bug di sorta.

62
00:03:20,930 --> 00:03:23,960
Server e fili e così via,
è una sorta di tangenziale collegata,

63
00:03:23,960 --> 00:03:27,410
ma al centro è in realtà piuttosto
familiare quello che sta succedendo qui.

64
00:03:27,410 --> 00:03:30,050
In realtà, mi permetta di andare in
il nostro apparecchio CS50.

65
00:03:30,050 --> 00:03:32,910
Lasciami andare avanti e massimizzare
la finestra del terminale qui.

66
00:03:32,910 --> 00:03:36,020
E voi ragazzi hanno utilizzato questo,
o la versione integrata della stessa,

67
00:03:36,020 --> 00:03:39,460
in gedit per scrivere programmi,
digitare i comandi, e così via,

68
00:03:39,460 --> 00:03:43,690
e questo è in realtà, e ha
stato per settimane, Bash, B-A-S-H.

69
00:03:43,690 --> 00:03:46,890
Questa è la Bourne-again shell,
che è solo un modo elegante per dire,

70
00:03:46,890 --> 00:03:50,220
questo è un programma che ha una
lampeggiante rapido, efficace,

71
00:03:50,220 --> 00:03:51,970
che siede lì in attesa
per l'ingresso per voi.

72
00:03:51,970 --> 00:03:53,920
Ed è il comando
interfaccia a riga tramite la quale

73
00:03:53,920 --> 00:03:57,650
voi ragazzi sono stati l'esecuzione di comandi e
in ultima analisi, compilazione e quindi eseguire

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

75
00:03:58,400 --> 00:04:01,320
>> Ma Bash è anche una programmazione
lingua nel senso seguente.

76
00:04:01,320 --> 00:04:05,460
Voi sapete che ci sono comandi come
cd e ls e anche clang e altri,

77
00:04:05,460 --> 00:04:09,580
ma è possibile definire i propri comandi
dalla loro attuazione in Bash.

78
00:04:09,580 --> 00:04:11,420
Ora non stiamo andando a
andare in grande dettaglio

79
00:04:11,420 --> 00:04:16,089
come per colpire il linguaggio di programmazione, ma
Sappiamo, per esempio, che per il momento,

80
00:04:16,089 --> 00:04:17,607
non esiste un comando chiamato "ciao."

81
00:04:17,607 --> 00:04:19,440
Così può essere trovato in
uno di questi pacchetti.

82
00:04:19,440 --> 00:04:20,856
Non è installato sul mio computer.

83
00:04:20,856 --> 00:04:21,870
Chiedere all'amministratore.

84
00:04:21,870 --> 00:04:26,030
Ma se io voglio che ci sia un programma
chiamato "ciao" in Bash o alla mia richiesta,

85
00:04:26,030 --> 00:04:30,810
Posso effettivamente usare la sintassi che è
abbastanza come C. Non è proprio la stessa cosa,

86
00:04:30,810 --> 00:04:35,020
ma sembra piuttosto simile a un
funzione, anche se mancano alcuni dettagli.

87
00:04:35,020 --> 00:04:38,090
Nulla sembra accadere,
ma ora se digito "ciao,"

88
00:04:38,090 --> 00:04:40,960
si può effettivamente scrivere un
programma, non in C, non in Java,

89
00:04:40,960 --> 00:04:44,280
non in un altro programmazione
linguaggio, ma in Bash sé.

90
00:04:44,280 --> 00:04:47,630
>> Ora la chiave qui è che ho scritto il
nome che ho voluto dare a questo nuovo comando,

91
00:04:47,630 --> 00:04:50,820
e le parentesi sono anche
simbolica di questa essendo una funzione.

92
00:04:50,820 --> 00:04:54,010
Per inciso, si può anche fare divertimento
le cose, e in effetti, anche su Mac OS,

93
00:04:54,010 --> 00:04:55,620
questo è un programma chiamato Terminal.

94
00:04:55,620 --> 00:04:58,800
Viene costruito in qualcuno di
computer che dispone di un Mac in questa stanza,

95
00:04:58,800 --> 00:05:03,640
e si possono fare cose simili in Mac
OS, ma si può andare più oltre.

96
00:05:03,640 --> 00:05:07,110
E questo è un po tangenziale,
ma è una specie di divertimento.

97
00:05:07,110 --> 00:05:09,715
Mi è stato ricordato questa mattina,
quando si pensa questo attraverso,

98
00:05:09,715 --> 00:05:13,279
di un piccolo gioco che ho usato per giocare
con uno degli ex TF di CS50

99
00:05:13,279 --> 00:05:16,570
per cui ogni volta che camminava lontano da
la tastiera con il suo schermo sbloccato,

100
00:05:16,570 --> 00:05:23,611
Vorrei eseguire un comando
come questo-- "dire ciao."

101
00:05:23,611 --> 00:05:26,610
E adesso ogni volta che è tornato al suo
tastiera dopo aver cancellato lo schermo

102
00:05:26,610 --> 00:05:27,985
e si sedeva,
provare a fare qualche lavoro,

103
00:05:27,985 --> 00:05:29,250
elencare il contenuto della sua directory--

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

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

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

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

108
00:05:32,120 --> 00:05:35,030
>> SPEAKER 1: Così, in tutta onestà,
non era in realtà "ciao."

109
00:05:35,030 --> 00:05:36,894
Di solito era qualcosa di
più simile a che--

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

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

112
00:05:37,750 --> 00:05:39,320
SPEAKER 1: --that I would--
così il suo computer sarebbe

113
00:05:39,320 --> 00:05:42,170
giuro su di lui ogni volta che in realtà
sedette alla tastiera.

114
00:05:42,170 --> 00:05:46,265
E ben presto ha capito
di non lasciare il suo schermo sbloccato.

115
00:05:46,265 --> 00:05:48,730
Ma questo suggerisce il tipo
di divertimento stupido che si

116
00:05:48,730 --> 00:05:50,210
può avere con qualcosa come Bash.

117
00:05:50,210 --> 00:05:52,770
Ma è un po 'più
serio, per essere sicuri, di quello.

118
00:05:52,770 --> 00:05:57,235
Ed in effetti, questo è uno dei
maggior numero di bug pericolosi e duraturi

119
00:05:57,235 --> 00:05:58,860
che ha davvero colpito il mondo a livello globale.

120
00:05:58,860 --> 00:06:02,060
Questo bug è stato intorno
per circa 20 anni,

121
00:06:02,060 --> 00:06:05,780
e sarete colpiti in un solo
momento per la sua relativa semplicità.

122
00:06:05,780 --> 00:06:07,990
>> Quindi questo è un rappresentante
ordinerà che se si

123
00:06:07,990 --> 00:06:10,448
possedere un Mac, letteralmente in questo momento
quando avete il vostro coperchio aperto,

124
00:06:10,448 --> 00:06:12,940
si può provare a digitare in quella
programma chiamato Terminal.

125
00:06:12,940 --> 00:06:15,410
Terminal è sotto
Applicazioni Utilities--

126
00:06:15,410 --> 00:06:18,790
per una volta, gli utenti di Windows non devono
preoccuparsi di questo particolare threat--

127
00:06:18,790 --> 00:06:22,310
ma quelli di voi con Mac possibile digitare
questo in una finestra come farò qui,

128
00:06:22,310 --> 00:06:24,210
e se si digita
che in questo programma

129
00:06:24,210 --> 00:06:28,830
chiamato Terminal, come farò adesso,
se vedete la parola "vulnerabile"

130
00:06:28,830 --> 00:06:32,200
il computer è
vulnerabili allo sfruttamento.

131
00:06:32,200 --> 00:06:33,850
>> Ora, che cosa vuol dire realmente?

132
00:06:33,850 --> 00:06:35,870
E questo è certamente
una sintassi abbastanza pazzo,

133
00:06:35,870 --> 00:06:39,050
ma diamo almeno tirare fuori
alcuni degli aspetti interessanti.

134
00:06:39,050 --> 00:06:42,567
Quindi c'è una certa sintassi che sembra
un po 'familiare, almeno dal C

135
00:06:42,567 --> 00:06:43,950
e programmazione, più in generale.

136
00:06:43,950 --> 00:06:47,550
Vedo alcune parentesi,
punto e virgola, parentesi graffe, e tali,

137
00:06:47,550 --> 00:06:50,820
ma si scopre che questa
cosa stupida qui in giallo

138
00:06:50,820 --> 00:06:53,580
è essenzialmente una funzione
che non fa nulla.

139
00:06:53,580 --> 00:06:57,840
I mezzi colon non fanno nulla, e la
punto e virgola significa smettere di fare nulla.

140
00:06:57,840 --> 00:07:00,250
Quindi all'interno di questi
parentesi graffe, il fatto

141
00:07:00,250 --> 00:07:02,440
che ho un uguale
firmare a sinistra, questo

142
00:07:02,440 --> 00:07:05,500
è essenzialmente la creazione di
un comando, o una variabile,

143
00:07:05,500 --> 00:07:09,520
chiamato x, e assegnandogli
quel po 'di colore giallo di codice lì.

144
00:07:09,520 --> 00:07:14,040
Questo potrebbe essere qualcosa del tipo "echo
ciao "o" bip dire "o qualcosa del genere

145
00:07:14,040 --> 00:07:15,120
simile a quello.

146
00:07:15,120 --> 00:07:17,780
Ma notare se i tuoi occhi
vagare più a destra,

147
00:07:17,780 --> 00:07:22,150
c'è di più a questa linea di
solo alla fine di quel punto e virgola.

148
00:07:22,150 --> 00:07:25,160
"Echo vulnerabile," e poi
al di là che c'è ancora di più.

149
00:07:25,160 --> 00:07:26,530
Un altro punto e virgola, bash-c :.

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

151
00:07:28,120 --> 00:07:34,050
>> Quindi, per farla breve,
questa riga di codice è

152
00:07:34,050 --> 00:07:36,660
sufficiente per avvincente
un computer che è

153
00:07:36,660 --> 00:07:39,830
vulnerabile a fare qualcosa
che vuoi che faccia,

154
00:07:39,830 --> 00:07:44,290
perché c'è un bug in Bash per cui
anche se Bash doveva fermare

155
00:07:44,290 --> 00:07:48,980
linee di lettura di comando a destra
lì dopo il testo giallo,

156
00:07:48,980 --> 00:07:52,520
per un 20-plus anni bug,
Bash è stata in realtà la lettura

157
00:07:52,520 --> 00:07:56,780
oltre tale punto e virgola e abbastanza
molto fare quello che viene detto.

158
00:07:56,780 --> 00:07:59,070
>> Allora, qual è l'implicazione
di che alla fine?

159
00:07:59,070 --> 00:08:01,340
Ho solo detto "echo ciao"
o "echo vulnerabile,"

160
00:08:01,340 --> 00:08:05,449
ma cosa succede se hai fatto qualcosa di
in realtà dannoso, come rm-rf *,

161
00:08:05,449 --> 00:08:07,240
che non si potrebbe
hanno mai scritto prima,

162
00:08:07,240 --> 00:08:08,920
e francamente probabilmente
non dovrebbe troppo presto,

163
00:08:08,920 --> 00:08:10,700
perché si può fare un
sacco di danni con esso.

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

165
00:08:11,210 --> 00:08:12,990
rm fa quello, naturalmente?

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

167
00:08:14,270 --> 00:08:15,930
* Significa che cosa?

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

169
00:08:16,430 --> 00:08:18,180
Quindi è un cosiddetto
wild card, quindi significa

170
00:08:18,180 --> 00:08:20,410
cancellare tutto in
la directory corrente.

171
00:08:20,410 --> 00:08:23,379
-r accade a significare ricorsiva,
il che significa che se quello che stai cancellando

172
00:08:23,379 --> 00:08:26,420
è una directory, e dentro di lì
è altri file e altre directory,

173
00:08:26,420 --> 00:08:28,950
ricorsivamente tuffarsi in là
e cancellare tutto questo.

174
00:08:28,950 --> 00:08:31,040
E f è il peggiore di tutti.

175
00:08:31,040 --> 00:08:32,580
Qualcuno sa cosa significa -f qui?

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

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

178
00:08:34,360 --> 00:08:37,830
Quindi forzare mezzi, anche
se questa è una cattiva idea,

179
00:08:37,830 --> 00:08:40,939
farlo senza di me chiedere conferma
per ulteriore conferma.

180
00:08:40,939 --> 00:08:43,230
Così, sai, ridiamo
questo, ma francamente, io probabilmente

181
00:08:43,230 --> 00:08:44,972
digitare questo più volte
un giorno, perché la realtà

182
00:08:44,972 --> 00:08:47,210
è che è il modo più veloce per
cancellare un sacco di roba.

183
00:08:47,210 --> 00:08:48,590
Ma anche io ho fatto qualche danno.

184
00:08:48,590 --> 00:08:53,100
>> Ma se si dovesse ingannare un computer
nella definizione di alcune variabili stupido

185
00:08:53,100 --> 00:08:56,810
o funzione chiamata x, ma poi
ingannando il computer in esecuzione

186
00:08:56,810 --> 00:09:00,030
al di là dei confini di quel
funzione, oltre che punto e virgola,

187
00:09:00,030 --> 00:09:04,430
si potrebbe infatti ingannare un computer
in esecuzione qualcosa come rm-rf

188
00:09:04,430 --> 00:09:07,810
o il comando mail
o il comando Copia.

189
00:09:07,810 --> 00:09:11,400
Tutto ciò che letteralmente si può fare con la
del computer, che si tratti di eliminazione di file,

190
00:09:11,400 --> 00:09:15,350
creazione di file, spamming qualcuno,
attaccando alcuni server remoto,

191
00:09:15,350 --> 00:09:17,190
se si può esprimere
con un comando, si

192
00:09:17,190 --> 00:09:19,120
può ingannare un computer a fare questo.

193
00:09:19,120 --> 00:09:21,510
>> Ora, ciò che è un esempio di
come si potrebbe fare questo?

194
00:09:21,510 --> 00:09:24,300
Beh, c'è un sacco di computer
su Bash internet esecuzione.

195
00:09:24,300 --> 00:09:26,390
Tutti noi utenti Mac sono tra di loro.

196
00:09:26,390 --> 00:09:30,390
Un sacco di server Linux sono tra
loro pure, e server Unix.

197
00:09:30,390 --> 00:09:32,630
Finestre ottiene di nuovo
relativamente fuori dai guai

198
00:09:32,630 --> 00:09:34,590
a meno che non hai installato
software speciale.

199
00:09:34,590 --> 00:09:37,130
Ora un sacco di server, per
esempio, server web gestiti,

200
00:09:37,130 --> 00:09:39,840
e infatti Linux è forse l'
sistema operativo più popolare

201
00:09:39,840 --> 00:09:43,060
per funzionare su computer su internet
che servono le pagine web.

202
00:09:43,060 --> 00:09:44,910
Ora, come vedremo più avanti
nel semestre, quando

203
00:09:44,910 --> 00:09:48,470
si invia una richiesta da
il tuo browser-- Chrome,

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

205
00:09:50,790 --> 00:09:53,730
si scopre che anche se
appena digitata www.example.com,

206
00:09:53,730 --> 00:09:59,590
il browser invia un messaggio
che è un po 'più arcane, come questo.

207
00:09:59,590 --> 00:10:01,239
>> Ma notare un po 'di qualcosa di strano.

208
00:10:01,239 --> 00:10:03,030
Le prime due righe
Non ho mai visto prima,

209
00:10:03,030 --> 00:10:04,904
ma non guardano
particolarmente minaccioso.

210
00:10:04,904 --> 00:10:08,030
Ma accorgo di quello che ho rubato
per la terza linea qui.

211
00:10:08,030 --> 00:10:13,390
Se un ragazzo cattivo dovesse inviare un messaggio
come questo dal suo computer

212
00:10:13,390 --> 00:10:17,270
di un Mac o di un vulnerabile
server vulnerabile Linux,

213
00:10:17,270 --> 00:10:21,580
la cosa divertente è che Bash,
che semplice prompt dei comandi poco,

214
00:10:21,580 --> 00:10:27,450
è onnipresente ed è spesso
utilizzato per eseguire essenzialmente

215
00:10:27,450 --> 00:10:30,020
il contenuto di un
messaggio che riceve.

216
00:10:30,020 --> 00:10:33,490
E da questa logica, è possibile
ingannare un server web, quindi,

217
00:10:33,490 --> 00:10:36,370
inviando qualcosa come
User-Agent, che di solito

218
00:10:36,370 --> 00:10:38,300
si suppone a dire il
Nome del tuo browser.

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

220
00:10:42,420 --> 00:10:44,590
è solo il browser del
modo di identificare se stesso.

221
00:10:44,590 --> 00:10:46,605
Ma se un cattivo ragazzo molto
dice abilmente, mm-mm, sono

222
00:10:46,605 --> 00:10:47,930
Non lo dirò
ciò che il mio browser,

223
00:10:47,930 --> 00:10:50,888
Io invece intenzione di inviare questo
criptico-guardando cosa con un rm-rf

224
00:10:50,888 --> 00:10:55,840
* In esso, si può letteralmente ingannare un
web server vulnerabile su internet

225
00:10:55,840 --> 00:10:59,055
in esecuzione esattamente questo in
lì per cancellare tutti i file.

226
00:10:59,055 --> 00:11:00,930
E, francamente, non è
anche il peggio.

227
00:11:00,930 --> 00:11:01,763
Si può fare qualsiasi cosa.

228
00:11:01,763 --> 00:11:04,480
Si potrebbe iniziare una distribuita
attacco denial of service

229
00:11:04,480 --> 00:11:07,030
se hai inviato questo messaggio a
grappoli interi server web

230
00:11:07,030 --> 00:11:10,256
e poi li aveva tutti discendono, per
esempio, su server Harvard.edu,

231
00:11:10,256 --> 00:11:12,130
e si può ordinare di botto
diamine fuori di essi

232
00:11:12,130 --> 00:11:15,490
da un traffico di rete che era
altrimenti innescato da questo cattivo ragazzo.

233
00:11:15,490 --> 00:11:18,760
>> Quindi, per farla breve, quasi
tutti in questa stanza che possiede un Mac

234
00:11:18,760 --> 00:11:20,240
è vulnerabile a questo.

235
00:11:20,240 --> 00:11:24,100
Il rivestimento d'argento è che se non sei
esecuzione di un web server sul vostro computer portatile,

236
00:11:24,100 --> 00:11:27,780
e se non hai effettivamente configurato
per consentire qualcosa come SSH in esso,

237
00:11:27,780 --> 00:11:28,670
sei davvero sicuro.

238
00:11:28,670 --> 00:11:31,710
E 'vulnerabile, ma non c'è
uno cercando di entrare nel vostro computer portatile,

239
00:11:31,710 --> 00:11:33,290
in modo da poter sorta di stare tranquilli.

240
00:11:33,290 --> 00:11:36,210
Tuttavia, Apple sarà presto
essere l'aggiornamento di una correzione per questo.

241
00:11:36,210 --> 00:11:39,660
Il mondo di Linux ha già rilasciato
una serie di correzioni per Fedora e Ubuntu

242
00:11:39,660 --> 00:11:43,790
e altre versioni di Linux, e anzi
se si esegue l'aggiornamento 50 in dell'apparecchio,

243
00:11:43,790 --> 00:11:45,930
anche che troppo sarà
aggiornato e corretto.

244
00:11:45,930 --> 00:11:47,764
Ma che non ha troppo
stato davvero vulnerabile,

245
00:11:47,764 --> 00:11:49,804
perché a meno che non hai
armeggiato con l'apparecchio

246
00:11:49,804 --> 00:11:52,770
e fatto il vostro computer portatile al pubblico
accessibili su internet, che non è

247
00:11:52,770 --> 00:11:54,910
Per impostazione predefinita, hai
effettivamente bene perché

248
00:11:54,910 --> 00:11:56,890
di firewalling e di altre tecniche.

249
00:11:56,890 --> 00:12:01,000
>> Ma è un esempio estremo di un bug
che abbiamo vissuto per letteralmente per 20

250
00:12:01,000 --> 00:12:04,050
anni, e chissà se qualcuno
tutto questo tempo ha saputo su di esso?

251
00:12:04,050 --> 00:12:06,300
Ed in effetti, questo è uno dei
le sfide fondamentali

252
00:12:06,300 --> 00:12:08,690
che vedremo più avanti nel
semestre per la sicurezza,

253
00:12:08,690 --> 00:12:13,020
è che, proprio come nel mondo reale,
i buoni sono in svantaggio.

254
00:12:13,020 --> 00:12:16,500
Per mantenere i cattivi fuori, dobbiamo
fare in modo che ogni porta è chiusa a chiave,

255
00:12:16,500 --> 00:12:20,340
che ogni finestra è sicuro, che
ogni punto di ingresso in una casa

256
00:12:20,340 --> 00:12:21,980
è sicuro per mantenere i cattivi fuori.

257
00:12:21,980 --> 00:12:26,870
Ma che cosa fa il cattivo deve
fare per compromettere in realtà la vostra casa

258
00:12:26,870 --> 00:12:28,200
e rubare da voi?

259
00:12:28,200 --> 00:12:32,574
Lui o lei deve solo trovare uno sbloccato
porta, una finestra rotta, o qualcosa del genere

260
00:12:32,574 --> 00:12:35,240
in tal senso, ed è il
stessa cosa in sicurezza informatica.

261
00:12:35,240 --> 00:12:37,660
Possiamo scrivere milioni di
linee di codice di programmazione

262
00:12:37,660 --> 00:12:40,570
e spendere centinaia o migliaia
di ore cercando di farlo giusto,

263
00:12:40,570 --> 00:12:43,370
ma se fate un solo
errore di correttezza,

264
00:12:43,370 --> 00:12:47,030
si può mettere l'intero sistema e
infatti in questo caso, l'intera Internet

265
00:12:47,030 --> 00:12:48,660
ea rischio mondo.

266
00:12:48,660 --> 00:12:51,950
>> Quindi, se vuoi saperne di più
su questo, vai a questo URL qui.

267
00:12:51,950 --> 00:12:54,450
Non c'è bisogno di un'azione
stasera se non sei

268
00:12:54,450 --> 00:12:57,116
tra quelli più comodo che
sono stati in esecuzione il proprio web

269
00:12:57,116 --> 00:12:59,810
server, nel qual caso si dovrebbe,
infatti, aggiornare il software.

270
00:12:59,810 --> 00:13:03,244
>> E anche questo è il titolo di
un discorso, e ora una carta,

271
00:13:03,244 --> 00:13:05,410
che abbiamo legati alla
sito web del corso per oggi.

272
00:13:05,410 --> 00:13:07,600
Era da un collega
di nome Ken Thompson, che

273
00:13:07,600 --> 00:13:10,120
è stato accettare un molto famoso
premio in informatica,

274
00:13:10,120 --> 00:13:13,495
e ha dato questo discorso alcuni anni
fa, in sostanza, su questo stesso argomento.

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

276
00:13:18,250 --> 00:13:20,520
Chiedere gente la domanda,
si dovrebbe davvero

277
00:13:20,520 --> 00:13:23,480
fiducia, in ultima analisi, la
software che hai ricevuto?

278
00:13:23,480 --> 00:13:26,100
Per esempio, tutti noi abbiamo
stata la scrittura di programmi,

279
00:13:26,100 --> 00:13:27,820
e siamo stati compilando
li con Clang.

280
00:13:27,820 --> 00:13:31,830
E per vostra conoscenza, hai scritto
tutti i programmi per CS50 dove c'è

281
00:13:31,830 --> 00:13:35,310
una porta sul retro di sorta, c'è un modo
che un cattivo ragazzo, se si esegue il programma,

282
00:13:35,310 --> 00:13:37,410
potrebbe prendere in consegna il vostro computer?

283
00:13:37,410 --> 00:13:38,310
Probabilmente no, giusto?

284
00:13:38,310 --> 00:13:40,180
Mario, e avidi, e di credito.

285
00:13:40,180 --> 00:13:41,680
Questi sono tutti piuttosto piccoli programmi.

286
00:13:41,680 --> 00:13:43,910
Dovresti essere abbastanza
male se effettivamente

287
00:13:43,910 --> 00:13:47,310
fatto tutto il computer vulnerabile
dopo aver scritto 10 o 20 righe di codice,

288
00:13:47,310 --> 00:13:49,690
o almeno a conoscenza di alcune
delle implicazioni di sicurezza.

289
00:13:49,690 --> 00:13:52,023
Ora io dico che scherzosamente,
ma stiamo andando a vedere oggi

290
00:13:52,023 --> 00:13:54,600
e questa settimana è in realtà
davvero, davvero facile

291
00:13:54,600 --> 00:13:57,980
per essere cattivo e rendere ancora
brevi programmi vulnerabili.

292
00:13:57,980 --> 00:14:02,880
>> Ma per ora, almeno, realizzare
che la domanda che si pone qui

293
00:14:02,880 --> 00:14:04,850
è circa Clang in un compilatore.

294
00:14:04,850 --> 00:14:08,360
Perché siamo stati fiduciosi Clang
per gli ultimi due o tre settimane?

295
00:14:08,360 --> 00:14:12,650
Chi può dire che chi ha scritto Clang
non ha avuto un "se" condizione in là

296
00:14:12,650 --> 00:14:17,680
che in sostanza iniettata alcuni zeri
e quelli in ogni programma si compila

297
00:14:17,680 --> 00:14:21,180
che avrebbe lasciato lui o lei di accesso
il computer quando si è addormentato

298
00:14:21,180 --> 00:14:23,580
e il vostro coperchio del portatile è aperta
e il computer è in esecuzione?

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

300
00:14:24,080 --> 00:14:28,350
Noi abbiamo questa sorta di diritto sistema onore
ora dove abbiamo fiducia che Clang è legit.

301
00:14:28,350 --> 00:14:30,000
Ti fidi che l'apparecchio è legit.

302
00:14:30,000 --> 00:14:34,430
Ti fidi che letteralmente ogni programma
sul vostro Mac o PC è affidabile.

303
00:14:34,430 --> 00:14:37,510
E come suggerisce questa semplice bug,
anche se non è dannoso,

304
00:14:37,510 --> 00:14:40,580
che non è assolutamente
probabile che sia il caso.

305
00:14:40,580 --> 00:14:42,350
>> Così si dovrebbe avere paura come l'inferno.

306
00:14:42,350 --> 00:14:45,560
Francamente, non c'è semplice
soluzione a questo altro

307
00:14:45,560 --> 00:14:48,185
di una sorta di consapevolezza sociale
la crescente complessità

308
00:14:48,185 --> 00:14:50,310
che stiamo costruendo in cima
dei nostri sistemi informatici,

309
00:14:50,310 --> 00:14:53,740
e come sempre più vulnerabili
potremmo benissimo essere.

310
00:14:53,740 --> 00:14:55,570
>> Ora, con quello detto, Breakout.

311
00:14:55,570 --> 00:14:59,889
Così Breakout è un problema impostato tre, e
Breakout è un gioco da ieri

312
00:14:59,889 --> 00:15:02,180
che si potrebbe ricordare, ma
per noi nel problema impostare tre,

313
00:15:02,180 --> 00:15:04,450
che ci permette di prendere
le cose su una tacca

314
00:15:04,450 --> 00:15:08,880
in modo che quando stiamo scrivendo programmi,
anche in una finestra di terminale come questo,

315
00:15:08,880 --> 00:15:14,670
possiamo effettivamente correre, in ultima analisi,
programmi grafici non

316
00:15:14,670 --> 00:15:17,800
a differenza di quelli che abbiamo avuto
l'accesso al Scratch.

317
00:15:17,800 --> 00:15:20,910
Quindi questo è il personale di
implementazione di Breakout,

318
00:15:20,910 --> 00:15:23,930
che è proprio questo mattone-rottura
gioco, che si sposta il paddle schiena

319
00:15:23,930 --> 00:15:27,590
e indietro, e si colpisce la palla
contro quei mattoncini colorati sulla parte superiore.

320
00:15:27,590 --> 00:15:30,020
Quindi questo ci sta portando
sorta di nuovo a dove

321
00:15:30,020 --> 00:15:33,180
siamo stati in grado di essere molto rapidamente
con Scratch, e ora con C,

322
00:15:33,180 --> 00:15:35,800
attuazione nostro
interfacce grafiche.

323
00:15:35,800 --> 00:15:38,960
>> Ma più di questo, questo
Set problema rappresenta il primo

324
00:15:38,960 --> 00:15:41,000
in cui stiamo dando
un mucchio di codice.

325
00:15:41,000 --> 00:15:43,940
E infatti, io porto esplicito
attenzione a questo, soprattutto perché

326
00:15:43,940 --> 00:15:47,090
per quelli meno confortevole, questo
problema fissato, almeno a prima vista,

327
00:15:47,090 --> 00:15:49,170
sta andando a sentire come
abbiamo preso su una tacca.

328
00:15:49,170 --> 00:15:51,540
Perché vi abbiamo dato,
per alcune delle ricerche

329
00:15:51,540 --> 00:15:54,930
e smistamento problemi nel pset,
un mucchio di codice che abbiamo scritto,

330
00:15:54,930 --> 00:15:56,680
e un paio di commenti
che dire "da fare"

331
00:15:56,680 --> 00:15:58,221
dove si deve riempire gli spazi vuoti.

332
00:15:58,221 --> 00:16:00,020
Quindi non troppo spaventoso, ma
è la prima volta

333
00:16:00,020 --> 00:16:03,370
vi stiamo consegnando il codice che avete bisogno di
prima di leggere, capire, e poi aggiungere a

334
00:16:03,370 --> 00:16:04,290
e completarlo.

335
00:16:04,290 --> 00:16:05,940
>> E poi con Breakout,
stiamo andando a fare lo stesso,

336
00:16:05,940 --> 00:16:08,740
dandovi qualche decina di più linee
di codice che, francamente, dare

337
00:16:08,740 --> 00:16:11,490
un sacco di quadro di riferimento per
il gioco ma fermarsi

338
00:16:11,490 --> 00:16:14,304
di attuare i mattoni
e la palla e la racchetta,

339
00:16:14,304 --> 00:16:15,970
ma facciamo implementare alcune altre caratteristiche.

340
00:16:15,970 --> 00:16:18,280
E anche che a prima vista, ancora una volta,
soprattutto se meno confortevole,

341
00:16:18,280 --> 00:16:21,480
potrebbe sembrare particolarmente scoraggiante e
Pensi che ci sono tante nuove funzioni

342
00:16:21,480 --> 00:16:24,070
è necessario avvolgere la vostra mente
intorno, e questo è vero.

343
00:16:24,070 --> 00:16:26,281
Ma tenere a mente, è
abbastanza come Scratch.

344
00:16:26,281 --> 00:16:28,780
Le probabilità sono non ha utilizzato tutti
i pezzi del puzzle in Scratch.

345
00:16:28,780 --> 00:16:31,120
Le probabilità sono che non ti importava di avvolgere
la vostra mente intorno tutti

346
00:16:31,120 --> 00:16:33,617
perché è bastato un
rapida occhiata per capire, oh,

347
00:16:33,617 --> 00:16:35,450
questo è quello che posso fare
con quel pezzo di puzzle.

348
00:16:35,450 --> 00:16:38,260
E infatti, nel problem set
3 spec, ti segnaliamo voi

349
00:16:38,260 --> 00:16:41,370
la documentazione che verrà
farvi conoscere alcune nuove funzioni,

350
00:16:41,370 --> 00:16:43,570
e in ultima analisi, la programmazione
Costruisce si utilizza.

351
00:16:43,570 --> 00:16:47,610
Condizioni, i cicli
variabili e funzioni

352
00:16:47,610 --> 00:16:50,720
è identico al
quello che abbiamo visto finora.

353
00:16:50,720 --> 00:16:53,560
>> Così in effetti, ciò che noi daremo
vi è un codice di esempio che

354
00:16:53,560 --> 00:16:56,110
consente di creare una finestra
che non sembra a differenza di questo,

355
00:16:56,110 --> 00:16:59,540
e infine trasformarlo in
qualcosa di molto simile.

356
00:16:59,540 --> 00:17:02,250
Approfittate quindi di CS50,
discutere l'orario di ufficio e di più,

357
00:17:02,250 --> 00:17:05,290
e prendere conforto nel fatto che
la quantità di codice da scrivere

358
00:17:05,290 --> 00:17:06,760
è in realtà non più di tanto.

359
00:17:06,760 --> 00:17:10,359
La prima sfida è solo per ambientarsi
a voi stessi di qualche codice che abbiamo scritto.

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

361
00:17:11,450 --> 00:17:15,810
>> Hai domande su pset3,
Shellshock, o in altro modo?

362
00:17:15,810 --> 00:17:19,226
>> PUBBLICO: Sembrava
passando con Breakout

363
00:17:19,226 --> 00:17:22,154
che il codice è quasi
uno stile orientato agli oggetti,

364
00:17:22,154 --> 00:17:24,675
ma ho pensato che fosse un C
object-oriented programma.

365
00:17:24,675 --> 00:17:26,050
SPEAKER 1: Una domanda eccellente.

366
00:17:26,050 --> 00:17:28,258
Quindi, nel guardare attraverso il
codice di distribuzione, il codice

367
00:17:28,258 --> 00:17:30,180
abbiamo scritto per pset3,
per chi ha familiarità, si

368
00:17:30,180 --> 00:17:32,230
sembra come se fosse un
poco orientato agli oggetti.

369
00:17:32,230 --> 00:17:33,800
Risposta breve è, è.

370
00:17:33,800 --> 00:17:38,130
Si tratta di una approssimazione di come si
potrebbe fare di codice orientato agli oggetti utilizzando

371
00:17:38,130 --> 00:17:41,850
un linguaggio come C, ma è
ancora in ultima analisi procedurale.

372
00:17:41,850 --> 00:17:44,900
Non esistono metodi all'interno di
le variabili, come vedrete.

373
00:17:44,900 --> 00:17:46,180
Ma ricorda che.

374
00:17:46,180 --> 00:17:48,780
E vedremo ancora una volta che la funzione
quando arriviamo a PHP e JavaScript

375
00:17:48,780 --> 00:17:49,946
verso la fine del semestre.

376
00:17:49,946 --> 00:17:53,667
Ma per ora, pensare ad esso come
un accenno di ciò che è a venire.

377
00:17:53,667 --> 00:17:54,250
Buona domanda.

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

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

380
00:17:56,550 --> 00:17:59,730
Così merge sort è stato il modo in cui
cose di sinistra ultima volta.

381
00:17:59,730 --> 00:18:03,250
E merge sort era fresco in
senso che era molto più veloce,

382
00:18:03,250 --> 00:18:07,100
almeno sulla base delle prove sommarie
abbiamo fatto la scorsa settimana, rispetto, ad esempio, bolla

383
00:18:07,100 --> 00:18:08,710
sort, selection sort, insertion sort.

384
00:18:08,710 --> 00:18:11,780
E ciò che era troppo pulito è solo
come succintamente e pulito

385
00:18:11,780 --> 00:18:12,810
si può esprimere.

386
00:18:12,810 --> 00:18:15,840
E che cosa abbiamo detto che era un superiore
bound sul tempo di esecuzione di merge

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

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

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

392
00:18:20,819 --> 00:18:23,776
E torneremo a ciò che
significa realmente o dove che viene da,

393
00:18:23,776 --> 00:18:25,570
ma questo era meglio
di quanto tempo di esecuzione

394
00:18:25,570 --> 00:18:28,440
che abbiamo visto per la bolla
selezione e insertion sort?

395
00:18:28,440 --> 00:18:30,610
Così n quadrato. n al quadrato
è più grande di questo,

396
00:18:30,610 --> 00:18:34,650
e anche se non è del tutto evidente,
sa che log n è minore di n,

397
00:18:34,650 --> 00:18:36,910
quindi se si fa n volte
qualcosa di più piccolo di n,

398
00:18:36,910 --> 00:18:38,680
che sta per essere inferiore a n al quadrato.

399
00:18:38,680 --> 00:18:40,130
E 'un po' di intuizione lì.

400
00:18:40,130 --> 00:18:42,190
Ma abbiamo pagato un prezzo per questo.

401
00:18:42,190 --> 00:18:47,000
Era veloce, ma un tema che ha iniziato
emergere la scorsa settimana è stato questo compromesso.

402
00:18:47,000 --> 00:18:49,804
Ho ottenuto la migliore prestazione
tempo saggio, ma cosa

403
00:18:49,804 --> 00:18:52,470
ho dovuto passare dall'altra
mano, al fine di ottenere che?

404
00:18:52,470 --> 00:18:53,591
>> PUBBLICO: Memoria.

405
00:18:53,591 --> 00:18:54,465
SPEAKER 1: dire ancora?

406
00:18:54,465 --> 00:18:55,173
PUBBLICO: Memoria.

407
00:18:55,173 --> 00:18:57,040
SPEAKER 1: Memoria, o
spazio più in generale.

408
00:18:57,040 --> 00:18:59,040
E non era super
evidente con i nostri uomini,

409
00:18:59,040 --> 00:19:02,240
ma ricordare che i nostri volontari
sono stati un passo avanti e un passo

410
00:19:02,240 --> 00:19:04,780
indietro come se ci fosse una matrice
qui, e come se ci fosse

411
00:19:04,780 --> 00:19:07,130
un secondo array qui che
potrebbero usare, perché noi

412
00:19:07,130 --> 00:19:09,080
da qualche parte necessaria per unire quelle persone.

413
00:19:09,080 --> 00:19:11,480
Non potevamo semplicemente scambiare sul posto.

414
00:19:11,480 --> 00:19:13,800
Così merge sort leva
è più spazio, che

415
00:19:13,800 --> 00:19:15,620
non abbiamo bisogno di
gli altri algoritmi,

416
00:19:15,620 --> 00:19:17,410
ma il lato positivo è che è molto più veloce.

417
00:19:17,410 --> 00:19:20,780
E, francamente, nello spazio reale mondo
questi days-- RAM, hard disk space--

418
00:19:20,780 --> 00:19:25,030
è relativamente a buon mercato, e così che è
non è necessariamente una cosa negativa.

419
00:19:25,030 --> 00:19:28,320
>> Quindi, diamo un rapido sguardo, un po '
più metodicamente, a quello che abbiamo fatto

420
00:19:28,320 --> 00:19:30,220
e perché abbiamo detto che era n log n.

421
00:19:30,220 --> 00:19:33,260
Così qui sono le otto numeri e la
otto volontari abbiamo avuto l'ultima volta.

422
00:19:33,260 --> 00:19:35,718
E la prima cosa che si fondono
Ordina ci ha detto di fare era quello?

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

424
00:19:37,010 --> 00:19:38,010
PUBBLICO: Divide in due.

425
00:19:38,010 --> 00:19:38,663
SPEAKER 1: dire ancora?

426
00:19:38,663 --> 00:19:39,650
PUBBLICO: Divide in due.

427
00:19:39,650 --> 00:19:40,610
SPEAKER 1: Divide in due, a destra.

428
00:19:40,610 --> 00:19:42,818
Questo ricorda molto
l'elenco telefonico, di dividere

429
00:19:42,818 --> 00:19:44,220
e conquistare più in generale.

430
00:19:44,220 --> 00:19:45,640
Così abbiamo guardato la metà sinistra.

431
00:19:45,640 --> 00:19:48,700
E poi una volta abbiamo detto, sorta
la metà sinistra degli elementi,

432
00:19:48,700 --> 00:19:49,690
cosa abbiamo successivo diciamo?

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

434
00:19:51,210 --> 00:19:54,860
Ordina la metà sinistra della sinistra
mezzo, che ci ha permesso di,

435
00:19:54,860 --> 00:19:57,570
dopo aver diviso in due,
concentrarsi su quattro e due.

436
00:19:57,570 --> 00:20:01,280
>> Come si ordina un elenco ora, in
giallo, di dimensione due, utilizzando Merge Sort?

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

438
00:20:02,330 --> 00:20:04,580
Beh, dividerlo a metà,
e ordinare la metà sinistra.

439
00:20:04,580 --> 00:20:07,100
E questo era il luogo dove le cose
ottenuto un po 'brevemente stupido.

440
00:20:07,100 --> 00:20:10,720
Come si ordina un elenco che è di
Taglia unica, come questo numero quattro qui?

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

442
00:20:12,330 --> 00:20:13,210
E 'ordinato.

443
00:20:13,210 --> 00:20:14,200
Il gioco è fatto.

444
00:20:14,200 --> 00:20:17,300
>> Ma allora come si fa a ordinare un elenco di
Un formato quando è il numero due?

445
00:20:17,300 --> 00:20:21,640
Beh, la stessa cosa, ma ora quello che era il
terzo e il passo fondamentale per merge sort?

446
00:20:21,640 --> 00:20:24,020
Si doveva unire sinistra
metà e la metà destra.

447
00:20:24,020 --> 00:20:26,580
E una volta che abbiamo fatto, abbiamo guardato
alle quattro, abbiamo guardato due.

448
00:20:26,580 --> 00:20:28,750
Abbiamo deciso tutto bene,
ovviamente due viene prima,

449
00:20:28,750 --> 00:20:31,840
così abbiamo messo due nella sua
posto, seguito da quattro.

450
00:20:31,840 --> 00:20:35,010
E ora si deve tipo di riavvolgere,
e questo è una sorta di caratteristica

451
00:20:35,010 --> 00:20:37,570
di un algoritmo come unione
Ordina, riavvolgere in memoria.

452
00:20:37,570 --> 00:20:40,240
Qual è stata la riga successiva della storia?

453
00:20:40,240 --> 00:20:41,780
Cosa devo concentrarmi sul prossimo?

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

455
00:20:43,110 --> 00:20:47,350
La metà destra della sinistra
mezzo, che è sei e otto.

456
00:20:47,350 --> 00:20:50,320
>> Quindi lasciatemi passo attraverso questo
senza che belaboring il punto di troppo.

457
00:20:50,320 --> 00:20:53,330
Sei e otto, poi sei è
ordinato, otto è ordinato.

458
00:20:53,330 --> 00:20:57,190
Unirli insieme come quella,
e ora il prossimo grande passo

459
00:20:57,190 --> 00:21:00,990
è, naturalmente, ordinare la metà di destra da
il primo passo di questo algoritmo.

460
00:21:00,990 --> 00:21:02,870
Quindi ci concentriamo su uno, tre, sette, cinque.

461
00:21:02,870 --> 00:21:04,540
Abbiamo poi concentriamo sulla metà sinistra.

462
00:21:04,540 --> 00:21:09,400
La metà sinistra di questo, la metà destra del
che, e poi si fondono in uno e tre.

463
00:21:09,400 --> 00:21:13,100
Poi la metà destra, poi a sinistra a metà
di esso, quindi la metà destra di esso.

464
00:21:13,100 --> 00:21:15,985
Unisci in, e adesso che passo rimane?

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

466
00:21:18,040 --> 00:21:22,460
Unire il grande metà sinistra e la grande
metà destra, così si va laggiù,

467
00:21:22,460 --> 00:21:27,330
poi due, poi tre, poi quattro, poi
cinque, poi sei, poi sette, poi otto.

468
00:21:27,330 --> 00:21:31,990
>> Così ora perché è questo in definitiva rivelando,
soprattutto se n e logaritmi più

469
00:21:31,990 --> 00:21:35,487
generalmente piuttosto sfuggirti,
almeno nella memoria recente?

470
00:21:35,487 --> 00:21:37,070
Beh, notare l'altezza di questa cosa.

471
00:21:37,070 --> 00:21:41,230
Avevamo otto elementi, e noi
diviso per due, a due, da due.

472
00:21:41,230 --> 00:21:44,590
Così log in base due di otto anni ci dà tre.

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

474
00:21:45,640 --> 00:21:48,540
E credetemi su che se
un po 'confuso su questo.

475
00:21:48,540 --> 00:21:54,710
Ma log in base due di otto è tre,
così abbiamo fatto tre strati di fusione.

476
00:21:54,710 --> 00:21:57,170
E quando ci siamo fusi
elementi, quanti elementi

477
00:21:57,170 --> 00:21:58,950
abbiamo guardiamo su ciascuno di tali righe?

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

479
00:22:00,212 --> 00:22:01,437
Un totale di n, giusto?

480
00:22:01,437 --> 00:22:04,020
Perché per unire la riga superiore,
anche se abbiamo fatto frammentario,

481
00:22:04,020 --> 00:22:05,990
abbiamo infine toccato ogni numero una volta.

482
00:22:05,990 --> 00:22:09,054
E in seconda fila, a
unire tali elenchi di dimensione due,

483
00:22:09,054 --> 00:22:10,470
abbiamo dovuto toccare ogni elemento una volta.

484
00:22:10,470 --> 00:22:12,690
E poi qui davvero
chiaramente in ultima fila,

485
00:22:12,690 --> 00:22:15,430
abbiamo dovuto toccare ciascuno di quelli
elementi di una volta, ma solo una volta,

486
00:22:15,430 --> 00:22:18,400
così si trova qui, allora, il nostro registro n n.

487
00:22:18,400 --> 00:22:21,780
>> Ed ora solo per rendere le cose un po '
più formale per un momento, se si

488
00:22:21,780 --> 00:22:24,260
dovevano ora analizzare questo
in una sorta di livello superiore

489
00:22:24,260 --> 00:22:28,340
e cercare di decidere, bene come
potreste andare su di esprimere

490
00:22:28,340 --> 00:22:31,780
il tempo di esecuzione di questo algoritmo
solo guardando e non

491
00:22:31,780 --> 00:22:33,590
utilizzando un esempio forzato?

492
00:22:33,590 --> 00:22:36,590
Beh, quanto tempo si dovrebbe dire un
un passo come questo in giallo avrebbe preso,

493
00:22:36,590 --> 00:22:37,173
se n <2 ritorno?

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

495
00:22:38,840 --> 00:22:39,830
Questo è un grande O di che cosa?

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

497
00:22:41,450 --> 00:22:44,540
Così sto vedendo uno, così un passo,
forse due passi perchè è se

498
00:22:44,540 --> 00:22:47,110
e poi tornare, ma è
costante di tempo, giusto?

499
00:22:47,110 --> 00:22:49,960
Così abbiamo detto O (1), e che è
come io esprimo questo.

500
00:22:49,960 --> 00:22:51,480
T, basta essere tempo di esecuzione.

501
00:22:51,480 --> 00:22:54,150
n è la dimensione dell'input,
quindi T (n), solo un modo elegante

502
00:22:54,150 --> 00:22:56,330
di dire la corsa
tempo dato input di dimensione n

503
00:22:56,330 --> 00:23:00,220
sta per essere dell'ordine
di tempo costante, O (1).

504
00:23:00,220 --> 00:23:01,970
>> Ma per il resto, che dire di questo?

505
00:23:01,970 --> 00:23:05,660
Come si dovrebbe esprimere il
tempo di questa linea gialla in esecuzione?

506
00:23:05,660 --> 00:23:06,250
T di che cosa?

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

508
00:23:09,440 --> 00:23:12,665
È possibile tipo di barare qui e
rispondere alla mia domanda ciclicamente.

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

510
00:23:14,770 --> 00:23:17,900
Quindi, se il tempo di esecuzione in
generale diciamo solo è T (n).

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

512
00:23:18,950 --> 00:23:22,490
E ora stai tipo di punting qui e
dicendo, beh, basta ordinare la metà sinistra,

513
00:23:22,490 --> 00:23:23,920
e poi ordinare la metà destra.

514
00:23:23,920 --> 00:23:27,520
Come potremmo simbolicamente rappresentare
il tempo di esecuzione di questa linea gialla?

515
00:23:27,520 --> 00:23:28,020
T di che cosa?

516
00:23:28,020 --> 00:23:29,360
Qual è la dimensione dell'input?

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

518
00:23:30,510 --> 00:23:31,057
n più di due.

519
00:23:31,057 --> 00:23:32,140
Perché non dico solo che?

520
00:23:32,140 --> 00:23:36,449
E allora questo è un altro T (n / 2) e poi
ancora una volta, se mi fondo due metà ordinate,

521
00:23:36,449 --> 00:23:38,615
quanti elementi sto andando
dover toccare totale?

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
Così posso esprimere questo,
solo per essere una sorta di fantasia,

525
00:23:42,790 --> 00:23:44,430
come il tempo di esecuzione in generale.

526
00:23:44,430 --> 00:23:51,140
T (n) è solo il tempo di esecuzione di T (n / 2),
più T (n / 2), a sinistra metà e metà a destra,

527
00:23:51,140 --> 00:23:55,360
più O (n), che è probabilmente n passi,
ma forse, se sto usando due dita,

528
00:23:55,360 --> 00:23:57,960
è il doppio
passi, ma è lineare.

529
00:23:57,960 --> 00:24:00,440
È certo numero di passi
questo è un fattore di n,

530
00:24:00,440 --> 00:24:02,270
così potremmo esprimere questo come questo.

531
00:24:02,270 --> 00:24:05,550
E questo è dove ora ci Punt al
posteriore del nostro libro di testo di matematica del liceo

532
00:24:05,550 --> 00:24:10,290
siamo che la ricorrenza in ultima analisi,
finisce pari questa, n log n volte,

533
00:24:10,290 --> 00:24:12,530
se effettivamente fare fuori
la matematica più formale.

534
00:24:12,530 --> 00:24:13,950
>> Ecco, questo è solo due punti di vista.

535
00:24:13,950 --> 00:24:17,500
Una numerico con una
hard-coded esempio rappresentativo

536
00:24:17,500 --> 00:24:21,140
utilizzando otto numeri, e una più
un'occhiata a come ci siamo arrivati.

537
00:24:21,140 --> 00:24:25,670
Ma ciò che è veramente interessante
è, ancora una volta, questa nozione di ciclismo.

538
00:24:25,670 --> 00:24:26,900
Non sto usando per cicli.

539
00:24:26,900 --> 00:24:29,860
Sto tipo di definizione
qualcosa in termini di se stessa,

540
00:24:29,860 --> 00:24:31,950
non solo con questa
funzione matematica,

541
00:24:31,950 --> 00:24:34,860
ma anche in termini di questa pseudo codice.

542
00:24:34,860 --> 00:24:38,260
Questo pseudo codice è ricorsiva
dal fatto che due delle sue linee

543
00:24:38,260 --> 00:24:42,310
è essenzialmente dicendogli di andare
utilizzarsi per risolvere un piccolo

544
00:24:42,310 --> 00:24:45,400
problema di piccole dimensioni,
e poi ancora e ancora

545
00:24:45,400 --> 00:24:48,820
e di nuovo fino a quando non si whittle
fino a questo cosiddetto caso base.

546
00:24:48,820 --> 00:24:52,810
>> Quindi cerchiamo di disegnare una realtà più convincente
take-away da questo come segue.

547
00:24:52,810 --> 00:24:58,420
Lasciami andare in gedit e prendo un
guardare alcuni dei codice sorgente di oggi,

548
00:24:58,420 --> 00:24:59,930
in particolare questo esempio qui.

549
00:24:59,930 --> 00:25:03,709
Sigma 0, che aggiunge a quanto pare
i numeri da uno a n.

550
00:25:03,709 --> 00:25:05,750
Vediamo quindi che cosa è familiare
e sconosciuto qui.

551
00:25:05,750 --> 00:25:08,690
In primo luogo abbiamo un paio di
comprende, quindi nulla di nuovo lì.

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

553
00:25:09,190 --> 00:25:11,370
Sono un po 'confuso su
questo dopo pochi giorni,

554
00:25:11,370 --> 00:25:13,790
ma che cosa abbiamo detto una
prototipo di una funzione è?

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

556
00:25:15,099 --> 00:25:16,015
PUBBLICO: [incomprensibile].

557
00:25:16,015 --> 00:25:16,905
SPEAKER 1: Che cos'è?

558
00:25:16,905 --> 00:25:17,800
PUBBLICO: Annunciamo esso.

559
00:25:17,800 --> 00:25:18,883
SPEAKER 1: Annunciamo esso.

560
00:25:18,883 --> 00:25:22,290
Quindi stai insegnando Clang, hey,
in realtà non applicazione del presente ancora,

561
00:25:22,290 --> 00:25:25,740
ma da qualche parte in questo file, presumibilmente,
sta per essere una funzione chiamata che cosa?

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
E questo è solo una promessa che
sta andando a guardare come questo.

565
00:25:30,540 --> 00:25:33,720
Sta andando a prendere un intero come
input-- e posso essere più esplicito

566
00:25:33,720 --> 00:25:36,570
e dire int n --e è
andando a restituire un int,

567
00:25:36,570 --> 00:25:39,900
ma mezzo punto e virgola, mm, vado a prendere in giro
per l'applicazione del presente un po 'più tardi.

568
00:25:39,900 --> 00:25:40,989
Anche in questo caso, Clang è muto.

569
00:25:40,989 --> 00:25:43,280
Sta solo andando a sapere che cosa
si dice verso il basso,

570
00:25:43,280 --> 00:25:45,765
così abbiamo bisogno di almeno dare
un accenno di ciò che è a venire.

571
00:25:45,765 --> 00:25:47,330
>> Ora diamo un'occhiata a principale qui.

572
00:25:47,330 --> 00:25:50,040
Facciamo scorrere qui e
vedere cosa principale sta facendo.

573
00:25:50,040 --> 00:25:53,780
Non è che molto di una funzione, e
infatti il ​​costrutto ecco familiare.

574
00:25:53,780 --> 00:25:57,590
Dichiaro una variabile n, e quindi
I tormentare ancora e ancora l'utente

575
00:25:57,590 --> 00:26:01,880
per un numero intero positivo con getInt,
e solo l'uscita di questo ciclo

576
00:26:01,880 --> 00:26:03,280
una volta che l'utente ha rispettato.

577
00:26:03,280 --> 00:26:05,670
Do While, abbiamo utilizzato per
importunare l'utente in quel modo.

578
00:26:05,670 --> 00:26:06,670
Ora questo è interessante.

579
00:26:06,670 --> 00:26:08,510
Dichiaro di un int chiamato "risposta".

580
00:26:08,510 --> 00:26:11,420
Assegno che il valore di ritorno
di una funzione chiamata "sigma".

581
00:26:11,420 --> 00:26:15,200
Non so che cosa che fa ancora, ma
Ricordo che dichiara che un momento fa.

582
00:26:15,200 --> 00:26:18,310
E poi sto passando l'
valore che l'utente ha digitato in, n,

583
00:26:18,310 --> 00:26:20,420
e poi vi riporto la risposta.

584
00:26:20,420 --> 00:26:22,260
Bene facciamo scorrere indietro
solo per un momento.

585
00:26:22,260 --> 00:26:28,620
Andiamo avanti in questa directory, fare
sigma 0, ed effettivamente eseguire questo programma

586
00:26:28,620 --> 00:26:30,490
e vedere cosa succede.

587
00:26:30,490 --> 00:26:35,930
Quindi, se vado avanti e correre
questo programma, ./sigma-0,

588
00:26:35,930 --> 00:26:40,139
e digito in un positivo
integer come due, Sigma,

589
00:26:40,139 --> 00:26:43,180
come il simbolo greco implica, è solo
andando a sommare tutti i numeri da

590
00:26:43,180 --> 00:26:44,320
azzeramento su un massimo di due.

591
00:26:44,320 --> 00:26:46,560
Quindi 0 più 1 più 2.

592
00:26:46,560 --> 00:26:48,830
Quindi questo dovrebbe auspicabilmente darmi 3.

593
00:26:48,830 --> 00:26:49,750
Questo è tutto quello che sta facendo.

594
00:26:49,750 --> 00:26:52,690
E allo stesso modo, se corro questo nuovo
e ho dato il numero tre,

595
00:26:52,690 --> 00:26:56,721
che è 3 più 2, in modo che sia
5, più 1 mi dovrebbe dare 6.

596
00:26:56,721 --> 00:26:59,470
E poi se ho veramente pazzesco e
iniziare a digitare in numeri più grandi,

597
00:26:59,470 --> 00:27:01,290
dovrebbe dare me
somme sempre più grandi.

598
00:27:01,290 --> 00:27:02,250
Ecco, questo è tutto.

599
00:27:02,250 --> 00:27:04,010
>> Così che cosa sigma assomiglia?

600
00:27:04,010 --> 00:27:05,430
Beh, è ​​abbastanza semplice.

601
00:27:05,430 --> 00:27:08,940
E 'come potremmo implementato
questo da un paio di settimane.

602
00:27:08,940 --> 00:27:11,120
"Int" sarà il tipo di ritorno.

603
00:27:11,120 --> 00:27:14,330
Sigma è il nome, e ci vuole
un m variabile invece di n.

604
00:27:14,330 --> 00:27:15,940
Cambierò che sulla parte superiore.

605
00:27:15,940 --> 00:27:17,340
Allora questo è solo un controllo di integrità.

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

607
00:27:18,430 --> 00:27:19,950
Vedremo perché in un attimo.

608
00:27:19,950 --> 00:27:24,220
Ora io dichiaro un'altra variabile,
somma, inizializzare a zero.

609
00:27:24,220 --> 00:27:28,140
Poi ho questo ciclo For
iterazione, a quanto pare per chiarezza,

610
00:27:28,140 --> 00:27:33,810
da i = 1 su un massimo di un = m, che è
qualunque sia l'utente digitato, e poi ho

611
00:27:33,810 --> 00:27:35,690
incrementare la somma in questo modo.

612
00:27:35,690 --> 00:27:37,360
E poi restituire la somma.

613
00:27:37,360 --> 00:27:38,440
>> Così un paio di domande.

614
00:27:38,440 --> 00:27:42,370
Uno, mi sostengono nel mio commento che questo
evita il rischio di un ciclo infinito.

615
00:27:42,370 --> 00:27:45,620
Perchè dovrebbe passare in un numero negativo
indurre, potenzialmente, un ciclo infinito?

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

617
00:27:49,396 --> 00:27:51,290
>> PUBBLICO: Non sarai mai raggiungere m.

618
00:27:51,290 --> 00:27:52,880
>> SPEAKER 1: Mai raggiungere m.

619
00:27:52,880 --> 00:27:55,880
Ma m viene passato, quindi cerchiamo di
considerare un semplice esempio.

620
00:27:55,880 --> 00:27:58,510
Se m viene passato dal
utente come uno negativo.

621
00:27:58,510 --> 00:28:00,059
Indipendentemente principale.

622
00:28:00,059 --> 00:28:01,850
Principale ci protegge da
anche questo, quindi sono appena

623
00:28:01,850 --> 00:28:04,680
essere davvero anale con
sigma per fare anche sicuri

624
00:28:04,680 --> 00:28:06,540
che l'ingresso non può essere negativo.

625
00:28:06,540 --> 00:28:10,130
Quindi, se m è negativo,
qualcosa di simile a uno negativo.

626
00:28:10,130 --> 00:28:11,930
Cosa succederà?

627
00:28:11,930 --> 00:28:14,390
Beh, mi sta per
ottenere inizializzato a uno,

628
00:28:14,390 --> 00:28:19,060
e poi mi sta per essere
minore o uguale a m?

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

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

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

632
00:28:26,930 --> 00:28:29,370
Che era-- cerchiamo di non,
cerchiamo di NIX questa storia.

633
00:28:29,370 --> 00:28:32,780
Non ho chiesto questa domanda, perché
il rischio che io alludo a

634
00:28:32,780 --> 00:28:38,360
non accadrà perché i è
andando sempre maggiore OK than--,

635
00:28:38,360 --> 00:28:39,871
Ho ritrattare questa domanda.

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

637
00:28:40,370 --> 00:28:42,030
Concentriamoci solo su questa parte qui.

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

639
00:28:44,210 --> 00:28:48,830
Perché ho Dichiaro alcuni
al di fuori del ciclo?

640
00:28:48,830 --> 00:28:52,010
Comunicazione on line 49 ho
dichiarato i all'interno del ciclo,

641
00:28:52,010 --> 00:28:54,950
ma in linea 48 ho
dichiarato alcuni fuori.

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

643
00:28:55,695 --> 00:28:56,611
PUBBLICO: [incomprensibile].

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

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

646
00:28:59,400 --> 00:29:03,360
Quindi, prima di tutto io di certo non lo faccio
vuole dichiarare e inizializzare somma

647
00:29:03,360 --> 00:29:06,130
a zero all'interno del
loop su ogni iterazione,

648
00:29:06,130 --> 00:29:09,370
perché questo sarebbe chiaramente sconfiggere l'
scopo di riassumere i numeri.

649
00:29:09,370 --> 00:29:11,770
Vorrei continuare a cambiare
il valore a zero.

650
00:29:11,770 --> 00:29:17,992
E inoltre, qual è un altro più arcane
ragione per quella stessa decisione di progettazione?

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

652
00:29:18,954 --> 00:29:20,279
>> PUBBLICO: [incomprensibile].

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

654
00:29:21,070 --> 00:29:24,060
Voglio accedervi fuori
dell'ansa troppo su quale linea?

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

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

657
00:29:26,400 --> 00:29:29,910
E sulla base della nostra regola di pollice
da un paio di lezioni fa,

658
00:29:29,910 --> 00:29:33,680
variabili hanno un ambito, in realtà, per il
parentesi graffe che li comprendono.

659
00:29:33,680 --> 00:29:38,190
Quindi, se io non dichiaro somma all'interno
di queste parentesi graffe esterne,

660
00:29:38,190 --> 00:29:40,250
Io non posso usarlo in linea 53.

661
00:29:40,250 --> 00:29:43,160
In altre parole, se ho dichiarato
somma qui, o anche all'interno della

662
00:29:43,160 --> 00:29:45,410
Per il ciclo, non ho potuto accedervi in ​​53.

663
00:29:45,410 --> 00:29:47,150
La variabile potrebbe effettivamente andato.

664
00:29:47,150 --> 00:29:48,579
Così un paio di motivi lì.

665
00:29:48,579 --> 00:29:50,370
Ma ora torniamo
e vedere cosa succede.

666
00:29:50,370 --> 00:29:51,730
Così sigma viene chiamato.

667
00:29:51,730 --> 00:29:55,640
Si aggiunge 1 più 2, o 1 più 2
oltre a 3, e poi restituisce il valore,

668
00:29:55,640 --> 00:29:59,660
memorizza in risposta, e printf qui
è per questo che sto vedendo sullo schermo.

669
00:29:59,660 --> 00:30:03,079
Quindi questo è quello che chiameremo un iterativo
approccio, dove l'iterazione solo

670
00:30:03,079 --> 00:30:03,870
significa utilizzare un ciclo.

671
00:30:03,870 --> 00:30:06,900
Un ciclo For, un ciclo While, un Do While
loop, solo facendo qualcosa di nuovo

672
00:30:06,900 --> 00:30:08,380
e ancora e ancora.

673
00:30:08,380 --> 00:30:13,505
>> Ma sigma è una specie di una funzione ordinata in
che ho potuto realizzare in modo diverso.

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

675
00:30:14,620 --> 00:30:19,120
Che dire di questa, che
solo per essere genere di freddo,

676
00:30:19,120 --> 00:30:21,880
mi permetta veramente a sbarazzarsi
di un lotto di distrazione

677
00:30:21,880 --> 00:30:24,380
perché questa funzione
è davvero molto semplice.

678
00:30:24,380 --> 00:30:27,780
Facciamo whittle giù solo
alle sue quattro linee principali

679
00:30:27,780 --> 00:30:30,410
e di sbarazzarsi di tutti i
commenti e parentesi graffe.

680
00:30:30,410 --> 00:30:34,334
Questa è una specie di mind-blowing
implementazione alternativa.

681
00:30:34,334 --> 00:30:37,250
Va bene, forse non mente-blowing,
ma è una specie di sexy, va bene,

682
00:30:37,250 --> 00:30:39,920
guardare a questa molto di più succintamente.

683
00:30:39,920 --> 00:30:43,120
Con appena quattro righe di codice,
Io prima ho questo controllo di integrità.

684
00:30:43,120 --> 00:30:45,732
Se m è inferiore o uguale a
pari a zero, sigma non ha senso.

685
00:30:45,732 --> 00:30:48,190
Dovrebbe solo essere in
questo caso per i numeri positivi,

686
00:30:48,190 --> 00:30:50,340
quindi sto solo andando a
restituire zero arbitrariamente

687
00:30:50,340 --> 00:30:53,210
così che abbiamo almeno
alcune cosiddetto caso base.

688
00:30:53,210 --> 00:30:54,430
>> Ma ecco la bellezza.

689
00:30:54,430 --> 00:30:59,930
La totalità di questa idea, aggiungendo l'
numeri da 1 a n o m in questo caso,

690
00:30:59,930 --> 00:31:02,630
può essere fatto secondo la tipologia di passare la patata bollente.

691
00:31:02,630 --> 00:31:04,947
Ebbene, qual è la somma di 1 a m?

692
00:31:04,947 --> 00:31:05,780
Beh, sai una cosa?

693
00:31:05,780 --> 00:31:11,949
E 'uguale alla somma di m
più la somma di 1 m meno 1.

694
00:31:11,949 --> 00:31:12,740
Beh, sai una cosa?

695
00:31:12,740 --> 00:31:13,940
Cosa c'è di sigma di m meno 1?

696
00:31:13,940 --> 00:31:17,860
Beh, se si segue questo tipo di
logicamente, è lo stesso che m meno 1

697
00:31:17,860 --> 00:31:21,415
più sigma di m meno 2.

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

699
00:31:22,480 --> 00:31:26,012
Così si può tipo di solo--
questo è come, se sei solo

700
00:31:26,012 --> 00:31:28,220
cercando di infastidire un amico
e ti chiedono una domanda,

701
00:31:28,220 --> 00:31:31,344
è sorta di rispondere con una domanda,
è possibile tipo di mantenere passare la patata bollente.

702
00:31:31,344 --> 00:31:34,560
Ma ciò che è fondamentale è che se si mantiene
rendendo la domanda più piccolo

703
00:31:34,560 --> 00:31:36,910
e più piccolo, sei
Non chiedere che cosa è sigma

704
00:31:36,910 --> 00:31:39,116
di n, ciò che è sigma di
n, che cosa è sigma di n?

705
00:31:39,116 --> 00:31:40,990
Ti stai chiedendo che cosa è
sigma di n, che cosa è sigma

706
00:31:40,990 --> 00:31:42,839
di n meno 1, qual è sigma di n meno 2?

707
00:31:42,839 --> 00:31:44,880
Alla fine la tua domanda
sta per diventare cosa?

708
00:31:44,880 --> 00:31:50,250
Qual è la sigma di uno o
pari a zero, qualche valore molto piccolo,

709
00:31:50,250 --> 00:31:52,220
e non appena si
ottenere che, il tuo amico,

710
00:31:52,220 --> 00:31:54,350
non si ha intenzione di chiedere
di nuovo la stessa domanda,

711
00:31:54,350 --> 00:31:55,975
si sta solo andando a dire, oh è pari a zero.

712
00:31:55,975 --> 00:31:58,490
Abbiamo finito di giocare questo tipo
di stupido gioco ciclico.

713
00:31:58,490 --> 00:32:02,950
>> Quindi ricorsione è l'atto di programmazione
di una funzione di chiamata stessa.

714
00:32:02,950 --> 00:32:06,630
Questo programma, quando viene compilato ed eseguito, è
andando a comportarsi esattamente allo stesso modo,

715
00:32:06,630 --> 00:32:09,620
ma ciò che è fondamentale è che all'interno
di una funzione chiamata sigma,

716
00:32:09,620 --> 00:32:13,150
vi è una linea di codice in cui
stiamo chiamando noi stessi,

717
00:32:13,150 --> 00:32:14,980
che normalmente sarebbe male.

718
00:32:14,980 --> 00:32:21,160
Ad esempio, cosa succede se ho
compilato questa, in modo da assicurarsi sigma--

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

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

721
00:32:25,050 --> 00:32:27,690
Intero positivo, per favore, 50 1275.

722
00:32:27,690 --> 00:32:30,810
Così che cosa la funzione sembra
essere, sulla base di una prova, corretto.

723
00:32:30,810 --> 00:32:34,917
Ma cosa succede se ho un po 'pericoloso
ed eliminare il cosiddetto caso base,

724
00:32:34,917 --> 00:32:37,750
e solo dire, anche io sto solo facendo
questo più complicato di quanto non sia.

725
00:32:37,750 --> 00:32:42,450
Diciamo solo calcolare la sigma
prendendo m e poi aggiungendo

726
00:32:42,450 --> 00:32:44,564
in sigma di un m meno?

727
00:32:44,564 --> 00:32:45,980
Ebbene, che cosa sta per succedere qui?

728
00:32:45,980 --> 00:32:47,140
Andiamo zoom out.

729
00:32:47,140 --> 00:32:52,920
Facciamo ricompilare il programma,
salvarlo, ricompilare il programma,

730
00:32:52,920 --> 00:33:00,450
e quindi pronto ./sigma-1 zoom in,
Inserisci il numero intero positivo per favore, 50.

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

732
00:33:02,180 --> 00:33:04,430
Quanti di voi sono disposti
a fess fino a vedere che?

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

734
00:33:04,950 --> 00:33:06,690
Quindi questo può accadere per
una serie di ragioni,

735
00:33:06,690 --> 00:33:09,148
e francamente questa settimana siamo
per darvi più di loro.

736
00:33:09,148 --> 00:33:11,780
Ma in questo caso, provare a
di ragionare a ritroso

737
00:33:11,780 --> 00:33:14,430
cosa sarebbe successo qui?

738
00:33:14,430 --> 00:33:17,400
Segmentation fault, dicevamo lo scorso
tempo, si riferisce ad un segmento di memoria.

739
00:33:17,400 --> 00:33:18,690
Qualcosa di brutto è accaduto.

740
00:33:18,690 --> 00:33:21,550
Ma che cosa era
meccanico che è andato storto

741
00:33:21,550 --> 00:33:25,000
qui a causa della mia rimozione
di quel cosiddetto caso base,

742
00:33:25,000 --> 00:33:26,870
dove sono tornato un valore hard-coded?

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

744
00:33:28,970 --> 00:33:30,460
Cosa pensi andato storto?

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

746
00:33:31,219 --> 00:33:32,135
>> PUBBLICO: [incomprensibile].

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

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

749
00:33:36,970 --> 00:33:37,550
Buona domanda.

750
00:33:37,550 --> 00:33:39,508
Quindi la dimensione del numero
che stavo riassumendo up

751
00:33:39,508 --> 00:33:41,920
ottenuto così grande che ha superato
la dimensione dello spazio di memoria.

752
00:33:41,920 --> 00:33:44,640
Buona idea, ma non fondamentalmente
andando a causare un incidente.

753
00:33:44,640 --> 00:33:48,230
Questo potrebbe causare integer overflow,
dove i bit appena capovolgere

754
00:33:48,230 --> 00:33:51,760
e poi ci scambiamo un davvero grande
per numero come un numero negativo,

755
00:33:51,760 --> 00:33:53,260
ma che in sé non causerà un crash.

756
00:33:53,260 --> 00:33:55,509
Perché alla fine del
giorno un int è ancora a 32 bit.

757
00:33:55,509 --> 00:33:57,640
Tu non stai andando a
accidentalmente rubare un po '33 °.

758
00:33:57,640 --> 00:33:58,431
Ma un buon pensiero.

759
00:33:58,431 --> 00:33:58,984
Già.

760
00:33:58,984 --> 00:33:59,900
>> PUBBLICO: [incomprensibile].

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

762
00:34:00,551 --> 00:34:02,300
SPEAKER 1: Il metodo
non smette mai di correre,

763
00:34:02,300 --> 00:34:06,658
e infatti si chiama di nuovo
e ancora e ancora e ancora

764
00:34:06,658 --> 00:34:08,449
e di nuovo, e nessuno di
quelle funzioni sempre

765
00:34:08,449 --> 00:34:13,310
finire perché la loro unica linea di
codice chiama themself ancora e ancora

766
00:34:13,310 --> 00:34:14,219
e di nuovo.

767
00:34:14,219 --> 00:34:16,080
E che cosa è veramente
succedendo qui, e ora ci

768
00:34:16,080 --> 00:34:18,100
può sorta di disegnare questo pittoricamente.

769
00:34:18,100 --> 00:34:20,899
Lasciami andare verso un
immagine solo per un attimo.

770
00:34:20,899 --> 00:34:22,940
Questa è una foto, che
alla fine rimpolpare

771
00:34:22,940 --> 00:34:26,336
più in dettaglio, di quello che sta succedendo
all'interno della memoria del computer.

772
00:34:26,336 --> 00:34:28,460
E si scopre che su
la parte inferiore di questa immagine

773
00:34:28,460 --> 00:34:29,709
è qualcosa che si chiama lo stack.

774
00:34:29,709 --> 00:34:31,920
Questo è un pezzo di
memoria, un pezzo di memoria RAM,

775
00:34:31,920 --> 00:34:33,920
questo è solo usato in qualsiasi momento
una funzione viene chiamata.

776
00:34:33,920 --> 00:34:36,239
Ogni volta che, un programmatore,
chiamare una funzione,

777
00:34:36,239 --> 00:34:38,860
il sistema operativo, come
Mac OS, Windows, o Linux,

778
00:34:38,860 --> 00:34:41,920
afferra un mucchio di byte, forse un
pochi kilobyte, forse pochi megabyte

779
00:34:41,920 --> 00:34:44,590
di memoria, li porge
a voi, e poi lascia

780
00:34:44,590 --> 00:34:47,650
si esegue la funzione utilizzando
qualunque variabili avete bisogno.

781
00:34:47,650 --> 00:34:50,699
E se poi chiama un altro
funzione ed un'altra funzione,

782
00:34:50,699 --> 00:34:53,590
si ottiene un'altra fetta di memoria
e un'altra fetta di memoria.

783
00:34:53,590 --> 00:34:57,090
>> E infatti, se questi vassoi verdi
da Annenberg rappresentare quel ricordo,

784
00:34:57,090 --> 00:34:59,870
ecco cosa succede il primo
volta che si chiama la funzione sigma.

785
00:34:59,870 --> 00:35:04,510
E 'come mettere un vassoio come questo
su ciò che è inizialmente uno stack vuoto.

786
00:35:04,510 --> 00:35:07,142
Ma poi se quel vassoio
si chiama, per così dire,

787
00:35:07,142 --> 00:35:08,850
chiamando un'altra istanza
di sigma, che è

788
00:35:08,850 --> 00:35:11,640
come chiedere il sistema operativo,
ooh, bisogno di un po 'di più memoria,

789
00:35:11,640 --> 00:35:12,520
me che dare.

790
00:35:12,520 --> 00:35:14,840
E poi viene accumulata su in cima.

791
00:35:14,840 --> 00:35:18,030
Ma ciò che è fondamentale è che
il primo cassetto è ancora lì,

792
00:35:18,030 --> 00:35:20,620
perché ha invocato questo secondo vassoio.

793
00:35:20,620 --> 00:35:23,500
Ora invece, chiamano sigma sigma,
è come chiedere di più memoria.

794
00:35:23,500 --> 00:35:25,830
Ottiene accumulato su qui.

795
00:35:25,830 --> 00:35:29,350
sigma chiamata sigma, che è un altro
vassoio che viene accumulata qui.

796
00:35:29,350 --> 00:35:32,942
E se continui a fare questo,
alla fine, tipo di mappare questo visiva

797
00:35:32,942 --> 00:35:35,525
a tale grafico, quello che sta succedendo a
accadere con la pila di vassoi?

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

799
00:35:37,480 --> 00:35:41,160
Si sta per superare l'importo
della memoria il computer dispone.

800
00:35:41,160 --> 00:35:45,790
E non appena questo vassoio verde
supera la linea orizzontale

801
00:35:45,790 --> 00:35:49,410
sopra stack e sopra quella parola heap,
che ci torneremo in futuro,

802
00:35:49,410 --> 00:35:50,410
che è una brutta cosa.

803
00:35:50,410 --> 00:35:52,810
Il mucchio è un diverso
segmento di memoria,

804
00:35:52,810 --> 00:35:55,190
e se si lascia che questi
vassoi palo e palo su,

805
00:35:55,190 --> 00:35:57,800
si sta andando a superare
il proprio segmento di memoria,

806
00:35:57,800 --> 00:36:00,420
e un programma è davvero andando in crash.

807
00:36:00,420 --> 00:36:02,930
>> Ora, come un a parte, questa idea
di ricorsione, quindi,

808
00:36:02,930 --> 00:36:06,500
può chiaramente portare a problemi, ma
non è necessariamente una cosa negativa.

809
00:36:06,500 --> 00:36:08,840
Perché prendere in considerazione, dopo
tutti, how-- e forse

810
00:36:08,840 --> 00:36:11,700
questo richiede un po 'di tempo per abituarsi
a --Come elegante o come semplice

811
00:36:11,700 --> 00:36:14,890
che l'attuazione di sigma è stato.

812
00:36:14,890 --> 00:36:17,440
E non stiamo andando ad utilizzare
ricorsione di tanto in CS50,

813
00:36:17,440 --> 00:36:20,780
ma in CS51, e davvero qualsiasi classe
dove manipolare strutture di dati

814
00:36:20,780 --> 00:36:23,640
come alberi, o alberi genealogici,
che hanno una certa gerarchia,

815
00:36:23,640 --> 00:36:26,000
è super, super utile.

816
00:36:26,000 --> 00:36:29,750
Ora, per inciso, in modo che si
come aspiranti scienziati informatici

817
00:36:29,750 --> 00:36:33,180
hanno familiarità con alcune delle Google
scherzi, se si va a Google

818
00:36:33,180 --> 00:36:36,345
e si guarda a ciò che è il
definizione di, diciamo, ricorsione, immettere.

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
Per inciso, ho tirato su alcuni.

822
00:36:42,670 --> 00:36:45,470
Questo era come 10 minuti di
procrastinazione questa mattina.

823
00:36:45,470 --> 00:36:52,890
Se anche Google "di traverso," avviso
inclinando la testa slightly--

824
00:36:52,890 --> 00:36:55,120
e allora questo è forse
più atroce di tutti

825
00:36:55,120 --> 00:36:57,286
dal momento che qualcuno ha speso come
la loro giornata attuazione del presente

826
00:36:57,286 --> 00:36:59,880
alcuni anni ago-- si accendono.

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

828
00:37:01,140 --> 00:37:04,540
Oh, wait-- questo è un bug.

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

830
00:37:08,410 --> 00:37:11,410
>> Quindi esecuzione su uno dei
più grandi siti del mondo

831
00:37:11,410 --> 00:37:13,510
sono questi stupidi piccole uova di Pasqua.

832
00:37:13,510 --> 00:37:16,690
Probabilmente consumano una
numero non banale di righe di codice

833
00:37:16,690 --> 00:37:19,280
solo così che possiamo avere
piccole cose divertenti come quella.

834
00:37:19,280 --> 00:37:22,140
Ma almeno ora si ottiene
alcuni di questi scherzi.

835
00:37:22,140 --> 00:37:28,330
>> Ora diamo uno sguardo ad alcuni dei
bianco giace abbiamo raccontato di ritardo,

836
00:37:28,330 --> 00:37:30,707
e iniziare a sbucciare indietro
alcuni strati tecnicamente

837
00:37:30,707 --> 00:37:32,790
in modo che si capisce davvero
quello che sta succedendo

838
00:37:32,790 --> 00:37:34,860
e si può capire
alcune delle minacce,

839
00:37:34,860 --> 00:37:38,060
come Shellshock, che
hanno iniziato a diventare

840
00:37:38,060 --> 00:37:41,110
in prima linea di ognuno di
attenzione, almeno nei media.

841
00:37:41,110 --> 00:37:45,810
Così qui è una funzione molto semplice
che restituisce nulla, nulla.

842
00:37:45,810 --> 00:37:46,790
Il suo nome è di swap.

843
00:37:46,790 --> 00:37:50,880
Prende in due variabili
e restituisce nulla.

844
00:37:50,880 --> 00:37:52,260
Prende in ae b.

845
00:37:52,260 --> 00:37:53,337
Quindi una rapida dimostrazione.

846
00:37:53,337 --> 00:37:54,170
Abbiamo portato questi in su.

847
00:37:54,170 --> 00:37:56,100
Potremmo anche prendere un po '
rompere qui solo per un attimo

848
00:37:56,100 --> 00:37:57,250
e hanno un po 'di qualcosa da bere.

849
00:37:57,250 --> 00:38:00,120
Se qualcuno non mi dispiacerebbe entrare
me qui solo per un attimo.

850
00:38:00,120 --> 00:38:01,830
Come su di te con la camicia marrone?

851
00:38:01,830 --> 00:38:02,335
Andiamo su.

852
00:38:02,335 --> 00:38:04,060

853
00:38:04,060 --> 00:38:05,260
Proprio quello di oggi.

854
00:38:05,260 --> 00:38:06,251
Grazie, però.

855
00:38:06,251 --> 00:38:08,000
Va bene, e abbiamo
venire che qui?

856
00:38:08,000 --> 00:38:08,660
Come ti chiami?

857
00:38:08,660 --> 00:38:09,360
>> SPEAKER 4: Laura.

858
00:38:09,360 --> 00:38:09,740
>> SPEAKER 1: Laura.

859
00:38:09,740 --> 00:38:10,370
Andiamo su.

860
00:38:10,370 --> 00:38:11,460

861
00:38:11,460 --> 00:38:13,850
Così Laura, molto semplice sfida di oggi.

862
00:38:13,850 --> 00:38:14,704

863
00:38:14,704 --> 00:38:15,370
Piacere di conoscerti yo.

864
00:38:15,370 --> 00:38:16,410

865
00:38:16,410 --> 00:38:16,910
Bene.

866
00:38:16,910 --> 00:38:21,179
Così abbiamo un po 'di latte qui e
abbiamo un po 'di succo d'arancia qui

867
00:38:21,179 --> 00:38:23,345
e alcune coppe che abbiamo
preso in prestito dalla Annenberg oggi.

868
00:38:23,345 --> 00:38:24,178
>> SPEAKER 4: Borrowed.

869
00:38:24,178 --> 00:38:27,240
SPEAKER 1: E intenzione di andare avanti
e vi darò mezzo bicchiere di questo.

870
00:38:27,240 --> 00:38:28,250

871
00:38:28,250 --> 00:38:28,800
Bene.

872
00:38:28,800 --> 00:38:30,750
E vi daremo la metà
un bicchiere di latte.

873
00:38:30,750 --> 00:38:31,905

874
00:38:31,905 --> 00:38:35,890
Oh, e solo così che si può
ricordare ciò che questo era come,

875
00:38:35,890 --> 00:38:38,860
Mi sono ricordato di portare
questo e oggi.

876
00:38:38,860 --> 00:38:42,030

877
00:38:42,030 --> 00:38:42,530
Bene.

878
00:38:42,530 --> 00:38:45,470
Se non ti dispiace, vediamo, abbiamo
li possono mettere sopra i vostri occhiali

879
00:38:45,470 --> 00:38:46,560
se vuoi.

880
00:38:46,560 --> 00:38:48,710
Questo sarà il mondo dagli occhi di Laura.

881
00:38:48,710 --> 00:38:49,210
Bene.

882
00:38:49,210 --> 00:38:53,820
Così il vostro obiettivo, dato due tazze di
liquido qui, latte e succo d'arancia,

883
00:38:53,820 --> 00:38:58,370
è scambiare i due contenuti in modo che l'
succo d'arancia va nella tazza del latte

884
00:38:58,370 --> 00:39:00,710
e il latte va in
la tazza di succo d'arancia.

885
00:39:00,710 --> 00:39:02,359
>> SPEAKER 4: Ricevo un'altra tazza?

886
00:39:02,359 --> 00:39:05,650
SPEAKER 1: Sono così contento che hai chiesto, anche se
sarebbe stato molto meglio di repertorio

887
00:39:05,650 --> 00:39:06,710
se non avessi chiesto.

888
00:39:06,710 --> 00:39:10,620
Ma sì, siamo in grado di offrire un terzo
coppa che è vuota, naturalmente.

889
00:39:10,620 --> 00:39:11,120
Bene.

890
00:39:11,120 --> 00:39:12,300
Così scambiare il contenuto lì.

891
00:39:12,300 --> 00:39:16,100

892
00:39:16,100 --> 00:39:17,050
Molto bello.

893
00:39:17,050 --> 00:39:20,390

894
00:39:20,390 --> 00:39:21,305
Molto buona.

895
00:39:21,305 --> 00:39:23,121

896
00:39:23,121 --> 00:39:24,745
Stai facendo questo notevole attenzione.

897
00:39:24,745 --> 00:39:26,970

898
00:39:26,970 --> 00:39:28,655
E un passo tre.

899
00:39:28,655 --> 00:39:30,390

900
00:39:30,390 --> 00:39:31,350
Bene.

901
00:39:31,350 --> 00:39:31,930
Eccellente.

902
00:39:31,930 --> 00:39:33,930
Un grande applauso
sarebbe bene per Laura.

903
00:39:33,930 --> 00:39:36,500

904
00:39:36,500 --> 00:39:37,000
Bene.

905
00:39:37,000 --> 00:39:40,790
Abbiamo un piccolo regalo d'addio
per voi, ma mi permetta di prendere questi.

906
00:39:40,790 --> 00:39:42,620
Vi ringrazio tanto.

907
00:39:42,620 --> 00:39:46,170
Così un semplice esempio, però,
per dimostrare che se si fa

908
00:39:46,170 --> 00:39:48,300
vogliono scambiare i contenuti
di due contenitori,

909
00:39:48,300 --> 00:39:52,360
o chiamiamoli variabili,
avete bisogno di qualche deposito temporaneo

910
00:39:52,360 --> 00:39:56,710
mettere in scena uno dei contenuti in modo
che si può effettivamente fare lo swap.

911
00:39:56,710 --> 00:40:01,790
Così in effetti, di questo codice fonte qui in
C rappresentativa esattamente questo.

912
00:40:01,790 --> 00:40:06,340
Se il succo d'arancia era una e il latte
era b, e abbiamo voluto scambiare i due,

913
00:40:06,340 --> 00:40:08,990
si potrebbe provare qualcosa di creativo
versando una nell'altra,

914
00:40:08,990 --> 00:40:11,031
ma che probabilmente non sarebbe
finire particolarmente bene.

915
00:40:11,031 --> 00:40:15,260
E così usiamo una tazza terza, chiamata
esso PGT, T-M-P per convenzione,

916
00:40:15,260 --> 00:40:19,370
e mettere il contenuto del
GU in quella, poi scambiare una tazza,

917
00:40:19,370 --> 00:40:22,610
poi mettere la GU in
tazza originale, così

918
00:40:22,610 --> 00:40:25,320
raggiungimento, esattamente come
Laura ha fatto, lo swap.

919
00:40:25,320 --> 00:40:26,850
>> Quindi cerchiamo di fare esattamente questo.

920
00:40:26,850 --> 00:40:30,110
Lasciami andare avanti e aprire
up un esempio che è

921
00:40:30,110 --> 00:40:32,720
denominata appunto "no
scambiare, "perché questo non è

922
00:40:32,720 --> 00:40:36,180
fatto come semplice come si potrebbe pensare.

923
00:40:36,180 --> 00:40:41,190
Quindi, in questo programma, notare che
Sto utilizzando stdio.h, il nostro vecchio amico.

924
00:40:41,190 --> 00:40:43,130
Ho il prototipo
per lo swap lassù, che

925
00:40:43,130 --> 00:40:45,450
significa che la sua attuazione di
probabilmente basso,

926
00:40:45,450 --> 00:40:48,050
e vediamo cosa principale
programma sta andando a fare per me.

927
00:40:48,050 --> 00:40:52,020
Ho Dichiaro int x ottiene
uno, e int y ottiene due.

928
00:40:52,020 --> 00:40:54,930
Quindi, pensare a quelli come GU
e latte, rispettivamente.

929
00:40:54,930 --> 00:40:57,100
E poi ho solo un
printf dicendo x è questo

930
00:40:57,100 --> 00:41:00,120
e y è questo, solo così posso
vedere visivamente quello che sta succedendo.

931
00:41:00,120 --> 00:41:03,810
Poi ho printf sostenendo
che sto scambiando i due,

932
00:41:03,810 --> 00:41:07,100
e poi stampare un
sostengono che stanno scambiati,

933
00:41:07,100 --> 00:41:09,300
Io e stampare le x e y di nuovo.

934
00:41:09,300 --> 00:41:13,010
Quindi qui in swap è
esattamente quello che ha fatto Laura,

935
00:41:13,010 --> 00:41:16,240
e esattamente quello che abbiamo visto su
schermo un momento fa.

936
00:41:16,240 --> 00:41:19,380
>> Quindi cerchiamo di andare avanti e
essere assai deluso.

937
00:41:19,380 --> 00:41:24,690
Non fare di swap, ed eseguire nessuna di swap,
zoom sull'uscita qui.

938
00:41:24,690 --> 00:41:28,320
Immettere x è 1, y è 2, scambiando scambiati.

939
00:41:28,320 --> 00:41:32,700
x è ancora 1, e y è ancora 2.

940
00:41:32,700 --> 00:41:37,630
Così, anche se, francamente, questo sembra
Esattamente come, anche se più tecnicamente,

941
00:41:37,630 --> 00:41:40,730
quello che ha fatto Laura, non sembrano funzionare.

942
00:41:40,730 --> 00:41:42,130
Allora perché?

943
00:41:42,130 --> 00:41:46,630
Beh, si scopre che, quando
scriviamo un programma come questo

944
00:41:46,630 --> 00:41:51,590
che ha sia principale, evidenziato qui,
e poi un'altra funzione, come scambio,

945
00:41:51,590 --> 00:41:54,230
evidenziato qui, che
chiama, il mondo

946
00:41:54,230 --> 00:41:57,030
sembra un po 'qualcosa di simile
questi vassoi un momento fa.

947
00:41:57,030 --> 00:42:00,440
Quando principale prima viene chiamato,
che è come chiedere di sistema operativo

948
00:42:00,440 --> 00:42:04,030
per un po 'di memoria per ogni locale
variabili come x e y che principale ha,

949
00:42:04,030 --> 00:42:05,660
e finiscono proprio lì.

950
00:42:05,660 --> 00:42:10,920
Ma se le chiamate principali di swap, e principale
passa per scambiare due argomenti, a e b,

951
00:42:10,920 --> 00:42:16,410
succo d'arancia e latte, non è come
consegnando il succo d'arancia e il latte

952
00:42:16,410 --> 00:42:17,500
di Laura.

953
00:42:17,500 --> 00:42:21,300
Ciò che un computer fa, è esso
passa copie del succo d'arancia

954
00:42:21,300 --> 00:42:27,110
e copie del latte a Laura, in modo che
ciò che è in ultima analisi, all'interno di questo vassoio

955
00:42:27,110 --> 00:42:32,510
è il valore di uno e due, o GU
e latte, ma loro copie,

956
00:42:32,510 --> 00:42:34,790
in modo che a questo punto
nella storia, ci

957
00:42:34,790 --> 00:42:36,930
è succo d'arancia e latte in ciascuno di questi vassoi.

958
00:42:36,930 --> 00:42:39,260
C'è un uno e due
in ciascuno di questi vassoi,

959
00:42:39,260 --> 00:42:41,720
e la funzione di swap è effettivamente funzionando.

960
00:42:41,720 --> 00:42:46,090
Li sta scambiando all'interno
del vassoio secondo più in alto,

961
00:42:46,090 --> 00:42:48,147
ma che lo scambio non ha alcun impatto.

962
00:42:48,147 --> 00:42:49,980
E sulla base di solo alcuni
principio di base che abbiamo

963
00:42:49,980 --> 00:42:52,970
parlato prima, e anzi
a pochi minuti fa, cosa

964
00:42:52,970 --> 00:42:58,770
potrebbe spiegare perché cambiare
A e B all'interno di scambio

965
00:42:58,770 --> 00:43:05,560
non ha alcun effetto su x ed y, sebbene
Ho passato x e y per la funzione swap.

966
00:43:05,560 --> 00:43:08,750
Qual è la parola chiave qui che
potrebbe semplicisticamente spiegare?

967
00:43:08,750 --> 00:43:11,250

968
00:43:11,250 --> 00:43:12,627
Penso che ho sentito qui?

969
00:43:12,627 --> 00:43:13,335
PUBBLICO: Return.

970
00:43:13,335 --> 00:43:14,085
SPEAKER 1: Return?

971
00:43:14,085 --> 00:43:14,590
Non tornare.

972
00:43:14,590 --> 00:43:15,895
Andiamo con un altro.

973
00:43:15,895 --> 00:43:16,395
Che cos'è?

974
00:43:16,395 --> 00:43:17,080
>> PUBBLICO: [incomprensibile].

975
00:43:17,080 --> 00:43:20,000
>> SPEAKER 1: OK, così abbiamo potuto return--
rendere il lavoro ritorno nella storia,

976
00:43:20,000 --> 00:43:21,914
ma c'è una spiegazione ancora più semplice.

977
00:43:21,914 --> 00:43:22,580
PUBBLICO: Scope.

978
00:43:22,580 --> 00:43:23,288
SPEAKER 1: Ambito di applicazione.

979
00:43:23,288 --> 00:43:24,300
Prendo portata.

980
00:43:24,300 --> 00:43:27,290
Così ambito, ricordare dove
la nostra x e y dichiarati.

981
00:43:27,290 --> 00:43:30,840
Sono dichiarate all'interno
di principale fino qui.

982
00:43:30,840 --> 00:43:33,200
A e B, nel frattempo, sono
effettivamente dichiarata

983
00:43:33,200 --> 00:43:35,930
interno di scambio, non del tutto in
le parentesi graffe, ma ancora

984
00:43:35,930 --> 00:43:37,690
nell'area generale di swap.

985
00:43:37,690 --> 00:43:40,560
E così effettivamente, a e b
esistere solo all'interno di questo vassoio

986
00:43:40,560 --> 00:43:44,850
da Annenberg, questo
secondo pezzo di codice.

987
00:43:44,850 --> 00:43:49,500
Quindi stiamo davvero cambiando la copia, ma
che non è poi così utile.

988
00:43:49,500 --> 00:43:52,190
>> Quindi diamo un'occhiata a
questo livello un po 'inferiore.

989
00:43:52,190 --> 00:43:55,430
Ho intenzione di tornare in
la directory di origine,

990
00:43:55,430 --> 00:43:58,330
e ho intenzione di primo
zoom in qui, e solo

991
00:43:58,330 --> 00:44:02,290
per confermare che sono in questo
finestra di terminale più grande,

992
00:44:02,290 --> 00:44:04,430
il programma è ancora comportarsi così.

993
00:44:04,430 --> 00:44:06,840
Supponiamo ora che questo
non è intenzionale.

994
00:44:06,840 --> 00:44:10,090
Chiaramente volevo swap
lavoro, così ci si sente come un insetto.

995
00:44:10,090 --> 00:44:12,780
Ora potrei iniziare ad aggiungere un
sacco di printf di al mio codice,

996
00:44:12,780 --> 00:44:16,010
stampare x qui, y su
qui, una qui, b qui.

997
00:44:16,010 --> 00:44:18,220
Ma francamente, questo è probabilmente quello che
che hai fatto per un paio di settimane

998
00:44:18,220 --> 00:44:20,190
ora, in orario di ufficio
e in casa quando si lavora

999
00:44:20,190 --> 00:44:22,150
su pset cercando di trovare alcuni bug.

1000
00:44:22,150 --> 00:44:25,560
Ma vedrete, se non avete già,
che problema ha impostato tre si introduce

1001
00:44:25,560 --> 00:44:31,630
ad un comando chiamato GDB,
dove GDB, debugger GNU,

1002
00:44:31,630 --> 00:44:34,040
stessa ha un sacco di
caratteristiche che può effettivamente

1003
00:44:34,040 --> 00:44:38,160
cerchiamo di capire le situazioni
in questo modo, ma più convincente,

1004
00:44:38,160 --> 00:44:39,940
risolvere problemi e trovare bug.

1005
00:44:39,940 --> 00:44:40,940
Quindi ho intenzione di fare questo.

1006
00:44:40,940 --> 00:44:44,770
Invece di ./noswap, sono invece
andando a correre GDB ./noswap.

1007
00:44:44,770 --> 00:44:47,410

1008
00:44:47,410 --> 00:44:51,200
In altre parole, ho intenzione di correre la mia
programma non in Bash, il nostro nuovo amico

1009
00:44:51,200 --> 00:44:51,850
oggi.

1010
00:44:51,850 --> 00:44:53,970
Io vado a correre la mia
programma noswap all'interno

1011
00:44:53,970 --> 00:44:56,900
di questo altro programma chiamato
GDB, che è un debugger, che

1012
00:44:56,900 --> 00:45:01,035
è un programma che è progettato per aiutare
voi umani trovare e rimuovere i bug.

1013
00:45:01,035 --> 00:45:03,410
Quindi, se ho colpito Corri qui, c'è
un importo atroce di testo

1014
00:45:03,410 --> 00:45:04,868
che hai davvero mai leggere.

1015
00:45:04,868 --> 00:45:07,290
E 'essenzialmente una distrazione
dal prompt, che

1016
00:45:07,290 --> 00:45:10,030
Sto andando a colpire Control-L
per arrivare fino in cima lì.

1017
00:45:10,030 --> 00:45:11,800
Questo è il prompt di GDB.

1018
00:45:11,800 --> 00:45:15,550
Se voglio eseguire questo programma ora,
come questo piccolo foglietto di oggi

1019
00:45:15,550 --> 00:45:21,860
scivolo suggerisce, Run è il primo
I comandi che intendevamo introdurre.

1020
00:45:21,860 --> 00:45:25,150
E sto solo andando a digitare
correre qui dentro di GDB,

1021
00:45:25,150 --> 00:45:26,811
e in effetti ha funzionato il mio programma.

1022
00:45:26,811 --> 00:45:29,310
Ora c'è qualche ulteriore
uscite della schermata come questa,

1023
00:45:29,310 --> 00:45:31,910
ma questo è GDB solo di essere anale
e ci dice cosa sta succedendo.

1024
00:45:31,910 --> 00:45:34,451
Non devi davvero preoccupare
su questi dettagli adesso.

1025
00:45:34,451 --> 00:45:36,890
Ma ciò che è veramente cool
GDB, se faccio questo again--

1026
00:45:36,890 --> 00:45:42,100
Control-L cancella il screen-- let me go
avanti e di tipo "break principale," in tal modo,

1027
00:45:42,100 --> 00:45:45,743
quando ho colpito Enter, l'impostazione che cosa è
chiamato un punto di interruzione a noswap.c,

1028
00:45:45,743 --> 00:45:51,270
linea 16, che è dove GDB
capito il mio programma in realtà

1029
00:45:51,270 --> 00:45:53,070
è, la mia funzione è in realtà.

1030
00:45:53,070 --> 00:45:55,070
Questo ignoreremo per ora
ma questo è l'indirizzo

1031
00:45:55,070 --> 00:45:57,310
nella memoria specificamente di questa funzione.

1032
00:45:57,310 --> 00:46:00,240
Così ora quando digito corro,
notare ciò che è cool qui.

1033
00:46:00,240 --> 00:46:05,650
Il mio programma interrompe alla linea I
detto GDB per mettere in pausa l'esecuzione in.

1034
00:46:05,650 --> 00:46:09,850
Quindi non devo cambiare ora il mio codice,
aggiungere qualche printf di, ricompilare, eseguire nuovamente

1035
00:46:09,850 --> 00:46:13,300
esso, cambiare, aggiungere un po 'di printf,
salvarlo, ricompilarlo, eseguirlo.

1036
00:46:13,300 --> 00:46:18,100
Posso solo a piedi attraverso il mio programma
passo dopo passo per passo a velocità umana,

1037
00:46:18,100 --> 00:46:20,880
non al tipo Intel-inside di velocità.

1038
00:46:20,880 --> 00:46:24,580
>> Così ora notare questa linea
appare qui, e se dovessi tornare

1039
00:46:24,580 --> 00:46:27,800
al mio programma gedit,
notare che questo è in realtà

1040
00:46:27,800 --> 00:46:29,280
la prima riga di codice.

1041
00:46:29,280 --> 00:46:31,240
C'è la linea 16 in gedit.

1042
00:46:31,240 --> 00:46:34,610
C'è la linea 16 all'interno GDB, e anche
se questa interfaccia in bianco e nero

1043
00:46:34,610 --> 00:46:37,760
non è quasi come utente
amichevole, questo significa

1044
00:46:37,760 --> 00:46:41,680
tale linea 16 non è stato eseguito
ancora, ma sta per essere.

1045
00:46:41,680 --> 00:46:46,220
Quindi, in effetti, se digito stampa
x, non printf, solo stampa x,

1046
00:46:46,220 --> 00:46:50,730
Ottengo un valore fasullo lì pari a zero,
perché x non è stata ancora inizializzata.

1047
00:46:50,730 --> 00:46:54,760
Quindi ho intenzione di scrivere il prossimo, o, se si
vuole essere di fantasia, solo n per il prossimo.

1048
00:46:54,760 --> 00:46:59,090
Ma quando digito prossima entrare, ora
notare che passa per la linea 17.

1049
00:46:59,090 --> 00:47:02,840
Quindi, logicamente, se ho giustiziato
linea 16 e ora tipo di stampa x,

1050
00:47:02,840 --> 00:47:03,640
cosa devo vedere?

1051
00:47:03,640 --> 00:47:04,970

1052
00:47:04,970 --> 00:47:05,520
Uno.

1053
00:47:05,520 --> 00:47:07,820
>> E ora questo è certamente confuso.

1054
00:47:07,820 --> 00:47:11,260
$ 2 è solo un modo elegante di, se
vuole fare riferimento a tale valore in seguito,

1055
00:47:11,260 --> 00:47:12,510
si può dire "il segno del dollaro due."

1056
00:47:12,510 --> 00:47:13,480
E 'come un riferimento all'indietro.

1057
00:47:13,480 --> 00:47:14,570
Ma per ora, basta ignorarlo.

1058
00:47:14,570 --> 00:47:17,070
La cosa interessante è ciò che è
sulla destra del segno uguale.

1059
00:47:17,070 --> 00:47:21,000
E ora, se digito il prossimo di nuovo
e stampare y, dovrei vedere 2.

1060
00:47:21,000 --> 00:47:23,870
Posso anche ora stampare
x di nuovo, e francamente,

1061
00:47:23,870 --> 00:47:27,130
se sto diventando un po 'confuso su
dove mi trovo, posso tipo di lista per lista

1062
00:47:27,130 --> 00:47:30,590
e solo vedere alcune contesto attorno
Il punto che sto davvero a.

1063
00:47:30,590 --> 00:47:35,180
E ora posso scrivere
prossimo, e c'è x è 1.

1064
00:47:35,180 --> 00:47:36,300
Ora scrivo successivo.

1065
00:47:36,300 --> 00:47:37,710
Oh, y è 2.

1066
00:47:37,710 --> 00:47:40,750
E ancora, è confusa,
perché l'output di GDB

1067
00:47:40,750 --> 00:47:43,044
viene commista con la mia uscita.

1068
00:47:43,044 --> 00:47:45,710
Ma se si tiene a mente, da
guardando avanti e indietro al vostro codice

1069
00:47:45,710 --> 00:47:47,740
o posa fuori lato
a fianco, forse, avrete

1070
00:47:47,740 --> 00:47:51,020
vedo che in realtà io sono solo
passando attraverso il mio programma.

1071
00:47:51,020 --> 00:47:54,620
>> Ma notare cosa succede dopo, letteralmente.

1072
00:47:54,620 --> 00:47:56,380
Ecco la linea 22.

1073
00:47:56,380 --> 00:48:01,315
Lasciami andare su di esso, spostando in tal modo il
a 23, e se stampo x ora, ancora uno.

1074
00:48:01,315 --> 00:48:03,890
E se stampo y ora, ancora uno.

1075
00:48:03,890 --> 00:48:05,820
Quindi questo non è un esercizio utile.

1076
00:48:05,820 --> 00:48:07,450
Quindi cerchiamo di rifare questo.

1077
00:48:07,450 --> 00:48:10,069
Lasciami andare indietro fino alla
ancora superiore e il tipo di esecuzione.

1078
00:48:10,069 --> 00:48:12,110
E sta dicendo che il programma
che è in fase di debug

1079
00:48:12,110 --> 00:48:14,109
ha già iniziato,
avviata dall'inizio.

1080
00:48:14,109 --> 00:48:15,420
Sì, facciamolo di nuovo.

1081
00:48:15,420 --> 00:48:22,000
E questa volta facciamolo prossimo,
Avanti, Avanti, Avanti, Avanti,

1082
00:48:22,000 --> 00:48:24,180
ma ora le cose si fanno interessanti.

1083
00:48:24,180 --> 00:48:27,760
Ora voglio fare un passo in
swap, quindi non mi tipo successivo.

1084
00:48:27,760 --> 00:48:34,380
Digito passo, e ora notarlo
mi ha saltato alla linea noswap.c 33.

1085
00:48:34,380 --> 00:48:37,240
Se dovessi tornare a gedit, che cosa è la linea 33?

1086
00:48:37,240 --> 00:48:40,500
Questa è la prima vera
riga di codice all'interno di swap.

1087
00:48:40,500 --> 00:48:44,150
Che è bello, perché ora posso
tipo di curiosare e ottenere curioso

1088
00:48:44,150 --> 00:48:46,052
quanto a che cosa sta succedendo veramente in là.

1089
00:48:46,052 --> 00:48:46,760
Permettetemi di stampare 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
Perché tmp ha qualche
pazzo, il valore spazzatura fasullo?

1093
00:48:51,438 --> 00:48:54,579

1094
00:48:54,579 --> 00:48:56,120
PUBBLICO: Non è stato inizializzato.

1095
00:48:56,120 --> 00:48:57,150
SPEAKER 1: Non è stato inizializzato.

1096
00:48:57,150 --> 00:49:00,270
E infatti, quando si esegue un programma,
si è dato un sacco di memoria

1097
00:49:00,270 --> 00:49:03,392
dal sistema operativo, ma si
non sono inizializzati i valori,

1098
00:49:03,392 --> 00:49:05,600
così qualunque bit sei
vedere qui, anche se è

1099
00:49:05,600 --> 00:49:07,770
questo pazzo grande negativo
numero, significa solo

1100
00:49:07,770 --> 00:49:10,750
che quelli sono i resti di
qualche precedente utilizzo di tale RAM,

1101
00:49:10,750 --> 00:49:13,050
anche se non ho
Mi serve ancora.

1102
00:49:13,050 --> 00:49:17,086
Così ora ho intenzione di andare avanti e di tipo
prossimo, e se io ora Tipo di stampa tmp,

1103
00:49:17,086 --> 00:49:17,835
cosa devo vedere?

1104
00:49:17,835 --> 00:49:19,570

1105
00:49:19,570 --> 00:49:23,360
Qualunque sia il valore di uno stato,
a è il primo argomento, basta

1106
00:49:23,360 --> 00:49:25,550
x come è stato il primo
cosa che viene passato in,

1107
00:49:25,550 --> 00:49:30,450
così un e x dovrebbe essere la stessa,
quindi stampare tmp mi deve stampare una.

1108
00:49:30,450 --> 00:49:36,360
>> Quindi, quello che vedrete nel set problema
tre è un tutorial di sorta su GDB,

1109
00:49:36,360 --> 00:49:40,020
ma si rende conto che questo è l'inizio
di uno sguardo a uno strumento che sarà effettivamente

1110
00:49:40,020 --> 00:49:42,774
aiutano a risolvere i problemi
in modo molto più efficace.

1111
00:49:42,774 --> 00:49:44,690
Quello che siamo in ultima analisi,
andando a fare il Mercoledì

1112
00:49:44,690 --> 00:49:48,180
è iniziare a sbucciare indietro di pochi strati
e rimuovere alcune ruote di formazione.

1113
00:49:48,180 --> 00:49:50,496
Quella cosa chiamata stringa che
abbiamo usato per qualche tempo,

1114
00:49:50,496 --> 00:49:53,370
stiamo andando a prendere lentamente che via
da voi e iniziare a parlare di

1115
00:49:53,370 --> 00:49:55,725
qualcosa di più esotericamente
conosciuto come char *,

1116
00:49:55,725 --> 00:49:59,550
ma stiamo andando a fare questa bella e
prima dolcemente, anche se i puntatori,

1117
00:49:59,550 --> 00:50:02,730
come si chiamano, può fare un po '
cose molto cattive, se abusato,

1118
00:50:02,730 --> 00:50:06,040
guardando un po 'claymation da
il nostro amico Nick Parlante da Stanford

1119
00:50:06,040 --> 00:50:09,670
University, un professore di computer
scienza che ha messo insieme questa anteprima

1120
00:50:09,670 --> 00:50:11,075
di ciò che è a venire questo Mercoledì.

1121
00:50:11,075 --> 00:50:12,196

1122
00:50:12,196 --> 00:50:13,400
>> [RIPRODUZIONE VIDEO]

1123
00:50:13,400 --> 00:50:13,900
Ehi, Binky.

1124
00:50:13,900 --> 00:50:14,930

1125
00:50:14,930 --> 00:50:15,780
Svegliati.

1126
00:50:15,780 --> 00:50:17,240
E 'tempo di puntatore divertimento.

1127
00:50:17,240 --> 00:50:18,260

1128
00:50:18,260 --> 00:50:19,350
>> -Che È?

1129
00:50:19,350 --> 00:50:21,150
Ulteriori informazioni su puntatori?

1130
00:50:21,150 --> 00:50:22,050
Oh, goody!

1131
00:50:22,050 --> 00:50:22,897

1132
00:50:22,897 --> 00:50:23,730
[FINE RIPRODUZIONE VIDEO]

1133
00:50:23,730 --> 00:50:25,396
SPEAKER 1: che vi attende il Mercoledì.

1134
00:50:25,396 --> 00:50:26,440
Ci vediamo allora.

1135
00:50:26,440 --> 00:50:27,106
[RIPRODUZIONE VIDEO]

1136
00:50:27,106 --> 00:50:30,420
-E Ora, pensieri profondi,
da Daven Farnham.

1137
00:50:30,420 --> 00:50:33,980

1138
00:50:33,980 --> 00:50:35,900
>> -Perché Stiamo imparando C?

1139
00:50:35,900 --> 00:50:36,785
Perché non A +?

1140
00:50:36,785 --> 00:50:38,550

1141
00:50:38,550 --> 00:50:40,910
>> [Risate]

1142
00:50:40,910 --> 00:50:42,160
>> [FINE RIPRODUZIONE VIDEO]