1
00:00:00,000 --> 00:00:12,040
>> [Přehrávání hudby]

2
00:00:12,040 --> 00:00:16,460
>> SPEAKER 1: Tak jo, to je CS50,
a to je začátek čtvrtého týdne

3
00:00:16,460 --> 00:00:20,420
a jak jste možná slyšeli nebo
číst, byl svět končí.

4
00:00:20,420 --> 00:00:23,520
Chystáte se na celém internetu
byl znalosti a povědomí

5
00:00:23,520 --> 00:00:27,100
chyby v programu, což je
programovací jazyk s názvem Bash.

6
00:00:27,100 --> 00:00:32,729
To bylo nádherně značkové
jako Shellshock nebo dveře Bash,

7
00:00:32,729 --> 00:00:35,485
ale předměty, jako jsou tyto
nebyly neobvyklé.

8
00:00:35,485 --> 00:00:38,807
A ve skutečnosti, mnoho z nich, aby
vzpomínky Heartbleed,

9
00:00:38,807 --> 00:00:41,640
které jste si možná všimli v
stiskněte znovu letos na jaře, což

10
00:00:41,640 --> 00:00:43,980
byl podobně docela dramatický.

11
00:00:43,980 --> 00:00:47,110
Teď ti z vás
dnes, kolik z vás,

12
00:00:47,110 --> 00:00:50,330
i když nechápu, co
je to všechno o, slyšel Shellshock?

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

14
00:00:51,370 --> 00:00:54,245
Dobře, a kolik z vás
mají počítače, které jsou zranitelné?

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

16
00:00:55,680 --> 00:01:00,250
OK, měl by tam být daleko, daleko více rukou
právě teď, z důvodů, které jsou vidět.

17
00:01:00,250 --> 00:01:02,580
>> Pojďme se podívat na to, co je
se děje v médiích

18
00:01:02,580 --> 00:01:05,304
A pak se to trochu vysvětlit
pro nás technicky.

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

20
00:01:07,670 --> 00:01:11,250
>> SPEAKER 2: Bezpečnostní experti mají
varoval, že vážná chyba by mohla

21
00:01:11,250 --> 00:01:15,650
asi ovlivnit stovky
miliony světových internetových uživatelů.

22
00:01:15,650 --> 00:01:20,600
Takže co přesně je chyba, že to bylo
daboval Shellshock, a co to dělá?

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

24
00:01:23,720 --> 00:01:28,910
No, Shellshock je také známý jako
Bash chyba, software je využívá.

25
00:01:28,910 --> 00:01:33,230
Hackeři používají virus skenování zranitelné
systémy běží Linux a Unix

26
00:01:33,230 --> 00:01:36,300
operační systémy a infikovat je.

27
00:01:36,300 --> 00:01:38,730
Bash je příkazový řádek shellu.

28
00:01:38,730 --> 00:01:43,460
To umožňuje uživatelům vydávat příkazy ke spuštění
programy a funkce v softwaru

29
00:01:43,460 --> 00:01:45,250
zadáním textu.

30
00:01:45,250 --> 00:01:49,980
To je obvykle používán programátory a
by neměla být otevřena vůči okolnímu světu,

31
00:01:49,980 --> 00:01:51,590
když Shellshock změny, které.

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

33
00:01:54,160 --> 00:01:57,910
>> No, worringly, někteří analytici
varují, že může být větší hrozbou,

34
00:01:57,910 --> 00:02:01,580
protože Shellshock umožňuje kompletní
ovládání infikovaného stroje,

35
00:02:01,580 --> 00:02:06,030
vzhledem k tomu, Heartbleed povoleno pouze
hackeři špehovat na počítačích.

36
00:02:06,030 --> 00:02:09,130
Je to tak vážné, že je to
byla hodnocena v 10 z 10

37
00:02:09,130 --> 00:02:11,900
k závažnosti podle vnitrostátních
Databáze zranitelnost.

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

39
00:02:15,530 --> 00:02:20,015
2/3 ze všech webových serverů jsou
rizik, včetně některých počítačích se systémem Mac.

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

41
00:02:22,760 --> 00:02:25,600
No, ujistěte se, že
opravit své systémy nyní.

42
00:02:25,600 --> 00:02:29,330
Každý hosting webových stránek v chodu
postižené operační systémy

43
00:02:29,330 --> 00:02:31,800
by měly přijmout opatření co nejdříve.

44
00:02:31,800 --> 00:02:35,390
Každý, kdo si může dovolit to mělo vypadat
jejich sledování a webové aplikace

45
00:02:35,390 --> 00:02:37,355
firewally dávat pozor na případné útoky.

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

47
00:02:39,979 --> 00:02:41,770
SPEAKER 3: Nejhorší věc
že by se mohlo stát, je

48
00:02:41,770 --> 00:02:45,080
že by někdo napsat kód, který
se automaticky přepne a skenování

49
00:02:45,080 --> 00:02:48,280
internet a bude mít vliv na
všech těchto počítačů.

50
00:02:48,280 --> 00:02:50,710
A když to dělají dobře,
Nejhorší věc, kterou mohl udělat

51
00:02:50,710 --> 00:02:53,300
je jen odstranit vše,
nebo zavřel místa dolů.

52
00:02:53,300 --> 00:02:55,360
Takže jsme mohli vidět poškození
z tohoto úhlu pohledu,

53
00:02:55,360 --> 00:02:58,300
kde budeme mít škodlivé lidí
kteří se jen rozhodnout, že způsobí katastrofu

54
00:02:58,300 --> 00:03:02,534
tím, že systémy, dolů nebo odstranění
soubory, a podobné věci.

55
00:03:02,534 --> 00:03:05,200
SPEAKER 2: Někteří říkají, že je to jeden
z nejobtížnějších měřit

56
00:03:05,200 --> 00:03:08,080
chyby v letech, a to
může trvat týdny nebo dokonce

57
00:03:08,080 --> 00:03:10,820
měsíců k určení jeho konečného dopadu.

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

59
00:03:12,180 --> 00:03:15,560
>> SPEAKER 1: Takže všechno je to pravda,
ale legrační věc je, téměř všechny

60
00:03:15,560 --> 00:03:18,330
Užívání metafor jste právě viděli,
s výjimkou snad klávesnici,

61
00:03:18,330 --> 00:03:20,930
nemá nic společného s
bug vůbec.

62
00:03:20,930 --> 00:03:23,960
Servery a dráty a tak dále,
je to trochu tangenciálně souvisejících

63
00:03:23,960 --> 00:03:27,410
ale v jádru je to vlastně docela
zná to, co se tady děje.

64
00:03:27,410 --> 00:03:30,050
Ve skutečnosti, nechte mě jít do
naše CS50 spotřebiče.

65
00:03:30,050 --> 00:03:32,910
Nech mě jít napřed a maximalizovat
okno terminálu zde.

66
00:03:32,910 --> 00:03:36,020
A vy jste pomocí tohoto,
nebo vložený verze této smlouvy,

67
00:03:36,020 --> 00:03:39,460
v gedit, aby se psát programy,
typ příkazy, a tak dále,

68
00:03:39,460 --> 00:03:43,690
a to je ve skutečnosti, a má
už několik týdnů, Bash, B-A-S-H.

69
00:03:43,690 --> 00:03:46,890
To je Bourne-again shell,
což je jen ozdobný způsob, jak říkat,

70
00:03:46,890 --> 00:03:50,220
To je program, který má
blikání rychlé, efektivní,

71
00:03:50,220 --> 00:03:51,970
že sedí tam čeká
pro vstup pro vás.

72
00:03:51,970 --> 00:03:53,920
A je to příkaz
řádky, přes které

73
00:03:53,920 --> 00:03:57,650
vy jste byla spuštěna příkazů a
nakonec kompilaci a spuštěním

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

75
00:03:58,400 --> 00:04:01,320
>> Ale Bash je také programování
jazyk v následujícím smyslu.

76
00:04:01,320 --> 00:04:05,460
Víte, že existují příkazy, jako je
cd a ls i zvonit a další,

77
00:04:05,460 --> 00:04:09,580
ale můžete definovat vlastní příkazy
od jejich zavádění do Bash.

78
00:04:09,580 --> 00:04:11,420
Teď už nebudeme
jít do skvělého detailu

79
00:04:11,420 --> 00:04:16,089
jako Bash programovací jazyk, ale
Víte, například, že v současné době,

80
00:04:16,089 --> 00:04:17,607
tam žádný příkaz s názvem "Ahoj."

81
00:04:17,607 --> 00:04:19,440
Takže to lze nalézt v
jeden z těchto balíčků.

82
00:04:19,440 --> 00:04:20,856
Není nainstalován na mém počítači.

83
00:04:20,856 --> 00:04:21,870
Zeptejte se na správce systému.

84
00:04:21,870 --> 00:04:26,030
Ale pokud chci tam být program
s názvem "ahoj" v bash nebo na mé výzvy,

85
00:04:26,030 --> 00:04:30,810
Mohu skutečně používat syntaxi, která je
docela jako C. Není to úplně stejné,

86
00:04:30,810 --> 00:04:35,020
ale vypadá to docela podobné
funkce, i když chybí některé detaily.

87
00:04:35,020 --> 00:04:38,090
Se zdánlivě nic neděje,
ale teď když jsem napsat "ahoj"

88
00:04:38,090 --> 00:04:40,960
, můžete vytvořit
programu, a to v jazyce C, a to v jazyce Java,

89
00:04:40,960 --> 00:04:44,280
ne v jiném programování
jazyk, ale v Bash sám.

90
00:04:44,280 --> 00:04:47,630
>> Nyní je zde klíčové je, že jsem napsal
Jméno Chtěl jsem, aby tento nový příkaz,

91
00:04:47,630 --> 00:04:50,820
a závorky jsou také
symbolický což je funkce.

92
00:04:50,820 --> 00:04:54,010
Mimochodem, můžete si také udělat legraci
věci, a ve skutečnosti, a to i na Mac OS,

93
00:04:54,010 --> 00:04:55,620
To je program s názvem Terminal.

94
00:04:55,620 --> 00:04:58,800
Je dodáván vestavěný do kohokoli
počítač, který má Mac v této místnosti,

95
00:04:58,800 --> 00:05:03,640
a můžete dělat podobné věci v Mac
OS, ale můžete jít víc než to.

96
00:05:03,640 --> 00:05:07,110
A to je trochu tangenciální,
ale je to docela legrace.

97
00:05:07,110 --> 00:05:09,715
Připomněl jsem si dnes ráno,
když myslí si, díky,

98
00:05:09,715 --> 00:05:13,279
na malou hru jsem hrával
s jedním z CS50 bývalých TFs

99
00:05:13,279 --> 00:05:16,570
kdy kdykoli by odejít z
Jeho klávesnice s jeho obrazovku odemknout,

100
00:05:16,570 --> 00:05:23,611
Já bych spustit příkaz
jako tohle-- "pozdravit."

101
00:05:23,611 --> 00:05:26,610
A teď nějaký čas se vrátil k jeho
klávesnice, co jsem vyčistil obrazovku

102
00:05:26,610 --> 00:05:27,985
a on by si sednout,
pokusit se udělat nějakou práci,

103
00:05:27,985 --> 00:05:29,250
vypsat obsah jeho directory--

104
00:05:29,250 --> 00:05:29,510
>> [Přehrávání zvuku]

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

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

107
00:05:31,621 --> 00:05:32,120
Dobrý den.

108
00:05:32,120 --> 00:05:35,030
>> SPEAKER 1: Takže, v spravedlnosti,
to není ve skutečnosti "ahoj."

109
00:05:35,030 --> 00:05:36,894
Bylo to obvykle něco
více podobný že--

110
00:05:36,894 --> 00:05:37,560
[Přehrávání zvuku]

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

112
00:05:37,750 --> 00:05:39,320
SPEAKER 1: začaly uznávat takzvané I would--
tak jeho počítač by

113
00:05:39,320 --> 00:05:42,170
nadávat na něj, kdykoli se mu vlastně
se posadil na jeho klávesnici.

114
00:05:42,170 --> 00:05:46,265
A velmi rychle přišel na to
nenechávat jeho obrazovka odemčena.

115
00:05:46,265 --> 00:05:48,730
Ale to naznačuje, že druh
z hloupé zábavy, která vás

116
00:05:48,730 --> 00:05:50,210
může mít něco jako Bash.

117
00:05:50,210 --> 00:05:52,770
Ale je to trochu víc
vážně, aby bylo jasno, než to.

118
00:05:52,770 --> 00:05:57,235
A ve skutečnosti, to je jeden z
nejnebezpečnější a dlouhotrvající chyby

119
00:05:57,235 --> 00:05:58,860
že opravdu zasáhla svět po celém světě.

120
00:05:58,860 --> 00:06:02,060
Tato chyba byla asi
pro asi 20 roků,

121
00:06:02,060 --> 00:06:05,780
a budete udeřil v několika
okamžik jeho relativní jednoduchost.

122
00:06:05,780 --> 00:06:07,990
>> Tak tohle je reprezentativní
příkaz, že pokud

123
00:06:07,990 --> 00:06:10,448
vlastní Mac, doslova hned
Když máte otevřené víko,

124
00:06:10,448 --> 00:06:12,940
můžete zkusit psát do toho
program s názvem Terminal.

125
00:06:12,940 --> 00:06:15,410
Terminál je pod
Aplikace Utilities--

126
00:06:15,410 --> 00:06:18,790
jednou, uživatelé Windows nemusíte
starat o tomto threat--

127
00:06:18,790 --> 00:06:22,310
ale ti z vás s počítači Mac můžete zadat
to do okna, jako to udělám tady,

128
00:06:22,310 --> 00:06:24,210
a pokud nechcete psát
že do tohoto programu

129
00:06:24,210 --> 00:06:28,830
Terminál, jako já budu dělat teď,
když vidíte slovo "zranitelný",

130
00:06:28,830 --> 00:06:32,200
váš počítač
náchylné k vykořisťování.

131
00:06:32,200 --> 00:06:33,850
>> Teď co to vlastně znamená?

132
00:06:33,850 --> 00:06:35,870
A to je pravda
někteří dost šílené syntax,

133
00:06:35,870 --> 00:06:39,050
ale pojďme alespoň vytáhnout
některé ze zajímavých aspektů.

134
00:06:39,050 --> 00:06:42,567
Takže tam je nějaká syntaxe, která vypadá
trochu zná, alespoň z C

135
00:06:42,567 --> 00:06:43,950
a programování obecně.

136
00:06:43,950 --> 00:06:47,550
Vidím nějaké závorky,
středníky, složené závorky, a takové,

137
00:06:47,550 --> 00:06:50,820
ale ukázalo se, že tento
hloupost zde ve žluté barvě

