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

2
00:00:12,040 --> 00:00:16,460
>> COLUNA 1: Tudo bem, essa é CS50,
e este é o início da quarta semana

3
00:00:16,460 --> 00:00:20,420
e como você já deve ter ouvido ou
ler, o mundo está acabando.

4
00:00:20,420 --> 00:00:23,520
Indo ao redor da internet
tem sido de conhecimento e conscientização

5
00:00:23,520 --> 00:00:27,100
de um bug em um programa, um
linguagem de programação chamada Bash.

6
00:00:27,100 --> 00:00:32,729
Este foi lindamente marca
como Shellshock, ou a porta Bash,

7
00:00:32,729 --> 00:00:35,485
mas artigos como estes
Não foram pouco frequentes.

8
00:00:35,485 --> 00:00:38,807
E, de fato, muitos deles trazem
recordações de Heartbleed,

9
00:00:38,807 --> 00:00:41,640
que você pode ter notado na
pressione novamente na primavera passada, que

10
00:00:41,640 --> 00:00:43,980
foi igualmente bastante dramática.

11
00:00:43,980 --> 00:00:47,110
Agora, aqueles de vocês aqui
hoje, como muitos de vocês têm,

12
00:00:47,110 --> 00:00:50,330
mesmo se você não entende o que
é tudo sobre, ouviu falar de Shellshock?

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

14
00:00:51,370 --> 00:00:54,245
Tudo bem, e como muitos de vocês
têm computadores que são vulneráveis?

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

16
00:00:55,680 --> 00:01:00,250
OK, não deve ser muito, muito mais mãos
até agora, por razões veremos.

17
00:01:00,250 --> 00:01:02,580
>> Vamos dar uma olhada no que está
vem acontecendo nos meios de comunicação

18
00:01:02,580 --> 00:01:05,304
e, em seguida, explicar um pouco
aqui para nós tecnicamente.

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

20
00:01:07,670 --> 00:01:11,250
>> COLUNA 2: Os especialistas em segurança têm
alertou que uma falha grave poderia

21
00:01:11,250 --> 00:01:15,650
ser de cerca de centenas de afectar
milhões de usuários da rede no mundo.

22
00:01:15,650 --> 00:01:20,600
Então, qual é exatamente o erro que tem sido
apelidado Shellshock, eo que ele faz?

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

24
00:01:23,720 --> 00:01:28,910
Bem, Shellshock também é conhecido como o
Bug Bash, o software que explora.

25
00:01:28,910 --> 00:01:33,230
Hackers usam vírus para escanear vulnerável
sistemas rodando Linux e Unix

26
00:01:33,230 --> 00:01:36,300
sistemas operacionais e infectá-las.

27
00:01:36,300 --> 00:01:38,730
Bash é um shell de linha de comando.

28
00:01:38,730 --> 00:01:43,460
Isso permite aos usuários enviar comandos para lançar
programas e funcionalidades no software

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

30
00:01:45,250 --> 00:01:49,980
É normalmente utilizado por programadores, e
não deve ser aberto ao mundo exterior,

31
00:01:49,980 --> 00:01:51,590
embora Shellshock muda isso.

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

33
00:01:54,160 --> 00:01:57,910
>> Bem, worringly, alguns analistas
advertem que poderia ser uma ameaça maior,

34
00:01:57,910 --> 00:02:01,580
Shellshock porque permite total
controle de uma máquina infectada,

35
00:02:01,580 --> 00:02:06,030
Considerando Heartbleed só permitiu
hackers para espionar computadores.

36
00:02:06,030 --> 00:02:09,130
É tão sério, é
foi avaliado a 10 de 10

37
00:02:09,130 --> 00:02:11,900
para a gravidade do National
Vulnerability Database.

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

39
00:02:15,530 --> 00:02:20,015
2/3 de todos os servidores web estão no
risco, incluindo alguns computadores Mac.

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

41
00:02:22,760 --> 00:02:25,600
Bem, certifique-se de
corrigir seus sistemas agora.

42
00:02:25,600 --> 00:02:29,330
Qualquer um que hospeda um site em funcionamento
os sistemas operacionais afetados

43
00:02:29,330 --> 00:02:31,800
deve agir o mais rápido possível.

44
00:02:31,800 --> 00:02:35,390
Qualquer um que pode pagar deve olhar
para seu aplicativo de monitoramento e web

45
00:02:35,390 --> 00:02:37,355
firewalls de olhar para qualquer ataque.

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

47
00:02:39,979 --> 00:02:41,770
Palestrante 3: A pior coisa
que poderia acontecer é

48
00:02:41,770 --> 00:02:45,080
que alguém iria escrever um código que
iria e verificar automaticamente

49
00:02:45,080 --> 00:02:48,280
a internet e afetaria
todos esses computadores.

50
00:02:48,280 --> 00:02:50,710
E uma vez que eles fazem isso, bem,
a pior coisa que poderia fazer

51
00:02:50,710 --> 00:02:53,300
é simplesmente apagar tudo,
ou fechar os sites de baixo.

52
00:02:53,300 --> 00:02:55,360
Para que pudéssemos ver os danos
a partir desse ponto de vista,

53
00:02:55,360 --> 00:02:58,300
onde teríamos pessoas mal-intencionadas
que apenas decidir causar estragos

54
00:02:58,300 --> 00:03:02,534
reunindo sistemas para baixo ou a exclusão
arquivos, e coisas assim.

55
00:03:02,534 --> 00:03:05,200
COLUNA 2: Alguns dizem que este é um
dos mais difíceis de medir

56
00:03:05,200 --> 00:03:08,080
bugs em anos, e
Pode levar semanas ou mesmo

57
00:03:08,080 --> 00:03:10,820
meses para determinar seu impacto final.

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

59
00:03:12,180 --> 00:03:15,560
>> COLUNA 1: Então, tudo isso é verdade,
mas o engraçado é que, quase todos

60
00:03:15,560 --> 00:03:18,330
das imagens que você acabou de ver,
exceto talvez o teclado,

61
00:03:18,330 --> 00:03:20,930
não tem nada a ver com
o bug qualquer.

62
00:03:20,930 --> 00:03:23,960
Servidores e fios e assim por diante,
É uma espécie de tangencialmente relacionado,

63
00:03:23,960 --> 00:03:27,410
mas no centro é realmente muito
familiarizado o que está acontecendo aqui.

64
00:03:27,410 --> 00:03:30,050
Na verdade, deixe-me entrar
nosso aparelho CS50.

65
00:03:30,050 --> 00:03:32,910
Deixe-me ir em frente e maximizar
a janela de terminal aqui.

66
00:03:32,910 --> 00:03:36,020
E vocês têm vindo a utilizar este,
ou a versão integrada do mesmo,

67
00:03:36,020 --> 00:03:39,460
no gedit para escrever programas,
digitar comandos, e assim por diante,

68
00:03:39,460 --> 00:03:43,690
e esta é na verdade, e tem
foi por semanas, Bash, B-A-S-H.

69
00:03:43,690 --> 00:03:46,890
Este é o Bourne-again Shell,
que é apenas uma maneira elegante de dizer,

70
00:03:46,890 --> 00:03:50,220
este é um programa que tem um
piscar rápido, eficaz,

71
00:03:50,220 --> 00:03:51,970
que fica lá esperando
para a entrada para você.

72
00:03:51,970 --> 00:03:53,920
E é o comando
interface de linha através da qual

73
00:03:53,920 --> 00:03:57,650
Vocês foram a execução de comandos e
em última análise, compilação e, em seguida, executando

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

75
00:03:58,400 --> 00:04:01,320
>> Mas Bash é também uma programação
linguagem no seguinte sentido.

76
00:04:01,320 --> 00:04:05,460
Você sabe que existem comandos como
cd e ls e também clang e outros,

77
00:04:05,460 --> 00:04:09,580
mas você pode definir seus próprios comandos
por implementá-las em Bash.

78
00:04:09,580 --> 00:04:11,420
Agora nós não vamos
entrar em grandes detalhes

79
00:04:11,420 --> 00:04:16,089
como para bater a linguagem de programação, mas
sabe, por exemplo, que, no momento,

80
00:04:16,089 --> 00:04:17,607
não há nenhum comando chamado "Olá".

81
00:04:17,607 --> 00:04:19,440
Por isso, pode ser encontrada em
um desses pacotes.

82
00:04:19,440 --> 00:04:20,856
Não está instalado no meu computador.

83
00:04:20,856 --> 00:04:21,870
Pergunte ao seu administrador.

84
00:04:21,870 --> 00:04:26,030
Mas se eu quero que haja um programa de
chamado "Olá" em Bash, ou pelo meu aviso,

85
00:04:26,030 --> 00:04:30,810
Eu posso realmente usar uma sintaxe que é
bem como C. Não é bem a mesma coisa,

86
00:04:30,810 --> 00:04:35,020
mas parece muito semelhante a um
função, ainda faltam alguns detalhes.

87
00:04:35,020 --> 00:04:38,090
Nada parece acontecer,
mas agora se eu digitar "Olá",

88
00:04:38,090 --> 00:04:40,960
você pode realmente escrever uma
programa, não em C, não em Java,

89
00:04:40,960 --> 00:04:44,280
não noutro programação
linguagem, mas em si Bash.

90
00:04:44,280 --> 00:04:47,630
>> Agora, a chave aqui é que eu escrevi o
nome eu queria dar a este novo comando,

91
00:04:47,630 --> 00:04:50,820
e os parênteses são também
simbólica de este ser uma função.

92
00:04:50,820 --> 00:04:54,010
Como um aparte, você também pode fazer o divertimento
as coisas, e de fato, mesmo no Mac OS,

93
00:04:54,010 --> 00:04:55,620
este é um programa chamado Terminal.

94
00:04:55,620 --> 00:04:58,800
Ele vem embutido no de ninguém
computador que tenha um Mac nesta sala,

95
00:04:58,800 --> 00:05:03,640
e você pode fazer coisas semelhantes em Mac
OS, mas você pode ir mais além.

96
00:05:03,640 --> 00:05:07,110
E isso é um pouco tangencial,
mas é o tipo de diversão.

97
00:05:07,110 --> 00:05:09,715
Lembrei-me hoje de manhã,
quando se pensa sobre isso,

98
00:05:09,715 --> 00:05:13,279
de um pequeno jogo que eu costumava jogar
com um dos ex-TFs do CS50

99
00:05:13,279 --> 00:05:16,570
em que a qualquer momento ele iria a pé
seu teclado com o seu ecrã desbloqueado,

100
00:05:16,570 --> 00:05:23,611
Gostaria de executar um comando
como isso-- "dizer Olá".

101
00:05:23,611 --> 00:05:26,610
E agora qualquer momento ele voltou para sua
teclado depois limpei a tela

102
00:05:26,610 --> 00:05:27,985
e ele iria sentar,
tentar fazer algum trabalho,

103
00:05:27,985 --> 00:05:29,250
listar o conteúdo de sua directory--

104
00:05:29,250 --> 00:05:29,510
>> [AUDIO REPRODUÇÃO]

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

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

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

108
00:05:32,120 --> 00:05:35,030
>> COLUNA 1: Então, para ser justo,
não era, na verdade, "Olá".

109
00:05:35,030 --> 00:05:36,894
Geralmente era algo
mais parecido com que--

110
00:05:36,894 --> 00:05:37,560
[AUDIO REPRODUÇÃO]

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

112
00:05:37,750 --> 00:05:39,320
COLUNA 1: --aquela I would--
assim que seu computador fosse

113
00:05:39,320 --> 00:05:42,170
Juro para ele a qualquer momento ele realmente
sentou-se à do teclado.

114
00:05:42,170 --> 00:05:46,265
E muito rapidamente ele descobriu
não deixar sua tela desbloqueado.

115
00:05:46,265 --> 00:05:48,730
Mas isso sugere o tipo
de diversão estúpida que você

116
00:05:48,730 --> 00:05:50,210
pode ter algo como Bash.

117
00:05:50,210 --> 00:05:52,770
Mas é um pouco mais
sério, com certeza, que isso.

118
00:05:52,770 --> 00:05:57,235
E, de fato, este é um dos
A maioria dos bugs perigosos e duradouros

119
00:05:57,235 --> 00:05:58,860
que realmente atingiu o mundo globalmente.

120
00:05:58,860 --> 00:06:02,060
Este erro tem sido em torno
para cerca de 20 anos,

121
00:06:02,060 --> 00:06:05,780
e você vai ser atingido em apenas um
momento de sua relativa simplicidade.

122
00:06:05,780 --> 00:06:07,990
>> Portanto, este é um representante
manda que se

123
00:06:07,990 --> 00:06:10,448
possuir um Mac, literalmente agora
quando você tem a sua tampa aberta,

124
00:06:10,448 --> 00:06:12,940
você pode tentar digitar em que
programa chamado Terminal.

125
00:06:12,940 --> 00:06:15,410
Terminal está sob
Aplicações Utilities--

126
00:06:15,410 --> 00:06:18,790
Pela primeira vez, os usuários do Windows não tem que
preocupar com isso threat-- especial

127
00:06:18,790 --> 00:06:22,310
mas aqueles de vocês com Macs pode digitar
isso em uma janela que eu vou fazer aqui,

128
00:06:22,310 --> 00:06:24,210
e se você digitar
que para este programa

129
00:06:24,210 --> 00:06:28,830
chamado Terminal, como eu vou fazer agora,
Se você ver a palavra "vulnerável"

130
00:06:28,830 --> 00:06:32,200
o computador é
vulneráveis ​​à exploração.

131
00:06:32,200 --> 00:06:33,850
>> Agora, o que isso realmente significa?

132
00:06:33,850 --> 00:06:35,870
E este é reconhecidamente
uma sintaxe muito louco,

133
00:06:35,870 --> 00:06:39,050
mas vamos ao menos tirar
alguns dos aspectos interessantes.

134
00:06:39,050 --> 00:06:42,567
Portanto, há uma sintaxe que parece
um pouco familiarizado, pelo menos, a partir do C

135
00:06:42,567 --> 00:06:43,950
e programação em geral.

136
00:06:43,950 --> 00:06:47,550
Vejo alguns parênteses,
ponto e vírgula, chaves e tal,

137
00:06:47,550 --> 00:06:50,820
mas verifica-se que este
coisa estúpida aqui em amarelo

138
00:06:50,820 --> 00:06:53,580
é essencialmente uma função
que não faz nada.

