1
00:00:00,000 --> 00:00:00,030

2
00:00:00,030 --> 00:00:00,460
>> David MALAN: Lahat ng karapatan.

3
00:00:00,460 --> 00:00:01,094
Kami ay bumalik.

4
00:00:01,094 --> 00:00:04,260
Kaya sa segment na ito sa programming kung ano
Akala ko gusto naming gawin ay isang halo ng mga bagay.

5
00:00:04,260 --> 00:00:06,340
One, gawin ang isang maliit na bit
ng isang bagay na kamay-on,

6
00:00:06,340 --> 00:00:08,690
albeit paggamit ng isang mas mapaglaro
programming environment--

7
00:00:08,690 --> 00:00:11,620
isa na ay demonstrative ng
eksakto ang uri ng mga ideya

8
00:00:11,620 --> 00:00:14,220
kami ay pakikipag-usap tungkol sa,
ngunit ng kaunti pa pormal.

9
00:00:14,220 --> 00:00:18,200
Two, tingnan ang ilan sa
ang mga teknikal na paraan

10
00:00:18,200 --> 00:00:21,520
na ang isang programmer ay tunay na malutas
problema tulad ng mga naghahanap problema

11
00:00:21,520 --> 00:00:24,530
na kami ay tumingin sa bago at
din ng isang mas panimula

12
00:00:24,530 --> 00:00:26,020
kagiliw-giliw na problema ng pag-uuri.

13
00:00:26,020 --> 00:00:28,840
>> Lang namin ipinapalagay mula sa makakuha ng pumunta
na na phone book ay pinagsunod-sunod,

14
00:00:28,840 --> 00:00:31,980
ngunit na nag-iisa ay talagang uri ng isang
mahirap problema sa maraming iba't ibang paraan

15
00:00:31,980 --> 00:00:32,479
upang malutas ito.

16
00:00:32,479 --> 00:00:34,366
Kaya gagamitin namin ang mga ito bilang
isang klase ng mga problema

17
00:00:34,366 --> 00:00:36,740
kinatawan ng mga bagay na
maaaring lutasin sa pangkalahatan.

18
00:00:36,740 --> 00:00:38,980
At pagkatapos ay gagamitin namin makipag-usap
tungkol sa ilang mga detalye kung ano ang

19
00:00:38,980 --> 00:00:42,360
ay tinatawag na data structures--
may interes paraan tulad listahan ng link

20
00:00:42,360 --> 00:00:46,290
at hash talahanayan at mga puno na
isang programmer gagawin talaga

21
00:00:46,290 --> 00:00:48,890
gamitin at sa pangkalahatan gamitin
sa isang whiteboard upang ipinta

22
00:00:48,890 --> 00:00:51,840
isang larawan ng kung ano ang kanyang
Envisions para sa pagpapatupad

23
00:00:51,840 --> 00:00:52,980
ilang piraso ng software.

24
00:00:52,980 --> 00:00:55,130
>> Kaya sabihin gawin ang hands-on bahaging muna.

25
00:00:55,130 --> 00:01:00,090
Kaya lang makuha ang iyong mga kamay marumi na may isang
kapaligiran tinatawag scratch.mit.edu.

26
00:01:00,090 --> 00:01:02,636
Ito ay isang kasangkapan na ginagamit namin
sa aming undergraduate class.

27
00:01:02,636 --> 00:01:04,510
Kahit na ito ay naka-disenyo
para sa edad 12 at pataas,

28
00:01:04,510 --> 00:01:07,570
ginagamit namin ito para sa up
bahagi ng na lubos ng kaunti

29
00:01:07,570 --> 00:01:10,020
dahil ito ay isang nice, fun
graphical na paraan ng pag-aaral

30
00:01:10,020 --> 00:01:12,160
isang maliit na bagay tungkol sa programming.

31
00:01:12,160 --> 00:01:17,600
Kaya magtungo sa URL na iyon, kung saan mo
dapat makita ang isang page lubos na tulad nito,

32
00:01:17,600 --> 00:01:23,330
at sige at i-click
Sumali Scratch sa kanang tuktok

33
00:01:23,330 --> 00:01:28,300
at pumili ng isang username at isang
password at sa huli makakuha ng iyong sarili

34
00:01:28,300 --> 00:01:29,970
isang account-- scratch.mit.edu.

35
00:01:29,970 --> 00:01:32,165

36
00:01:32,165 --> 00:01:34,665
Akala ko gusto ko bang gamitin ito bilang isang
pagkakataon unang upang ipakita na ito.

37
00:01:34,665 --> 00:01:39,120
Ang isang tanong ay dumating up sa panahon ng pahinga
tungkol sa kung ano ang tunay na code ganito ang hitsura.

38
00:01:39,120 --> 00:01:41,315
At kami ay pakikipag-usap
pagkatapos patamaan tungkol sa C,

39
00:01:41,315 --> 00:01:45,060
in particular-- lalo na ng isang
mas mababang antas sa isang mas lumang wika.

40
00:01:45,060 --> 00:01:47,750
At ako lamang ay isang mabilis
Paghahanap sa Google upang mahanap C code

41
00:01:47,750 --> 00:01:51,574
para sa binary paghahanap, ang algorithm na kami
magamit upang maghanap na phone book nang mas maaga.

42
00:01:51,574 --> 00:01:54,240
Ang partikular na halimbawa, ng mga kurso,
ay hindi paghahanap ng isang phone book.

43
00:01:54,240 --> 00:01:57,840
Ito lamang naghahanap ng isang buong grupo ng mga
numero sa memory ng computer.

44
00:01:57,840 --> 00:02:01,000
Ngunit kung nais mong lamang makakuha ng isang visual
kahulugan ng kung ano ang isang aktwal na mga programa

45
00:02:01,000 --> 00:02:05,370
wika ganito ang hitsura, ang hitsura nito
isang maliit na bagay tulad nito.

46
00:02:05,370 --> 00:02:09,759
Kaya ito ay tungkol sa 20-plus,
30 o kaya mga linya ng code,

47
00:02:09,759 --> 00:02:12,640
ngunit ang pag-uusap namin
ay nagkakaroon ng higit sa pahinga

48
00:02:12,640 --> 00:02:16,000
ay tungkol sa kung paano ito aktwal na
makakakuha morphed sa mga zero at mga

49
00:02:16,000 --> 00:02:19,200
at kung hindi lamang ang maaari mong ibalik sa dati na
proseso at pumunta mula zero at mga

50
00:02:19,200 --> 00:02:20,210
i-back sa code.

51
00:02:20,210 --> 00:02:22,620
>> Sa kasamaang palad, ang proseso
ay kaya transformative

52
00:02:22,620 --> 00:02:24,890
na ito ay isang pulutong mas madali kaysa sa sinabi tapos na.

53
00:02:24,890 --> 00:02:29,400
Nagpunta ako maaga at aktwal na naka
na programa, Binary Search,

54
00:02:29,400 --> 00:02:32,700
sa mga zero at mga bago sa pamamagitan ng paraan ng isang
programa na tinatawag na Compiler Ang na ako

55
00:02:32,700 --> 00:02:34,400
mangyari na magkaroon dito mismo sa aking Mac.

56
00:02:34,400 --> 00:02:37,850
At kung pagtingin mo ang mga screen
dito, mismong tumututok

57
00:02:37,850 --> 00:02:43,520
sa mga middle anim na haligi lamang,
makikita mo lamang zero at mga.

58
00:02:43,520 --> 00:02:48,290
At ang mga ay ang mga zero at mga bago na
gumawa ng sulat eksakto na searching programa.

59
00:02:48,290 --> 00:02:53,720
>> At sa gayon ang bawat tipak ng limang bits,
bawat byte ng mga zero at mga bago dito,

60
00:02:53,720 --> 00:02:57,310
kumakatawan ang ilang mga pagtuturo
karaniwang sa loob ng isang computer.

61
00:02:57,310 --> 00:03:00,730
At sa katunayan, kung ka na marinig ang
marketing slogan "Intel loob" - na,

62
00:03:00,730 --> 00:03:04,610
siyempre, ay nangangahulugan lamang mayroon kang isang
Intel CPU o utak sa loob ng computer.

63
00:03:04,610 --> 00:03:08,000
At kung ano ang ibig sabihin nito upang maging isang CPU ay
na ikaw ay may isang pagtuturo set,

64
00:03:08,000 --> 00:03:08,840
kaya na magsalita.

65
00:03:08,840 --> 00:03:11,620
>> Bawat CPU sa mundo, marami sa
ang mga ito na ginawa ng Intel mga araw na ito,

66
00:03:11,620 --> 00:03:13,690
nauunawaan ng isang may hangganan
bilang ng mga tagubilin.

67
00:03:13,690 --> 00:03:18,690
At ang mga tagubilin ay kaya mababa na antas
habang nagdadagdag ito ng dalawang numero ng magkasama,

68
00:03:18,690 --> 00:03:22,560
multiply ang dalawang numero ng magkasama,
galaw ng mga piraso ng data mula dito

69
00:03:22,560 --> 00:03:27,340
sa dito sa memory, kundi itong
impormasyon mula dito sa dito sa memorya,

70
00:03:27,340 --> 00:03:32,200
at iba pa forth-- kaya napaka, napaka
mababang antas, halos electronic detalye.

71
00:03:32,200 --> 00:03:34,780
Ngunit sa mga mathematical
operations kaisa

72
00:03:34,780 --> 00:03:37,410
sa kung ano ang napag-usapan namin kanina,
ang representasyon ng data

73
00:03:37,410 --> 00:03:40,450
bilang mga zero at mga, maaari
kang bumuo ng up ang lahat ng bagay

74
00:03:40,450 --> 00:03:44,180
na ang isang computer ay maaaring gawin ngayon, kung
ito ay tekstuwal, graphical, musical,

75
00:03:44,180 --> 00:03:45,580
o kung hindi man.

76
00:03:45,580 --> 00:03:49,450
>> Kaya ito ay mas madali upang makakuha
nawala sa mga damo ng mabilis.

77
00:03:49,450 --> 00:03:52,150
At mayroong isang pulutong ng mga
syntactical hamon

78
00:03:52,150 --> 00:03:56,630
kung saan kung gumawa ka ng ang pinakasimpleng,
stupidest ng typos wala sa mga programa

79
00:03:56,630 --> 00:03:57,860
gagana kung ano pa man.

80
00:03:57,860 --> 00:04:00,366
At kaya sa halip ng paggamit ng isang
wika tulad ng C na ito umaga,

81
00:04:00,366 --> 00:04:02,240
Akala ko ay ito ay
mas masaya upang aktwal na gawin

82
00:04:02,240 --> 00:04:04,840
isang bagay na mas visual, na kung saan
habang dinisenyo para sa mga bata

83
00:04:04,840 --> 00:04:08,079
ay talagang isang perpektong paghahayag
ng isang aktwal na programming

84
00:04:08,079 --> 00:04:10,370
language-- lang ang mangyayari sa
gamitin ang mga larawan sa halip ng teksto

85
00:04:10,370 --> 00:04:11,710
upang kumatawan sa mga ideya.

86
00:04:11,710 --> 00:04:15,470
>> Kaya sa sandaling ikaw ay sa katunayan ay may isang
account sa scratch.mit.edu,

87
00:04:15,470 --> 00:04:21,070
i-click ang pindutan ng Gumawa
sa pinakamataas na naiwan, sa mga site.

88
00:04:21,070 --> 00:04:24,620
At dapat mong makita ang isang kapaligiran tulad ng
ang isa ako tungkol sa upang makita ang sa aking screen

89
00:04:24,620 --> 00:04:26,310
dito.

90
00:04:26,310 --> 00:04:29,350
At kami gastusin lamang ng isang maliit
bit ng oras sa paglalaro dito.

91
00:04:29,350 --> 00:04:34,080
Sabihin makita kung hindi lahat kami ay maaaring malutas ang ilang
problema nang magkasama sa mga sumusunod na paraan.

92
00:04:34,080 --> 00:04:39,420
>> Kaya kung ano ang makikita mo sa loob ng
environment-- at talagang lang basta hayaan

93
00:04:39,420 --> 00:04:40,050
akin i-pause.

94
00:04:40,050 --> 00:04:42,680
Ay sinuman na hindi dito?

95
00:04:42,680 --> 00:04:45,070
Hindi dito?

96
00:04:45,070 --> 00:04:45,800
OK.

97
00:04:45,800 --> 00:04:49,030
Kaya hayaan mo akong ituro ng ilang
mga katangian ng environment na ito.

98
00:04:49,030 --> 00:04:55,024
>> Kaya sa kaliwang tuktok ng screen, kami
may stage ni Scratch, kaya na magsalita.

99
00:04:55,024 --> 00:04:57,440
Scratch ay hindi lamang ang pangalan
ng programming language;

100
00:04:57,440 --> 00:05:00,356
ito ay din ang pangalan ng pusa na
nakikita mo sa pamamagitan ng default doon sa orange.

101
00:05:00,356 --> 00:05:02,160
Siya ay nasa isang yugto, kaya
marami tulad ng inilarawan ko

102
00:05:02,160 --> 00:05:05,770
ang pagong mas maaga bilang kabilang sa
hugis-parihaba white board kapaligiran.

103
00:05:05,770 --> 00:05:09,800
Mundo na ito pusa ay nakakulong ganap
sa na rectangle up tuktok doon.

104
00:05:09,800 --> 00:05:12,210
>> Samantala, sa kanan
kamay gilid dito, ito ay

105
00:05:12,210 --> 00:05:15,610
lamang ng isang script area,
blangkong slate kung ikaw ay.

106
00:05:15,610 --> 00:05:18,590
Ito ay kung saan kami ay pagpunta sa sumulat
ang aming mga programa sa loob lamang ng ilang sandali.

107
00:05:18,590 --> 00:05:22,935
At ang malaking bloke na dapat namin
gamitin upang isulat ito program-- ang puzzle

108
00:05:22,935 --> 00:05:25,310
piraso, kung ikaw will-- ay
mga karapatan dito sa gitna,

109
00:05:25,310 --> 00:05:27,500
at sila ay ikinategorya
sa pamamagitan ng pag-andar.

110
00:05:27,500 --> 00:05:31,000
Kaya, halimbawa, ako pagpunta sa sige
at nagpapakita ng hindi bababa sa isa sa mga.

111
00:05:31,000 --> 00:05:33,690
Ako pagpunta sa sige at i-click ang
Control kategoryang up tuktok.

112
00:05:33,690 --> 00:05:35,720
>> Kaya ito ang mga kategorya up tuktok.

113
00:05:35,720 --> 00:05:39,410
Pupunta ako sa i-click ang Control kategorya.

114
00:05:39,410 --> 00:05:44,020
Sa halip, ako pagpunta sa i-click ang Mga Kaganapan
kategorya, ang pinakaunang isa up tuktok.

115
00:05:44,020 --> 00:05:47,790
At kung gusto mong upang sundin kasama kahit
tulad ng ginagawa namin ito, ikaw ay lubos na maligayang pagdating sa.

116
00:05:47,790 --> 00:05:52,180
Pupunta ako sa i-click at i-drag ito
unang isa, "kapag berdeng bandila click."

117
00:05:52,180 --> 00:05:58,410
At pagkatapos ay ako pagpunta sa drop ito lamang
halos sa tuktok ng aking blangko slates.

118
00:05:58,410 --> 00:06:01,450
>> At kung ano ang maganda tungkol Scratch
ay na ito palaisipan piraso, kapag

119
00:06:01,450 --> 00:06:04,560
interlocked sa iba pang mga puzzle
piraso, ay pagpunta sa gawin literal

120
00:06:04,560 --> 00:06:06,460
kung ano ang mga piraso ng puzzle sabihin na gawin.

121
00:06:06,460 --> 00:06:09,710
Kaya, halimbawa, Scratch ay tama
ngayon sa gitna ng kanyang mundo.

122
00:06:09,710 --> 00:06:14,660
Ako pagpunta sa sige at piliin ang
ngayon, sabihin nating, ang kategorya Motion,

123
00:06:14,660 --> 00:06:18,000
kung nais mong upang gawin ang
same-- kategoryang Motion.

124
00:06:18,000 --> 00:06:20,430
At ngayon mapansin mayroon akong isang buong
grupo ng mga piraso ng puzzle dito

125
00:06:20,430 --> 00:06:23,370
na, muli, uri ng gawin kung ano ang sinasabi nila.

126
00:06:23,370 --> 00:06:28,110
At ako pagpunta sa sige at i-drag and
drop ang ilipat bloke karapatan sa paglipas dito.

127
00:06:28,110 --> 00:06:31,860
>> At mapansin na sa lalong madaling makakuha ka
malapit sa ibaba ng "green bandila

128
00:06:31,860 --> 00:06:34,580
nag-click "na pindutan, notice
kung paano ang isang puting linya ay lilitaw,

129
00:06:34,580 --> 00:06:36,950
na parang ito ay halos
magnetic, ito ay nagnanais na pumunta doon.

130
00:06:36,950 --> 00:06:43,070
Ipaalam lamang sa pumunta, at ito ay snap
sama-sama at ang mga hugis ay tutugma.

131
00:06:43,070 --> 00:06:46,620
At ngayon maaari mong marahil halos
hulaan kung saan kami ay pagpunta sa mga ito.

132
00:06:46,620 --> 00:06:51,570
>> Kung tumingin ka sa mga Scratch stage
sa paglipas dito at tumingin sa itaas ng mga ito,

133
00:06:51,570 --> 00:06:55,142
makikita mo ang isang pulang ilaw, isang
itigil-sign, at isang green flag.

134
00:06:55,142 --> 00:06:57,100
At ako pagpunta sa sige
at panoorin ang aking screen--

135
00:06:57,100 --> 00:06:58,460
para sa sandali lamang, kung maaari mong.

136
00:06:58,460 --> 00:07:01,960
Pupunta ako sa i-click ang
berdeng bandila sa ngayon,

137
00:07:01,960 --> 00:07:07,850
at kaniyang kinilos kung ano ay lilitaw upang maging 10 mga hakbang
o 10 pixels, 10 mga tuldok, sa screen.

138
00:07:07,850 --> 00:07:13,390
>> At kaya hindi na kapana-panabik,
ngunit hayaan mo akong magpanukala

139
00:07:13,390 --> 00:07:17,440
walang kahit pagtuturo na ito, kailangan lang
gamit ang sariling iyong sariling intuition-- let

140
00:07:17,440 --> 00:07:22,560
akong magpanukala na figure out ka kung paano
gumawa Scratch lakad karapatan off ang yugto.

141
00:07:22,560 --> 00:07:28,700
Nakarating siya gumawa ng paraan para sa kanang bahagi ng
screen, ang lahat ng mga paraan sa kanan.

142
00:07:28,700 --> 00:07:32,200
Hayaan akong bigyan ka ng ilang sandali
o kaya upang bunuin iyon.

143
00:07:32,200 --> 00:07:37,681
Baka gusto mong kumuha ng isang pagtingin
sa iba pang mga kategorya ng mga bloke.

144
00:07:37,681 --> 00:07:38,180
Lahat tama.

145
00:07:38,180 --> 00:07:41,290
Kaya lang sa paglalagom, kapag mayroon kaming
ang berdeng bandila click dito

146
00:07:41,290 --> 00:07:44,850
at ilipat 10 hakbang ay ang
lamang pagtuturo, sa bawat oras na ko

147
00:07:44,850 --> 00:07:46,720
i-click ang berdeng bandila, kung ano ang nangyayari?

148
00:07:46,720 --> 00:07:50,070
Well, na tumatakbo ang aking programa.

149
00:07:50,070 --> 00:07:52,450
Kaya kaya kong gawin ito
siguro 10 beses mano-mano,

150
00:07:52,450 --> 00:07:55,130
ngunit ito nararamdaman ng kaunti
bit hackish, kaya na magsalita,

151
00:07:55,130 --> 00:07:57,480
kung saan hindi ako talagang
paglutas ng problema.

152
00:07:57,480 --> 00:08:00,530
Ako lang sinusubukan muli at
muli at muli at muli

153
00:08:00,530 --> 00:08:03,180
hanggang ako uri ng aksidenteng
makamit ang direktiba

154
00:08:03,180 --> 00:08:05,560
na ako magse-set out upang makamit mas maaga.

155
00:08:05,560 --> 00:08:08,200
>> Ngunit alam namin mula sa aming mga
pseudocode mas maaga na may

156
00:08:08,200 --> 00:08:11,870
ito paniwala sa programming ng looping,
ginagawa nang paulit-ulit ng isang bagay.

157
00:08:11,870 --> 00:08:14,888
At gayon din nakita ko na ang isang grupo ng mga ka
Naabot para sa kung ano puzzle piraso?

158
00:08:14,888 --> 00:08:17,870

159
00:08:17,870 --> 00:08:18,730
Ulitin hanggang.

160
00:08:18,730 --> 00:08:21,400
Kaya maaari naming gawin ang isang bagay
tulad ulitin hanggang.

161
00:08:21,400 --> 00:08:23,760
At kung ano ang ginawa mo ulitin hanggang eksakto?

162
00:08:23,760 --> 00:08:27,720

163
00:08:27,720 --> 00:08:28,540
>> OK.

164
00:08:28,540 --> 00:08:31,974
At hayaan mo akong pumunta sa isang bagay na
medyo mas simple para sa mga lamang ng ilang sandali.

165
00:08:31,974 --> 00:08:33,140
Hayaan akong magpatuloy at gawin ito.

166
00:08:33,140 --> 00:08:35,559
Pansinin na, tulad ng maaari kang magkaroon ng
natuklasan sa ilalim Control,

167
00:08:35,559 --> 00:08:38,409
diyan ay ito repeat block, kung saan
ay hindi mukhang ito ay na malaki.

168
00:08:38,409 --> 00:08:41,039
Mayroong hindi magkano ang kuwarto sa
pagitan ng mga dalawang dilaw na linya.

169
00:08:41,039 --> 00:08:43,539
Ngunit bilang ang ilan sa inyo ay maaaring magkaroon ng
napansin, kung i-drag mo at drop,

170
00:08:43,539 --> 00:08:45,150
paunawa kung paano ito ay lumalaki upang punan ang hugis.

171
00:08:45,150 --> 00:08:46,274
>> At maaari ka ring Cram higit pa.

172
00:08:46,274 --> 00:08:48,670
Makikita ito lamang panatilihin ang lumalaking kung
i-drag mo at mag-hover sa ibabaw nito.

173
00:08:48,670 --> 00:08:51,110
At hindi ko alam kung ano ang
pinakamahusay na dito, kaya hayaan

174
00:08:51,110 --> 00:08:54,760
akin ng hindi bababa ulitin limang beses, para sa
halimbawa, at pagkatapos ay bumalik sa entablado

175
00:08:54,760 --> 00:08:56,720
at i-click ang berdeng bandila.

176
00:08:56,720 --> 00:08:59,110
At ngayon mapansin ito ay hindi pa doon.

177
00:08:59,110 --> 00:09:02,400
>> Ngayon ilan sa inyo iminungkahi, bilang
Victoria lamang ay, ulitin 10 beses.

178
00:09:02,400 --> 00:09:05,140
At na sa pangkalahatan ay
kumuha sa kanya lahat ng paraan,

179
00:09:05,140 --> 00:09:10,510
ngunit gagawin hindi ba ng isang mas matatag na
paraan kaysa arbitrarily figuring out

180
00:09:10,510 --> 00:09:12,640
kung gaano karaming mga gumagalaw upang gumawa?

181
00:09:12,640 --> 00:09:17,680
Ano ang maaaring maging isang mas mahusay na block
kaysa ulitin 10 beses na ito?

182
00:09:17,680 --> 00:09:20,380
>> Oo, kaya kung bakit hindi gumawa ng isang bagay magpakailanman?

183
00:09:20,380 --> 00:09:24,390
At ngayon hayaan mo akong ilipat ito palaisipan piraso
sa loob doon at kumuha alisan ng isang ito.

184
00:09:24,390 --> 00:09:28,300
Ngayon pansinin kahit na kung saan Scratch
pagsisimula, siya ay napupunta sa gilid.

185
00:09:28,300 --> 00:09:30,700
At thankfully MIT,
na gumagawa ng simula, lamang

186
00:09:30,700 --> 00:09:33,190
tinitiyak na siya ay hindi kailanman
disappears ganap.

187
00:09:33,190 --> 00:09:35,360
Maaari mong palaging grab kanyang buntot.

188
00:09:35,360 --> 00:09:37,680
>> At lamang intuitively,
bakit niya panatilihin ang paglipat?

189
00:09:37,680 --> 00:09:38,892
Anong nangyayari dito?

190
00:09:38,892 --> 00:09:41,440

191
00:09:41,440 --> 00:09:43,824
Siya tila sa may tumigil, ngunit
pagkatapos ay kung ako pick up at i-drag

192
00:09:43,824 --> 00:09:45,240
siya mapigil ang kinakapos upang pumunta sa banda roon.

193
00:09:45,240 --> 00:09:46,123
Bakit na?

194
00:09:46,123 --> 00:09:51,610

195
00:09:51,610 --> 00:09:54,360
Truly, isang computer ay literal
pagpunta sa gawin kung ano ang iyong sabihin sa ito upang gawin.

196
00:09:54,360 --> 00:09:58,380
Kaya kung sinabi mo ito nang mas maaga gawin ang
sumusunod na bagay magpakailanman, ilipat 10 mga hakbang,

197
00:09:58,380 --> 00:10:01,860
ito ay pagpunta upang panatilihin ang pagpunta at pagpunta
hanggang maabot ko ang pulang stop sign

198
00:10:01,860 --> 00:10:04,620
at itigil ang programa sa kabuuan.

199
00:10:04,620 --> 00:10:06,610
>> Kaya kahit na ikaw ay hindi
gawin ito, kung paano kaya kong

200
00:10:06,610 --> 00:10:09,510
gumawa Scratch ilipat mas mabilis
sa kabila ng screen?

201
00:10:09,510 --> 00:10:12,060

202
00:10:12,060 --> 00:10:13,280
Higit pang mga hakbang, right?

203
00:10:13,280 --> 00:10:15,710
Kaya sa halip ng paggawa ng 10
sa isang pagkakataon, bakit hindi namin

204
00:10:15,710 --> 00:10:20,100
sige at baguhin ito to--
ano ang gusto mong propose-- 50?

205
00:10:20,100 --> 00:10:24,410
Kaya ngayon ako pagpunta sa i-click ang berdeng
flag, at sa katunayan, siya ay napupunta talagang mabilis.

206
00:10:24,410 --> 00:10:27,180
>> At ito, siyempre, ay lamang
isang paghahayag ng animation.

207
00:10:27,180 --> 00:10:28,060
Ano ang animation?

208
00:10:28,060 --> 00:10:33,090
Lamang Ito ay nagpapakita sa iyo ng tao isang
ang maramihang mga imahe pa rin talaga,

209
00:10:33,090 --> 00:10:34,160
tunay, tunay mabilis.

210
00:10:34,160 --> 00:10:36,500
At kaya kung kami ay lamang na nagsasabi sa
sa kanya upang ilipat sa karagdagang hakbang,

211
00:10:36,500 --> 00:10:39,750
lang namin sa pag-ang epekto ay upang
pagbabago kung saan siya ay sa screen