138
00:06:50,820 --> 00:06:53,580
je v podstatě funkce
že nedělá nic.

139
00:06:53,580 --> 00:06:57,840
Dvojtečka znamená nedělat nic, a
středník znamená přestat dělat nic.

140
00:06:57,840 --> 00:07:00,250
Takže uvnitř nich
složené závorky, skutečnost,

141
00:07:00,250 --> 00:07:02,440
že mám rovné
přihlásit se vlevo, to

142
00:07:02,440 --> 00:07:05,500
je v podstatě vytváří
příkaz, nebo proměnná,

143
00:07:05,500 --> 00:07:09,520
nazvaný x a přiřazením
ta žlutá část kódu tam.

144
00:07:09,520 --> 00:07:14,040
To by mohlo být něco jako "echo
ahoj "nebo" říkají pípnutí ", nebo tak něco

145
00:07:14,040 --> 00:07:15,120
podobný tomu.

146
00:07:15,120 --> 00:07:17,780
Povšimněme si ale, pokud vaše oči
dále putovat na pravé straně,

147
00:07:17,780 --> 00:07:22,150
tam je více k této čáře, než
jen konec této středníkem.

148
00:07:22,150 --> 00:07:25,160
"Echo zranitelný", a pak
Kromě toho je tu ještě víc.

149
00:07:25,160 --> 00:07:26,530
Další středník, bash-c :.

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

151
00:07:28,120 --> 00:07:34,050
>> Tak dlouhý příběh krátký,
tento řádek kódu je

152
00:07:34,050 --> 00:07:36,660
dostatečná pro přesvědčivé
Počítač, který je

153
00:07:36,660 --> 00:07:39,830
citlivé na něco
že chcete to dělat,

154
00:07:39,830 --> 00:07:44,290
protože tam je chyba v Bash, kdy
i když Bash měl zastavit

155
00:07:44,290 --> 00:07:48,980
čtení řádků příkazu vpravo
tam po žluté textu,

156
00:07:48,980 --> 00:07:52,520
na 20 a navíc rok stará chyba,
Bash skutečně četl

157
00:07:52,520 --> 00:07:56,780
po tomto středníkem a hezká
hodně dělá to, co je řečeno.

158
00:07:56,780 --> 00:07:59,070
>> Takže to, co je to důsledek
z toho nakonec?

159
00:07:59,070 --> 00:08:01,340
Jen jsem řekl, "echo ahoj"
nebo "echo zranitelné,"

160
00:08:01,340 --> 00:08:05,449
ale co když jste něco
ve skutečnosti škodlivý, jako rm -rf *

161
00:08:05,449 --> 00:08:07,240
které jste možná ne
kdy napsal dříve,

162
00:08:07,240 --> 00:08:08,920
a upřímně řečeno, pravděpodobně
neměli příliš brzy,

163
00:08:08,920 --> 00:08:10,700
protože můžete dělat
Mnoho škod s ním.

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

165
00:08:11,210 --> 00:08:12,990
rm co dělá, samozřejmě?

166
00:08:12,990 --> 00:08:14,270
Odstraňuje.

167
00:08:14,270 --> 00:08:15,930
* Znamená co?

168
00:08:15,930 --> 00:08:16,430
Vše.

169
00:08:16,430 --> 00:08:18,180
Takže je to tak-zvané
divoká karta, tak to znamená, že

170
00:08:18,180 --> 00:08:20,410
smazat vše
aktuální adresář.

171
00:08:20,410 --> 00:08:23,379
r se děje tak, že znamená rekurzivní,
což znamená, že pokud to, co jste smazání

172
00:08:23,379 --> 00:08:26,420
je adresář, a uvnitř tam
je další soubory a další adresáře,

173
00:08:26,420 --> 00:08:28,950
rekurzivně ponořit do ještě
a odstranit všechno.

174
00:08:28,950 --> 00:08:31,040
A f je nejhorší ze všech.

175
00:08:31,040 --> 00:08:32,580
Každý, kdo ví, co f zde znamená?

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
Takže nutit prostředky, a to i
jestli je to dobrý nápad,

179
00:08:37,830 --> 00:08:40,939
to aniž by mě výzva
Pro další potvrzení.

180
00:08:40,939 --> 00:08:43,230
Takže, víte, my smát
, ale upřímně řečeno, asi bych

181
00:08:43,230 --> 00:08:44,972
Tento typ vícekrát
den, protože skutečnosti

182
00:08:44,972 --> 00:08:47,210
je, že je to nejrychlejší způsob, jak
odstranit spoustu věcí.

183
00:08:47,210 --> 00:08:48,590
Ale i já jsem udělal nějakou škodu.

184
00:08:48,590 --> 00:08:53,100
>> Ale pokud jste byli na trik počítač
do definování nějaké stupidní proměnné

185
00:08:53,100 --> 00:08:56,810
nebo volání funkce x, ale pak
podvádět počítače do provádění

186
00:08:56,810 --> 00:09:00,030
za hranice, které
funkce nad rámec tohoto středníkem,

187
00:09:00,030 --> 00:09:04,430
můžete opravdu trik počítač
k vykonání něco jako rm -rf

188
00:09:04,430 --> 00:09:07,810
nebo příkaz E-mail
nebo příkaz Kopírovat.

189
00:09:07,810 --> 00:09:11,400
Cokoliv doslova můžete dělat s
počítač, ať už je to mazání souborů,

190
00:09:11,400 --> 00:09:15,350
vytváření souborů, spamy někoho,
útočí na nějaké serveru vzdáleně,

191
00:09:15,350 --> 00:09:17,190
pokud můžete vyjádřit
s příkazem, je

192
00:09:17,190 --> 00:09:19,120
může přimět počítač, aby dělali to.

193
00:09:19,120 --> 00:09:21,510
>> Teď, co je příklad
, jak by to mohlo dělat?

194
00:09:21,510 --> 00:09:24,300
No, je tu spousta počítačů
na internet tekoucí Bash.

195
00:09:24,300 --> 00:09:26,390
Všichni uživatelé, abychom Mac jsou mezi nimi.

196
00:09:26,390 --> 00:09:30,390
Mnoho linuxových serverů patří mezi
je také, a servery Unix.

197
00:09:30,390 --> 00:09:32,630
Windows opět dostane
relativně vyvěšený

198
00:09:32,630 --> 00:09:34,590
Pokud jste nainstalovali
speciální software.

199
00:09:34,590 --> 00:09:37,130
Teď hodně serverů, pro
instance, spustit webové servery,

200
00:09:37,130 --> 00:09:39,840
a ve skutečnosti Linux je možná
nejoblíbenější operační systém

201
00:09:39,840 --> 00:09:43,060
aby mohlo běžet na počítačích na internetu
které se servírují stránky.

202
00:09:43,060 --> 00:09:44,910
Nyní, jak uvidíme později,
v semestru, kdy

203
00:09:44,910 --> 00:09:48,470
odešlete žádost
Váš browser-- Chrome,

204
00:09:48,470 --> 00:09:50,790
Internet Explorer, whatever--
na vzdáleném serveru,

205
00:09:50,790 --> 00:09:53,730
Ukazuje se, že i když
jste právě zadali www.example.com,

206
00:09:53,730 --> 00:09:59,590
Váš prohlížeč odeslání zprávy
to je trochu tajemný, jako je tento.

207
00:09:59,590 --> 00:10:01,239
>> Ale všimněte si něco podivného.

208
00:10:01,239 --> 00:10:03,030
První dva řádky
Nikdy jsem neviděl,

209
00:10:03,030 --> 00:10:04,904
ale nevypadají
zvláště ohrožující.

210
00:10:04,904 --> 00:10:08,030
Ale všimněte, co jsem ukradl
na třetím řádku zde.

211
00:10:08,030 --> 00:10:13,390
Je-li špatný člověk měl poslat zprávu
takhle ze svého počítače

212
00:10:13,390 --> 00:10:17,270
na zranitelné Mac nebo
zranitelný server Linux,

213
00:10:17,270 --> 00:10:21,580
Legrační je, že Bash,
že jednoduchý malý příkazový řádek,

214
00:10:21,580 --> 00:10:27,450
je všudypřítomný a je často
použitý v podstatě provést

215
00:10:27,450 --> 00:10:30,020
obsah
zprávu, která se mu věnuje.

216
00:10:30,020 --> 00:10:33,490
A tím, že logika, můžete
trik webový server, proto,

217
00:10:33,490 --> 00:10:36,370
zasláním něco jako
User-Agent, který obvykle

218
00:10:36,370 --> 00:10:38,300
má říkat
název vašeho prohlížeče.

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

220
00:10:42,420 --> 00:10:44,590
je prostě váš prohlížeč je
způsob ztotožňuje.

221
00:10:44,590 --> 00:10:46,605
Ale když padouch velmi
chytře říká, mm-mm, já jsem

222
00:10:46,605 --> 00:10:47,930
Není ti to říct
co můj prohlížeč,

223
00:10:47,930 --> 00:10:50,888
Já místo toho bude ti to poslat
mystický vypadající věc s rm -rf

224
00:10:50,888 --> 00:10:55,840
* V ní můžete doslova trik
zranitelné webový server na internetu

225
00:10:55,840 --> 00:10:59,055
v provedení přesně, že v
tam pro smazání všech souborů.

226
00:10:59,055 --> 00:11:00,930
A upřímně řečeno, to není
i to nejhorší.

227
00:11:00,930 --> 00:11:01,763
Můžete dělat cokoliv.

228
00:11:01,763 --> 00:11:04,480
Dalo by se začít distribuované
odmítnutí služby útoku

229
00:11:04,480 --> 00:11:07,030
pokud jsi poslal tuto zprávu
celé svazky webových serverů

230
00:11:07,030 --> 00:11:10,256
a pak nechal všechny sestoupit, pro
instance na serverech Harvard.edu,

231
00:11:10,256 --> 00:11:12,130
a můžete seřadit Bang
sakra z nich

232
00:11:12,130 --> 00:11:15,490
o provozu na síti, který byl
jinak vyvolána tímto špatný chlap.

233
00:11:15,490 --> 00:11:18,760
>> Tak dlouhý příběh krátký, téměř
všichni v této místnosti, kdo vlastní Mac

234
00:11:18,760 --> 00:11:20,240
Je citlivá na to.

235
00:11:20,240 --> 00:11:24,100
Dobrou zprávou je, že pokud jste
běží webový server na vašem notebooku,

236
00:11:24,100 --> 00:11:27,780
a pokud jste skutečně nakonfigurován
to, aby něco takového SSH do toho,

237
00:11:27,780 --> 00:11:28,670
jste opravdu v bezpečí.

238
00:11:28,670 --> 00:11:31,710
To je zranitelný, ale není
kdo se snaží dostat do vašeho notebooku,

239
00:11:31,710 --> 00:11:33,290
takže můžete trochu jisti.

240
00:11:33,290 --> 00:11:36,210
Nicméně, Apple brzy
bude aktualizovat opravu to.

241
00:11:36,210 --> 00:11:39,660
Svět Linuxu již vydala
počet oprav pro Fedora a Ubuntu

242
00:11:39,660 --> 00:11:43,790
a další verze Linux, a opravdu
Pokud spustíte aktualizaci 50 v zařízení,

243
00:11:43,790 --> 00:11:45,930
dokonce, že taky bude
aktualizována a opravena.

244
00:11:45,930 --> 00:11:47,764
Že ale příliš nemá
opravdu byl zranitelný,

245
00:11:47,764 --> 00:11:49,804
protože pokud jste
pohráli si se spotřebičem

246
00:11:49,804 --> 00:11:52,770
a dělal váš notebook veřejně
dostupné na internetu, což není

247
00:11:52,770 --> 00:11:54,910
Ve výchozím nastavení, vy jste
ve skutečnosti bylo v pořádku, protože

248
00:11:54,910 --> 00:11:56,890
z firewall a dalších technik.

249
00:11:56,890 --> 00:12:01,000
>> Ale je to extrémní příklad chyby
že jsme žili za doslova 20

250
00:12:01,000 --> 00:12:04,050
let, a kdo ví, jestli se někdo
Celou tu dobu se ví o tom?

251
00:12:04,050 --> 00:12:06,300
A ve skutečnosti, to je jeden z
základní problémy

252
00:12:06,300 --> 00:12:08,690
že uvidíme později
semestr o bezpečnost,

253
00:12:08,690 --> 00:12:13,020
je to, že stejně jako v reálném světě,
dobří jsou v nevýhodě.

254
00:12:13,020 --> 00:12:16,500
Chcete-li zachovat padouchy ven, musíme
Ujistěte se, že všechny dveře jsou zamčené,

255
00:12:16,500 --> 00:12:20,340
že každé okno je bezpečný, že
každý bod vstupu do domu

256
00:12:20,340 --> 00:12:21,980
je bezpečný, aby padouchy ven.

257
00:12:21,980 --> 00:12:26,870
Ale to, co dělá špatný člověk musí
to skutečně ohrozit váš domov

258
00:12:26,870 --> 00:12:28,200
a krást od vás?

259
00:12:28,200 --> 00:12:32,574
On nebo ona prostě musí najít ten, odemčený
dveře, jeden rozbité okno, nebo tak něco

260
00:12:32,574 --> 00:12:35,240
v tomto směru, a to je
Totéž se v oblasti počítačové bezpečnosti.

261
00:12:35,240 --> 00:12:37,660
Můžeme psát miliony
řádky programového kódu

262
00:12:37,660 --> 00:12:40,570
a utrácet stovky nebo tisíce
hodin, se snaží, aby si to v pořádku,

263
00:12:40,570 --> 00:12:43,370
ale pokud uděláte jen jeden
chyba ve správnosti,

264
00:12:43,370 --> 00:12:47,030
si můžete dát celý systém a
skutečně v tomto případě celý internet

265
00:12:47,030 --> 00:12:48,660
a svět v ohrožení.

266
00:12:48,660 --> 00:12:51,950
>> Takže pokud byste se chtěli dozvědět více
o tom, přejděte na následující adresu zde.

267
00:12:51,950 --> 00:12:54,450
Není třeba akci
dnes večer, pokud jste

268
00:12:54,450 --> 00:12:57,116
mezi ty klidnější, že
Byly běží vlastní web

269
00:12:57,116 --> 00:12:59,810
serveru, v tom případě byste měli,
ve skutečnosti, aktualizovat software.

270
00:12:59,810 --> 00:13:03,244
>> I to je název
řeč, a nyní papír,

271
00:13:03,244 --> 00:13:05,410
že jsme svázána
Webové stránky hřiště je pro dnešek vše.

272
00:13:05,410 --> 00:13:07,600
Bylo by kolegy
jmenoval Ken Thompson, který