139
00:06:53,580 --> 00:06:57,840
Os meios de cólon fazer nada, ea
ponto e vírgula significa parar de fazer nada.

140
00:06:57,840 --> 00:07:00,250
Assim, dentro destas
chaves, o fato de

141
00:07:00,250 --> 00:07:02,440
que eu tenho um igual
assinar para a esquerda, este

142
00:07:02,440 --> 00:07:05,500
É, essencialmente, criar
um comando ou de uma variável,

143
00:07:05,500 --> 00:07:09,520
chamado x, e atribuindo-lhe
que pouco amarelo de código lá.

144
00:07:09,520 --> 00:07:14,040
Isso poderia ser algo como "echo
Olá "ou" dizer bip "ou algo

145
00:07:14,040 --> 00:07:15,120
semelhante ao.

146
00:07:15,120 --> 00:07:17,780
Mas observe se os seus olhos
vagar mais para a direita,

147
00:07:17,780 --> 00:07:22,150
não há mais a esta linha de
apenas o fim desse ponto e vírgula.

148
00:07:22,150 --> 00:07:25,160
"Echo vulnerável", e em seguida,
além disso há ainda mais.

149
00:07:25,160 --> 00:07:26,530
Outro ponto e vírgula, o bash-c :.

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

151
00:07:28,120 --> 00:07:34,050
>> Então, longa história curta,
esta linha de código é

152
00:07:34,050 --> 00:07:36,660
suficiente para convincente
um computador que é

153
00:07:36,660 --> 00:07:39,830
vulneráveis ​​a fazer algo
que você quer que ele faça,

154
00:07:39,830 --> 00:07:44,290
porque há um bug no qual Bash
embora Bash deveria parar

155
00:07:44,290 --> 00:07:48,980
linhas de leitura da direita comando
lá depois do texto amarelo,

156
00:07:48,980 --> 00:07:52,520
por um ano de idade bug 20-plus,
Bash foi realmente lendo

157
00:07:52,520 --> 00:07:56,780
além desse ponto e vírgula e bonita
muito fazendo o que é dito.

158
00:07:56,780 --> 00:07:59,070
>> Então, qual é a implicação
de que, em última análise?

159
00:07:59,070 --> 00:08:01,340
Eu apenas disse "echo Olá"
ou "echo vulnerável"

160
00:08:01,340 --> 00:08:05,449
mas que se você fez algo
realmente maliciosa, como rm-rf *,

161
00:08:05,449 --> 00:08:07,240
que você não pode
já escreveu anteriormente,

162
00:08:07,240 --> 00:08:08,920
e, francamente, você provavelmente
não deve muito em breve,

163
00:08:08,920 --> 00:08:10,700
porque você pode fazer uma
muitos danos com ele.

164
00:08:10,700 --> 00:08:11,210
Por quê?

165
00:08:11,210 --> 00:08:12,990
rm faz o que, é claro?

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

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

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

169
00:08:16,430 --> 00:08:18,180
Portanto, é um chamado
wild card, então isso significa

170
00:08:18,180 --> 00:08:20,410
apagar tudo em
o diretório atual.

171
00:08:20,410 --> 00:08:23,379
r acontece para significar recursiva,
o que significa que se o que você está excluindo

172
00:08:23,379 --> 00:08:26,420
é um diretório, e lá dentro
é outros arquivos e outros diretórios,

173
00:08:26,420 --> 00:08:28,950
recursivamente mergulhar lá
e apagar tudo isso.

174
00:08:28,950 --> 00:08:31,040
E-f é o pior de todos eles.

175
00:08:31,040 --> 00:08:32,580
Alguém sabe o que significa f aqui?

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

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

178
00:08:34,360 --> 00:08:37,830
Assim forçar os meios, inclusive
Se esta é uma má idéia,

179
00:08:37,830 --> 00:08:40,939
fazê-lo sem me avisar
para confirmação.

180
00:08:40,939 --> 00:08:43,230
Então, você sabe, nós rimos
isso, mas, francamente, eu provavelmente

181
00:08:43,230 --> 00:08:44,972
digite isso várias vezes
um dia, porque a realidade

182
00:08:44,972 --> 00:08:47,210
é que é o caminho mais rápido para
excluir um monte de coisas.

183
00:08:47,210 --> 00:08:48,590
Mas, mesmo que eu tenha feito algum dano.

184
00:08:48,590 --> 00:08:53,100
>> Mas se você fosse para enganar um computador
para definir alguma variável estúpido

185
00:08:53,100 --> 00:08:56,810
ou função chamada x, mas depois
enganar o computador em execução

186
00:08:56,810 --> 00:09:00,030
para além dos limites dessa
função, além disso ponto e vírgula,

187
00:09:00,030 --> 00:09:04,430
você poderia realmente enganar um computador
para executar algo como rm-rf

188
00:09:04,430 --> 00:09:07,810
ou o comando de Email
ou o comando Copiar.

189
00:09:07,810 --> 00:09:11,400
Qualquer coisa, literalmente, você pode fazer com o
computador, seja apagando arquivos,

190
00:09:11,400 --> 00:09:15,350
a criação de arquivos, enviar spam para alguém,
atacando algum servidor remotamente,

191
00:09:15,350 --> 00:09:17,190
se você pode expressá-lo
com um comando, você

192
00:09:17,190 --> 00:09:19,120
pode enganar um computador para fazer isso.

193
00:09:19,120 --> 00:09:21,510
>> Agora, o que é um exemplo de
como você pode fazer isso?

194
00:09:21,510 --> 00:09:24,300
Bem, há um monte de computadores
no Bash internet funcionando.

195
00:09:24,300 --> 00:09:26,390
Todos os usuários nos Mac estão entre eles.

196
00:09:26,390 --> 00:09:30,390
Um monte de servidores Linux estão entre
eles também, e servidores Unix.

197
00:09:30,390 --> 00:09:32,630
O Windows novamente fica
relativamente fora do gancho

198
00:09:32,630 --> 00:09:34,590
a menos que você tenha instalado
software especial.

199
00:09:34,590 --> 00:09:37,130
Agora um monte de servidores, por
exemplo, servidores web são executados,

200
00:09:37,130 --> 00:09:39,840
e, de facto, é talvez o Linux
mais popular sistema operacional

201
00:09:39,840 --> 00:09:43,060
para rodar em computadores na internet
que estão servindo páginas da rede.

202
00:09:43,060 --> 00:09:44,910
Agora, como veremos mais tarde
no semestre, quando

203
00:09:44,910 --> 00:09:48,470
você envia uma solicitação de
seu browser-- Chrome,

204
00:09:48,470 --> 00:09:50,790
Internet Explorer, whatever--
para um servidor remoto,

205
00:09:50,790 --> 00:09:53,730
verifica-se que, apesar de
você acabou de digitar www.example.com,

206
00:09:53,730 --> 00:09:59,590
seu navegador está enviando uma mensagem
isso é um pouco mais misteriosa, como este.

207
00:09:59,590 --> 00:10:01,239
>> Mas note um pouco de algo estranho.

208
00:10:01,239 --> 00:10:03,030
As primeiras duas linhas
Eu nunca tinha visto antes,

209
00:10:03,030 --> 00:10:04,904
mas eles não se parecem
particularmente ameaçador.

210
00:10:04,904 --> 00:10:08,030
Mas note o que eu roubei
para a terceira linha aqui.

211
00:10:08,030 --> 00:10:13,390
Se um bandido foram para enviar uma mensagem
assim de seu computador

212
00:10:13,390 --> 00:10:17,270
a um Mac ou um vulnerável
servidor Linux vulnerável,

213
00:10:17,270 --> 00:10:21,580
o engraçado é que Bash,
que prompt de comando pouco simples,

214
00:10:21,580 --> 00:10:27,450
é onipresente e muitas vezes é
Usado para executar essencialmente

215
00:10:27,450 --> 00:10:30,020
o conteúdo de um
mensagem que recebe.

216
00:10:30,020 --> 00:10:33,490
E por essa lógica, você pode
enganar um servidor web, por isso,

217
00:10:33,490 --> 00:10:36,370
enviando algo parecido
User-Agent, que geralmente

218
00:10:36,370 --> 00:10:38,300
é suposto dizer o
Nome do seu browser.

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

220
00:10:42,420 --> 00:10:44,590
é apenas seu navegador de
maneira de identificar-se.

221
00:10:44,590 --> 00:10:46,605
Mas se um cara mau muito
inteligentemente diz: mm-mm, eu sou

222
00:10:46,605 --> 00:10:47,930
não vou dizer a você
o meu navegador é,

223
00:10:47,930 --> 00:10:50,888
Estou em vez de ir para enviar-lhe esta
coisa enigmática-olhando com uma -rf rm

224
00:10:50,888 --> 00:10:55,840
* Nele, você pode literalmente enganar um
servidor web vulnerável na internet

225
00:10:55,840 --> 00:10:59,055
para executar exatamente o que, em
lá para apagar todos os arquivos.

226
00:10:59,055 --> 00:11:00,930
E, francamente, isso não é
até mesmo o pior de tudo.

227
00:11:00,930 --> 00:11:01,763
Você pode fazer qualquer coisa.

228
00:11:01,763 --> 00:11:04,480
Você poderia começar a distribuição
ataque de negação de serviço

229
00:11:04,480 --> 00:11:07,030
se você enviou esta mensagem a
cachos inteiros de servidores web

230
00:11:07,030 --> 00:11:10,256
e depois tinha todos eles descem, para
exemplo, em servidores Harvard.edu,

231
00:11:10,256 --> 00:11:12,130
e você pode classificar de Bang
o inferno fora deles

232
00:11:12,130 --> 00:11:15,490
por um tráfego de rede que foi
caso contrário, desencadeada por um cara ruim.

233
00:11:15,490 --> 00:11:18,760
>> Então, longa história curta, quase
todos nesta sala que possui um Mac

234
00:11:18,760 --> 00:11:20,240
é vulnerável a isso.

235
00:11:20,240 --> 00:11:24,100
O consolo é que, a menos que você é
executando um servidor web em seu laptop,

236
00:11:24,100 --> 00:11:27,780
e, a menos que você realmente configurado
para permitir que algo como SSH para ele,

237
00:11:27,780 --> 00:11:28,670
você está realmente seguro.

238
00:11:28,670 --> 00:11:31,710
É vulnerável, mas não é
um tentando entrar em seu laptop,

239
00:11:31,710 --> 00:11:33,290
assim você pode classificar de ter a certeza.

240
00:11:33,290 --> 00:11:36,210
No entanto, a Apple em breve
estar atualizando uma correção para isso.

241
00:11:36,210 --> 00:11:39,660
O mundo do Linux já lançou
uma série de correções para o Fedora e Ubuntu

242
00:11:39,660 --> 00:11:43,790
e outras versões do Linux, e de fato
se você executar update 50 no aparelho,

243
00:11:43,790 --> 00:11:45,930
mesmo que também será
atualizados e corrigidos.

244
00:11:45,930 --> 00:11:47,764
Mas isso também não tem
sido realmente vulnerável,

245
00:11:47,764 --> 00:11:49,804
porque a menos que você tem
consertou com o aparelho

246
00:11:49,804 --> 00:11:52,770
e fez o seu laptop publicamente
acessível na internet, o que não é

247
00:11:52,770 --> 00:11:54,910
Por padrão, você tem
na verdade, foi bom porque

248
00:11:54,910 --> 00:11:56,890
de firewall e outras técnicas.

249
00:11:56,890 --> 00:12:01,000
>> Mas é um exemplo extremo de um bug
que vivemos para, literalmente, para 20

250
00:12:01,000 --> 00:12:04,050
anos, e quem sabe se alguém
todo este tempo soube sobre isso?

251
00:12:04,050 --> 00:12:06,300
E, de fato, este é um dos
os desafios fundamentais

252
00:12:06,300 --> 00:12:08,690
que vamos ver mais tarde na
semestre com a segurança,

253
00:12:08,690 --> 00:12:13,020
é que, assim como no mundo real,
os mocinhos estão em desvantagem.

254
00:12:13,020 --> 00:12:16,500
Para manter os bandidos fora, temos que
certifique-se de que cada porta está trancada,

255
00:12:16,500 --> 00:12:20,340
que cada janela é segura, que
todos os pontos de entrada em uma casa

256
00:12:20,340 --> 00:12:21,980
é seguro para manter os bandidos fora.

257
00:12:21,980 --> 00:12:26,870
Mas o que o vilão tem que
fazer para realmente comprometer a sua casa

258
00:12:26,870 --> 00:12:28,200
e roubá-lo?

259
00:12:28,200 --> 00:12:32,574
Ele ou ela só tem que encontrar um desbloqueado
porta, uma janela quebrada, ou algo

260
00:12:32,574 --> 00:12:35,240
nesse sentido, e é o
mesma coisa em segurança de computadores.

261
00:12:35,240 --> 00:12:37,660
Podemos escrever milhões de
linhas de código de programação

262
00:12:37,660 --> 00:12:40,570
e gastar centenas ou milhares
de horas a tentar obtê-lo correto,

263
00:12:40,570 --> 00:12:43,370
mas se você fizer apenas uma
erro na correção,

264
00:12:43,370 --> 00:12:47,030
você pode colocar todo o sistema e
na verdade, neste caso, toda a Internet

265
00:12:47,030 --> 00:12:48,660
e do mundo em risco.

266
00:12:48,660 --> 00:12:51,950
>> Então, se você quiser saber mais
sobre isso, vá para esta URL aqui.

267
00:12:51,950 --> 00:12:54,450
Não há necessidade de uma ação
hoje à noite, a menos que você é

268
00:12:54,450 --> 00:12:57,116
entre aqueles que mais confortável
foram executando o seu próprio web

269
00:12:57,116 --> 00:12:59,810
servidor, no caso de você deve, que,
Na verdade, atualizar seu software.

270
00:12:59,810 --> 00:13:03,244
>> E este também é o título de
um discurso e, agora, um papel,

271
00:13:03,244 --> 00:13:05,410
que temos ligado na
site do curso para hoje.

272
00:13:05,410 --> 00:13:07,600
Foi por um colega
chamado Ken Thompson, que

273
00:13:07,600 --> 00:13:10,120
estava aceitando um famoso
prêmio em ciência da computação,

274
00:13:10,120 --> 00:13:13,495
e ele deu a este discurso de alguns anos
há, essencialmente, sobre o mesmo tema.

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

276
00:13:18,250 --> 00:13:20,520
Perguntar pessoas a pergunta,
Se você realmente