212
00:10:39,750 --> 00:10:42,900
lahat ng mga mas mabilis na sa bawat yunit ng oras.

213
00:10:42,900 --> 00:10:46,454
>> Ngayon ang susunod na hamon na aking iminungkahi
ay upang magkaroon ng kanya bounce off sa gilid.

214
00:10:46,454 --> 00:10:49,120
At walang pag-alam kung ano ang palaisipan
piraso exist-- dahil ito ay pagmultahin

215
00:10:49,120 --> 00:10:53,030
kung hindi mo makakuha ng sa
yugto ng challenge-- ano

216
00:10:53,030 --> 00:10:54,280
ang gusto mong gawin intuitively?

217
00:10:54,280 --> 00:10:58,030
Paano kami ay may kanya bounce pabalik-
balik, sa pagitan ng kaliwa at kanang?

218
00:10:58,030 --> 00:11:02,630

219
00:11:02,630 --> 00:11:03,810
>> Yeah.

220
00:11:03,810 --> 00:11:05,680
Kaya kailangan namin ng ilang mga uri
ng kalagayan, at kami

221
00:11:05,680 --> 00:11:09,710
mukhang may conditionals, kaya na
makipag-usap, sa ilalim ng kategorya Control.

222
00:11:09,710 --> 00:11:14,110
Alin sa mga bloke
namin malamang na gusto?

223
00:11:14,110 --> 00:11:15,200
Yeah, siguro "kung, pagkatapos."

224
00:11:15,200 --> 00:11:18,780
Kaya mapapansin na kabilang sa mga kulay-dilaw na mga bloke
ang mayroon kami dito, diyan ay ito "kung"

225
00:11:18,780 --> 00:11:23,920
o ito "kung, sino pa ang paririto" block na habilin
daan sa amin upang gumawa ng isang desisyon na gawin ito

226
00:11:23,920 --> 00:11:25,000
o upang gawin iyon.

227
00:11:25,000 --> 00:11:27,380
At maaari mong kahit na nest ang mga ito
upang gawin ang maramihang mga bagay na ito.

228
00:11:27,380 --> 00:11:34,910
O kung hindi mo na pa nawala dito,
sige sa kategorya Sensing

229
00:11:34,910 --> 00:11:39,612
at- sabihin makita kung ito ay dito.

230
00:11:39,612 --> 00:11:43,050

231
00:11:43,050 --> 00:11:52,050
>> Kaya kung ano ang bloke ay maaaring maging kapaki-pakinabang dito
upang makita kung siya ay off ang yugto?

232
00:11:52,050 --> 00:11:56,740
Yeah, mapapansin na ang ilan sa mga bloke
maaaring parametrized, kaya na magsalita.

233
00:11:56,740 --> 00:12:00,706
Sila ay maaaring uri ng customized na, hindi
hindi katulad HTML kahapon na may mga katangian,

234
00:12:00,706 --> 00:12:03,330
kung saan ang mga katangian uri ng
i-customize ang pag-uugali ng isang tag.

235
00:12:03,330 --> 00:12:08,880
Katulad nito dito, maaari ko grab ito hinahawakan
block at pagbabago at tanungin ang tanong,

236
00:12:08,880 --> 00:12:11,500
ikaw ay pagpindot sa mouse
pointer tulad ng mga cursor

237
00:12:11,500 --> 00:12:13,250
o ikaw ay pagpindot sa gilid?

238
00:12:13,250 --> 00:12:15,210
>> Kaya hayaan mo akong pumunta sa at gawin ito.

239
00:12:15,210 --> 00:12:18,130
Pupunta ako upang mag-zoom out para sa isang sandali.

240
00:12:18,130 --> 00:12:21,320
Hayaan akong sunggaban ito palaisipan piraso
dito, ito piraso ng puzzle na ito,

241
00:12:21,320 --> 00:12:24,570
at ako pagpunta sa kaguluhan
up ang mga ito para sa sandali lamang.

242
00:12:24,570 --> 00:12:27,620
Pupunta ako upang ilipat ito,
baguhin ito sa paghawak edge,

243
00:12:27,620 --> 00:12:38,590
at ako pagpunta sa paggalaw gawin ito.

244
00:12:38,590 --> 00:12:40,490
Kaya narito ang ilang mga sangkap.

245
00:12:40,490 --> 00:12:42,570
Sa tingin ko Mayroon akong ang lahat ng gusto ko.

246
00:12:42,570 --> 00:12:47,710
>> Gusto isang tao na gusto upang ipanukala kung paano ko
maaaring kumonekta mga siguro itaas hanggang sa ibaba

247
00:12:47,710 --> 00:12:52,020
upang malutas ang problema ng pagkakaroon ng
Scratch ilipat karapatan sa kaliwa papunta sa kanan upang

248
00:12:52,020 --> 00:12:57,020
kaliwa papunta sa kanan papuntang kaliwa, ang bawat
oras lamang nagba-bounce off ang mga pader?

249
00:12:57,020 --> 00:12:58,050
Ano ang gusto kong gawin?

250
00:12:58,050 --> 00:13:01,097
Aling block ang dapat kong kumonekta sa
"Kapag berdeng bandila click unang"?

251
00:13:01,097 --> 00:13:04,060

252
00:13:04,060 --> 00:13:06,200
>> OK, kaya sabihin magsimula sa ang "walang hanggan."

253
00:13:06,200 --> 00:13:07,170
Ano ang napupunta sa loob ng susunod?

254
00:13:07,170 --> 00:13:10,290
Ibang tao.

255
00:13:10,290 --> 00:13:11,850
OK, ilipat hakbang.

256
00:13:11,850 --> 00:13:12,350
Lahat tama.

257
00:13:12,350 --> 00:13:14,470
Tapos ano?

258
00:13:14,470 --> 00:13:15,120
Kaya pagkatapos ay ang kung.

259
00:13:15,120 --> 00:13:17,720
At mapansin, kahit na ito asta
Napapagitnaan magkasama mahigpit,

260
00:13:17,720 --> 00:13:19,500
ito lamang lumago upang punan.

261
00:13:19,500 --> 00:13:21,500
Ito ay lamang tumalon sa kung saan gusto ko ito.

262
00:13:21,500 --> 00:13:25,920
>> At ano ang gagawin ko bang ilagay sa pagitan ng
ang kung at ang pagkatapos?

263
00:13:25,920 --> 00:13:27,180
Marahil "kung hawakan gilid."

264
00:13:27,180 --> 00:13:31,800
At pansinin, muli, ito ay masyadong malaki
para dito, ngunit ito ay lumago upang punan.

265
00:13:31,800 --> 00:13:35,002
At pagkatapos ay i-15 degrees?

266
00:13:35,002 --> 00:13:35,710
Ilang degrees?

267
00:13:35,710 --> 00:13:38,800

268
00:13:38,800 --> 00:13:41,196
Oo, kaya 180 ay iikot
akin ang lahat ng mga paraan sa paligid.

269
00:13:41,196 --> 00:13:42,570
Kaya sabihin makita kung ako got ang karapatan na ito.

270
00:13:42,570 --> 00:13:43,930
Hayaan akong mag-zoom out.

271
00:13:43,930 --> 00:13:45,130
>> Hayaan akong i-drag Scratch up.

272
00:13:45,130 --> 00:13:50,030
Kaya siya ay isang maliit na pangit
ngayon, ngunit iyan ay pagmultahin.

273
00:13:50,030 --> 00:13:52,231
Paano ko i-reset sa kanya madali?

274
00:13:52,231 --> 00:13:59,879

275
00:13:59,879 --> 00:14:01,045
Ako pagpunta sa impostor na bahagyang.

276
00:14:01,045 --> 00:14:04,074

277
00:14:04,074 --> 00:14:05,990
Kaya ako pagdaragdag ng isa pang
block, lamang na maging malinaw.

278
00:14:05,990 --> 00:14:08,424
Gusto ko sa kanya upang ituro 90 degrees
sa kanan sa pamamagitan ng default,

279
00:14:08,424 --> 00:14:10,840
kaya lang ako pagpunta sa sabihin sa kanya
upang gawin iyon ng programming.

280
00:14:10,840 --> 00:14:11,632
At dito namin pumunta.

281
00:14:11,632 --> 00:14:14,740

282
00:14:14,740 --> 00:14:15,740
Mukhang naming gumawa niyaon.

283
00:14:15,740 --> 00:14:19,980
Ito ay isang maliit na kakaiba, dahil
Naglalakad siya baligtad.

284
00:14:19,980 --> 00:14:21,250
Sabihin tumawag na ang isang bug.

285
00:14:21,250 --> 00:14:22,120
Iyan ay isang pagkakamali.

286
00:14:22,120 --> 00:14:27,320
Ang isang bug ay isang pagkakamali sa isang programa, ang isang
logical error na ako, ang tao, ginawa.

287
00:14:27,320 --> 00:14:28,985
Bakit siya pagpunta baligtad?

288
00:14:28,985 --> 00:14:33,560

289
00:14:33,560 --> 00:14:35,250
Ang ibig MIT magtaas o ginawa ko?

290
00:14:35,250 --> 00:14:38,840

291
00:14:38,840 --> 00:14:42,550
>> Yeah, I mean, ito ay hindi MIT ni
kasalanan. Binigyan naman nila ako ng isang piraso puzzle

292
00:14:42,550 --> 00:14:44,970
na nagsasabing i-ilang bilang ng mga degree.

293
00:14:44,970 --> 00:14:47,672
At sa Victoria mungkahi,
Ako pag-on 180 degrees,

294
00:14:47,672 --> 00:14:48,880
na kung saan ay ang karapatan intuwisyon.

295
00:14:48,880 --> 00:14:53,700
Ngunit pag 180 degrees literal
ay nangangahulugan ng pag-on 180 degrees,

296
00:14:53,700 --> 00:14:55,860
at iyan ay hindi talagang
ano ang gusto ko, tila.

297
00:14:55,860 --> 00:14:58,026
Dahil hindi bababa sa siya ay nasa
ito ng dalawang-dimensional na mundo,

298
00:14:58,026 --> 00:15:00,740
kaya pag-on ang tunay na nangyayari
upang i-flip sa kanya baligtad.

299
00:15:00,740 --> 00:15:04,030
>> Ako marahil nais na gumamit ng kung ano ang block
sa halip, batay sa kung ano ang nakikita mo dito?

300
00:15:04,030 --> 00:15:11,890

301
00:15:11,890 --> 00:15:14,790
Paano natin ayusin ito?

302
00:15:14,790 --> 00:15:18,380
Yeah, kaya maaari kaming ituro
sa tapat ng direksyon.

303
00:15:18,380 --> 00:15:22,300
At talagang kahit na
hindi pagpunta sa maging sapat na,

304
00:15:22,300 --> 00:15:26,410
dahil aming makakaya lamang hard code
sa pagturo kaliwa o kanan.

305
00:15:26,410 --> 00:15:27,920
>> Alam mo kung ano ang maaari naming gawin?

306
00:15:27,920 --> 00:15:30,160
Mukhang kami ay may isang
convenience block dito.

307
00:15:30,160 --> 00:15:32,987
Kung ako mag-zoom in, tingnan ang
isang bagay na gusto namin dito?

308
00:15:32,987 --> 00:15:36,120

309
00:15:36,120 --> 00:15:40,020
Kaya mukhang MIT ay may isang
abstraction built in dito.

310
00:15:40,020 --> 00:15:45,440
block na ito ay tila upang maging katumbas
na kung saan ang iba pang mga bloke, plural?

311
00:15:45,440 --> 00:15:49,510
>> Ito isang bloke ay tila na maging katumbas
sa ito buong trio ng mga bloke

312
00:15:49,510 --> 00:15:50,880
na mayroon kami dito.

313
00:15:50,880 --> 00:15:54,670
Kaya ito lumiliko out maaari kong gawing simple ang aking
programa sa pamamagitan ng getting alisan ng lahat ng na

314
00:15:54,670 --> 00:15:58,270
at lamang ilagay ito sa dito.

315
00:15:58,270 --> 00:16:01,620
At ngayon siya ay pa rin ng kaunti
maraming surot, at iyan ay pagmultahin para sa ngayon.

316
00:16:01,620 --> 00:16:03,370
Susubukan naming mag-iwan na maging.

317
00:16:03,370 --> 00:16:06,000
Ngunit ang aking mga programa ay kahit na
mas simple, at ito, masyadong,

318
00:16:06,000 --> 00:16:09,060
ay magiging representative
ng isang layunin sa programming--

319
00:16:09,060 --> 00:16:13,430
ay upang may perpektong gumawa ng iyong code bilang
simple, bilang compact hangga't maaari,

320
00:16:13,430 --> 00:16:15,650
habang pa rin bilang
nababasa hangga't maaari.

321
00:16:15,650 --> 00:16:20,310
Hindi mo nais na gawin ito upang maikli at malinaw
na ito ay mahirap na maunawaan.

322
00:16:20,310 --> 00:16:22,826
>> Ngunit mapansin ko na papalitan
tatlong mga bloke sa isa,

323
00:16:22,826 --> 00:16:24,200
at iyan ay arguably isang magandang bagay.

324
00:16:24,200 --> 00:16:27,280
Ko na abstracted malayo ang paniwala
ng pag-check kung ikaw ay

325
00:16:27,280 --> 00:16:29,120
sa gilid na may isa lamang block.

326
00:16:29,120 --> 00:16:31,520
Ngayon ay maaari naming masiyahan sa mga ito, sa katunayan.

327
00:16:31,520 --> 00:16:35,790
Na ito ay hindi magdagdag ng so much
intelektwal halaga ngunit mapaglaro halaga.

328
00:16:35,790 --> 00:16:39,730
Ako pagpunta sa sige
at grab ang tunog dito.

329
00:16:39,730 --> 00:16:42,900

330
00:16:42,900 --> 00:16:46,420
Kaya hayaan mo akong sige, at ipaalam sa akin
itigil ang programa para sa isang sandali.

331
00:16:46,420 --> 00:16:52,070
Pupunta ako upang i-record ang mga sumusunod,
na nagpapahintulot ng access sa aking mikropono.

332
00:16:52,070 --> 00:16:53,181
>> Ayan na naman.

333
00:16:53,181 --> 00:16:53,680
Ouch.

334
00:16:53,680 --> 00:16:58,710

335
00:16:58,710 --> 00:17:01,140
Tayo'y subukan ito muli.

336
00:17:01,140 --> 00:17:02,279
Ayan na naman.

337
00:17:02,279 --> 00:17:03,570
OK, naitala ko ang maling bagay.

338
00:17:03,570 --> 00:17:04,580
Ayan na naman.

339
00:17:04,580 --> 00:17:05,080
Ouch.

340
00:17:05,080 --> 00:17:07,910

341
00:17:07,910 --> 00:17:08,800
Ouch.

342
00:17:08,800 --> 00:17:09,300
Lahat tama.

343
00:17:09,300 --> 00:17:10,791
Ngayon ay kailangan ko upang makakuha ng mapupuksa ng na.

344
00:17:10,791 --> 00:17:11,290
Lahat tama.

345
00:17:11,290 --> 00:17:13,950
>> Kaya ngayon mayroon akong isang
record ng lamang "ouch."

346
00:17:13,950 --> 00:17:18,040
Kaya ngayon ako pagpunta sa pumunta
maaga at tawagan ito "ouch."

347
00:17:18,040 --> 00:17:20,270
Pupunta ako sa bumalik
sa aking mga script, at ngayon

348
00:17:20,270 --> 00:17:25,460
notice mayroong block na ito na tinatawag na
play ng tunog "meow" o-play ng tunog "ouch."

349
00:17:25,460 --> 00:17:28,920
Pupunta ako upang i-drag ito, at kung saan
ang dapat kong ilagay ito para sa nakakatawa epekto?

350
00:17:28,920 --> 00:17:31,740

351
00:17:31,740 --> 00:17:37,860
Yeah, kaya ngayon ito ay uri ng
maraming surot, dahil ngayon ito block--

352
00:17:37,860 --> 00:17:42,050
paunawa kung paano ito "kung sa gilid,
bounce "ay uri ng self-contained.

353
00:17:42,050 --> 00:17:43,704
Kaya kailangan ko upang ayusin ito.

354
00:17:43,704 --> 00:17:44,870
Hayaan akong magpatuloy at gawin ito.

355
00:17:44,870 --> 00:17:48,630
Hayaan akong kumuha alisan ng mga ito at bumalik
sa aming orihinal na, mas sinadya

356
00:17:48,630 --> 00:17:49,870
functionality.

357
00:17:49,870 --> 00:18:01,080
Kaya "kung hawakan talim," Gusto kong
upang i-on, tulad ng Victoria iminungkahi,

358
00:18:01,080 --> 00:18:02,480
180 degrees.

359
00:18:02,480 --> 00:18:05,497
At ang gusto kong i-play
ang tunog "ouch" doon?

360
00:18:05,497 --> 00:18:11,800

361
00:18:11,800 --> 00:18:15,580
>> Yeah, mapapansin ito ay sa labas
na dilaw na bloke.

362
00:18:15,580 --> 00:18:17,680
Kaya ito, masyadong, ay magiging isang
bug, ngunit Napansin ko ito.

363
00:18:17,680 --> 00:18:21,290
Kaya ako pagpunta sa i-drag ito up dito,
at notice ngayon ito ay sa loob ng "kung."

364
00:18:21,290 --> 00:18:24,250
Kaya ang "kung" ay ganitong uri
ng tulad braso-like blot

365
00:18:24,250 --> 00:18:26,260
na lamang ang pagpunta sa
gawin kung ano ang nasa loob ng mga ito.

366
00:18:26,260 --> 00:18:30,216
Kaya ngayon kung ako mag-zoom out sa
ang panganib ng annoying--

367
00:18:30,216 --> 00:18:32,860

368
00:18:32,860 --> 00:18:36,470
>> COMPUTER: Ouch, ouch, ouch.

369
00:18:36,470 --> 00:18:39,910
>> David MALAN: At ito
ay pumunta lamang sa magpakailanman.

370
00:18:39,910 --> 00:18:44,160
Ngayon lang upang mapabilis bagay
dito, hayaan mo akong sige at buksan up,

371
00:18:44,160 --> 00:18:50,460
sabihin say-- hayaan mo akong pumunta sa ilang
ng aking sariling mga bagay-bagay mula sa klase.

372
00:18:50,460 --> 00:18:53,000

373
00:18:53,000 --> 00:19:00,220
At hayaan mo akong magbukas ng, sabihin nating, ang
isa na ginawa ng isa sa aming mga Fellows ng pagtuturo

374
00:19:00,220 --> 00:19:01,500
isang pares ng mga taon na nakalipas.

375
00:19:01,500 --> 00:19:04,732
Kaya ang ilan sa inyo ay maaaring pagpapabalik
ito laro mula sa nakalipas na panahon,

376
00:19:04,732 --> 00:19:05,940
at ito ay talagang kahanga-hangang.

377
00:19:05,940 --> 00:19:08,190
Kahit na tapos na namin ang
pinakasimpleng ng mga programa sa ngayon,

378
00:19:08,190 --> 00:19:09,980
isipin natin kung ano ito
talagang ganito ang hitsura.

379
00:19:09,980 --> 00:19:10,650
Hayaan akong pindutin ang play.

380
00:19:10,650 --> 00:19:14,210

381
00:19:14,210 --> 00:19:18,980
>> Kaya sa larong ito, mayroon kaming isang
palaka, at gamit ang mga arrow keys--

382
00:19:18,980 --> 00:19:23,340
siya ay tumatagal ng mas malaking hakbang kaysa remember-- ko
Mayroon akong kontrol sa palaka na ito.

383
00:19:23,340 --> 00:19:29,630
At ang layunin ay upang makakuha ng buong busy
road na walang tumatakbo sa mga kotse.

384
00:19:29,630 --> 00:19:34,735
At sabihin see-- kung pumunta ako dito, ako
kailangang maghintay para sa isang mag-log upang mag-scroll sa pamamagitan ng.

385
00:19:34,735 --> 00:19:38,130

386
00:19:38,130 --> 00:19:39,274
Ito nararamdaman tulad ng isang bug.

387
00:19:39,274 --> 00:19:42,240

388
00:19:42,240 --> 00:19:43,495
Ito ay uri ng isang bug.

389
00:19:43,495 --> 00:19:45,980

390
00:19:45,980 --> 00:19:46,480
Lahat tama.

391
00:19:46,480 --> 00:19:51,550
Ako ay nasa ito dito,
doon, at pagkatapos ay sa iyo na panatilihin

392
00:19:51,550 --> 00:19:54,100
pagpunta hanggang sa makuha mo ang lahat ng
ang mga palaka sa liryo pads.

393
00:19:54,100 --> 00:19:55,920
Ngayon na ito ay maaaring tumingin
lahat ng mga mas mahirap unawain,

394
00:19:55,920 --> 00:19:57,840
ngunit sabihin subukan upang basagin
ito down itak

395
00:19:57,840 --> 00:20:00,040
at pasalita sa kanyang mga bloke component.

396
00:20:00,040 --> 00:20:03,910
Kaya doon ay marahil isang malaking suliranin
piraso na hindi pa namin nakikita pa

397
00:20:03,910 --> 00:20:07,440
ngunit na pagtugon sa mga keystroke,
sa mga bagay ko pindutin sa keyboard.

398
00:20:07,440 --> 00:20:11,660
>> Kaya doon ay marahil ilang mga uri ng
block na nagsasabing, kung key ay katumbas up,

399
00:20:11,660 --> 00:20:15,965
pagkatapos ay gawin ang isang bagay na may Scratch--
siguro ilipat ito 10 hakbang sa ganitong paraan.

400
00:20:15,965 --> 00:20:20,240
Kung down key ay pinindot, ilipat 10 hakbang
sa ganitong paraan, o kaliwa key, ilipat 10 hakbang

401
00:20:20,240 --> 00:20:21,710
sa ganitong paraan, 10 hakbang na.

402
00:20:21,710 --> 00:20:23,644
malinaw ko na nakabukas ang cat sa isang palaka.

403
00:20:23,644 --> 00:20:26,060
Kaya na lamang kung saan ang
costume, pati Scratch tawag it-- namin

404
00:20:26,060 --> 00:20:28,440
lamang-import ng isang larawan ng palaka.

405
00:20:28,440 --> 00:20:29,570
>> Ngunit ano pa ang nangyayari?

406
00:20:29,570 --> 00:20:32,794
Ano ang iba pang mga linya ng code,
ano ang iba pang mga piraso ng puzzle

407
00:20:32,794 --> 00:20:35,460
ginawa Blake, ating pagtuturo kapwa,
gamitin sa programang ito, tila?

408
00:20:35,460 --> 00:20:38,320

409
00:20:38,320 --> 00:20:42,730
Ano kaya ang paggawa ng lahat ng bagay move--
kung ano ang programming bumuo?

410
00:20:42,730 --> 00:20:44,950
>> Motion, sure-- kaya ang
ilipat block, para sigurado.

411
00:20:44,950 --> 00:20:49,330
At kung ano ang na ilipat block
loob ng, malamang?

412
00:20:49,330 --> 00:20:52,850
Yeah, ang ilang mga uri ng loop, marahil ng isang
magpakailanman harangan, marahil ng isang umuulit block--

413
00:20:52,850 --> 00:20:54,070
ulitin hanggang block.

414
00:20:54,070 --> 00:20:57,330
At na kung ano ang gawin ang mga logs at
liryo pads at lahat ng iba pa ilipat

415
00:20:57,330 --> 00:20:57,990
pabalik-balik.

416
00:20:57,990 --> 00:21:00,270
Lamang Ito ay nangyayari endlessly.

417
00:21:00,270 --> 00:21:03,180
>> Bakit ang ilan sa mga kotse
paglipat ng mas mabilis kaysa sa iba?

418
00:21:03,180 --> 00:21:06,607
Ano ang iba't ibang tungkol sa mga programang ito?

419
00:21:06,607 --> 00:21:09,690
Yeah, marahil ang ilan sa kanila ay pagkuha
higit pang mga hakbang sa isang beses at ang ilan sa kanila

420
00:21:09,690 --> 00:21:10,690
mas kaunting mga hakbang sa iisang pagkakataon.

421
00:21:10,690 --> 00:21:14,670
At ang visual effect
ay mabilis kumpara mabagal.

422
00:21:14,670 --> 00:21:16,030
>> Ano sa tingin mo ang nangyari?

423
00:21:16,030 --> 00:21:19,700
Kapag nakuha ko ang aking frog lahat ng mga paraan
sa kabila ng kalye at ang ilog

424
00:21:19,700 --> 00:21:23,560
papunta sa liryo pad, isang bagay
kapansin-pansin ang nangyari.

425
00:21:23,560 --> 00:21:26,540
Ano ang nangyari sa lalong madaling ginawa ko na?

426
00:21:26,540 --> 00:21:27,210
Ito tumigil.

427
00:21:27,210 --> 00:21:29,680
palaka na tumigil, at
Nakakuha ako ng isang pangalawang palaka.

428
00:21:29,680 --> 00:21:33,155
Kaya kung ano ang bumuo ay dapat na
ginagamit doon, kung ano tampok na ito?

429
00:21:33,155 --> 00:21:36,020

430
00:21:36,020 --> 00:21:38,660
>> Oo, kaya mayroong ilang mga uri ng
"Kung" kondisyon up doon, masyadong.

431
00:21:38,660 --> 00:21:41,909
At ito ay lumiliko out-- hindi namin nakita this--
ngunit mayroong iba pang mga bloke sa may na

432
00:21:41,909 --> 00:21:45,300
maaaring sabihin, kung ikaw ay paghawak
isa pang bagay sa screen,

433
00:21:45,300 --> 00:21:47,720
kung ikaw ay pagpindot sa liryo pad, "pagkatapos."

434
00:21:47,720 --> 00:21:50,810
At pagkatapos ay na kapag kami ay
gawin ang ikalawang palaka lilitaw.

435
00:21:50,810 --> 00:21:54,969
Kaya kahit na ang laro na ito ay tiyak na
very napetsahan, kahit na sa unang tingin

436
00:21:54,969 --> 00:21:58,010
may kaya magkano ang pagpunta on-- at Blake
ay hindi mamalo ito up sa dalawang minuto,

437
00:21:58,010 --> 00:22:00,390
ito marahil kinuha sa kanya ng ilang
oras upang lumikha ng larong ito

438
00:22:00,390 --> 00:22:03,850
batay sa kanyang memory o mga video
ng bersyon ni nakalipas na panahon ng mga ito.

439
00:22:03,850 --> 00:22:07,940
Subalit ang lahat ng mga maliit na bagay
pagpunta sa screen sa paghihiwalay

440
00:22:07,940 --> 00:22:11,550
pasingawan sa mga napaka-simple
constructs-- paggalaw o pahayag

441
00:22:11,550 --> 00:22:15,519
tulad namin tinalakay, loop at
kondisyon, at na ang tungkol dito.

442
00:22:15,519 --> 00:22:17,060
Mayroong ilang mga iba pang may interes tampok.

443
00:22:17,060 --> 00:22:19,130
Ang ilan sa kanila ay pulos
aesthetic o acoustic,

444
00:22:19,130 --> 00:22:20,964
tulad ng mga tunog ko lang nilalaro gamit.