273
00:13:07,600 --> 00:13:10,120
bylo přijetí velmi slavný
Ocenění ve vědě o počítačích,

274
00:13:10,120 --> 00:13:13,495
a dal tuto řeč o několik let
Před podstatě na stejné téma.

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

276
00:13:18,250 --> 00:13:20,520
Žádat lidi otázka,
měli byste opravdu

277
00:13:20,520 --> 00:13:23,480
důvěra, nakonec,
Software, který jste dostali?

278
00:13:23,480 --> 00:13:26,100
Například, my všichni máme
bylo psaní programů,

279
00:13:26,100 --> 00:13:27,820
a my jsme byli sestavování
je s Clang.

280
00:13:27,820 --> 00:13:31,830
A své znalosti, jste napsal
všechny programy pro CS50 tam, kde je

281
00:13:31,830 --> 00:13:35,310
zadní dveře druhů, existuje způsob, jak
že padouch, pokud běží program,

282
00:13:35,310 --> 00:13:37,410
mohl převzít vašem počítači?

283
00:13:37,410 --> 00:13:38,310
Asi ne, že jo?

284
00:13:38,310 --> 00:13:40,180
Mario a Greedy a Credit.

285
00:13:40,180 --> 00:13:41,680
To vše jsou docela malé programy.

286
00:13:41,680 --> 00:13:43,910
Musel byste být dost
špatné, pokud jste skutečně

287
00:13:43,910 --> 00:13:47,310
dělal celý počítač zranitelný
po napsání 10 nebo 20 řádků kódu,

288
00:13:47,310 --> 00:13:49,690
nebo alespoň vědomi některých
bezpečnostních důsledků.

289
00:13:49,690 --> 00:13:52,023
Teď říkám, že bodře,
ale budeme vidět dnes

290
00:13:52,023 --> 00:13:54,600
a tento týden je to vlastně
opravdu, ale opravdu snadné

291
00:13:54,600 --> 00:13:57,980
být špatný, a aby ještě
krátké programy zranitelné.

292
00:13:57,980 --> 00:14:02,880
>> Ale teď, alespoň si uvědomit,
že tato otázka je sem pozval

293
00:14:02,880 --> 00:14:04,850
je o Clang v kompilátoru.

294
00:14:04,850 --> 00:14:08,360
Proč jsme se věřit zvonění
za poslední dva nebo tři týdny?

295
00:14:08,360 --> 00:14:12,650
Kdo může říci, že ten, kdo psal zvonění
neměl "kdyby" podmínku, že

296
00:14:12,650 --> 00:14:17,680
že v podstatě injekčně nějaké nuly
a ty do každého programu, sestavuje

297
00:14:17,680 --> 00:14:21,180
že by ho nechal, nebo její přístup
počítač, když jsi spal

298
00:14:21,180 --> 00:14:23,580
a vaše víko notebooku je otevřena
a počítač se systémem?

299
00:14:23,580 --> 00:14:24,080
Je to tak?

300
00:14:24,080 --> 00:14:28,350
Máme tento druh čest systému práva
Nyní, pokud věříme, že Clang je důvěryhodně.

301
00:14:28,350 --> 00:14:30,000
Věříte, že spotřebič je důvěryhodně.

302
00:14:30,000 --> 00:14:34,430
Věříte, že doslova každý program,
na počítači Mac nebo PC je důvěryhodný.

303
00:14:34,430 --> 00:14:37,510
A jak tento jednoduchý chyba naznačuje,
i když to není škodlivý,

304
00:14:37,510 --> 00:14:40,580
to rozhodně není
pravděpodobné, že tomu tak je.

305
00:14:40,580 --> 00:14:42,350
>> Takže byste měli bát jako čert.

306
00:14:42,350 --> 00:14:45,560
Upřímně řečeno, není jednoduché
Roztok se tento druhý

307
00:14:45,560 --> 00:14:48,185
než jakési společenské povědomí
z rostoucí složitosti

308
00:14:48,185 --> 00:14:50,310
že stavíme na vrcholu
našich počítačových systémů,

309
00:14:50,310 --> 00:14:53,740
a jak se stále více zranitelnější
bychom mohli být docela dobře.

310
00:14:53,740 --> 00:14:55,570
>> Nyní se, že řekl, Breakout.

311
00:14:55,570 --> 00:14:59,889
Takže Breakout je problém nastavit tři a
Breakout je hra z dávných dob

312
00:14:59,889 --> 00:15:02,180
které by vás mohly vyvolat, ale
pro nás problém nastavit tři,

313
00:15:02,180 --> 00:15:04,450
to nám umožňuje, aby se
věci zpět do zářezu

314
00:15:04,450 --> 00:15:08,880
tak, že když píšeme programy,
i v terminálovém okně, jako je tento,

315
00:15:08,880 --> 00:15:14,670
můžeme skutečně spustit, nakonec,
grafické programy ne

316
00:15:14,670 --> 00:15:17,800
Na rozdíl od těch, které jsme měli
přístup v Scratch.

317
00:15:17,800 --> 00:15:20,910
Tak tohle je na zaměstnance je
realizace Breakout,

318
00:15:20,910 --> 00:15:23,930
což je právě tato cihla-lámání
hra, že se pohybujete pádlo zpět

319
00:15:23,930 --> 00:15:27,590
a tam, a odpálil míček
před těmi barevnými cihlami až nahoře.

320
00:15:27,590 --> 00:15:30,020
Takže to je, že nás
trochu zpátky tam, kde

321
00:15:30,020 --> 00:15:33,180
jsme byli schopni se velmi rychle
Scratch, a teď s C,

322
00:15:33,180 --> 00:15:35,800
, kterým se provádí vlastní
grafická uživatelská rozhraní.

323
00:15:35,800 --> 00:15:38,960
>> Ale víc než to, že tento
Problém set představuje první

324
00:15:38,960 --> 00:15:41,000
ve které dáváme
Jste banda kódu.

325
00:15:41,000 --> 00:15:43,940
A ve skutečnosti, já uvedu explicitní
pozornost na to, protože zejména

326
00:15:43,940 --> 00:15:47,090
Pro ty méně příjemné, to
problém nastavit, alespoň na první pohled,

327
00:15:47,090 --> 00:15:49,170
se bude cítit jako
udělali jsme ji do zářezu.

328
00:15:49,170 --> 00:15:51,540
Vzhledem k tomu, že jsme vám dal,
Pro některé z hledání

329
00:15:51,540 --> 00:15:54,930
a třídění problémy v pset,
banda kódu, který jsme napsali,

330
00:15:54,930 --> 00:15:56,680
a pár komentářů
které říkají "dělat,"

331
00:15:56,680 --> 00:15:58,221
kde budete muset vyplnit prázdná místa.

332
00:15:58,221 --> 00:16:00,020
Takže ne příliš děsivé, ale
je to poprvé,

333
00:16:00,020 --> 00:16:03,370
jsme podal vám kód, který je třeba
nejprve přečíst, pochopit a pak se přidají do

334
00:16:03,370 --> 00:16:04,290
a dokončit ji.

335
00:16:04,290 --> 00:16:05,940
>> A pak Breakout,
budeme dělat totéž,

336
00:16:05,940 --> 00:16:08,740
která vám několik desítek více linek
kódu, který, upřímně řečeno, aby vám

337
00:16:08,740 --> 00:16:11,490
hodně rámce pro
hra, ale zastavit před

338
00:16:11,490 --> 00:16:14,304
prováděcích cihly
a míč a pádlo,

339
00:16:14,304 --> 00:16:15,970
ale my realizovat některé další funkce.

340
00:16:15,970 --> 00:16:18,280
A dokonce, že na první pohled, znovu,
zejména v případě méně pohodlné,

341
00:16:18,280 --> 00:16:21,480
Mohlo by se zdát obzvláště skličující a
si myslíte, že je tak mnoho nových funkcí

342
00:16:21,480 --> 00:16:24,070
budete muset zabalit svou mysl
kolem, a je to pravda.

343
00:16:24,070 --> 00:16:26,281
Ale mějte na paměti, že je to
docela jako Scratch.

344
00:16:26,281 --> 00:16:28,780
Kurz jste nepoužili všechny
že kousky skládačky na začátku.

345
00:16:28,780 --> 00:16:31,120
Kurz jste se nestaral zabalit
vaše mysl asi všichni

346
00:16:31,120 --> 00:16:33,617
protože vše, co se to
Letmý pohled pochopit, oh,

347
00:16:33,617 --> 00:16:35,450
že to, co se dá dělat
s tímto kousek puzzle.

348
00:16:35,450 --> 00:16:38,260
A skutečně, v problému nastavení
3 spec, budeme bod,

349
00:16:38,260 --> 00:16:41,370
v dokumentaci, která bude
Představujeme Vám některých nových funkcí,

350
00:16:41,370 --> 00:16:43,570
a nakonec programování
konstruuje, který používáte.

351
00:16:43,570 --> 00:16:47,610
Podmínky, smyčky,
proměnné a funkce

352
00:16:47,610 --> 00:16:50,720
bude stejná jako
to, co jsme viděli doposud.

353
00:16:50,720 --> 00:16:53,560
>> Takže opravdu, co dáme
vám je nějaký ukázkový kód, který

354
00:16:53,560 --> 00:16:56,110
vám umožní vytvořit okno
který vypadá ne na rozdíl od toho

355
00:16:56,110 --> 00:16:59,540
a nakonec přeměnit ji na
něco takového, jako toto.

356
00:16:59,540 --> 00:17:02,250
Takže využít CS50,
diskutovat úřední hodiny a více,

357
00:17:02,250 --> 00:17:05,290
a útěchu v tom, že
množství kódu musíte napsat

358
00:17:05,290 --> 00:17:06,760
ve skutečnosti není tak moc.

359
00:17:06,760 --> 00:17:10,359
Prvním úkolem je jen aklimatizovat
sami nějaký kód jsme napsali.

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

361
00:17:11,450 --> 00:17:15,810
>> Jakékoliv dotazy týkající se pset3,
Shellshock, nebo jinak?

362
00:17:15,810 --> 00:17:19,226
>> Diváků: Zdálo se, že
prochází s Breakout

363
00:17:19,226 --> 00:17:22,154
že kód je téměř
objektově-orientovaný styl,

364
00:17:22,154 --> 00:17:24,675
ale myslím, že C je
objektově-orientovaný program.

365
00:17:24,675 --> 00:17:26,050
SPEAKER 1: výborná otázka.

366
00:17:26,050 --> 00:17:28,258
Takže při pohledu přes
distribuce kód, kód

367
00:17:28,258 --> 00:17:30,180
jsme napsali pro pset3,
Pro ty, kteří znají, ho

368
00:17:30,180 --> 00:17:32,230
Vypadá to, že je to
trochu objektově-orientovaný.

369
00:17:32,230 --> 00:17:33,800
Stručná odpověď je, že to je.

370
00:17:33,800 --> 00:17:38,130
Je to přiblížení na to, jak
mohli dělat objektově-orientovaný kód pomocí

371
00:17:38,130 --> 00:17:41,850
jazyk C, ale to je
ještě nakonec procedurální.

372
00:17:41,850 --> 00:17:44,900
Tam jsou umístěny uvnitř žádné metody
proměnné, jak uvidíte.

373
00:17:44,900 --> 00:17:46,180
Ale připomíná to.

374
00:17:46,180 --> 00:17:48,780
A uvidíme, tuto funkci znovu
až se dostaneme do PHP a JavaScript

375
00:17:48,780 --> 00:17:49,946
ke konci semestru.

376
00:17:49,946 --> 00:17:53,667
Ale teď, myslím, že na to, jak
náznak toho, co je přijde.

377
00:17:53,667 --> 00:17:54,250
Dobrá otázka.

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

379
00:17:56,051 --> 00:17:56,550
V pořádku.

380
00:17:56,550 --> 00:17:59,730
Takže sloučení trochu bylo, jak jsme se
levá věci minule.

381
00:17:59,730 --> 00:18:03,250
A sloučit druh byl cool in
pocit, že je to tak mnohem rychlejší,

382
00:18:03,250 --> 00:18:07,100
alespoň na základě zběžné testy
jsme dělali minulý týden, než, řekněme, bublina

383
00:18:07,100 --> 00:18:08,710
třídění, výběr třídění, vkládání sort.

384
00:18:08,710 --> 00:18:11,780
A to, co bylo hezké i jen
jak stručně a čistě

385
00:18:11,780 --> 00:18:12,810
můžete vyjádřit.

386
00:18:12,810 --> 00:18:15,840
A to, co jsme si řekli, že je to horní
vázán na běžící čas sloučení

387
00:18:15,840 --> 00:18:16,340
třídit?

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

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

390
00:18:18,495 --> 00:18:19,360
>> Diváků: n log n?

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

392
00:18:20,819 --> 00:18:23,776
A vrátíme se k tomu, co to
ve skutečnosti znamená, nebo kde to pochází,

393
00:18:23,776 --> 00:18:25,570
ale toto bylo lepší
než jaké doby chodu

394
00:18:25,570 --> 00:18:28,440
které jsme viděli na bubliny
Výběr a vkládání třídit?

395
00:18:28,440 --> 00:18:30,610
Tak n na druhou. n na druhou
je větší než to,

396
00:18:30,610 --> 00:18:34,650
A i když to není zcela zřejmé,
vím, že log n je menší než n,

397
00:18:34,650 --> 00:18:36,910
takže pokud to n-krát
něco menší než n,

398
00:18:36,910 --> 00:18:38,680
že to bude menší než n na druhou.

399
00:18:38,680 --> 00:18:40,130
Je to trochu intuice tam.

400
00:18:40,130 --> 00:18:42,190
Ale my jsme zaplatili cenu za to.

401
00:18:42,190 --> 00:18:47,000
Bylo to rychlejší, ale téma, které začalo
objevovat minulý týden byl tento kompromis.

402
00:18:47,000 --> 00:18:49,804
Mám lepší výkon
Čas moudrý, ale to, co

403
00:18:49,804 --> 00:18:52,470
jsem musel strávit na straně druhé
ruce, aby bylo dosaženo, že?

404
00:18:52,470 --> 00:18:53,591
>> DIVÁKŮ: Memory.

405
00:18:53,591 --> 00:18:54,465
SPEAKER 1: Cože?

406
00:18:54,465 --> 00:18:55,173
DIVÁKŮ: Memory.

407
00:18:55,173 --> 00:18:57,040
SPEAKER 1: Paměti, nebo
místo obecně.

408
00:18:57,040 --> 00:18:59,040
A nebylo to výborný
zřejmé, s našimi lidmi,

409
00:18:59,040 --> 00:19:02,240
ale připomenout, že naše dobrovolníky
byly vykročil vpřed a posílení