277
00:13:20,520 --> 00:13:23,480
confiança, em última análise, o
software que lhe foi dado?

278
00:13:23,480 --> 00:13:26,100
Por exemplo, todos nós temos
escrevendo programas,

279
00:13:26,100 --> 00:13:27,820
e estamos compilando
los com Tinido.

280
00:13:27,820 --> 00:13:31,830
E para o seu conhecimento, você escreveu
qualquer programa de CS50 onde há

281
00:13:31,830 --> 00:13:35,310
uma porta traseira do tipo, há uma maneira
que um cara mau, se executar o programa,

282
00:13:35,310 --> 00:13:37,410
poderia assumir o seu computador?

283
00:13:37,410 --> 00:13:38,310
Provavelmente não, certo?

284
00:13:38,310 --> 00:13:40,180
Mario e Greedy e Crédito.

285
00:13:40,180 --> 00:13:41,680
Estes são todos muito pequenos programas.

286
00:13:41,680 --> 00:13:43,910
Você teria que ser muito
ruim se você realmente

287
00:13:43,910 --> 00:13:47,310
fez todo o seu computador vulnerável
depois de escrever 10 ou 20 linhas de código,

288
00:13:47,310 --> 00:13:49,690
ou, pelo menos, alguns desconhecem
das implicações de segurança.

289
00:13:49,690 --> 00:13:52,023
Agora eu digo isso de brincadeira,
mas vamos ver hoje

290
00:13:52,023 --> 00:13:54,600
e esta semana é realmente
muito, muito fácil

291
00:13:54,600 --> 00:13:57,980
ser mau e fazer ainda
programas curtos vulneráveis.

292
00:13:57,980 --> 00:14:02,880
>> Mas, por enquanto, pelo menos, perceber
que a questão que se coloca aqui

293
00:14:02,880 --> 00:14:04,850
é sobre Clang em um compilador.

294
00:14:04,850 --> 00:14:08,360
Por que temos sido confiando Clang
nos últimos dois ou três semanas?

295
00:14:08,360 --> 00:14:12,650
Quem vai dizer que quem escreveu Clang
não tinha um "se" condição lá

296
00:14:12,650 --> 00:14:17,680
que, essencialmente, injetado alguns zeros
e aqueles em cada programa que compila

297
00:14:17,680 --> 00:14:21,180
que permitiria a ele ou ela o acesso
seu computador quando você está dormindo

298
00:14:21,180 --> 00:14:23,580
e sua tampa do laptop é aberto
e seu computador está funcionando?

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

300
00:14:24,080 --> 00:14:28,350
Temos este tipo de direito sistema de honra
agora onde nós confio que Clang é legal.

301
00:14:28,350 --> 00:14:30,000
Você confia que o aparelho é legal.

302
00:14:30,000 --> 00:14:34,430
Você confia em que, literalmente, todos os programas
no seu Mac ou PC é confiável.

303
00:14:34,430 --> 00:14:37,510
E como este bug simples sugere,
mesmo se ele não é malicioso,

304
00:14:37,510 --> 00:14:40,580
isso não é absolutamente
susceptível de ser o caso.

305
00:14:40,580 --> 00:14:42,350
>> Então você deve estar assustada como o inferno.

306
00:14:42,350 --> 00:14:45,560
Francamente, não há simples
solução a esta outra

307
00:14:45,560 --> 00:14:48,185
do que um tipo de consciência social
da crescente complexidade

308
00:14:48,185 --> 00:14:50,310
que estamos construindo em cima
de nossos sistemas de computador,

309
00:14:50,310 --> 00:14:53,740
e como cada vez mais vulneráveis
que poderia muito bem ser.

310
00:14:53,740 --> 00:14:55,570
>> Agora, com o que disse, Breakout.

311
00:14:55,570 --> 00:14:59,889
Então Breakout é problema definir três, e
Breakout é um jogo de antigamente

312
00:14:59,889 --> 00:15:02,180
que você deve se lembrar, mas
para nós no conjunto de problemas de três,

313
00:15:02,180 --> 00:15:04,450
que nos permite tomar
as coisas de volta até um entalhe

314
00:15:04,450 --> 00:15:08,880
para que, quando estamos a escrever programas,
mesmo em uma janela de terminal como este,

315
00:15:08,880 --> 00:15:14,670
podemos realmente executado, em última análise,
programas gráficos não

316
00:15:14,670 --> 00:15:17,800
ao contrário daqueles que tivemos
acesso a em risco.

317
00:15:17,800 --> 00:15:20,910
Portanto, este é o pessoal do
implementação de Breakout,

318
00:15:20,910 --> 00:15:23,930
que é apenas isso de quebra de tijolos
jogo, que você mover sua raquete para trás

319
00:15:23,930 --> 00:15:27,590
e para trás, e você bater na bola
contra os tijolos coloridos em cima.

320
00:15:27,590 --> 00:15:30,020
Então, isso está nos trazendo
espécie de volta para onde

321
00:15:30,020 --> 00:15:33,180
, foram capazes de ser muito rapidamente
com o Scratch, e agora com C,

322
00:15:33,180 --> 00:15:35,800
implementação da nossa própria
interfaces gráficas de usuário.

323
00:15:35,800 --> 00:15:38,960
>> Mas mais do que isso, este
conjunto representa o primeiro problema

324
00:15:38,960 --> 00:15:41,000
em que nós estamos dando
você um monte de código.

325
00:15:41,000 --> 00:15:43,940
E, na verdade, eu trago explícita
atenção para isso, porque especialmente

326
00:15:43,940 --> 00:15:47,090
para aqueles menos confortável, este
conjunto de problemas, pelo menos à primeira vista,

327
00:15:47,090 --> 00:15:49,170
vai sentir como
demos-se um entalhe.

328
00:15:49,170 --> 00:15:51,540
Porque nós te dei,
para algumas das buscas

329
00:15:51,540 --> 00:15:54,930
e classificar os problemas no pset,
um monte de código que escreveu,

330
00:15:54,930 --> 00:15:56,680
e um par de comentários
que dizem "fazer",

331
00:15:56,680 --> 00:15:58,221
onde você tem que preencher os espaços em branco.

332
00:15:58,221 --> 00:16:00,020
Então, não muito assustador, mas
é a primeira vez

333
00:16:00,020 --> 00:16:03,370
estamos entregando-lhe um código que você precisa
primeiro ler, entender, e em seguida, adicione a

334
00:16:03,370 --> 00:16:04,290
e concluí-lo.

335
00:16:04,290 --> 00:16:05,940
>> E então, com Breakout,
vamos fazer o mesmo,

336
00:16:05,940 --> 00:16:08,740
dando-lhe uma dúzia de mais linhas
de código que, francamente, dar-lhe

337
00:16:08,740 --> 00:16:11,490
uma grande parte do quadro de
o jogo mas param

338
00:16:11,490 --> 00:16:14,304
de implementar os tijolos
e a bola e na raquete,

339
00:16:14,304 --> 00:16:15,970
mas fazemos implementar algumas outras características.

340
00:16:15,970 --> 00:16:18,280
E, mesmo que à primeira vista, mais uma vez,
especialmente se menos confortável,

341
00:16:18,280 --> 00:16:21,480
Pode parecer particularmente difícil e
Você acha que há tantas novas funções

342
00:16:21,480 --> 00:16:24,070
você precisa envolver sua mente
ao redor, e isso é verdade.

343
00:16:24,070 --> 00:16:26,281
Mas lembre-se, é
bem como do risco.

344
00:16:26,281 --> 00:16:28,780
As probabilidades são que você não usar todos
as peças do puzzle em zero.

345
00:16:28,780 --> 00:16:31,120
As probabilidades são que você não se importava para embrulhar
sua mente em torno de todos eles

346
00:16:31,120 --> 00:16:33,617
porque tudo o que tinha era uma
rápida olhada para compreender, oh,

347
00:16:33,617 --> 00:16:35,450
isso é o que eu posso fazer
com essa peça do puzzle.

348
00:16:35,450 --> 00:16:38,260
E, de fato, no conjunto de problemas
3 spec, vamos apontá-lo

349
00:16:38,260 --> 00:16:41,370
na documentação que será
apresentá-lo a novas funções,

350
00:16:41,370 --> 00:16:43,570
e, finalmente, a programação
constrói você usa.

351
00:16:43,570 --> 00:16:47,610
Condições, laços,
variáveis ​​e funções

352
00:16:47,610 --> 00:16:50,720
será idêntico ao
o que temos visto até agora.

353
00:16:50,720 --> 00:16:53,560
>> Então, na verdade, o que nós vamos dar
você é um código de exemplo que

354
00:16:53,560 --> 00:16:56,110
permite criar uma janela
que não parece, ao contrário disso,

355
00:16:56,110 --> 00:16:59,540
e, finalmente, transformá-lo em
algo parecido com isso.

356
00:16:59,540 --> 00:17:02,250
Então, aproveite CS50,
discutir o horário de expediente e mais,

357
00:17:02,250 --> 00:17:05,290
e se consolar com o fato de que
a quantidade de código que você tem que escrever

358
00:17:05,290 --> 00:17:06,760
na verdade não é tanto assim.

359
00:17:06,760 --> 00:17:10,359
O primeiro desafio é apenas para se aclimatar
-se de algum código que você escreveu.

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

361
00:17:11,450 --> 00:17:15,810
>> Qualquer dúvida sobre pset3,
Shellshock, ou de outra forma?

362
00:17:15,810 --> 00:17:19,226
>> AUDIÊNCIA: Parecia que
passando com Breakout

363
00:17:19,226 --> 00:17:22,154
que o código é quase
um estilo orientado a objetos,

364
00:17:22,154 --> 00:17:24,675
mas eu pensei que era um C
programa orientado a objeto.

365
00:17:24,675 --> 00:17:26,050
COLUNA 1: Uma excelente pergunta.

366
00:17:26,050 --> 00:17:28,258
Assim, em olhando através da
código de distribuição, o código

367
00:17:28,258 --> 00:17:30,180
nós escrevemos para pset3,
para os que estão familiarizados, ele

368
00:17:30,180 --> 00:17:32,230
Parece que é um
pouco orientada a objetos.

369
00:17:32,230 --> 00:17:33,800
A resposta curta é, é.

370
00:17:33,800 --> 00:17:38,130
É uma aproximação de como você
pode fazer código orientado a objetos usando

371
00:17:38,130 --> 00:17:41,850
uma linguagem como C, mas é
ainda, em última análise processual.

372
00:17:41,850 --> 00:17:44,900
Não existem métodos dentro de
as variáveis, como você vai ver.

373
00:17:44,900 --> 00:17:46,180
Mas ele lembra-se disso.

374
00:17:46,180 --> 00:17:48,780
E nós vamos ver esse recurso novamente
quando chegarmos ao PHP e JavaScript

375
00:17:48,780 --> 00:17:49,946
até o final do semestre.

376
00:17:49,946 --> 00:17:53,667
Mas, por agora, pense nisso como
uma dica do que está por vir.

377
00:17:53,667 --> 00:17:54,250
Boa pergunta.

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

379
00:17:56,051 --> 00:17:56,550
Tudo certo.

380
00:17:56,550 --> 00:17:59,730
Então, merge sort era como nós
coisas deixadas pela última vez.

381
00:17:59,730 --> 00:18:03,250
E merge sort foi legal no
sentido de que era muito mais rápido,

382
00:18:03,250 --> 00:18:07,100
, pelo menos, com base nos ensaios superficiais
fizemos na semana passada, que, digamos, bolha

383
00:18:07,100 --> 00:18:08,710
tipo, a seleção de classificação, ordenação por inserção.

384
00:18:08,710 --> 00:18:11,780
E o que era limpo também é apenas
como forma sucinta e limpa

385
00:18:11,780 --> 00:18:12,810
você pode expressá-la.

386
00:18:12,810 --> 00:18:15,840
E o que podemos dizer que foi um superior
obrigados, sob o tempo de execução da fusão

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

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

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

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

391
00:18:19,360 --> 00:18:20,819
>> COLUNA 1: n log n, certo. n log n.

392
00:18:20,819 --> 00:18:23,776
E nós vamos voltar para o que isso
realmente significa ou de onde vem isso,

393
00:18:23,776 --> 00:18:25,570
mas este foi melhor
do que o tempo de execução

394
00:18:25,570 --> 00:18:28,440
que vimos para bolha
seleção e inserção tipo?

395
00:18:28,440 --> 00:18:30,610
Então n ao quadrado. n ao quadrado
é maior do que isso,

396
00:18:30,610 --> 00:18:34,650
e mesmo se não é óbvio,
sei que log n é menor do que n,

397
00:18:34,650 --> 00:18:36,910
por isso, se você fizer n vezes
algo menor do que n,

398
00:18:36,910 --> 00:18:38,680
vai ser menor do que n ao quadrado.

399
00:18:38,680 --> 00:18:40,130
É um pouco de intuição lá.

400
00:18:40,130 --> 00:18:42,190
Mas pagamos um preço por isso.

401
00:18:42,190 --> 00:18:47,000
Ele foi mais rápido, mas um tema que começou
a surgir na semana passada foi essa compensação.

402
00:18:47,000 --> 00:18:49,804
Eu tenho um melhor desempenho
tempo sábio, mas o que

403
00:18:49,804 --> 00:18:52,470
que eu tenho que passar por outro
lado, a fim de conseguir isso?

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

405
00:18:53,591 --> 00:18:54,465
COLUNA 1: Diga de novo?

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

407
00:18:55,173 --> 00:18:57,040
COLUNA 1: Memória, ou
espaço de forma mais geral.

408
00:18:57,040 --> 00:18:59,040
E não foi super
óbvia com os seres humanos,

409
00:18:59,040 --> 00:19:02,240
mas lembrar que nossos voluntários
foram avançando e pisando

410
00:19:02,240 --> 00:19:04,780
de volta como se houvesse uma matriz
aqui, e como se houvesse

411
00:19:04,780 --> 00:19:07,130
um segundo conjunto que aqui
eles poderiam usar, porque nós

412
00:19:07,130 --> 00:19:09,080
um lugar necessário para mesclar essas pessoas.

413
00:19:09,080 --> 00:19:11,480
Nós não poderíamos simplesmente trocá-los no lugar.

414
00:19:11,480 --> 00:19:13,800
Então, merge sort alavancagem
há mais espaço, que

415
00:19:13,800 --> 00:19:15,620
nós não precisamos de
os outros algoritmos,