445
00:22:20,964 --> 00:22:23,380
Ngunit para sa pinaka-bahagi, ikaw
magkaroon sa wikang ito, simula,

446
00:22:23,380 --> 00:22:25,350
lahat ng mga pangunahing
gusali ng mga bloke na kayo

447
00:22:25,350 --> 00:22:29,280
magkaroon sa C, Java, JavaScript,
PHP, Ruby, Python,

448
00:22:29,280 --> 00:22:32,960
at anumang bilang ng iba pang mga wika.

449
00:22:32,960 --> 00:22:36,720
Ang anumang mga katanungan tungkol sa Scratch?

450
00:22:36,720 --> 00:22:37,220
Lahat tama.

451
00:22:37,220 --> 00:22:40,303
Kaya hindi namin ay sumisid sa mas malalim sa simula,
bagaman ikaw ay malugod na ito katapusan ng linggo,

452
00:22:40,303 --> 00:22:42,860
lalo na kung mayroon kang mga bata o
nieces at nephews at tulad,

453
00:22:42,860 --> 00:22:44,220
upang ipakilala ang mga ito sa scratch.

454
00:22:44,220 --> 00:22:47,960
Ito ay talagang isang kamangha-mangha mapaglaro
kapaligiran na may, tulad ng mga may-akda nito sabihin,

455
00:22:47,960 --> 00:22:49,120
mataas na kisame.

456
00:22:49,120 --> 00:22:51,670
Kahit na namin na nagsimula sa
napakababang-level sa mga detalye,

457
00:22:51,670 --> 00:22:54,890
maaari mong talagang gawin ganap ng isang bit
sa ito, at ito ay marahil

458
00:22:54,890 --> 00:22:57,360
isang pagtatanghal ng eksakto na.

459
00:22:57,360 --> 00:23:02,920
>> Ngunit sabihin ngayon lumipat sa ilang mga higit pa
sopistikadong problema, kung ikaw ay,

460
00:23:02,920 --> 00:23:05,870
na kilala bilang "naghahanap" at
"Pag-uuri," mas pangkalahatang paraan.

461
00:23:05,870 --> 00:23:09,500
Kami ay nagkaroon na ito phone book earlier-- narito ang
isa pa lamang para discussion--

462
00:23:09,500 --> 00:23:13,460
na kami ay able sa paghahanap
nang mas mahusay dahil

463
00:23:13,460 --> 00:23:15,270
ng isang makabuluhang palagay.

464
00:23:15,270 --> 00:23:17,655
At lamang maging malinaw, kung ano
palagay ay ko ang paggawa ng

465
00:23:17,655 --> 00:23:19,280
kapag naghahanap sa pamamagitan ng phone book?

466
00:23:19,280 --> 00:23:23,342

467
00:23:23,342 --> 00:23:25,300
That Mike Smith ay sa
phone book, kahit na ako

468
00:23:25,300 --> 00:23:27,410
magagawang upang mahawakan
ang sitwasyon nang hindi siya

469
00:23:27,410 --> 00:23:30,720
doon kung ako lang tumigil prematurely.

470
00:23:30,720 --> 00:23:31,806
Ang libro ay alphabetical.

471
00:23:31,806 --> 00:23:33,930
At iyan ay isang napakamapagbigay
palagay, dahil na

472
00:23:33,930 --> 00:23:36,580
nangangahulugan someone-- ako uri
ng pag-cut isang sulok,

473
00:23:36,580 --> 00:23:40,580
tulad ng ako ay mas mabilis dahil ang isang tao
sino pa ang paririto ay isang pulutong ng mga hirap sa trabaho para sa akin.

474
00:23:40,580 --> 00:23:43,120
>> Ngunit paano kung ang telepono
libro ay unsorted?

475
00:23:43,120 --> 00:23:47,050
Siguro Verizon got tamad, lamang threw
pangalan ng lahat at numero sa doon

476
00:23:47,050 --> 00:23:50,120
siguro sa pagkakasunud-sunod sa kung saan sila
sign up para sa serbisyo ng telepono.

477
00:23:50,120 --> 00:23:54,570
At kung gaano karaming oras ang aabutin sa akin
upang mahanap ang isang tao tulad ng Mike Smith?

478
00:23:54,570 --> 00:23:58,160
1,000 page phone book-- kung gaano karaming
mga pahina ang mayroon ako upang tumingin sa pamamagitan ng?

479
00:23:58,160 --> 00:23:58,905
>> Lahat sila.

480
00:23:58,905 --> 00:24:00,030
Ikaw uri ng out ka sana.

481
00:24:00,030 --> 00:24:03,420
Mong literal ay may upang tumingin sa bawat
pahina kung ang telepono ng libro ay lamang

482
00:24:03,420 --> 00:24:04,450
random pinagsunod-sunod.

483
00:24:04,450 --> 00:24:06,910
Maaari kang makakuha ng masuwerteng at hanapin Mike
sa pinakadulo unang pahina, dahil siya

484
00:24:06,910 --> 00:24:08,826
ay ang unang customer
mag-order ng serbisyo ng telepono.

485
00:24:08,826 --> 00:24:10,760
Ngunit maaaring siya ay ang huling, masyadong.

486
00:24:10,760 --> 00:24:12,500
>> So random order ay hindi mabuti.

487
00:24:12,500 --> 00:24:16,750
Kaya ipagpalagay na mayroon kami upang ayusin ang
phone book o sa pangkalahatan data uri

488
00:24:16,750 --> 00:24:18,520
na kami ay ibinigay.

489
00:24:18,520 --> 00:24:19,440
Paano natin ito magagawa?

490
00:24:19,440 --> 00:24:21,360
>> Well, hayaan mo akong subukan lamang
isang simpleng halimbawa dito.

491
00:24:21,360 --> 00:24:24,290
Hayaan akong sige at palabunutan ng
ilang mga numero sa board.

492
00:24:24,290 --> 00:24:35,480
Ipalagay na ang mga numero na mayroon kami ay,
sabihin nating, apat, dalawa, isa, tatlo.

493
00:24:35,480 --> 00:24:38,390
At, Ben, uri-uriin ang mga numerong ito para sa amin.

494
00:24:38,390 --> 00:24:39,017
>> OK, mabuti.

495
00:24:39,017 --> 00:24:39,850
Paano ang ginawa mo iyon?

496
00:24:39,850 --> 00:24:42,731

497
00:24:42,731 --> 00:24:43,230
Lahat tama.

498
00:24:43,230 --> 00:24:44,710
Kaya magsimula sa na ang pinakamaliit na
halaga at ang pinakamataas na,

499
00:24:44,710 --> 00:24:46,084
at iyon ang tunay na magandang intuwisyon.

500
00:24:46,084 --> 00:24:48,080
At mapagtanto na kami
ang mga tao ay talagang kaakit-akit

501
00:24:48,080 --> 00:24:49,913
magandang sa paglutas ng mga problema
tulad nito, hindi bababa sa

502
00:24:49,913 --> 00:24:51,810
kapag ang data ay relatibong maliit.

503
00:24:51,810 --> 00:24:54,860
Sa sandaling simulan mo upang may daan-daang
ng mga numero, libu-libong ng mga numero,

504
00:24:54,860 --> 00:24:58,440
milyon-milyong mga numero, Ben marahil
hindi maaaring gawin ito lubos na mabilis,

505
00:24:58,440 --> 00:25:00,620
sa pag-aakala na mayroong
gaps sa ang mga numero.

506
00:25:00,620 --> 00:25:03,450
Medyo madali upang mabilang sa isang milyong
sa kabilang banda, lamang oras na gugulin.

507
00:25:03,450 --> 00:25:07,150
>> Kaya ang algorithm ito tunog
tulad ng Ben ginagamit ngayon lang

508
00:25:07,150 --> 00:25:08,930
ay ang paghahanap para sa mga pinakamaliliit na numero.

509
00:25:08,930 --> 00:25:12,900
Kaya kahit na namin ang mga tao ay maaaring tumagal ng
sa isang pulutong ng mga impormasyon visually,

510
00:25:12,900 --> 00:25:14,830
isang computer ay talagang
isang maliit na mas limitado.

511
00:25:14,830 --> 00:25:17,560
Ang computer ay maaari lamang
Tingnan natin ang isa byte sa isang panahon

512
00:25:17,560 --> 00:25:20,770
o marahil apat na bytes sa isang time--
mga araw na ito siguro 8 bytes sa isang time--

513
00:25:20,770 --> 00:25:24,450
ngunit isang napaka-maliit na bilang
ng bytes sa isang ibinigay na oras.

514
00:25:24,450 --> 00:25:28,480
>> Kaya ibinigay na namin talagang magkaroon ng
apat na magkakahiwalay na mga halaga here--

515
00:25:28,480 --> 00:25:32,440
at maaari mong isipin Ben bilang pagkakaroon
blinders sa kung siya ay isang computer tulad

516
00:25:32,440 --> 00:25:36,450
na ay hindi siya makakakita ng kahit ano maliban
sa isang numero sa isang time--

517
00:25:36,450 --> 00:25:39,720
kaya kami sa pangkalahatan ay ipinapalagay, na kahalintulad lamang
English, kami basahin mula sa kanan papuntang kaliwa.

518
00:25:39,720 --> 00:25:42,870
Kaya ang unang numero Ben marahil ay tumingin
sa ay apat at pagkatapos ay masyadong mabilis

519
00:25:42,870 --> 00:25:44,770
natanto na ang isang medyo malaking
number-- hayaan mo akong panatilihin ang naghahanap.

520
00:25:44,770 --> 00:25:45,357
>> Mayroong dalawang.

521
00:25:45,357 --> 00:25:45,940
Maghintay ng isang minuto.

522
00:25:45,940 --> 00:25:47,070
Dalawang ay mas maliit kaysa apat.

523
00:25:47,070 --> 00:25:47,986
Pupunta ako upang matandaan.

524
00:25:47,986 --> 00:25:49,070
Dalawang ay ngayon ang pinakamaliit.

525
00:25:49,070 --> 00:25:50,417
Ngayon one-- na mas mahusay.

526
00:25:50,417 --> 00:25:51,250
Iyan ay kahit na mas maliit.

527
00:25:51,250 --> 00:25:54,000
Ako pagpunta sa kalimutan ang tungkol sa dalawang
at tandaan lamang ng isa ngayon.

528
00:25:54,000 --> 00:25:56,550
>> At hindi siya nakagawa ihinto ang pagtingin?

529
00:25:56,550 --> 00:25:58,360
Well, siya ay maaaring batay
sa impormasyong ito,

530
00:25:58,360 --> 00:26:00,477
ngunit gusto niya mas mahusay na search
ang natitirang bahagi ng listahan.

531
00:26:00,477 --> 00:26:02,060
Dahil kung ano ang kung zero ay sa listahan?

532
00:26:02,060 --> 00:26:03,643
Paano kung negatibo isa'y ayon sa listahan?

533
00:26:03,643 --> 00:26:07,720
Siya lamang ang nakakaalam na ang kanyang sagot
ay tama kung siya ay exhaustively

534
00:26:07,720 --> 00:26:08,729
naka-check ang buong listahan.

535
00:26:08,729 --> 00:26:10,020
Kaya tinitingnan namin ang magpahinga ng ito.

536
00:26:10,020 --> 00:26:11,394
Three-- na noon ay isang aksaya ng oras.

537
00:26:11,394 --> 00:26:13,540
Got kapus-palad, ngunit ako ay
pa rin tama na gawin ito.

538
00:26:13,540 --> 00:26:17,857
At kaya ngayon siya siguro
pinili ang pinakamaliit na bilang

539
00:26:17,857 --> 00:26:20,440
at lamang ilagay ito sa simula
ng listahan, tulad ng makikita kong gawin dito.

540
00:26:20,440 --> 00:26:23,480
Ngayon kung ano ang gagawin mo susunod, kahit na
hindi mo naisip tungkol dito halos

541
00:26:23,480 --> 00:26:25,962
sa lawak na ito?

542
00:26:25,962 --> 00:26:27,670
Ulitin ang proseso,
kaya ang ilang mga uri ng loop.

543
00:26:27,670 --> 00:26:28,920
May isang pamilyar na ideya.

544
00:26:28,920 --> 00:26:30,860
Kaya dito ay apat.

545
00:26:30,860 --> 00:26:32,110
Iyan ay kasalukuyang ang pinakamaliit.

546
00:26:32,110 --> 00:26:33,220
Iyan ay isang kandidato.

547
00:26:33,220 --> 00:26:33,900
Hindi na.

548
00:26:33,900 --> 00:26:34,770
Ngayon ko na nakita sa dalawa.

549
00:26:34,770 --> 00:26:36,630
Iyan ang susunod na pinakamaliit na elemento.

550
00:26:36,630 --> 00:26:40,800
Three-- iyan ay hindi mas maliit, kaya
ngayon Ben ay maaaring aking bubunutin ang dalawa.

551
00:26:40,800 --> 00:26:44,510
>> At ngayon kami ulitin ang proseso, at
siyempre tatlong makakakuha hugot susunod.

552
00:26:44,510 --> 00:26:45,420
Ulitin ang proseso.

553
00:26:45,420 --> 00:26:46,990
Apat makakakuha hugot.

554
00:26:46,990 --> 00:26:50,140
At ngayon kami ay out ng mga numero,
kaya ang listahan ay dapat na pinagsunod-sunod.

555
00:26:50,140 --> 00:26:51,960
>> At sa katunayan, ito ay isang pormal na algorithm.

556
00:26:51,960 --> 00:26:56,610
Ang isang computer scientist gagawin
tawag na ito "pagpili ng uri,"

557
00:26:56,610 --> 00:27:00,880
ang ideya ng pagiging uri ng
ilista iteratively-- muli

558
00:27:00,880 --> 00:27:03,807
at muli at muli ng pagpili
ang pinakamaliit na bilang.

559
00:27:03,807 --> 00:27:06,140
At kung ano ang magaling tungkol dito ay
ito lang ang kaya darn intuitive.

560
00:27:06,140 --> 00:27:07,470
Ito ay sobrang simple.

561
00:27:07,470 --> 00:27:11,100
At maaari mong ulitin ang parehong
operasyon muli at muli.

562
00:27:11,100 --> 00:27:12,150
Ito ay simple.

563
00:27:12,150 --> 00:27:17,170
>> Sa kasong ito ito ay mabilis, ngunit
kung gaano katagal ay ito tunay na tumagal?

564
00:27:17,170 --> 00:27:19,880
Sabihin gumawa ito tila at
pakiramdam ng isang maliit na mas nakakapagod.

565
00:27:19,880 --> 00:27:24,150
Kaya isa, dalawa, tatlo, apat, lima anim,
pito, walo, siyam, 10, 11, 12, 13, 14,

566
00:27:24,150 --> 00:27:26,160
15, 16-- arbitrary numero.

567
00:27:26,160 --> 00:27:28,780
Nais ko lamang pa ito
oras na lamang ang apat.

568
00:27:28,780 --> 00:27:30,780
Kaya kung ako got ang isang buong
grupo ng mga numero now-- ito

569
00:27:30,780 --> 00:27:32,420
ay hindi kahit na mahalaga
kung ano ang kanilang are-- sabihin

570
00:27:32,420 --> 00:27:34,380
isipin ang tungkol sa kung ano ang
algorithm ay tunay na tulad ng.

571
00:27:34,380 --> 00:27:35,857
>> Ipalagay na may mga numero doon.

572
00:27:35,857 --> 00:27:38,190
Muli, hindi mahalaga kung ano
ang mga ito, ngunit ang mga ito random.

573
00:27:38,190 --> 00:27:39,679
Ako ay nag-aaplay algorithm ni Ben.

574
00:27:39,679 --> 00:27:41,220
Kailangan ko upang piliin ang pinakamaliit na bilang.

575
00:27:41,220 --> 00:27:41,761
Ano ang gagawin ko?

576
00:27:41,761 --> 00:27:44,240
At ako pagpunta sa pisikal na
gawin ito sa oras na ito na kumilos ito.

577
00:27:44,240 --> 00:27:46,099
Naghahanap, naghahanap,
naghahanap, naghahanap, naghahanap.

578
00:27:46,099 --> 00:27:48,140
Tanging sa pamamagitan ng ang oras na nakukuha ko sa
ang dulo ng listahan Maaari

579
00:27:48,140 --> 00:27:51,230
Napag-alaman kong ang pinakamaliit
number ay dalawang oras na ito.

580
00:27:51,230 --> 00:27:52,720
One ay hindi sa listahan.

581
00:27:52,720 --> 00:27:54,400
Kaya ko bang ilagay down na dalawa.

582
00:27:54,400 --> 00:27:55,590
>> Ano ang gagawin ko susunod?

583
00:27:55,590 --> 00:27:58,600
Naghahanap, naghahanap, naghahanap, naghahanap.

584
00:27:58,600 --> 00:28:02,250
Ngayon ko natagpuan ang numero ng pitong, dahil
mayroong gaps sa mga numbers--

585
00:28:02,250 --> 00:28:03,300
ngunit lamang arbitrary.

586
00:28:03,300 --> 00:28:03,800
Lahat tama.

587
00:28:03,800 --> 00:28:06,030
Kaya ngayon maaari ko bang ilagay down na pitong.

588
00:28:06,030 --> 00:28:08,860
Naghahanap naghahanap, naghahanap.

589
00:28:08,860 --> 00:28:11,030
>> Ngayon ako sa pag-aakala, ng
siyempre, na Ben ay hindi

590
00:28:11,030 --> 00:28:14,780
may dagdag na RAM, dagdag
memory, dahil, siyempre,

591
00:28:14,780 --> 00:28:16,080
Naghahanap ako sa parehong numero.

592
00:28:16,080 --> 00:28:18,246
Tiyak na maaari aking naalaala
ang lahat ng mga numero,

593
00:28:18,246 --> 00:28:19,930
at iyan ay ganap na totoo.

594
00:28:19,930 --> 00:28:22,610
Ngunit kung Ben Naaalala ng lahat
ng mga numero siya ay nakita,

595
00:28:22,610 --> 00:28:24,430
siya ay hindi tunay na ginawa
pangunahing pag-unlad

596
00:28:24,430 --> 00:28:26,170
dahil siya ay mayroon nang
ang kakayahan upang maghanap

597
00:28:26,170 --> 00:28:27,540
sa pamamagitan ng mga numero sa board.

598
00:28:27,540 --> 00:28:29,373
Remembering ang lahat ng mga
numero ay hindi makakatulong,

599
00:28:29,373 --> 00:28:32,490
dahil maaari siya pa rin bilang isang computer
lamang tumingin sa, na aming sinabi, isang numero

600
00:28:32,490 --> 00:28:33,080
sa isang pagkakataon.

601
00:28:33,080 --> 00:28:35,760
Kaya walang uri ng cheat
doon na maaari mong pagkilos.

602
00:28:35,760 --> 00:28:39,170
>> Kaya sa katotohanan, bilang ako
patuloy na maghanap sa listahan,

603
00:28:39,170 --> 00:28:44,200
Literal na ako kung lamang panatilihin ang pagpunta
pabalik-balik sa pamamagitan ng ito, plucking out

604
00:28:44,200 --> 00:28:45,710
ang susunod na maliit na numero.

605
00:28:45,710 --> 00:28:48,810
At bilang maaari mong uri ng magpakilala
mula sa aking ulok mga paggalaw,

606
00:28:48,810 --> 00:28:50,860
ito lamang ay nagiging sobrang
nakakapagod nang masyadong mabilis,

607
00:28:50,860 --> 00:28:54,850
at tila ako ay pagpunta sa likod at
balik, pabalik-balik pa ng kaunti.

608
00:28:54,850 --> 00:29:03,220
Ngayon upang maging patas, hindi ko na kailangang pumunta
lubos na bilang, well, sabihin see-- upang maging patas,

609
00:29:03,220 --> 00:29:06,310
Hindi ko na kailangang maglakad lubos
ng maraming mga hakbang sa bawat oras.

610
00:29:06,310 --> 00:29:09,200
Dahil, siyempre, bilang ako
piliin ang mga numero mula sa listahan,

611
00:29:09,200 --> 00:29:11,860
ang mga natitirang mga listahan ay nakakakuha ng mas maikli.

612
00:29:11,860 --> 00:29:14,240
>> At kaya sabihin isipin ang tungkol
kung gaano karaming mga hakbang na ako talaga

613
00:29:14,240 --> 00:29:16,010
traipsing sa pamamagitan ng bawat oras.

614
00:29:16,010 --> 00:29:18,950
Sa pinakaunang sitwasyon
kami ay nagkaroon ng 16 mga numero,

615
00:29:18,950 --> 00:29:22,210
at iba pa maximally-- sabihin lang
gawin ito para sa isang discussion--

616
00:29:22,210 --> 00:29:25,640
Mayroon akong upang tumingin sa pamamagitan ng 16
mga numero upang mahanap ang pinakamaliit.

617
00:29:25,640 --> 00:29:28,420
Ngunit sa sandaling ko na naagaw
ang pinakamaliit na bilang, kung paano

618
00:29:28,420 --> 00:29:30,590
katagal ang natitirang listahan, siyempre?

619
00:29:30,590 --> 00:29:31,420
Just 15.

620
00:29:31,420 --> 00:29:34,670
Kaya kung gaano karaming mga numero ay Ben o ba akong magkaroon ng
upang tumingin sa pamamagitan ng ikalawang oras sa paligid?

621
00:29:34,670 --> 00:29:36,832
15, lamang upang pumunta at hanapin ang pinakamaliit.

622
00:29:36,832 --> 00:29:39,540
Ngunit ngayon, siyempre, ang listahan ay,
masyadong, mas maliit kaysa sa ito ay bago.

623
00:29:39,540 --> 00:29:42,540
Kaya kung gaano karaming mga hakbang ginawa ko
may sa gawin ang susunod na pagkakataon?

624
00:29:42,540 --> 00:29:49,970
14 at pagkatapos ay 13 at pagkatapos ay 12, plus tuldok,
tuldok, tuldok, hanggang ako kaliwa na may isa lamang.

625
00:29:49,970 --> 00:29:53,146
Kaya ngayon isang computer siyentipiko gagawin
magtanong, well, kung ano ang ginagawa na ang lahat ng pantay-pantay?

626
00:29:53,146 --> 00:29:55,770
Ito ang tunay na katumbas ng ilang mga kongkreto
number na kami ng dati tiyak

627
00:29:55,770 --> 00:30:00,490
gawin arithmetically, ngunit nais naming makipag-usap
tungkol sa kahusayan ng mga algorithm

628
00:30:00,490 --> 00:30:04,940
ng kaunti pa formulaically,
independiyenteng ng kung gaano katagal ang listahan ay.

629
00:30:04,940 --> 00:30:06,240
>> At sa gayon alam mo kung ano?

630
00:30:06,240 --> 00:30:09,860
Ito ay 16, ngunit tulad ng sinabi ko bago,
sabihin lamang tawagan ang laki ng problema

631
00:30:09,860 --> 00:30:10,970
n, kung saan ang n ay ang ilang mga numero.

632
00:30:10,970 --> 00:30:13,220
Siguro ito ay 16, marahil ito ay
tatlo, marahil ito ay isang milyon.

633
00:30:13,220 --> 00:30:13,761
Hindi ko alam.

634
00:30:13,761 --> 00:30:14,390
Wala akong pakialam.

635
00:30:14,390 --> 00:30:16,520
Ano ko talagang gusto ay
isang formula na maaari kong

636
00:30:16,520 --> 00:30:19,420
gamitin upang ihambing ito algorithm
laban sa iba pang mga algorithm

637
00:30:19,420 --> 00:30:22,350
na ang isang tao ay maaaring i-claim
ay mas mahusay o mas masahol pa.

638
00:30:22,350 --> 00:30:25,430
>> Kaya ito ay lumiliko out, at ako lamang
malaman na ito mula grade school,

639
00:30:25,430 --> 00:30:34,790
na ito talagang gumagana out sa parehong
bagay bilang n higit n plus one sa higit sa dalawang.

640
00:30:34,790 --> 00:30:40,020
At ito ang mangyayari sa pantay, ng
Siyempre, n squared plus n higit sa dalawang.

641
00:30:40,020 --> 00:30:43,250
Kaya kung nais ko ng isang formula
para sa kung paano maraming mga hakbang

642
00:30:43,250 --> 00:30:46,330
ay kasangkot sa pagtingin sa lahat
ng mga numero muli at muli

643
00:30:46,330 --> 00:30:52,681
at muli at muli, nais kong sabihin
n ito ay squared plus n higit sa dalawang.

644
00:30:52,681 --> 00:30:53,430
Pero alam mo kung ano?

645
00:30:53,430 --> 00:30:54,500
Ito lamang ang hitsura makalat.

646
00:30:54,500 --> 00:30:56,470
Ko lang talagang gusto ng isang
pangkalahatang kamalayan ng mga bagay.

647
00:30:56,470 --> 00:30:58,810
At maaari mong isipin ang mula
high school na

648
00:30:58,810 --> 00:31:00,660
ay ang pagkaunawa ng pinakamataas matagalang order.

649
00:31:00,660 --> 00:31:05,300
Alin sa mga tuntuning ito, ang n
squared, ang n, o ang kalahati,

650
00:31:05,300 --> 00:31:07,550
ay ang pinaka-epekto sa paglipas ng panahon?

651
00:31:07,550 --> 00:31:11,920
Ang mas malaki n ay makakakuha ng, na kung saan
sa mga bagay na ang pinakagigiliwan mo?

652
00:31:11,920 --> 00:31:15,560
>> Sa ibang salita, kung ang plug ko
in a million, n squared

653
00:31:15,560 --> 00:31:17,900
ay magiging pinaka-malamang
ang dominating kadahilanan,

654
00:31:17,900 --> 00:31:21,670
dahil ang isang milyong beses
mismo ay isang pulutong mas malaki

655
00:31:21,670 --> 00:31:23,682
kaysa plus isang karagdagang million.

656
00:31:23,682 --> 00:31:24,390
Kaya alam mo kung ano?

657
00:31:24,390 --> 00:31:27,305
Ito ay tulad ng isang darn malaki
numero kung parisukat sa iyo ng isang numero.

658
00:31:27,305 --> 00:31:28,430
Ito ay hindi talagang mahalaga.

659
00:31:28,430 --> 00:31:30,596
Lamang kami ng pagpunta krus na
out at kalimutan ang tungkol dito.

660
00:31:30,596 --> 00:31:34,250
At sa gayon ang isang computer siyentipiko nais sabihin
na ang kahusayan ng algorithm na ito

661
00:31:34,250 --> 00:31:37,850
ay sa pagkakasunud-sunod ng n squared--
Ibig sabihin ko tunay na isang approximation.

662
00:31:37,850 --> 00:31:40,810
Ito ay uri ng halos n squared.

663
00:31:40,810 --> 00:31:44,130
Sa paglipas ng panahon, ang mas malaki
at mas malaki n ay makakakuha ng, ito

664
00:31:44,130 --> 00:31:47,610
ay isang mahusay na kuru-kuro para sa kung ano ang
kahusayan o kakulangan ng kahusayan

665
00:31:47,610 --> 00:31:49,400
ng algorithm na ito ay tunay.