410
00:19:02,240 --> 00:19:04,780
zpět, i když tam je pole
tady, a jako by to

411
00:19:04,780 --> 00:19:07,130
Druhá pole, které zde
by mohly využít, protože jsme

412
00:19:07,130 --> 00:19:09,080
Potřebné někde sloučit ty lidi.

413
00:19:09,080 --> 00:19:11,480
Nemohli jsme jen vyměnit je na místě.

414
00:19:11,480 --> 00:19:13,800
Takže sloučit třídění vliv
je prostor, který

415
00:19:13,800 --> 00:19:15,620
nemuseli jsme se
další algoritmy,

416
00:19:15,620 --> 00:19:17,410
ale Výhodou je, že je to mnohem rychlejší.

417
00:19:17,410 --> 00:19:20,780
A upřímně řečeno, v reálném světě prostoru
Tyto days-- RAM, pevný disk space--

418
00:19:20,780 --> 00:19:25,030
je relativně levné, a tak to je
není nutně špatná věc.

419
00:19:25,030 --> 00:19:28,320
>> Takže pojďme se rychle podívat, trochu
více metodicky, na to, co jsme udělali

420
00:19:28,320 --> 00:19:30,220
a proč řekl, že je n log n.

421
00:19:30,220 --> 00:19:33,260
Tak tady je osm čísel a
Osm dobrovolníků jsme měli minule.

422
00:19:33,260 --> 00:19:35,718
A první věc, která Sloučit
Seřadit nám řekl, dělat to, co?

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

424
00:19:37,010 --> 00:19:38,010
Diváků: Rozdělit na dvě části.

425
00:19:38,010 --> 00:19:38,663
SPEAKER 1: Cože?

426
00:19:38,663 --> 00:19:39,650
Diváků: Rozdělit na dvě části.

427
00:19:39,650 --> 00:19:40,610
SPEAKER 1: Rozdělte na dvě části, vpravo.

428
00:19:40,610 --> 00:19:42,818
To je velmi připomíná
telefonní seznam, rozděl

429
00:19:42,818 --> 00:19:44,220
a dobýt obecněji.

430
00:19:44,220 --> 00:19:45,640
Takže jsme se podívali na levé polovině.

431
00:19:45,640 --> 00:19:48,700
A pak jednou jsme si řekli, třídění
levá polovina z prvků,

432
00:19:48,700 --> 00:19:49,690
co jsme další říci?

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

434
00:19:51,210 --> 00:19:54,860
Seřadit levou polovinu vlevo
polovina, která nám umožnila,

435
00:19:54,860 --> 00:19:57,570
Po rozdělení na dvě části,
zaměřit se na čtyři a dvě.

436
00:19:57,570 --> 00:20:01,280
>> Jak seřadit seznam nyní,
žlutá, velikosti dvou, pomocí Merge Sort?

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

438
00:20:02,330 --> 00:20:04,580
No rozdělit jej na polovinu,
a seřadit levou polovinu.

439
00:20:04,580 --> 00:20:07,100
A to bylo místo, kde se věci
mám trochu hloupý krátce.

440
00:20:07,100 --> 00:20:10,720
Jak seřadit seznam, který je z
velikost jednoho, jako tady toto číslo čtyři?

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

442
00:20:12,330 --> 00:20:13,210
Je řazeny.

443
00:20:13,210 --> 00:20:14,200
Máte hotovo.

444
00:20:14,200 --> 00:20:17,300
>> Ale jak si seřadit seznam
Velikost jednoho, když je to číslo dvě?

445
00:20:17,300 --> 00:20:21,640
No, to samé, ale nyní to, co bylo
Třetím a klíčovým krokem při sloučení Seřadit?

446
00:20:21,640 --> 00:20:24,020
Vy jste měli sloučit levé
polovina a pravou polovinu.

447
00:20:24,020 --> 00:20:26,580
A jakmile jsme udělali, že jsme se zaměřili
ve čtyři jsme se zaměřili na dvě.

448
00:20:26,580 --> 00:20:28,750
Rozhodli jsme se v pořádku,
zřejmě dva je na prvním místě,

449
00:20:28,750 --> 00:20:31,840
tak jsme dali dva ve své
místo, následuje čtyři.

450
00:20:31,840 --> 00:20:35,010
A teď jste si na trochu vzad,
a to je druh charakteristiky

451
00:20:35,010 --> 00:20:37,570
algoritmu, jako je korespondence
Třídit vzad v paměti.

452
00:20:37,570 --> 00:20:40,240
Jaký byl další linie příběhu?

453
00:20:40,240 --> 00:20:41,780
Co bych měl zaměřit na další?

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

455
00:20:43,110 --> 00:20:47,350
Pravá polovina vlevo
polovina, což je šest a osm.

456
00:20:47,350 --> 00:20:50,320
>> Takže jen krok přes to
bez hašteřit bod příliš mnoho.

457
00:20:50,320 --> 00:20:53,330
Šest a osm, pak šest je
řazeny, osm je tříděn.

458
00:20:53,330 --> 00:20:57,190
Spojit je dohromady, jako to,
a teď další velký krok

459
00:20:57,190 --> 00:21:00,990
Je, samozřejmě, třídit pravou polovinu z
První krok tohoto algoritmu.

460
00:21:00,990 --> 00:21:02,870
Tak jsme se zaměřit na jeden, tři, sedm, pět.

461
00:21:02,870 --> 00:21:04,540
Dále se zaměřujeme na levé polovině.

462
00:21:04,540 --> 00:21:09,400
Levá polovina, že pravá polovina
že, a pak sloučit do jedné a tři.

463
00:21:09,400 --> 00:21:13,100
Pak pravou polovinu, potom levé polovině
ní, pak pravá polovina z nich.

464
00:21:13,100 --> 00:21:15,985
Sloučit ji, a co teď krok zůstává?

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

466
00:21:18,040 --> 00:21:22,460
Sloučit velký levé poloviny a velké
pravá polovina, takže se jde tam,

467
00:21:22,460 --> 00:21:27,330
pak dvě, pak tři, pak čtyři, pak
pět, šest a pak, pak sedm, pak osm.

468
00:21:27,330 --> 00:21:31,990
>> Takže teď, proč se to nakonec odhalí,
zejména v případě, n a logaritmy více

469
00:21:31,990 --> 00:21:35,487
obecně spíše útěk vás,
alespoň v nedávné paměti?

470
00:21:35,487 --> 00:21:37,070
Dobře si všimněte, výška této věci.

471
00:21:37,070 --> 00:21:41,230
Měli jsme osm prvků, a my jsme
dělí ji dvěma, dvěma, dvěma.

472
00:21:41,230 --> 00:21:44,590
Takže log základnu dva z osmi nám dává tři.

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

474
00:21:45,640 --> 00:21:48,540
A věř mi, že pokud na
trochu mlhavé na to.

475
00:21:48,540 --> 00:21:54,710
Ale přihlásit základ dvou z osmi jsou tři,
tak jsme udělali tři vrstvy sloučení.

476
00:21:54,710 --> 00:21:57,170
A když jsme sloučili
prvky, kolik elementů

477
00:21:57,170 --> 00:21:58,950
se podíváme na na každém z těchto řádků?

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

479
00:22:00,212 --> 00:22:01,437
Celkem n, ne?

480
00:22:01,437 --> 00:22:04,020
Vzhledem k tomu, sloučit horní řádek,
i když jsme to po částech,

481
00:22:04,020 --> 00:22:05,990
nakonec jsme kdysi dotkl každé číslo.

482
00:22:05,990 --> 00:22:09,054
A v druhé řadě, k
sloučení těchto seznamů velikosti dvou,

483
00:22:09,054 --> 00:22:10,470
jsme museli jednou dotknout každého prvku.

484
00:22:10,470 --> 00:22:12,690
A pak tu opravdu
jasně v poslední řadě,

485
00:22:12,690 --> 00:22:15,430
jsme se museli dotknout každého z nich
Prvky jednou, ale jen jednou,

486
00:22:15,430 --> 00:22:18,400
tak zde leží, pak se naše n log n.

487
00:22:18,400 --> 00:22:21,780
>> A teď jen aby se věci trochu
více formální jen na chvíli, pokud máte

488
00:22:21,780 --> 00:22:24,260
bylo nyní analyzovat toto
na jakési vyšší úrovni

489
00:22:24,260 --> 00:22:28,340
a pokusit se rozhodnout dobře, jak
může jít o vyjádření

490
00:22:28,340 --> 00:22:31,780
doba chodu tohoto algoritmu
jen při pohledu na něj, a ne

491
00:22:31,780 --> 00:22:33,590
pomocí spiklenecký příklad?

492
00:22:33,590 --> 00:22:36,590
No, kolik času byste řekli
krok jako je to v žluté bude trvat,

493
00:22:36,590 --> 00:22:37,173
pokud n <2 návrat?

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

495
00:22:38,840 --> 00:22:39,830
To je velký O co?

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

497
00:22:41,450 --> 00:22:44,540
Takže jsem viděl jednoho, tak jeden krok,
možná dva kroky, protože je to v případě,

498
00:22:44,540 --> 00:22:47,110
a pak se vrátit, ale je to
časová konstanta, ne?

499
00:22:47,110 --> 00:22:49,960
Tak jsme si řekli, O (1), a to
jak jsem si to vyjádřit.

500
00:22:49,960 --> 00:22:51,480
T, jen se běh času.

501
00:22:51,480 --> 00:22:54,150
n je velikost vstupu,
tak T (n), jen ozdobný způsob, jak

502
00:22:54,150 --> 00:22:56,330
říkat běh
čas vzhledem vstup velikosti n

503
00:22:56,330 --> 00:23:00,220
bude na objednávce
o konstantním čase, v O (1).

504
00:23:00,220 --> 00:23:01,970
>> Ale jinak, co tohle?

505
00:23:01,970 --> 00:23:05,660
Jak byste vyjádřit
doba chodu tohoto žlutou čárou?

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

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

508
00:23:09,440 --> 00:23:12,665
Můžete trochu podvádět tu a
odpověz na mou otázku cyklicky.

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

510
00:23:14,770 --> 00:23:17,900
Takže v případě, že čas běží v
Obecně jen říct, je T (n).

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

512
00:23:18,950 --> 00:23:22,490
A teď trochu plavit sem
říkal, no, prostě tak nějak levou polovinu,

513
00:23:22,490 --> 00:23:23,920
a pak třídit pravou polovinu.

514
00:23:23,920 --> 00:23:27,520
Jak můžeme symbolicky reprezentovat
doba chodu tohoto žlutou čárou?

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

516
00:23:28,020 --> 00:23:29,360
Jaká je velikost vstupu?

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

518
00:23:30,510 --> 00:23:31,057
n po dvou.

519
00:23:31,057 --> 00:23:32,140
Proč jsem jen říct, že?

520
00:23:32,140 --> 00:23:36,449
A pak je další T (n / 2) a pak
znovu, když jsem sloučit dva setříděné poloviny,

521
00:23:36,449 --> 00:23:38,615
kolik prvků jdu
muset dotknout všech?

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
Takže můžu vyjádřit to,
jen aby se trochu fantazie,

525
00:23:42,790 --> 00:23:44,430
jak čas běží obecně.

526
00:23:44,430 --> 00:23:51,140
T (n) je právě běžící čas T (n / 2),
Plus T (n / 2), vlevo polovina a pravou polovinu,

527
00:23:51,140 --> 00:23:55,360
Plus O (n), což je pravděpodobně n kroků,
ale možná, když jsem pomocí dvou prstů,

528
00:23:55,360 --> 00:23:57,960
to je dvakrát tolik
kroky, ale je to lineární.

529
00:23:57,960 --> 00:24:00,440
Je to nějaký počet kroků
To je faktor n,

530
00:24:00,440 --> 00:24:02,270
tak bychom mohli vyjádřit to, protože to.

531
00:24:02,270 --> 00:24:05,550
A to je místo, kde se budeme plavit na
zpět na naší střední školy z matematiky učebnici

532
00:24:05,550 --> 00:24:10,290
jsme, že opakování nakonec
skončí rovná to, n krát log n,

533
00:24:10,290 --> 00:24:12,530
pokud jste skutečně udělat z
matematika více formálně.

534
00:24:12,530 --> 00:24:13,950
>> Tak to je jen dva pohledy.

535
00:24:13,950 --> 00:24:17,500
Jeden s číselně
pevně reprezentativního příkladu

536
00:24:17,500 --> 00:24:21,140
pomocí osmi čísel a další
Obecně pohled na to, jak jsme se tam dostali.

537
00:24:21,140 --> 00:24:25,670
Ale co je opravdu zajímavé,
je opět tento pojem cyklistiky.

538
00:24:25,670 --> 00:24:26,900
Nejsem použitím smyček.

539
00:24:26,900 --> 00:24:29,860
Jsem trochu definování
něco ve smyslu sama o sobě,

540
00:24:29,860 --> 00:24:31,950
nejen s tímto
matematické funkce,

541
00:24:31,950 --> 00:24:34,860
ale také z hlediska tohoto pseudokódu.

542
00:24:34,860 --> 00:24:38,260
Tento kód pseudo rekurzivní
v tom, že dva ze svých linií

543
00:24:38,260 --> 00:24:42,310
je v podstatě říká to go
používají se k řešení menší

544
00:24:42,310 --> 00:24:45,400
Problém menší velikosti,
a pak znovu a znovu

545
00:24:45,400 --> 00:24:48,820
a znovu, dokud se nám to ořezávat
až do této takzvané referenční případ.

546
00:24:48,820 --> 00:24:52,810
>> Takže pojďme se vlastně nakreslit přesvědčivější
se-od to takto.

547
00:24:52,810 --> 00:24:58,420
Nech mě jít do gedit a vzít
podívejte se na některé z dnešního zdrojového kódu,

548
00:24:58,420 --> 00:24:59,930
zejména tento příklad zde.

549
00:24:59,930 --> 00:25:03,709
Sigma 0, který zřejmě dodává
čísla jedna až n.

550
00:25:03,709 --> 00:25:05,750
Takže pojďme se podívat, co je znají
a neznámé zde.

551
00:25:05,750 --> 00:25:08,690
Nejprve musíme pár
patří, takže nic nového tam.

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

553
00:25:09,190 --> 00:25:11,370
Jsem trochu zamlžený na
to po několika dnech,

554
00:25:11,370 --> 00:25:13,790
ale to, co jsme si řekli
Prototyp funkce je?

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

556
00:25:15,099 --> 00:25:16,015
Diváků: [neslyšitelné].

557
00:25:16,015 --> 00:25:16,905
SPEAKER 1: Co je to?

558
00:25:16,905 --> 00:25:17,800
Diváků: Oznamujeme to.