416
00:19:15,620 --> 00:19:17,410
mas a vantagem é que é muito mais rápido.

417
00:19:17,410 --> 00:19:20,780
E, francamente, no espaço do mundo real
estes RAM dias--, disco rígido espaço--

418
00:19:20,780 --> 00:19:25,030
é relativamente barato, e por isso é
não necessariamente uma coisa ruim.

419
00:19:25,030 --> 00:19:28,320
>> Então, vamos dar uma olhada rápida, um pouco
mais metodicamente, pelo o que fizemos

420
00:19:28,320 --> 00:19:30,220
e por isso que disse que estava n log n.

421
00:19:30,220 --> 00:19:33,260
Então aqui estão os oito números ea
oito voluntários que tivemos da última vez.

422
00:19:33,260 --> 00:19:35,718
E a primeira coisa que se fundem
Ordenar nos disse para fazer o que era?

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

424
00:19:37,010 --> 00:19:38,010
AUDIÊNCIA: Divide em dois.

425
00:19:38,010 --> 00:19:38,663
COLUNA 1: Diga de novo?

426
00:19:38,663 --> 00:19:39,650
AUDIÊNCIA: Divide em dois.

427
00:19:39,650 --> 00:19:40,610
COLUNA 1: Divida em dois, certo.

428
00:19:40,610 --> 00:19:42,818
Isso lembra muito
o livro de telefone, de dividir

429
00:19:42,818 --> 00:19:44,220
e conquistar mais geral.

430
00:19:44,220 --> 00:19:45,640
Então, olhamos para o lado esquerdo.

431
00:19:45,640 --> 00:19:48,700
E, em seguida, uma vez dissemos, tipo
a metade da esquerda dos elementos,

432
00:19:48,700 --> 00:19:49,690
o que nós fizemos próxima dizer?

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

434
00:19:51,210 --> 00:19:54,860
Ordena a metade esquerda da esquerda
metade, o que nos permitiu,

435
00:19:54,860 --> 00:19:57,570
depois de dividir em dois,
concentrar em quatro e dois.

436
00:19:57,570 --> 00:20:01,280
>> Como você classificar uma lista agora, em
amarelo, de tamanho dois, usando Merge Sort?

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

438
00:20:02,330 --> 00:20:04,580
Bem dividi-lo ao meio,
e classificar a metade esquerda.

439
00:20:04,580 --> 00:20:07,100
E este era o lugar onde as coisas
ficou um pouco brevemente estúpido.

440
00:20:07,100 --> 00:20:10,720
Como você classificar uma lista que é de
tamanho um, como este número quatro aqui?

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

442
00:20:12,330 --> 00:20:13,210
É classificada.

443
00:20:13,210 --> 00:20:14,200
Você está feito.

444
00:20:14,200 --> 00:20:17,300
>> Mas então como você classificar uma lista de
um tamanho quando é o número dois?

445
00:20:17,300 --> 00:20:21,640
Bem, a mesma coisa, mas agora o que era o
terceiro eo passo fundamental na Merge Sort?

446
00:20:21,640 --> 00:20:24,020
Você tinha que se fundem à esquerda
metade e metade direita.

447
00:20:24,020 --> 00:20:26,580
E uma vez que fizemos isso, nós olhamos
em quatro, nós olhamos para dois.

448
00:20:26,580 --> 00:20:28,750
Decidimos tudo bem,
obviamente dois vem em primeiro lugar,

449
00:20:28,750 --> 00:20:31,840
então colocamos dois em sua
lugar, seguido por quatro.

450
00:20:31,840 --> 00:20:35,010
E agora você tem que tipo de retrocesso,
e isso é uma espécie de característica

451
00:20:35,010 --> 00:20:37,570
de um algoritmo como Mesclar
Ordenar, retroceder na memória.

452
00:20:37,570 --> 00:20:40,240
Qual foi a linha seguinte da história?

453
00:20:40,240 --> 00:20:41,780
O que eu deveria estar centrada na próxima?

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

455
00:20:43,110 --> 00:20:47,350
A metade direita da esquerda
metade, que é de seis e oito anos.

456
00:20:47,350 --> 00:20:50,320
>> Então deixe-me passar por este
sem belaboring o ponto muito.

457
00:20:50,320 --> 00:20:53,330
Seis e oito, em seguida, seis são
classificadas, oito são classificados.

458
00:20:53,330 --> 00:20:57,190
Fundi-las assim,
e agora o próximo grande passo

459
00:20:57,190 --> 00:21:00,990
É, claro, ordenar a metade direita da
o primeiro passo deste algoritmo.

460
00:21:00,990 --> 00:21:02,870
Então, nos concentramos em um, três, sete, cinco.

461
00:21:02,870 --> 00:21:04,540
Nós, então, concentrar-se na metade esquerda.

462
00:21:04,540 --> 00:21:09,400
A metade esquerda do que a metade direita
que, em seguida, fundir em um e três.

463
00:21:09,400 --> 00:21:13,100
Em seguida, a metade direita, depois à esquerda metade
do mesmo, em seguida, a metade direita do mesmo.

464
00:21:13,100 --> 00:21:15,985
Mesclar-lo, e agora o que passo permanece?

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

466
00:21:18,040 --> 00:21:22,460
Mesclar o grande meia esquerda eo grande
metade direita, de modo que um vai lá em baixo,

467
00:21:22,460 --> 00:21:27,330
depois dois, depois três, depois quatro, depois
cinco, depois seis, depois sete, depois oito.

468
00:21:27,330 --> 00:21:31,990
>> Então agora porque é que isto acaba por revelar,
especialmente se n mais e logaritmos

469
00:21:31,990 --> 00:21:35,487
geralmente bastante escapar de você,
pelo menos na memória recente?

470
00:21:35,487 --> 00:21:37,070
Bem, observe a altura dessa coisa.

471
00:21:37,070 --> 00:21:41,230
Tivemos oito elementos, e nós
dividido por dois, por dois, por dois.

472
00:21:41,230 --> 00:21:44,590
Então log base dois dos oito nos dá três.

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

474
00:21:45,640 --> 00:21:48,540
E confiar em mim que, se
um pouco vago sobre isso.

475
00:21:48,540 --> 00:21:54,710
Mas log base dois dos oito é três,
assim fizemos três camadas de fusão.

476
00:21:54,710 --> 00:21:57,170
E quando se fundiu
elementos, quantos elementos

477
00:21:57,170 --> 00:21:58,950
se olharmos para a cada uma dessas linhas?

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

479
00:22:00,212 --> 00:22:01,437
Um total de n, certo?

480
00:22:01,437 --> 00:22:04,020
Porque se fundir a linha superior,
mesmo que nós fizemos isso aos poucos,

481
00:22:04,020 --> 00:22:05,990
que em última análise, tocou em cada número uma vez.

482
00:22:05,990 --> 00:22:09,054
E na segunda linha, a
mesclar essas listas de tamanho dois,

483
00:22:09,054 --> 00:22:10,470
tivemos que tocar cada elemento uma vez.

484
00:22:10,470 --> 00:22:12,690
E então aqui realmente
claramente na última fila,

485
00:22:12,690 --> 00:22:15,430
tivemos que tocar cada um desses
elementos uma vez, mas apenas uma vez,

486
00:22:15,430 --> 00:22:18,400
então aqui está, então, a nossa log n n.

487
00:22:18,400 --> 00:22:21,780
>> E agora só para tornar as coisas um pouco
mais formal só por um momento, se você

488
00:22:21,780 --> 00:22:24,260
eram agora analisar esta
a uma espécie de nível mais elevado

489
00:22:24,260 --> 00:22:28,340
e tentar decidir, bem como
pode você ir sobre expressando

490
00:22:28,340 --> 00:22:31,780
o tempo de execução deste algoritmo
só de olhar para ele e não

491
00:22:31,780 --> 00:22:33,590
usando um exemplo inventado?

492
00:22:33,590 --> 00:22:36,590
Bem, quanto tempo você diria que um
passo como este em amarelo levaria,

493
00:22:36,590 --> 00:22:37,173
Se n <2 retorno?

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

495
00:22:38,840 --> 00:22:39,830
Isso é um grande O de quê?

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

497
00:22:41,450 --> 00:22:44,540
Então, eu estou vendo um, por isso uma única etapa,
talvez duas etapas porque é se

498
00:22:44,540 --> 00:22:47,110
e depois voltar, mas é
constante de tempo, certo?

499
00:22:47,110 --> 00:22:49,960
Então nós dissemos O (1), e que é
como vou expressar isso.

500
00:22:49,960 --> 00:22:51,480
T, basta ter tempo de execução.

501
00:22:51,480 --> 00:22:54,150
n é o tamanho da entrada,
então T (n), apenas uma maneira elegante

502
00:22:54,150 --> 00:22:56,330
de dizer que o funcionamento
dado tempo de entrada de tamanho n

503
00:22:56,330 --> 00:23:00,220
vai ser na ordem
constante de tempo, em O (1).

504
00:23:00,220 --> 00:23:01,970
>> Mas por outro lado, o que sobre isso?

505
00:23:01,970 --> 00:23:05,660
Como você se expressar a
tempo desta linha amarela que funcionam?

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

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

508
00:23:09,440 --> 00:23:12,665
Você pode tipo de fraude aqui e
responder a minha pergunta ciclicamente.

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

510
00:23:14,770 --> 00:23:17,900
Assim, se o tempo de funcionamento em
geral que acabamos de dizer é T (n).

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

512
00:23:18,950 --> 00:23:22,490
E agora você está tipo de punt aqui e
dizendo, bem, apenas ordenar a metade esquerda,

513
00:23:22,490 --> 00:23:23,920
e, em seguida, classificar a metade direita.

514
00:23:23,920 --> 00:23:27,520
Como podemos representar simbolicamente
o tempo de execução desta linha amarela?

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

516
00:23:28,020 --> 00:23:29,360
Qual é o tamanho da entrada?

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

518
00:23:30,510 --> 00:23:31,057
n mais de dois.

519
00:23:31,057 --> 00:23:32,140
Por que eu não disse isso?

520
00:23:32,140 --> 00:23:36,449
E, em seguida, esta é outra T (n / 2) e, em seguida,
novamente, se eu fundir duas metades ordenadas,

521
00:23:36,449 --> 00:23:38,615
quantos elementos é que eu vou
ter que tocar todo?

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
Para que eu possa expressar isto,
apenas para ser uma espécie de fantasia,

525
00:23:42,790 --> 00:23:44,430
como o tempo de funcionamento em geral.

526
00:23:44,430 --> 00:23:51,140
T (n) é apenas o tempo de execução T (n / 2),
além de T (n / 2), deixou metade e metade direita,

527
00:23:51,140 --> 00:23:55,360
além S (n), que é, provavelmente, n passos,
mas talvez, se eu estou usando dois dedos,

528
00:23:55,360 --> 00:23:57,960
é o dobro
passos, mas é linear.

529
00:23:57,960 --> 00:24:00,440
É uma série de passos
isso é um fator de n,

530
00:24:00,440 --> 00:24:02,270
assim podemos expressar isso como este.

531
00:24:02,270 --> 00:24:05,550
E é aí que agora vamos chutar para o
de trás do nosso livro de matemática do ensino médio

532
00:24:05,550 --> 00:24:10,290
estamos em última análise, que a recorrência
termina-se igual a este, n vezes log n,

533
00:24:10,290 --> 00:24:12,530
se você realmente fazer a
a matemática mais formal.

534
00:24:12,530 --> 00:24:13,950
>> Então, isso é apenas duas perspectivas.

535
00:24:13,950 --> 00:24:17,500
Uma numericamente com um
codificado exemplo representativo

536
00:24:17,500 --> 00:24:21,140
usando oito números e um mais
olhada geral como chegamos lá.

537
00:24:21,140 --> 00:24:25,670
Mas o que é realmente interessante aqui
é, mais uma vez, essa noção de ciclismo.

538
00:24:25,670 --> 00:24:26,900
Eu não estou usando para loops.

539
00:24:26,900 --> 00:24:29,860
Eu sou o tipo de definição
algo em termos de si mesmo,

540
00:24:29,860 --> 00:24:31,950
Não só com a presente
função matemática,

541
00:24:31,950 --> 00:24:34,860
mas também em termos de este código pseudo.

542
00:24:34,860 --> 00:24:38,260
Este código pseudo é recursiva
em que duas das suas linhas

543
00:24:38,260 --> 00:24:42,310
é, essencialmente, dizendo-lhe para ir
utilizar-se para resolver um menor

544
00:24:42,310 --> 00:24:45,400
problema de menor tamanho,
e, em seguida, uma e outra vez

545
00:24:45,400 --> 00:24:48,820
e de novo até que ele talhar
até este chamado caso base.

546
00:24:48,820 --> 00:24:52,810
>> Então, vamos realmente tirar um mais atraente
take-away de isso da seguinte forma.

547
00:24:52,810 --> 00:24:58,420
Deixe-me ir em gedit e dar uma
olhar para alguns dos código-fonte de hoje,

548
00:24:58,420 --> 00:24:59,930
em particular, este exemplo aqui.

549
00:24:59,930 --> 00:25:03,709
Sigma 0, que, aparentemente aumenta
os números de um a n.

550
00:25:03,709 --> 00:25:05,750
Então vamos ver o que é familiar
e desconhecido aqui.

551
00:25:05,750 --> 00:25:08,690
Primeiro, temos um par de
inclui, portanto, nada de novo nisso.

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

553
00:25:09,190 --> 00:25:11,370
Eu sou um pouco vago sobre
isso depois de alguns dias,

554
00:25:11,370 --> 00:25:13,790
mas o que dizemos um
protótipo de uma função é?

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

556
00:25:15,099 --> 00:25:16,015
AUDIÊNCIA: [inaudível].

557
00:25:16,015 --> 00:25:16,905
COLUNA 1: O que é isso?

558
00:25:16,905 --> 00:25:17,800
AUDIÊNCIA: Nós anunciá-lo.

559
00:25:17,800 --> 00:25:18,883
COLUNA 1: Nós anunciá-lo.

560
00:25:18,883 --> 00:25:22,290
Então, você está ensinando Clang, hey,
não realmente implementar isso ainda,

561
00:25:22,290 --> 00:25:25,740
mas em algum lugar neste arquivo, presumivelmente,
vai ser uma função chamada quê?

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

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

