1
00:00:02,840 --> 00:00:03,840
<b>Kodirao <i><Dr.B></i></b>

2
00:00:04,040 --> 00:00:07,840
A da mi to ne primijetimo, moderni život je zauzet.

3
00:00:10,080 --> 00:00:14,480
Dok tražimo ljubav, kupujte online,

4
00:00:14,480 --> 00:00:18,000
putovati svijetom,

5
00:00:18,000 --> 00:00:20,320
čak i dok spašavamo živote,

6
00:00:20,320 --> 00:00:25,160
postoje uputstva korak po korak koja tiho rade iza scene.

7
00:00:27,080 --> 00:00:30,440
Sve više i više oni upravljaju našim životima.

8
00:00:30,440 --> 00:00:33,040
Zovu se algoritmi.

9
00:00:34,400 --> 00:00:36,640
Algoritmi su svuda.

10
00:00:36,640 --> 00:00:39,680
Ovi mali komadi matematike postali su centralni

11
00:00:39,680 --> 00:00:41,520
na naš svakodnevni život.

12
00:00:41,520 --> 00:00:44,800
Ali pošto su nevidljivi, skloni smo da ih uzimamo zdravo za gotovo,

13
00:00:44,800 --> 00:00:46,320
čak ih pogrešno razumeti.

14
00:00:50,960 --> 00:00:52,080
SMIJEH

15
00:00:53,200 --> 00:00:57,040
Oni su tajna našeg digitalnog svijeta i još mnogo toga.

16
00:00:58,720 --> 00:01:02,120
'U ovom programu ću vam pokazati neke od mojih omiljenih

17
00:01:02,120 --> 00:01:05,880
'algoritmi koji otkrivaju odakle dolaze...'

18
00:01:05,880 --> 00:01:08,480
Algoritmi su stari.

19
00:01:08,480 --> 00:01:09,800
'..kako rade...'

20
00:01:09,800 --> 00:01:11,920
Izazov je pronaći najkraći put...

21
00:01:11,920 --> 00:01:14,640
Ovo su grube upute koje biste koristili.

22
00:01:14,640 --> 00:01:17,800
..za povratak na svoju početnu tačku.

23
00:01:17,800 --> 00:01:20,240
'..šta bi mogli učiniti u budućnosti.'

24
00:01:20,240 --> 00:01:23,440
- Algoritam je vrsta samog pisanja? Ili...?
- Apsolutno.

25
00:01:23,440 --> 00:01:26,080
'..i kako ne možemo živjeti bez njih.'

26
00:01:26,080 --> 00:01:29,600
Čak i kada pečemo tortu, slijedimo algoritam.

27
00:01:29,600 --> 00:01:32,520
Kao matematičar, volim algoritme.

28
00:01:32,520 --> 00:01:35,120
Ne samo da su impresivni u rješavanju problema,

29
00:01:35,120 --> 00:01:38,800
ali i neobično lijepa, dodirujući matematiku

30
00:01:38,800 --> 00:01:42,200
poredak koji podupire funkcioniranje svemira.

31
00:01:42,200 --> 00:01:45,760
Dobrodošli u čudan i divan svijet algoritama.

32
00:01:54,600 --> 00:01:57,680
Većina nas nosi jednu od ovih.

33
00:01:57,680 --> 00:02:00,160
Možda ste to primijetili kada snimite fotografiju

34
00:02:00,160 --> 00:02:05,800
sa vašim telefonom, onda crta okvir oko bilo kojeg lica, ovako.

35
00:02:05,800 --> 00:02:09,480
Ovo je rezultat posebnog algoritma za detekciju lica

36
00:02:09,480 --> 00:02:13,200
i pomaže da lice na fotografiji ostane u fokusu.

37
00:02:14,480 --> 00:02:18,280
'Kao i svi algoritmi, i ovaj rješava problem.

38
00:02:18,280 --> 00:02:21,520
'U ovom slučaju, pronalaženje ljudskog lica.

39
00:02:21,520 --> 00:02:24,760
'Dok ga ne zavara lice od voća,

40
00:02:24,760 --> 00:02:28,400
'Ona otkriva ljudsko lice na fotografiji.

41
00:02:28,400 --> 00:02:31,200
'Pa, kako to radi?

42
00:02:31,200 --> 00:02:34,120
'U svojoj osnovi, algoritmi su nešto više od toga

43
00:02:34,120 --> 00:02:37,280
'serija uputstava korak po korak.

44
00:02:37,280 --> 00:02:40,520
'Ovaj radi metodičnim skeniranjem slike

45
00:02:40,520 --> 00:02:43,520
'tražeći četiri određena apstraktna uzorka

46
00:02:43,520 --> 00:02:45,960
'povezano sa licem.

47
00:02:45,960 --> 00:02:48,280
'Kada se ovi otkriju jedno za drugim,

48
00:02:48,280 --> 00:02:52,520
'tada algoritam pokazuje da je pronađeno ljudsko lice.'

49
00:02:52,520 --> 00:02:56,880
Proces dodiruje osnovni obrazac iza svih lica,

50
00:02:56,880 --> 00:02:59,520
bez obzira na oblik ili veličinu.

51
00:02:59,520 --> 00:03:02,840
Krajnji rezultat je samo jedan primjer kako algoritmi imaju

52
00:03:02,840 --> 00:03:05,560
olakšala nam živote.

53
00:03:05,560 --> 00:03:09,000
- Uradiću to!
- Uradiću to!
- Ja sam prvi bio ovde!
- OK.

54
00:03:09,000 --> 00:03:10,600
Dakle, idite.

55
00:03:10,600 --> 00:03:14,240
„Skloni smo povezivanju algoritama sa računarima, pametnim telefonima

56
00:03:14,240 --> 00:03:15,480
'i internet.

57
00:03:15,480 --> 00:03:19,320
'Ali oni nisu isključivi u svijetu tehnologije.

58
00:03:19,320 --> 00:03:24,160
'Moj svakodnevni posao je profesor matematike na Univerzitetu Oksford.

59
00:03:24,160 --> 00:03:26,920
'A jedna od stvari u kojima najviše uživam je čuvanje

60
00:03:26,920 --> 00:03:29,120
'studenti na prstima.'

61
00:03:29,120 --> 00:03:31,040
OK, uzeću jednu.

62
00:03:31,040 --> 00:03:33,920
Evo, igramo matematičku igru sa teglom

63
00:03:33,920 --> 00:03:37,120
puna čokolade i jednog ljutog čilija.

64
00:03:38,480 --> 00:03:42,720
'Cilj je da ne ostanete s čilijem na kraju.

65
00:03:42,720 --> 00:03:44,360
'Ali ono što ti studenti ne znaju,

66
00:03:44,360 --> 00:03:49,520
'je da igram uz pomoć algoritma.'

67
00:03:49,520 --> 00:03:51,800
- OK. Spreman? OBA:
- Da.

68
00:03:51,800 --> 00:03:54,560
U redu, ja idem prvi, pa zapamti, možeš uzeti jedan,

69
00:03:54,560 --> 00:03:57,200
dvije ili tri čokolade odjednom.

70
00:03:57,200 --> 00:04:00,880
Nisam pohlepan tip, pa ću samo uzeti jedan. Sada je tvoj red.

71
00:04:00,880 --> 00:04:05,440
'Svaki igrač dolazi na svoj red, između jedne i tri čokolade.'

72
00:04:05,440 --> 00:04:09,120
Uzeo si dva, OK. Dakle, uzeću... Uzeću dva.

73
00:04:09,120 --> 00:04:12,280
'Šta god moj protivnik uradi, moj algoritam mi govori

74
00:04:12,280 --> 00:04:14,200
'kako odgovoriti.'

75
00:04:14,200 --> 00:04:16,520
OK, uzeću dva.

76
00:04:16,520 --> 00:04:19,080
I opet si na redu. SHE LAUGHS

77
00:04:19,080 --> 00:04:20,680
Oh, da.

78
00:04:20,680 --> 00:04:24,040
- Pa ja ću uzeti... tri.
- Tri. I ja ću uzeti jednu.

79
00:04:24,040 --> 00:04:27,160
- And just a chilli left...
- Pa, čekaj. Jesam li to ja?
- Da, jesi

80
00:04:27,160 --> 00:04:29,640
- da jedem čili.
- Oh, ne!
- Pa, izvoli.

81
00:04:29,640 --> 00:04:32,960
'Dozvolite mi da otkrijem kako mi je algoritam koji sam koristio pomogao da pobijedim.'

82
00:04:32,960 --> 00:04:34,520
It's the only way to learn.

83
00:04:35,680 --> 00:04:40,680
Dakle, ključ je razmišljati o grupisanju stvari u četiri.

84
00:04:41,960 --> 00:04:46,720
13 čokolada podijeljeno je u tri grupe po četiri, s jednom preostalo.

85
00:04:46,720 --> 00:04:50,160
Dakle, uzimajući jednu čokoladu u prvom krugu pa četiri

86
00:04:50,160 --> 00:04:54,160
minus sve što drugi igrač uzme u narednim rundama,

87
00:04:54,160 --> 00:04:57,040
ovaj algoritam osigurava da drugi igrač

88
00:04:57,040 --> 00:04:58,960
uvijek ostaje sa čilijem.

89
00:04:58,960 --> 00:05:01,080
Suština zaista dobrog

90
00:05:01,080 --> 00:05:04,240
algoritam, njegova magija, ako želite, je matematika.

91
00:05:04,240 --> 00:05:07,440
Najbolji algoritmi su oni koji dodiruju temelj

92
00:05:07,440 --> 00:05:10,400
matematička struktura koja se krije ispod problema.

93
00:05:11,600 --> 00:05:13,080
OK, vrati čili.

94
00:05:14,480 --> 00:05:17,760
Upoznaću vas sa nekim od algoritama koji postoje

95
00:05:17,760 --> 00:05:20,320
postati srce modernog života.

96
00:05:21,880 --> 00:05:24,920
Ali prvo, želim da vam to pokažem, uz svu njihovu modernost

97
00:05:24,920 --> 00:05:28,360
aplikacije, algoritmi su izuzetno stari.

98
00:05:29,680 --> 00:05:33,600
U stvari, oni su prethodili kompjuterima hiljadama godina.

99
00:05:35,480 --> 00:05:38,280
Osmišljen je najstariji algoritam za koji znamo

100
00:05:38,280 --> 00:05:40,480
za rješavanje matematičkog problema.

101
00:05:40,480 --> 00:05:44,800
Prvi ga je zapisao starogrčki matematičar Euklid.

102
00:05:44,800 --> 00:05:47,520
Euklidov algoritam, kao što je poznato,

103
00:05:47,520 --> 00:05:50,680
je metoda za pronalaženje najvećeg zajedničkog devizora.

104
00:05:52,360 --> 00:05:55,680
Najveći zajednički devizor je najveći broj koji će

105
00:05:55,680 --> 00:06:00,280
podijeliti na par drugih brojeva bez ostavljanja ostatka.

106
00:06:00,280 --> 00:06:03,000
Dakle, u ovom slučaju, četiri se dijeli na osam

107
00:06:03,000 --> 00:06:06,080
i 12 bez ostatka.

108
00:06:06,080 --> 00:06:08,520
Lako je pronaći za male brojeve,

109
00:06:08,520 --> 00:06:10,600
ali mnogo teže za velike.

110
00:06:12,120 --> 00:06:15,480
Dok je Euklid bio najveći matematičar svog vremena,

111
00:06:15,480 --> 00:06:18,640
njegov algoritam mu je mogao doneti bogatstvo kao keramičar.

112
00:06:19,840 --> 00:06:22,280
Dozvolite mi da vam pokažem zašto.

113
00:06:22,280 --> 00:06:25,440
Zamislite da imate pod pravougaonog oblika

114
00:06:25,440 --> 00:06:26,760
i želite da nađete

115
00:06:26,760 --> 00:06:30,360
najefikasniji način da ga obložite kvadratnim pločicama.

116
00:06:30,360 --> 00:06:34,080
Drugim riječima, koja je najveća kvadratna pločica koja će točno biti

117
00:06:34,080 --> 00:06:38,040
podijeliti dimenzije poda bez ičega viška?

118
00:06:38,040 --> 00:06:40,440
Ovo je, zapravo, geometrijska verzija