666
00:31:49,400 --> 00:31:52,040
At nakukuha ko na, siyempre,
mula sa aktwal na paggawa ng matematika.

667
00:31:52,040 --> 00:31:54,040
Ngunit ngayon lang ako waving
aking mga kamay, dahil ko lang

668
00:31:54,040 --> 00:31:55,790
gusto ng isang pangkalahatang pakiramdam ng algorithm na ito.

669
00:31:55,790 --> 00:31:58,850
>> Kaya gamit ang parehong logic, samantala,
sabihin isaalang-alang ang isa pang algorithm

670
00:31:58,850 --> 00:32:01,162
kami ay tumingin at-- linear paghahanap.

671
00:32:01,162 --> 00:32:02,870
Kapag ako ay naghahanap
para sa book-- phone

672
00:32:02,870 --> 00:32:05,980
hindi paghihiwalay ito, paghahanap
sa pamamagitan ng book-- phone

673
00:32:05,980 --> 00:32:09,197
namin iningatan nagsasabi na ito ay
1,000 mga hakbang, o 500 hakbang.

674
00:32:09,197 --> 00:32:10,280
Ngunit sabihin ng tuntuning panlahat na.

675
00:32:10,280 --> 00:32:12,860
Kung may n mga pahina sa
phone book, kung ano ang

676
00:32:12,860 --> 00:32:17,250
ang oras o ang
kahusayan ng linear paghahanap?

677
00:32:17,250 --> 00:32:19,750
Ito ay sa order ng
kung gaano karaming mga hakbang na ito upang makahanap ng

678
00:32:19,750 --> 00:32:24,210
Mike Smith gamit linear paghahanap, ang
unang algorithm, o kahit na ang ikalawang?

679
00:32:24,210 --> 00:32:27,240

680
00:32:27,240 --> 00:32:31,710
>> Sa pinakamasama kaso, Mike
ay sa dulo ng aklat.

681
00:32:31,710 --> 00:32:35,590
Kaya kung ang phone book ay may 1,000 mga pahina,
sinabi namin huling oras, sa pinakamasama kaso,

682
00:32:35,590 --> 00:32:38,380
maaaring tumagal ng humigit-kumulang kung gaano
maraming mga pahina upang mahanap Mike?

683
00:32:38,380 --> 00:32:38,990
Like 1,000.

684
00:32:38,990 --> 00:32:39,830
Ito ay isang itaas na nakatali.

685
00:32:39,830 --> 00:32:41,790
Ito ay isang pinakamasama posibleng sitwasyon.

686
00:32:41,790 --> 00:32:44,410
Ngunit muli, kami ay gumagalaw ang layo
mula sa mga numero tulad ng 1,000 ngayon.

687
00:32:44,410 --> 00:32:45,730
Ito ay lamang ng n.

688
00:32:45,730 --> 00:32:47,470
>> Kaya kung ano ang lohikal na konklusyon?

689
00:32:47,470 --> 00:32:50,210
Paghahanap ng Mike sa isang telepono
libro na may mga pahina n

690
00:32:50,210 --> 00:32:55,280
Maaaring tumagal, sa pinakadulo pinakamasama kaso,
kung gaano karaming mga hakbang na ito sa pagkakasunud-sunod ng n?

691
00:32:55,280 --> 00:32:58,110
At sa katunayan ng isang computer
siyentipiko nais sabihin

692
00:32:58,110 --> 00:33:02,340
na ang pagtakbo ng oras, o ang
pagganap o ang kahusayan

693
00:33:02,340 --> 00:33:07,470
o kawalan ng kaalaman, ng isang algorithm tulad
isang linear paghahanap ay sa order ng n.

694
00:33:07,470 --> 00:33:10,010
At maaari naming ilapat ang parehong
lohika ng tawiran ng isang bagay out

695
00:33:10,010 --> 00:33:13,170
bilang ko lang ginawa sa ikalawang
algorithm nagkaroon kami sa phone book,

696
00:33:13,170 --> 00:33:16,040
na ating pinuntahan dalawang pahina sa isang pagkakataon.

697
00:33:16,040 --> 00:33:20,120
>> Kaya 1,000 ang pahinang phone book baka
ariin mo kaming 500 pahina liko, plus one

698
00:33:20,120 --> 00:33:21,910
kung double namin pabalik ng kaunti.

699
00:33:21,910 --> 00:33:26,590
Kaya kung ang isang phone book ay may mga pahina n, ngunit
kami ay gumagawa ng dalawang pahina sa isang pagkakataon,

700
00:33:26,590 --> 00:33:28,900
na halos kung ano?

701
00:33:28,900 --> 00:33:33,190
N higit sa dalawang, kaya na tulad n higit sa dalawang.

702
00:33:33,190 --> 00:33:38,490
Ngunit ginawa ko ang pag-angkin ng isang
ilang sandali ang nakalipas na n sa ibabaw two--

703
00:33:38,490 --> 00:33:41,060
iyon ang uri ng ang parehong bilang lamang n.

704
00:33:41,060 --> 00:33:44,050
Ito ay lamang ng isang pare-pareho na kadahilanan,
computer siyentipiko nais sabihin.

705
00:33:44,050 --> 00:33:45,970
Sabihin lamang ang focus sa
ang mga variable, really--

706
00:33:45,970 --> 00:33:47,780
ang pinakamalaking variable sa equation.

707
00:33:47,780 --> 00:33:52,530
>> Kaya linear paghahanap, kung tapos na ang isa
pahina sa isang oras o dalawang pahina sa isang pagkakataon,

708
00:33:52,530 --> 00:33:54,810
ay isang uri ng panimula ang parehong.

709
00:33:54,810 --> 00:33:56,880
Ito ay pa rin sa order ng n.

710
00:33:56,880 --> 00:34:01,930
Ngunit inaangkin ko ang aking larawan mas maaga
na ang ikatlong algorithm ay hindi

711
00:34:01,930 --> 00:34:02,480
linear.

712
00:34:02,480 --> 00:34:03,605
Ito ay hindi isang tuwid na linya.

713
00:34:03,605 --> 00:34:08,659
At ito'y yaong hindi tuwid na linya, at ang
algebraic formula nagkaroon kung ano?

714
00:34:08,659 --> 00:34:11,812
Log ng n-- kaya log base dalawa sa n.

715
00:34:11,812 --> 00:34:14,520
At hindi namin kailangang pumunta sa masyadong
maraming detalye sa logarithms araw na ito,

716
00:34:14,520 --> 00:34:17,394
ngunit karamihan computer siyentipiko gagawin hindi
kahit na sabihin sa iyo kung ano ang base ay.

717
00:34:17,394 --> 00:34:20,639
Dahil ito ay ang lahat lamang
pare-pareho ang mga kadahilanan, kaya na magsalita,

718
00:34:20,639 --> 00:34:22,659
lamang bahagyang numeric pagkakaiba.

719
00:34:22,659 --> 00:34:31,179
At kaya ito ay magiging isang napaka-pangkaraniwan
paraan para lalo pormal na computer

720
00:34:31,179 --> 00:34:33,949
siyentipiko sa isang lupon o
programmers sa isang white board

721
00:34:33,949 --> 00:34:36,889
aktwal na arguing na
algorithm sila ay gumamit ng

722
00:34:36,889 --> 00:34:39,500
o kung ano ang kahusayan
ng kanilang algorithm ay.

723
00:34:39,500 --> 00:34:42,960
>> At ito ay hindi kinakailangan ng isang bagay
talakayin sa iyo sa anumang mahusay na detalye,

724
00:34:42,960 --> 00:34:47,889
ngunit isang mahusay na programmer ay isang tao
na may isang solid, pormal na background.

725
00:34:47,889 --> 00:34:50,120
Siya ay able sa makipag-usap sa
sa iyo sa ganitong uri ng paraan

726
00:34:50,120 --> 00:34:53,350
at tunay na gumawa ng
husay argumento bilang

727
00:34:53,350 --> 00:34:56,870
kung bakit isa algorithm o
isang piraso ng software

728
00:34:56,870 --> 00:35:00,165
ay higit na mataas sa ilang mga paraan sa isa pa.

729
00:35:00,165 --> 00:35:02,540
Dahil maaari mong tiyak na
lamang patakbuhin ang program na isang tao

730
00:35:02,540 --> 00:35:04,980
at bilangin ang bilang ng mga segundo
ang kinakailangan upang ayusin ang ilang mga numero,

731
00:35:04,980 --> 00:35:06,710
at maaari mong magpatakbo ng ilang
program iba pang mga tao

732
00:35:06,710 --> 00:35:08,418
at bilangin ang bilang
ng mga segundo na aabutin.

733
00:35:08,418 --> 00:35:12,840
Ngunit ito ay isang mas pangkalahatang paraan na
maaari mong gamitin upang pag-aralan mga algorithm,

734
00:35:12,840 --> 00:35:15,520
kung ikaw ay, lamang sa
papel o lamang sa salita.

735
00:35:15,520 --> 00:35:18,430
Nang walang kahit na tumatakbo ito, nang walang
kahit na sinusubukan sample inputs,

736
00:35:18,430 --> 00:35:20,180
maaari mo lamang dahilan sa pamamagitan nito.

737
00:35:20,180 --> 00:35:24,670
At kaya sa pagtanggap ng empleyado ng isang developer o kung
pagkakaroon sa kanya uri ng magpakilala sa iyo

738
00:35:24,670 --> 00:35:28,460
kung bakit ang kanilang algorithm, ang kanilang mga lihim
sauce para sa paghahanap ng bilyun-bilyong

739
00:35:28,460 --> 00:35:30,580
ng mga web page para sa iyong
kumpanya ay mas mahusay, ang mga ito

740
00:35:30,580 --> 00:35:33,302
ang mga uri ng argumento nila
dapat na sa isip ay maaaring gumawa.

741
00:35:33,302 --> 00:35:35,010
O hindi bababa sa mga ito ay
ang uri ng mga bagay

742
00:35:35,010 --> 00:35:40,211
na sumampa ka sa discussion, sa
hindi bababa sa isang napaka-pormal na talakayan.

743
00:35:40,211 --> 00:35:40,710
Lahat tama.

744
00:35:40,710 --> 00:35:44,400
Kaya Ben iminungkahi ng isang bagay
tinatawag selection sort.

745
00:35:44,400 --> 00:35:48,200
Ngunit ako pagpunta sa imungkahi na mayroong
iba pang mga paraan ng paggawa nito, masyadong.

746
00:35:48,200 --> 00:35:50,400
Ano Hindi ko talaga gusto
tungkol sa Ben algorithm

747
00:35:50,400 --> 00:35:54,400
ay na patuloy siyang lumakad, o
pagkakaroon akin maglakad, pabalik-balik

748
00:35:54,400 --> 00:35:56,930
at pabalik-balik at pabalik-balik.

749
00:35:56,930 --> 00:36:04,130
Paano kung sa halip ako ay upang gawin
isang bagay tulad ng mga numerong ito dito

750
00:36:04,130 --> 00:36:08,200
at ako ay sa makatarungan makitungo sa bawat
number naman bilang ako binigyan nito?

751
00:36:08,200 --> 00:36:10,780
>> Sa ibang salita, narito ang
aking listahan ng mga numero.

752
00:36:10,780 --> 00:36:12,944
Apat, isa, tatlo, dalawa.

753
00:36:12,944 --> 00:36:14,360
At ako pagpunta sa gawin ang mga sumusunod.

754
00:36:14,360 --> 00:36:17,230
Ako pagpunta sa ipasok ang mga numero
kung saan sila nabibilang sa halip

755
00:36:17,230 --> 00:36:18,980
kaysa pagpili sa mga ito nang paisa-isa.

756
00:36:18,980 --> 00:36:20,820
Sa ibang salita, narito ang bilang apat.

757
00:36:20,820 --> 00:36:22,430
>> Ito ang aking orihinal na listahan.

758
00:36:22,430 --> 00:36:25,290
At ako pagpunta upang mapanatili ang
mahalagang isang bagong listahan dito.

759
00:36:25,290 --> 00:36:26,710
Kaya ito ay ang lumang listahan.

760
00:36:26,710 --> 00:36:28,560
Ito ang bagong listahan.

761
00:36:28,560 --> 00:36:30,220
nakikita ko ang mga numero ng apat muna.

762
00:36:30,220 --> 00:36:34,500
Ang aking bagong listahan ay una walang laman,
kaya ito ay trivially kaso

763
00:36:34,500 --> 00:36:36,410
na apat na ngayon ay sari-sari listahan.

764
00:36:36,410 --> 00:36:39,560
Tingin lang ako sa pagkuha ng bilang ako ibinigay,
at ako ng paglagay ito sa aking bagong listahan.

765
00:36:39,560 --> 00:36:41,460
>> Ay pinagsunod-sunod ang bagong listahan?

766
00:36:41,460 --> 00:36:41,990
Yeah.

767
00:36:41,990 --> 00:36:45,090
Ito ay bobo dahil mayroong isa lamang
elemento, ngunit ito ay ganap na pinagsunod-sunod.

768
00:36:45,090 --> 00:36:46,390
May walang wala sa lugar.

769
00:36:46,390 --> 00:36:49,290
Ito ay mas kawili-wiling, ang algorithm,
kapag lumipat ako sa susunod na hakbang.

770
00:36:49,290 --> 00:36:50,550
>> Ngayon Mayroon akong isa.

771
00:36:50,550 --> 00:36:55,430
Kaya isa, siyempre, ay kabilang sa
simula o dulo ng ito ng mga bagong listahan?

772
00:36:55,430 --> 00:36:56,360
Ang simula.

773
00:36:56,360 --> 00:36:58,530
Kaya kailangan kong gawin ang ilang mga trabaho ngayon.

774
00:36:58,530 --> 00:37:01,410
Gumagamit ako pagkuha ng ilang mga
kalayaan sa aking marker

775
00:37:01,410 --> 00:37:03,120
sa pamamagitan lamang ng pagguhit bagay
kung saan gusto ko ang mga ito,

776
00:37:03,120 --> 00:37:05,320
ngunit iyan ay hindi talagang
tumpak sa isang computer.

777
00:37:05,320 --> 00:37:08,530
Ang isang computer, bilang alam namin, ay may
RAM, o Random Access Memory,

778
00:37:08,530 --> 00:37:12,411
at iyon ang isa byte at
isa pang byte at isa pang byte.

779
00:37:12,411 --> 00:37:14,910
At kung mayroon kang isang gigabyte ng
RAM, mayroon kang isang bilyong bytes,

780
00:37:14,910 --> 00:37:16,680
ngunit ang mga ito pisikal sa isang lokasyon.

781
00:37:16,680 --> 00:37:19,540
Hindi lamang ka maaaring ilipat bagay sa paligid
sa pamamagitan ng pagguhit ito sa board

782
00:37:19,540 --> 00:37:20,750
Kahit saan mo gusto.

783
00:37:20,750 --> 00:37:24,090
Kaya kung ang aking bagong listahan ay
apat na mga lokasyon sa memorya,

784
00:37:24,090 --> 00:37:27,480
sa kasamaang-palad ang apat ay
na sa maling lugar.

785
00:37:27,480 --> 00:37:30,410
>> Kaya upang ipasok ang numero ng isa
hindi lang ako makapag gumuhit ito dito.

786
00:37:30,410 --> 00:37:31,901
Ito memory location ay hindi umiiral.

787
00:37:31,901 --> 00:37:35,150
Iyon ay magiging pagdaraya, at ako ay
cheating pictorially para sa isang ilang minuto

788
00:37:35,150 --> 00:37:35,800
dito.

789
00:37:35,800 --> 00:37:40,950
Kaya talaga, kung gusto ko upang ilagay ang isa dito,
Mayroon akong upang pansamantalang kopyahin ang apat

790
00:37:40,950 --> 00:37:43,030
at pagkatapos ay ilagay ang isa doon.

791
00:37:43,030 --> 00:37:45,500
>> Iyon ay pinong, na tama,
na technically maaari,

792
00:37:45,500 --> 00:37:48,410
ngunit mapagtanto na dagdag na trabaho.

793
00:37:48,410 --> 00:37:50,460
Hindi ko na lang ilagay ang numero sa lugar.

794
00:37:50,460 --> 00:37:53,026
Ako unang nagkaroon upang ilipat ang isang
numero, pagkatapos ay ilagay ito sa lugar,

795
00:37:53,026 --> 00:37:54,650
kaya ako uri ng lambal ang aking halaga ng trabaho.

796
00:37:54,650 --> 00:37:55,660
Kaya panatilihin na sa isip.

797
00:37:55,660 --> 00:37:57,120
>> Ngunit ngayon ako tapos may sangkap na ito.

798
00:37:57,120 --> 00:37:59,056
Ngayon, gusto kong i-grab ang numero ng tatlong.

799
00:37:59,056 --> 00:38:00,430
Saan, siyempre, ay ito nabibilang?

800
00:38:00,430 --> 00:38:01,480
Sa gitna.

801
00:38:01,480 --> 00:38:03,650
Hindi ko ma-impostor anymore
at lamang ilagay ito doon,

802
00:38:03,650 --> 00:38:06,770
dahil, muli, ito memory
ay sa pisikal na mga lokasyon.

803
00:38:06,770 --> 00:38:10,900
Kaya ko bang kopyahin ang apat
at kaniyang inilagay ang tatlong sa paglipas dito.

804
00:38:10,900 --> 00:38:11,550
Hindi isang malaking pakikitungo.

805
00:38:11,550 --> 00:38:14,610
Ito ay lamang ng isa dagdag na hakbang
again-- nararamdaman napaka murang.

806
00:38:14,610 --> 00:38:16,445
>> Ngunit ngayon ilipat ko sa sa dalawang.

807
00:38:16,445 --> 00:38:17,820
Ang dalawang, siyempre, ay kabilang dito.

808
00:38:17,820 --> 00:38:20,990
Ngayon simulan mo upang makita kung paano
ang trabaho ay maaaring pile up.

809
00:38:20,990 --> 00:38:23,520
Ngayon kung ano ang kailangan kong gawin?

810
00:38:23,520 --> 00:38:28,570
Yeah, kailangan kong ilipat ang apat,
Ako pagkatapos ay kung kopyahin ang tatlo,

811
00:38:28,570 --> 00:38:31,200
at ngayon ko ipasok ang dalawa.

812
00:38:31,200 --> 00:38:34,460
At ang catch na may ganitong
algorithm, nang kawili-wili sapat,

813
00:38:34,460 --> 00:38:41,050
ay na ipagpalagay na mayroon kami ng isang mas matinding
kaso kung saan ito ay sabihin natin walo, pito,

814
00:38:41,050 --> 00:38:45,150
anim, lima, apat, tatlo, dalawa, isa.

815
00:38:45,150 --> 00:38:49,450
Ito ay, sa maraming mga konteksto,
ang pinakamasama kaso sitwasyon,

816
00:38:49,450 --> 00:38:51,570
dahil ang darn bagay
ay literal paurong.

817
00:38:51,570 --> 00:38:53,670
>> Hindi ito tunay
makakaapekto algorithm ni Ben,

818
00:38:53,670 --> 00:38:55,940
dahil sa pagpili ni Ben
uri siya ay pagpunta sa panatilihin

819
00:38:55,940 --> 00:38:58,359
pagpaparoo't parito sa listahan.

820
00:38:58,359 --> 00:39:01,150
At dahil palaging siya ay naghahanap
sa pamamagitan ng buong natitirang listahan,

821
00:39:01,150 --> 00:39:02,858
hindi bale
kung saan ang mga elemento ay.

822
00:39:02,858 --> 00:39:05,630
Ngunit sa kasong ito sa aking pagpasok
approach-- sabihin subukan ito.

823
00:39:05,630 --> 00:39:08,616
>> Kaya isa, dalawa, tatlo, apat,
lima, anim, pito, walo.

824
00:39:08,616 --> 00:39:11,630
Isa dalawa tatlo apat,
lima, anim, pito, walo.

825
00:39:11,630 --> 00:39:14,320
Pupunta ako upang gawin ang mga walong,
at saan ko bang ilagay ito?

826
00:39:14,320 --> 00:39:17,260
Well, sa simula ng aking listahan,
dahil ang bagong listahan ay pinagsunod-sunod.

827
00:39:17,260 --> 00:39:18,760
At i-cross ko ito out.

828
00:39:18,760 --> 00:39:20,551
>> Saan ko maaaring ilagay ang pitong?

829
00:39:20,551 --> 00:39:21,050
Darn ito.

830
00:39:21,050 --> 00:39:23,174
Ito mga pangangailangan upang pumunta doon, kaya
kailangan kong gawin ang ilang mga pagkopya.

831
00:39:23,174 --> 00:39:26,820

832
00:39:26,820 --> 00:39:28,480
At ngayon ang pitong napupunta dito.

833
00:39:28,480 --> 00:39:29,860
Ngayon ilipat ko sa sa anim.

834
00:39:29,860 --> 00:39:30,980
Ngayon ay mas mas maraming trabaho.

835
00:39:30,980 --> 00:39:32,570
>> Eight ay may upang pumunta dito.

836
00:39:32,570 --> 00:39:33,920
Seven ay may upang pumunta dito.

837
00:39:33,920 --> 00:39:35,450
Ngayon ang anim ay maaaring pumunta dito.

838
00:39:35,450 --> 00:39:37,950
Ngayon ko grab ang lima.

839
00:39:37,950 --> 00:39:40,560
Ngayon ang walong ay may upang pumunta
dito, pitong ay may upang pumunta dito,

840
00:39:40,560 --> 00:39:43,650
anim ay may upang pumunta dito, at
ngayon ang limang at ulitin.

841
00:39:43,650 --> 00:39:46,610
At ako ay medyo magkano
gumagalaw ito patuloy.

842
00:39:46,610 --> 00:39:52,950
>> Kaya sa katapusan, ito algorithm-- bibigyan namin
tumawag ito insertion sort-- talagang

843
00:39:52,950 --> 00:39:55,020
ay may isang pulutong ng mga trabaho, masyadong.

844
00:39:55,020 --> 00:39:56,970
Ito ay lamang ng iba't ibang
uri ng trabaho kaysa sa Ben.

845
00:39:56,970 --> 00:40:00,090
ni Ben trabaho ay nagkaroon sa akin ng pagpunta
pabalik-balik lahat ng oras,

846
00:40:00,090 --> 00:40:03,510
pagpili sa susunod na pinakamaliit
element muli at muli.

847
00:40:03,510 --> 00:40:06,660
Kaya ito ay na ito napaka-visual uri ng trabaho.

848
00:40:06,660 --> 00:40:10,600
>> Ang iba pang mga algorithm, na kung saan ay pa rin
correct-- ito makakuha ng trabaho done--

849
00:40:10,600 --> 00:40:12,800
nagbabago lamang ang halaga ng trabaho.

850
00:40:12,800 --> 00:40:15,420
Mukhang sa una ikaw ay
pag-save, dahil ikaw lamang

851
00:40:15,420 --> 00:40:19,190
pagharap sa bawat elemento
up harap nang walang paglalakad ang lahat

852
00:40:19,190 --> 00:40:20,930
ang paraan sa pamamagitan ng listahan tulad ng Ben ay.

853
00:40:20,930 --> 00:40:25,300
Ngunit ang problema ay, lalo na sa mga
crazy mga kaso kung saan ito ay ang lahat paurong,

854
00:40:25,300 --> 00:40:27,830
ikaw ay lamang uri ng
postponing ang mahirap na trabaho

855
00:40:27,830 --> 00:40:30,360
hanggang sa ikaw ay upang ayusin ang iyong mga pagkakamali.

856
00:40:30,360 --> 00:40:33,919
>> At kaya kung maaari mong isipin na ito
walong pu't pitong pu't anim at limang

857
00:40:33,919 --> 00:40:36,710
at sa ibang pagkakataon sa apat na at tatlong at dalawang
paglipat ng kanilang mga paraan sa pamamagitan ng listahan,

858
00:40:36,710 --> 00:40:39,060
lamang namin ay nagbago ang
uri ng trabaho ang aming ginagawa.

859
00:40:39,060 --> 00:40:42,340
Sa halip ng paggawa nito sa
simula ng aking pag-ulit,

860
00:40:42,340 --> 00:40:45,250
Lang ako sa paggawa nito sa
dulo ng bawat pag-ulit.

861
00:40:45,250 --> 00:40:50,550
Kaya ito lumiliko out na algorithm na ito,
masyadong, sa pangkalahatan ay tinatawag na pagpapasok ng uri,

862
00:40:50,550 --> 00:40:52,190
ay din sa pagkakasunud-sunod ng n squared.

863
00:40:52,190 --> 00:40:56,480
Ito ay talagang hindi mas mabuti,
Walang mas mahusay na sa lahat.

864
00:40:56,480 --> 00:41:00,810
>> Gayunman, may isang ikatlong diskarte
Gusto ko hinihikayat sa amin upang isaalang-alang,

865
00:41:00,810 --> 00:41:02,970
na kung saan ay na ito.

866
00:41:02,970 --> 00:41:07,850
Kaya ipagpalagay aking listahan, para sa simple
muli, ay apat, isa, tatlo,

867
00:41:07,850 --> 00:41:11,080
two-- lamang ng apat na numero.

868
00:41:11,080 --> 00:41:13,300
Ben ay nagkaroon ng magandang intuwisyon,
mabuting tao intuwisyon

869
00:41:13,300 --> 00:41:16,340
bago, kung saan tayo naayos na ang buong
ilista eventually-- insertion sort.

870
00:41:16,340 --> 00:41:18,020
coaxed ako sa amin kasama.

871
00:41:18,020 --> 00:41:22,530
Ngunit sabihin isaalang-alang ang
pinakasimpleng paraan upang ayusin ang listahang ito.

872
00:41:22,530 --> 00:41:24,110
>> Ang listahang ito ay hindi pinagsunod-sunod.

873
00:41:24,110 --> 00:41:26,130
Bakit?

874
00:41:26,130 --> 00:41:31,920
Sa Ingles, ipaliwanag kung bakit
ito ay hindi tunay na pinagsunod-sunod.

875
00:41:31,920 --> 00:41:33,400
Ano ang ibig ito nangangahulugan na hindi na pinagsunod-sunod?

876
00:41:33,400 --> 00:41:34,220
>> MAG-AARAL: Hindi ito sequential.

877
00:41:34,220 --> 00:41:34,990
>> David MALAN: Hindi sequential.

878
00:41:34,990 --> 00:41:35,822
Bigyan mo ako ng isang halimbawa.

879
00:41:35,822 --> 00:41:37,180
>> MAG-AARAL: Ilagay ang mga ito sa pagkakasunud-sunod.

880
00:41:37,180 --> 00:41:37,440
>> David MALAN: OK.

881
00:41:37,440 --> 00:41:38,790
Bigyan mo ako ng isang mas tiyak na halimbawa.

882
00:41:38,790 --> 00:41:39,832
>> MAG-AARAL: Pataas order.

883
00:41:39,832 --> 00:41:41,206
David MALAN: Hindi pataas order.

884
00:41:41,206 --> 00:41:42,100
Maging mas tumpak.

885
00:41:42,100 --> 00:41:45,190
Hindi ko alam kung ano ang ibig sabihin sa pamamagitan ng pataas.

886
00:41:45,190 --> 00:41:47,150
Ano ang mali?