559
00:25:17,800 --> 00:25:18,883
SPEAKER 1: Oznamujeme to.

560
00:25:18,883 --> 00:25:22,290
Takže jste se učil zvonění, hej,
není ve skutečnosti provádění tohoto dosud,

561
00:25:22,290 --> 00:25:25,740
ale někde v tomto souboru, pravděpodobně,
se bude funkce volána, co?

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
A to je jen slib, že
bude to vypadat takto.

565
00:25:30,540 --> 00:25:33,720
Bude to trvat celé číslo jako
input-- a můžu být konkrétnější

566
00:25:33,720 --> 00:25:36,570
a říkají, int n --a, že je to
chystá vrátit int,

567
00:25:36,570 --> 00:25:39,900
ale středník znamená, mm, budu obejít
k provádění tohoto o něco později.

568
00:25:39,900 --> 00:25:40,989
Opět platí, že Clang je hloupý.

569
00:25:40,989 --> 00:25:43,280
Je to jen bude vědět, co
řeknete, že shora dolů,

570
00:25:43,280 --> 00:25:45,765
takže musíme dát alespoň
je to náznak toho, co je přijde.

571
00:25:45,765 --> 00:25:47,330
>> Nyní se podívejme na hlavní zde.

572
00:25:47,330 --> 00:25:50,040
Pojďme se procházet sem a
vidět, co hlavní dělá.

573
00:25:50,040 --> 00:25:53,780
Není to tak dlouho, funkce, a
ve skutečnosti zde konstrukt je obeznámen.

574
00:25:53,780 --> 00:25:57,590
Prohlašuji, proměnné n, a pak
Znovu a znovu jsem se obtěžovat uživatele

575
00:25:57,590 --> 00:26:01,880
pro kladné celé číslo pomocí vezmi_int,
a jediný výstup z této smyčky

576
00:26:01,880 --> 00:26:03,280
Jakmile uživatel splnil.

577
00:26:03,280 --> 00:26:05,670
Dělat, když jsme použili k
obtěžovat uživatele v tomto smyslu.

578
00:26:05,670 --> 00:26:06,670
Nyní je to zajímavé.

579
00:26:06,670 --> 00:26:08,510
Prohlašuji, int s názvem "odpověď".

580
00:26:08,510 --> 00:26:11,420
I přiřadit je návratová hodnota
o funkci nazvanou "sigma".

581
00:26:11,420 --> 00:26:15,200
Já nevím, co to ještě dělá, ale
Vzpomínám si, deklarovat ji před chvílí.

582
00:26:15,200 --> 00:26:18,310
A pak jsem kolem v
hodnota, kterou uživatel zadal, n,

583
00:26:18,310 --> 00:26:20,420
a pak jsem nahlásit odpověď.

584
00:26:20,420 --> 00:26:22,260
No pojďme se posunout zpět
jen na chvíli.

585
00:26:22,260 --> 00:26:28,620
Pojďme dál do tohoto adresáře, aby
sigma 0, a ve skutečnosti spustit tento program

586
00:26:28,620 --> 00:26:30,490
a uvidíme, co se stane.

587
00:26:30,490 --> 00:26:35,930
Takže když jsem se do toho pusťte a běh
tento program, ./sigma-0,

588
00:26:35,930 --> 00:26:40,139
jsem se a zadejte pozitivní
číslo jako dvě, Sigma,

589
00:26:40,139 --> 00:26:43,180
jako řecký symbol znamená, je jen
chystá sečíst všechna čísla od

590
00:26:43,180 --> 00:26:44,320
nulu až na dva.

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

592
00:26:46,560 --> 00:26:48,830
Tak by to mělo snad mi dát 3.

593
00:26:48,830 --> 00:26:49,750
To je všechno, co dělá.

594
00:26:49,750 --> 00:26:52,690
A podobně, když jsem spustit tento znovu
a dám mu číslo tři,

595
00:26:52,690 --> 00:26:56,721
to je 3 plus 2, tak to je
5 plus 1 by mi šest.

596
00:26:56,721 --> 00:26:59,470
A pak když jsem opravdu blázen a
začněte psát ve větších počtech,

597
00:26:59,470 --> 00:27:01,290
to by mi
větší a větší částky.

598
00:27:01,290 --> 00:27:02,250
Takže to je všechno.

599
00:27:02,250 --> 00:27:04,010
>> Tak co sigma vypadá?

600
00:27:04,010 --> 00:27:05,430
No, je to docela jednoduché.

601
00:27:05,430 --> 00:27:08,940
To je, jak jsme mohli realizovat
to za posledních pár týdnů.

602
00:27:08,940 --> 00:27:11,120
"Int" bude návratový typ.

603
00:27:11,120 --> 00:27:14,330
Sigma je název, a to trvá
Proměnná m místo n.

604
00:27:14,330 --> 00:27:15,940
Změním to až nahoře.

605
00:27:15,940 --> 00:27:17,340
Pak je to jen kontrola zdravý rozum.

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

607
00:27:18,430 --> 00:27:19,950
Uvidíme, proč za chvíli.

608
00:27:19,950 --> 00:27:24,220
Teď Prohlašuji další proměnné,
částka, inicializovat na nulu.

609
00:27:24,220 --> 00:27:28,140
Pak jsem to pro smyčce
iterace, zřejmě pro přehlednost,

610
00:27:28,140 --> 00:27:33,810
od i = 1 až na an = m, což je
co uživatel zadal, a pak jsem

611
00:27:33,810 --> 00:27:35,690
zvýšit částku, jako je tento.

612
00:27:35,690 --> 00:27:37,360
A pak se vrátit částku.

613
00:27:37,360 --> 00:27:38,440
>> Takže pár otázek.

614
00:27:38,440 --> 00:27:42,370
Jednou jsem nárok na můj komentář, že tento
zabraňuje riziku nekonečné smyčce.

615
00:27:42,370 --> 00:27:45,620
Proč by předáním záporného čísla
vyvolat potenciálně nekonečnou smyčku?

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

617
00:27:49,396 --> 00:27:51,290
>> Diváků: Nikdy dosáhnout metrů.

618
00:27:51,290 --> 00:27:52,880
>> SPEAKER 1: Nikdy nesahejte m.

619
00:27:52,880 --> 00:27:55,880
Ale m je předán, takže pojďme
zvážit jednoduchý příklad.

620
00:27:55,880 --> 00:27:58,510
Pokud m je předán do
uživatel jako negativního.

621
00:27:58,510 --> 00:28:00,059
Bez ohledu na to hlavní.

622
00:28:00,059 --> 00:28:01,850
Hlavní nás chrání před
to taky, takže jsem jen

623
00:28:01,850 --> 00:28:04,680
je opravdu anal s
sigma se také ujistit,

624
00:28:04,680 --> 00:28:06,540
že vstup nemůže být záporná.

625
00:28:06,540 --> 00:28:10,130
Takže, pokud m je záporný,
něco negativního.

626
00:28:10,130 --> 00:28:11,930
Co se bude dít?

627
00:28:11,930 --> 00:28:14,390
No, já se chystá
inicializaci jednoho,

628
00:28:14,390 --> 00:28:19,060
a pak i bude
méně než nebo rovno m?

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

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

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

632
00:28:26,930 --> 00:28:29,370
To byl-- pojďme ne,
pojďme nix tento příběh.

633
00:28:29,370 --> 00:28:32,780
Neptal jsem se na tuto otázku, protože
riziko, že jsem se zmiňovat o

634
00:28:32,780 --> 00:28:38,360
se to nestane, protože i je
vždy bude mít větší than-- OK,

635
00:28:38,360 --> 00:28:39,871
I odvolat na tuto otázku.

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

637
00:28:40,370 --> 00:28:42,030
Pojďme se zaměřit pouze na tuto část zde.

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

639
00:28:44,210 --> 00:28:48,830
Proč jste Prohlašuji, některé
mimo smyčky?

640
00:28:48,830 --> 00:28:52,010
Oznámení o lince 49 jsem
prohlásil i uvnitř smyčky,

641
00:28:52,010 --> 00:28:54,950
ale on-line 48 jsem
prohlásil trochu mimo.

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

643
00:28:55,695 --> 00:28:56,611
Diváků: [neslyšitelné].

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

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

646
00:28:59,400 --> 00:29:03,360
Takže v první řadě určitě ne
chtějí deklarovat a inicializovat částku

647
00:29:03,360 --> 00:29:06,130
na nulový vnitřní
smyčky na každé iteraci,

648
00:29:06,130 --> 00:29:09,370
protože by to jasně porazit
Účelem sečtením čísel.

649
00:29:09,370 --> 00:29:11,770
Já bych se neustále mění
hodnota zpět na nulu.

650
00:29:11,770 --> 00:29:17,992
A také to, co je další více tajemný
Důvodem pro téhož rozhodnutí designu?

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

652
00:29:18,954 --> 00:29:20,279
>> Diváků: [neslyšitelné].

653
00:29:20,279 --> 00:29:21,070
SPEAKER 1: Přesně tak.

654
00:29:21,070 --> 00:29:24,060
Chci se k nim dostat ven
smyčky příliš na tom, co online?

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

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

657
00:29:26,400 --> 00:29:29,910
A podle našeho pravidlo
od pár přednášek před,

658
00:29:29,910 --> 00:29:33,680
proměnné jsou rozsahem, opravdu, na
složené závorky, které je zahrnují.

659
00:29:33,680 --> 00:29:38,190
Takže pokud nemám deklarovat částku uvnitř
z těchto vnějších složených závorkách,

660
00:29:38,190 --> 00:29:40,250
Nemohu použít v souladu 53.

661
00:29:40,250 --> 00:29:43,160
Jinak řečeno, když jsem prohlásil,
částka sem, nebo dokonce v

662
00:29:43,160 --> 00:29:45,410
Pro smyčku, mohl bych se dostat ji do 53.

663
00:29:45,410 --> 00:29:47,150
Proměnná by účinně pryč.

664
00:29:47,150 --> 00:29:48,579
Takže pár důvodů tam.

665
00:29:48,579 --> 00:29:50,370
Ale teď se vraťme
a uvidíme, co se stane.

666
00:29:50,370 --> 00:29:51,730
Takže sigma volána.

667
00:29:51,730 --> 00:29:55,640
Dodává se 1 plus 2, nebo 1 plus 2
plus 3 a vrátí hodnotu,

668
00:29:55,640 --> 00:29:59,660
ukládá je do odpovědi, a printf zde
je důvod, proč jsem viděl na obrazovce.

669
00:29:59,660 --> 00:30:03,079
Tak tohle je to, co nazveme iterační
přístup, kde iterace jen

670
00:30:03,079 --> 00:30:03,870
znamená, že pomocí smyčky.

671
00:30:03,870 --> 00:30:06,900
U smyčky, while, dělat, když
smyčky, prostě dělat něco znovu

672
00:30:06,900 --> 00:30:08,380
a znovu a znovu.

673
00:30:08,380 --> 00:30:13,505
>> Ale sigma je docela elegantní funkce v
že jsem mohl realizovat jinak.

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

675
00:30:14,620 --> 00:30:19,120
Co o tom, které
jen aby se trochu v pohodě,

676
00:30:19,120 --> 00:30:21,880
dovolte mi, abych opravdu zbavit
z mnoha rozptýlení

677
00:30:21,880 --> 00:30:24,380
protože tuto funkci
je opravdu velmi jednoduché.

678
00:30:24,380 --> 00:30:27,780
Pojďme řezat ho jen
svých čtyř hlavních linií

679
00:30:27,780 --> 00:30:30,410
a zbavit se všech
připomínky a složené závorky.

680
00:30:30,410 --> 00:30:34,334
To je tak trochu ohromující
Alternativní implementace.

681
00:30:34,334 --> 00:30:37,250
Dobře, možná ne ohromující,
ale je to trochu svůdnější, v pořádku,

682
00:30:37,250 --> 00:30:39,920
podívat se na to tak mnohem stručněji.

683
00:30:39,920 --> 00:30:43,120
S pouhými čtyřmi řádky kódu,
Poprvé jsem tuto kontrolu zdravý rozum.

684
00:30:43,120 --> 00:30:45,732
Je-li m je menší než nebo rovna
nula, sigma nemá smysl.

685
00:30:45,732 --> 00:30:48,190
Je to jen má být v
v tomto případě pro kladná čísla,

686
00:30:48,190 --> 00:30:50,340
tak jsem jen tak
vrátit nulu libovolně

687
00:30:50,340 --> 00:30:53,210
tak, že jsme aspoň
některé takzvané referenční případ.

688
00:30:53,210 --> 00:30:54,430
>> Ale tady je to krása.

689
00:30:54,430 --> 00:30:59,930
Celistvost této myšlenky, dodává
Čísla od 1 do n, m, nebo v tomto případě,

690
00:30:59,930 --> 00:31:02,630
může být provedeno podle druhu absolvování babku.

691
00:31:02,630 --> 00:31:04,947
No, a co je součet 1 až m?

692
00:31:04,947 --> 00:31:05,780
No, víš co?

693
00:31:05,780 --> 00:31:11,949
Je to stejné jako součet m
plus součet 1 až M minus jedna.

694
00:31:11,949 --> 00:31:12,740
Tak víš co?

695
00:31:12,740 --> 00:31:13,940
Co je to sigma z m mínus 1?

696
00:31:13,940 --> 00:31:17,860
No, pokud jste trochu sledovat tento
logicky, je to to samé jako M minus 1

697
00:31:17,860 --> 00:31:21,415
navíc sigma M minus dva.

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

699
00:31:22,480 --> 00:31:26,012
Takže můžete trochu jen--
to je jako, když jste právě

700
00:31:26,012 --> 00:31:28,220
se snaží otravovat přítele
a oni vás na něco zeptat,

701
00:31:28,220 --> 00:31:31,344
tak nějak odpovědět na otázku,
můžete trochu držet kolem babku.

702
00:31:31,344 --> 00:31:34,560
Ale co je klíčové je, že pokud budete mít
takže otázka, menší a menší,

703
00:31:34,560 --> 00:31:36,910
a menší, ty jsi
ne se ptát, co je to sigma

704
00:31:36,910 --> 00:31:39,116
n, co je sigma o
n, co je sigma n?

705
00:31:39,116 --> 00:31:40,990
Ptáte se, co je
sigma n, co je sigma

706
00:31:40,990 --> 00:31:42,839
n minus 1, co je sigma n mínus 2?

707
00:31:42,839 --> 00:31:44,880
Nakonec vaše otázka
se stane co?

708
00:31:44,880 --> 00:31:50,250
Co je sigma jednoho nebo
nula, některé velmi malé hodnoty,

709
00:31:50,250 --> 00:31:52,220
a jakmile se
si, že váš přítel,