119
00:06:40,440 --> 00:06:43,080
najvećeg uobičajenog problema uređaja.

120
00:06:43,080 --> 00:06:46,280
Dimenzije poda su dva broja

121
00:06:46,280 --> 00:06:48,640
i veličinu pločica, što ćemo pokušati

122
00:06:48,640 --> 00:06:51,960
i vježbajte, njihov je najveći zajednički planer.

123
00:06:54,040 --> 00:06:57,480
Pratićemo Euklidov algoritam korak po korak da bismo pokazali

124
00:06:57,480 --> 00:07:01,480
kako može pronaći kvadratnu pločicu savršene veličine za ovaj pod.

125
00:07:02,920 --> 00:07:06,800
Prema Euklidovom algoritmu, treba da počnemo da popunjavamo pravougaonik

126
00:07:06,800 --> 00:07:10,960
sa kvadratnim pločicama koje odgovaraju najmanjoj od dvije dimenzije.

127
00:07:13,760 --> 00:07:15,920
Ovo je prva faza posla.

128
00:07:17,160 --> 00:07:19,040
Euklidov algoritam nam tada govori

129
00:07:19,040 --> 00:07:22,400
da ponovo uradite potpuno istu stvar sa ovim pravougaonikom.

130
00:07:24,080 --> 00:07:28,520
U svakoj fazi, algoritam nam govori da odaberemo kvadratne pločice

131
00:07:28,520 --> 00:07:31,600
odgovara najkraćoj strani pravougaonika.

132
00:07:33,600 --> 00:07:38,880
Dakle, ovoga puta naše kvadratne pločice savršeno ispunjavaju preostali prostor.

133
00:07:38,880 --> 00:07:42,960
Sada, moja kvadratna pločica ima dimenzije 15x15.

134
00:07:42,960 --> 00:07:45,720
Tako nam govori Euklidov algoritam

135
00:07:45,720 --> 00:07:50,440
da je najveći zajednički devizor 150 i 345 15.

136
00:07:53,240 --> 00:07:56,160
Ne predlažem da svaki put koristite Euklidov algoritam

137
00:07:56,160 --> 00:07:58,360
morate naručiti pločice,

138
00:07:58,360 --> 00:08:02,480
ali nevjerovatna stvar je ta jednostavna metoda korak po korak

139
00:08:02,480 --> 00:08:06,440
pronalazi savršenu kvadratnu pločicu bez obzira na dimenzije poda.

140
00:08:07,800 --> 00:08:11,640
Euklidov algoritam može izgledati samo kao matematička tehnika,

141
00:08:11,640 --> 00:08:16,400
ali vrlo elegantno ispunjava sve kriterije za algoritam.

142
00:08:16,400 --> 00:08:20,120
To je precizno izrečena uputstva, procedura

143
00:08:20,120 --> 00:08:24,800
uvijek završi, i može se dokazati da radi u svim slučajevima.

144
00:08:28,320 --> 00:08:31,800
Moć algoritama je u tome što ne morate ponovo izmišljati

145
00:08:31,800 --> 00:08:36,480
točak svaki put. Oni su opšta rješenja problema.

146
00:08:36,480 --> 00:08:40,000
Ovo važi za drevne algoritme kao i za moderne.

147
00:08:45,320 --> 00:08:49,480
Godine 1998, u ovoj garaži u Menlo Parku u Kaliforniji,

148
00:08:49,480 --> 00:08:52,440
napravljen je važan deo algoritamske istorije.

149
00:08:54,520 --> 00:08:58,560
Unutra su bila dva doktoranta sa Univerziteta Stamford.

150
00:08:58,560 --> 00:09:00,760
Larry Page i Sergey Brin.

151
00:09:02,320 --> 00:09:05,640
Njihov cilj je bio da osmisle pretraživač koji bi mogao pronaći

152
00:09:05,640 --> 00:09:08,480
stvari efikasno na World Wide Webu.

153
00:09:11,000 --> 00:09:13,880
Iz ovih skromnih početaka nastao je Google.

154
00:09:15,400 --> 00:09:18,760
Ali Google ne bi bio Google da nije bilo tog algoritma

155
00:09:18,760 --> 00:09:21,600
Larry i Sergey su kreirali, pod nazivom PageRank.

156
00:09:30,880 --> 00:09:34,040
PageRank je bio algoritam u srcu prvog

157
00:09:34,040 --> 00:09:37,200
inkarnacija Google pretraživača.

158
00:09:37,200 --> 00:09:42,120
Sada, tehnički, to nije algoritam pretraživanja, već algoritam za rangiranje.

159
00:09:42,120 --> 00:09:45,600
Dakle, kada unesete upit u pretraživač,

160
00:09:45,600 --> 00:09:49,880
tada postoje bukvalno milioni stranica koje će odgovarati tom upitu.

161
00:09:49,880 --> 00:09:53,600
Ono što PageRank radi je da rangira sve te stranice na jednu

162
00:09:53,600 --> 00:09:56,960
na vrhu je onaj za koji ćete više biti zainteresovani.

163
00:09:58,520 --> 00:10:01,440
Larry i Sergey su došli na ideju da urade PageRank

164
00:10:01,440 --> 00:10:05,880
i da ga koristi kao sistem rangiranja za poboljšanje kvaliteta web pretrage.

165
00:10:05,880 --> 00:10:07,800
Sećam se sebe u to vreme,

166
00:10:07,800 --> 00:10:10,720
koristili ste web pretraživač kao što je AltaVista.

167
00:10:10,720 --> 00:10:12,760
Morali biste kliknuti na vezu Sljedeća stranica

168
00:10:12,760 --> 00:10:14,880
mnogo puta da pronađete ono što tražite.

169
00:10:14,880 --> 00:10:17,280
PageRank je bio jedan od razloga zašto je to bio Google

170
00:10:17,280 --> 00:10:20,760
mnogo bolje od postojećih pretraživača u to vrijeme.

171
00:10:21,800 --> 00:10:24,840
Unutrašnji rad PageRank-a je skriven od pogleda

172
00:10:24,840 --> 00:10:26,680
na World Wide Webu.

173
00:10:26,680 --> 00:10:30,360
Da bismo otkrili kako radi svoj posao, koristićemo PageRank

174
00:10:30,360 --> 00:10:33,440
algoritam za rangiranje igrača fudbalskog tima.

175
00:10:34,600 --> 00:10:36,960
PageRank gleda na dvije stvari.

176
00:10:36,960 --> 00:10:42,040
Gleda dolazne veze do web stranice, odnosno ostalih stranica

177
00:10:42,040 --> 00:10:46,360
tu vezu do stranice i gleda koliko su te stranice važne.

178
00:10:51,960 --> 00:10:54,840
U našoj demonstraciji da pokažemo pamet PageRank-a

179
00:10:54,840 --> 00:10:59,280
algoritam, igrači u fudbalskom timu su web stranice

180
00:10:59,280 --> 00:11:02,880
a prolazi između njih su web veze.

181
00:11:02,880 --> 00:11:05,680
Ulaz za algoritam.

182
00:11:05,680 --> 00:11:09,240
Uopšteno govoreći, PageRank algoritam će dati više

183
00:11:09,240 --> 00:11:13,240
rangirati na web stranicu ako ima puno linkova koji dolaze s drugih web stranica.

184
00:11:13,240 --> 00:11:16,000
Dakle, u slučaju fudbala, ako igrač dobije više

185
00:11:16,000 --> 00:11:20,080
pasova od ostatka tima, onda će oni biti više rangirani.

186
00:11:20,080 --> 00:11:21,680
Nije baš tako jednostavno.

187
00:11:21,680 --> 00:11:24,960
Jer PageRank algoritam zapravo daje veću težinu

188
00:11:24,960 --> 00:11:28,880
link sa web stranice koja sama po sebi ima visok rang stranice.

189
00:11:28,880 --> 00:11:32,520
Dakle, u stvari, pas popularnog igrača vrijedi više od toga

190
00:11:32,520 --> 00:11:35,960
dodavanje igrača koji uopšte nije uključen u igru.

191
00:11:37,120 --> 00:11:40,920
Ovo je vizualizacija algoritma na djelu.

192
00:11:40,920 --> 00:11:45,880
Statistika je trenutni rang igrača. Izlaz algoritma.

193
00:11:45,880 --> 00:11:50,280
I svaki put kada postoji prolaz, ove rang liste se ažuriraju.

194
00:11:50,280 --> 00:11:56,360
Kada Google koristi ovaj algoritam, mijenja samo jednu stvar - unos.

195
00:11:56,360 --> 00:11:59,280
Umjesto propusnica, koristi web linkove.

196
00:12:01,280 --> 00:12:04,320
Imajte na umu da važnost stranice zavisi od važnosti

197
00:12:04,320 --> 00:12:06,480
stranica koje vode do njega.

198
00:12:06,480 --> 00:12:09,160
To znači da morate izračunati rang stranice za sve

199
00:12:09,160 --> 00:12:11,240
stranicama u isto vrijeme.

200
00:12:11,240 --> 00:12:14,200
I zapravo morate ponoviti izračunavanje jer svaki put,

201
00:12:14,200 --> 00:12:16,600
ažurirat ćete važnost svih stranica.

202
00:12:16,600 --> 00:12:19,040
A to će zauzvrat uticati

203
00:12:19,040 --> 00:12:22,120
važnost stranica na koje te stranice povezuju.

204
00:12:30,680 --> 00:12:33,840
Na kraju meča posao algoritma je završen.

205
00:12:36,720 --> 00:12:39,880
Ako želimo da tražimo ključnog igrača u timu,

206
00:12:39,880 --> 00:12:41,840
ovo je PageRank odgovor.

207
00:12:43,800 --> 00:12:46,400
Igrač 11 ima najviši PageRank rezultat.

208
00:12:48,320 --> 00:12:50,640
Mislim da je PageRank algoritam vjerovatno

209
00:12:50,640 --> 00:12:52,560
moj omiljeni algoritam svih vremena.

210
00:12:52,560 --> 00:12:54,960
I nevjerovatno je da se može primijeniti ne samo na

211
00:12:54,960 --> 00:12:58,520
World Wide Web, ali i analiziranje fudbalske utakmice.

212
00:12:58,520 --> 00:13:01,320
Ali za mene je to činjenica da ima prelijepog

213
00:13:01,320 --> 00:13:03,880
matematika u svom srcu koja se čini da uvek pronađe

214
00:13:03,880 --> 00:13:05,960
web stranicu koju tražim.

215
00:13:08,120 --> 00:13:09,320
Unutar Google-a, mislim

216
00:13:09,320 --> 00:13:14,320
PageRank se smatra veoma važnim dijelom Googleovog ranog razvoja.

217
00:13:15,520 --> 00:13:18,600
PageRank je bio tajna zašto je pretraživač Larry

218
00:13:18,600 --> 00:13:22,200
a Sergey izgrađen 1990-ih bio je tako uspješan.

219
00:13:23,920 --> 00:13:28,640
Sada Google obrađuje preko 3,5 milijardi pretraživanja svakog dana.

220
00:13:28,640 --> 00:13:31,960
To je najpopularniji pretraživač na svijetu.

221
00:13:31,960 --> 00:13:36,480
A kompanija je vrijedna više od 450 milijardi.

222
00:13:37,560 --> 00:13:40,760
Nije loše za dva doktoranta koji rade u garaži.

223
00:13:49,000 --> 00:13:52,600
Algoritmi su jednostavni recepti korak po korak.

224
00:13:52,600 --> 00:13:56,800
Njihovo izmišljanje zahtijeva nevjerovatnu kreativnost i genijalnost.

225
00:13:56,800 --> 00:14:01,000
Ali njihova upotreba je samo pitanje pridržavanja uputa.

226
00:14:01,000 --> 00:14:04,600
I zato su algoritmi savršeni za računare.

227
00:14:08,240 --> 00:14:10,200
Kompjuteri su samo mašine.

228
00:14:10,200 --> 00:14:14,000
Oni samo rade zadatke koji se ponavljaju fenomenalnom brzinom.

229
00:14:14,000 --> 00:14:15,560
Neverovatne brzine.

230
00:14:15,560 --> 00:14:20,080
Dakle, oni su apsolutno savršeni za obavljanje ovih zadataka koji se ponavljaju