564
00:25:27,540 --> 00:25:30,540
E esta é apenas uma promessa de que
ele vai olhar como este.

565
00:25:30,540 --> 00:25:33,720
Vai demorar um inteiro como
input-- e eu posso ser mais explícito

566
00:25:33,720 --> 00:25:36,570
e dizer int n --e é
vai retornar um int,

567
00:25:36,570 --> 00:25:39,900
mas meio ponto e vírgula, mm, eu vou dar a volta
para implementar esta um pouco mais tarde.

568
00:25:39,900 --> 00:25:40,989
Mais uma vez, Clang é burro.

569
00:25:40,989 --> 00:25:43,280
Ele só vai saber o que
você diga a ele de cima para baixo,

570
00:25:43,280 --> 00:25:45,765
por isso precisamos de pelo menos dar
uma dica do que está por vir.

571
00:25:45,765 --> 00:25:47,330
>> Agora vamos olhar para o principal aqui.

572
00:25:47,330 --> 00:25:50,040
Vamos rolar para baixo aqui e
ver o principal está fazendo.

573
00:25:50,040 --> 00:25:53,780
Não é que a longo de uma função, e
na verdade, a construção aqui é familiar.

574
00:25:53,780 --> 00:25:57,590
Eu declaro uma variável n, e depois
Eu importunar o usuário novo e de novo

575
00:25:57,590 --> 00:26:01,880
para um número inteiro positivo utilizando getInt,
e só sair fora deste circuito

576
00:26:01,880 --> 00:26:03,280
uma vez que o usuário tenha cumprido.

577
00:26:03,280 --> 00:26:05,670
Do While, que usamos para
importunar o usuário dessa maneira.

578
00:26:05,670 --> 00:26:06,670
Agora isto é interessante.

579
00:26:06,670 --> 00:26:08,510
Declaro um int chamado de "resposta".

580
00:26:08,510 --> 00:26:11,420
Eu atribuí-lo o valor de retorno
de uma função chamada "sigma".

581
00:26:11,420 --> 00:26:15,200
Eu não sei o que isso faz ainda, mas
Lembro-me de declarar que um momento atrás.

582
00:26:15,200 --> 00:26:18,310
E então eu estou passando no
valor que o usuário digitou, n,

583
00:26:18,310 --> 00:26:20,420
e então eu relatar a resposta.

584
00:26:20,420 --> 00:26:22,260
Bem, vamos rolar para trás
por apenas um momento.

585
00:26:22,260 --> 00:26:28,620
Vamos em frente neste diretório, fazer
sigma 0, e realmente executar este programa

586
00:26:28,620 --> 00:26:30,490
e ver o que acontece.

587
00:26:30,490 --> 00:26:35,930
Então, se eu ir em frente e correr
Neste programa, ./sigma-0,

588
00:26:35,930 --> 00:26:40,139
e eu digitar um positivo
inteiro como dois, Sigma,

589
00:26:40,139 --> 00:26:43,180
como o símbolo grego indica, é apenas
vai somar todos os números de

590
00:26:43,180 --> 00:26:44,320
zerar em até dois.

591
00:26:44,320 --> 00:26:46,560
Assim 0 mais 1 mais 2.

592
00:26:46,560 --> 00:26:48,830
Portanto, este deve espero dar-me 3.

593
00:26:48,830 --> 00:26:49,750
Isso é tudo o que está fazendo.

594
00:26:49,750 --> 00:26:52,690
E da mesma forma, se eu executar isto novamente
e eu dar-lhe o número de três,

595
00:26:52,690 --> 00:26:56,721
isso é 3 + 2, de modo que é
5, mais 1 deveria me dar 6.

596
00:26:56,721 --> 00:26:59,470
E então se eu ficar muito louco e
começar a digitar em números maiores,

597
00:26:59,470 --> 00:27:01,290
deve dar-me
somas cada vez maiores.

598
00:27:01,290 --> 00:27:02,250
Então, isso é tudo.

599
00:27:02,250 --> 00:27:04,010
>> Então, o que sigma parece?

600
00:27:04,010 --> 00:27:05,430
Bem, é bastante simples.

601
00:27:05,430 --> 00:27:08,940
É como poderíamos ter implementado
isso para o último par de semanas.

602
00:27:08,940 --> 00:27:11,120
"Int" vai ser o tipo de retorno.

603
00:27:11,120 --> 00:27:14,330
Sigma é o nome, e é preciso
m uma variável em vez de n.

604
00:27:14,330 --> 00:27:15,940
Eu vou mudar isso em cima.

605
00:27:15,940 --> 00:27:17,340
Então este é apenas um teste de sanidade.

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

607
00:27:18,430 --> 00:27:19,950
Vamos ver por que em um momento.

608
00:27:19,950 --> 00:27:24,220
Agora eu declarar outra variável,
suma, inicialize-o a zero.

609
00:27:24,220 --> 00:27:28,140
Então eu tenho esse loop
iteração, aparentemente, para maior clareza,

610
00:27:28,140 --> 00:27:33,810
a partir de i = 1 em cima de um m =, que é
tudo o que o usuário digitou, e então eu

611
00:27:33,810 --> 00:27:35,690
incrementar a soma assim.

612
00:27:35,690 --> 00:27:37,360
E, em seguida, retornar a soma.

613
00:27:37,360 --> 00:27:38,440
>> Assim, um par de perguntas.

614
00:27:38,440 --> 00:27:42,370
Um, eu afirmo no meu comentário que esta
evita risco de um loop infinito.

615
00:27:42,370 --> 00:27:45,620
Por que passar em um número negativo
induzir, potencialmente, um loop infinito?

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

617
00:27:49,396 --> 00:27:51,290
>> AUDIÊNCIA: Você nunca vai chegar a m.

618
00:27:51,290 --> 00:27:52,880
>> COLUNA 1: Nunca chegar m.

619
00:27:52,880 --> 00:27:55,880
Mas m é passado, então vamos
Considere um exemplo simples.

620
00:27:55,880 --> 00:27:58,510
Se m é passado pelo
usuário como um negativo.

621
00:27:58,510 --> 00:28:00,059
Independentemente do principal.

622
00:28:00,059 --> 00:28:01,850
Principal nos protege de
isso também, então eu sou apenas

623
00:28:01,850 --> 00:28:04,680
sendo muito anal com
sigma também certificar-se

624
00:28:04,680 --> 00:28:06,540
que a entrada não pode ser negativa.

625
00:28:06,540 --> 00:28:10,130
Portanto, se m for negativo,
algo como um negativo.

626
00:28:10,130 --> 00:28:11,930
O que vai acontecer?

627
00:28:11,930 --> 00:28:14,390
Bem, eu vai
se inicializado com um,

628
00:28:14,390 --> 00:28:19,060
e então eu vai ser
inferior ou igual a m?

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

630
00:28:24,130 --> 00:28:24,765
>> Estar por.

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

632
00:28:26,930 --> 00:28:29,370
Isso estava-- não vamos,
vamos nix esta história.

633
00:28:29,370 --> 00:28:32,780
Eu não pedi a essa pergunta, porque
o risco que estou aludindo

634
00:28:32,780 --> 00:28:38,360
não vai acontecer, porque eu é
sempre vai ser maior OK than--,

635
00:28:38,360 --> 00:28:39,871
Eu retiro a essa pergunta.

636
00:28:39,871 --> 00:28:40,370
Está bem.

637
00:28:40,370 --> 00:28:42,030
Vamos focar apenas esta parte aqui.

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

639
00:28:44,210 --> 00:28:48,830
Por que eu declarar algum
fora do loop?

640
00:28:48,830 --> 00:28:52,010
Aviso na linha 49 eu tenho
declarado i interior do laço,

641
00:28:52,010 --> 00:28:54,950
mas em linha 48 eu tenho
declarou alguns fora.

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

643
00:28:55,695 --> 00:28:56,611
AUDIÊNCIA: [inaudível].

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

645
00:28:58,734 --> 00:28:59,400
COLUNA 1: Claro.

646
00:28:59,400 --> 00:29:03,360
Então, em primeiro lugar, eu certamente não
quero declarar e inicializar soma

647
00:29:03,360 --> 00:29:06,130
a zero no interior da
circuito em cada iteração,

648
00:29:06,130 --> 00:29:09,370
porque isso iria derrotar claramente a
propósito de somar os números.

649
00:29:09,370 --> 00:29:11,770
Gostaria de ficar mudando
o valor de volta para zero.

650
00:29:11,770 --> 00:29:17,992
E também, o que é um outro mais arcanos
razão para essa mesma decisão design?

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

652
00:29:18,954 --> 00:29:20,279
>> AUDIÊNCIA: [inaudível].

653
00:29:20,279 --> 00:29:21,070
COLUNA 1: Exatamente.

654
00:29:21,070 --> 00:29:24,060
Eu quero acessá-lo fora
do laço também em que linha?

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

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

657
00:29:26,400 --> 00:29:29,910
E com base em nossa regra de ouro
a partir de um par de palestras atrás,

658
00:29:29,910 --> 00:29:33,680
variáveis ​​são escopo, realmente, para o
chaves que eles abrangem.

659
00:29:33,680 --> 00:29:38,190
Então, se eu não declarar soma dentro
dessas chaves externas,

660
00:29:38,190 --> 00:29:40,250
Eu não posso usá-lo na linha 53.

661
00:29:40,250 --> 00:29:43,160
Dito de outra forma, se eu declarei
soma aqui, ou até mesmo dentro do

662
00:29:43,160 --> 00:29:45,410
Para loop, eu não podia acessá-lo em 53.

663
00:29:45,410 --> 00:29:47,150
A variável que efetivamente desaparecido.

664
00:29:47,150 --> 00:29:48,579
Assim, um par de razões lá.

665
00:29:48,579 --> 00:29:50,370
Mas agora vamos voltar
e ver o que acontece.

666
00:29:50,370 --> 00:29:51,730
Então sigma é chamada.

667
00:29:51,730 --> 00:29:55,640
Acrescenta-se 1 mais 2 ou 1 mais 2
mais 3, e em seguida, retorna o valor,

668
00:29:55,640 --> 00:29:59,660
armazena em resposta, e printf aqui
É por isso que eu estou vendo na tela.

669
00:29:59,660 --> 00:30:03,079
Então é isso que nós vamos chamar uma iterativo
abordagem, onde apenas iteração

670
00:30:03,079 --> 00:30:03,870
significa usar um loop.

671
00:30:03,870 --> 00:30:06,900
Um loop, um loop While, um Do While
loop, apenas fazendo algo de novo

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

673
00:30:08,380 --> 00:30:13,505
>> Mas sigma é um tipo de função puro em
que eu poderia implementá-lo de forma diferente.

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

675
00:30:14,620 --> 00:30:19,120
E sobre isso, o que
apenas para ser bem legal,

676
00:30:19,120 --> 00:30:21,880
deixe-me realmente se livrar
de uma grande quantidade de distracção

677
00:30:21,880 --> 00:30:24,380
porque esta função
É realmente muito simples.

678
00:30:24,380 --> 00:30:27,780
Vamos talhar-lo apenas
aos seus quatro linhas centrais

679
00:30:27,780 --> 00:30:30,410
e se livrar de toda a
comentários e chaves.

680
00:30:30,410 --> 00:30:34,334
Esta é uma espécie de alucinante
execução alternativa.

681
00:30:34,334 --> 00:30:37,250
Tudo bem, talvez não alucinante,
mas é o tipo de mais sexy, tudo bem,

682
00:30:37,250 --> 00:30:39,920
de olhar para este muito mais sucinta.

683
00:30:39,920 --> 00:30:43,120
Com apenas quatro linhas de código,
A primeira vez que tenho esse teste de sanidade.

684
00:30:43,120 --> 00:30:45,732
Se m é igual ou inferior a
zero, sigma não faz sentido.

685
00:30:45,732 --> 00:30:48,190
É só deveria estar na
Neste caso, para números positivos,

686
00:30:48,190 --> 00:30:50,340
então eu só vou
retornar zero arbitrariamente

687
00:30:50,340 --> 00:30:53,210
para que, pelo menos, ter
alguns chamados caso base.

688
00:30:53,210 --> 00:30:54,430
>> Mas aqui está a beleza.

689
00:30:54,430 --> 00:30:59,930
A totalidade dessa ideia, acrescentando que o
os números entre 1 e n, ou m, neste caso,

690
00:30:59,930 --> 00:31:02,630
pode ser feito por meio de passar a bola.

691
00:31:02,630 --> 00:31:04,947
Bem, o que é a soma de 1 a m?

692
00:31:04,947 --> 00:31:05,780
Bem, você sabe o quê?

693
00:31:05,780 --> 00:31:11,949
É o mesmo que a soma de m
mais a soma de 1 para menos 1 m.

694
00:31:11,949 --> 00:31:12,740
Bem, você sabe o quê?

695
00:31:12,740 --> 00:31:13,940
O que há de sigma de m menos 1?

696
00:31:13,940 --> 00:31:17,860
Bem, se você seguir este tipo de
logicamente, é o mesmo que m menos 1

697
00:31:17,860 --> 00:31:21,415
além de sigma de m menos 2.

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

699
00:31:22,480 --> 00:31:26,012
Assim, você pode tipo de apenas--
isso é assim, se você está apenas

700
00:31:26,012 --> 00:31:28,220
tentando irritar um amigo
e eles lhe fazer uma pergunta,

701
00:31:28,220 --> 00:31:31,344
você meio que responder com uma pergunta,
você pode tipo de manter passar a bola.

702
00:31:31,344 --> 00:31:34,560
Mas o que é importante é que se você continuar
fazer a pergunta menor e menor

703
00:31:34,560 --> 00:31:36,910
e menor, você está
não perguntar o que há de sigma

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

705
00:31:39,116 --> 00:31:40,990
Você está fazendo o que é
sigma de n, o que é sigma

706
00:31:40,990 --> 00:31:42,839
de n menos 1, o que é sigma de n menos 2?

707
00:31:42,839 --> 00:31:44,880
Eventualmente sua pergunta
vai tornar-se o quê?

708
00:31:44,880 --> 00:31:50,250
O que é de uma ou sigma
zero, um valor muito pequeno,

709
00:31:50,250 --> 00:31:52,220
e assim que
conseguir isso, o seu amigo,

710
00:31:52,220 --> 00:31:54,350
você não vai perguntar
a mesma pergunta novamente,

711
00:31:54,350 --> 00:31:55,975
você está indo só para dizer, ah, é zero.