887
00:41:47,150 --> 00:41:49,930
>> MAG-AARAL: Ang pinakamaliit na ng
mga numero ay hindi sa unang space.

888
00:41:49,930 --> 00:41:51,140
>> David MALAN: Pinakamaliit number ni
hindi sa unang space.

889
00:41:51,140 --> 00:41:52,120
Maging mas tiyak.

890
00:41:52,120 --> 00:41:55,000
Ako simula upang magtuloy.

891
00:41:55,000 --> 00:41:59,470
Kami ay pagbibilang, ngunit
kung ano ang out of order dito?

892
00:41:59,470 --> 00:42:00,707
>> MAG-AARAL: Numerical sequence.

893
00:42:00,707 --> 00:42:02,040
David MALAN: Numerical sequence.

894
00:42:02,040 --> 00:42:04,248
Ang bawat tao'y uri ng pag-iingat
ito here-- napakataas na antas.

895
00:42:04,248 --> 00:42:07,450
Just literal sabihin sa akin kung ano ang
mali tulad ng isang limang-taong gulang na maaaring.

896
00:42:07,450 --> 00:42:08,310
>> MAG-AARAL: Plus isa.

897
00:42:08,310 --> 00:42:08,750
>> David MALAN: Ano iyon?

898
00:42:08,750 --> 00:42:09,610
>> MAG-AARAL: Plus isa.

899
00:42:09,610 --> 00:42:11,235
>> David MALAN: Ano ang ibig mo bang sabihin plus one?

900
00:42:11,235 --> 00:42:12,754

901
00:42:12,754 --> 00:42:14,170
Bigyan mo ako ng isang iba't ibang mga limang-taon gulang na.

902
00:42:14,170 --> 00:42:16,840

903
00:42:16,840 --> 00:42:18,330
Ano ang mali, mom?

904
00:42:18,330 --> 00:42:19,940
Ano ang mali, ama?

905
00:42:19,940 --> 00:42:22,808
Ano ang ibig sabihin na ito ay hindi pinagsunod-sunod?

906
00:42:22,808 --> 00:42:24,370
>> MAG-AARAL: Hindi ito ang tamang lugar.

907
00:42:24,370 --> 00:42:25,580
>> David MALAN: Ano ang
wala sa tamang lugar?

908
00:42:25,580 --> 00:42:26,174
>> MAG-AARAL: Four.

909
00:42:26,174 --> 00:42:27,090
David MALAN: OK, mabuti.

910
00:42:27,090 --> 00:42:29,110
Kaya apat na ay hindi kung saan ito ay dapat.

911
00:42:29,110 --> 00:42:30,590
Sa partikular, ay tama ito?

912
00:42:30,590 --> 00:42:33,000
Apat at isa, ang unang
dalawang numero nakikita ko.

913
00:42:33,000 --> 00:42:34,930
Ito ba ay tama?

914
00:42:34,930 --> 00:42:36,427
Hindi, ang mga ito ay sa labas ng order, right?

915
00:42:36,427 --> 00:42:38,135
Sa katunayan, sa tingin ngayon
tungkol sa isang computer, masyadong.

916
00:42:38,135 --> 00:42:40,824
Maaari lamang ito tumingin sa marahil isa,
siguro dalawang bagay nang sabay once--

917
00:42:40,824 --> 00:42:43,240
at talagang lamang ng isang bagay
sa isang panahon, ngunit ito ay maaaring sa hindi bababa sa

918
00:42:43,240 --> 00:42:45,790
tumingin sa isang bagay at pagkatapos ay ang
susunod na bagay karapatan sa tabi nito.

919
00:42:45,790 --> 00:42:47,380
>> Kaya ang mga ito sa pagkakasunud-sunod?

920
00:42:47,380 --> 00:42:48,032
Syempre hindi.

921
00:42:48,032 --> 00:42:48,740
Kaya alam mo kung ano?

922
00:42:48,740 --> 00:42:51,020
Bakit hindi namin kumuha ng sanggol
hakbang sa pag-aayos ng problemang ito

923
00:42:51,020 --> 00:42:53,410
sa halip ng paggawa ng mga fancy
algorithm tulad ng Ben, kung saan

924
00:42:53,410 --> 00:42:56,440
siya ay uri ng pag-aayos ng ito sa pamamagitan ng
looping sa pamamagitan ng listahan

925
00:42:56,440 --> 00:42:59,670
sa halip ng paggawa ng kung ano ang aking ginawa, kung saan
Ko lang ang uri ng taning na ito bilang namin pumunta?

926
00:42:59,670 --> 00:43:03,650
Sabihin lang literal masira ang
paniwala ng order-- numerical order,

927
00:43:03,650 --> 00:43:06,990
tumawag ito anumang want-- mo
sa mga pairwise paghahambing.

928
00:43:06,990 --> 00:43:07,590
>> Apat na pu't isa.

929
00:43:07,590 --> 00:43:09,970
Ito ba ang tamang pagkakasunod-sunod?

930
00:43:09,970 --> 00:43:11,310
Kaya sabihin ayusin na.

931
00:43:11,310 --> 00:43:14,700
Isa at apat na, at pagkatapos ay
kami na lang kopyahin na.

932
00:43:14,700 --> 00:43:15,560
O sige, good.

933
00:43:15,560 --> 00:43:17,022
At aking iniayos sa isa at apat.

934
00:43:17,022 --> 00:43:18,320
Tatlong at dalawa?

935
00:43:18,320 --> 00:43:18,820
Hindi.

936
00:43:18,820 --> 00:43:21,690
Hayaan ang aking mga salita tumugma sa aking mga daliri.

937
00:43:21,690 --> 00:43:23,695
Apat at tatlo?

938
00:43:23,695 --> 00:43:27,930
>> Hindi ito sa pagkakasunod-sunod, kaya ako pagpunta
na gawin ang isa, tatlo, apat, dalawa.

939
00:43:27,930 --> 00:43:28,680
OK, mabuti.

940
00:43:28,680 --> 00:43:32,310
Ngayon apat at dalawa?

941
00:43:32,310 --> 00:43:33,370
Kailangan namin upang ayusin ito, masyadong.

942
00:43:33,370 --> 00:43:36,700
Kaya isa, tatlo, dalawa, apat.

943
00:43:36,700 --> 00:43:39,820
Kaya ay ito inayos?

944
00:43:39,820 --> 00:43:43,170
Hindi, ngunit ito ay mas malapit sa pinagsunod-sunod?

945
00:43:43,170 --> 00:43:48,930
>> Ito ay, dahil naayos na namin ito
pagkakamali, naayos na namin ang pagkakamaling ito,

946
00:43:48,930 --> 00:43:50,370
at naayos na namin ang pagkakamaling ito.

947
00:43:50,370 --> 00:43:52,420
Kaya naayos na namin ng tatlong mga pagkakamali arguably.

948
00:43:52,420 --> 00:43:58,100
Still ay hindi talagang tumingin pinagsunod-sunod, ngunit
ito ay talaga mas malapit sa pinagsunod-sunod na

949
00:43:58,100 --> 00:44:00,080
dahil naayos na namin ang ilan sa mga pagkakamali.

950
00:44:00,080 --> 00:44:02,047
>> Ngayon kung ano ang gagawin ko susunod?

951
00:44:02,047 --> 00:44:03,630
Ako uri ng naabot ang dulo ng listahan.

952
00:44:03,630 --> 00:44:05,680
Ako tila sa may taning na
lahat ng mga pagkakamali, ngunit walang.

953
00:44:05,680 --> 00:44:08,510
Dahil sa kasong ito, ang ilang mga numero
maaaring bubbled up mas malapit

954
00:44:08,510 --> 00:44:10,410
sa iba pang mga numero na
ay pa rin sa labas ng order.

955
00:44:10,410 --> 00:44:12,951
Kaya sabihin gawin ito muli, at kukunin ko na
lamang gawin ito sa lugar ngayon.

956
00:44:12,951 --> 00:44:14,170
One at tatlo?

957
00:44:14,170 --> 00:44:14,720
Ayos lang.

958
00:44:14,720 --> 00:44:16,070
Tatlong at dalawa?

959
00:44:16,070 --> 00:44:17,560
Of course hindi, kaya sabihin baguhin iyon.

960
00:44:17,560 --> 00:44:19,160
Sa gayo'y dalawa, tatlo.

961
00:44:19,160 --> 00:44:21,340
Tatlo at apat na?

962
00:44:21,340 --> 00:44:24,370
At ngayon sabihin lamang
lalo na pilosopo dito.

963
00:44:24,370 --> 00:44:26,350
Ito ba ay pinagsunod-sunod?

964
00:44:26,350 --> 00:44:29,280
You tao malaman ito ay pinagsunod-sunod.

965
00:44:29,280 --> 00:44:30,400
>> ang dapat kong subukan muli.

966
00:44:30,400 --> 00:44:31,900
Kaya Olivia ay pagpapanukala sinusubukan kong muli.

967
00:44:31,900 --> 00:44:32,530
Bakit?

968
00:44:32,530 --> 00:44:35,810
Dahil ang isang computer ay hindi magkaroon
ang mga luho ng aming mga mata ng tao

969
00:44:35,810 --> 00:44:38,080
na lamang glancing back-- OK, ako tapos na.

970
00:44:38,080 --> 00:44:41,610
Paano gumagana ang computer matukoy
na ang listahan ay pinagsunod-sunod ngayon?

971
00:44:41,610 --> 00:44:44,590
Nang wala sa loob.

972
00:44:44,590 --> 00:44:47,650
>> ang dapat kong pumunta sa pamamagitan ng
minsan pa, at lamang kung ako

973
00:44:47,650 --> 00:44:51,190
huwag gumawa / makahanap ng anumang mga pagkakamali maaari kong
pagkatapos ay tapusin na rin ang computer, yep,

974
00:44:51,190 --> 00:44:51,980
kami ay handa na upang patakbuhin.

975
00:44:51,980 --> 00:44:54,850
Kaya isa at dalawa, dalawa at
tatlo, tatlong pu't apat.

976
00:44:54,850 --> 00:44:58,030
Ngayon ay maaari kong definitively sabihin na ito ay
pinagsunod-sunod, dahil sa pinagaling kong walang mga pagbabago.

977
00:44:58,030 --> 00:45:01,940
Ngayon ay ito ay isang bug at lamang
sira ang bait kung ako, ang computer,

978
00:45:01,940 --> 00:45:05,640
nagtanong muli ang mga parehong mga katanungan
umaasang iba't ibang mga sagot.

979
00:45:05,640 --> 00:45:07,110
Hindi ba dapat mangyari.

980
00:45:07,110 --> 00:45:08,600
>> At kaya ngayon ang listahan ay pinagsunod-sunod.

981
00:45:08,600 --> 00:45:12,630
Sa kasamaang palad, tumatakbo ang oras ng
algorithm na ito ay din n squared.

982
00:45:12,630 --> 00:45:13,130
Bakit?

983
00:45:13,130 --> 00:45:19,520
Dahil ikaw ay may n numero, at sa
pinakamasama kaso mayroon kang upang ilipat n numero

984
00:45:19,520 --> 00:45:23,637
n beses dahil mayroon kang upang panatilihin ang pagpunta
bumalik upang suriin at potensyal na ayusin

985
00:45:23,637 --> 00:45:24,220
mga numerong ito.

986
00:45:24,220 --> 00:45:26,280
At maaari naming gawin ang isang mas
pormal na pag-aaral, masyadong.

987
00:45:26,280 --> 00:45:29,530
>> Kaya ito ay na makapagsalita nagsagawa kami
tatlong iba't ibang approach na ito, isa

988
00:45:29,530 --> 00:45:32,210
ng mga ito kaagad intuitive
off ang bat mula sa Ben

989
00:45:32,210 --> 00:45:35,170
sa aking mga iminungkahing insertion
uri sa isang ito

990
00:45:35,170 --> 00:45:38,540
kung saan mo uri ng malimutan
ang kagubatan para sa mga puno sa una.

991
00:45:38,540 --> 00:45:41,760
Ngunit pagkatapos ay kung magdadala sa iyo ng isang hakbang pabalik,
voila, naayos na namin ang pag-uuri paniwala.

992
00:45:41,760 --> 00:45:43,824
Kaya ito ay, maglakas-loob sabihin,
isang mas mababang antas marahil

993
00:45:43,824 --> 00:45:45,740
kaysa sa ilang ng iba pang mga
algorithm, ngunit sabihin

994
00:45:45,740 --> 00:45:48,550
makita kung hindi namin maaaring maisalarawan
ito sa pamamagitan ng paraan ng mga ito.

995
00:45:48,550 --> 00:45:51,450
>> Kaya ito ay ang ilang mga nice
software na ang isang tao

996
00:45:51,450 --> 00:45:56,110
sinulat gamit ang mga makukulay bar na
pagpunta sa gawin ang mga sumusunod na para sa amin.

997
00:45:56,110 --> 00:45:57,736
Bawat isa sa mga bar ay kumakatawan sa isang numero.

998
00:45:57,736 --> 00:46:00,026
Taller bar, ang mas malaki
ang numero, mas maliit na ang bar,

999
00:46:00,026 --> 00:46:00,990
ang mas maliit na ang numero.

1000
00:46:00,990 --> 00:46:05,880
Kaya sa isip na gusto namin sa isang masarap na pyramid
kung saan ito ay nagsisimula maliit at ay makakakuha ng malaking,

1001
00:46:05,880 --> 00:46:08,330
at na ay nangangahulugan na
mga bar ay pinagsunod-sunod.

1002
00:46:08,330 --> 00:46:11,200
Kaya ako pagpunta sa sige at piliin,
halimbawa, algorithm ni Ben

1003
00:46:11,200 --> 00:46:13,990
first-- selection sort.

1004
00:46:13,990 --> 00:46:16,220
>> At pansinin kung ano ang ginagawa nito.

1005
00:46:16,220 --> 00:46:18,670
Ang paraan na kanilang pinili upang
maisalarawan ang algorithm na ito

1006
00:46:18,670 --> 00:46:22,090
ay na, tulad ng ako ay
naglalakad sa pamamagitan ng aking listahan,

1007
00:46:22,090 --> 00:46:24,710
program na ito ay maaaring
sa pamamagitan ng kanyang listahan ng mga numero,

1008
00:46:24,710 --> 00:46:28,160
highlight sa pink bawat
number na ito ay naghahanap sa.

1009
00:46:28,160 --> 00:46:32,360
At kung ano ang tungkol sa mangyayari ngayon?

1010
00:46:32,360 --> 00:46:35,154
>> Ang pinakamaliit na bilang na
Ko o Ben natagpuan biglang

1011
00:46:35,154 --> 00:46:36,820
makakakuha ng inilipat sa simula ng listahan.

1012
00:46:36,820 --> 00:46:40,037
At mapansin ang kanilang ginawa paalisin
ang bilang na ay doon,

1013
00:46:40,037 --> 00:46:41,120
at na ay ganap na ganap pagmultahin.

1014
00:46:41,120 --> 00:46:42,600
Hindi ko makuha sa na antas ng detalye.

1015
00:46:42,600 --> 00:46:44,308
Ngunit kailangan namin upang ilagay
na numero sa isang lugar,

1016
00:46:44,308 --> 00:46:47,775
kaya kami lamang inilipat ito sa
bukas na lugar na ay nilikha.

1017
00:46:47,775 --> 00:46:49,900
Kaya ako ng pagpunta sa bilis na ito
up, dahil kung hindi man ito

1018
00:46:49,900 --> 00:46:51,871
nagiging napaka-nakakapagod mabilis.

1019
00:46:51,871 --> 00:46:55,800

1020
00:46:55,800 --> 00:46:58,600
Animation speed-- doon pumunta kami.

1021
00:46:58,600 --> 00:47:01,850
Kaya parehong ngayon prinsipyo
Ako ay nag-aaplay, ngunit ikaw

1022
00:47:01,850 --> 00:47:06,540
maaaring magsimula sa pakiramdam ang algorithm, kung ikaw
ay, o makita ito ng kaunti pa malinaw.

1023
00:47:06,540 --> 00:47:13,190
At ito algorithm ay ang epekto ng
pagpili sa susunod na pinakamaliit na elemento,

1024
00:47:13,190 --> 00:47:16,422
kaya ikaw ay pagpunta sa simulan upang
makita ito ramp up sa kaliwa.

1025
00:47:16,422 --> 00:47:19,130
At sa bawat pag-ulit, bilang ako
iminungkahi, ito ay isang maliit na mas mababa trabaho.

1026
00:47:19,130 --> 00:47:21,921
Hindi nito ay may upang pumunta lahat ng mga paraan
pabalik sa kaliwang dulo ng listahan,

1027
00:47:21,921 --> 00:47:23,900
dahil ito ay mayroon
alam ang mga ito ay pinagsunod-sunod.

1028
00:47:23,900 --> 00:47:28,129
Kaya ito uri ng pakiramdam ng tulad ng ito ay
accelerating, kahit na ang bawat hakbang ay

1029
00:47:28,129 --> 00:47:29,420
pagkuha ng parehong halaga ng oras.

1030
00:47:29,420 --> 00:47:31,600
Mayroon lamang mas kaunting mga hakbang natitira.

1031
00:47:31,600 --> 00:47:35,240
At ngayon maaari mong uri ng pakiramdam ang
algorithm paglilinis up ang dulo ng ito,

1032
00:47:35,240 --> 00:47:37,040
at sa katunayan ngayon ito ay pinagsunod-sunod.

1033
00:47:37,040 --> 00:47:41,620
>> Kaya insertion sort ay ang lahat ng tapos na.

1034
00:47:41,620 --> 00:47:43,600
Kailangan ko upang muling i-sunod ang array.

1035
00:47:43,600 --> 00:47:45,940
At mapansin Maaari ko lang
panatilihin randomizing ito,

1036
00:47:45,940 --> 00:47:50,630
at kami makakuha ng isang approximation ng
ang parehong diskarte, insertion sort.

1037
00:47:50,630 --> 00:47:55,050
Hayaan akong mabagal ito pababa sa dito.

1038
00:47:55,050 --> 00:47:56,915
Magsimula tayo na sa paglipas Hayaan.

1039
00:47:56,915 --> 00:47:57,414
Itigil.

1040
00:47:57,414 --> 00:48:00,662

1041
00:48:00,662 --> 00:48:02,410
>> ni laktawan apat Hayaan.

1042
00:48:02,410 --> 00:48:03,200
Mayroon kaming pumunta.

1043
00:48:03,200 --> 00:48:04,190
Sunod sila array.

1044
00:48:04,190 --> 00:48:05,555
At dito namin go-- insertion sort.

1045
00:48:05,555 --> 00:48:10,260

1046
00:48:10,260 --> 00:48:12,800
Play.

1047
00:48:12,800 --> 00:48:17,280
Pansinin na ito ay pagharap sa bawat
element ito encounters kaagad,

1048
00:48:17,280 --> 00:48:20,282
ngunit kung ito ay kabilang sa
maling notice lugar

1049
00:48:20,282 --> 00:48:21,740
lahat ng mga trabaho na may mangyari.

1050
00:48:21,740 --> 00:48:24,700
Mayroon kaming upang panatilihin ang paglilipat pa
at higit pang mga elemento upang gumawa ng room

1051
00:48:24,700 --> 00:48:27,340
for the one gusto naming ilagay sa lugar.

1052
00:48:27,340 --> 00:48:30,740
>> Kaya kami ay nagbibigay-diin sa
kaliwang dulo ng listahan lamang.

1053
00:48:30,740 --> 00:48:34,460
Paunawa kami ay hindi kahit na tumingin at-- namin
hindi naka-highlight sa pink kahit ano

1054
00:48:34,460 --> 00:48:35,610
sa kanan.

1055
00:48:35,610 --> 00:48:38,180
Lang namin ay pagharap sa
ang mga problema bilang namin pumunta,

1056
00:48:38,180 --> 00:48:40,430
ngunit kami ay ang paglikha ng isang pulutong ng mga
trabaho para sa ating sarili pa rin.

1057
00:48:40,430 --> 00:48:44,410
At kaya kung pabilisin namin ito up
ngayon upang pumunta sa pagkumpleto,

1058
00:48:44,410 --> 00:48:46,210
ito ay may isang iba't ibang mga pakiramdam na ito sa katunayan.

1059
00:48:46,210 --> 00:48:50,150
Lamang Ito ay nagbibigay-diin sa kaliwang dulo ngunit
paggawa ng isang kaunti pa sa trabaho bilang needed--

1060
00:48:50,150 --> 00:48:53,230
uri ng smoothing bagay
higit sa, pag-aayos ng mga bagay,

1061
00:48:53,230 --> 00:48:58,350
ngunit pagharap huli sa
bawat elemento nang paisa-isa

1062
00:48:58,350 --> 00:49:07,740
hanggang sa makuha namin sa the-- well, kami
ang lahat ng malaman kung paano ito ay pagpunta sa dulo,

1063
00:49:07,740 --> 00:49:09,700
kaya ito ay isang maliit na underwhelming marahil.

1064
00:49:09,700 --> 00:49:12,830
>> Ngunit ang listahan sa end--
spoiler-- ay pagpunta sa ay pinagsunod-sunod.

1065
00:49:12,830 --> 00:49:15,300
Kaya tingnan natin ang isa sa huling isa.

1066
00:49:15,300 --> 00:49:16,840
Hindi lamang namin ay maaaring laktawan ngayon.

1067
00:49:16,840 --> 00:49:18,000
Malapit na tayo.

1068
00:49:18,000 --> 00:49:19,980
Dalawang upang pumunta, ang isa ay upang pumunta.

1069
00:49:19,980 --> 00:49:22,680
At voila.

1070
00:49:22,680 --> 00:49:23,450
Magaling.

1071
00:49:23,450 --> 00:49:27,220
>> Kaya ngayon sabihin gawin ang isa huling isa,
muling randomizing may bubble sort.

1072
00:49:27,220 --> 00:49:31,690
At mapansin dito, lalo na kung mabagal ko ito
down, ito ay panatilihin ang swooping sa pamamagitan ng.

1073
00:49:31,690 --> 00:49:36,830
Ngunit mapansin ito lamang ang gumagawa ng pairwise
comparisons-- uri ng lokal na mga solusyon.

1074
00:49:36,830 --> 00:49:39,050
Ngunit sa lalong madaling makuha namin sa
ang dulo ng listahan sa pink,

1075
00:49:39,050 --> 00:49:40,690
kung ano ang pagpunta sa may sa mangyari muli?

1076
00:49:40,690 --> 00:49:44,539

1077
00:49:44,539 --> 00:49:46,830
Yeah, ito ay pagpunta sa may sa
magsimulang muli, dahil ito lamang

1078
00:49:46,830 --> 00:49:49,870
fixed pairwise pagkakamali.

1079
00:49:49,870 --> 00:49:53,120
At na maaaring nagsiwalat pa iba.

1080
00:49:53,120 --> 00:49:58,950
At kaya kung pabilisin mo ito up, makikita mo
makita na, mas maraming bilang ng pangalan ng nagpapahiwatig,

1081
00:49:58,950 --> 00:50:01,870
ang mga mas maliit elements-- o sa halip,
ang mas malaki elements-- ay simula

1082
00:50:01,870 --> 00:50:03,740
sa bubble up sa itaas, kung ikaw ay.

1083
00:50:03,740 --> 00:50:07,380
At ang mga mas maliit na mga elemento ay
simula na bubble pababa sa kaliwa.

1084
00:50:07,380 --> 00:50:10,780
At sa katunayan, na ang uri ng
ang visual effect pati na rin.

1085
00:50:10,780 --> 00:50:17,150
At kaya ito ay end up pagtatapos
sa isang katulad na paraan, masyadong.

1086
00:50:17,150 --> 00:50:19,160
>> Wala kaming na matatahanan
sa partikular na isa.

1087
00:50:19,160 --> 00:50:21,010
Hayaan akong buksan ito ngayon, masyadong.

1088
00:50:21,010 --> 00:50:24,040
May ilang iba pang mga pag-uuri algorithm
sa mundo, ang ilan sa kung saan

1089
00:50:24,040 --> 00:50:25,580
ay nakunan dito.

1090
00:50:25,580 --> 00:50:29,960
At lalo na para sa mga aaral na hindi
kinakailangang visual o matematika,

1091
00:50:29,960 --> 00:50:31,930
tulad ng ginawa namin bago, maaari naming
ring gawin ito audially

1092
00:50:31,930 --> 00:50:34,210
kung iuugnay namin ang isang tunog na may ito.

1093
00:50:34,210 --> 00:50:36,990
At katuwaan lang, narito ang isang
ilang iba't-ibang mga algorithm,

1094
00:50:36,990 --> 00:50:40,950
at isa sa kanila sa partikular ikaw
pagpunta sa paunawa ay tinatawag na "pagsasama-uuri."

1095
00:50:40,950 --> 00:50:43,250
>> Ito ay talagang isang panimula
mas mahusay na algorithm,

1096
00:50:43,250 --> 00:50:45,860
tulad na sumanib-uuri, ang isa sa
sana ang mga na ikaw ay tungkol sa upang makita,

1097
00:50:45,860 --> 00:50:49,170
ay hindi pagkakasunud-sunod ng n squared.

1098
00:50:49,170 --> 00:50:57,280
Ito ay sa pagkakasunud-sunod ng n beses log ng
n, kung saan ay talagang mas maliit at sa gayon ay

1099
00:50:57,280 --> 00:50:58,940
mas mabilis kaysa sa mga iba pang mga tatlong.

1100
00:50:58,940 --> 00:51:00,670
At mayroong isang pares ng iba pang
silly mga na kami makita.

1101
00:51:00,670 --> 00:51:01,933
>> Kaya dito namin pumunta sa ilang mga tunog.

1102
00:51:01,933 --> 00:51:06,620

1103
00:51:06,620 --> 00:51:10,490
Ito ang pagpapasok ng uri, kaya muli
lamang ito ay pagharap sa ang mga elemento

1104
00:51:10,490 --> 00:51:13,420
bilang dumating sila.

1105
00:51:13,420 --> 00:51:17,180
Ito ang bubble sort, kaya ito ay
alang ang mga ito pares sa isang pagkakataon.

1106
00:51:17,180 --> 00:51:22,030

1107
00:51:22,030 --> 00:51:24,490
At muli, ang pinakamalaking elemento
ay bulubok up sa tuktok.

1108
00:51:24,490 --> 00:51:38,098

1109
00:51:38,098 --> 00:51:41,710
>> Next up pagpili-uuri.

1110
00:51:41,710 --> 00:51:45,420
Ito ang ni Ben algorithm, kung saan
muli siya ay pagpili iteratively

1111
00:51:45,420 --> 00:51:46,843
sa susunod na pinakamaliit na elemento.

1112
00:51:46,843 --> 00:51:49,801

1113
00:51:49,801 --> 00:51:53,900
At muli, ngayon maaari mong talagang marinig na
ito ay bilis ng takbo ninyo up ngunit lamang sa gana

1114
00:51:53,900 --> 00:51:58,230
bilang ito ay paggawa ng mas mababa at mas kaunti
trabaho sa bawat pag-ulit.

1115
00:51:58,230 --> 00:52:04,170
Ito ang mas mabilis na isa, pagsamahin uri,
na kung saan ay pag-uuri ng mga kumpol ng mga numero