231
00:14:20,080 --> 00:14:23,120
koji su nedvosmisleno definisani

232
00:14:23,120 --> 00:14:27,320
i može se obaviti u ograničenom vremenskom periodu.

233
00:14:29,040 --> 00:14:32,040
Računarski kod u osnovi čini algoritam specifičnim.

234
00:14:32,040 --> 00:14:33,840
Dakle, algoritam je vrsta ideje.

235
00:14:33,840 --> 00:14:35,280
Kako biste riješili problem?

236
00:14:35,280 --> 00:14:37,680
Ovo su grube upute koje biste koristili.

237
00:14:37,680 --> 00:14:40,760
A onda se to može prevesti u određeni kod.

238
00:14:43,920 --> 00:14:47,880
Mnogo vrsta algoritama je kreirano sa računarom na umu.

239
00:14:49,800 --> 00:14:53,360
A neki od najvažnijih su algoritmi za sortiranje.

240
00:14:54,880 --> 00:14:58,880
Sada, posao algoritma za sortiranje je da dovede stvari u red.

241
00:14:58,880 --> 00:15:00,560
I imaju mnogo namjena.

242
00:15:00,560 --> 00:15:03,720
Na primjer, na internetu se dobija informacija

243
00:15:03,720 --> 00:15:08,720
razbijene na pakete podataka koji se zatim šalju preko weba.

244
00:15:08,720 --> 00:15:11,000
Sada, da ponovo sastavimo te podatke,

245
00:15:11,000 --> 00:15:15,120
algoritmi sortiranja su apsolutno ključni za postavljanje ovih podataka

246
00:15:15,120 --> 00:15:18,720
vratimo ispravnim redoslijedom kako bismo mogli vidjeti sliku,

247
00:15:18,720 --> 00:15:21,560
ili pročitajte email koji smo upravo poslali.

248
00:15:26,120 --> 00:15:30,000
Ovo je Korporacija za razvoj sistema u Kaliforniji.

249
00:15:30,000 --> 00:15:35,560
Smatra se prvom svetskom kompanijom za kompjuterski softver.

250
00:15:35,560 --> 00:15:40,680
I tu su 1963. godine dva kompjuterska naučnika prvi put formalno

251
00:15:40,680 --> 00:15:44,360
napisao jedan od najpoznatijih algoritama za sortiranje svih vremena.

252
00:15:48,240 --> 00:15:50,280
To se zove sortiranje mehurića.

253
00:15:50,280 --> 00:15:53,520
A evo i primjera mjehurića na djelu,

254
00:15:53,520 --> 00:15:55,920
sortiranje blokova umjesto brojeva.

255
00:15:57,720 --> 00:16:01,200
Ime je dobio jer sa svakim krugom algoritma,

256
00:16:01,200 --> 00:16:05,240
najveći nesortirani predmet mehurići do vrha.

257
00:16:05,240 --> 00:16:09,000
Kao i svi naši algoritmi do sada, u ludilu postoji metoda.

258
00:16:14,760 --> 00:16:16,640
Da vidite kako ovaj algoritam radi,

259
00:16:16,640 --> 00:16:19,120
koristićemo ga za sortiranje osam objekata.

260
00:16:20,760 --> 00:16:24,720
Sada, algoritam sortiranja mehurića kaže da se objekti razmatraju u parovima

261
00:16:24,720 --> 00:16:27,480
i zamijenite ih ako su u pogrešnom redoslijedu.

262
00:16:27,480 --> 00:16:31,840
Tako da ćemo početi na ovom kraju i napredovati do vrha.

263
00:16:31,840 --> 00:16:35,880
Dakle, smatram da su ova dva, u pogrešnom redosledu, pa ih zamenjujem.

264
00:16:37,560 --> 00:16:40,000
Uzmite u obzir sljedeći par, oni su u pravom redoslijedu,

265
00:16:40,000 --> 00:16:42,280
pa ih ostavljam onakvima kakvi jesu.

266
00:16:42,280 --> 00:16:45,960
Uzmite u obzir ovaj par, oni su u pogrešnom redosledu, pa ih menjam.

267
00:16:48,920 --> 00:16:51,080
I samo nastavljamo sa ovim.

268
00:16:58,160 --> 00:17:01,600
Sada algoritam sortiranja mehurića kaže da se vratimo na početak

269
00:17:01,600 --> 00:17:05,760
i ponavljajte proces iznova i iznova dok objekti ne budu u redu.

270
00:17:19,800 --> 00:17:24,120
Algoritam se zaustavlja kada nema parova za zamjenu.

271
00:17:24,120 --> 00:17:27,880
Dakle, algoritam sortiranja mjehurićima je uspješno obavio svoj posao.

272
00:17:27,880 --> 00:17:30,760
Sada imam savršeno poređane predmete,

273
00:17:30,760 --> 00:17:32,640
according to ascending height.

274
00:17:34,160 --> 00:17:37,640
Bubble sortiranje je elegantno jednostavno i jednostavno.

275
00:17:37,640 --> 00:17:41,880
Ali ako je obim zadatka sortiranja ogroman, recimo, organiziranje ogromnih dijelova

276
00:17:41,880 --> 00:17:45,720
podataka, onda bi mogli postojati bolji algoritmi za sortiranje za posao.

277
00:17:50,800 --> 00:17:52,680
This is John von Neumann,

278
00:17:52,680 --> 00:17:56,560
naučni genije koji je pomogao pionirima modernog kompjutera,

279
00:17:56,560 --> 00:17:58,760
game theory, the atomic bomb

280
00:17:58,760 --> 00:18:02,200
i, kako se ispostavilo, izmislio algoritam za sortiranje.

281
00:18:04,760 --> 00:18:08,080
Osmislio ga je da radi na ovome, jednom od najranijih na svijetu

282
00:18:08,080 --> 00:18:11,880
elektronske kompjutere, čiji je dizajn pomogao.

283
00:18:11,880 --> 00:18:14,800
Algoritam se zove sortiranje spajanjem.

284
00:18:16,800 --> 00:18:21,200
Algoritam sortiranja spajanjem radi na principu zavadi pa vladaj.

285
00:18:21,200 --> 00:18:26,280
I sastoji se iz dva dijela. Prvi bit je dio za podjelu.

286
00:18:28,560 --> 00:18:31,920
Ovo uključuje podjelu svega u manje grupe.

287
00:18:35,240 --> 00:18:38,160
A sada dolazi ono što osvaja.

288
00:18:40,720 --> 00:18:43,640
Grupe su sada ponovo spojene.

289
00:18:43,640 --> 00:18:47,480
Ali dok spajam te dvije grupe, upoređujem veličine objekata

290
00:18:47,480 --> 00:18:51,400
jedan po par tako da se spojena grupa sortira.

291
00:19:00,480 --> 00:19:03,240
Sada, algoritam za sortiranje spajanjem može izgledati prilično slično kao

292
00:19:03,240 --> 00:19:07,240
bubble sort, ali ono što dolazi na svoje je ono sa većim

293
00:19:07,240 --> 00:19:10,280
broj objekata, to je mnogo, mnogo brže.

294
00:19:10,280 --> 00:19:15,520
Pa da vidimo kako se sortiranje spajanjem upoređuje po brzini sa sortiranjem u obliku mehurića.

295
00:19:15,520 --> 00:19:18,040
Vrijeme je za bitku algoritama!

296
00:19:21,880 --> 00:19:26,000
Ovdje imamo sortiranje oblačićima na dnu i sortiranje spajanjem na vrhu.

297
00:19:26,000 --> 00:19:28,760
Imamo ih da sortiraju 1000 objekata.

298
00:19:28,760 --> 00:19:31,840
Sada, iako će oboje dati isti krajnji rezultat,

299
00:19:31,840 --> 00:19:35,280
već možete vidjeti da sortiranje spajanjem dolazi mnogo brže.

300
00:19:35,280 --> 00:19:38,760
I ova razlika u performansama postaje sve izraženija

301
00:19:38,760 --> 00:19:41,120
više objekata od njih se traži da sortiraju.

302
00:19:53,040 --> 00:19:55,200
SMIJEH

303
00:19:57,600 --> 00:19:59,560
Pa, ovaj...

304
00:19:59,560 --> 00:20:02,920
- Žao mi je, možda...
- Ne, ne, ne, ne, ne.

305
00:20:02,920 --> 00:20:05,000
Mislim...mislim, ovaj...

306
00:20:05,000 --> 00:20:08,400
Mislim da bi sortiranje mehurića bilo pogrešan put.

307
00:20:08,400 --> 00:20:10,160
SMIJEH

308
00:20:10,160 --> 00:20:11,680
APLAUZ

309
00:20:12,720 --> 00:20:15,360
Hajde. Ko mu je ovo rekao?

310
00:20:22,480 --> 00:20:24,760
Sortiranje spajanjem pobjeđuje sortiranje oblačićima

311
00:20:24,760 --> 00:20:26,800
za sortiranje velikih količina podataka.

312
00:20:28,560 --> 00:20:31,200
Ali u ludom svijetu algoritama, postoji mnogo,

313
00:20:31,200 --> 00:20:33,520
mnogo različitih načina sortiranja.

314
00:20:36,000 --> 00:20:37,680
pri posljednjem prebrojavanju,

315
00:20:37,680 --> 00:20:41,160
postojalo je preko 20 različitih tipova algoritama za sortiranje.

316
00:20:42,920 --> 00:20:46,800
Svi na čudan način postižu isti rezultat, ali na različite načine.

317
00:20:58,240 --> 00:21:02,680
- Dakle, postoji sortiranje oblačićima, postoji sortiranje spajanjem.
- Sortiranje umetanjem.

318
00:21:02,680 --> 00:21:06,480
- Postoji hrpa sortiranja, postoji brzo sortiranje.
- Timsort.

319
00:21:06,480 --> 00:21:07,840
Imaš vrstu patuljaka.

320
00:21:07,840 --> 00:21:10,840
Postoji vrsta golubova, koja se još naziva i radix sorta.

321
00:21:10,840 --> 00:21:13,440
Postoji bogosort, koji se možda nikada neće završiti.

322
00:21:19,400 --> 00:21:23,320
Ne postoji najbolji algoritam za sortiranje.

323
00:21:23,320 --> 00:21:25,440
Svaki ima svoje prednosti i nedostatke.

324
00:21:26,640 --> 00:21:28,080
I koji se navikne

325
00:21:28,080 --> 00:21:31,080
često zavisi od specifičnosti problema.

326
00:21:32,760 --> 00:21:36,640
Mislim da je ljepota proučavanja algoritama pokušati težiti

327
00:21:36,640 --> 00:21:40,400
za rješenja koja su što elegantnija i efikasnija.

328
00:21:40,400 --> 00:21:44,640
Zapravo mislim da je vrsta mehurića vrlo lijepa. Sviđa mi se.

329
00:21:44,640 --> 00:21:46,320
Sortiranje spajanjem je predivno.

330
00:21:49,520 --> 00:21:51,840
Zaista ne bismo mogli bez njih.

331
00:21:51,840 --> 00:21:54,840
Algoritmi za sortiranje unose red u svijet.

332
00:22:05,240 --> 00:22:07,920
Do sada smo vidjeli algoritme kako se bave malim

333
00:22:07,920 --> 00:22:11,280
problemi s dimenzioniranjem naših kupaonskih pločica i sortiranjem naših podataka.

334
00:22:12,920 --> 00:22:16,040
Ali koliko se dobro nose sa neurednim svijetom ljubavi?

335
00:22:18,080 --> 00:22:20,880
Online dating je zaista popularan ovih dana.

336
00:22:20,880 --> 00:22:23,640
Zapravo, jedna anketa sugerira da više od trećine

337
00:22:23,640 --> 00:22:26,400
nedavnih brakova započetih na internetu.

338
00:22:27,400 --> 00:22:30,800
Način na koji ove web stranice za upoznavanje rade je da koriste nešto što se zove

339
00:22:30,800 --> 00:22:33,000
odgovarajući algoritam.

340
00:22:33,000 --> 00:22:36,200
Pretražuju po profilima, pokušavaju spojiti ljude prema

341
00:22:36,200 --> 00:22:40,320
prema njihovim sklonostima i nesklonostima, osobinama ličnosti i tako dalje.