710
00:31:52,220 --> 00:31:54,350
nebudete se zeptat
opět stejná otázka,

711
00:31:54,350 --> 00:31:55,975
jste jen chtěl říct, oh to je nula.

712
00:31:55,975 --> 00:31:58,490
Skončili jsme hrát tento druh
z hloupé cyklické hry.

713
00:31:58,490 --> 00:32:02,950
>> Takže rekurze je akt v programování
z funkce volá sama sebe.

714
00:32:02,950 --> 00:32:06,630
Tento program, který při kompilaci a spuštění je
bude chovat přesně stejným způsobem,

715
00:32:06,630 --> 00:32:09,620
ale to, co je klíčové je, že uvnitř
o funkci nazvanou sigma,

716
00:32:09,620 --> 00:32:13,150
je řádek kódu přičemž
Říkáme sami,

717
00:32:13,150 --> 00:32:14,980
které by za normálních okolností bylo špatné.

718
00:32:14,980 --> 00:32:21,160
Například, co nejdříve, pokud I
sestavil toto, takže se sigma--

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

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

721
00:32:25,050 --> 00:32:27,690
Kladné celé číslo, prosím, 50 1275.

722
00:32:27,690 --> 00:32:30,810
Takže to, co je funkce Zdá se, že
být, na základě jednoho testu, správné.

723
00:32:30,810 --> 00:32:34,917
Ale co když mám trochu nebezpečné
a odstranit takzvanou základní věci,

724
00:32:34,917 --> 00:32:37,750
a jen říct, tak jsem jen dělat
to složitější, než to je.

725
00:32:37,750 --> 00:32:42,450
Řekněme, výpočet sigma
tím, že m a pak se přidá

726
00:32:42,450 --> 00:32:44,564
v sigma m mínus jedna?

727
00:32:44,564 --> 00:32:45,980
No, a co se bude dít tady?

728
00:32:45,980 --> 00:32:47,140
Pojďme oddálit.

729
00:32:47,140 --> 00:32:52,920
Pojďme překompilovat program,
uložit, překompilovat program,

730
00:32:52,920 --> 00:33:00,450
a tedy připraven ./sigma 1 přiblížení,
zadejte kladné číslo, prosím, 50.

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

732
00:33:02,180 --> 00:33:04,430
Kolik z vás je ochotno
na Fess až když viděl, že?

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

734
00:33:04,950 --> 00:33:06,690
Tak tohle se může stát pro
celá řada důvodů,

735
00:33:06,690 --> 00:33:09,148
a upřímně řečeno, tento týden jsme
o tom, aby vám více z nich.

736
00:33:09,148 --> 00:33:11,780
Ale v tomto případě se pokuste
rozum zpět

737
00:33:11,780 --> 00:33:14,430
co by se tu stalo?

738
00:33:14,430 --> 00:33:17,400
Chyba segmentace, řekli jsme poslední
čas, označuje segment paměti.

739
00:33:17,400 --> 00:33:18,690
Něco špatného se stalo.

740
00:33:18,690 --> 00:33:21,550
Ale co to bylo
mechanicky to pokazilo

741
00:33:21,550 --> 00:33:25,000
zde kvůli mému odstranění
této takzvané základní věci,

742
00:33:25,000 --> 00:33:26,870
kde jsem se vrátil pevně hodnotu?

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

744
00:33:28,970 --> 00:33:30,460
Co si myslíte, že se stalo?

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

746
00:33:31,219 --> 00:33:32,135
>> Diváků: [neslyšitelné].

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

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

749
00:33:36,970 --> 00:33:37,550
Dobrá otázka.

750
00:33:37,550 --> 00:33:39,508
Takže velikost čísla
že jsem se sečtením

751
00:33:39,508 --> 00:33:41,920
byl tak velký, že je překročena
velikost paměti.

752
00:33:41,920 --> 00:33:44,640
To je dobrý nápad, ale ne zásadně
chystá způsobit pád.

753
00:33:44,640 --> 00:33:48,230
To by mohlo vést k přetečení celého čísla,
kde bity jen otočit

754
00:33:48,230 --> 00:33:51,760
a pak jsme se mylně opravdu velký
číslo jako záporné číslo,

755
00:33:51,760 --> 00:33:53,260
ale to samo o sobě nezpůsobí pád.

756
00:33:53,260 --> 00:33:55,509
Protože na konci
den int je stále 32 bitů.

757
00:33:55,509 --> 00:33:57,640
Vy nebudete
náhodně ukrást 33. bit.

758
00:33:57,640 --> 00:33:58,431
Ale dobrá myšlenka.

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

760
00:33:58,984 --> 00:33:59,900
>> Diváků: [neslyšitelné].

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

762
00:34:00,551 --> 00:34:02,300
SPEAKER 1: Metoda
nikdy zastaví,

763
00:34:02,300 --> 00:34:06,658
a opravdu to tak nazývá znovu
a znovu a znovu a znovu

764
00:34:06,658 --> 00:34:08,449
a znovu, a nikdo z
ty funkce vůbec

765
00:34:08,449 --> 00:34:13,310
dokončit, protože jejich jediným řádku
Kód vlastního života volá znovu a znovu

766
00:34:13,310 --> 00:34:14,219
a znovu.

767
00:34:14,219 --> 00:34:16,080
A co je opravdu
se tu děje, a teď jsme

768
00:34:16,080 --> 00:34:18,100
může druh čerpat to obrazně.

769
00:34:18,100 --> 00:34:20,899
Nechte mě projít do
obraz na chvíli.

770
00:34:20,899 --> 00:34:22,940
To je obraz, který
nakonec zhmotnit

771
00:34:22,940 --> 00:34:26,336
podrobněji o tom, co se děje
vnitřní paměti vašeho počítače.

772
00:34:26,336 --> 00:34:28,460
A ukázalo se, že na
Spodní část tohoto obrázku

773
00:34:28,460 --> 00:34:29,709
je něco, co nazývá zásobník.

774
00:34:29,709 --> 00:34:31,920
To je kus
paměti, kus paměti RAM,

775
00:34:31,920 --> 00:34:33,920
to je jen použít kdykoliv
funkce se nazývá.

776
00:34:33,920 --> 00:34:36,239
Kdykoliv, programátor,
volání funkce,

777
00:34:36,239 --> 00:34:38,860
operační systém, jako je
Mac OS, Windows, nebo Linux,

778
00:34:38,860 --> 00:34:41,920
chytne banda bajtů, možná
pár kilobajtů, možná pár megabajtů

779
00:34:41,920 --> 00:34:44,590
paměti, předá je
pro vás, a pak se nechá

780
00:34:44,590 --> 00:34:47,650
můžete spustit funkci pomocí
bez ohledu na proměnné, které potřebujete.

781
00:34:47,650 --> 00:34:50,699
A pokud si pak volat další
funkce a další funkce,

782
00:34:50,699 --> 00:34:53,590
dostanete další kus paměti
a další plátek paměti.

783
00:34:53,590 --> 00:34:57,090
>> A skutečně, pokud je těchto zelených zásobníků
od Annenberg představují, že paměť,

784
00:34:57,090 --> 00:34:59,870
tady je to, co se stane první
když budete volat funkci sigma.

785
00:34:59,870 --> 00:35:04,510
Je to jako dávat zásobník takhle
na to, co je nejprve prázdný zásobník.

786
00:35:04,510 --> 00:35:07,142
Ale pak když je tento zásobník
volá sám, abych tak řekl,

787
00:35:07,142 --> 00:35:08,850
volá další instanci
sigma, je to

788
00:35:08,850 --> 00:35:11,640
jako se ptát, operační systém,
ooh, potřebují trochu více paměti,

789
00:35:11,640 --> 00:35:12,520
dej mi to.

790
00:35:12,520 --> 00:35:14,840
A pak se to dostane nahromadí na na vrcholu.

791
00:35:14,840 --> 00:35:18,030
Ale to, co je klíčem je, že
První zásobník je stále tady,

792
00:35:18,030 --> 00:35:20,620
proto, že použil tento druhý zásobník.

793
00:35:20,620 --> 00:35:23,500
Nyní mezitím sigma sigma volání,
To je jako ptát se na více paměti.

794
00:35:23,500 --> 00:35:25,830
Dostane nahromadí na sem.

795
00:35:25,830 --> 00:35:29,350
sigma volat Sigma, to je další
zásobník, který se nahromadí na zde.

796
00:35:29,350 --> 00:35:32,942
A pokud budete mít, co děláme,
nakonec, druh map tato vizuální

797
00:35:32,942 --> 00:35:35,525
tohoto grafu, co se děje na
stane s hromadou misek?

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

799
00:35:37,480 --> 00:35:41,160
To bude vyšší než výše
paměti má váš počítač.

800
00:35:41,160 --> 00:35:45,790
A jakmile ekologickým zásobníku
přesahuje vodorovnou čáru

801
00:35:45,790 --> 00:35:49,410
nad komínem a nad to slovo hromady,
které se vrátíme v budoucnosti,

802
00:35:49,410 --> 00:35:50,410
to je špatná věc.

803
00:35:50,410 --> 00:35:52,810
Halda je jiný
segment paměti,

804
00:35:52,810 --> 00:35:55,190
a pokud si nechat tyto
zásobníky hromada a hromada na,

805
00:35:55,190 --> 00:35:57,800
budete překročit
vlastní segment paměti,

806
00:35:57,800 --> 00:36:00,420
a program je opravdu chystá k havárii.

807
00:36:00,420 --> 00:36:02,930
>> Nyní jako stranou, tuto myšlenku
rekurze, tedy

808
00:36:02,930 --> 00:36:06,500
jasně vést k problémům, ale
to není nutně špatná věc.

809
00:36:06,500 --> 00:36:08,840
Vzhledem k tomu, zvážit, po
všichni, Jak-- a možná

810
00:36:08,840 --> 00:36:11,700
to trvá nějaký čas zvykat
na --how elegantní nebo jak jednoduché

811
00:36:11,700 --> 00:36:14,890
že provádění sigma je.

812
00:36:14,890 --> 00:36:17,440
A my nebudeme používat
rekurze tak moc v CS50,

813
00:36:17,440 --> 00:36:20,780
ale v CS51, a opravdu kterákoliv třída
kde se manipulovat datové struktury

814
00:36:20,780 --> 00:36:23,640
jako jsou stromy, nebo rodinné stromy,
které mají určitou hierarchii,

815
00:36:23,640 --> 00:36:26,000
je to super, super užitečné.

816
00:36:26,000 --> 00:36:29,750
Nyní, stejně jako stranou, aby vás
jako začínající počítačoví odborníci

817
00:36:29,750 --> 00:36:33,180
jsou obeznámeni s některými z Google je
uvnitř vtipy, pokud jdete na Google

818
00:36:33,180 --> 00:36:36,345
a podívat se, co je
definice, řekněme, rekurze, zadejte.

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
Jako stranou, vytáhl jsem pár.

822
00:36:42,670 --> 00:36:45,470
To je jako 10 minut
otálení dnes ráno.

823
00:36:45,470 --> 00:36:52,890
Pokud se vám také Google "nakřivo" oznámení
nakláněním hlavu slightly--

824
00:36:52,890 --> 00:36:55,120
a tohle je možná
těch nejděsivějších ze všech

825
00:36:55,120 --> 00:36:57,286
protože někdo strávil jako
jejich den provádění tohoto

826
00:36:57,286 --> 00:36:59,880
několik let ago-- pojď.

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

828
00:37:01,140 --> 00:37:04,540
Oh, počkej to je chyba.

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

830
00:37:08,410 --> 00:37:11,410
>> Tak běží na jednom z
největší světová stránky

831
00:37:11,410 --> 00:37:13,510
jsou tyto hloupé velikonoční vajíčka.

832
00:37:13,510 --> 00:37:16,690
Pravděpodobně konzumují
netriviální počet řádků kódu

833
00:37:16,690 --> 00:37:19,280
jen proto, že můžeme mít
malé zábavné věci, jako že.

834
00:37:19,280 --> 00:37:22,140
Ale aspoň teď dostanete
některé z těchto uvnitř vtipy.

835
00:37:22,140 --> 00:37:28,330
>> Nyní se pojďme podívat na některé z
White Lies jsme říkali pozdní,

836
00:37:28,330 --> 00:37:30,707
a začít loupat zpět
některé vrstvy technicky

837
00:37:30,707 --> 00:37:32,790
takže si opravdu pochopit,
co se děje

838
00:37:32,790 --> 00:37:34,860
a můžete pochopit,
některé z hrozeb,

839
00:37:34,860 --> 00:37:38,060
jako Shellshock, že
se nyní začínají být

840
00:37:38,060 --> 00:37:41,110
Na čele každého z nás
pozornost, přinejmenším v médiích.

841
00:37:41,110 --> 00:37:45,810
Takže tady je velmi jednoduchá funkce
že se vrátí nic neplatné.

842
00:37:45,810 --> 00:37:46,790
Jeho jméno je odkládací.

843
00:37:46,790 --> 00:37:50,880
Trvá dvou proměnných
a vrátí nic.

844
00:37:50,880 --> 00:37:52,260
Bere na A a B..

845
00:37:52,260 --> 00:37:53,337
Tak rychle demonstrace.

846
00:37:53,337 --> 00:37:54,170
Vzali jsme to nahoru.

847
00:37:54,170 --> 00:37:56,100
Mohli bychom také vzít trochu
zlomit tu jen na chvíli

848
00:37:56,100 --> 00:37:57,250
a mít něco k pití.

849
00:37:57,250 --> 00:38:00,120
Pokud někdo by mi nevadilo spojení
me up na chvíli tady.

850
00:38:00,120 --> 00:38:01,830
Jak se o vás v kaštanově hnědé košili?

851
00:38:01,830 --> 00:38:02,335
Pojď nahoru.

852
00:38:02,335 --> 00:38:04,060

853
00:38:04,060 --> 00:38:05,260
Jen jeden dnes.

854
00:38:05,260 --> 00:38:06,251
Děkuji, i když.

855
00:38:06,251 --> 00:38:08,000
Tak jo, a máme
přijít, kdo tady?

856
00:38:08,000 --> 00:38:08,660
Jak se jmenujete?

857
00:38:08,660 --> 00:38:09,360
>> SPEAKER 4: Laura.

858
00:38:09,360 --> 00:38:09,740
>> SPEAKER 1: Laura.

859
00:38:09,740 --> 00:38:10,370
Pojď nahoru.

860
00:38:10,370 --> 00:38:11,460

861
00:38:11,460 --> 00:38:13,850
Takže Laura, velmi jednoduchá výzva dnes.

862
00:38:13,850 --> 00:38:14,704