1116
00:52:04,170 --> 00:52:05,971
sama-sama at pagkatapos ay pagsasama-sama ng mga ito.

1117
00:52:05,971 --> 00:52:07,720
Kaya look-- kaliwa
kalahati ay naka-pinagsunod-sunod.

1118
00:52:07,720 --> 00:52:14,165
>> Ngayon ito ay pag-uuri ang kanang kalahati, at
ngayon ito ay pagpunta sa pagsamahin ang mga ito sa isa.

1119
00:52:14,165 --> 00:52:19,160
Ito ay isang bagay na tinatawag na "Gnome uri."

1120
00:52:19,160 --> 00:52:23,460
At maaari mong uri ng makita na
ito ay pagpunta papunta at pabalik,

1121
00:52:23,460 --> 00:52:27,950
pag-aayos ng trabaho ng isang maliit na bit dito at
may bago ito naaayos sa mga bagong trabaho.

1122
00:52:27,950 --> 00:52:32,900

1123
00:52:32,900 --> 00:52:33,692
At na ito.

1124
00:52:33,692 --> 00:52:36,400
May isa pang uri, na kung saan ay
talagang lamang para sa akademikong layunin,

1125
00:52:36,400 --> 00:52:40,980
tinatawag na "bobo uri," na tumatagal
ang iyong data, uri ito random,

1126
00:52:40,980 --> 00:52:43,350
at pagkatapos ay sumusuri kung ito ay pinagsunod-sunod.

1127
00:52:43,350 --> 00:52:47,880
At kung ito ay hindi, ito muling uri ito
random, sumusuri kung ito ay pinagsunod-sunod,

1128
00:52:47,880 --> 00:52:49,440
at kung hindi inuulit.

1129
00:52:49,440 --> 00:52:52,660
At sa teorya, probabilistically
ito ay makumpleto,

1130
00:52:52,660 --> 00:52:54,140
ngunit pagkatapos ng lubos ng kaunti ng oras.

1131
00:52:54,140 --> 00:52:56,930
Ito ay hindi ang pinaka-
mahusay ng mga algorithm.

1132
00:52:56,930 --> 00:53:02,550
Kaya ang anumang mga katanungan sa mga
partikular na algorithm o anumang bagay

1133
00:53:02,550 --> 00:53:04,720
may kaugnayan doon, masyadong?

1134
00:53:04,720 --> 00:53:09,430
>> Well, sabihin ngayon manunudyo bukod kung ano ang lahat
mga linyang ito ay na ako ng pagguhit

1135
00:53:09,430 --> 00:53:15,090
at kung ano ako sa pag-aakala ang computer
maaaring gawin sa ilalim ng hood.

1136
00:53:15,090 --> 00:53:18,650
Gusto ko magtaltalan na ang lahat ng mga numerong ito
Panatilihin ko drawing-- kailangan nila upang makakuha

1137
00:53:18,650 --> 00:53:21,330
naka-imbak sa isang lugar sa memorya.

1138
00:53:21,330 --> 00:53:24,130
Susubukan naming kumuha alisan ng ang tao na ito ngayon, masyadong.

1139
00:53:24,130 --> 00:53:30,110
>> Kaya ang isang piraso ng memorya sa isang
computer-- kaya RAM DIMM ay

1140
00:53:30,110 --> 00:53:35,480
kung ano ang aming hinanap kahapon, dual
inline memory module-- ganito ang hitsura.

1141
00:53:35,480 --> 00:53:39,370
At bawat isa sa mga maliit na itim na chips
ilang bilang ng mga bytes, karaniwang.

1142
00:53:39,370 --> 00:53:44,380
At pagkatapos ay ang gold pins ay gaya ng mga
wires na ikonekta ito sa computer,

1143
00:53:44,380 --> 00:53:47,521
at ang berde silikon board ay lamang
kung ano ang mapigil ang lahat ng bagay sa lahat ng sama-sama.

1144
00:53:47,521 --> 00:53:48,770
Kaya kung ano ang na ito ay talagang ibig sabihin nito?

1145
00:53:48,770 --> 00:53:53,180
Kung ako uri ng gumuhit ito parehong larawan,
sabihin ipagpalagay para sa simple

1146
00:53:53,180 --> 00:53:55,280
na ito DIMM, dual
inline memory module,

1147
00:53:55,280 --> 00:54:00,530
ay isa gigabyte ng RAM, isang gigabyte ng
memory, na kung saan ay kung gaano karaming bytes kabuuang?

1148
00:54:00,530 --> 00:54:02,100
One gigabyte ay kung gaano karaming bytes?

1149
00:54:02,100 --> 00:54:04,860

1150
00:54:04,860 --> 00:54:06,030
Higit pa diyan.

1151
00:54:06,030 --> 00:54:09,960
1,124 ay kilo, 1,000.

1152
00:54:09,960 --> 00:54:11,730
Mega ay million.

1153
00:54:11,730 --> 00:54:14,570
Giga ay isang bilyon.

1154
00:54:14,570 --> 00:54:15,070
>> Ako ba ay namamalagi?

1155
00:54:15,070 --> 00:54:16,670
Puwede ba kaming kahit na basahin ang label?

1156
00:54:16,670 --> 00:54:19,920
Ito ay talagang 128
gigabytes, kaya higit pa.

1157
00:54:19,920 --> 00:54:22,130
Ngunit kami ay magpanggap na ito
ay isa lamang gigabyte.

1158
00:54:22,130 --> 00:54:25,640
Kaya na nangangahulugan na mayroong isang bilyong
bytes ng memorya na magagamit sa akin

1159
00:54:25,640 --> 00:54:29,770
o 8 bilyong bits, ngunit kami ay pagpunta
upang makipag-usap sa mga tuntunin ng mga byte ngayon,

1160
00:54:29,770 --> 00:54:30,750
sumulong.

1161
00:54:30,750 --> 00:54:36,330
>> Kaya kung ano ang ibig sabihin nito ay na ito ay
isa byte, ito ay isa pang byte,

1162
00:54:36,330 --> 00:54:38,680
ito ay isa pang byte,
at kung kami ay talagang nais

1163
00:54:38,680 --> 00:54:43,280
upang maging tiyak gusto naming magkaroon upang
gumuhit ng isang billion maliit na mga parisukat.

1164
00:54:43,280 --> 00:54:44,320
Ngunit ano ang ibig sabihin nito?

1165
00:54:44,320 --> 00:54:46,420
Well, ipaalam sa akin lamang mag-zoom
in sa this picture.

1166
00:54:46,420 --> 00:54:50,900
Kung Mayroon akong isang bagay na mukhang
tulad nito ngayon, na apat na bytes.

1167
00:54:50,900 --> 00:54:53,710
>> At kaya ako ay maaaring ilagay ang apat na numero dito.

1168
00:54:53,710 --> 00:54:54,990
Isa dalawa tatlo apat.

1169
00:54:54,990 --> 00:55:00,170
O maaari ko bang ilagay ang apat na mga titik o simbolo.

1170
00:55:00,170 --> 00:55:02,620
"Hey!" maaaring pumunta doon,
dahil ang bawat isa ng mga titik,

1171
00:55:02,620 --> 00:55:04,370
namin tinalakay nang mas maaga,
ay maaaring kinakatawan

1172
00:55:04,370 --> 00:55:06,650
na may walong bits o ASCII o isang byte.

1173
00:55:06,650 --> 00:55:09,370
Kaya sa ibang salita, maaari mong
ilagay 8 bilyon bagay sa loob

1174
00:55:09,370 --> 00:55:11,137
ng isang ito stick ng memorya.

1175
00:55:11,137 --> 00:55:14,345
Ngayon kung ano ang ibig sabihin na ilagay ang mga bagay sa likod
upang i-back upang i-back sa memory tulad nito?

1176
00:55:14,345 --> 00:55:17,330
Ito ay kung ano ang isang programista
ay tumawag ng isang "array."

1177
00:55:17,330 --> 00:55:21,250
Sa isang computer program, tingin ninyo ay hindi
tungkol sa mga pinagbabatayan ng hardware, per se.

1178
00:55:21,250 --> 00:55:24,427
Ikaw lamang ang tingin ng iyong sarili bilang pagkakaroon ng
access sa isang kabuuang billion bytes,

1179
00:55:24,427 --> 00:55:26,010
at maaari mong kahit anong gusto mo dito.

1180
00:55:26,010 --> 00:55:27,880
Ngunit para sa kaginhawahan
ito ay karaniwang kapaki-pakinabang

1181
00:55:27,880 --> 00:55:31,202
upang mapanatili ang iyong memory karapatan
tabi ng bawat isa na katulad nito.

1182
00:55:31,202 --> 00:55:33,660
Kaya kung ako mag-zoom in sa this--
dahil tiyak na kami ay hindi pagpunta

1183
00:55:33,660 --> 00:55:39,310
upang gumuhit ng isang billion maliit squares--
sabihin ipagpalagay na ang board na ito ay kumakatawan sa

1184
00:55:39,310 --> 00:55:40,610
na stick ng memorya na ngayon.

1185
00:55:40,610 --> 00:55:43,800
At kukunin ko na lang gumuhit ng marami ayon sa aking
marker nagtatapos up pagbibigay sa akin dito.

1186
00:55:43,800 --> 00:55:46,420

1187
00:55:46,420 --> 00:55:52,300
Kaya ngayon kami ay may isang stick
ng memory sa board

1188
00:55:52,300 --> 00:55:56,400
na nakuha ng isa, dalawa, tatlo, apat, lima,
anim, isa, dalawa, tatlo, apat, lima, anim,

1189
00:55:56,400 --> 00:56:01,130
seven-- kaya 42 bytes ng
memory sa kabuuang screen.

1190
00:56:01,130 --> 00:56:01,630
Salamat.

1191
00:56:01,630 --> 00:56:02,838
Oo, ginawa ang aking mga arithmetic karapatan.

1192
00:56:02,838 --> 00:56:05,120
Kaya 42 bytes ng memory dito.

1193
00:56:05,120 --> 00:56:06,660
Kaya kung ano ang na ito tunay na ibig sabihin?

1194
00:56:06,660 --> 00:56:09,830
Well, isang computer programmer
Gusto talagang pangkalahatan

1195
00:56:09,830 --> 00:56:12,450
tingin ng mga ito bilang memory addressable.

1196
00:56:12,450 --> 00:56:16,630
Sa ibang salita, ang bawat isa sa mga ito
lokasyon sa memorya, sa hardware,

1197
00:56:16,630 --> 00:56:18,030
ay may isang natatanging address.

1198
00:56:18,030 --> 00:56:22,020
>> Ito ay hindi bilang kumplikadong bilang One Brattle
Square, Cambridge, Mass., 02138.

1199
00:56:22,020 --> 00:56:23,830
Sa halip, ito ay lamang ng isang numero.

1200
00:56:23,830 --> 00:56:27,930
Ito ang byte numerong zero, ito ay
isa, ito ay dalawang, ito ay tatlo,

1201
00:56:27,930 --> 00:56:30,327
at ito ay 41.

1202
00:56:30,327 --> 00:56:30,910
Maghintay ng isang minuto.

1203
00:56:30,910 --> 00:56:32,510
Akala ko ang sinabi ko 42 sa isang sandali ang nakalipas.

1204
00:56:32,510 --> 00:56:35,050

1205
00:56:35,050 --> 00:56:37,772
Sinimulan ko ang pagbibilang sa zero,
kaya na talagang tama.

1206
00:56:37,772 --> 00:56:40,980
Ngayon hindi namin ay may upang aktwal na gumuhit ito
bilang isang grid, at kung gumuhit ka ito bilang isang grid

1207
00:56:40,980 --> 00:56:43,520
Sa tingin ko bagay na talagang
makakuha ng isang bit nakaliligaw.

1208
00:56:43,520 --> 00:56:46,650
Ano ang isang programmer ay,
sa kanyang sariling pag-iisip,

1209
00:56:46,650 --> 00:56:50,310
sa pangkalahatan sa tingin ng mga ito
memorya bilang ay tulad ng isang tape,

1210
00:56:50,310 --> 00:56:53,340
gaya ng putol ng masking tape
na lamang napupunta sa at sa magpakailanman

1211
00:56:53,340 --> 00:56:54,980
o hanggang sa naubusan ka ng memorya.

1212
00:56:54,980 --> 00:56:59,200
Kaya ang isang mas karaniwang paraan upang gumuhit
at sa tingin lamang tungkol memory

1213
00:56:59,200 --> 00:57:03,710
ay magiging na ito ay byte zero, isa,
dalawa, tatlo, at pagkatapos ay tuldok, tuldok, tuldok.

1214
00:57:03,710 --> 00:57:07,650
At mayroon kang 42 tulad bytes total, kahit
bagaman pisikal ito maaaring aktwal na

1215
00:57:07,650 --> 00:57:09,480
maging isang bagay na mas tulad nito.

1216
00:57:09,480 --> 00:57:12,850
>> Kaya't kung ikaw ngayon sa tingin ng iyong
memory ng mga ito, tulad ng isang tape,

1217
00:57:12,850 --> 00:57:17,640
ito ay kung ano ang isang programista muli
ay tumawag ng isang array ng memory.

1218
00:57:17,640 --> 00:57:20,660
At kapag gusto mong aktwal na tindahan
isang bagay sa memorya ng isang computer,

1219
00:57:20,660 --> 00:57:23,290
ikaw ay karaniwang gawin ang mga bagay store
i-back-to-back upang i-back-to-back.

1220
00:57:23,290 --> 00:57:25,010
Kaya kami ay pakikipag-usap tungkol sa mga numero.

1221
00:57:25,010 --> 00:57:30,880
At kapag gusto ko upang malutas ang problema
tulad ng apat, isa, tatlo, dalawa,

1222
00:57:30,880 --> 00:57:33,820
kahit na lamang ako ay pagguhit
lamang ang mga numero apat, isa, tatlo,

1223
00:57:33,820 --> 00:57:39,490
dalawang sa board, ang computer gagawin
talagang may ganitong setup sa memorya.

1224
00:57:39,490 --> 00:57:43,347
>> At kung ano ang magiging sa tabi ng
dalawa sa memory ng computer?

1225
00:57:43,347 --> 00:57:44,680
Well, walang kasagutan sa na.

1226
00:57:44,680 --> 00:57:45,770
Hindi namin talaga alam.

1227
00:57:45,770 --> 00:57:48,200
At habang ang mga
computer ay hindi ito kailangan,

1228
00:57:48,200 --> 00:57:51,440
ito ay hindi kailangang pag-aalaga kung ano ang susunod
sa mga numero ng ginagawa nito pag-aalaga tungkol.

1229
00:57:51,440 --> 00:57:55,130
At kapag sinabi ko mas maaga na ang isang computer
ay maaari lamang tumingin sa isa address sa isang pagkakataon,

1230
00:57:55,130 --> 00:57:56,170
ito ay uri ng kung bakit.

1231
00:57:56,170 --> 00:57:59,490
>> Hindi hindi katulad ng isang record
player at isang pagbabasa ulo

1232
00:57:59,490 --> 00:58:03,030
lamang pagiging able sa tumingin sa isang tiyak na
uka sa isang pisikal na record old-school

1233
00:58:03,030 --> 00:58:06,500
sa isang panahon, katulad
Maaari isang computer thanks

1234
00:58:06,500 --> 00:58:09,810
sa kanyang CPU at ang kanyang
Intel pagtuturo set,

1235
00:58:09,810 --> 00:58:12,480
kabilang na ang pagtuturo
ay basahin mula sa memorya

1236
00:58:12,480 --> 00:58:15,590
o i-save sa memory-- isang
computer ay maaaring lamang tumingin

1237
00:58:15,590 --> 00:58:19,210
sa isang lokasyon sa isang time--
minsan ng isang kumbinasyon ng mga ito,

1238
00:58:19,210 --> 00:58:21,770
ngunit talagang lamang sa isang lokasyon sa isang pagkakataon.

1239
00:58:21,770 --> 00:58:24,770
Kaya kapag kami ay ginagawa
mga iba't-ibang mga algorithm,

1240
00:58:24,770 --> 00:58:28,110
Hindi ko na lamang ang pagsusulat sa isang
vacuum-- apat, isa, tatlo, dalawa.

1241
00:58:28,110 --> 00:58:30,849
Yaong mga numero talagang nabibilang
sa tabi-tabi pisikal sa memorya.

1242
00:58:30,849 --> 00:58:32,890
Kaya may mga maliliit na maliit
transistors o ilang mga uri

1243
00:58:32,890 --> 00:58:35,840
ng electronics sa ilalim ng
hood sa pag-iimbak ng mga halagang ito.

1244
00:58:35,840 --> 00:58:40,460
>> At sa kabuuan, kung gaano karaming mga bits ay
kasangkot sa ngayon, lamang na maging malinaw?

1245
00:58:40,460 --> 00:58:45,580
Kaya ito ay apat na bytes, o
ngayon ito ay 32 bits total.

1246
00:58:45,580 --> 00:58:49,280
Kaya may mga tunay na 32 mga zero at
mga aakda ang apat na bagay.

1247
00:58:49,280 --> 00:58:52,070
Mayroong kahit higit pa sa paglipas dito, ngunit
muli hindi namin pakialam tungkol sa na.

1248
00:58:52,070 --> 00:58:55,120
>> Kaya ngayon sabihin humingi ng isa pang
tanong gamit memory,

1249
00:58:55,120 --> 00:58:57,519
dahil na sa dulo
ng araw ay sa pag-iiba.

1250
00:58:57,519 --> 00:59:00,310
Walang bagay na kung ano ang maaari naming gawin sa mga
ang computer, sa dulo ng araw

1251
00:59:00,310 --> 00:59:02,560
ang hardware ay pa rin ang
parehong sa ilalim ng hood.

1252
00:59:02,560 --> 00:59:04,670
Paano Gusto ko mag-imbak ng isang salita sa dito?

1253
00:59:04,670 --> 00:59:09,710
Well, isang salita sa isang computer tulad ng
"Hey!" ay naka-imbak tulad nito lamang.

1254
00:59:09,710 --> 00:59:12,300
At kung ikaw ay wanted sa isang mas mahabang
salita, maaari mo lamang

1255
00:59:12,300 --> 00:59:19,120
patungan na iyon at sabihin ng isang bagay
tulad ng "hello" at mag-imbak na dito.

1256
00:59:19,120 --> 00:59:23,930
>> At kaya dito, masyadong, ito contiguousness
ay talagang isang bentahe,

1257
00:59:23,930 --> 00:59:26,530
dahil ang isang computer ay maaaring lamang
basahin mula sa kanan papuntang kaliwa.

1258
00:59:26,530 --> 00:59:28,680
Ngunit narito ang isang tanong.

1259
00:59:28,680 --> 00:59:33,480
Sa konteksto ng salitang ito,
h-e-l-l-o, exclamation point,

1260
00:59:33,480 --> 00:59:38,740
kung paano maaaring ang computer alam kung saan ang
salita ay nagsisimula at kung saan ang salita ay nagtatapos?

1261
00:59:38,740 --> 00:59:41,690

1262
00:59:41,690 --> 00:59:43,800
Sa konteksto ng mga numero,
kung paano gumagana ang computer

1263
00:59:43,800 --> 00:59:48,396
alam kung gaano katagal ang pagkakasunod-sunod ng
numero ay o kung saan ito ay nagsisimula?

1264
00:59:48,396 --> 00:59:50,270
Well, ito ay lumiliko out--
at hindi namin ay pumunta masyadong maraming

1265
00:59:50,270 --> 00:59:54,970
sa antas na ito ng detail--
computer ilipat bagay sa paligid sa memorya

1266
00:59:54,970 --> 00:59:57,800
literal sa pamamagitan ng paraan ng mga address na ito.

1267
00:59:57,800 --> 01:00:02,080
Kaya sa isang computer, kung ikaw ay
pagsusulat ng code upang mag-imbak ng mga bagay

1268
01:00:02,080 --> 01:00:05,800
tulad ng mga salita, kung ano ang ikaw ay
talagang ginagawa ay nagta-type

1269
01:00:05,800 --> 01:00:11,320
expression na matandaan kung saan sa
memory ng computer ang mga salitang ito ay.

1270
01:00:11,320 --> 01:00:14,370
Kaya hayaan mo akong gawin ang isang napaka,
napaka-simpleng halimbawa.

1271
01:00:14,370 --> 01:00:18,260
>> Ako pagpunta sa sige at
buksan up ng isang simpleng programa ng teksto,

1272
01:00:18,260 --> 01:00:20,330
at ako pagpunta upang lumikha ng
isang file na tinatawag hello.c.

1273
01:00:20,330 --> 01:00:22,849
Karamihan ng impormasyon na ito namin
hindi pumunta sa sa mahusay na detalye,

1274
01:00:22,849 --> 01:00:25,140
ngunit ako pagpunta sa magsulat ng isang
program sa parehong wika,

1275
01:00:25,140 --> 01:00:31,140
C. Ito ay malayo mas intimidating,
Gusto ko magtaltalan, kaysa sa simula,

1276
01:00:31,140 --> 01:00:32,490
ngunit ito ay halos kapareho sa espiritu.

1277
01:00:32,490 --> 01:00:34,364
Sa katunayan, mga kulot
braces-- Maaari mong uri ng

1278
01:00:34,364 --> 01:00:37,820
isip ng kung ano lang ginawa ko ng mga ito.

1279
01:00:37,820 --> 01:00:39,240
>> Natin gawin ito, ang tunay na Hayaan.

1280
01:00:39,240 --> 01:00:45,100
Kapag berdeng bandila click,
gawin ang sumusunod.

1281
01:00:45,100 --> 01:00:50,210
gusto kong i-print out "hello."

1282
01:00:50,210 --> 01:00:51,500
Kaya ito ay pseudocode ngayon.

1283
01:00:51,500 --> 01:00:53,000
Ako uri ng blurring ng mga linya.

1284
01:00:53,000 --> 01:00:56,750
Sa C, wikang ito ako pinag
tungkol sa, ang linyang ito print kumusta

1285
01:00:56,750 --> 01:01:01,940
talagang nagiging "printf" na may
ilang mga panaklong at isang semi-colon.

1286
01:01:01,940 --> 01:01:03,480
>> Ngunit ito ay ang eksaktong parehong ideya.

1287
01:01:03,480 --> 01:01:06,730
At ito tunay user-friendly
"Kapag berdeng bandila click" ay nagiging

1288
01:01:06,730 --> 01:01:10,182
ang mas arcane "int pangunahing walang bisa."

1289
01:01:10,182 --> 01:01:12,890
At ito tunay ay walang mapping,
kaya lang ako pagpunta sa huwag pansinin na.

1290
01:01:12,890 --> 01:01:17,210
Ngunit ang kulot tirante ay gaya ng mga
hubog piraso puzzle tulad nito.

1291
01:01:17,210 --> 01:01:18,700
>> Kaya maaari mong uri ng hulaan.

1292
01:01:18,700 --> 01:01:22,357
Kahit na hindi mo na program bago,
kung ano ang ibig sa programang ito marahil gawin?

1293
01:01:22,357 --> 01:01:25,560

1294
01:01:25,560 --> 01:01:28,000
Marahil Kopya kumusta
na may isang exclamation point.

1295
01:01:28,000 --> 01:01:29,150
>> Kaya sabihin subukan na.

1296
01:01:29,150 --> 01:01:30,800
Ako pagpunta sa i-save ito.

1297
01:01:30,800 --> 01:01:34,000
At ito ay, muli, isang napaka
old kapaligiran ng paaralan.

1298
01:01:34,000 --> 01:01:35,420
Hindi ko ma-i-click ang, hindi ko maaaring i-drag.

1299
01:01:35,420 --> 01:01:36,910
Mayroon akong mag-type utos.

1300
01:01:36,910 --> 01:01:41,320
Kaya gusto kong patakbuhin ang aking programa, kaya
maaari kong gawin ito, tulad ng hello.c.

1301
01:01:41,320 --> 01:01:42,292
Iyan ang file ako ran.

1302
01:01:42,292 --> 01:01:43,500
Ngunit maghintay, ako nawawala ng isang hakbang.

1303
01:01:43,500 --> 01:01:46,470
Ano ang sinabi namin ay isang kinakailangang
hakbang para sa isang wika tulad ng C?

1304
01:01:46,470 --> 01:01:49,470
Lamang ko na nakasulat na pinagmulan
code, ngunit kung ano ang kailangan ko?

1305
01:01:49,470 --> 01:01:50,670
Yeah, kailangan ko ng isang tagatala.

1306
01:01:50,670 --> 01:01:57,670
Kaya sa aking Mac dito, mayroon akong isang
programa na tinatawag GCC, GNU C compiler,

1307
01:01:57,670 --> 01:02:03,990
na nagpapahintulot sa akin na gawin this-- tira
aking source code sa, kami ay tumawag ito,

1308
01:02:03,990 --> 01:02:04,930
machine code.

1309
01:02:04,930 --> 01:02:10,180
>> At maaari ko bang makita na,
muli, tulad ng sumusunod, ang mga ito

1310
01:02:10,180 --> 01:02:14,090
ang mga zero at mga ko lang
nilikha mula sa aking source code,

1311
01:02:14,090 --> 01:02:15,730
ang lahat ng mga zero at mga.

1312
01:02:15,730 --> 01:02:17,770
At kung gusto kong patakbuhin
aking program-- ito ang mangyayari

1313
01:02:17,770 --> 01:02:23,010
na tinatawag a.out para
makasaysayang reasons-- "hello."

1314
01:02:23,010 --> 01:02:24,070
Maaari ko bang patakbuhin itong muli.

1315
01:02:24,070 --> 01:02:25,690
Kumusta kumusta kumusta.

1316
01:02:25,690 --> 01:02:27,430
At ito ay anyong nagtatrabaho.

1317
01:02:27,430 --> 01:02:31,000
>> Ngunit na nangangahulugan sa isang lugar sa aking
memory ng computer ay ang mga salita

1318
01:02:31,000 --> 01:02:35,279
h-e-l-l-o, exclamation point.

1319
01:02:35,279 --> 01:02:38,070
At ito ay lumiliko out, lamang bilang isang bukod,
kung ano ang isang computer na gagawin ay karaniwang

1320
01:02:38,070 --> 01:02:40,550
gawin upang ito nakakaalam kung saan
bagay simulan at end-- ito ay

1321
01:02:40,550 --> 01:02:42,460
pagpunta sa maglagay ng isang espesyal na simbolo dito.

1322
01:02:42,460 --> 01:02:46,064
At ang convention ay upang ilagay ang
numerong zero sa dulo ng isang salita

1323
01:02:46,064 --> 01:02:48,230
sa gayon ay alam mo kung saan ito
aktwal na nagtatapos, sa gayon ay ikaw

1324
01:02:48,230 --> 01:02:52,750
hindi panatilihin sa pag-print ang higit pa at higit pa
karakter kaysa sa iyong aktwal balak.

1325
01:02:52,750 --> 01:02:55,400
>> Ngunit ang takeaway dito, kahit na
kahit na ito ay medyo arcane,

1326
01:02:55,400 --> 01:02:58,140
ay na ito ay sa huli
medyo simple.