342
00:22:40,320 --> 00:22:43,200
U stvari, algoritmi su izgleda bolji od ljudi.

343
00:22:43,200 --> 00:22:46,480
Jer nedavna istraživanja su pokazala da se oni koji se upoznaju na internetu

344
00:22:46,480 --> 00:22:49,160
imaju tendenciju da budu sretniji i imaju duže brakove.

345
00:22:52,360 --> 00:22:56,640
Zamoliću vas da primite svoje nagrade od Njegovog Veličanstva Kralja.

346
00:22:56,640 --> 00:23:01,080
U stvari, algoritmi za podudaranje imaju dosta toga da se pohvale.

347
00:23:01,080 --> 00:23:05,800
Jer 2012. je prvi put dodijeljena Nobelova nagrada

348
00:23:05,800 --> 00:23:07,840
zbog algoritma.

349
00:23:07,840 --> 00:23:11,280
Algoritam podudaranja koji je kreirao pokojni David Gale

350
00:23:11,280 --> 00:23:13,480
i matematičar Lloyd Shapley,

351
00:23:13,480 --> 00:23:16,240
ovdje se vidi kako prima svoj dio nagrade.

352
00:23:20,040 --> 00:23:23,720
Priča počinje 1960-ih kada su Gale i Shapley željeli

353
00:23:23,720 --> 00:23:27,840
riješiti problem u vezi sa upisom na fakultet.

354
00:23:27,840 --> 00:23:31,880
Kako spojiti studente i fakultete tako da svi dobiju mjesto.

355
00:23:32,880 --> 00:23:35,400
Ali, što je još važnije, bio je sretan, čak i ako

356
00:23:35,400 --> 00:23:37,480
nisu dobili svoj prvi izbor.

357
00:23:40,480 --> 00:23:44,160
Nazvali su to problemom stabilnog braka.

358
00:23:44,160 --> 00:23:46,680
Problem stabilnog braka ide ovako.

359
00:23:46,680 --> 00:23:49,120
Pretpostavimo da imate četiri žene i četiri muškarca

360
00:23:49,120 --> 00:23:51,000
i žele da se venčaju.

361
00:23:51,000 --> 00:23:54,000
Sada su se međusobno rangirali prema svojim preferencijama.

362
00:23:54,000 --> 00:23:55,880
Tako, na primjer, Kraljica srca ovdje,

363
00:23:55,880 --> 00:23:57,960
prvi izbor je Kralj trefova.

364
00:23:57,960 --> 00:24:00,040
Drugi izbor, Kralj dijamanata,

365
00:24:00,040 --> 00:24:02,840
a njen poslednji izbor je Kralj Srca.

366
00:24:02,840 --> 00:24:06,080
Dakle, ovdje je izazov igrati Kupidona i upariti kraljeve

367
00:24:06,080 --> 00:24:09,920
i kraljice tako da svaka dobije partnera, ali, što je još važnije,

368
00:24:09,920 --> 00:24:12,520
tako da brakovi budu stabilni.

369
00:24:12,520 --> 00:24:15,640
Stabilan brak znači da kraljevi i kraljice nemaju

370
00:24:15,640 --> 00:24:20,640
obavezno dobijaju svoj prvi izbor, ali dobijaju najbolje u ponudi.

371
00:24:20,640 --> 00:24:25,240
Na primjer, ako uparim Kralja srca i Kraljicu srca

372
00:24:25,240 --> 00:24:28,240
i pik kralj i pikova dama,

373
00:24:28,240 --> 00:24:31,040
ovo bi bio nestabilan brak.

374
00:24:31,040 --> 00:24:34,480
Zato što pikovom kralju baš i ne voli pikova dama.

375
00:24:34,480 --> 00:24:36,640
Više bi volio Kraljicu srca.

376
00:24:38,120 --> 00:24:40,040
Kraljica srca, sa svoje strane,

377
00:24:40,040 --> 00:24:41,960
ne voli Kralja srca.

378
00:24:41,960 --> 00:24:44,840
Ona bi više voljela pikovog kralja.

379
00:24:44,840 --> 00:24:48,120
Dakle, ovo dvoje će pobjeći zajedno u ovom paru.

380
00:24:51,960 --> 00:24:56,480
Tamo gdje postoji problem, tu je i algoritam koji ne zaostaje.

381
00:24:56,480 --> 00:24:59,160
Godine 1962. Gejl i Šepli su to smislili

382
00:24:59,160 --> 00:25:02,760
njihov algoritam dobitnik Nobelove nagrade.

383
00:25:02,760 --> 00:25:09,560
Recept korak po korak koji uvijek pronalazi savršeno stabilne brakove.

384
00:25:09,560 --> 00:25:11,240
Dakle, u prvom krugu algoritma,

385
00:25:11,240 --> 00:25:14,440
sve su kraljice zaprosile svoje kraljeve prvog izbora.

386
00:25:14,440 --> 00:25:18,720
Dakle, prvi izbor pikove dame je pikov kralj.

387
00:25:18,720 --> 00:25:21,200
Ona zaprosi pikovog kralja.

388
00:25:21,200 --> 00:25:24,360
Prvi izbor Kraljice Srca je Kralj Trefova,

389
00:25:24,360 --> 00:25:26,800
pa je zaprosila Kralja klubova.

390
00:25:26,800 --> 00:25:30,360
Prvi izbor Kraljice dijamanata je pikov kralj.

391
00:25:30,360 --> 00:25:33,320
A prvi izbor kraljice trefa je i pikov kralj.

392
00:25:33,320 --> 00:25:36,600
Dakle, čini se da je pikov kralj Darcy na ovom kraljevskom dvoru.

393
00:25:37,800 --> 00:25:40,560
Sada, pik kralj ima tri prijedloga.

394
00:25:41,720 --> 00:25:44,840
Zato bira svoju najpopularniju kraljicu,

395
00:25:44,840 --> 00:25:48,640
koja je zapravo Kraljica dijamanata, a odbacuje druga dva.

396
00:25:51,440 --> 00:25:55,600
Dakle, imamo dva privremena angažmana, dva odbijena.

397
00:25:55,600 --> 00:25:59,280
Sada uklanjamo prve izbore odbijene kraljice.

398
00:25:59,280 --> 00:26:01,040
I vrijeme je za drugu rundu.

399
00:26:02,480 --> 00:26:06,960
Dakle, pikova dama će zaprositi kralja dijamanata.

400
00:26:06,960 --> 00:26:10,160
A Kraljica trefa zaprosi Kralja trefa.

401
00:26:11,560 --> 00:26:14,240
Ali sada Kralj klubova ima dva prijedloga

402
00:26:14,240 --> 00:26:17,440
i zapravo preferira Kraljicu klubova.

403
00:26:17,440 --> 00:26:20,280
Stoga odbacuje Kraljicu srca, svoju privremenu

404
00:26:20,280 --> 00:26:22,920
angažman u prvom krugu algoritma,

405
00:26:22,920 --> 00:26:24,440
i moramo ponovo početi.

406
00:26:26,000 --> 00:26:28,080
U svakoj rundi, odbijene dame

407
00:26:28,080 --> 00:26:31,360
zaprositi sljedećeg kralja na njihovoj listi.

408
00:26:31,360 --> 00:26:34,480
A kraljevi uvijek traže najbolju ponudu koju dobiju.

409
00:26:35,680 --> 00:26:40,000
U ovom krugu algoritma ona zaprosi Kralja Srca

410
00:26:40,000 --> 00:26:44,040
i konačno, svi su upareni sa jednom kraljicom i kraljem

411
00:26:44,040 --> 00:26:45,960
i svi brakovi su stabilni.

412
00:26:49,120 --> 00:26:53,440
Gale-Shapley algoritam se danas koristi u cijelom svijetu.

413
00:26:53,440 --> 00:26:56,840
U Danskoj, uskladiti djecu sa dnevnim boravcima.

414
00:26:56,840 --> 00:27:00,040
U Mađarskoj, upariti učenike i škole.

415
00:27:00,040 --> 00:27:03,440
U New Yorku, dodijeliti rabine u sinagoge.

416
00:27:03,440 --> 00:27:07,360
I u Kini, Njemačkoj i Španiji, da uporedi studente sa univerzitetima.

417
00:27:10,480 --> 00:27:13,560
Dok je u Velikoj Britaniji, to je dovelo do razvoja

418
00:27:13,560 --> 00:27:18,440
algoritma podudaranja koji je nekim ljudima spasio živote.

419
00:27:23,040 --> 00:27:26,800
U dobi od 20 godina, Seraya u južnom Londonu je dijagnosticirana

420
00:27:26,800 --> 00:27:31,120
sa hroničnom bolešću bubrega i rekla da joj je potrebna transplantacija.

421
00:27:32,880 --> 00:27:37,000
Bio sam na dijalizi 18 mjeseci i jako loše.

422
00:27:37,000 --> 00:27:40,240
Nisam mogao da idem na posao. Nisam imao društveni život.

423
00:27:40,240 --> 00:27:44,200
Bila je to bukvalno bolnica tri puta sedmično za liječenje i kod kuće.

424
00:27:45,440 --> 00:27:47,880
Bliski prijatelj je bio spreman da donira,

425
00:27:47,880 --> 00:27:50,880
ali njihovi tipovi tkiva nisu bili kompatibilni.

426
00:27:53,480 --> 00:27:55,840
U Sent Albansu, Tamir je bio teško bolestan

427
00:27:55,840 --> 00:27:58,840
i njegova supruga Lindzi htela je da donira.

428
00:27:58,840 --> 00:28:00,560
Ali oni su imali isti problem.

429
00:28:02,000 --> 00:28:04,760
Prošli smo sve analize krvi i sve preglede

430
00:28:04,760 --> 00:28:08,040
i ispostavilo se da smo nekompatibilne krvne grupe.

431
00:28:10,320 --> 00:28:13,080
Često, bubrežni bolesnici koji imaju dovoljno sreće

432
00:28:13,080 --> 00:28:16,080
da bi potencijalni donator otkrio da postoji neslaganje

433
00:28:16,080 --> 00:28:18,920
između krvne grupe ili tipa tkiva njihovog donora.

434
00:28:20,720 --> 00:28:26,280
Ali od 2007. godine NHS koristi poseban algoritam za uparivanje

435
00:28:26,280 --> 00:28:29,160
kako bi se pronašla potencijalna podudaranja za voljnih donatora

436
00:28:29,160 --> 00:28:31,480
bubrežnim bolesnicima širom Velike Britanije.

437
00:28:35,360 --> 00:28:37,640
Kada smo prvi put pogledali ovaj problem,

438
00:28:37,640 --> 00:28:41,320
zaista smo potcijenili složenost.

439
00:28:41,320 --> 00:28:46,360
I prvobitno, tek smo počeli sa zamjenama između dva para.

440
00:28:46,360 --> 00:28:48,120
Tako da je bilo vrlo jednostavno,

441
00:28:48,120 --> 00:28:53,040
ali ubrzo je postalo očigledno da nam treba nešto mnogo složenije.

442
00:28:56,920 --> 00:29:00,000
Stupio sam u kontakt s Rachel Johnson u NHS-u

443
00:29:00,000 --> 00:29:02,720
i onda smo se u toj fazi uključili u mogućnost dizajna

444
00:29:02,720 --> 00:29:05,560
algoritmi koji bi omogućili ne samo razmjenu u parovima,

445
00:29:05,560 --> 00:29:08,120
ali i razmjene između tri para.

446
00:29:10,080 --> 00:29:13,080
Algoritam razmatra nekoliko scenarija.

447
00:29:13,080 --> 00:29:15,400
Najjednostavniji je dvosmjerna zamjena

448
00:29:15,400 --> 00:29:18,360
sa dva para koji razmjenjuju bubrege.

449
00:29:21,560 --> 00:29:23,840
Komplikovanija je trosmjerna zamjena,

450
00:29:23,840 --> 00:29:26,720
gde bubrezi prolaze kroz ciklus.

451
00:29:29,960 --> 00:29:34,960
U svakom od naših podudarnih ciklusa ima 200 pacijenata.

452
00:29:34,960 --> 00:29:38,960
Moramo potražiti sve moguće transplantacije.

453
00:29:40,200 --> 00:29:42,440
I iznenađujuće je koliko ih ima.