712
00:31:55,975 --> 00:31:58,490
Nós somos feitos de jogar este tipo
de jogo cíclico estúpido.

713
00:31:58,490 --> 00:32:02,950
>> Então recursividade é o ato em programação
de uma função que se autodenomina.

714
00:32:02,950 --> 00:32:06,630
Este programa, quando compilado e executado, é
vai se comportar exatamente da mesma maneira,

715
00:32:06,630 --> 00:32:09,620
mas o que é importante é que dentro
de uma função chamada sigma,

716
00:32:09,620 --> 00:32:13,150
há uma linha de código, em que
estamos chamando a nós mesmos,

717
00:32:13,150 --> 00:32:14,980
que, normalmente, seria ruim.

718
00:32:14,980 --> 00:32:21,160
Por exemplo, se eu primeiro
compilou este, assim que sigma--

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

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

721
00:32:25,050 --> 00:32:27,690
Inteiro positivo, por favor, 50 1275.

722
00:32:27,690 --> 00:32:30,810
Então, qual a função parece
ser, com base em um teste, correcta.

723
00:32:30,810 --> 00:32:34,917
Mas e se eu ficar um pouco perigoso
e excluir o chamado caso base,

724
00:32:34,917 --> 00:32:37,750
e dizer, bem, eu só estou fazendo
isso é mais complicado do que é.

725
00:32:37,750 --> 00:32:42,450
Vamos calcular o sigma
tomando m e, em seguida, adicionando

726
00:32:42,450 --> 00:32:44,564
em sigma m de menos um?

727
00:32:44,564 --> 00:32:45,980
Bem, o que vai acontecer aqui?

728
00:32:45,980 --> 00:32:47,140
Vamos diminuir o zoom.

729
00:32:47,140 --> 00:32:52,920
Vamos recompilar o programa,
salvá-lo, recompilar o programa,

730
00:32:52,920 --> 00:33:00,450
e então pronto ./sigma-1 ampliar,
entrar inteiro positivo, por favor, 50.

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

732
00:33:02,180 --> 00:33:04,430
Quantos de vocês estão dispostos
para confessar a ver isso?

733
00:33:04,430 --> 00:33:04,950
>> Está bem.

734
00:33:04,950 --> 00:33:06,690
Então isso pode acontecer por
um certo número de razões,

735
00:33:06,690 --> 00:33:09,148
e, francamente, esta semana estamos
prestes a dar-lhe mais um deles.

736
00:33:09,148 --> 00:33:11,780
Mas, neste caso, tente
raciocinar para trás

737
00:33:11,780 --> 00:33:14,430
o que poderia ter acontecido aqui?

738
00:33:14,430 --> 00:33:17,400
Falha de segmentação, que disse na última
tempo, refere-se a um segmento de memória.

739
00:33:17,400 --> 00:33:18,690
Algo ruim aconteceu.

740
00:33:18,690 --> 00:33:21,550
Mas o que era
mecanicamente que não deu certo

741
00:33:21,550 --> 00:33:25,000
aqui por causa da minha remoção
de que o chamado caso base,

742
00:33:25,000 --> 00:33:26,870
onde voltei um valor embutido?

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

744
00:33:28,970 --> 00:33:30,460
O que você acha que deu errado?

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

746
00:33:31,219 --> 00:33:32,135
>> AUDIÊNCIA: [inaudível].

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

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

749
00:33:36,970 --> 00:33:37,550
Boa pergunta.

750
00:33:37,550 --> 00:33:39,508
Assim, o tamanho do número
que eu estava resumindo

751
00:33:39,508 --> 00:33:41,920
ficou tão grande que excedeu
o tamanho do espaço de memória.

752
00:33:41,920 --> 00:33:44,640
Boa idéia, mas não fundamentalmente
vai causar um acidente.

753
00:33:44,640 --> 00:33:48,230
Isso pode causar estouro de inteiros,
onde os bits simplesmente virar

754
00:33:48,230 --> 00:33:51,760
e, em seguida, nós confundimos realmente um grande
número de como um número negativo,

755
00:33:51,760 --> 00:33:53,260
mas isso em si não vai causar um acidente.

756
00:33:53,260 --> 00:33:55,509
Porque, no final do
dia um int ainda é de 32 bits.

757
00:33:55,509 --> 00:33:57,640
Você não vai
acidentalmente roubar um pouco 33.

758
00:33:57,640 --> 00:33:58,431
Mas um bom pensamento.

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

760
00:33:58,984 --> 00:33:59,900
>> AUDIÊNCIA: [inaudível].

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

762
00:34:00,551 --> 00:34:02,300
COLUNA 1: O método
nunca pára de correr,

763
00:34:02,300 --> 00:34:06,658
e, de fato, chama a si mesmo novamente
e de novo e de novo e de novo

764
00:34:06,658 --> 00:34:08,449
e mais uma vez, e nenhuma
as funções de todos os tempos

765
00:34:08,449 --> 00:34:13,310
terminar, pois seu único linha de
código chama a si mesmos uma e outra vez

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

767
00:34:14,219 --> 00:34:16,080
E o que é realmente
acontecendo aqui, e agora nós

768
00:34:16,080 --> 00:34:18,100
pode tipo de desenhar esse pictoricamente.

769
00:34:18,100 --> 00:34:20,899
Deixai-me passar para um
imagem por apenas um momento.

770
00:34:20,899 --> 00:34:22,940
Esta é uma imagem, que
acabará por detalhar

771
00:34:22,940 --> 00:34:26,336
com mais detalhes, do que está acontecendo
dentro da memória do seu computador.

772
00:34:26,336 --> 00:34:28,460
E verifica-se que em
a parte inferior da imagem

773
00:34:28,460 --> 00:34:29,709
é algo chamado de pilha.

774
00:34:29,709 --> 00:34:31,920
Este é um pedaço de
memória, um pedaço de memória RAM,

775
00:34:31,920 --> 00:34:33,920
que é apenas usado a qualquer momento
uma função é chamada.

776
00:34:33,920 --> 00:34:36,239
Toda vez que você, programador,
chamar uma função,

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

778
00:34:38,860 --> 00:34:41,920
pega um monte de bytes, talvez um
poucos kilobytes, talvez alguns megabytes

779
00:34:41,920 --> 00:34:44,590
de memória, os entrega
para você, e então permite que

780
00:34:44,590 --> 00:34:47,650
você executar a sua função usando
o que quer que as variáveis ​​que você precisa.

781
00:34:47,650 --> 00:34:50,699
E se, em seguida, chamar outro
função e uma outra função,

782
00:34:50,699 --> 00:34:53,590
você começa uma outra fatia de memória
e outra fatia de memória.

783
00:34:53,590 --> 00:34:57,090
>> E, de fato, se estas bandejas verdes
de Annenberg representam a memória,

784
00:34:57,090 --> 00:34:59,870
aqui está o que acontece pela primeira
vez que você chamar função sigma.

785
00:34:59,870 --> 00:35:04,510
É como colocar uma bandeja como esta
sobre o que é inicialmente uma pilha vazia.

786
00:35:04,510 --> 00:35:07,142
Mas, então, se essa bandeja
chama-se, por assim dizer,

787
00:35:07,142 --> 00:35:08,850
chamando outra instância
de sigma, que é

788
00:35:08,850 --> 00:35:11,640
como perguntar o sistema operacional,
ooh, precisa de um pouco mais de memória,

789
00:35:11,640 --> 00:35:12,520
me que dar.

790
00:35:12,520 --> 00:35:14,840
E então ele fica empilhado em na parte superior.

791
00:35:14,840 --> 00:35:18,030
Mas o que é importante aqui é que
a primeira bandeja ainda está lá,

792
00:35:18,030 --> 00:35:20,620
porque ele invocou esta segunda bandeja.

793
00:35:20,620 --> 00:35:23,500
Agora, entretanto, chamar sigma sigma,
Isso é como perguntar para mais memória.

794
00:35:23,500 --> 00:35:25,830
Fica empilhado em cima aqui.

795
00:35:25,830 --> 00:35:29,350
sigma chamar sigma, que é um outro
bandeja que fica empilhado aqui.

796
00:35:29,350 --> 00:35:32,942
E se você continuar fazendo isso,
eventualmente, tipo de mapear esse visual

797
00:35:32,942 --> 00:35:35,525
para esse gráfico, o que vai
acontecer com a pilha de bandejas?

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

799
00:35:37,480 --> 00:35:41,160
Ele vai exceder o montante
de memória do computador.

800
00:35:41,160 --> 00:35:45,790
E assim que esta bandeja verde
excede a linha horizontal

801
00:35:45,790 --> 00:35:49,410
acima pilha e acima dessa palavra montão,
que vamos voltar no futuro,

802
00:35:49,410 --> 00:35:50,410
que é uma coisa ruim.

803
00:35:50,410 --> 00:35:52,810
A pilha é um diferente
segmento de memória,

804
00:35:52,810 --> 00:35:55,190
e se você deixar que estes
bandejas de pilha e pilha em,

805
00:35:55,190 --> 00:35:57,800
você vai exceder
seu próprio segmento de memória,

806
00:35:57,800 --> 00:36:00,420
e um programa é de fato vai falhar.

807
00:36:00,420 --> 00:36:02,930
>> Agora, como um aparte, esta idéia
de recursividade, portanto,

808
00:36:02,930 --> 00:36:06,500
pode claramente levar a problemas, mas
não é necessariamente uma coisa ruim.

809
00:36:06,500 --> 00:36:08,840
Porque considerar, depois
tudo, e talvez how--

810
00:36:08,840 --> 00:36:11,700
isso leva algum tempo para se acostumar
• Como a elegante ou como simples

811
00:36:11,700 --> 00:36:14,890
que a implementação do sigma foi.

812
00:36:14,890 --> 00:36:17,440
E nós não vamos usar
recursão muito nos CS50,

813
00:36:17,440 --> 00:36:20,780
mas em CS51, e realmente qualquer classe
onde você manipular estruturas de dados

814
00:36:20,780 --> 00:36:23,640
como árvores ou árvores genealógicas,
que têm alguma hierarquia,

815
00:36:23,640 --> 00:36:26,000
ele é super, super útil.

816
00:36:26,000 --> 00:36:29,750
Agora, como um aparte, para que você
como aspirantes a cientistas da computação

817
00:36:29,750 --> 00:36:33,180
estão familiarizados com alguns dos Google
piadas, se você vai para o Google

818
00:36:33,180 --> 00:36:36,345
e você olha para o que está a
definição de, digamos, a recursão, digite.

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
Como um aparte, eu puxei um pouco.

822
00:36:42,670 --> 00:36:45,470
Isso foi como 10 minutos de
procrastinação esta manhã.

823
00:36:45,470 --> 00:36:52,890
Se você também Google "torto", aviso
inclinando a cabeça slightly--

824
00:36:52,890 --> 00:36:55,120
e então este é, talvez,
mais atroz de todos

825
00:36:55,120 --> 00:36:57,286
desde que alguém passou como
seu dia de aplicação do presente

826
00:36:57,286 --> 00:36:59,880
alguns anos ago-- vamos.

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

828
00:37:01,140 --> 00:37:04,540
Oh, wait-- isso é um bug.

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

830
00:37:08,410 --> 00:37:11,410
>> Assim sendo executado em um dos
maiores sites do mundo

831
00:37:11,410 --> 00:37:13,510
são esses ovos de Páscoa estúpidos.

832
00:37:13,510 --> 00:37:16,690
Eles provavelmente consumir uma
número não trivial de linhas de código

833
00:37:16,690 --> 00:37:19,280
apenas para que possamos ter
pequenas coisas divertidas como essa.

834
00:37:19,280 --> 00:37:22,140
Mas pelo menos agora você começa
algumas dessas piadas.

835
00:37:22,140 --> 00:37:28,330
>> Agora vamos dar uma olhada em algumas das
branco mentiras que temos vindo a dizer nos últimos tempos,

836
00:37:28,330 --> 00:37:30,707
e começar a descascar
algumas camadas tecnicamente

837
00:37:30,707 --> 00:37:32,790
de modo que você realmente entender
o que está acontecendo

838
00:37:32,790 --> 00:37:34,860
e você pode entender
algumas das ameaças,

839
00:37:34,860 --> 00:37:38,060
como Shellshock, que
já começou a se tornar

840
00:37:38,060 --> 00:37:41,110
na vanguarda de todo mundo
atenção, pelo menos nos meios de comunicação.

841
00:37:41,110 --> 00:37:45,810
Então aqui está uma função muito simples
que retorna nada, vazio.

842
00:37:45,810 --> 00:37:46,790
Seu nome é swap.

843
00:37:46,790 --> 00:37:50,880
Leva em duas variáveis
e ele retorna nada.

844
00:37:50,880 --> 00:37:52,260
Leva em ae b.

845
00:37:52,260 --> 00:37:53,337
Então, uma rápida demonstração.

846
00:37:53,337 --> 00:37:54,170
Trouxemos estes acima.

847
00:37:54,170 --> 00:37:56,100
Podemos muito bem ter um pouco
quebrar aqui por apenas um momento

848
00:37:56,100 --> 00:37:57,250
e ter um pouco de algo para beber.

849
00:37:57,250 --> 00:38:00,120
Se alguém não se importaria se juntar
me até aqui só por um momento.

850
00:38:00,120 --> 00:38:01,830
E quanto a você com a camisa marrom?

851
00:38:01,830 --> 00:38:02,335
Vamos lá para cima.

852
00:38:02,335 --> 00:38:04,060

853
00:38:04,060 --> 00:38:05,260
Apenas o de hoje.

854
00:38:05,260 --> 00:38:06,251
Obrigado, no entanto.

855
00:38:06,251 --> 00:38:08,000
Tudo bem, e temos
chegando que aqui?

856
00:38:08,000 --> 00:38:08,660
Qual o seu nome?

857
00:38:08,660 --> 00:38:09,360
>> COLUNA 4: Laura.

858
00:38:09,360 --> 00:38:09,740
>> COLUNA 1: Laura.

859
00:38:09,740 --> 00:38:10,370
Vamos lá para cima.

860
00:38:10,370 --> 00:38:11,460

861
00:38:11,460 --> 00:38:13,850
Então Laura, desafio muito simples hoje.

862
00:38:13,850 --> 00:38:14,704

863
00:38:14,704 --> 00:38:15,370
Prazer em conhecê-yo.

864
00:38:15,370 --> 00:38:16,410