1327
01:02:58,140 --> 01:03:04,550
Ikaw ay bibigyan ng isang uri ng isang tape, isang blangkong
space kung saan maaari mong isulat ang mga titik.

1328
01:03:04,550 --> 01:03:07,150
Kailangan lang may sa magkaroon ng isang
espesyal na simbolo, tulad ng arbitrarily

1329
01:03:07,150 --> 01:03:10,316
ang bilang zero, upang ilagay sa dulo ng
ang iyong mga salita nang sa gayon ay alam sa computer,

1330
01:03:10,316 --> 01:03:13,410
oh, dapat ko bang itigil printing matapos
nakikita ko ang exclamation point.

1331
01:03:13,410 --> 01:03:16,090
Dahil ang susunod na bagay doon
ay isang ASCII na halaga ng zero,

1332
01:03:16,090 --> 01:03:19,125
o ang null karakter bilang
ang isang tao ay tumawag ito.

1333
01:03:19,125 --> 01:03:21,500
Ngunit mayroong uri ng isang problema
dito, at sabihin bumalik

1334
01:03:21,500 --> 01:03:23,320
sa mga numero para sa isang sandali.

1335
01:03:23,320 --> 01:03:28,720
Ipagpalagay na ko, sa katunayan,
magkaroon ng isang array ng mga numero,

1336
01:03:28,720 --> 01:03:30,730
at ipagpalagay na ang
program Sumulat ako ay

1337
01:03:30,730 --> 01:03:34,680
tulad ng isang grado ng libro para sa isang guro
at isang guro sa silid.

1338
01:03:34,680 --> 01:03:38,720
At ang program na ito ay nagbibigay-daan sa kanya
i-type sa mga marka ng kanilang mga estudyante

1339
01:03:38,720 --> 01:03:39,960
sa mga pagsusulit.

1340
01:03:39,960 --> 01:03:43,750
At ipagpalagay na ang estudyante ay makakakuha ng
100 sa kanilang unang pagsusulit, marahil

1341
01:03:43,750 --> 01:03:49,920
tulad ng isang 80 sa susunod na isa, at pagkatapos ng isang
75, pagkatapos ng isang 90 sa ikaapat na pagsusulit.

1342
01:03:49,920 --> 01:03:54,150
>> Kaya sa puntong ito sa kuwento,
array ay ng laki apat.

1343
01:03:54,150 --> 01:03:58,470
Mayroon talagang mas memorya sa
computer, ngunit ang array, kaya na magsalita,

1344
01:03:58,470 --> 01:04:00,350
ay ng laki apat.

1345
01:04:00,350 --> 01:04:06,060
Ipagpalagay na ngayon na ang mga guro ay nais
upang magtalaga ng isang ikalimang pagsusulit sa klase.

1346
01:04:06,060 --> 01:04:08,510
Well, isa sa mga bagay na siya
o siya ay pagpunta sa may sa gawin

1347
01:04:08,510 --> 01:04:10,650
ngayon ay mag-imbak ng isang karagdagang halaga dito.

1348
01:04:10,650 --> 01:04:15,490
Ngunit kung ang array ang guro ay
nilikha sa programang ito ay ang laki para sa,

1349
01:04:15,490 --> 01:04:22,440
ang isa sa mga problema sa isang array ay na
hindi lamang ang maaari mong panatilihin ang pagdaragdag sa memory.

1350
01:04:22,440 --> 01:04:26,470
Dahil kung ano ang kung ang isa pang bahagi ng
programa ay ang salitang "hey" right there?

1351
01:04:26,470 --> 01:04:29,650
>> Sa ibang salita, ang aking memorya ay maaaring maging
ginagamit para sa anumang bagay sa isang programa.

1352
01:04:29,650 --> 01:04:33,250
At kung in advance ko nai-type sa, hey,
Gusto kong input apat na mga marka ng pagsusulit,

1353
01:04:33,250 --> 01:04:34,784
upang sila'y magsiyaon dito at dito.

1354
01:04:34,784 --> 01:04:37,700
At kung ikaw ay biglang magbago ang isip
mamaya at sabihin na gusto kong ikalimang pagsusulit

1355
01:04:37,700 --> 01:04:40,872
puntos, hindi mo magagawa lamang
ilagay ito kung saan man gusto mo,

1356
01:04:40,872 --> 01:04:42,580
dahil kung ano kung ito
memory ay ginagamit

1357
01:04:42,580 --> 01:04:45,990
para sa isang bagay else-- ilang iba pang mga program
o ilang iba pang mga tampok ng programa

1358
01:04:45,990 --> 01:04:46,910
na kayo ay tumatakbo?

1359
01:04:46,910 --> 01:04:50,650
Kaya ikaw ay may mag-isip nang maaga
kung paano mo gustong upang i-imbak ang iyong data,

1360
01:04:50,650 --> 01:04:54,480
dahil ngayon mo na lagyan ng kulay
iyong sarili sa isang digital na sulok.

1361
01:04:54,480 --> 01:04:57,280
>> Kaya isang guro maaaring sa halip
sabihin kapag pagsulat ng isang programa

1362
01:04:57,280 --> 01:04:59,360
upang mag-imbak ang kanyang
marka, alam mo kung ano?

1363
01:04:59,360 --> 01:05:04,180
I am pagpunta upang humiling,
kapag sumusulat ang aking mga programa,

1364
01:05:04,180 --> 01:05:12,070
na gusto kong zero, isa, dalawa, tatlo,
apat, lima, anim, walo marka total.

1365
01:05:12,070 --> 01:05:15,320
Kaya isa, dalawa, tatlo, apat,
lima, anim, pito, walo.

1366
01:05:15,320 --> 01:05:18,612
Guro ay maaaring lamang over-allocate
memory kapag sumusulat kanyang programa

1367
01:05:18,612 --> 01:05:19,570
at sabihin mo, alam mo kung ano?

1368
01:05:19,570 --> 01:05:22,236
hindi ako pagpunta sa magtalaga ng karagdagang
sa walong mga pagsusulit sa isang semester.

1369
01:05:22,236 --> 01:05:23,130
Iyan na lamang mabaliw.

1370
01:05:23,130 --> 01:05:24,470
Hindi ko makikita maglaan iyon.

1371
01:05:24,470 --> 01:05:28,270
Kaya na sa ganitong paraan siya ay may ang
flexibility sa mga marka store student,

1372
01:05:28,270 --> 01:05:33,010
tulad ng 75, 90, at marahil isang dagdag na kung saan
ang mag-aaral Nakakuha dagdag na credit, 105.

1373
01:05:33,010 --> 01:05:36,130
>> Ngunit kung ang mga guro ay hindi kailanman
ay gumagamit ng mga ito ng tatlong mga puwang,

1374
01:05:36,130 --> 01:05:38,860
mayroong isang madaling gamitin na takeaway dito.

1375
01:05:38,860 --> 01:05:41,410
Siya o siya lamang ay pag-aaksaya space.

1376
01:05:41,410 --> 01:05:44,790
Kaya sa ibang salita, mayroong ito
karaniwang tradeoff sa programming

1377
01:05:44,790 --> 01:05:48,241
kung saan maaari kang mag-allocate
eksakto tulad ng maraming memorya hangga't gusto mo,

1378
01:05:48,241 --> 01:05:51,490
tuwad ng kung saan ay na ikaw ay sobrang
efficient-- hindi ka pagiging mapag-aksaya

1379
01:05:51,490 --> 01:05:54,640
sa all-- ngunit ang downside sa mga ito
ay kung ano ang kung nagbago ang iyong isip kapag

1380
01:05:54,640 --> 01:05:58,780
gamit ang programa na nais mong iimbak
mas maraming data kaysa sa iyo orihinal na inilaan.

1381
01:05:58,780 --> 01:06:03,030
>> Kaya siguro ang solusyon ay, at pagkatapos,
isulat ang iyong mga programa sa paraan

1382
01:06:03,030 --> 01:06:05,605
na ginagamit nila mas memorya
kaysa sila ay talagang kailangan.

1383
01:06:05,605 --> 01:06:07,730
Sa ganitong paraan hindi ka pagpunta
upang tumakbo sa problemang iyon,

1384
01:06:07,730 --> 01:06:09,730
ngunit ikaw ay pagiging mapag-aksaya.

1385
01:06:09,730 --> 01:06:12,960
At ang mas memorya ng iyong programa ay gumagamit,
bilang namin tinalakay kahapon, mas mababa

1386
01:06:12,960 --> 01:06:15,410
memory na magagamit
para sa iba pang mga programa,

1387
01:06:15,410 --> 01:06:18,790
ang mas maaga ang iyong computer ay maaaring mabagal
down na dahil sa virtual memory.

1388
01:06:18,790 --> 01:06:22,670
At kaya ang ideal na solusyon ay maaaring kung ano?

1389
01:06:22,670 --> 01:06:24,610
>> Under-allocating tila masama.

1390
01:06:24,610 --> 01:06:27,030
Over-allocating tila masama.

1391
01:06:27,030 --> 01:06:31,120
Kaya kung ano ang maaaring maging isang mas mahusay na solusyon?

1392
01:06:31,120 --> 01:06:32,390
Reallocating.

1393
01:06:32,390 --> 01:06:33,590
Maging mas dynamic.

1394
01:06:33,590 --> 01:06:37,520
Huwag pilitin ang iyong sarili upang pumili ng isang
priori, sa simula, kung ano ang gusto mo.

1395
01:06:37,520 --> 01:06:41,370
At tiyak na hindi over-maglaan,
baka mo na mapag-aksaya.

1396
01:06:41,370 --> 01:06:45,770
>> At kaya upang makamit ang layuning iyon, kami
kailangang magtapon ang data na ito istraktura,

1397
01:06:45,770 --> 01:06:48,100
kaya na magsalita, ang layo.

1398
01:06:48,100 --> 01:06:51,080
At kaya kung ano ang isang programmer
ay karaniwang gamitin

1399
01:06:51,080 --> 01:06:55,940
ay isang bagay na tinatawag hindi isang
array ngunit isang naka-link na listahan.

1400
01:06:55,940 --> 01:07:00,860
Sa ibang salita, siya ay
magsimulang mag-isip ng kanilang mga memory

1401
01:07:00,860 --> 01:07:05,280
bilang uri ng isang hugis na sila
maaari gumuhit sa mga sumusunod na paraan.

1402
01:07:05,280 --> 01:07:08,520
Kung gusto kong mag-imbak ng isang numero sa
isang program-- kaya Setyembre,

1403
01:07:08,520 --> 01:07:12,600
Ibinigay ko ang aking mga mag-aaral ng isang pagsusulit; gusto ko
upang mag-imbak unang pagsusulit ang mga mag-aaral ',

1404
01:07:12,600 --> 01:07:16,220
at sila got ang isang 100 sa it-- ko
ay pagpunta sa hilingin ang aking computer,

1405
01:07:16,220 --> 01:07:19,540
sa pamamagitan ng paraan ng programa na hindi ko na
nakasulat, para sa isa tipak ng memory.

1406
01:07:19,540 --> 01:07:22,570
At ako pagpunta sa tindahan ng
number 100 sa loob nito, at iyon ito.

1407
01:07:22,570 --> 01:07:24,820
>> Pagkatapos ng ilang linggo mamaya
kapag nakukuha ko ang aking pangalawang pagsusulit,

1408
01:07:24,820 --> 01:07:27,890
at ito ay oras na mag-type
sa na 90%, I am pagpunta

1409
01:07:27,890 --> 01:07:32,129
upang hilingin sa computer, hey, computer,
Maaari ba akong magkaroon ng isa pang tipak ng memory?

1410
01:07:32,129 --> 01:07:34,170
Ito ay pagpunta sa bigyan ako ito
Walang laman tipak ng memory.

1411
01:07:34,170 --> 01:07:39,370
Pupunta ako upang ilagay sa bilang 90,
ngunit sa aking mga programa sa anumang paraan o other--

1412
01:07:39,370 --> 01:07:42,100
at hindi namin ay mag-alala tungkol sa
ang syntax para this-- kailangan ko

1413
01:07:42,100 --> 01:07:44,430
upang kahit papaano ay kadena ng mga bagay na sama-sama.

1414
01:07:44,430 --> 01:07:47,430
At kukunin ko na kadena ang mga ito kasama ang
kung ano ang hitsura tulad ng isang arrow dito.

1415
01:07:47,430 --> 01:07:50,050
>> Ang ikatlong pagsusulit na nanggagaling up,
Ako pagpunta sa sabihin, hey, computer,

1416
01:07:50,050 --> 01:07:51,680
bigyan ako ng isa pang tipak ng memory.

1417
01:07:51,680 --> 01:07:54,660
At ako pagpunta upang ilagay down na
ano man ito ay, tulad ng 75,

1418
01:07:54,660 --> 01:07:56,920
at kailangan kong chain na ito
magkasama ngayon sa anumang paraan.

1419
01:07:56,920 --> 01:08:00,290
Fourth pagsusulit ay dumating kasama, at marahil
iyon patungo sa katapusan ng semestre.

1420
01:08:00,290 --> 01:08:03,140
At sa pamamagitan ng puntong iyon ang aking mga programa
ay maaaring maging gamit memory

1421
01:08:03,140 --> 01:08:05,540
lahat ng dako ng lugar, sa buong pisikal.

1422
01:08:05,540 --> 01:08:08,170
At kaya lamang sa mga kicks, ako
pagpunta sa gumuhit ito hanggang

1423
01:08:08,170 --> 01:08:11,260
quiz-- nakalimutan ko kung ano ito ay; ako
tingin siguro isang 80 o something--

1424
01:08:11,260 --> 01:08:12,500
paraan sa paglipas dito.

1425
01:08:12,500 --> 01:08:15,920
>> Ngunit iyon lamang ang fine, dahil pictorially
Pupunta ako upang gumuhit ang linyang ito.

1426
01:08:15,920 --> 01:08:19,063
Sa ibang salita, sa katotohanan,
sa hardware ng iyong computer,

1427
01:08:19,063 --> 01:08:20,979
ang unang puntos baka
end up dito dahil ito ay

1428
01:08:20,979 --> 01:08:22,529
karapatan sa simula ng semestre.

1429
01:08:22,529 --> 01:08:25,810
Ang susunod na isa ay maaaring end up dito
dahil ang isang bit ng oras ang lumipas

1430
01:08:25,810 --> 01:08:27,210
at ang programa mapigil ang pagtakbo.

1431
01:08:27,210 --> 01:08:30,060
Ang susunod na iskor, na kung saan ay
isang 75, ay maaaring maging sa paglipas dito.

1432
01:08:30,060 --> 01:08:33,420
At ang huling puntos ay maaaring maging
isang 80, na kung saan ay higit sa dito.

1433
01:08:33,420 --> 01:08:38,729
>> Kaya sa katotohanan, pisikal, ito ay maaaring maging
ano ang memorya ng iyong computer kamukha.

1434
01:08:38,729 --> 01:08:41,569
Ngunit ito ay hindi isang kapaki-pakinabang mental
paradaym para sa isang computer programmer.

1435
01:08:41,569 --> 01:08:44,649
Bakit dapat mong pag-aalaga kung saan ang
ano ba ang iyong data ay nagtatapos up?

1436
01:08:44,649 --> 01:08:46,200
Gusto mo lamang upang mag-imbak ng data.

1437
01:08:46,200 --> 01:08:49,390
>> Ito ay uri ng tulad ng ating talakayan
mas maaga ng pagguhit ang kubo.

1438
01:08:49,390 --> 01:08:52,200
Bakit mo pag-aalaga kung ano ang
ang mga anggulo ay ng kubo

1439
01:08:52,200 --> 01:08:53,740
at kung paano mo ay may upang i-sa gumuhit ito?

1440
01:08:53,740 --> 01:08:54,950
Gusto mo lamang ng isang kubo.

1441
01:08:54,950 --> 01:08:57,359
Katulad nito dito, ikaw
lamang ang nais na grado book.

1442
01:08:57,359 --> 01:08:59,559
Gusto mo lang mag-isip ng
ito bilang isang listahan ng mga numero.

1443
01:08:59,559 --> 01:09:01,350
Sino ang nagmamalasakit kung paano ito ay
ipinatupad sa hardware?

1444
01:09:01,350 --> 01:09:05,180
>> Kaya ang abstraction ngayon
ay ang larawang ito dito.

1445
01:09:05,180 --> 01:09:07,580
Ito ay isang listahan ng mga link, pati na
isang programmer ay tumawag ito,

1446
01:09:07,580 --> 01:09:10,640
insofar bilang ikaw ay may isang
list, nang walang alinlangan ng mga numero.

1447
01:09:10,640 --> 01:09:14,990
Ngunit ito ay naka-link pictorially
sa pamamagitan ng paraan ng mga arrow,

1448
01:09:14,990 --> 01:09:18,510
at lahat ng mga arrow are-- ilalim
ng hood, kung gusto mong malaman,

1449
01:09:18,510 --> 01:09:23,210
pagpapabalik na ang aming pisikal na hardware ay may
addresses zero, isa, dalawa, tatlo, apat.

1450
01:09:23,210 --> 01:09:28,465
Ang lahat ng mga pana ay ay tulad ng isang mapa
o mga direksyon, kung saan kung 90 is-- ngayon

1451
01:09:28,465 --> 01:09:29,090
Nakatanggap ako upang mabilang.

1452
01:09:29,090 --> 01:09:31,750
>> Zero, isa, dalawa, tatlo,
apat, lima, anim, pito.

1453
01:09:31,750 --> 01:09:35,640
Mukhang ang 90 ay
memory address bilang na pito.

1454
01:09:35,640 --> 01:09:38,460
Ang lahat ng mga pana ay ay
tulad ng isang maliit scrap ng papel

1455
01:09:38,460 --> 01:09:42,439
na nagbibigay sa mga direksyon sa
program na nagsasabing sundin ang mapa

1456
01:09:42,439 --> 01:09:43,880
upang makakuha ng sa lokasyon pitong.

1457
01:09:43,880 --> 01:09:46,680
At doon ay makikita mo ang
pangalawang pagsusulit na marka ng mag-aaral.

1458
01:09:46,680 --> 01:09:52,100
Samantala, ang 75-- kung patuloy ko ito,
ito ay pito, walo, siyam, 10, 11, 12,

1459
01:09:52,100 --> 01:09:54,240
13, 14, 15.

1460
01:09:54,240 --> 01:09:59,080
>> Ang iba pang mga arrow lamang kumakatawan
isang mapa upang memory location 15.

1461
01:09:59,080 --> 01:10:02,550
Ngunit muli, ang programmer sa pangkalahatan ay
hindi pag-aalaga tungkol sa mga ito antas ng detalye.

1462
01:10:02,550 --> 01:10:05,530
At sa karamihan ng bawat programming
wika ngayon, ang programmer

1463
01:10:05,530 --> 01:10:10,490
Hindi maa-kahit na alam kung saan sa memory
ang mga numerong ito ay tunay.

1464
01:10:10,490 --> 01:10:14,830
Lahat siya ay may sa pag-aalaga tungkol sa ay
na sila ay sa paanuman naka-link nang sama-sama

1465
01:10:14,830 --> 01:10:18,390
sa isang istraktura ng data tulad nito.

1466
01:10:18,390 --> 01:10:21,580
>> Ngunit ito ay lumiliko out hindi
upang makakuha ng masyadong teknikal.

1467
01:10:21,580 --> 01:10:27,430
Ngunit lamang dahil maaari naming marahil
kayang magkaroon talakayang ito dito,

1468
01:10:27,430 --> 01:10:33,630
Ipagpalagay na namin muling bisitahin
ang isyu na ito dito ng isang array.

1469
01:10:33,630 --> 01:10:35,780
Tayo'y makita kung kami ikinalulungkot pagpunta dito.

1470
01:10:35,780 --> 01:10:42,950
Ito ay 100, 90, 75, at 80.

1471
01:10:42,950 --> 01:10:44,980
>> Hayaan akong dagli gumawa ito claim.

1472
01:10:44,980 --> 01:10:48,980
Ito ay isang array, at muli, ang
salient katangian ng isang array

1473
01:10:48,980 --> 01:10:52,400
ay na ang lahat ng iyong data ay bumalik sa
back to back in memory-- literal

1474
01:10:52,400 --> 01:10:56,830
isang byte o marahil apat na bytes,
ilang takdang bilang ng mga bytes ang layo.

1475
01:10:56,830 --> 01:11:00,710
Sa isang naka-link na listahan, na kung saan maaari naming gumuhit
tulad nito, sa ilalim ng hood na

1476
01:11:00,710 --> 01:11:02,000
nakakaalam kung saan bagay-bagay na ay?

1477
01:11:02,000 --> 01:11:03,630
Ito ay hindi kahit na kailangan upang dumaloy tulad nito.

1478
01:11:03,630 --> 01:11:06,050
Ang ilan sa mga data ay maaaring
pabalik sa kaliwa hanggang doon.

1479
01:11:06,050 --> 01:11:07,530
Ni hindi mo na malaman.

1480
01:11:07,530 --> 01:11:15,430
>> At kaya sa isang array, mayroon kang isang
tampok na kilala bilang random access.

1481
01:11:15,430 --> 01:11:20,570
At kung ano ang random access ibig sabihin nito ay
na ang computer ay maaaring tumalon agad

1482
01:11:20,570 --> 01:11:22,730
sa anumang lokasyon sa isang array.

1483
01:11:22,730 --> 01:11:23,580
Bakit?

1484
01:11:23,580 --> 01:11:26,000
Dahil ang computer alam
na ang unang lokasyon ay

1485
01:11:26,000 --> 01:11:29,540
zero, isa, dalawa, tatlo.

1486
01:11:29,540 --> 01:11:33,890
>> At kaya kung gusto mong pumunta mula sa
ito ng elemento sa susunod na elemento,

1487
01:11:33,890 --> 01:11:36,099
mong literal, sa
isip computer, idagdag lamang ang isa.

1488
01:11:36,099 --> 01:11:39,140
Kung nais mong pumunta sa ikatlong elemento,
idagdag lamang one-- susunod na elemento, lamang

1489
01:11:39,140 --> 01:11:40,290
magdagdag ng isa.

1490
01:11:40,290 --> 01:11:42,980
Gayunpaman, sa ang bersyon na ito
ng kuwento, ipagpalagay

1491
01:11:42,980 --> 01:11:46,080
ang computer ay kasalukuyang naghahanap
sa o pakikitungo sa mga number 100.

1492
01:11:46,080 --> 01:11:49,770
Paano mo makakuha ng sa susunod
grado sa grade libro?

1493
01:11:49,770 --> 01:11:52,560
>> Mayroon kang gumawa ng pitong
hakbang, na kung saan ay arbitrary.

1494
01:11:52,560 --> 01:11:58,120
Upang makakuha ng sa susunod na isa, kailangan mong
kumuha ng isa pang walong baytang upang makapunta sa 15.

1495
01:11:58,120 --> 01:12:02,250
Sa ibang salita, ito ay hindi isang
pare-pareho ang agwat sa pagitan ng mga numero,

1496
01:12:02,250 --> 01:12:04,857
at kaya ito lamang tumatagal ng
computer na mas maraming oras ay ang point.

1497
01:12:04,857 --> 01:12:06,940
Ang computer na may sa paghahanap
sa pamamagitan ng memory upang

1498
01:12:06,940 --> 01:12:08,990
upang mahanap kung ano ang iyong hinahanap.

1499
01:12:08,990 --> 01:12:14,260
>> Kaya kung saan ang isang array ay may gawi na maging isang
mabilis ang data structure-- dahil ikaw

1500
01:12:14,260 --> 01:12:17,610
maaaring literal lamang gawin simpleng aritmetika
at makakuha ng kung saan mo nais sa pamamagitan ng pagdaragdag ng isa,

1501
01:12:17,610 --> 01:12:21,300
para instance-- isang naka-link na listahan,
mong isakripisyo ang tampok na iyon.

1502
01:12:21,300 --> 01:12:24,020
Hindi ka maaaring pumunta lamang mula sa unang
sa ikalawang sa mga ikatlong sa ika-apat.

1503
01:12:24,020 --> 01:12:25,240
Kailangan mong sundin ang mapa.

1504
01:12:25,240 --> 01:12:28,160
Mayroon kang gumawa ng higit pang mga hakbang
upang makakuha ng mga halaga, na kung saan

1505
01:12:28,160 --> 01:12:30,230
ay tila sa maaari ng pagdagdag ng isang gastos.

1506
01:12:30,230 --> 01:12:35,910
Kaya kami ay nagbabayad ng isang presyo, ngunit kung ano ang
ang tampok na Dan ay naghahanap dito?

1507
01:12:35,910 --> 01:12:38,110
Ano ang isang listahan ng mga link
tila daan sa amin upang gawin,

1508
01:12:38,110 --> 01:12:40,240
na kung saan ay ang pinagmulan ng
ito partikular na kuwento?

1509
01:12:40,240 --> 01:12:43,250

1510
01:12:43,250 --> 01:12:43,830
>> Mismong.

1511
01:12:43,830 --> 01:12:46,220
Ang isang dynamic na laki dito.

1512
01:12:46,220 --> 01:12:48,040
Maaari naming idagdag sa listahang ito.

1513
01:12:48,040 --> 01:12:51,430
Maaari naming kahit na pag-urong ang listahan, kaya
na lamang ang aming ginagamit ng mas maraming memory

1514
01:12:51,430 --> 01:12:55,560
bilang namin talagang gusto at kaya
kami ay hindi kailanman over-allocating.

1515
01:12:55,560 --> 01:12:58,470
>> Ngayon lang na talagang lisa-picky,
mayroong isang nakatagong gastos.

1516
01:12:58,470 --> 01:13:01,980
Kaya hindi lamang mo dapat hayaan mo akong kumbinsihin
mo na ito ay isang nakahihimok tradeoff.

1517
01:13:01,980 --> 01:13:04,190
May isa pang nakatagong gastos dito.

1518
01:13:04,190 --> 01:13:06,550
Ang benepisyo, upang maging malinaw,
ay na makuha namin dynamism.

1519
01:13:06,550 --> 01:13:10,359
Kung gusto kong isa pang elemento, maaari ko na lang
gumuhit ito at maglagay ng numero sa doon.

1520
01:13:10,359 --> 01:13:12,150
At pagkatapos ay maaari kong i-link ito
na may larawan dito,

1521
01:13:12,150 --> 01:13:14,970
samantalang sa paglipas dito, muli, kung na hindi ko na
ipininta ang aking sarili sa isang sulok,

1522
01:13:14,970 --> 01:13:19,410
kung may ibang tao ay gumagamit na
ang memory dito, ako sa labas ng kapalaran.

1523
01:13:19,410 --> 01:13:21,700
ipininta ko na ang aking sarili sa sulok.

1524
01:13:21,700 --> 01:13:24,390
>> Ngunit kung ano ang mga nakatagong
gastos sa larawang ito?

1525
01:13:24,390 --> 01:13:27,690
Ito ay hindi lamang ang dami
ng oras na ito ay tumatagal

1526
01:13:27,690 --> 01:13:29,870
upang pumunta mula dito sa dito,
na kung saan ay pitong mga hakbang, at pagkatapos ay

1527
01:13:29,870 --> 01:13:32,820
walong baytang, na kung saan ay higit pa sa isa.