454
00:29:42,440 --> 00:29:44,440
Ima ih bukvalno, znate, stotine,

455
00:29:44,440 --> 00:29:47,040
ponekad hiljade mogućnosti.

456
00:29:47,040 --> 00:29:51,400
To je nešto što se jednostavno ne bi moglo postići bez algoritma.

457
00:29:53,120 --> 00:29:57,120
Jednog dana, Seraya je primila poziv da je pronađena poklapanja

458
00:29:57,120 --> 00:30:02,200
400 milja dalje sa Lindom, donatorom koja živi u Bownessu blizu Edinburga.

459
00:30:03,720 --> 00:30:06,760
Tati mog muža je trebao novi bubreg.

460
00:30:06,760 --> 00:30:11,200
Bio je bolestan neko vrijeme. I nisam bio savršen spoj.

461
00:30:11,200 --> 00:30:17,000
I onda sam dobio telefonski poziv i sve je krenulo odatle.

462
00:30:19,120 --> 00:30:20,920
Dobili smo prvi telefonski poziv

463
00:30:20,920 --> 00:30:23,520
bili smo upareni u trosmernom bazenu.

464
00:30:23,520 --> 00:30:26,560
Samo ste nervozni jer to neće ići dalje

465
00:30:26,560 --> 00:30:28,240
jer tvoj život zavisi od toga.

466
00:30:29,960 --> 00:30:31,640
Za parove koji se podudaraju,

467
00:30:31,640 --> 00:30:35,080
sve operacije su se morale odvijati istovremeno.

468
00:30:35,080 --> 00:30:38,280
Bio je to veliki logistički izazov.

469
00:30:38,280 --> 00:30:41,360
Kada je moj donator otišao u pozorište, zvali su da provjere

470
00:30:41,360 --> 00:30:44,600
da je i moj donator bio u Njukaslu i ide u pozorište.

471
00:30:44,600 --> 00:30:46,960
I oboje su ga dobili u isto vrijeme.

472
00:30:46,960 --> 00:30:49,400
I oni zovu i bubrezi izlaze.

473
00:30:49,400 --> 00:30:51,160
Mislim da su išli motorom.

474
00:30:51,160 --> 00:30:53,120
Rečeno nam je da bi mogli ići helikopterom,

475
00:30:53,120 --> 00:30:56,680
pa sam mislio da je barem jedan dio mene mogao biti u helikopteru,

476
00:30:56,680 --> 00:30:58,960
ali, ne, išlo je motorom.

477
00:31:02,880 --> 00:31:06,200
I to se na kraju, srećom, dogodilo u decembru.

478
00:31:06,200 --> 00:31:09,160
- Najbolji božićni poklon.
- Hm!

479
00:31:09,160 --> 00:31:12,440
Lično, samo sam zamislio da su doktori iza

480
00:31:12,440 --> 00:31:14,880
uparivanje ljudi sa ove liste.

481
00:31:14,880 --> 00:31:17,640
Dakle, da, malo je čudno

482
00:31:17,640 --> 00:31:20,240
da se na kraju dana svede na matematiku.

483
00:31:20,240 --> 00:31:23,720
To je sjajna shema i još uvijek je relativno skora.

484
00:31:23,720 --> 00:31:27,120
A prije mnogo godina, ne bih imao ovu priliku.

485
00:31:27,120 --> 00:31:31,480
Osjećam veliku zahvalnost Lindi i algoritmu.

486
00:31:31,480 --> 00:31:33,400
Dakle, da, veoma sam zahvalan.

487
00:31:34,680 --> 00:31:39,760
Do sada je više od 400 pacijenata koristilo program NHS

488
00:31:39,760 --> 00:31:42,520
i njegov poseban algoritam uparivanja.

489
00:31:42,520 --> 00:31:44,840
Tek kada smo zaista vidjeli medijske članke

490
00:31:44,840 --> 00:31:47,160
i zapravo smo počeli da mislimo, "Oh, čekaj,

491
00:31:47,160 --> 00:31:49,480
„ta osoba je možda zaista imala taj meč

492
00:31:49,480 --> 00:31:53,080
"kroz razmjenu parova u oktobarskom nizu podudaranja" i tako dalje,

493
00:31:53,080 --> 00:31:55,320
da zapravo počinjete da viđate priče

494
00:31:55,320 --> 00:31:57,200
koji stoje iza anonimnih podataka.

495
00:31:57,200 --> 00:32:00,560
Prilično je smiješno jer je David uvijek jako zabrinut

496
00:32:00,560 --> 00:32:03,400
da će algoritmu trebati dosta vremena da se pokrene.

497
00:32:03,400 --> 00:32:07,280
I, znate, prošlo je do 30 minuta i on se zabrine.

498
00:32:07,280 --> 00:32:10,440
Ali zapravo, 30 minuta, znate, nama,

499
00:32:10,440 --> 00:32:14,080
neverovatno je da sve to može da uradi za 30 minuta.

500
00:32:25,000 --> 00:32:29,360
Do sada smo videli kako su algoritmi sposobni za neverovatne podvige.

501
00:32:30,440 --> 00:32:33,520
Od rješavanja apstraktnih matematičkih problema

502
00:32:33,520 --> 00:32:37,320
da nam pomogne da pronađemo stvari na World Wide Webu.

503
00:32:37,320 --> 00:32:41,240
A ključna stvar za sve ove algoritme je njihova brzina.

504
00:32:41,240 --> 00:32:44,480
Dakle, važna karakteristika dobrog algoritma je prva

505
00:32:44,480 --> 00:32:47,440
da bi bilo bolje da je tačno, ali kada jednom znaš da je tačno,

506
00:32:47,440 --> 00:32:49,400
takođe je važno da brzo radi.

507
00:32:49,400 --> 00:32:52,600
Nije dobro imati algoritam koji traje duže

508
00:32:52,600 --> 00:32:57,000
nego svoj životni vijek za trčanje ako želite rezultat sutra.

509
00:32:58,320 --> 00:33:02,680
Ovaj algoritam za detekciju lica je primjer efikasnog algoritma.

510
00:33:02,680 --> 00:33:05,840
Pošto je efikasan, može da radi u realnom vremenu.

511
00:33:05,840 --> 00:33:07,720
I to je ono što ga čini korisnim.

512
00:33:09,640 --> 00:33:14,160
Ali baš kao iu stvarnom životu, neki problemi su teži od drugih.

513
00:33:14,160 --> 00:33:17,480
S vremena na vrijeme, algoritmi se susreću sa svojim parom.

514
00:33:19,200 --> 00:33:21,960
Mislim da je najčešća zabluda o algoritmima

515
00:33:21,960 --> 00:33:24,280
je samo da algoritmi mogu sve.

516
00:33:24,280 --> 00:33:27,240
Mislim da ljudi zapravo ne znaju za granice.

517
00:33:27,240 --> 00:33:30,760
Neki problemi se jednostavno ne mogu riješiti efikasnim algoritmima.

518
00:33:32,640 --> 00:33:36,800
Postoje neka mjesta gdje efikasni algoritmi ne mogu ići.

519
00:33:36,800 --> 00:33:40,000
Linije u pesku koje se ne mogu preći.

520
00:33:40,000 --> 00:33:43,240
Problem je u znanju koje probleme mogu riješiti

521
00:33:43,240 --> 00:33:44,680
a koje ne mogu.

522
00:33:48,040 --> 00:33:51,320
Uzmite ovu Rubikovu kocku i zamislite opštiji izazov

523
00:33:51,320 --> 00:33:54,000
pokušaja rješavanja kocke proizvoljnih dimenzija.

524
00:33:54,000 --> 00:33:57,040
Tako, na primjer, sa 50 kvadrata na svakoj strani.

525
00:33:57,040 --> 00:33:58,520
Mogli biste ovo očekivati

526
00:33:58,520 --> 00:34:01,600
da bude jedan od zaista đavolski teških problema,

527
00:34:01,600 --> 00:34:03,960
ali zapravo spada u laki tabor.

528
00:34:03,960 --> 00:34:08,000
Znamo algoritam koji može riješiti opštu Rubikovu kocku

529
00:34:08,000 --> 00:34:09,800
u razumnom roku.

530
00:34:13,320 --> 00:34:14,680
Iako izgleda teško,

531
00:34:14,680 --> 00:34:17,920
ovaj problem se može rešiti efikasnim algoritmima.

532
00:34:22,800 --> 00:34:25,280
Međutim, evo jednog koji definitivno ne može.

533
00:34:27,400 --> 00:34:30,320
Zamislite da imate tablu za nacrte proizvoljne veličine

534
00:34:30,320 --> 00:34:32,800
i raspored komada na tabli.

535
00:34:32,800 --> 00:34:34,360
Izazov je vježbati

536
00:34:34,360 --> 00:34:38,240
da li bijeli može iznuditi pobjedu sa ove pozicije.

537
00:34:38,240 --> 00:34:40,120
Sada, draftovi su prilično laka igra,

538
00:34:40,120 --> 00:34:42,400
ali je to matematicki dokazano

539
00:34:42,400 --> 00:34:46,640
da ne postoji algoritam koji može efikasno da reši ovaj problem.

540
00:34:46,640 --> 00:34:49,040
To je inherentno težak problem.

541
00:34:51,160 --> 00:34:55,600
Jedini način da riješite ovu zagonetku je kroz čistu muku -

542
00:34:55,600 --> 00:34:58,320
radeći sve milione mogućnosti.

543
00:35:00,080 --> 00:35:04,840
Dakle, ovaj problem je potpuno van domašaja efikasnih algoritama.

544
00:35:04,840 --> 00:35:06,520
Ne može se brzo riješiti.

545
00:35:10,240 --> 00:35:14,600
Ali za neke probleme, nije jasno koliko su teški.

546
00:35:14,600 --> 00:35:19,080
Ovo je veliki sudoku. Ima 625 kvadrata.

547
00:35:20,320 --> 00:35:24,400
Jedna od lijepih stvari kod sudokua je da kada jednom nađete rješenje,

548
00:35:24,400 --> 00:35:28,040
relativno je jednostavno provjeriti da li je ispravno ili ne.

549
00:35:28,040 --> 00:35:30,360
I ovo je istina koliko god bila velika zagonetka.

550
00:35:32,360 --> 00:35:34,800
U ovom slučaju, moram samo provjeriti svaki red,

551
00:35:34,800 --> 00:35:38,280
kolona i blok ne sadrže broj dvaput.

552
00:35:38,280 --> 00:35:42,240
Sudoku spada u veoma posebnu kategoriju problema

553
00:35:42,240 --> 00:35:44,840
koji svi dijele ovu karakteristiku.

554
00:35:44,840 --> 00:35:48,840
Jednom kada dođete do rješenja, uvijek ga je lako provjeriti.

555
00:35:49,880 --> 00:35:53,160
Misterija je da li postoji efikasan algoritam

556
00:35:53,160 --> 00:35:55,520
da na prvom mestu nađemo rešenje.

557
00:35:58,360 --> 00:36:02,520
I sudoku nije sam. Mnogo je ovakvih problema.

558
00:36:02,520 --> 00:36:05,040
Najintenzivnije proučavan od svih

559
00:36:05,040 --> 00:36:08,480
je poznat kao problem trgovačkog putnika.

560
00:36:13,360 --> 00:36:16,920
Prodavac putuje od vrata do vrata, od grada do grada,

561
00:36:16,920 --> 00:36:20,480
prodajem sve od četkica i Hoovera do dvostrukog stakla.

562
00:36:22,520 --> 00:36:25,000
Zvuči kao jednostavan posao.

563
00:36:25,000 --> 00:36:28,880
Ali svi trgovački putnici suočavaju se s istim pitanjem.

564
00:36:28,880 --> 00:36:31,560
Koji je najkraći put?

565
00:36:33,520 --> 00:36:37,400
Ovaj problem je toliko važan da je Institut za matematiku Clay

566
00:36:37,400 --> 00:36:42,120
ponudio 1 milion za onoga ko nađe efikasan algoritam,

567
00:36:42,120 --> 00:36:44,520
ili dokazati da nijedan ne postoji.

568
00:36:46,400 --> 00:36:49,000
Problem trgovačkog putnika ide ovako.