863
00:38:14,704 --> 00:38:15,370
Nice to meet yo.

864
00:38:15,370 --> 00:38:16,410

865
00:38:16,410 --> 00:38:16,910
V pořádku.

866
00:38:16,910 --> 00:38:21,179
Takže máme trochu mléka sem a
máme nějaký pomerančový džus sem

867
00:38:21,179 --> 00:38:23,345
a některé poháry, které jsme
půjčil si od Annenberg dnes.

868
00:38:23,345 --> 00:38:24,178
>> SPEAKER 4: Půjčil.

869
00:38:24,178 --> 00:38:27,240
SPEAKER 1: A bude pokračovat
a dá vám půl sklenice tohoto.

870
00:38:27,240 --> 00:38:28,250

871
00:38:28,250 --> 00:38:28,800
V pořádku.

872
00:38:28,800 --> 00:38:30,750
A my vám dáme poloviny
sklenici mléka.

873
00:38:30,750 --> 00:38:31,905

874
00:38:31,905 --> 00:38:35,890
Jo, a jen tak, že můžete
vzpomenout, co to bylo, jako,

875
00:38:35,890 --> 00:38:38,860
Vzpomněl jsem si, aby
to a dnes.

876
00:38:38,860 --> 00:38:42,030

877
00:38:42,030 --> 00:38:42,530
Dobře.

878
00:38:42,530 --> 00:38:45,470
Pokud vám to nebude vadit, podívejme se, my
je dát na své vlastní brýle

879
00:38:45,470 --> 00:38:46,560
jestli chcete.

880
00:38:46,560 --> 00:38:48,710
Bude to svět z Laurových očí.

881
00:38:48,710 --> 00:38:49,210
V pořádku.

882
00:38:49,210 --> 00:38:53,820
Takže váš cíl, vzhledem k tomu dva šálky
Zde kapalina, mléko a pomerančový džus,

883
00:38:53,820 --> 00:38:58,370
je prohodit obsah tak, aby se
pomerančová šťáva jde do šálku mléka

884
00:38:58,370 --> 00:39:00,710
a jde do mléka
pomerančový džus šálek.

885
00:39:00,710 --> 00:39:02,359
>> SPEAKER 4: Dostanu jeden šálek?

886
00:39:02,359 --> 00:39:05,650
SPEAKER 1: Jsem rád, že se ptáš, když
bylo by to mnohem lepší záběry

887
00:39:05,650 --> 00:39:06,710
pokud jste se neptal.

888
00:39:06,710 --> 00:39:10,620
Ale ano, můžeme nabídnout třetiny
kalich je prázdná, samozřejmě.

889
00:39:10,620 --> 00:39:11,120
V pořádku.

890
00:39:11,120 --> 00:39:12,300
Takže vyměnit obsah tam.

891
00:39:12,300 --> 00:39:16,100

892
00:39:16,100 --> 00:39:17,050
Very nice.

893
00:39:17,050 --> 00:39:20,390

894
00:39:20,390 --> 00:39:21,305
Velmi dobře.

895
00:39:21,305 --> 00:39:23,121

896
00:39:23,121 --> 00:39:24,745
Děláš to pozoruhodně opatrně.

897
00:39:24,745 --> 00:39:26,970

898
00:39:26,970 --> 00:39:28,655
A krok tři.

899
00:39:28,655 --> 00:39:30,390

900
00:39:30,390 --> 00:39:31,350
V pořádku.

901
00:39:31,350 --> 00:39:31,930
Výborně.

902
00:39:31,930 --> 00:39:33,930
Velký potlesk
by bylo dobré pro Lauru.

903
00:39:33,930 --> 00:39:36,500

904
00:39:36,500 --> 00:39:37,000
V pořádku.

905
00:39:37,000 --> 00:39:40,790
Máme malý dárek na rozloučenou
pro vás, ale dovolte mi, abych to.

906
00:39:40,790 --> 00:39:42,620
Děkuji moc.

907
00:39:42,620 --> 00:39:46,170
Tak jednoduchý příklad, i když,
prokázat, že pokud si

908
00:39:46,170 --> 00:39:48,300
Chcete měnit obsah
ze dvou nádob,

909
00:39:48,300 --> 00:39:52,360
nebo říkejme jim proměnné,
budete potřebovat nějaké dočasné uskladnění

910
00:39:52,360 --> 00:39:56,710
inscenovat jednu z obsahu v rozsahu, v
že můžete skutečně udělat swap.

911
00:39:56,710 --> 00:40:01,790
Takže opravdu, tento zdrojový kód zde v
C je představitelem přesně to.

912
00:40:01,790 --> 00:40:06,340
V případě, že pomerančový džus byl a mléko
Byl b, a my jsme chtěli vyměnit dvě,

913
00:40:06,340 --> 00:40:08,990
můžete zkusit něco kreativního
nalitím do sebe,

914
00:40:08,990 --> 00:40:11,031
ale to asi ne
konec obzvláště dobře.

915
00:40:11,031 --> 00:40:15,260
A tak jsme se použít třetina šálku, hovor
to tmp, T-M-P konvencí,

916
00:40:15,260 --> 00:40:19,370
a dát obsah
Věst v tom, že pak vyměnit jeden šálek,

917
00:40:19,370 --> 00:40:22,610
pak dal OJ do
Originální pohár, čímž se

918
00:40:22,610 --> 00:40:25,320
dosažení, přesně tak, jak
Laura udělala, swap.

919
00:40:25,320 --> 00:40:26,850
>> Takže pojďme dělat přesně to.

920
00:40:26,850 --> 00:40:30,110
Nech mě jít napřed a otevřít
up příklad, který je

921
00:40:30,110 --> 00:40:32,720
vlastně říká "ne
vyměnit, "protože to není

922
00:40:32,720 --> 00:40:36,180
jak jednoduše udělat, jak byste si mohli myslet.

923
00:40:36,180 --> 00:40:41,190
Takže v rámci tohoto programu, zjistíte, že
Já používám stdio.h naše stará známá.

924
00:40:41,190 --> 00:40:43,130
Mám prototyp
odkládací prostor tam, což

925
00:40:43,130 --> 00:40:45,450
znamená, že její realizace je
asi dole,

926
00:40:45,450 --> 00:40:48,050
a podívejme se, co to hlavní
Program bude dělat pro mě.

927
00:40:48,050 --> 00:40:52,020
První Prohlašuji, int x dostane
jeden, a int y dostane dva.

928
00:40:52,020 --> 00:40:54,930
Takže myslíte, že z těch, co věstníku
a mléka, resp.

929
00:40:54,930 --> 00:40:57,100
A pak jsem se
printf říkat x je to

930
00:40:57,100 --> 00:41:00,120
a y je to, jen tak mohu
vizuálně vidět, co se děje.

931
00:41:00,120 --> 00:41:03,810
Pak jsem printf tvrdí
že jsem přečerpání dva,

932
00:41:03,810 --> 00:41:07,100
a pak jsem vytisknout
tvrdí, že to vyměnili,

933
00:41:07,100 --> 00:41:09,300
a já znovu vytisknout x a y.

934
00:41:09,300 --> 00:41:13,010
Takže tady v swap
přesně to, co Laura udělala,

935
00:41:13,010 --> 00:41:16,240
a přesně to, co jsme viděli na
obrazovka před chvílí.

936
00:41:16,240 --> 00:41:19,380
>> Tak pojďme do toho a
bude velice zklamán.

937
00:41:19,380 --> 00:41:24,690
Nenechte výměnu a spustit žádný swap,
přiblížení na výstupu zde.

938
00:41:24,690 --> 00:41:28,320
Zadejte x 1, y je 2, swapping prohozeny.

939
00:41:28,320 --> 00:41:32,700
x je stále 1, a y je ještě 2.

940
00:41:32,700 --> 00:41:37,630
Takže i když, upřímně řečeno, to vypadá
přesně líbí, i když technicky,

941
00:41:37,630 --> 00:41:40,730
co Laura udělala, nezdálo se, že práce.

942
00:41:40,730 --> 00:41:42,130
Tak proč to je?

943
00:41:42,130 --> 00:41:46,630
No, ukázalo se, že při
napíšeme program, jako je tento

944
00:41:46,630 --> 00:41:51,590
která oba hlavní, zdůraznil zde
a pak další funkce, jako odkládací prostor,

945
00:41:51,590 --> 00:41:54,230
zde zdůrazněno, které
volá, svět

946
00:41:54,230 --> 00:41:57,030
vypadá něco jako
Tyto zásobníky před chvílí.

947
00:41:57,030 --> 00:42:00,440
Když hlavní nejprve volána,
To je jako ptát se operační systém

948
00:42:00,440 --> 00:42:04,030
o trochu paměti pro jakýkoli místní
proměnných, jako je x a y, které má hlavní,

949
00:42:04,030 --> 00:42:05,660
a skončí tady.

950
00:42:05,660 --> 00:42:10,920
Ale pokud hlavní hovory přepínat, a hlavní
přechází vyměnit dva argumenty, A a B,

951
00:42:10,920 --> 00:42:16,410
pomerančový džus a mléko, to není jako
podal pomerančový džus a mléko

952
00:42:16,410 --> 00:42:17,500
Lauře.

953
00:42:17,500 --> 00:42:21,300
Co dělá počítač, je to
předá kopie pomerančového džusu

954
00:42:21,300 --> 00:42:27,110
a kopie mléka Laura, aby se
co je nakonec uvnitř tohoto zásobníku

955
00:42:27,110 --> 00:42:32,510
je jedna hodnota, a dva, nebo Úř
a mléka, ale jejich kopie,

956
00:42:32,510 --> 00:42:34,790
tak, že v tomto bodě
v příběhu, tam

957
00:42:34,790 --> 00:42:36,930
je věst a mléko v každé z těchto zásobníků.

958
00:42:36,930 --> 00:42:39,260
K dispozici je jedna a dvě
v každé z těchto zásobníků,

959
00:42:39,260 --> 00:42:41,720
a funkce odkládací skutečně funguje.

960
00:42:41,720 --> 00:42:46,090
Je to vymění je uvnitř
z druhé nejvyšší zásobníku,

961
00:42:46,090 --> 00:42:48,147
ale že odkládání nemá žádný vliv.

962
00:42:48,147 --> 00:42:49,980
A na základě jen některé
Základním principem máme

963
00:42:49,980 --> 00:42:52,970
mluvil o dříve, a sice
před pár minut, co

964
00:42:52,970 --> 00:42:58,770
by mohlo vysvětlit, proč změny
a b uvnitř swapu

965
00:42:58,770 --> 00:43:05,560
nemá žádný vliv na x a y, i když
Prošel jsem x a y na funkci paměti.

966
00:43:05,560 --> 00:43:08,750
Co je klíčové slovo zde, že
může zjednodušeně vysvětlit?

967
00:43:08,750 --> 00:43:11,250

968
00:43:11,250 --> 00:43:12,627
Myslím, že je tady jsem slyšel?

969
00:43:12,627 --> 00:43:13,335
DIVÁKŮ: Return.

970
00:43:13,335 --> 00:43:14,085
SPEAKER 1: Návrat?

971
00:43:14,085 --> 00:43:14,590
Nevrátí.

972
00:43:14,590 --> 00:43:15,895
Pojďme s jedním jiný.

973
00:43:15,895 --> 00:43:16,395
Co je to?

974
00:43:16,395 --> 00:43:17,080
>> Diváků: [neslyšitelné].

975
00:43:17,080 --> 00:43:20,000
>> SPEAKER 1: OK, takže jsme mohli return--
aby zpáteční práce v příběhu,

976
00:43:20,000 --> 00:43:21,914
ale tam je ještě jednodušší vysvětlení.

977
00:43:21,914 --> 00:43:22,580
DIVÁKŮ: Scope.

978
00:43:22,580 --> 00:43:23,288
SPEAKER 1: Rozsah platnosti.

979
00:43:23,288 --> 00:43:24,300
Vezmu rozsahu.

980
00:43:24,300 --> 00:43:27,290
Takže rozsah, si vzpomenout, kde
Naše x a y prohlásil.

981
00:43:27,290 --> 00:43:30,840
Jsou deklarované uvnitř
z hlavní až tady.

982
00:43:30,840 --> 00:43:33,200
a, b, zatím, jsou
fakticky vyhlásil

983
00:43:33,200 --> 00:43:35,930
uvnitř odkládací prostor, ne zcela
Složené závorky, ale stále

984
00:43:35,930 --> 00:43:37,690
v obecné části swapu.

985
00:43:37,690 --> 00:43:40,560
A tak skutečně, a ab
existují pouze v rámci tohoto zásobníku

986
00:43:40,560 --> 00:43:44,850
z Annenberg, toto
Druhý kus kódu.

987
00:43:44,850 --> 00:43:49,500
Takže jsme opravdu mění kopii, ale
to není opravdu všechno, že užitečné.

988
00:43:49,500 --> 00:43:52,190
>> Takže pojďme se podívat na
to trochu nižší úrovni.

989
00:43:52,190 --> 00:43:55,430
Chystám se vrátit do
Source Directory,

990
00:43:55,430 --> 00:43:58,330
a já budu první
přiblížit tady, a jen

991
00:43:58,330 --> 00:44:02,290
potvrdit, že jsem v tomto
větší okno terminálu,

992
00:44:02,290 --> 00:44:04,430
Program se stále chová takhle.

993
00:44:04,430 --> 00:44:06,840
Předpokládejme nyní, že tento
není úmyslné.

994
00:44:06,840 --> 00:44:10,090
Jasně jsem chtěl výměnu na
práce, takže je to jako chyba.

995
00:44:10,090 --> 00:44:12,780
Teď jsem mohl začít přidávat
hodně printf let na mém kódu,

996
00:44:12,780 --> 00:44:16,010
vytisknout x sem, y po
tady, tady, b sem.

997
00:44:16,010 --> 00:44:18,220
Ale upřímně řečeno, to je asi to, co
jsi dělal za pár týdnů

998
00:44:18,220 --> 00:44:20,190
Nyní, v úředních hodinách
a doma při práci

999
00:44:20,190 --> 00:44:22,150
na psets se snaží najít nějaké chyby.

1000
00:44:22,150 --> 00:44:25,560
Ale uvidíte, pokud jste tak již neučinili,
že problém nastavit tři vás seznámí

1001
00:44:25,560 --> 00:44:31,630
k příkazu názvem GDB,
kde GDB, GNU debugger,

1002
00:44:31,630 --> 00:44:34,040
má sama spoustu
funkce, které mohou ve skutečnosti

1003
00:44:34,040 --> 00:44:38,160
abychom pochopili situaci
takhle, ale přesvědčivě,

1004
00:44:38,160 --> 00:44:39,940
řešit problémy a najít chyby.