1528
01:13:32,820 --> 01:13:34,830
Ano ang isa pang nakatagong gastos?

1529
01:13:34,830 --> 01:13:35,440
Hindi lamang oras.

1530
01:13:35,440 --> 01:13:44,790

1531
01:13:44,790 --> 01:13:49,940
Ang karagdagang impormasyon ay
kinakailangan upang makamit ang larawang ito.

1532
01:13:49,940 --> 01:13:53,210
>> Oo, na mapa, ang mga maliit na mga scrap ng
papel, pati na panatilihin ko naglalarawan sa mga ito bilang.

1533
01:13:53,210 --> 01:13:55,650
Ang mga arrows-- mga ito ay hindi libre.

1534
01:13:55,650 --> 01:13:57,660
A computer-- alam mo
kung ano ang isang computer ay may.

1535
01:13:57,660 --> 01:13:58,790
Ito ay may zero at mga.

1536
01:13:58,790 --> 01:14:03,170
Kung nais mong kumakatawan sa isang arrow o isang
mapa o isang numero, kailangan mo ng ilang memory.

1537
01:14:03,170 --> 01:14:05,950
Kaya't ang isang presyo na iyong
bayaran para sa isang naka-link na listahan,

1538
01:14:05,950 --> 01:14:09,070
isang pangkaraniwang computer science
mapagkukunan, ay din space.

1539
01:14:09,070 --> 01:14:11,710
>> At sa katunayan kaya, kaya karaniwang,
kabilang sa mga tradeoffs

1540
01:14:11,710 --> 01:14:15,580
sa pagdisenyo ng software engineering
systems kapanahunan at space--

1541
01:14:15,580 --> 01:14:18,596
ay dalawang sa iyong mga sangkap, dalawang
ng iyong pinaka-mahal na mga sangkap.

1542
01:14:18,596 --> 01:14:21,220
Na ito ay gastos sa akin mas maraming oras
dahil kailangan kong sundin ang mapa,

1543
01:14:21,220 --> 01:14:25,730
kundi pati na rin ito ay costing sa akin ng dagdag na espasyo
dahil mayroon akong upang panatilihin ang mapa na ito sa paligid.

1544
01:14:25,730 --> 01:14:28,730
Kaya ang pag-asa, bilang na namin uri ng
tinalakay sa paglipas ng kahapon at ngayon,

1545
01:14:28,730 --> 01:14:31,720
ay na ang mga benepisyo
ay lumamang ang gastos.

1546
01:14:31,720 --> 01:14:33,870
>> Ngunit walang malinaw na solusyon dito.

1547
01:14:33,870 --> 01:14:35,870
Siguro ito ay better--
a la mabilis at marumi,

1548
01:14:35,870 --> 01:14:38,660
bilang Kareem ipinanukalang earlier--
upang ihagis memory sa problema.

1549
01:14:38,660 --> 01:14:42,520
Lamang bumili ng mas maraming memory, sa tingin mas mababa
mahirap tungkol sa paglutas ng mga problema,

1550
01:14:42,520 --> 01:14:44,595
at malutas ito sa isang mas madaling paraan.

1551
01:14:44,595 --> 01:14:46,720
At sa katunayan mas maaga, kapag
usapan natin ang tungkol tradeoffs,

1552
01:14:46,720 --> 01:14:49,190
ito ay hindi na espasyo sa
ang computer at oras.

1553
01:14:49,190 --> 01:14:51,810
Ito ay nag-develop oras, na
ay isa pang mapagkukunan.

1554
01:14:51,810 --> 01:14:54,829
>> Kaya muli, ito ay ito balancing act
sinusubukan upang magpasya kung alin sa mga bagay na iyon

1555
01:14:54,829 --> 01:14:55,870
ikaw ay handa na gastusin?

1556
01:14:55,870 --> 01:14:57,380
Alin ang hindi bababa sa mahal?

1557
01:14:57,380 --> 01:15:01,040
Kung saan ay magbubunga ng mas mahusay na mga resulta?

1558
01:15:01,040 --> 01:15:01,540
Yeah?

1559
01:15:01,540 --> 01:15:11,310

1560
01:15:11,310 --> 01:15:12,580
>> Sa katunayan.

1561
01:15:12,580 --> 01:15:15,970
Sa kasong ito, kung ikaw ay
na kumakatawan sa mga numero sa maps--

1562
01:15:15,970 --> 01:15:18,820
ito ay tinatawag na sa maraming wika
"Payo" o "address" -

1563
01:15:18,820 --> 01:15:20,390
ito ay double ang space.

1564
01:15:20,390 --> 01:15:24,390
Iyon ay hindi kailangang maging kasing masamang bilang double kung
ngayon lang kami sa pag-iimbak ng mga numero.

1565
01:15:24,390 --> 01:15:27,410
Ipagpalagay na kami ay pag-iimbak
pasyente talaan sa isang hospital--

1566
01:15:27,410 --> 01:15:30,870
kaya pangalan ni Pierson, numero ng telepono,
numero ng social security, doktor

1567
01:15:30,870 --> 01:15:31,540
kasaysayan.

1568
01:15:31,540 --> 01:15:34,160
Ang kahon na ito ay maaaring maging magkano,
magkano ang mas malaki, at sa sitwasyong

1569
01:15:34,160 --> 01:15:38,000
isang maliit na maliit maliit na pointer, ang address ng
sa susunod element-- ito ay hindi isang malaking pakikitungo.

1570
01:15:38,000 --> 01:15:40,620
Ito ay tulad ng isang palawit
gastos na ito ay hindi mahalaga.

1571
01:15:40,620 --> 01:15:43,210
Ngunit sa kasong ito, yeah, ito ay isang pagdodoble.

1572
01:15:43,210 --> 01:15:45,290
Magandang tanong.

1573
01:15:45,290 --> 01:15:47,900
>> Natin makipag-usap tungkol sa oras ng isang Hayaan
kaunti pa concretely.

1574
01:15:47,900 --> 01:15:50,380
Ano ang pagtakbo ng oras
ng paghahanap listahang ito?

1575
01:15:50,380 --> 01:15:53,640
Ipagpalagay Nais kong maghanap
sa pamamagitan ng lahat ng mga marka ng mga estudyante,

1576
01:15:53,640 --> 01:15:55,980
at mayroong n marka
sa ganitong istraktura ng data.

1577
01:15:55,980 --> 01:15:58,830
Dito, masyadong, maaari naming humiram
ang bokabularyo ng mas maaga.

1578
01:15:58,830 --> 01:16:00,890
Ito ay isang linear istraktura ng data.

1579
01:16:00,890 --> 01:16:04,570
>> Big O ng n ay kung ano ang kinakailangan upang makakuha ng
sa dulo ng ito istraktura ng data,

1580
01:16:04,570 --> 01:16:08,410
whereas-- at hindi pa namin nakikita
ito before-- isang array ay nagbibigay sa iyo

1581
01:16:08,410 --> 01:16:13,555
ano ang tinatawag na pare-pareho ang oras, na nangangahulugan
isang hakbang o dalawang hakbang o 10 steps--

1582
01:16:13,555 --> 01:16:14,180
ay hindi mahalaga.

1583
01:16:14,180 --> 01:16:15,440
Ito ay isang nakapirming numero.

1584
01:16:15,440 --> 01:16:17,440
Ito ay may kinalaman sa
ang laki ng array.

1585
01:16:17,440 --> 01:16:20,130
At ang dahilan para sa na,
muli, ay random access.

1586
01:16:20,130 --> 01:16:23,180
Ang computer na maaari lamang kaagad
tumalon sa isa pang lokasyon,

1587
01:16:23,180 --> 01:16:27,770
dahil ang mga ito ang lahat ng mga parehong
distansya mula sa lahat ng bagay sino pa ang paririto.

1588
01:16:27,770 --> 01:16:29,112
Walang pag-iisip na kasangkot.

1589
01:16:29,112 --> 01:16:31,900

1590
01:16:31,900 --> 01:16:32,400
Lahat tama.

1591
01:16:32,400 --> 01:16:39,230
Kaya kung maaari ko, hayaan mo akong subukan na
pintura ng dalawang huling larawan.

1592
01:16:39,230 --> 01:16:42,830
Isang napaka-karaniwang isa na kilala bilang isang hash table.

1593
01:16:42,830 --> 01:16:51,120
Kaya upang ganyakin ang talakayang ito,
hayaan mo akong mag-isip tungkol sa kung paano gawin ito.

1594
01:16:51,120 --> 01:16:52,610
>> Kaya kung paano tungkol dito?

1595
01:16:52,610 --> 01:16:55,160
Ipagpalagay na ang problema
gusto naming malutas ngayon

1596
01:16:55,160 --> 01:16:58,360
ay pagpapatupad sa isang dictionary--
kaya ng isang buong grupo ng mga salitang Ingles

1597
01:16:58,360 --> 01:16:59,330
o ano pa man.

1598
01:16:59,330 --> 01:17:02,724
At ang layunin ay upang ma-sagot
tanong ng form na ito ay isang salita?

1599
01:17:02,724 --> 01:17:04,640
Kaya nais mong ipatupad
isang spell checker, lamang

1600
01:17:04,640 --> 01:17:07,220
tulad ng isang pisikal na diksyunaryo
na maaari mong tingnan ang mga bagay sa.

1601
01:17:07,220 --> 01:17:10,490
Ipagpalagay ako ay upang gawin ito sa isang array.

1602
01:17:10,490 --> 01:17:12,590
kaya kong gawin ito.

1603
01:17:12,590 --> 01:17:20,756
>> At ipagpalagay na ang mga salita ay apple
at saging at milong bilog.

1604
01:17:20,756 --> 01:17:23,330

1605
01:17:23,330 --> 01:17:26,465
At hindi ako makapag-isip ng mga prutas
na nagsisimula sa d, kaya kami lamang

1606
01:17:26,465 --> 01:17:27,590
pagpunta sa may tatlong prutas.

1607
01:17:27,590 --> 01:17:31,510
Kaya ito ay isang array, at kami ay
pagtatago ng lahat ng mga salitang ito

1608
01:17:31,510 --> 01:17:34,200
sa ganitong diksyunaryo bilang isang array.

1609
01:17:34,200 --> 01:17:39,350
Ang tanong, at pagkatapos, ay kung paano pa
maaari mong itabi ang impormasyon na ito?

1610
01:17:39,350 --> 01:17:43,160
>> Well, ako uri ng cheating dito, dahil
bawat isa sa mga titik sa salita

1611
01:17:43,160 --> 01:17:44,490
ay talagang isang indibidwal byte.

1612
01:17:44,490 --> 01:17:46,740
Kaya kung ako talagang nais na maging
lisa-picky, ko dapat talagang

1613
01:17:46,740 --> 01:17:49,600
ay naghahati ito up sa marami
mas maliit na chunks ng memorya,

1614
01:17:49,600 --> 01:17:51,289
at maaari naming gawin eksakto na.

1615
01:17:51,289 --> 01:17:53,580
Ngunit kami ay pagpunta sa tumakbo sa
ang parehong problema tulad ng dati.

1616
01:17:53,580 --> 01:17:56,674
Paano kung, bilang Merriam Webster o Oxford
ang bawat year-- sila magdagdag ng mga salita

1617
01:17:56,674 --> 01:17:59,340
sa dictionary-- hindi kami
kinakailangang gusto upang ipinta ang ating sarili

1618
01:17:59,340 --> 01:18:00,780
sa isang sulok na may isang array?

1619
01:18:00,780 --> 01:18:05,710
>> Kaya sa halip, marahil ng isang mas matalinong diskarte
ay upang ilagay apple sa sarili nitong node o kahon,

1620
01:18:05,710 --> 01:18:11,190
tulad ng gagawin namin sabihin, saging, at
pagkatapos dito mayroon kaming milong bilog.

1621
01:18:11,190 --> 01:18:14,990

1622
01:18:14,990 --> 01:18:16,790
At kami string ng mga bagay na sama-sama.

1623
01:18:16,790 --> 01:18:19,980
Kaya ito ay ang array, at
ito ay naka-link na listahan.

1624
01:18:19,980 --> 01:18:23,300
Kung hindi mo pa masyadong maaaring makita, ito lamang
nagsasabing "array," at ito says "listahan."

1625
01:18:23,300 --> 01:18:25,780
>> Kaya kami ay may parehong
eksaktong mga isyu tulad ng dati,

1626
01:18:25,780 --> 01:18:28,600
kung saan mayroon kami ngayon
dynamism sa aming naka-link na listahan.

1627
01:18:28,600 --> 01:18:31,090
Ngunit kami ay may isang medyo mabagal na diksiyunaryo.

1628
01:18:31,090 --> 01:18:32,870
Ipagpalagay na nais ko upang tumingin up ng isang salita.

1629
01:18:32,870 --> 01:18:35,430
Maaaring dalhin ako malaking O ng n
hakbang, dahil ang salita baka

1630
01:18:35,430 --> 01:18:37,840
maging lahat ng mga paraan sa dulo ng
sa listahan, tulad ng milong bilog.

1631
01:18:37,840 --> 01:18:40,600
At ito ay lumiliko out na
sa programming, pag-uuri

1632
01:18:40,600 --> 01:18:42,700
ng mga banal na Kopita ng data
istruktura, ay isang bagay

1633
01:18:42,700 --> 01:18:46,620
na nagbibigay sa iyo ng pare-pareho
oras tulad ng isang array

1634
01:18:46,620 --> 01:18:50,870
ngunit na pa rin ay nagbibigay sa iyo dynamism.

1635
01:18:50,870 --> 01:18:52,940
>> Upang maaari naming magkaroon ng pinakamahusay na ng parehong mundo?

1636
01:18:52,940 --> 01:18:55,570
At sa katunayan, mayroong isang bagay
na tinatawag na ang hash table

1637
01:18:55,570 --> 01:18:59,320
na nagpapahintulot sa iyo na gawin eksakto
na, albeit humigit-kumulang.

1638
01:18:59,320 --> 01:19:03,140
A hash talahanayan ay isang may interes
istraktura ng data na namin

1639
01:19:03,140 --> 01:19:06,340
makapag-isip ng bilang ang
kumbinasyon ng isang array

1640
01:19:06,340 --> 01:19:12,390
at pupuntahan ko upang gumuhit ito
tulad this-- at mga listahan ng link

1641
01:19:12,390 --> 01:19:17,310
na kukunin ko gumuhit tulad na ito sa paglipas dito.

1642
01:19:17,310 --> 01:19:19,760
>> At ang paraan ng bagay na ito
mga gawa ay tulad ng sumusunod.

1643
01:19:19,760 --> 01:19:23,310

1644
01:19:23,310 --> 01:19:29,540
Kung ito now-- hash table--
ang aking ikatlong istraktura ng data,

1645
01:19:29,540 --> 01:19:32,590
at gusto kong mag-imbak
mga salita sa ito, ako hindi

1646
01:19:32,590 --> 01:19:35,440
nais na lamang-imbak ang lahat ng
mga salita pabalik upang i-back upang i-back upang i-back.

1647
01:19:35,440 --> 01:19:37,430
Gusto kong masulit ang ilang
piraso ng impormasyon

1648
01:19:37,430 --> 01:19:40,330
tungkol sa mga salita na hahayaan
ako kumuha ito kung saan ito ay mas mabilis.

1649
01:19:40,330 --> 01:19:43,666
>> Kaya ibinigay ang mga salita apple
at saging at milong bilog,

1650
01:19:43,666 --> 01:19:45,040
Kusa ko pinili ang mga salitang iyon.

1651
01:19:45,040 --> 01:19:45,340
Bakit?

1652
01:19:45,340 --> 01:19:47,631
Ano ang uri ng panimula
iba't ibang tungkol sa tatlo?

1653
01:19:47,631 --> 01:19:49,950

1654
01:19:49,950 --> 01:19:51,484
Ano ang halata?

1655
01:19:51,484 --> 01:19:52,900
Simulan nila na may iba't ibang mga titik.

1656
01:19:52,900 --> 01:19:53,900
>> Kaya alam mo kung ano?

1657
01:19:53,900 --> 01:19:57,120
Sa halip na ilagay ang lahat ng aking mga salita sa
ang parehong bucket, kaya na magsalita,

1658
01:19:57,120 --> 01:20:00,390
tulad sa isang malaking listahan, bakit hindi
Ko ng hindi bababa subukan ang isang optimization

1659
01:20:00,390 --> 01:20:04,180
at gumawa ng aking listahan 1/26 bilang mahaba.

1660
01:20:04,180 --> 01:20:07,440
A nakapanghihimok optimization
maaaring bakit hindi

1661
01:20:07,440 --> 01:20:10,650
I-- kapag nagpapasok ng isang salita
sa ito istraktura ng data,

1662
01:20:10,650 --> 01:20:14,300
sa memorya ng computer, kung bakit
hindi ko ilagay ang lahat ng 'a' mga salita dito,

1663
01:20:14,300 --> 01:20:17,270
lahat ng 'b' mga salita dito,
at ang lahat ng 'c' salita dito?

1664
01:20:17,270 --> 01:20:24,610
Kaya ito ay nagtatapos up ng paglagay ng isang mansanas
dito, saging dito, milong bilog dito,

1665
01:20:24,610 --> 01:20:25,730
at iba pa.

1666
01:20:25,730 --> 01:20:31,700
>> At kung ako ay may isang karagdagang
salita like-- kung ano ang iba?

1667
01:20:31,700 --> 01:20:36,640
Mansanas, saging, peras.

1668
01:20:36,640 --> 01:20:39,370
Kahit sino sa tingin ng isang prutas
na nagsisimula sa a, b, oc?

1669
01:20:39,370 --> 01:20:40,570
Blueberry-- perpekto.

1670
01:20:40,570 --> 01:20:43,990
Iyon ay pagpunta sa end up dito.

1671
01:20:43,990 --> 01:20:47,530
At kaya tila namin na magkaroon ng isang
marginally mas mahusay na solusyon,

1672
01:20:47,530 --> 01:20:50,820
dahil ngayon kung gusto kong
upang maghanap para sa apple, ako

1673
01:20:50,820 --> 01:20:53,200
first-- ginagawa ko'y hindi lamang dive
sa aking data istraktura.

1674
01:20:53,200 --> 01:20:54,850
Hindi ko sumisid sa memorya ng aking computer.

1675
01:20:54,850 --> 01:20:56,530
Ako unang tumingin sa ang unang titik.

1676
01:20:56,530 --> 01:20:58,610
>> At ito ay kung ano ang isang computer
siyentipiko nais sabihin.

1677
01:20:58,610 --> 01:21:00,760
hash ka sa iyong data istraktura.

1678
01:21:00,760 --> 01:21:04,100
Dalhin mo ang iyong input, na sa
kasong ito ay isang salita tulad ng mansanas.

1679
01:21:04,100 --> 01:21:07,150
pag-aralan mo ito, ang pagtingin sa
ang unang titik sa kasong ito,

1680
01:21:07,150 --> 01:21:08,340
at dahil doon hashing ito.

1681
01:21:08,340 --> 01:21:10,950
Hashing ay isang pangkalahatang kataga kung saan
magdadala sa iyo ng isang bagay bilang input

1682
01:21:10,950 --> 01:21:12,116
at makagawa ka ng ilang mga output.

1683
01:21:12,116 --> 01:21:15,090
At ang output sa na
kaso ay ang lokasyon

1684
01:21:15,090 --> 01:21:18,150
na nais mong hanapin, ang unang
lokasyon, pangalawang lokasyon, third.

1685
01:21:18,150 --> 01:21:22,160
Kaya ang input ay mansanas,
ang output ay unang.

1686
01:21:22,160 --> 01:21:25,054
input ay banana, ang
output ay dapat na segundo.

1687
01:21:25,054 --> 01:21:27,220
input ay milong bilog,
ang output ay dapat na third.

1688
01:21:27,220 --> 01:21:30,320
input ay blueberry, ang
output ay dapat muli maging second.

1689
01:21:30,320 --> 01:21:34,010
At iyon ang kung ano ang tumutulong magdadala sa iyo
shortcut sa pamamagitan ng iyong memory

1690
01:21:34,010 --> 01:21:39,050
upang makakuha ng sa mga salita
o data ng mas epektibo.

1691
01:21:39,050 --> 01:21:43,330
>> Ngayon na ito cuts down ating panahon potensyal
pamamagitan ng mas maraming gaya ng mula sa 26,

1692
01:21:43,330 --> 01:21:45,850
dahil kung akala mo na ikaw
magkaroon ng maraming "a" salitang gaya ng "z"

1693
01:21:45,850 --> 01:21:48,080
salitang gaya ng "q" mga salita, na
ay hindi tunay realistic--

1694
01:21:48,080 --> 01:21:50,830
ikaw ay pagpunta sa magkaroon ng hilig sa kabuuan
tiyak na mga titik ng alphabet--

1695
01:21:50,830 --> 01:21:53,204
ngunit ito ay magiging isang incremental
diskarte na ay magbibigay-daan sa

1696
01:21:53,204 --> 01:21:55,930
mo upang makakuha ng mga salita mas mabilis.

1697
01:21:55,930 --> 01:21:59,660
At sa katotohanan, isang sopistikadong
programa, ang Googles ng mundo,

1698
01:21:59,660 --> 01:22:02,180
ang Facebooks ng world--
ang mga ito ay gumamit ng isang hash table

1699
01:22:02,180 --> 01:22:03,740
para sa isang pulutong ng mga iba't ibang mga layunin.

1700
01:22:03,740 --> 01:22:06,590
Ngunit hindi sila ay kaya walang muwang bilang
upang lamang tumingin sa ang unang titik

1701
01:22:06,590 --> 01:22:09,700
sa mansanas o saging o
peras o milong bilog,

1702
01:22:09,700 --> 01:22:13,420
dahil tulad ng makikita mo ang mga
mga listahan ay maaari pa ring makakuha ng mahaba.

1703
01:22:13,420 --> 01:22:17,130
>> At kaya ito ay maaaring pa rin uri
ng linear-- kaya uri ng mabagal,

1704
01:22:17,130 --> 01:22:19,980
tulad ng sa malaking O ng n
na namin tinalakay nang mas maaga.

1705
01:22:19,980 --> 01:22:25,290
Kaya kung ano ay isang tunay na magandang hash table
do-- magkakaroon ito ng isang magkano ang mas malaking array.

1706
01:22:25,290 --> 01:22:28,574
At ito ay gamitin ng isang mas
sopistikadong hashing function,

1707
01:22:28,574 --> 01:22:30,240
upang ito ay hindi lang basta tingnan ang "a."

1708
01:22:30,240 --> 01:22:35,480
Siguro ito ay tumitingin sa "a-p-p-l-e" at
kahit papaano nagpalit ang limang titik

1709
01:22:35,480 --> 01:22:38,400
sa ang lokasyon kung saan
apple ay dapat na naka-imbak.

1710
01:22:38,400 --> 01:22:42,660
Kami ay lamang naively gamit ang titik 'a'
mag-isa, dahil sa ito ay maganda at simple.

1711
01:22:42,660 --> 01:22:44,600
>> Ngunit ang isang hash table, sa
Sa katapusan, maaari mong isipin

1712
01:22:44,600 --> 01:22:47,270
ng bilang isang kumbinasyon ng
isang array, ang bawat isa

1713
01:22:47,270 --> 01:22:51,700
ay may isang listahan ng mga link na may perpektong
dapat na bilang maikling hangga't maaari.

1714
01:22:51,700 --> 01:22:54,364
At ito ay hindi isang malinaw na solusyon.

1715
01:22:54,364 --> 01:22:57,280
Sa katunayan, marami ng fine tuning
na napupunta sa ilalim ng hood kapag

1716
01:22:57,280 --> 01:22:59,654
pagpapatupad ng mga uri ng mga
sopistikadong istruktura ng data

1717
01:22:59,654 --> 01:23:01,640
ay kung ano ay ang tamang
haba ng array?

1718
01:23:01,640 --> 01:23:03,250
Ano ang tamang hash?

1719
01:23:03,250 --> 01:23:04,830
Paano mag-imbak ka ng mga bagay sa memory?

1720
01:23:04,830 --> 01:23:07,249
>> Ngunit mapagtanto kung gaano kabilis
ang ganitong uri ng talakayan

1721
01:23:07,249 --> 01:23:10,540
tumataas, alinman sa ngayon na ito ay uri
ng higit sa isa ng ulo sa puntong ito, na kung saan

1722
01:23:10,540 --> 01:23:11,360
ay ayos.

1723
01:23:11,360 --> 01:23:18,820
Ngunit kami nagsimula, isipin ang, na may tunay na
isang bagay na mababa ang antas at electronic.

1724
01:23:18,820 --> 01:23:20,819
At kaya ito ay muling sinabi ay ito
tema ng abstraction,

1725
01:23:20,819 --> 01:23:23,610
kung saan sa sandaling simulan mo na kumuha para sa
ipinagkaloob, OK, Mayroon akong it-- mayroong

1726
01:23:23,610 --> 01:23:26,680
pisikal na memory, OK, nakuha ko, sa bawat
pisikal na lokasyon ay may isang address,

1727
01:23:26,680 --> 01:23:29,910
OK, nakuha ko ito, maaari ba akong kumakatawan
mga address bilang arrows--

1728
01:23:29,910 --> 01:23:34,650
maaari mong masyadong mabilis simulan upang magkaroon
mas sopistikadong pag-uusap na

1729
01:23:34,650 --> 01:23:38,360
sa dulo mukhang na nagpapahintulot sa amin
upang malutas ang problema tulad ng paghahanap

1730
01:23:38,360 --> 01:23:41,620
at pag-uuri ng mas epektibo.

1731
01:23:41,620 --> 01:23:44,190
At magpahinga sigurado, too--
dahil sa tingin ko ito

1732
01:23:44,190 --> 01:23:48,700
ay ang pinakamalalim na kami ay wala na sa ilang
sa mga CS paksa proper-- na namin

1733
01:23:48,700 --> 01:23:51,880
tapos na sa isang araw at isang kalahati sa ito
ituro kung ano ang iyong karaniwang gawin sa paglipas ng

1734
01:23:51,880 --> 01:23:55,520
kurso ng walong linggo sa isang semestre.

1735
01:23:55,520 --> 01:23:59,670
>> Ang anumang mga katanungan sa mga ito?

1736
01:23:59,670 --> 01:24:01,100
Hindi?

1737
01:24:01,100 --> 01:24:01,940
Lahat tama.

1738
01:24:01,940 --> 01:24:05,610
Well, bakit hindi namin i-pause doon,
simulan tanghalian ng ilang minuto maaga,

1739
01:24:05,610 --> 01:24:07,052
ipagpatuloy sa loob lamang tungkol sa isang oras?

1740
01:24:07,052 --> 01:24:08,760
At kukunin ko na magtagal para
ng kaunti sa mga tanong.

1741
01:24:08,760 --> 01:24:11,343
Pagkatapos ay ako pagpunta sa may sa pumunta
tumagal ng ilang mga tawag kung iyon lamang ang OK.

1742
01:24:11,343 --> 01:24:15,000
Kukunin ko i-on ang ilang musika sa habang panahon,
ngunit lunch dapat na sa paligid ng sulok.

1743
01:24:15,000 --> 01:24:17,862