569
00:36:49,000 --> 00:36:50,520
Zamislite da ste prodavac

570
00:36:50,520 --> 00:36:55,120
i morate posjetiti listu gradova predstavljenih crvenim tačkama.

571
00:36:55,120 --> 00:36:57,640
Izazov je pronaći najkraći put

572
00:36:57,640 --> 00:37:02,040
tako da svaki grad posjetite jednom prije nego se vratite na svoju početnu tačku.

573
00:37:02,040 --> 00:37:04,520
Sada, možete zamisliti najbolju stvar

574
00:37:04,520 --> 00:37:07,520
da samo razmotrim sve rute, ovako.

575
00:37:13,960 --> 00:37:18,560
Metoda provjere svih mogućnosti je vrsta algoritma.

576
00:37:18,560 --> 00:37:20,440
I za tri grada, radi dobro

577
00:37:20,440 --> 00:37:23,640
jer postoje samo tri moguća ruta za provjeru.

578
00:37:27,080 --> 00:37:30,200
Ali šta ako na listu dodamo još dva grada?

579
00:37:32,920 --> 00:37:36,360
Sa pet gradova postoji 60 različitih mogućih ruta.

580
00:37:39,160 --> 00:37:44,040
A ako dodamo još jedan grad, onda postoji 360 mogućih ruta.

581
00:37:44,040 --> 00:37:49,320
A za deset gradova postoji preko 1,8 miliona mogućih ruta.

582
00:37:49,320 --> 00:37:51,600
Ako je naš algoritam progutao kroz njih,

583
00:37:51,600 --> 00:37:54,720
provjeravajući sve ovo brzinom od deset u sekundi,

584
00:37:54,720 --> 00:37:58,320
proći će dva dana prije nego što se nađe najkraći.

585
00:37:58,320 --> 00:38:01,720
Tako da možete vidjeti metodu isprobavanja svih različitih mogućnosti,

586
00:38:01,720 --> 00:38:06,440
neka vrsta brute-force algoritma, ako želite, jednostavno je nepraktična.

587
00:38:07,720 --> 00:38:10,880
Ako je neko pronašao brzi algoritam za problem trgovačkog putnika,

588
00:38:10,880 --> 00:38:12,280
to bi bilo izuzetno značajno.

589
00:38:12,280 --> 00:38:15,240
Ako bi neko od mojih učenika smislio efikasan algoritam

590
00:38:15,240 --> 00:38:17,320
za problem trgovačkog putnika,

591
00:38:17,320 --> 00:38:20,280
Naterao bih ga da mi to objasni,

592
00:38:20,280 --> 00:38:23,200
Ubio bih ga i onda bih otišao i zatražio

593
00:38:23,200 --> 00:38:25,720
Clay nagrada, milion.

594
00:38:25,720 --> 00:38:28,360
Ali mislim da su moji učenici sigurni.

595
00:38:29,680 --> 00:38:32,680
Problem se javlja u mnogim oblastima.

596
00:38:32,680 --> 00:38:35,000
Od lemljenja ploča...

597
00:38:37,360 --> 00:38:40,680
..za planiranje ruta za dostavu supermarketa.

598
00:38:40,680 --> 00:38:45,320
Ali da li je problem trgovačkog putnika tajno već riješen?

599
00:38:49,960 --> 00:38:54,080
Tim naučnika koji radi u Rothamsted Research-u u Harpendenu

600
00:38:54,080 --> 00:38:57,520
okrenuli su se prirodi da vide da li je pronašla odgovor.

601
00:39:03,200 --> 00:39:06,160
Sprovode složen eksperiment za proučavanje

602
00:39:06,160 --> 00:39:10,320
kako bumbar rješava problem trgovačkog putnika.

603
00:39:13,480 --> 00:39:17,680
Pčele moraju hraniti nektar kako bi opskrbile svoju košnicu.

604
00:39:17,680 --> 00:39:19,920
I zato moraju da posete

605
00:39:19,920 --> 00:39:22,520
moguće stotine cvijeća na svakom putovanju.

606
00:39:22,520 --> 00:39:25,240
Ono što žele je pronaći efikasan način

607
00:39:25,240 --> 00:39:28,040
da prođu između svih ovih cvijeća koje posjećuju.

608
00:39:31,360 --> 00:39:35,680
Skromni bumbar se suočava sa sopstvenim problemom trgovačkog putnika.

609
00:39:35,680 --> 00:39:38,360
Cveće je isto kao gradovi.

610
00:39:38,360 --> 00:39:41,480
A pčela je trgovački putnik.

611
00:39:41,480 --> 00:39:45,600
Jedna pčela će izaći u potrazi za hranom mnogo, mnogo puta svaki dan.

612
00:39:45,600 --> 00:39:47,360
Dakle, tokom jednog dana,

613
00:39:47,360 --> 00:39:51,680
zaista pomaže da se krene najefikasnijim mogućim putem.

614
00:39:51,680 --> 00:39:53,920
Dakle, ono što radimo je da pokušavamo da shvatimo

615
00:39:53,920 --> 00:39:58,000
koja tačno pravila koriste da bi suzili mogućnosti.

616
00:40:00,480 --> 00:40:04,160
Joe je postavio pet hranilica koje igraju ulogu cvijeća.

617
00:40:05,560 --> 00:40:10,200
Svaka hranilica ima dovoljno nektara da pčela mora posjetiti svih pet

618
00:40:10,200 --> 00:40:12,360
da mu pruži pun medeni stomak.

619
00:40:13,560 --> 00:40:16,280
A kako zapravo znate kuda to vodi?

620
00:40:16,280 --> 00:40:18,960
Za ovo koristimo harmonijski radar.

621
00:40:18,960 --> 00:40:22,280
Dakle, dok se vrti u krug, emituje radarski signal.

622
00:40:22,280 --> 00:40:25,200
I pričvrstili smo malu antenu na zadnji deo pčele,

623
00:40:25,200 --> 00:40:27,880
koji zatim reflektuje signal sa radara.

624
00:40:27,880 --> 00:40:31,200
Ovo nam omogućava da tačno vidimo gde je pčela otišla

625
00:40:31,200 --> 00:40:32,800
dok se kreće po terenu.

626
00:40:34,240 --> 00:40:38,000
Dakle, kako bumbar rješava problem trgovačkog putnika?

627
00:40:38,000 --> 00:40:40,120
U redu, sada ga uključujemo.

628
00:40:47,080 --> 00:40:51,600
Sa pet feedera, postoji ukupno 60 mogućih ruta.

629
00:40:51,600 --> 00:40:54,480
Najkraći je oko spoljne ivice.

630
00:40:58,040 --> 00:41:02,520
Ova toplotna mapa pokazuje put kojim je prešla jedna pčela.

631
00:41:02,520 --> 00:41:06,240
U početku, to je jednostavno otkrivanje položaja hranilica.

632
00:41:07,920 --> 00:41:12,360
Tada se čini da pčela metodično mijenja različite dijelove rute

633
00:41:12,360 --> 00:41:14,680
da vidim da li to može da skrati.

634
00:41:16,920 --> 00:41:20,760
U roku od 20 putovanja, izbrusio je na efikasnoj ruti.

635
00:41:26,480 --> 00:41:29,840
Ovaj put nije uvijek apsolutno najkraći,

636
00:41:29,840 --> 00:41:31,760
ali za pčelu je dovoljno dobro.

637
00:41:36,440 --> 00:41:40,040
Nevjerovatno je da su nakon nekoliko pokušaja uspjeli

638
00:41:40,040 --> 00:41:44,040
na nešto što je dovoljno efikasno da oni traže hranu.

639
00:41:44,040 --> 00:41:47,920
Da, tako je. Ne mogu provesti dane ili čak, znate,

640
00:41:47,920 --> 00:41:50,560
mogli bi potrajati mjeseci ili godine da se isproba svaka mogućnost.

641
00:41:50,560 --> 00:41:52,920
Tako da moraju vrlo brzo pronaći rutu

642
00:41:52,920 --> 00:41:55,680
koje mogu raditi iznova i iznova i iznova

643
00:41:55,680 --> 00:41:59,800
- u cilju efikasnog obezbeđivanja hrane.
- Fantastično.

644
00:41:59,800 --> 00:42:01,960
Mislim da je pčela sada postala moj omiljeni insekt.

645
00:42:01,960 --> 00:42:05,520
- Očigledno je matematičar u duši.
- Apsolutno.

646
00:42:06,920 --> 00:42:11,640
Da budemo jasni. Pčele neće biti nagrađene sa milion.

647
00:42:11,640 --> 00:42:15,120
Nisu nekim čudom riješili problem trgovačkog putnika

648
00:42:15,120 --> 00:42:18,080
jer ne nađu uvijek najkraći put.

649
00:42:19,400 --> 00:42:21,760
Ali njihov algoritam je pametan pristup.

650
00:42:21,760 --> 00:42:25,080
U matematici je to poznato kao heuristika.

651
00:42:25,080 --> 00:42:29,320
Algoritmi koji su efikasni, koji ne nalaze savršeno rješenje,

652
00:42:29,320 --> 00:42:31,080
ali prići što bliže mogu.

653
00:42:44,520 --> 00:42:46,720
Isti heuristički pristup

654
00:42:46,720 --> 00:42:49,960
je korišten za razvoj algoritma za aerodrom Heathrow.

655
00:42:51,400 --> 00:42:54,040
DISPEČER: 'Otvoreno za polijetanje...'

656
00:42:54,040 --> 00:42:57,880
Heathrow obavi preko 1.300 letova dnevno.

657
00:42:57,880 --> 00:43:00,000
To je najprometniji aerodrom u Evropi.

658
00:43:00,000 --> 00:43:04,640
'..430 slobodno za polijetanje. Površinski vjetar 247 stupnjeva pri tri čvora.'

659
00:43:12,840 --> 00:43:15,120
Izazov za kontrolu vazdušnog saobraćaja

660
00:43:15,120 --> 00:43:18,640
je maksimiziranje broja aviona koji polijeću svakog sata

661
00:43:18,640 --> 00:43:22,800
i osigurati da aerodrom radi efikasno i bezbedno.

662
00:43:22,800 --> 00:43:29,400
'..iza British Airwaysa 747, postrojite 27 odmah iza.'

663
00:43:29,400 --> 00:43:33,520
Jedna od ključnih odluka je redosled polijetanja.

664
00:43:33,520 --> 00:43:36,680
Trenutno polazimo iz grupe srednjih aviona,

665
00:43:36,680 --> 00:43:39,680
koji će biti odvojeni od jedne minute.

666
00:43:39,680 --> 00:43:43,400
Iza toga se, dakle, vidi 747, koji je veliki avion.

667
00:43:44,800 --> 00:43:48,200
Srednji avioni moraju biti odvojeni od turbulencije

668
00:43:48,200 --> 00:43:50,360
proizveden od strane većih aviona.

669
00:43:50,360 --> 00:43:52,720
Stoga je naručivanje veličina ključno.

670
00:43:53,800 --> 00:43:56,120
Idealna sekvenca za polijetanje uključuje

671
00:43:56,120 --> 00:43:58,840
zaista blokirajući grupe aviona.

672
00:43:58,840 --> 00:44:01,080
Dakle, želite da se veliki avioni grupišu zajedno,

673
00:44:01,080 --> 00:44:03,440
srednji avioni koji se grupišu.

674
00:44:03,440 --> 00:44:05,240
I to omogućava razdvajanje

675
00:44:05,240 --> 00:44:07,640
između tih aviona treba minimizirati.

676
00:44:10,640 --> 00:44:14,160
Drugi faktor koji treba uzeti u obzir pri planiranju polijetanja

677
00:44:14,160 --> 00:44:16,040
tamo kuda lete avioni.

678
00:44:19,920 --> 00:44:22,320
Želimo da jedan ide na sjever, jedan na jug,

679
00:44:22,320 --> 00:44:24,360
sljedeći ide na sjever, pa na jug.

680
00:44:24,360 --> 00:44:29,040
Kada bi svi avioni išli u istom pravcu, razmak bi bio mnogo veći

681
00:44:29,040 --> 00:44:31,560
i ne bismo koristili pistu tako efikasno.

682
00:44:31,560 --> 00:44:34,600
Svi kontrolori sjede u kontrolnim tornjevima i razmišljaju,