1005
00:44:39,940 --> 00:44:40,940
Tak jdu na to.

1006
00:44:40,940 --> 00:44:44,770
Místo toho, aby ./noswap jsem místo
bude běžet GDB ./noswap.

1007
00:44:44,770 --> 00:44:47,410

1008
00:44:47,410 --> 00:44:51,200
Jinými slovy, budu běžet můj
Program není Bash, náš nový přítel

1009
00:44:51,200 --> 00:44:51,850
dnes.

1010
00:44:51,850 --> 00:44:53,970
Chystám se spustit můj
Program noswap uvnitř

1011
00:44:53,970 --> 00:44:56,900
tohoto jiného programu s názvem
GDB, který je debugger, který

1012
00:44:56,900 --> 00:45:01,035
je program, který je navržen tak, aby
Vy lidé najít a odstranit chyby.

1013
00:45:01,035 --> 00:45:03,410
Takže když jsem narazila Spustit tady, je tu
ukrutný množství textu

1014
00:45:03,410 --> 00:45:04,868
že opravdu nikdy nebudete muset číst.

1015
00:45:04,868 --> 00:45:07,290
Je to v podstatě rozptýlení
z příkazového řádku, který

1016
00:45:07,290 --> 00:45:10,030
Chystám se udeřit Control-L
dostat se na tam nahoře.

1017
00:45:10,030 --> 00:45:11,800
To je výzva GDB.

1018
00:45:11,800 --> 00:45:15,550
Pokud chci spustit tento program nyní
protože tento malý tahák na dnešní

1019
00:45:15,550 --> 00:45:21,860
snímek naznačuje, Run je první
příkazy, které nám chtěl představit.

1020
00:45:21,860 --> 00:45:25,150
A já jsem prostě jít s typem
běžet až tady uvnitř GDB,

1021
00:45:25,150 --> 00:45:26,811
a opravdu to běžel můj program.

1022
00:45:26,811 --> 00:45:29,310
Teď tam je nějaký další
výstupy na obrazovku, jako je tato,

1023
00:45:29,310 --> 00:45:31,910
ale to je jen GDB je anální
a říkat nám, co se děje.

1024
00:45:31,910 --> 00:45:34,451
Ty opravdu nemají na starosti
o těchto údajů právě teď.

1025
00:45:34,451 --> 00:45:36,890
Ale to, co je opravdu v pohodě
GDB, je-li to udělat again--

1026
00:45:36,890 --> 00:45:42,100
Control-L vymaže screen-- nech mě jít
dopředu a typu "break hlavní," tím,

1027
00:45:42,100 --> 00:45:45,743
když jsem stiskněte klávesu Enter, nastavení, co je
volal zlom v noswap.c,

1028
00:45:45,743 --> 00:45:51,270
řádek 16, který je tam, kde GDB
přišel můj program ve skutečnosti

1029
00:45:51,270 --> 00:45:53,070
je moje funkce je ve skutečnosti.

1030
00:45:53,070 --> 00:45:55,070
To budeme ignorovat nyní
ale to je adresa

1031
00:45:55,070 --> 00:45:57,310
v paměti specificky této funkce.

1032
00:45:57,310 --> 00:46:00,240
Takže teď, když typ jsem běžet,
Všimněte si, co je v pohodě zde.

1033
00:46:00,240 --> 00:46:05,650
Můj program vypukne v řádku I
řekl GDB pozastavit výkon na.

1034
00:46:05,650 --> 00:46:09,850
Takže nemám teď změnit svůj kód,
přidat nějaké printf je, překompilovat to, repríza

1035
00:46:09,850 --> 00:46:13,300
to, změnit, přidat nějaké printf je,
uložit, překompilovat ho spustit.

1036
00:46:13,300 --> 00:46:18,100
Mohu jen projít můj program
krok za krokem za krokem při lidskou rychlostí,

1037
00:46:18,100 --> 00:46:20,880
ne na Intel-uvnitř druhu rychlosti.

1038
00:46:20,880 --> 00:46:24,580
>> Takže teď všimnete tento řádek
Zde se zobrazí, a když jsem se vrátit

1039
00:46:24,580 --> 00:46:27,800
do mého programu v gedit,
Všimněte si, že to je ve skutečnosti

1040
00:46:27,800 --> 00:46:29,280
První řádek kódu.

1041
00:46:29,280 --> 00:46:31,240
K dispozici je řada 16 v gedit.

1042
00:46:31,240 --> 00:46:34,610
K dispozici je řada 16 v GDB, a dokonce i
i když tento černý a bílý rozhraní

1043
00:46:34,610 --> 00:46:37,760
není zdaleka tak uživatel
přátelský, to znamená, že

1044
00:46:37,760 --> 00:46:41,680
že linka 16 nebyl vykonán
ještě, ale je to o tom, že je.

1045
00:46:41,680 --> 00:46:46,220
Takže vlastně když jsem typ tisku
x, ne printf, jen print x,

1046
00:46:46,220 --> 00:46:50,730
Mám nějakou falešnou hodnotu tam nula,
protože x nebyl dosud inicializován.

1047
00:46:50,730 --> 00:46:54,760
Takže budu psát dál, nebo, pokud máte
Chcete být fantazie, jen n na další.

1048
00:46:54,760 --> 00:46:59,090
Ale když jsem typ příští vstoupit, nyní
Všimněte si, že se pohybuje na lince 17.

1049
00:46:59,090 --> 00:47:02,840
Takže logicky, pokud jsem popraven
řádek 16 a teď napište print x,

1050
00:47:02,840 --> 00:47:03,640
co bych měl vidět?

1051
00:47:03,640 --> 00:47:04,970

1052
00:47:04,970 --> 00:47:05,520
One.

1053
00:47:05,520 --> 00:47:07,820
>> A teď je to sice matoucí.

1054
00:47:07,820 --> 00:47:11,260
2 dolarů je jen ozdobný způsob, pokud máte
chcete odkázat na tuto hodnotu vyšší,

1055
00:47:11,260 --> 00:47:12,510
můžete říct "dolar podepsat dva."

1056
00:47:12,510 --> 00:47:13,480
Je to jako odkaz zpět.

1057
00:47:13,480 --> 00:47:14,570
Ale teď, prostě ignorovat.

1058
00:47:14,570 --> 00:47:17,070
Co je zajímavé je to, co je
vpravo od rovnítka.

1059
00:47:17,070 --> 00:47:21,000
A teď když jsem psát další zase
a tisk y, měl bych vidět dva.

1060
00:47:21,000 --> 00:47:23,870
Mohu nyní také vytisknout
x znovu, a upřímně řečeno,

1061
00:47:23,870 --> 00:47:27,130
když jsem stále trochu zmatená,
tam, kde jsem, mohu psát seznam pro seznam

1062
00:47:27,130 --> 00:47:30,590
a prostě vidět nějaký kontext kolem
bod Vlastně jsem na.

1063
00:47:30,590 --> 00:47:35,180
A teď můžu psát
Další, a tam je 1 x.

1064
00:47:35,180 --> 00:47:36,300
Teď píšu dál.

1065
00:47:36,300 --> 00:47:37,710
Oh, y je 2.

1066
00:47:37,710 --> 00:47:40,750
A opět, je to matoucí,
protože výstup GDB je

1067
00:47:40,750 --> 00:47:43,044
je smíšeny s vlastní výstup.

1068
00:47:43,044 --> 00:47:45,710
Ale pokud budete mít na mysli tím, že
podíval se tam a zpět na váš kód

1069
00:47:45,710 --> 00:47:47,740
nebo kterým ji z boku
po boku možná budete

1070
00:47:47,740 --> 00:47:51,020
vidět, že ve skutečnosti jsem jen
krokování mého programu.

1071
00:47:51,020 --> 00:47:54,620
>> Povšimněme si ale, co se bude dít dál, a to doslova.

1072
00:47:54,620 --> 00:47:56,380
Tady je linka 22.

1073
00:47:56,380 --> 00:48:01,315
Nech mě jít přes něj, čímž se posouvá o
na 23, a když jsem vytisknout x teď ještě jeden.

1074
00:48:01,315 --> 00:48:03,890
A když jsem vytisknout y teď ještě jeden.

1075
00:48:03,890 --> 00:48:05,820
Takže to není vhodné cvičení.

1076
00:48:05,820 --> 00:48:07,450
Takže pojďme zopakovat to.

1077
00:48:07,450 --> 00:48:10,069
Dovolte mi, abych se vrátit do
opět nahoře a typ běh.

1078
00:48:10,069 --> 00:48:12,110
A to říká program
který je laděn

1079
00:48:12,110 --> 00:48:14,109
začala již
začal od začátku.

1080
00:48:14,109 --> 00:48:15,420
Ano, pojďme to udělat znovu.

1081
00:48:15,420 --> 00:48:22,000
A tentokrát pojďme dělat dál,
další, další, další, další,

1082
00:48:22,000 --> 00:48:24,180
ale teď se věci zajímavé.

1083
00:48:24,180 --> 00:48:27,760
Teď chci vstoupit do
Swap, takže si nemyslím, psát dál.

1084
00:48:27,760 --> 00:48:34,380
Píšu krok, a teď si toho
skočil mi do noswap.c lince 33.

1085
00:48:34,380 --> 00:48:37,240
Mám-li se vrátit do gedit, co je řádek 33?

1086
00:48:37,240 --> 00:48:40,500
To je první skutečný
řádek kódu uvnitř swapu.

1087
00:48:40,500 --> 00:48:44,150
Což je pěkné, protože teď můžu
druh hrabat kolem sebe a dostat zvědavý

1088
00:48:44,150 --> 00:48:46,052
o tom, co se děje opravdu tam.

1089
00:48:46,052 --> 00:48:46,760
Dovolte mi, abych vytisknout 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
Proč tmp mít některé
blázen, falešné odpadky hodnota?

1093
00:48:51,438 --> 00:48:54,579

1094
00:48:54,579 --> 00:48:56,120
Diváků: To nebyl inicializován.

1095
00:48:56,120 --> 00:48:57,150
SPEAKER 1: To nebyl inicializován.

1096
00:48:57,150 --> 00:49:00,270
A skutečně, při spuštění programu,
jste dostal spoustu paměti

1097
00:49:00,270 --> 00:49:03,392
operačním systémem, ale
nebyly inicializovány žádné hodnoty,

1098
00:49:03,392 --> 00:49:05,600
Takže bez ohledu na bity jste
viděl sem, i když je to

1099
00:49:05,600 --> 00:49:07,770
tento šílený velký negativní
číslo, prostě znamená,

1100
00:49:07,770 --> 00:49:10,750
že to jsou zbytky z
některé předchozí využití této paměti RAM,

1101
00:49:10,750 --> 00:49:13,050
i když nemám
já ho potřeboval ještě.

1102
00:49:13,050 --> 00:49:17,086
Takže teď jdu do toho pusťte a typ
další, a když jsem teď psát tiskové tmp,

1103
00:49:17,086 --> 00:49:17,835
co bych měl vidět?

1104
00:49:17,835 --> 00:49:19,570

1105
00:49:19,570 --> 00:49:23,360
Ať už je hodnota byla
je první argument, jen

1106
00:49:23,360 --> 00:49:25,550
jako X byl první
co byly přeneseny do,

1107
00:49:25,550 --> 00:49:30,450
tak a x by měla být stejná,
tak tisknout tmp by mi vytisknout jeden.

1108
00:49:30,450 --> 00:49:36,360
>> Takže to, co uvidíte v problémové sady
tři je výukový program svého druhu na GDB,

1109
00:49:36,360 --> 00:49:40,020
ale si uvědomit, že toto je začátek
z pohledu na nástroj, který bude skutečně

1110
00:49:40,020 --> 00:49:42,774
pomoci při řešení problémů
tak mnohem efektivněji.

1111
00:49:42,774 --> 00:49:44,690
Co jsme nakonec
dělat ve středu

1112
00:49:44,690 --> 00:49:48,180
se začne loupat o několik vrstev
a odstranit některé tréninkové kola.

1113
00:49:48,180 --> 00:49:50,496
To, čemu se říká řetězec, který
jsme delší dobu používat,

1114
00:49:50,496 --> 00:49:53,370
jdeme pomalu brát pryč
od vás a začít mluvit o

1115
00:49:53,370 --> 00:49:55,725
něco esoterického
známý jako char *,

1116
00:49:55,725 --> 00:49:59,550
ale budeme to udělat pěkný a
nejprve mírně, i když ukazatele,

1117
00:49:59,550 --> 00:50:02,730
jak se jim říká, můžete udělat nějaké
velmi špatné věci, pokud by byl zneužit,

1118
00:50:02,730 --> 00:50:06,040
při pohledu na malou claymation od
náš přítel Nick Parlante ze Stanfordu

1119
00:50:06,040 --> 00:50:09,670
University, profesor v počítači
vědy, který dal dohromady tento náhled

1120
00:50:09,670 --> 00:50:11,075
toho, co je přijde tuto středu.

1121
00:50:11,075 --> 00:50:12,196

1122
00:50:12,196 --> 00:50:13,400
>> [PŘEHRÁVÁNÍ]

1123
00:50:13,400 --> 00:50:13,900
Hej, Binky.

1124
00:50:13,900 --> 00:50:14,930

1125
00:50:14,930 --> 00:50:15,780
Probuď se.

1126
00:50:15,780 --> 00:50:17,240
Je čas na ukazatel zábavy.

1127
00:50:17,240 --> 00:50:18,260

1128
00:50:18,260 --> 00:50:19,350
>> Co je to?

1129
00:50:19,350 --> 00:50:21,150
Další informace o ukazateli?

1130
00:50:21,150 --> 00:50:22,050
Oh, dobrota!

1131
00:50:22,050 --> 00:50:22,897

1132
00:50:22,897 --> 00:50:23,730
[END VIDEOPŘEHRÁVÁNÍ]

1133
00:50:23,730 --> 00:50:25,396
SPEAKER 1: To na vás čeká ve středu.

1134
00:50:25,396 --> 00:50:26,440
Uvidíme se pak.

1135
00:50:26,440 --> 00:50:27,106
[PŘEHRÁVÁNÍ]

1136
00:50:27,106 --> 00:50:30,420
-A Teď, hluboké myšlenky,
od Daven Farnham.

1137
00:50:30,420 --> 00:50:33,980

1138
00:50:33,980 --> 00:50:35,900
>> Proč se učíme C?

1139
00:50:35,900 --> 00:50:36,785
Proč ne +?

1140
00:50:36,785 --> 00:50:38,550

1141
00:50:38,550 --> 00:50:40,910
>> [SMÍCH]

1142
00:50:40,910 --> 00:50:42,160
>> [END VIDEOPŘEHRÁVÁNÍ]