865
00:38:16,410 --> 00:38:16,910
Tudo certo.

866
00:38:16,910 --> 00:38:21,179
Portanto, temos um pouco de leite até aqui e
nós temos um pouco de suco de laranja aqui

867
00:38:21,179 --> 00:38:23,345
e alguns copos que nós
emprestado de Annenberg hoje.

868
00:38:23,345 --> 00:38:24,178
>> COLUNA 4: emprestado.

869
00:38:24,178 --> 00:38:27,240
COLUNA 1: E indo para a frente
e dar-lhe metade de um copo de presente.

870
00:38:27,240 --> 00:38:28,250

871
00:38:28,250 --> 00:38:28,800
Tudo certo.

872
00:38:28,800 --> 00:38:30,750
E nós vamos dar-lhe metade
um copo de leite.

873
00:38:30,750 --> 00:38:31,905

874
00:38:31,905 --> 00:38:35,890
Ah, e só para que você possa
lembre-se que este era como,

875
00:38:35,890 --> 00:38:38,860
Lembrei-me de trazer
isso e hoje.

876
00:38:38,860 --> 00:38:42,030

877
00:38:42,030 --> 00:38:42,530
Ok.

878
00:38:42,530 --> 00:38:45,470
Se você não se importa, vamos ver, nós
pode colocá-los sobre seus próprios óculos

879
00:38:45,470 --> 00:38:46,560
se você quiser.

880
00:38:46,560 --> 00:38:48,710
Este vai ser o mundo de olhos de Laura.

881
00:38:48,710 --> 00:38:49,210
Tudo certo.

882
00:38:49,210 --> 00:38:53,820
Portanto, o seu objetivo, dado duas xícaras de
líquido aqui, leite e suco de laranja,

883
00:38:53,820 --> 00:38:58,370
é trocar os dois conteúdos de modo que a
suco de laranja vai para a xícara de leite

884
00:38:58,370 --> 00:39:00,710
e o leite passa para
o copo de suco de laranja.

885
00:39:00,710 --> 00:39:02,359
>> COLUNA 4: Eu recebo um outro copo?

886
00:39:02,359 --> 00:39:05,650
COLUNA 1: Eu estou tão feliz que você perguntou, embora
que teria sido muito melhor filmagem

887
00:39:05,650 --> 00:39:06,710
se você não tivesse pedido.

888
00:39:06,710 --> 00:39:10,620
Mas sim, nós podemos oferecer-lhe um terceiro
copo que está vazio, é claro.

889
00:39:10,620 --> 00:39:11,120
Tudo certo.

890
00:39:11,120 --> 00:39:12,300
Então trocar o conteúdo lá.

891
00:39:12,300 --> 00:39:16,100

892
00:39:16,100 --> 00:39:17,050
Muito bom.

893
00:39:17,050 --> 00:39:20,390

894
00:39:20,390 --> 00:39:21,305
Muito bom.

895
00:39:21,305 --> 00:39:23,121

896
00:39:23,121 --> 00:39:24,745
Você está fazendo isso extremamente cuidado.

897
00:39:24,745 --> 00:39:26,970

898
00:39:26,970 --> 00:39:28,655
E o passo três.

899
00:39:28,655 --> 00:39:30,390

900
00:39:30,390 --> 00:39:31,350
Tudo certo.

901
00:39:31,350 --> 00:39:31,930
Excelente.

902
00:39:31,930 --> 00:39:33,930
Um grande aplauso
seria bom para Laura.

903
00:39:33,930 --> 00:39:36,500

904
00:39:36,500 --> 00:39:37,000
Tudo certo.

905
00:39:37,000 --> 00:39:40,790
Temos um pequeno presente de despedida
para você, mas deixe-me levá-los.

906
00:39:40,790 --> 00:39:42,620
Muito obrigado.

907
00:39:42,620 --> 00:39:46,170
Assim, um exemplo simples, no entanto,
para demonstrar que, se você fizer

908
00:39:46,170 --> 00:39:48,300
quer trocar o conteúdo
de dois recipientes,

909
00:39:48,300 --> 00:39:52,360
ou vamos chamá-los de variáveis,
você precisa de algum armazenamento temporário

910
00:39:52,360 --> 00:39:56,710
encenar um dos conteúdos na
que você pode realmente fazer a troca.

911
00:39:56,710 --> 00:40:01,790
Então, na verdade, este código fonte aqui em
C é representativa de exatamente isso.

912
00:40:01,790 --> 00:40:06,340
Se o sumo de laranja era um eo leite
era b, e queríamos trocar os dois,

913
00:40:06,340 --> 00:40:08,990
você poderia tentar algo criativo
vertendo-se umas às outras,

914
00:40:08,990 --> 00:40:11,031
mas que provavelmente não
acabar particularmente bem.

915
00:40:11,031 --> 00:40:15,260
E, assim, usar um copo terceira, chamada
ele tmp, T-M-P, por convenção,

916
00:40:15,260 --> 00:40:19,370
e colocar o conteúdo do
JO em que, em seguida, trocar um copo,

917
00:40:19,370 --> 00:40:22,610
em seguida, colocar o JO no
copo originais, assim

918
00:40:22,610 --> 00:40:25,320
atingir, exatamente como
Laura fez, o swap.

919
00:40:25,320 --> 00:40:26,850
>> Então, vamos fazer exatamente isso.

920
00:40:26,850 --> 00:40:30,110
Deixe-me ir em frente e abrir
-se um exemplo de que é

921
00:40:30,110 --> 00:40:32,720
na verdade, chamado de "não
Swap ", porque este não é

922
00:40:32,720 --> 00:40:36,180
como simplesmente feito como se poderia pensar.

923
00:40:36,180 --> 00:40:41,190
Então, neste programa, note que
Estou usando stdio.h, nosso velho amigo.

924
00:40:41,190 --> 00:40:43,130
Eu tenho o protótipo
para trocar lá em cima, o que

925
00:40:43,130 --> 00:40:45,450
significa a sua implementação de
provavelmente abaixo,

926
00:40:45,450 --> 00:40:48,050
e vamos ver o que este principal
programa vai fazer por mim.

927
00:40:48,050 --> 00:40:52,020
A primeira vez que declarar int x recebe
um, e int y recebe dois.

928
00:40:52,020 --> 00:40:54,930
Então, acho que aqueles que JO
e leite, respectivamente.

929
00:40:54,930 --> 00:40:57,100
E então eu só tenho um
printf dizendo x é este

930
00:40:57,100 --> 00:41:00,120
e y é isso, só para que eu possa
visualmente ver o que está acontecendo.

931
00:41:00,120 --> 00:41:03,810
Então eu printf reivindicando
que eu estou trocando os dois,

932
00:41:03,810 --> 00:41:07,100
e então eu imprimir um
afirmam que eles são trocados,

933
00:41:07,100 --> 00:41:09,300
e eu imprimir x e y novamente.

934
00:41:09,300 --> 00:41:13,010
Então, aqui em swap é
exatamente o que Laura fez,

935
00:41:13,010 --> 00:41:16,240
e exatamente o que vimos em
a tela de um momento atrás.

936
00:41:16,240 --> 00:41:19,380
>> Então, vamos em frente e
uma grande desilusão.

937
00:41:19,380 --> 00:41:24,690
Não se troca, e não corre swap,
zoom sobre a saída aqui.

938
00:41:24,690 --> 00:41:28,320
Digite x é 1, y é 2, trocando trocados.

939
00:41:28,320 --> 00:41:32,700
ainda x é 1, e y é ainda 2.

940
00:41:32,700 --> 00:41:37,630
Assim, mesmo que, francamente, isso parece
exatamente como, ainda mais tecnicamente,

941
00:41:37,630 --> 00:41:40,730
Laura o que fez, não parece funcionar.

942
00:41:40,730 --> 00:41:42,130
Então, por que isso?

943
00:41:42,130 --> 00:41:46,630
Bem, acontece que quando
nós escrevemos um programa como este

944
00:41:46,630 --> 00:41:51,590
que tem tanto principal, destacamos aqui,
e, em seguida, uma outra função, como swap,

945
00:41:51,590 --> 00:41:54,230
Destacam-se aqui, que
chama, o mundo

946
00:41:54,230 --> 00:41:57,030
parece um pouco algo como
estas bandejas há pouco.

947
00:41:57,030 --> 00:42:00,440
Quando principal em primeiro lugar é chamado,
Isso é como perguntar sistema operacional

948
00:42:00,440 --> 00:42:04,030
para um pouco de memória para qualquer local,
variáveis ​​como x e y que a principal tem,

949
00:42:04,030 --> 00:42:05,660
e eles acabam por aí.

950
00:42:05,660 --> 00:42:10,920
Mas, se as chamadas principais trocar, e principal
passa para trocar dois argumentos, a e b,

951
00:42:10,920 --> 00:42:16,410
suco de laranja e leite, não é como
entregando o suco de laranja eo leite

952
00:42:16,410 --> 00:42:17,500
para Laura.

953
00:42:17,500 --> 00:42:21,300
O que um computador faz, é
passa cópias do suco de laranja

954
00:42:21,300 --> 00:42:27,110
e cópias do leite para Laura, de modo que
o que é, em última análise dentro desta bandeja

955
00:42:27,110 --> 00:42:32,510
é o valor de um e dois, ou JO
e leite, mas cópias dos mesmos,

956
00:42:32,510 --> 00:42:34,790
de modo que, neste ponto
na história, não

957
00:42:34,790 --> 00:42:36,930
é JO e leite em cada uma destas bandejas.

958
00:42:36,930 --> 00:42:39,260
Há um um e dois
em cada uma destas bandejas,

959
00:42:39,260 --> 00:42:41,720
ea função de swap é de fato trabalhando.

960
00:42:41,720 --> 00:42:46,090
Está trocando-os por dentro
de bandeja o segundo mais alto,

961
00:42:46,090 --> 00:42:48,147
mas que a troca não tem impacto.

962
00:42:48,147 --> 00:42:49,980
E com base em apenas algumas
princípio básico nós temos

963
00:42:49,980 --> 00:42:52,970
falamos antes, e de fato
a poucos minutos atrás, o que

964
00:42:52,970 --> 00:42:58,770
poderia explicar por que mudar
a e b dentro de troca

965
00:42:58,770 --> 00:43:05,560
não tem efeito sobre x e y, embora
Passei x e y para a função swap.

966
00:43:05,560 --> 00:43:08,750
Qual é a palavra chave aqui que
pode simplista explicar?

967
00:43:08,750 --> 00:43:11,250

968
00:43:11,250 --> 00:43:12,627
Acho que ouvi-lo aqui?

969
00:43:12,627 --> 00:43:13,335
AUDIÊNCIA: Return.

970
00:43:13,335 --> 00:43:14,085
COLUNA 1: Retorno?

971
00:43:14,085 --> 00:43:14,590
Não voltar.

972
00:43:14,590 --> 00:43:15,895
Vamos com um outro.

973
00:43:15,895 --> 00:43:16,395
O que é isso?

974
00:43:16,395 --> 00:43:17,080
>> AUDIÊNCIA: [inaudível].

975
00:43:17,080 --> 00:43:20,000
>> COLUNA 1: OK, então return-- pudéssemos
tornar o trabalho de retorno na história,

976
00:43:20,000 --> 00:43:21,914
mas há uma explicação ainda mais simples.

977
00:43:21,914 --> 00:43:22,580
AUDIÊNCIA: Scope.

978
00:43:22,580 --> 00:43:23,288
COLUNA 1: Âmbito.

979
00:43:23,288 --> 00:43:24,300
Vou levar escopo.

980
00:43:24,300 --> 00:43:27,290
Então alcance, lembre-se que
a x e y declarada.

981
00:43:27,290 --> 00:43:30,840
Eles estão declaradas dentro
de principal até aqui.

982
00:43:30,840 --> 00:43:33,200
a e b, entretanto, são
efetivamente declarado

983
00:43:33,200 --> 00:43:35,930
dentro de swap, não exatamente
as chaves, mas ainda

984
00:43:35,930 --> 00:43:37,690
na área geral de swap.

985
00:43:37,690 --> 00:43:40,560
E assim, de facto, a e b
só existem dentro dessa bandeja

986
00:43:40,560 --> 00:43:44,850
de Annenberg, esta
segunda parte do código.

987
00:43:44,850 --> 00:43:49,500
Então, nós estamos mudando a cópia, mas
isso não é realmente tudo o que útil.

988
00:43:49,500 --> 00:43:52,190
>> Então, vamos dar uma olhada
este nível um pouco inferior.

989
00:43:52,190 --> 00:43:55,430
Eu vou voltar para
o diretório de origem,

990
00:43:55,430 --> 00:43:58,330
e eu estou indo para a primeira
zoom aqui, e apenas

991
00:43:58,330 --> 00:44:02,290
para confirmar que estou nesta
janela de terminal maior,

992
00:44:02,290 --> 00:44:04,430
o programa ainda está se comportando assim.

993
00:44:04,430 --> 00:44:06,840
Suponha agora que este
não é intencional.

994
00:44:06,840 --> 00:44:10,090
É evidente que eu queria swap para
trabalho, por isso se sente como um bug.

995
00:44:10,090 --> 00:44:12,780
Agora eu poderia começar a adicionar um
Muitas printf do para o meu código,

996
00:44:12,780 --> 00:44:16,010
imprimir x aqui, y sobre
aqui, um ali, b aqui.

997
00:44:16,010 --> 00:44:18,220
Mas, francamente, isso é provavelmente o que
você tem feito por um par de semanas

998
00:44:18,220 --> 00:44:20,190
agora, no horário de expediente
e em casa quando se trabalha

999
00:44:20,190 --> 00:44:22,150
em Série de Exercícios tentando encontrar alguns bugs.

1000
00:44:22,150 --> 00:44:25,560
Mas você vai ver, se você não tiver,
que conjunto de problemas apresenta três

1001
00:44:25,560 --> 00:44:31,630
para um comando chamado GDB,
onde GDB, depurador GNU,

1002
00:44:31,630 --> 00:44:34,040
tem-se um monte de
recursos que podem, na verdade,

1003
00:44:34,040 --> 00:44:38,160
vamos entender situações
como este, mas mais convincente,

1004
00:44:38,160 --> 00:44:39,940
resolver problemas e encontrar bugs.

1005
00:44:39,940 --> 00:44:40,940
Então, eu vou fazer isso.

1006
00:44:40,940 --> 00:44:44,770
Em vez de ./noswap, estou vez
vai correr GDB ./noswap.