683
00:44:34,600 --> 00:44:37,880
„Imam sve ove letelice na sever, sve ove na jug.

684
00:44:37,880 --> 00:44:39,640
"Imam ove velike,

685
00:44:39,640 --> 00:44:42,200
„Zato želim da pokušam da grupišem sve velike zajedno

686
00:44:42,200 --> 00:44:44,600
"tako da ne moram ići od velikog do malog."

687
00:44:44,600 --> 00:44:48,000
I to je vrlo složen problem za rješavanje u njihovim glavama.

688
00:44:48,000 --> 00:44:50,440
'..906. novembar...'

689
00:44:50,440 --> 00:44:54,280
2013. godine timu se pridružio algoritam.

690
00:44:54,280 --> 00:44:58,240
Njegov posao je da predvidi najvjerovatniji redoslijed polijetanja

691
00:44:58,240 --> 00:45:00,400
i savjetovati kontrolu zračnog saobraćaja

692
00:45:00,400 --> 00:45:03,240
kada bi se avion trebao odgurnuti od kapija.

693
00:45:03,240 --> 00:45:06,240
Da biste to učinili, ne uključuje ništa manje od simulacije

694
00:45:06,240 --> 00:45:09,480
cjelokupni vanjski rad aerodroma.

695
00:45:11,280 --> 00:45:14,240
Izvođenje miliona proračuna svake sekunde.

696
00:45:14,240 --> 00:45:17,040
FAINT DISPATCHER

697
00:45:21,720 --> 00:45:25,080
Algoritam radi pokušavajući da predvidi

698
00:45:25,080 --> 00:45:28,360
kojim redosledom će avion poleteti.

699
00:45:28,360 --> 00:45:30,640
Ako zna kojim redosledom mogu da polete,

700
00:45:30,640 --> 00:45:32,560
onda može raditi unazad i reći,

701
00:45:32,560 --> 00:45:34,600
„Ako treba da poleti u ovo vreme,

702
00:45:34,600 --> 00:45:37,480
"onda treba ući u red na pisti u ovom trenutku,

703
00:45:37,480 --> 00:45:39,840
"onda treba završiti taksi u ovo vrijeme,

704
00:45:39,840 --> 00:45:42,520
"tako da u ovom trenutku treba da započne svoju taksi operaciju.

705
00:45:42,520 --> 00:45:45,480
"U tom slučaju, mora završiti svoje odbijanje do ovog trenutka,

706
00:45:45,480 --> 00:45:47,600
"tako da do ovog trenutka treba da počne sa odbijanjem."

707
00:45:47,600 --> 00:45:50,600
I može raditi sve unazad od vremena kada treba da poleti

708
00:45:50,600 --> 00:45:52,640
do kada bi trebalo da počne da se vraća.

709
00:45:55,440 --> 00:45:58,720
Izlaz algoritma se daje kontroli letenja

710
00:45:58,720 --> 00:46:01,560
preko internog kompjuterskog sistema aerodroma

711
00:46:01,560 --> 00:46:05,800
i prikazano pilotu na kapiji u obliku TSAT-a,

712
00:46:05,800 --> 00:46:07,800
preporučeno vrijeme vraćanja.

713
00:46:10,000 --> 00:46:12,800
Pilot može pogledati u sistem za ulazak u stalak

714
00:46:12,800 --> 00:46:15,960
da zapravo vidi u koje vrijeme očekuje da otputuje.

715
00:46:17,880 --> 00:46:21,200
Najveća prednost algoritma je što znači da možete

716
00:46:21,200 --> 00:46:25,040
držati avione na postolju duže, a da oni kasnije ne polete.

717
00:46:25,040 --> 00:46:28,440
Dakle, nema gubitaka za putnike u smislu kašnjenja.

718
00:46:28,440 --> 00:46:30,840
Ono što možete učiniti je da svoje motore možete pokrenuti kasnije.

719
00:46:33,080 --> 00:46:35,480
U stvari, ako uštedimo dva minuta taksi

720
00:46:35,480 --> 00:46:37,840
na putu do kraja piste, preko godinu dana,

721
00:46:37,840 --> 00:46:40,520
to je zapravo ušteda goriva vrijedna 15 miliona A£.

722
00:46:42,280 --> 00:46:46,240
Heathrow algoritam sekvenciranja pokazuje šta se može postići

723
00:46:46,240 --> 00:46:47,920
sa heurističkim pristupom.

724
00:46:49,040 --> 00:46:52,320
Baš kao i pčele, algoritam ne pronalazi

725
00:46:52,320 --> 00:46:55,360
apsolutno savršeno rešenje za sve vreme,

726
00:46:55,360 --> 00:46:58,720
ali ipak čini težak posao malo lakšim.

727
00:47:00,320 --> 00:47:02,080
Veoma smo ponosni na algoritam

728
00:47:02,080 --> 00:47:05,720
jer to zapravo sada, smatramo, modelira stvarni svijet i koristi se.

729
00:47:16,120 --> 00:47:19,080
U početku su kreirani algoritmi

730
00:47:19,080 --> 00:47:21,640
od matematičara za matematičare.

731
00:47:21,640 --> 00:47:23,800
I tokom prošlog veka,

732
00:47:23,800 --> 00:47:26,400
kreirani su algoritmi za kompjutere.

733
00:47:29,240 --> 00:47:33,960
Ali možda će naša veza proći kroz dramatičnu revoluciju.

734
00:47:39,720 --> 00:47:41,920
U Microsoft Research u Kembridžu,

735
00:47:41,920 --> 00:47:46,360
naučnici koriste nove tehnike za razvoj algoritama...

736
00:47:46,360 --> 00:47:50,400
brisanje granice između pronalazača i samog algoritma.

737
00:47:56,600 --> 00:47:59,920
Ovo je Kinect algoritam za praćenje skeleta.

738
00:47:59,920 --> 00:48:02,760
Neverovatna stvar je da je u stanju da se identifikuje

739
00:48:02,760 --> 00:48:04,920
različitim delovima mog tela.

740
00:48:04,920 --> 00:48:08,360
Tako da možete vidjeti da mi je vrh glave obojen u crveno

741
00:48:08,360 --> 00:48:11,040
i moja desna ruka ovde u plavom.

742
00:48:11,040 --> 00:48:13,560
Vidite da je moj vrat obojen u zeleno.

743
00:48:13,560 --> 00:48:16,080
Ovaj algoritam me nikada ranije nije sreo,

744
00:48:16,080 --> 00:48:18,760
ne znam kako ću se kretati u svemiru,

745
00:48:18,760 --> 00:48:22,040
ali samo koristeći podatke koji dolaze iz ove posebne kamere ovdje,

746
00:48:22,040 --> 00:48:25,520
mjerenje udaljenosti od kamere do mog tijela,

747
00:48:25,520 --> 00:48:28,120
može da napravi ovu mapu.

748
00:48:30,520 --> 00:48:33,960
Koji god položaj da zauzmem, koristeći ništa više od inputa

749
00:48:33,960 --> 00:48:36,360
sa specijalne kamere sa senzorom dubine,

750
00:48:36,360 --> 00:48:39,360
algoritam je u stanju da precizno identifikuje,

751
00:48:39,360 --> 00:48:42,760
piksel po piksel, različite dijelove mog tijela.

752
00:48:46,640 --> 00:48:49,720
Razvijen je za Microsoft Xbox konzolu

753
00:48:49,720 --> 00:48:53,640
za praćenje kretanja držanja tijela igrača u realnom vremenu.

754
00:48:58,440 --> 00:49:01,600
Ali isto tako izvanredno kao što ovaj algoritam može učiniti

755
00:49:01,600 --> 00:49:04,480
je proces iza kako je stvoren,

756
00:49:04,480 --> 00:49:07,080
kako objašnjava istraživač Jamie Shotton.

757
00:49:09,640 --> 00:49:12,640
Ono što se dešava je da svaki piksel na slici,

758
00:49:12,640 --> 00:49:16,080
pokrećemo algoritam koji se zove stablo odlučivanja.

759
00:49:16,080 --> 00:49:19,520
A stablo odluka možete zamisliti kao igru ​​od 20 pitanja.

760
00:49:19,520 --> 00:49:22,560
Dakle, stablo odlučivanja na neki način uzima piksel, recimo, na mojoj ruci,

761
00:49:22,560 --> 00:49:25,320
i pokušavam da odlučim, OK, moram da obojim to plavo

762
00:49:25,320 --> 00:49:28,480
- jer je to na ruci, a ne na mom tijelu.
- Da.

763
00:49:28,480 --> 00:49:31,200
Ključ za stablo odlučivanja je činjenica da 20 pitanja

764
00:49:31,200 --> 00:49:33,880
koje pitate nisu isti

765
00:49:33,880 --> 00:49:37,000
za svaki piksel koji pokušavamo da klasifikujemo.

766
00:49:37,000 --> 00:49:39,680
I cijeli set mogućih pitanja

767
00:49:39,680 --> 00:49:43,080
na koji bi se moglo odgovoriti je eksponencijalno.

768
00:49:43,080 --> 00:49:46,360
- Dva do dvadeset.
- Dobro, OK. To je preko milion pitanja,

769
00:49:46,360 --> 00:49:49,240
mnogo pitanja moraćete da programirate tamo.

770
00:49:49,240 --> 00:49:51,080
Da. Trajalo bi predugo

771
00:49:51,080 --> 00:49:55,120
i biti previše sklon greškama da bismo mi kao ljudi to programirali ručno.

772
00:49:55,120 --> 00:49:58,760
- Dakle, algoritam je vrsta samog pisanja, ili...?
- Apsolutno.

773
00:50:02,960 --> 00:50:05,520
Algoritam nije dizajnirao Jamie

774
00:50:05,520 --> 00:50:08,960
ali umjesto toga kroz proces koji se zove mašinsko učenje.

775
00:50:11,440 --> 00:50:15,720
To je uključivalo prikazivanje algoritma miliona slika treninga,

776
00:50:15,720 --> 00:50:19,320
tijela u različitim pozama i raznih oblika i veličina,

777
00:50:19,320 --> 00:50:23,600
od veoma debelih do veoma mršavih, veoma niskih do veoma visokih.

778
00:50:24,640 --> 00:50:28,880
I iz ovoga je algoritam u suštini naučen na primjeru,

779
00:50:28,880 --> 00:50:31,040
osmišljavanje sopstvenih pravila.

780
00:50:34,200 --> 00:50:37,760
Gdje naša inteligencija dolazi kao dizajneri sistema

781
00:50:37,760 --> 00:50:41,240
nije u programiranju algoritma, sam po sebi,

782
00:50:41,240 --> 00:50:44,200
već u dizajniranju skupa podataka za obuku

783
00:50:44,200 --> 00:50:48,160
da uhvatimo sve vrste varijacija koje očekujemo da vidimo

784
00:50:48,160 --> 00:50:51,040
kada ovaj sistem postavimo u dnevne sobe ljudi

785
00:50:51,040 --> 00:50:52,360
da igraju njihove igre.

786
00:50:52,360 --> 00:50:55,600
Dakle, na kraju, da li zapravo znate šta algoritam radi?

787
00:50:55,600 --> 00:50:57,800
Možemo da shvatimo šta pokušava da uradi

788
00:50:57,800 --> 00:50:59,400
i kako to otprilike funkcionira,

789
00:50:59,400 --> 00:51:02,960
ali nikako nismo mogli da shvatimo šta se tačno dešava.

790
00:51:04,960 --> 00:51:09,920
Isti pristup mašinskog učenja korišten je u drugim aplikacijama.

791
00:51:09,920 --> 00:51:14,680
Na primjer, ovaj algoritam je u stanju raditi nešto što dugo vremena

792
00:51:14,680 --> 00:51:19,560
smatralo se da je vještina isključivo neurohirurga i radiologa.

793
00:51:19,560 --> 00:51:22,800
Iz MR skeniranja, algoritam može identificirati

794
00:51:22,800 --> 00:51:26,480
i mapirati tumor na mozgu u 3-D.

795
00:51:26,480 --> 00:51:29,280
To znači da posao koji obično traje sat vremena

796
00:51:29,280 --> 00:51:31,360
može se obaviti za nekoliko minuta.