1007
00:44:44,770 --> 00:44:47,410

1008
00:44:47,410 --> 00:44:51,200
Em outras palavras, eu estou indo para executar o meu
programa não em Bash, nosso novo amigo

1009
00:44:51,200 --> 00:44:51,850
hoje.

1010
00:44:51,850 --> 00:44:53,970
Eu estou indo para executar o meu
programa noswap dentro

1011
00:44:53,970 --> 00:44:56,900
deste outro programa chamado
GDB, que é um depurador, que

1012
00:44:56,900 --> 00:45:01,035
é um programa que foi projetado para ajudar
Vocês, humanos, encontrar e remover bugs.

1013
00:45:01,035 --> 00:45:03,410
Então, se eu bater correr aqui, há
uma quantidade atroz de texto

1014
00:45:03,410 --> 00:45:04,868
que você realmente nunca tem que ler.

1015
00:45:04,868 --> 00:45:07,290
É essencialmente uma distração
a partir da linha, que

1016
00:45:07,290 --> 00:45:10,030
Eu vou bater Control-L
para chegar no topo lá.

1017
00:45:10,030 --> 00:45:11,800
Este é o prompt GDB.

1018
00:45:11,800 --> 00:45:15,550
Se eu quiser executar este programa agora,
como esta pequena folha de fraude em hoje

1019
00:45:15,550 --> 00:45:21,860
slides sugere, Run é o primeiro
ordena que pretendia introduzir.

1020
00:45:21,860 --> 00:45:25,150
E eu estou indo só para digitar
correr até aqui dentro de GDB,

1021
00:45:25,150 --> 00:45:26,811
e na verdade ele correu meu programa.

1022
00:45:26,811 --> 00:45:29,310
Agora há algum adicional
saídas da tela como esta,

1023
00:45:29,310 --> 00:45:31,910
mas isso é GDB apenas sendo anal
e nos dizer o que está acontecendo.

1024
00:45:31,910 --> 00:45:34,451
Você realmente não precisa se preocupar
sobre esses detalhes agora mesmo.

1025
00:45:34,451 --> 00:45:36,890
Mas o que é realmente legal sobre
GDB, se eu fizer isso novamente--

1026
00:45:36,890 --> 00:45:42,100
Control-L limpa o screen-- deixe-me ir
em frente e digite "quebrar principal", assim,

1027
00:45:42,100 --> 00:45:45,743
quando eu pressione Enter, definindo o que é
chamado um ponto de ruptura na noswap.c,

1028
00:45:45,743 --> 00:45:51,270
linha 16, que é onde GDB
descobri o meu programa, na verdade,

1029
00:45:51,270 --> 00:45:53,070
é, a minha função é realmente.

1030
00:45:53,070 --> 00:45:55,070
Isso nós vamos ignorar por agora
mas esse é o endereço

1031
00:45:55,070 --> 00:45:57,310
na memória especificamente desta função.

1032
00:45:57,310 --> 00:46:00,240
Então agora quando eu digito correr,
perceber o que é legal aqui.

1033
00:46:00,240 --> 00:46:05,650
Meu programa quebra na linha I
disse GDB para pausar a execução em.

1034
00:46:05,650 --> 00:46:09,850
Então eu não tenho que mudar agora meu código,
adicionar alguns printf de, recompilar, reprise

1035
00:46:09,850 --> 00:46:13,300
ele, alterar, adicionar alguns printf do,
salvá-lo, recompilar, executá-lo.

1036
00:46:13,300 --> 00:46:18,100
Eu só posso andar através do meu programa
passo a passo a passo na velocidade humana,

1037
00:46:18,100 --> 00:46:20,880
não no tipo Intel dentro da velocidade.

1038
00:46:20,880 --> 00:46:24,580
>> Então agora perceber essa linha
aparece aqui, e se eu voltar

1039
00:46:24,580 --> 00:46:27,800
ao meu programa no gedit,
perceber que isso é verdade

1040
00:46:27,800 --> 00:46:29,280
a primeira linha de código.

1041
00:46:29,280 --> 00:46:31,240
Há linha 16 em gedit.

1042
00:46:31,240 --> 00:46:34,610
Há linha 16 no GDB, e mesmo
embora esta interface em preto e branco

1043
00:46:34,610 --> 00:46:37,760
não é tão usuário
amigável, isso significa

1044
00:46:37,760 --> 00:46:41,680
que a linha 16 não foi executado
ainda, mas que está prestes a ser.

1045
00:46:41,680 --> 00:46:46,220
Então, na verdade, se eu digitar impressão
x, não printf, apenas print x,

1046
00:46:46,220 --> 00:46:50,730
Eu recebo algum valor falso lá de zero,
porque x ainda não foi inicializado.

1047
00:46:50,730 --> 00:46:54,760
Então eu vou escrever a seguir, ou, se você
quer ser extravagante, apenas n para o próximo.

1048
00:46:54,760 --> 00:46:59,090
Mas quando eu digito seguinte entra, agora
notar que se move sobre a linha 17.

1049
00:46:59,090 --> 00:47:02,840
Então, logicamente, se eu tiver executado
linha 16 e agora estou a escrever print x,

1050
00:47:02,840 --> 00:47:03,640
o que devo ver?

1051
00:47:03,640 --> 00:47:04,970

1052
00:47:04,970 --> 00:47:05,520
Uma.

1053
00:47:05,520 --> 00:47:07,820
>> E agora esse é reconhecidamente confuso.

1054
00:47:07,820 --> 00:47:11,260
Dois dólares é apenas uma maneira elegante de, se você
quero referir-se a esse valor mais tarde,

1055
00:47:11,260 --> 00:47:12,510
você pode dizer "sinal de dólar dois."

1056
00:47:12,510 --> 00:47:13,480
É como uma referência para trás.

1057
00:47:13,480 --> 00:47:14,570
Mas, por enquanto, apenas ignorá-lo.

1058
00:47:14,570 --> 00:47:17,070
O que é interessante é o que é
à direita do sinal de igual.

1059
00:47:17,070 --> 00:47:21,000
E agora se eu digitar seguinte novamente
e imprimir y, eu deveria ver 2.

1060
00:47:21,000 --> 00:47:23,870
Eu também já pode imprimir
x novamente, e, francamente,

1061
00:47:23,870 --> 00:47:27,130
se eu estou ficando um pouco confuso quanto ao
onde eu estou, eu posso tipo de lista para lista

1062
00:47:27,130 --> 00:47:30,590
e só ver algum contexto ao redor
o ponto que eu estou realmente em.

1063
00:47:30,590 --> 00:47:35,180
E agora eu posso escrever
ao lado, e não é x 1.

1064
00:47:35,180 --> 00:47:36,300
Agora eu digito seguinte.

1065
00:47:36,300 --> 00:47:37,710
Oh, y é 2.

1066
00:47:37,710 --> 00:47:40,750
E mais uma vez, é confuso,
porque a produção do GDB

1067
00:47:40,750 --> 00:47:43,044
está sendo misturados com a minha própria saída.

1068
00:47:43,044 --> 00:47:45,710
Mas se você manter em mente, por
olhando para trás e para a frente em seu código

1069
00:47:45,710 --> 00:47:47,740
ou colocando-o para fora do lado
a lado, talvez, você vai

1070
00:47:47,740 --> 00:47:51,020
ver que realmente eu sou apenas
percorrendo meu programa.

1071
00:47:51,020 --> 00:47:54,620
>> Mas observe o que acontece em seguida, literalmente.

1072
00:47:54,620 --> 00:47:56,380
Aqui está a linha 22.

1073
00:47:56,380 --> 00:48:01,315
Deixe-me ir sobre ele, movendo-se, assim, em
a 23, e se eu imprimir x agora, ainda um.

1074
00:48:01,315 --> 00:48:03,890
E se eu imprimir y agora, ainda um.

1075
00:48:03,890 --> 00:48:05,820
Portanto, este não é um exercício útil.

1076
00:48:05,820 --> 00:48:07,450
Então, vamos refazer isso.

1077
00:48:07,450 --> 00:48:10,069
Deixe-me voltar até o
tiragem superior e tipo novamente.

1078
00:48:10,069 --> 00:48:12,110
E ele está dizendo o programa
que está sendo depurado

1079
00:48:12,110 --> 00:48:14,109
já começou,
iniciado a partir do início.

1080
00:48:14,109 --> 00:48:15,420
Sim, vamos fazer isso de novo.

1081
00:48:15,420 --> 00:48:22,000
E desta vez vamos fazer a seguir,
next, next, next, next,

1082
00:48:22,000 --> 00:48:24,180
mas agora as coisas começam a ficar interessantes.

1083
00:48:24,180 --> 00:48:27,760
Agora eu quero entrar
swap, então eu não digitar em seguida.

1084
00:48:27,760 --> 00:48:34,380
Eu digito passo, e agora percebe que
me saltou para a linha noswap.c 33.

1085
00:48:34,380 --> 00:48:37,240
Se eu voltar para o gedit, o que é linha 33?

1086
00:48:37,240 --> 00:48:40,500
Essa é a primeira real
linha de código dentro de swap.

1087
00:48:40,500 --> 00:48:44,150
O que é bom, porque agora eu posso
tipo de fuçar e ficar curioso

1088
00:48:44,150 --> 00:48:46,052
sobre o que está acontecendo realmente lá.

1089
00:48:46,052 --> 00:48:46,760
Deixe-me imprimir 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
Por que ter algum tmp
louco, valor de lixo falso?

1093
00:48:51,438 --> 00:48:54,579

1094
00:48:54,579 --> 00:48:56,120
AUDIÊNCIA: Não foi inicializado.

1095
00:48:56,120 --> 00:48:57,150
COLUNA 1: Não foi inicializado.

1096
00:48:57,150 --> 00:49:00,270
E, de fato, quando você executar um programa,
você está dado um monte de memória

1097
00:49:00,270 --> 00:49:03,392
pelo sistema operacional, mas você
não inicializou quaisquer valores,

1098
00:49:03,392 --> 00:49:05,600
então o que você está bocados
vendo aqui, mesmo que seja

1099
00:49:05,600 --> 00:49:07,770
este grande negativo louco
número, significa apenas

1100
00:49:07,770 --> 00:49:10,750
que aqueles que são os restos de
algum uso anterior de que a memória RAM,

1101
00:49:10,750 --> 00:49:13,050
apesar de eu não ter
eu precisava disso ainda.

1102
00:49:13,050 --> 00:49:17,086
Então agora eu estou indo para ir em frente e tipo
seguinte, e se eu agora digite impressão tmp,

1103
00:49:17,086 --> 00:49:17,835
o que devo ver?

1104
00:49:17,835 --> 00:49:19,570

1105
00:49:19,570 --> 00:49:23,360
Seja qual for o valor de a foi,
um é o primeiro argumento, apenas

1106
00:49:23,360 --> 00:49:25,550
como x foi o primeiro
coisa que está sendo transmitido,

1107
00:49:25,550 --> 00:49:30,450
assim um e x deve ser o mesmo,
assim imprimir tmp deve imprimir-me um.

1108
00:49:30,450 --> 00:49:36,360
>> Então, o que você verá no conjunto de problemas
três é um tutorial das sortes no GDB,

1109
00:49:36,360 --> 00:49:40,020
mas percebe que este é o começo
de uma olhada em uma ferramenta que vai realmente

1110
00:49:40,020 --> 00:49:42,774
ajudá-lo a resolver problemas
forma muito mais eficaz.

1111
00:49:42,774 --> 00:49:44,690
O que nós estamos, em última instância
vai fazer na quarta-feira

1112
00:49:44,690 --> 00:49:48,180
é começar a descascar algumas camadas
e remover algumas rodinhas.

1113
00:49:48,180 --> 00:49:50,496
Essa coisa chamada cadeia que
temos utilizado durante algum tempo,

1114
00:49:50,496 --> 00:49:53,370
vamos tomar lentamente que longe
de você e começar a falar sobre

1115
00:49:53,370 --> 00:49:55,725
algo mais esotericamente
conhecido como char *,

1116
00:49:55,725 --> 00:49:59,550
mas vamos fazer isso agradável e
suavemente em primeiro lugar, embora os ponteiros,

1117
00:49:59,550 --> 00:50:02,730
como são chamados, podem fazer alguma
coisas muito ruins se vítimas de abuso,

1118
00:50:02,730 --> 00:50:06,040
olhando um pouco de claymation
nosso amigo Nick Parlante de Stanford

1119
00:50:06,040 --> 00:50:09,670
Universidade, professor em computador
ciência que montar esse pré-visualização

1120
00:50:09,670 --> 00:50:11,075
do que está por vir nesta quarta-feira.

1121
00:50:11,075 --> 00:50:12,196

1122
00:50:12,196 --> 00:50:13,400
>> [REPRODUÇÃO]

1123
00:50:13,400 --> 00:50:13,900
Ei, Binky.

1124
00:50:13,900 --> 00:50:14,930

1125
00:50:14,930 --> 00:50:15,780
Acorde.

1126
00:50:15,780 --> 00:50:17,240
É hora de diversão ponteiro.

1127
00:50:17,240 --> 00:50:18,260

1128
00:50:18,260 --> 00:50:19,350
>> -Qual Que é isso?

1129
00:50:19,350 --> 00:50:21,150
Saiba mais sobre ponteiros?

1130
00:50:21,150 --> 00:50:22,050
Ah, que bom!

1131
00:50:22,050 --> 00:50:22,897

1132
00:50:22,897 --> 00:50:23,730
[FIM REPRODUÇÃO DE VÍDEO]

1133
00:50:23,730 --> 00:50:25,396
COLUNA 1: Que espera por você na quarta-feira.

1134
00:50:25,396 --> 00:50:26,440
Vamos vê-lo em seguida.

1135
00:50:26,440 --> 00:50:27,106
[REPRODUÇÃO]

1136
00:50:27,106 --> 00:50:30,420
-E Agora, pensamentos profundos,
por Daven Farnham.

1137
00:50:30,420 --> 00:50:33,980

1138
00:50:33,980 --> 00:50:35,900
>> Por quê estamos aprendendo C?

1139
00:50:35,900 --> 00:50:36,785
Por que não A +?

1140
00:50:36,785 --> 00:50:38,550

1141
00:50:38,550 --> 00:50:40,910
>> [Risos]

1142
00:50:40,910 --> 00:50:42,160
>> [FIM REPRODUÇÃO DE VÍDEO]