797
00:51:34,640 --> 00:51:37,640
Profesor Chris Bishop je zainteresovan za razvoj

798
00:51:37,640 --> 00:51:40,880
koncept mašinskog učenja još dalje.

799
00:51:40,880 --> 00:51:44,680
Da kreiramo algoritme koji mogu učiti baš kao i mi,

800
00:51:44,680 --> 00:51:46,600
direktno iz iskustva.

801
00:51:49,160 --> 00:51:52,120
Tako da ova demonstracija, mislim, ilustruje pravac

802
00:51:52,120 --> 00:51:54,120
da će algoritmi raditi u godinama koje su pred nama.

803
00:51:54,120 --> 00:51:57,640
OK, mogu vidjeti mnogo filmova ovdje gore, pa šta će algoritam uraditi?

804
00:51:57,640 --> 00:52:00,760
Imamo nekoliko stotina najčešće gledanih filmova,

805
00:52:00,760 --> 00:52:02,240
i šta će to učiniti,

806
00:52:02,240 --> 00:52:06,600
naučit će o vašim ličnim sklonostima i nesviđanjima.

807
00:52:06,600 --> 00:52:08,080
Već je obučeno,

808
00:52:08,080 --> 00:52:11,080
tako da je to algoritam mašinskog učenja iza kulisa,

809
00:52:11,080 --> 00:52:14,480
ali je već obučen na osnovu podataka od oko 10.000 ljudi.

810
00:52:14,480 --> 00:52:18,160
Ono što će sada uraditi je da nauči o vašim preferencijama.

811
00:52:18,160 --> 00:52:20,200
Trenutno ne zna ništa o tebi,

812
00:52:20,200 --> 00:52:22,760
tako da su ovi filmovi samo nasumično poređani na ekranu.

813
00:52:22,760 --> 00:52:25,440
Ono što treba da uradiš je da nađeš jedan od ovih filmova,

814
00:52:25,440 --> 00:52:28,120
ili onaj koji vam se sviđa ili onaj koji vam se ne sviđa.

815
00:52:28,120 --> 00:52:31,160
Ako vam se sviđa, možete ga prevući do zelene regije,

816
00:52:31,160 --> 00:52:33,600
ako vam se ne sviđa, preko u crvenu regiju.

817
00:52:33,600 --> 00:52:35,600
Rushmore, veliki sam obožavatelj Rushmorea.

818
00:52:35,600 --> 00:52:37,560
Sviđa ti se Rushmore? OK, u redu.

819
00:52:37,560 --> 00:52:41,120
Dakle, ono što se sada dešava je da ako je film dole sa desne strane

820
00:52:41,120 --> 00:52:44,760
- u blizini zelene regije, vrlo je siguran da će vam se svidjeti.
- OK.

821
00:52:44,760 --> 00:52:46,600
Dakle, ovde dole blizu crvenog regiona,

822
00:52:46,600 --> 00:52:48,560
vrlo sam siguran da ti se neće svidjeti.

823
00:52:48,560 --> 00:52:51,400
U sredini je 50-50. To zapravo ne zna.

824
00:52:51,400 --> 00:52:54,320
Dakle, ako izaberem film u sredini ovdje,

825
00:52:54,320 --> 00:52:57,680
Nisam veliki obožavatelj Austina Powersa, pa hajde da snimimo taj...

826
00:52:57,680 --> 00:53:00,800
Pa vidite, počinju da se šire postrance,

827
00:53:00,800 --> 00:53:04,480
- Biće malo samouverenije.
- Prilično je dobro.

828
00:53:04,480 --> 00:53:07,480
Veliki sam obožavatelj Dr Strangelove

829
00:53:07,480 --> 00:53:11,480
i veliki sam obožavatelj Vudija Alena,

830
00:53:11,480 --> 00:53:14,520
ali Spinal Tap, misli da će mi se to svidjeti.

831
00:53:14,520 --> 00:53:18,040
Dakle, to je zanimljivo, pa kada je bio siguran da vam se sviđaju

832
00:53:18,040 --> 00:53:19,800
i rekao si da ti se sviđaju,

833
00:53:19,800 --> 00:53:22,920
nije se mnogo toga dogodilo jer se nije mnogo naučilo.

834
00:53:22,920 --> 00:53:25,840
Kada ste bili sigurni da će vam se svidjeti, u slučaju kičmenog tapa

835
00:53:25,840 --> 00:53:28,280
a vi ste rekli, "Ne sviđa mi se", došlo je do velike promene.

836
00:53:28,280 --> 00:53:30,200
To je učenje stvari od mene.

837
00:53:30,200 --> 00:53:33,080
Ja zapravo mijenjam algoritam dok sam u interakciji s njim.

838
00:53:33,080 --> 00:53:36,520
Tačno. Dok je Kinect bio obučen u laboratoriji i potom zamrznut,

839
00:53:36,520 --> 00:53:38,560
ovaj algoritam nastavlja da se prilagođava

840
00:53:38,560 --> 00:53:41,280
i nastavlja da se razvija tokom svog života.

841
00:53:41,280 --> 00:53:44,120
Što više filmova ocijenite da im se sviđaju i ne sviđaju,

842
00:53:44,120 --> 00:53:45,960
što više zna o vama lično

843
00:53:45,960 --> 00:53:48,760
i što je u stanju da da dobre preporuke.

844
00:53:48,760 --> 00:53:52,320
Ovaj algoritam počinje da se oseća mnogo ljudskije

845
00:53:52,320 --> 00:53:54,840
na način na koji je u interakciji sa svijetom.

846
00:53:54,840 --> 00:53:57,840
Da li je to vaš cilj, pronaći način za proizvodnju algoritama

847
00:53:57,840 --> 00:54:00,560
to liči na način na koji pregovaramo o svijetu?

848
00:54:00,560 --> 00:54:03,720
Tačno. To je korak niz taj veoma dug put do proizvodnje mašina

849
00:54:03,720 --> 00:54:05,880
koji su zaista sposobni koliko i ljudski mozak.

850
00:54:05,880 --> 00:54:08,720
Pred nama je dug put, ali ovo je mali korak u tom pravcu

851
00:54:08,720 --> 00:54:10,160
jer to više nije popravljeno.

852
00:54:10,160 --> 00:54:12,480
Sada nastavlja da uči na isti način

853
00:54:12,480 --> 00:54:14,800
koje nastavljamo da učimo u svakodnevnom životu.

854
00:54:19,680 --> 00:54:21,680
Mislim da tek počinjemo

855
00:54:21,680 --> 00:54:24,240
kako bi se ostvario puni potencijal algoritama

856
00:54:24,240 --> 00:54:26,600
i imam još jedno mjesto koje želim posjetiti,

857
00:54:26,600 --> 00:54:28,840
za koje mi je rečeno da će mi dati uvid

858
00:54:28,840 --> 00:54:31,760
koliko su oni u stanju da urade za nas.

859
00:54:40,600 --> 00:54:43,600
To je svijet u kojem je gotovo sve automatizirano.

860
00:54:46,920 --> 00:54:49,400
Gdje su algoritmi u kontroli.

861
00:54:49,400 --> 00:54:53,920
To je najveće automatizirano skladište namirnica na svijetu.

862
00:54:53,920 --> 00:54:57,520
Pripada online prodavcu prehrambenih proizvoda Ocado

863
00:54:57,520 --> 00:55:01,000
i to je ekvivalent 45 supermarketa u jednom.

864
00:55:02,720 --> 00:55:06,600
Preko dva miliona artikala prođe kroz ovo skladište svakog dana.

865
00:55:06,600 --> 00:55:10,360
U svakom trenutku postoji oko 7.000 sanduka

866
00:55:10,360 --> 00:55:12,800
prelazak preko 25 kilometara staze,

867
00:55:12,800 --> 00:55:18,360
i kontrola svakog aspekta ovog zadivljujućeg spektakla su algoritmi.

868
00:55:25,520 --> 00:55:29,120
Svaki od tih crvenih sanduka je dio narudžbe kupca

869
00:55:29,120 --> 00:55:32,880
i oni mogu nastaviti odavde da pronađu druge predmete

870
00:55:32,880 --> 00:55:35,160
koje žele preko magacina,

871
00:55:35,160 --> 00:55:37,280
dok se na kraju ne završe,

872
00:55:37,280 --> 00:55:41,360
utovaren u kombi, a zatim odvezen našim sistemom rutiranja

873
00:55:41,360 --> 00:55:43,720
na ruti, koja na mnogo načina,

874
00:55:43,720 --> 00:55:47,360
rješava probleme kao što je problem trgovačkog putnika.

875
00:55:47,360 --> 00:55:49,720
Odluke se donose posvuda

876
00:55:49,720 --> 00:55:52,240
kao što crveni sanduk ide ovuda pa onuda.

877
00:55:52,240 --> 00:55:55,600
Složenost koja stoji iza svega ovoga je iznad

878
00:55:55,600 --> 00:55:58,760
šta bi bilo koji čovjek mogao kontrolisati ili riješiti,

879
00:55:58,760 --> 00:56:01,760
i tu su ti algoritmi,

880
00:56:01,760 --> 00:56:03,960
dolaze ove tehnike rješavanja problema

881
00:56:03,960 --> 00:56:05,920
da prevaziđu te izazove.

882
00:56:11,000 --> 00:56:15,480
Gdje god pogledate, nevidljiva ruka algoritma je na djelu.

883
00:56:16,560 --> 00:56:20,360
Algoritmi predviđanja prate i dopunjuju zalihe

884
00:56:20,360 --> 00:56:24,720
sa više od 43.000 proizvoda, predviđajući potražnju kupaca.

885
00:56:26,760 --> 00:56:29,840
Algoritmi kontrolnog sistema upravljaju prometom

886
00:56:29,840 --> 00:56:33,320
od više od 7.000 sanduka oko skladišta.

887
00:56:36,360 --> 00:56:39,800
A algoritmi za usmjeravanje kombija kontroliraju kretanje flote

888
00:56:39,800 --> 00:56:41,960
od preko 1.500 kombija,

889
00:56:41,960 --> 00:56:46,240
testiranje preko četiri miliona različitih kombinacija ruta svake sekunde.

890
00:56:48,120 --> 00:56:51,160
Gotovo da možete vidjeti kako um mašine radi

891
00:56:51,160 --> 00:56:54,360
i to nije statičan proces, pa je zato ogromna količina

892
00:56:54,360 --> 00:56:59,520
strojnog učenja ovdje, tako da je to kao organizam koji se sam prilagođava.

893
00:56:59,520 --> 00:57:02,200
Neprestano se mora učiti kako to učiniti bolje.

894
00:57:02,200 --> 00:57:04,360
Ljudi to nisu mogli.

895
00:57:04,360 --> 00:57:06,600
Mašina se mora sama podesiti.

896
00:57:10,640 --> 00:57:14,080
Dakle, za koga biste rekli da je zapravo kontrolisao celu stvar?

897
00:57:14,080 --> 00:57:17,400
Na kraju krajeva, algoritmi su ti koji imaju kontrolu.

898
00:57:17,400 --> 00:57:19,960
Mislim da dobijam algoritamske talase vrućine

899
00:57:19,960 --> 00:57:22,080
gledajući ovu nevjerovatnu stvar!

900
00:57:24,440 --> 00:57:26,560
U nekom smislu, ovo skladište je kao

901
00:57:26,560 --> 00:57:28,880
mali mikrokosmos savremenog sveta.

902
00:57:28,880 --> 00:57:32,640
Algoritmi pokreću sve od pretraživača na internetu,

903
00:57:32,640 --> 00:57:35,680
Sat navigacija, čak i čuvanje naših kreditnih kartica.

904
00:57:35,680 --> 00:57:39,680
Naš svijet ne bi funkcionisao bez snage ovih algoritama.

905
00:57:45,440 --> 00:57:48,920
Otvoreni univerzitet je napravio besplatan paket za učenje,

906
00:57:48,920 --> 00:57:52,880
kreirajte i otkrijte više o digitalnoj tehnologiji prošlosti i sadašnjosti.

907
00:57:52,880 --> 00:57:55,280
Za naručivanje svog primjerka pozovite...

908
00:57:58,560 --> 00:58:00,080
..ili pratite link ispod

909
00:58:00,080 --> 00:58:01,680
na Otvoreni univerzitet.


