1
00:00:03,740 --> 00:00:05,400
Sem percebermos,
2
00:00:05,400 --> 00:00:08,240
a vida moderna
assumiu o controle.
3
00:00:09,920 --> 00:00:12,000
Quando buscamos
um parceiro...
4
00:00:12,300 --> 00:00:14,200
...fazemos compras online...
5
00:00:14,820 --> 00:00:16,880
...viajamos pelo mundo...
6
00:00:17,640 --> 00:00:20,000
...e até quando
salvamos vidas,
7
00:00:20,000 --> 00:00:22,280
há instruções passo a passo
8
00:00:22,280 --> 00:00:25,360
agindo sutilmente
nos bastidores.
9
00:00:26,720 --> 00:00:30,040
Cada vez mais, elas estão
dominando nossas vidas.
10
00:00:30,240 --> 00:00:33,080
Elas são chamadas algoritmos.
11
00:00:34,280 --> 00:00:36,560
Algoritmos estão
por toda parte.
12
00:00:36,560 --> 00:00:38,520
Esses pedaços matemáticos
compostos por bits
13
00:00:38,520 --> 00:00:41,160
tornaram-se fundamentais
em nosso cotidiano.
14
00:00:41,240 --> 00:00:44,720
Mas como são invisíveis,
costumamos ignorá-los,
15
00:00:44,720 --> 00:00:46,440
e até não os compreendemos.
16
00:00:46,440 --> 00:00:48,640
Qual é a forma mais
eficiente de se ordenar
17
00:00:48,640 --> 00:00:50,980
um milhão de
inteiros de 32 bits?
18
00:00:53,160 --> 00:00:55,760
Eles são o segredo
para nosso mundo digital,
19
00:00:55,760 --> 00:00:57,520
e muito mais que isso.
20
00:00:58,320 --> 00:01:00,840
Nesse programa,
irei mostrar a você
21
00:01:00,840 --> 00:01:02,920
alguns dos meus
algoritmos favoritos,
22
00:01:02,920 --> 00:01:05,320
para revelar de onde
eles vieram...
23
00:01:05,920 --> 00:01:07,760
Algoritmos são antigos.
24
00:01:08,120 --> 00:01:09,440
...como eles funcionam...
25
00:01:09,440 --> 00:01:11,720
O desafio é encontrar
a rota mais curta...
26
00:01:11,960 --> 00:01:14,360
Essas são as instruções
que você usaria
27
00:01:14,640 --> 00:01:17,500
...para retornar a
seu ponto de partida.
28
00:01:17,500 --> 00:01:19,920
...o que eles poderão
realizar no futuro...
29
00:01:19,960 --> 00:01:22,080
O algoritmo está se
reescrevendo? Ou...?
30
00:01:22,240 --> 00:01:23,360
Exatamente.
31
00:01:23,360 --> 00:01:25,880
...e como não podemos
viver sem eles.
32
00:01:25,880 --> 00:01:27,520
Até quando fazemos um bolo,
33
00:01:27,520 --> 00:01:29,240
estamos seguindo
um algoritmo.
34
00:01:29,360 --> 00:01:32,320
Como matemático,
eu amo algoritmos.
35
00:01:32,320 --> 00:01:34,920
Eles não são só incríveis
resolvedores de problemas,
36
00:01:34,920 --> 00:01:37,200
mas também
estranhamente belos,
37
00:01:37,200 --> 00:01:39,240
usando-se da
ordem matemática
38
00:01:39,240 --> 00:01:42,080
que sustenta todo o
funcionamento do Universo.
39
00:01:42,080 --> 00:01:44,360
Bem-vindos ao estranho
e maravilhoso mundo
40
00:01:44,360 --> 00:01:46,200
dos algoritmos.
41
00:01:51,000 --> 00:01:53,560
AS REGRAS SECRETAS DO
MUNDO MODERNO: ALGORITMOS
42
00:01:54,520 --> 00:01:57,440
A maioria de nós carrega
um desses por aí.
43
00:01:57,440 --> 00:01:58,640
Você deve ter percebido que,
44
00:01:58,640 --> 00:02:00,960
ao tirar uma foto
com o seu celular,
45
00:02:01,120 --> 00:02:02,800
ele, então, desenha uma caixa
46
00:02:02,800 --> 00:02:05,520
ao redor de qualquer rosto,
dessa forma...
47
00:02:05,720 --> 00:02:06,560
Esse é o resultado
48
00:02:06,560 --> 00:02:09,400
de um algoritmo especial
de detecção de faces,
49
00:02:09,400 --> 00:02:13,480
e ele ajuda a manter
o rosto da foto em foco.
50
00:02:14,360 --> 00:02:17,960
Como todos os algoritmos,
este aqui resolve um problema.
51
00:02:18,160 --> 00:02:21,160
Nesse caso, encontrar
um rosto humano.
52
00:02:21,600 --> 00:02:24,560
Embora não se engane
por um rosto com frutas,
53
00:02:24,560 --> 00:02:28,320
ele detecta o rosto
humano em uma foto.
54
00:02:28,440 --> 00:02:30,520
Então, como ele faz isso?
55
00:02:31,080 --> 00:02:33,840
Em sua essência,
algoritmos não são mais
56
00:02:33,840 --> 00:02:37,000
do que uma série de
instruções passo a passo.
57
00:02:37,200 --> 00:02:40,440
Este funciona escaneando,
metodicamente, a imagem,
58
00:02:40,440 --> 00:02:43,280
em busca de quatro padrões
abstratos específicos,
59
00:02:43,280 --> 00:02:45,520
associados a um rosto.
60
00:02:45,520 --> 00:02:48,160
Quando eles são detectados,
um após o outro,
61
00:02:48,160 --> 00:02:49,600
então, o algoritmo indica
62
00:02:49,600 --> 00:02:51,880
que encontrou
um rosto humano.
63
00:02:52,440 --> 00:02:55,400
O processo se aproveita
de um padrão básico,
64
00:02:55,400 --> 00:02:56,800
presente em todos os rostos,
65
00:02:56,800 --> 00:02:59,080
não importa o formato
ou o tamanho.
66
00:02:59,080 --> 00:03:01,520
O resultado final
é apenas um exemplo
67
00:03:01,520 --> 00:03:04,760
de como os algoritmos
facilitaram nossas vidas.
68
00:03:05,040 --> 00:03:06,600
- Eu quero! - Eu faço!
- Eu faço!
69
00:03:06,600 --> 00:03:08,840
Eu vou participar.
Eu estava aqui antes.
70
00:03:08,840 --> 00:03:10,000
Bem, pode começar.
71
00:03:10,240 --> 00:03:13,160
Nós tendemos a associar
algoritmos a computadores,
72
00:03:13,160 --> 00:03:15,240
smartphones e à Internet.
73
00:03:15,240 --> 00:03:18,640
Mas eles não são exclusivos
do mundo da tecnologia.
74
00:03:19,040 --> 00:03:21,920
Eu trabalho como
Professor de Matemática
75
00:03:21,920 --> 00:03:23,720
na Universidade de Oxford.
76
00:03:24,040 --> 00:03:26,080
E uma das coisas
que eu mais gosto
77
00:03:26,080 --> 00:03:28,800
é manter o interesse
dos estudantes.
78
00:03:28,800 --> 00:03:30,240
OK, vou pegar um.
79
00:03:30,720 --> 00:03:33,080
Aqui, estamos brincando
com um jogo matemático,
80
00:03:33,080 --> 00:03:34,600
usando um frasco
cheio de chocolates
81
00:03:34,600 --> 00:03:37,120
e uma ardida
pimenta vermelha.
82
00:03:38,320 --> 00:03:42,440
O objetivo é não ficar
com a pimenta no final.
83
00:03:42,600 --> 00:03:44,760
Mas o que os estudantes
não sabem é que
84
00:03:44,760 --> 00:03:48,000
estou brincando com a
ajuda de um algoritmo.
85
00:03:49,400 --> 00:03:51,680
- OK. Prontas?
- Sim.
86
00:03:51,680 --> 00:03:52,720
Certo, eu irei primeiro.
87
00:03:52,720 --> 00:03:54,280
Então, lembrem-se:
podem pegar um,
88
00:03:54,280 --> 00:03:56,080
dois ou três chocolates
de uma só vez.
89
00:03:57,080 --> 00:03:58,560
Não sou ganancioso, então,
90
00:03:58,560 --> 00:04:00,800
vou pegar apenas um.
Agora, é a sua vez.
91
00:04:00,800 --> 00:04:02,760
Cada jogador tem o seu turno,
92
00:04:02,760 --> 00:04:05,280
podendo pegar entre
um e três chocolates.
93
00:04:05,280 --> 00:04:06,440
Você pegou dois, OK.
94
00:04:06,440 --> 00:04:09,040
Então, eu irei pegar...
Eu irei pegar dois.
95
00:04:09,040 --> 00:04:10,760
Não importa o que
meu oponente faça,
96
00:04:10,760 --> 00:04:13,920
meu algoritmo me diz
como devo reagir.
97
00:04:14,040 --> 00:04:15,640
OK, eu irei pegar dois.
98
00:04:16,400 --> 00:04:17,920
E é sua vez, novamente.
99
00:04:18,920 --> 00:04:19,960
Oh, sim.
100
00:04:20,560 --> 00:04:23,800
- Então, irei pegar três.
- Três, e eu irei pegar um.
101
00:04:23,800 --> 00:04:26,320
E só sobrou a pimenta...
- Espere! Sou eu?
102
00:04:26,320 --> 00:04:27,960
Sim, vai ter que
comer a pimenta!
103
00:04:28,480 --> 00:04:29,400
Bem, aí está!
104
00:04:29,400 --> 00:04:31,000
Deixe-me revelar
como o algoritmo
105
00:04:31,000 --> 00:04:33,160
que eu estava usando
me ajudou a vencer.
106
00:04:33,160 --> 00:04:34,640
É a única forma de aprender.
107
00:04:35,560 --> 00:04:40,840
A chave é pensar em agrupar
as coisas em quartetos.
108
00:04:41,300 --> 00:04:44,880
13 chocolates divididos
em 3 grupos de 4,
109
00:04:44,880 --> 00:04:46,320
com um sobrando.
110
00:04:46,320 --> 00:04:48,240
Então, ao pegar
um chocolate
111
00:04:48,240 --> 00:04:49,440
na primeira rodada
112
00:04:49,440 --> 00:04:51,400
e, a seguir, quatro
menos o quanto
113
00:04:51,400 --> 00:04:54,040
o outro jogador pegue
nas rodadas subsequentes,
114
00:04:54,040 --> 00:04:56,840
esse algoritmo assegura
que o outro jogador
115
00:04:56,840 --> 00:04:59,040
sempre irá ficar
com a pimenta.
116
00:04:59,040 --> 00:05:01,000
A essência de
um ótimo algoritmo,
117
00:05:01,000 --> 00:05:02,600
a sua mágica,
por assim dizer,
118
00:05:02,600 --> 00:05:03,960
é a Matemática.
119
00:05:03,960 --> 00:05:05,720
Os melhores algoritmos
são aqueles
120
00:05:05,720 --> 00:05:08,640
que tiram partido da
estrutura matemática básica
121
00:05:08,640 --> 00:05:10,560
oculta abaixo do problema.
122
00:05:11,000 --> 00:05:12,880
Ok, ponha a pimenta de volta.
123
00:05:14,360 --> 00:05:17,440
Eu irei introduzi-los
a alguns dos algoritmos
124
00:05:17,440 --> 00:05:20,720
que se tornaram
símbolo da vida moderna.
125
00:05:21,760 --> 00:05:23,920
Mas, antes, eu quero
mostrar a vocês que,
126
00:05:23,920 --> 00:05:26,000
apesar de todas as suas
aplicações modernas,
127
00:05:26,000 --> 00:05:29,000
os algoritmos são
extremamente antigos.
128
00:05:29,360 --> 00:05:31,880
De fato, eles antecedem
os computadores
129
00:05:31,880 --> 00:05:34,240
em milhares de anos.
130
00:05:35,120 --> 00:05:37,320
O algoritmo mais
antigo já conhecido
131
00:05:37,320 --> 00:05:40,400
foi projetado para resolver
um problema matemático.
132
00:05:40,400 --> 00:05:41,560
Ele foi inicialmente escrito
133
00:05:41,560 --> 00:05:44,800
pelo matemático grego
da Antiguidade, Euclides.
134
00:05:45,120 --> 00:05:47,360
O Algoritmo de Euclides,
como ele é conhecido,
135
00:05:47,360 --> 00:05:51,000
é um método para encontrar
o Máximo Divisor Comum.
136
00:05:52,000 --> 00:05:55,280
O Máximo Divisor Comum
é o maior número
137
00:05:55,280 --> 00:05:57,720
que irá dividir um
par de outros números,
138
00:05:57,720 --> 00:05:59,680
sem deixar um resto.
139
00:05:59,960 --> 00:06:03,760
Então, nesse caso,
4 divide tanto 8 quanto 12,
140
00:06:03,760 --> 00:06:05,360
sem deixar resto.
141
00:06:05,600 --> 00:06:08,320
É simples encontrá-lo
com números pequenos,
142
00:06:08,320 --> 00:06:11,200
mas bem mais difícil
para números grandes.
143
00:06:12,000 --> 00:06:15,200
Embora Euclides seja o maior
matemático de seu tempo,
144
00:06:15,200 --> 00:06:17,640
seu algoritmo poderia ter
lhe rendido uma fortuna...
145
00:06:17,640 --> 00:06:19,080
...como telhador.
146
00:06:19,560 --> 00:06:21,640
Eu vou lhe mostrar o porquê.
147
00:06:22,560 --> 00:06:25,600
Imagine que você tenha
um piso retangular,
148
00:06:25,600 --> 00:06:27,520
e você quer descobrir
a forma mais eficiente
149
00:06:27,520 --> 00:06:30,120
de ladrilhá-lo com
azulejos quadrados.
150
00:06:30,120 --> 00:06:31,080
Em outras palavras,
151
00:06:31,080 --> 00:06:33,120
qual é o maior
azulejo quadrado
152
00:06:33,120 --> 00:06:34,520
que irá dividir,
precisamente,
153
00:06:34,520 --> 00:06:37,840
as dimensões do piso,
sem que haja resto?
154
00:06:37,880 --> 00:06:40,360
Essa é, de fato,
uma versão geométrica
155
00:06:40,360 --> 00:06:42,800
do problema do Máximo
Divisor Comum.
156
00:06:42,960 --> 00:06:45,840
As dimensões do piso
são os dois números
157
00:06:45,840 --> 00:06:49,480
e o tamanho dos tijolos,
o que tentaremos descobrir,
158
00:06:49,480 --> 00:06:52,080
é o seu Máximo
Divisor Comum.
159
00:06:53,520 --> 00:06:55,680
Iremos acompanhar
o Algoritmo de Euclides
160
00:06:55,680 --> 00:06:56,840
passo a passo,
161
00:06:56,840 --> 00:06:58,240
para demonstrar
como ele é capaz
162
00:06:58,240 --> 00:07:00,640
de encontrar o azulejo
quadrado ideal
163
00:07:00,640 --> 00:07:01,840
para esse piso.
164
00:07:02,800 --> 00:07:04,760
De acordo com o
Algoritmo de Euclides,
165
00:07:04,760 --> 00:07:06,800
precisamos começar a
preencher o retângulo
166
00:07:06,800 --> 00:07:07,960
com azulejos quadrados
167
00:07:07,960 --> 00:07:11,120
correspondentes à menor
das duas dimensões.
168
00:07:13,600 --> 00:07:16,520
Essa é a primeira
etapa do trabalho.
169
00:07:17,000 --> 00:07:19,000
O Algoritmo de Euclides,
a seguir, nos diz
170
00:07:19,000 --> 00:07:20,920
para fazer exatamente
a mesma coisa, novamente,
171
00:07:20,920 --> 00:07:22,680
com esse retângulo.
172
00:07:23,720 --> 00:07:26,720
Em cada etapa,
o algoritmo nos diz
173
00:07:26,720 --> 00:07:28,480
para selecionar
azulejos quadrados
174
00:07:28,480 --> 00:07:31,880
correspondentes ao menor
lado do retângulo.
175
00:07:33,480 --> 00:07:35,600
Então, dessa vez,
nossos azulejos quadrados
176
00:07:35,600 --> 00:07:38,560
preenchem, perfeitamente,
o espaço restante.
177
00:07:38,560 --> 00:07:42,520
Bem, meu azulejo
quadrado mede 15x15.
178
00:07:42,520 --> 00:07:44,680
Então, o Algoritmo
de Euclides nos diz
179
00:07:44,680 --> 00:07:50,840
que o Máximo Divisor Comum
de 150 e 345 é 15.
180
00:07:52,720 --> 00:07:54,080
Eu não estou sugerindo
181
00:07:54,080 --> 00:07:55,480
que você use o
Algoritmo de Euclides
182
00:07:55,480 --> 00:07:58,040
toda vez que precisar
comprar azulejos,
183
00:07:58,040 --> 00:07:59,920
mas o incrível é que
184
00:07:59,920 --> 00:08:02,360
esse simples
método passo a passo
185
00:08:02,360 --> 00:08:04,520
encontra o azulejo
quadrado perfeito,
186
00:08:04,520 --> 00:08:07,200
não importa quais sejam
as dimensões do piso.
187
00:08:07,640 --> 00:08:08,920
O Algoritmo de Euclides
188
00:08:08,920 --> 00:08:11,880
pode parecer apenas
uma técnica matemática,
189
00:08:11,880 --> 00:08:13,760
mas ele preenche,
muito elegantemente,
190
00:08:13,760 --> 00:08:16,200
todos os critérios
para um algoritmo.
191
00:08:16,200 --> 00:08:19,440
É um conjunto precisamente
estabelecido de instruções,
192
00:08:19,440 --> 00:08:21,400
o procedimento sempre acaba,
193
00:08:21,400 --> 00:08:25,160
e pode-se provar que ele
funciona em todos os casos.
194
00:08:27,840 --> 00:08:30,440
O poder dos algoritmos
é que você não
195
00:08:30,440 --> 00:08:33,680
precisa reinventar
a roda o tempo todo.
196
00:08:33,680 --> 00:08:36,240
Eles são soluções gerais
para os problemas.
197
00:08:36,240 --> 00:08:38,800
Isso vale tanto para
algoritmos antigos
198
00:08:38,800 --> 00:08:40,840
quanto para os modernos.
199
00:08:44,800 --> 00:08:47,320
Em 1998, nessa garagem,
200
00:08:47,320 --> 00:08:50,640
em Menlo Park, Califórnia,
uma parte importante
201
00:08:50,640 --> 00:08:52,880
da história dos
algoritmos foi feita.
202
00:08:53,880 --> 00:08:55,880
Aqui dentro,
havia dois estudantes
203
00:08:55,880 --> 00:08:58,280
de PhD da Universidade
de Stamford.
204
00:08:58,280 --> 00:09:01,200
Larry Page e Sergey Brin.
205
00:09:02,120 --> 00:09:04,840
Seu objetivo era criar
um mecanismo de busca
206
00:09:04,840 --> 00:09:06,680
que pudesse encontrar
coisas, de modo eficiente,
207
00:09:06,680 --> 00:09:08,560
na Rede Mundial de
Computadores (WWB).
208
00:09:10,720 --> 00:09:14,560
Emergindo desse início
humilde, nascia o Google.
209
00:09:15,040 --> 00:09:16,920
Mas o Google não
seria o Google,
210
00:09:16,920 --> 00:09:18,560
se não fosse graças
a um algoritmo
211
00:09:18,560 --> 00:09:22,400
que Larry e Sergey criaram,
chamado PageRank.
212
00:09:30,760 --> 00:09:33,200
O PageRank era o
algoritmo no centro
213
00:09:33,200 --> 00:09:37,080
da primeira encarnação do
motor de buscas do Google.
214
00:09:37,080 --> 00:09:39,680
Bem, tecnicamente, não é
um algoritmo de buscas,
215
00:09:39,680 --> 00:09:41,840
mas um algoritmo
de ranking.
216
00:09:42,000 --> 00:09:43,920
Então, quando você
digita um termo
217
00:09:43,920 --> 00:09:45,600
em um motor de buscas,
218
00:09:45,600 --> 00:09:47,520
há, literalmente,
milhões de páginas
219
00:09:47,520 --> 00:09:49,560
que se adequarão
a esse termo.
220
00:09:49,560 --> 00:09:52,920
O que o PageRank faz é
rankear todas essas páginas,
221
00:09:52,920 --> 00:09:54,480
de modo que a página no topo
222
00:09:54,480 --> 00:09:56,080
seja aquela em que
você, provavelmente,
223
00:09:56,080 --> 00:09:57,640
estará mais interessado.
224
00:09:58,440 --> 00:09:59,520
Larry e Sergey
225
00:09:59,520 --> 00:10:01,600
surgiram com a idéia
de fazer o PageRank,
226
00:10:01,600 --> 00:10:03,360
e de usá-lo como um
indicador de ranking
227
00:10:03,360 --> 00:10:05,720
para melhorar a qualidade
das buscas na web.
228
00:10:05,720 --> 00:10:07,440
Eu me lembro de, na época,
229
00:10:07,440 --> 00:10:10,320
usar um motor de buscas
web, como o AltaVista.
230
00:10:10,560 --> 00:10:12,760
Você precisava clicar no
link "Próxima Página"
231
00:10:12,760 --> 00:10:13,800
um bocado de vezes
para encontrar
232
00:10:13,800 --> 00:10:14,800
o que você estava buscando.
233
00:10:14,800 --> 00:10:16,360
O PageRank foi uma
das razões pela qual
234
00:10:16,360 --> 00:10:17,880
o Google se saiu bem melhor
235
00:10:17,880 --> 00:10:20,720
do que os motores de busca
existentes na época.
236
00:10:21,720 --> 00:10:23,720
O funcionamento
interno do PageRank
237
00:10:23,720 --> 00:10:26,360
fica oculto na Rede Mundial
de Computadores.
238
00:10:26,360 --> 00:10:28,960
Assim, para revelar
como ele faz seu trabalho,
239
00:10:28,960 --> 00:10:30,880
nós iremos usar o
Algoritmo do PageRank
240
00:10:30,880 --> 00:10:34,000
para rankear os jogadores
de uma equipe de futebol.
241
00:10:34,400 --> 00:10:36,840
O PageRank examina
duas coisas.
242
00:10:36,840 --> 00:10:40,200
Ele examina os links de
entrada para a página web,
243
00:10:40,200 --> 00:10:43,240
ou seja, as outras páginas
com link para a página,
244
00:10:43,240 --> 00:10:46,960
e examina o quão importantes
são essas páginas.
245
00:10:51,560 --> 00:10:52,880
Em nossa demonstração
246
00:10:52,880 --> 00:10:55,600
para exibir a inteligência
do algoritmo do PageRank,
247
00:10:55,600 --> 00:10:57,360
os jogadores da
equipe de futebol
248
00:10:57,360 --> 00:10:59,000
são as páginas web
249
00:10:59,440 --> 00:11:02,840
e os passes entre eles
são os links web -
250
00:11:02,840 --> 00:11:04,920
a entrada do algoritmo.
251
00:11:05,600 --> 00:11:08,080
A grosso modo,
o algoritmo do PageRank
252
00:11:08,080 --> 00:11:10,360
irá atribuir uma posição
maior a uma página web,
253
00:11:10,360 --> 00:11:13,120
caso ela tenha vários links
vindos de outras páginas.
254
00:11:13,120 --> 00:11:14,560
Assim, no caso do futebol,
255
00:11:14,560 --> 00:11:16,400
se um jogador
receber mais passes
256
00:11:16,400 --> 00:11:17,320
do restante de sua equipe,
257
00:11:17,320 --> 00:11:19,200
então, estará mais
alto no ranking.
258
00:11:19,880 --> 00:11:21,600
Não é assim tão simples,
259
00:11:21,600 --> 00:11:23,800
porque o algoritmo do
PageRank, na verdade,
260
00:11:23,800 --> 00:11:26,200
atribui um peso maior
a um link de um website
261
00:11:26,200 --> 00:11:28,840
que tenha, ele próprio, uma
página de ranking elevado.
262
00:11:28,840 --> 00:11:31,160
Então, na verdade, o passo
de um jogador popular
263
00:11:31,160 --> 00:11:32,880
vale mais do que um passe
264
00:11:32,880 --> 00:11:35,600
de um jogador que esteja
pouco envolvido no jogo.
265
00:11:36,880 --> 00:11:40,520
Essa é uma amostra
do algoritmo em ação.
266
00:11:40,720 --> 00:11:43,440
Os status são o ranking
atual dos jogadores -
267
00:11:43,440 --> 00:11:45,280
a saída do algoritmo.
268
00:11:45,920 --> 00:11:47,840
E toda vez que há um passe,
269
00:11:47,840 --> 00:11:50,080
esses rankings
são atualizados.
270
00:11:50,560 --> 00:11:52,680
Quando o Google
usa esse algoritmo,
271
00:11:52,680 --> 00:11:56,080
ele altera apenas
uma coisa - a entrada.
272
00:11:56,080 --> 00:11:59,800
Ao invés dos passes,
ele usa links web.
273
00:12:01,080 --> 00:12:02,840
Note que a importância
de uma página
274
00:12:02,840 --> 00:12:06,120
depende da importância das
páginas que se ligam a ela.
275
00:12:06,440 --> 00:12:08,200
Isso significa que
você precisa computar
276
00:12:08,200 --> 00:12:10,640
o PageRank para todas as
páginas ao mesmo tempo.
277
00:12:10,960 --> 00:12:13,120
E você, de fato, precisa
repetir esses cálculos,
278
00:12:13,120 --> 00:12:14,960
porque, a cada vez,
você atualiza
279
00:12:14,960 --> 00:12:16,760
a importância
de todas as páginas.
280
00:12:16,760 --> 00:12:19,000
E isso, por sua vez,
irá influenciar
281
00:12:19,000 --> 00:12:20,240
a importância das páginas
282
00:12:20,240 --> 00:12:21,960
a quem essas
páginas se conectam.
283
00:12:30,520 --> 00:12:34,120
No final do jogo, o trabalho
do algoritmo está feito.
284
00:12:36,440 --> 00:12:39,760
Se quisermos procurar
o jogador chave da equipe,
285
00:12:39,760 --> 00:12:42,360
essa é a resposta do PageRank.
286
00:12:43,120 --> 00:12:47,120
O Jogador 11 tem a pontuação
mais alta no PageRank.
287
00:12:48,200 --> 00:12:50,000
Eu acho que o
Algoritmo do PageRank
288
00:12:50,000 --> 00:12:52,960
é, provavelmente,
meu algoritmo predileto.
289
00:12:53,000 --> 00:12:54,400
E é incrível que
ele possa ser aplicado
290
00:12:54,400 --> 00:12:55,960
não apenas à Rede
Mundial de Computadores,
291
00:12:55,960 --> 00:12:58,360
mas, também, à análise
de uma partida de futebol.
292
00:12:58,360 --> 00:12:59,800
Mas, para mim, é
o fato de existir
293
00:12:59,800 --> 00:13:02,400
uma bela peça matemática
em sua essência,
294
00:13:02,400 --> 00:13:03,840
a qual sempre
parece encontrar
295
00:13:03,840 --> 00:13:05,920
a página web que
estou procurando.
296
00:13:08,360 --> 00:13:09,320
Dentro da Google, eu acho,
297
00:13:09,320 --> 00:13:12,120
o PageRank é visto como
uma parte muito importante
298
00:13:12,120 --> 00:13:14,520
do desenvolvimento
inicial da Google.
299
00:13:15,400 --> 00:13:18,200
O PageRank era a razão do
porquê o motor de buscas
300
00:13:18,200 --> 00:13:20,880
que Larry e Sergey
construíram nos anos 1990
301
00:13:20,880 --> 00:13:22,640
foi tão exitoso.
302
00:13:23,120 --> 00:13:25,200
Atualmente, o Google
lida com mais de
303
00:13:25,200 --> 00:13:28,600
3.5 bilhões de
pesquisas diárias.
304
00:13:28,600 --> 00:13:31,560
É o motor de buscas
mais famoso do mundo.
305
00:13:31,560 --> 00:13:36,680
E a empresa vale mais
de US$450 bilhões.
306
00:13:37,200 --> 00:13:39,560
Nada mau para dois
estudantes de PhD
307
00:13:39,560 --> 00:13:41,520
trabalhando em uma garagem.
308
00:13:48,640 --> 00:13:52,520
Algoritmos são simples
receitas passo a passo.
309
00:13:52,520 --> 00:13:53,800
Inventá-los requer uma
310
00:13:53,800 --> 00:13:56,640
incrível criatividade
e genialidade.
311
00:13:56,640 --> 00:14:00,160
Mas usá-los é só uma
questão de seguir instruções.
312
00:14:00,760 --> 00:14:02,560
E é por isso que algoritmos
313
00:14:02,560 --> 00:14:05,000
são perfeitos
para computadores.
314
00:14:07,960 --> 00:14:10,080
Computadores são
apenas máquinas.
315
00:14:10,080 --> 00:14:12,000
Eles simplesmente fazem
tarefas repetitivas
316
00:14:12,000 --> 00:14:14,040
a velocidades fenomenais.
317
00:14:14,040 --> 00:14:15,480
Velocidades inacreditáveis.
318
00:14:15,480 --> 00:14:17,600
Então, eles são
absolutamente perfeitos
319
00:14:17,600 --> 00:14:20,080
para desempenhar essas
tarefas repetitivas,
320
00:14:20,080 --> 00:14:23,000
as quais são
claramente definidas
321
00:14:23,000 --> 00:14:25,000
e que podem ser feitas
322
00:14:25,000 --> 00:14:27,800
em uma quantidade
finita de tempo.
323
00:14:28,960 --> 00:14:30,360
O código do computador
está, basicamente,
324
00:14:30,360 --> 00:14:32,040
construindo um
algoritmo específico.
325
00:14:32,040 --> 00:14:33,760
Então, o algoritmo
é o tipo da idéia:
326
00:14:33,760 --> 00:14:35,160
"Como resolver o problema?"
327
00:14:35,160 --> 00:14:37,400
Essas são as instruções
que você usaria.
328
00:14:37,400 --> 00:14:39,160
E, então, isso pode
ser traduzido
329
00:14:39,160 --> 00:14:40,800
em um determinado código.
330
00:14:43,200 --> 00:14:45,080
Diversos tipos de algoritmos
331
00:14:45,080 --> 00:14:48,040
têm sido criados com
o computador em mente.
332
00:14:49,680 --> 00:14:51,280
E alguns dos
mais importantes
333
00:14:51,280 --> 00:14:53,840
são algoritmos de ordenação.
334
00:14:54,480 --> 00:14:56,520
Bem, a tarefa de um
algoritmo de ordenação
335
00:14:56,520 --> 00:14:58,800
é pôr as coisas em ordem.
336
00:14:58,800 --> 00:15:00,680
E eles têm uma
inifinidade de usos.
337
00:15:00,680 --> 00:15:02,560
Por exemplo, na Internet,
338
00:15:02,560 --> 00:15:06,200
a informação é quebrada
em pacotes de dados,
339
00:15:06,200 --> 00:15:08,560
os quais são, então,
enviados através da web.
340
00:15:08,560 --> 00:15:11,080
Bem, para reconstruir esse dado,
341
00:15:11,080 --> 00:15:13,520
algoritmos de ordenação são
absolutamente cruciais
342
00:15:13,520 --> 00:15:16,640
para realocar esses dados
na ordem correta,
343
00:15:16,640 --> 00:15:18,520
de modo que possamos
visualizar a imagem,
344
00:15:18,520 --> 00:15:21,160
ou ler o e-mail
que acabamos de enviar.
345
00:15:25,880 --> 00:15:28,680
Essa é a Corporação de
Desenvolvimento de Sistemas,
346
00:15:28,680 --> 00:15:30,080
na Califórnia.
347
00:15:30,360 --> 00:15:32,480
Ela é considerada a
primeira empresa mundial
348
00:15:32,480 --> 00:15:34,400
de softwares de computador.
349
00:15:35,440 --> 00:15:37,760
E foi aqui, em 1963,
350
00:15:37,760 --> 00:15:39,560
que dois cientistas
da computação
351
00:15:39,560 --> 00:15:41,320
escreveram, formalmente,
pela primeira vez,
352
00:15:41,320 --> 00:15:45,040
um dos algoritmos de ordenação
mais icônicos da história.
353
00:15:47,880 --> 00:15:50,440
Ele é chamado Bubblesort.
354
00:15:50,560 --> 00:15:53,680
E aqui temos um exemplo
do Bubblesort em ação,
355
00:15:53,680 --> 00:15:56,320
ordenando blocos,
ao invés de números.
356
00:15:57,440 --> 00:16:01,040
Ele recebe esse nome porque,
a cada iteração do algoritmo,
357
00:16:01,040 --> 00:16:03,200
os maiores objetos
desordenados
358
00:16:03,200 --> 00:16:05,040
trafegam até o topo.
359
00:16:05,040 --> 00:16:07,200
Como todos os
algoritmos até o momento,
360
00:16:07,200 --> 00:16:09,680
há um método na loucura.
361
00:16:14,480 --> 00:16:16,560
Para ver como esse
algoritmo funciona,
362
00:16:16,560 --> 00:16:19,640
nós iremos usá-lo para
ordenar oito objetos.
363
00:16:20,300 --> 00:16:21,960
O algoritmo Bubblesort
364
00:16:21,960 --> 00:16:24,480
diz para considerarmos
os objetos em pares
365
00:16:24,480 --> 00:16:25,920
e para os trocarmos,
366
00:16:25,920 --> 00:16:27,400
caso eles estejam
na ordem errada.
367
00:16:27,400 --> 00:16:29,160
Então, nós iremos
começar nessa ponta
368
00:16:29,160 --> 00:16:31,240
e prosseguir até o topo.
369
00:16:31,560 --> 00:16:33,120
Então, eu considero
esses dois -
370
00:16:33,120 --> 00:16:35,720
eles estão na ordem errada,
então, eu os troco.
371
00:16:37,440 --> 00:16:40,000
Consideremos o próximo par -
eles estão na ordem certa,
372
00:16:40,000 --> 00:16:41,640
então, eu os deixo
como eles estão.
373
00:16:42,040 --> 00:16:43,360
Consideremos esse par -
374
00:16:43,360 --> 00:16:45,840
eles estão na ordem errada,
então, eu os troco.
375
00:16:48,560 --> 00:16:50,880
E seguimos fazendo isso.
376
00:16:57,960 --> 00:16:59,600
Agora, o algoritmo Bubblesort
377
00:16:59,600 --> 00:17:01,560
diz para retornarmos
até o começo
378
00:17:01,560 --> 00:17:04,080
e repetir o processo
continuamente,
379
00:17:04,080 --> 00:17:06,400
até que os objetos
estejam em ordem.
380
00:17:19,640 --> 00:17:21,320
O algoritmo pára quando
381
00:17:21,320 --> 00:17:23,880
não há mais pares
a serem trocados.
382
00:17:24,000 --> 00:17:25,800
Assim, o algoritmo Bubblesort
383
00:17:25,800 --> 00:17:27,600
fez, exitosamente,
seu trabalho.
384
00:17:27,600 --> 00:17:30,680
Eu, agora, tenho os objetos
perfeitamente ordenados,
385
00:17:30,680 --> 00:17:32,920
de acordo com uma
ordem crescente.
386
00:17:34,040 --> 00:17:37,520
O Bubblesort é, elegante,
simples e direto.
387
00:17:37,520 --> 00:17:40,040
Mas se a escala da tarefa
de ordenação for grande -
388
00:17:40,040 --> 00:17:42,680
como organizar vastos
conjuntos de dados -
389
00:17:42,840 --> 00:17:45,240
então, há algoritmos de
ordenação melhores
390
00:17:45,240 --> 00:17:46,600
para o trabalho.
391
00:17:50,440 --> 00:17:54,080
Esse é John von Neumann,
o gênio científico
392
00:17:54,080 --> 00:17:56,480
que ajudou a desenvolver
o computador moderno,
393
00:17:56,480 --> 00:17:58,600
a Teoria dos Jogos,
a Bomba Atômica
394
00:17:58,600 --> 00:18:00,480
e, como iremos mostrar,
395
00:18:00,480 --> 00:18:02,960
inventou um
algoritmo de ordenação.
396
00:18:04,440 --> 00:18:06,600
Ele o projetou para
trabalhar com isso:
397
00:18:06,600 --> 00:18:09,520
um dos primeiros computadores
eletrônicos do mundo,
398
00:18:09,520 --> 00:18:11,600
o qual ele ajudou a projetar.
399
00:18:11,720 --> 00:18:14,840
O algoritmo é chamado
Mergesort.
400
00:18:16,440 --> 00:18:19,120
O Algoritmo Mergesort
funciona com o princípio
401
00:18:19,120 --> 00:18:21,000
de dividir para conquistar.
402
00:18:21,000 --> 00:18:23,680
E ele consiste em duas partes.
403
00:18:23,680 --> 00:18:26,520
A primeira é
a parte da divisão.
404
00:18:28,360 --> 00:18:32,040
Isso envolve dividir
tudo em grupos menores.
405
00:18:35,560 --> 00:18:38,360
E, agora, vem a
parte da conquista.
406
00:18:40,440 --> 00:18:43,280
Os grupos são, agora,
recombinados.
407
00:18:43,360 --> 00:18:45,440
Mas conforme eu
recombino os dois grupos,
408
00:18:45,440 --> 00:18:47,560
eu comparo os
tamanhos dos objetos,
409
00:18:47,560 --> 00:18:49,000
um par por vez,
410
00:18:49,000 --> 00:18:52,000
de modo que o grupo
combinado fique ordenado.
411
00:19:00,040 --> 00:19:01,720
Bem, o Algoritmo Mergesort
412
00:19:01,720 --> 00:19:04,120
pode parecer bem
semelhante ao Bubblesort,
413
00:19:04,120 --> 00:19:06,120
mas seu diferencial é que,
414
00:19:06,120 --> 00:19:08,160
com um grupo de
objetos bem maior,
415
00:19:08,160 --> 00:19:10,480
ele é muito,
muito mais rápido.
416
00:19:10,560 --> 00:19:12,520
Vejamos como o Mergesort
417
00:19:12,520 --> 00:19:15,360
se compara, em velocidade,
ao Bubblesort.
418
00:19:15,360 --> 00:19:19,080
É hora de uma batalha
de algoritmos!
419
00:19:21,560 --> 00:19:24,000
Aqui, vemos o
Bubblesort, na base,
420
00:19:24,000 --> 00:19:25,880
e o Mergesort, no topo.
421
00:19:25,880 --> 00:19:28,640
E nós os fizemos
ordenar 1.000 objetos.
422
00:19:28,640 --> 00:19:29,800
Bem, apesar de ambos
423
00:19:29,800 --> 00:19:31,880
gerarem o mesmo
resultado final,
424
00:19:31,880 --> 00:19:33,600
você já consegue ver
que o Mergesort
425
00:19:33,600 --> 00:19:35,400
está indo mais rápido.
426
00:19:35,640 --> 00:19:37,400
E essa diferença
na performance
427
00:19:37,400 --> 00:19:38,800
fica bem mais acentuada,
428
00:19:38,800 --> 00:19:41,720
conforme aumenta o número
de objetos a ordenar.
429
00:19:49,160 --> 00:19:51,280
Qual é a forma mais
eficiente de se ordenar
430
00:19:51,280 --> 00:19:53,720
um milhão de
inteiros de 32 bits?
431
00:19:57,400 --> 00:19:58,800
Bem, eu...
432
00:19:59,440 --> 00:20:02,800
- Desculpe, talvez...
- Não, não, não, não, não.
433
00:20:02,800 --> 00:20:05,320
Eu acho que... Eu acho...
434
00:20:05,520 --> 00:20:09,040
Eu acho que o Bubblesort
não seria a escolha certa.
435
00:20:12,040 --> 00:20:15,240
Fala sério!
Quem soprou pra ele?
436
00:20:22,240 --> 00:20:25,120
O Mergesort vence
claramente o Bubblesort,
437
00:20:25,120 --> 00:20:27,600
ao ordenar enormes
quantidades de dados.
438
00:20:28,440 --> 00:20:30,640
Mas no mundo louco
dos algoritmos,
439
00:20:30,640 --> 00:20:33,680
há muitas, muitas formas
diferentes de se ordenar.
440
00:20:36,560 --> 00:20:37,760
Na última contagem,
441
00:20:37,760 --> 00:20:39,720
havia mais de 20
tipos diferentes
442
00:20:39,720 --> 00:20:41,560
de algoritmos de ordenação.
443
00:20:42,800 --> 00:20:45,200
Todos estranhamente
obtendo o mesmo resultado,
444
00:20:45,200 --> 00:20:47,400
mas por meios diferentes.
445
00:20:58,160 --> 00:21:01,040
Há o Bubblesort,
há o Mergesort.
446
00:21:01,040 --> 00:21:02,320
O Insertion sort.
447
00:21:02,320 --> 00:21:04,560
Há o Heapsort,
há o Quicksort.
448
00:21:04,560 --> 00:21:06,040
O Timsort.
449
00:21:06,360 --> 00:21:07,800
Há o gnome sort.
450
00:21:07,800 --> 00:21:09,240
Há o pigeonhole sort,
451
00:21:09,240 --> 00:21:10,960
que também é chamado
de radix sort.
452
00:21:10,960 --> 00:21:13,720
Há o bogosort,
o qual pode não ter fim.
453
00:21:19,120 --> 00:21:22,680
Não existe isso de "o melhor
algoritmo de ordenação".
454
00:21:23,160 --> 00:21:26,040
Cada um tem seus
prós e contras.
455
00:21:26,520 --> 00:21:28,280
E aquele que será usado
456
00:21:28,280 --> 00:21:31,320
muitas vezes depende das
especificidades do problema.
457
00:21:32,300 --> 00:21:34,800
Eu acho que a beleza
de estudar algoritmos
458
00:21:34,800 --> 00:21:37,480
é tentar buscar soluções
459
00:21:37,480 --> 00:21:40,600
que sejam o mais elegantes
e eficazes possível.
460
00:21:40,600 --> 00:21:43,600
Eu, pessoalmente, acho o
Bubblesort bem legal.
461
00:21:43,600 --> 00:21:46,440
Eu gosto dele.
O Mergesort é lindo.
462
00:21:49,200 --> 00:21:51,680
Nós não conseguiríamos
viver sem eles.
463
00:21:51,720 --> 00:21:55,520
Algoritmos de ordenação
trazem ordem ao mundo.
464
00:22:05,120 --> 00:22:06,920
Até agora,
nós vimos algoritmos
465
00:22:06,920 --> 00:22:08,520
que atacam
problemas pequenos,
466
00:22:08,520 --> 00:22:10,400
como dimensionar
azulejos de banheiro
467
00:22:10,400 --> 00:22:12,160
e organizar nossos dados.
468
00:22:12,800 --> 00:22:14,480
Mas como será que se saem
469
00:22:14,480 --> 00:22:17,040
com o complicado
mundo do amor?
470
00:22:17,880 --> 00:22:20,720
Encontros online são bem
populares, atualmente.
471
00:22:20,720 --> 00:22:23,560
De fato, uma pesquisa
sugere que mais de 1/3
472
00:22:23,560 --> 00:22:26,760
dos casamentos recentes
começou online.
473
00:22:27,640 --> 00:22:29,600
A forma como esses sites
de encontro funcionam
474
00:22:29,600 --> 00:22:32,760
é usando algo chamado
Algoritmo de Emparelhamento.
475
00:22:32,760 --> 00:22:34,720
Eles vasculham os perfis,
476
00:22:34,720 --> 00:22:35,800
tentando emparelhar
as pessoas
477
00:22:35,800 --> 00:22:37,960
de acordo com seus
gostos e aversões,
478
00:22:37,960 --> 00:22:39,920
traços de personalidade,
e assim por diante.
479
00:22:39,920 --> 00:22:41,400
Na verdade, os algoritmos
480
00:22:41,400 --> 00:22:43,080
parecem ser melhores
do que os humanos,
481
00:22:43,080 --> 00:22:44,600
porque pesquisas recentes
482
00:22:44,600 --> 00:22:46,600
mostraram que aqueles
que se encontram online
483
00:22:46,600 --> 00:22:47,760
tendem a ser mais felizes
484
00:22:47,760 --> 00:22:49,720
e a terem casamentos
mais duradouros.
485
00:22:52,080 --> 00:22:54,480
Agora, peço que vocês
recebam seus prêmios
486
00:22:54,480 --> 00:22:56,480
da Sua Majestade, o Rei.
487
00:22:56,840 --> 00:22:58,680
De fato, algoritmos
de emparelhamento
488
00:22:58,680 --> 00:23:00,960
têm muito para se gabar,
489
00:23:00,960 --> 00:23:03,960
porque em 2012,
pela primeira vez,
490
00:23:03,960 --> 00:23:07,720
um Prêmio Nobel foi concedido
graças a um algoritmo.
491
00:23:07,720 --> 00:23:09,200
Um algoritmo
de emparelhamento,
492
00:23:09,200 --> 00:23:11,680
criado pelo economista
David Gale
493
00:23:11,680 --> 00:23:13,560
e pelo matemático
Lloyd Shapley,
494
00:23:13,560 --> 00:23:16,720
vistos aqui, recebendo
sua parte do prêmio.
495
00:23:19,300 --> 00:23:22,000
A história começa
nos anos 1960,
496
00:23:22,000 --> 00:23:24,000
quando Gale e Shapley
queriam resolver
497
00:23:24,000 --> 00:23:27,280
um problema relacionado
a admissões na faculdade.
498
00:23:27,720 --> 00:23:30,160
Como emparelhar
estudantes e colégios,
499
00:23:30,160 --> 00:23:32,320
de modo que todos
tivessem um lugar?
500
00:23:32,800 --> 00:23:35,080
Porém, mais importante,
que ficassem felizes,
501
00:23:35,080 --> 00:23:37,920
ainda que não ficassem
com sua primeira escolha.
502
00:23:40,160 --> 00:23:43,600
Eles o chamaram de Problema
do Emparelhamento Estável.
503
00:23:43,840 --> 00:23:46,520
O Problema do Emparelhamento
Estável funciona assim:
504
00:23:46,520 --> 00:23:49,320
suponha que você tenha
4 mulheres e 4 homens,
505
00:23:49,320 --> 00:23:50,880
e eles querem se casar.
506
00:23:50,880 --> 00:23:54,000
Bem, eles se avaliaram,
conforme suas preferências.
507
00:23:54,000 --> 00:23:55,760
Então, por exemplo,
a Rainha de Copas, aqui -
508
00:23:55,760 --> 00:23:57,800
sua primeira escolha
é o Rei de Paus.
509
00:23:57,800 --> 00:23:59,840
Segunda escolha: Rei de Ouros,
510
00:23:59,840 --> 00:24:02,680
e sua última escolha
é o Rei de Copas.
511
00:24:02,760 --> 00:24:05,040
O desafio, aqui,
é bancar o cupido,
512
00:24:05,040 --> 00:24:06,760
e emparelhar reis e rainhas,
513
00:24:06,760 --> 00:24:08,560
de modo que cada um
tenha um parceiro,
514
00:24:08,560 --> 00:24:09,920
porém, mais importante:
515
00:24:09,920 --> 00:24:11,960
que os casamentos
sejam estáveis.
516
00:24:12,360 --> 00:24:14,480
Um casamento estável
significa que
517
00:24:14,480 --> 00:24:16,360
os reis e rainhas
não necessariamente
518
00:24:16,360 --> 00:24:18,160
ficarão com sua
primeira escolha,
519
00:24:18,160 --> 00:24:20,440
mas que eles terão
a melhor em oferta.
520
00:24:20,600 --> 00:24:23,280
Por exemplo, se eu
emparelhar o Rei de Copas
521
00:24:23,280 --> 00:24:24,600
com a Rainha de Copas,
522
00:24:24,840 --> 00:24:27,760
e o Rei de Espadas
com a Rainha de Espadas,
523
00:24:27,840 --> 00:24:31,200
esse seria um
casamento instável,
524
00:24:31,440 --> 00:24:34,880
porque o Rei de Espadas não
gosta da Rainha de Espadas.
525
00:24:34,880 --> 00:24:37,080
Ele preferiria
a Rainha de Copas.
526
00:24:37,960 --> 00:24:39,800
A Rainha de Copas,
por sua vez,
527
00:24:39,800 --> 00:24:41,760
não gosta do Rei de Copas.
528
00:24:41,880 --> 00:24:44,200
Ela preferiria
o Rei de Espadas.
529
00:24:44,600 --> 00:24:48,640
Então, esses dois irão ficar
juntos, nesse emparelhamento.
530
00:24:51,840 --> 00:24:53,240
Onde houver um problema,
531
00:24:53,240 --> 00:24:56,280
haverá um algoritmo
não muito atrás.
532
00:24:56,400 --> 00:24:58,880
Em 1962, Gale e Shapley
533
00:24:58,880 --> 00:25:02,200
surgiram com seu algoritmo
vencedor do Prêmio Nobel.
534
00:25:02,400 --> 00:25:05,680
Uma receita passo a passo
que sempre encontra
535
00:25:05,680 --> 00:25:08,400
emparelhamentos
perfeitamente estáveis.
536
00:25:09,160 --> 00:25:11,200
Então, na primeira
rodada do algoritmo,
537
00:25:11,200 --> 00:25:12,880
todas as rainhas
fazem propostas
538
00:25:12,880 --> 00:25:14,800
aos seus reis
de primeira escolha.
539
00:25:14,800 --> 00:25:16,120
Então, a Rainha de Espadas
540
00:25:16,120 --> 00:25:18,440
tem como primeira escolha
o Rei de Espadas.
541
00:25:18,440 --> 00:25:21,000
Ela se oferece
ao Rei de Espadas.
542
00:25:21,000 --> 00:25:22,760
A primeira escolha
da Rainha de Copas
543
00:25:22,760 --> 00:25:24,240
é o Rei de Paus,
544
00:25:24,240 --> 00:25:26,520
então, ela se oferece
ao Rei de Paus.
545
00:25:26,520 --> 00:25:28,120
A primeira escolha
da Rainha de Ouros
546
00:25:28,120 --> 00:25:29,720
é o Rei de Espadas.
547
00:25:30,200 --> 00:25:31,680
E a primeira escolha
da Rainha de Paus
548
00:25:31,680 --> 00:25:33,400
também é o Rei de Espadas.
549
00:25:33,400 --> 00:25:35,320
Então, o Rei de Espadas
parece ser o preferido
550
00:25:35,320 --> 00:25:36,960
dessa Corte Real.
551
00:25:37,440 --> 00:25:40,800
Bem, o Rei de Espadas
recebeu três propostas.
552
00:25:41,440 --> 00:25:44,480
Então, ele escolhe sua
rainha mais popular,
553
00:25:44,480 --> 00:25:46,560
que é, na verdade,
a Rainha de Ouros,
554
00:25:46,560 --> 00:25:49,160
e ele rejeita as outras duas.
555
00:25:51,160 --> 00:25:53,200
Então, temos dois
relacionamentos provisórios
556
00:25:53,200 --> 00:25:54,840
e duas rejeições.
557
00:25:55,520 --> 00:25:56,760
Nós, agora, removemos
558
00:25:56,760 --> 00:25:59,320
as primeiras escolhas
rejeitadas pelas rainhas.
559
00:25:59,320 --> 00:26:01,480
E é hora da segunda rodada.
560
00:26:02,440 --> 00:26:04,560
Então, a Rainha de Espadas
irá se oferecer
561
00:26:04,560 --> 00:26:06,400
ao Rei de Ouros.
562
00:26:06,720 --> 00:26:10,560
E a Rainha de Paus irá
se oferecer ao Rei de Paus.
563
00:26:11,440 --> 00:26:14,480
Mas, agora, o Rei de Paus
recebeu duas propostas,
564
00:26:14,480 --> 00:26:16,960
e ele, na verdade,
prefere a Rainha de Paus.
565
00:26:17,440 --> 00:26:19,640
Então, ele rejeita
a Rainha de Copas -
566
00:26:19,640 --> 00:26:20,840
seu relacionamento provisório
567
00:26:20,840 --> 00:26:22,560
da primeira rodada
do algoritmo -
568
00:26:22,640 --> 00:26:24,480
e nós precisamos
começar novamente.
569
00:26:25,880 --> 00:26:28,080
A cada rodada,
as rainhas rejeitadas
570
00:26:28,080 --> 00:26:30,920
se oferecem ao próximo
rei de sua lista.
571
00:26:31,280 --> 00:26:35,040
E os reis sempre irão
querer a melhor oferta.
572
00:26:35,520 --> 00:26:36,920
Nessa rodada do algoritmo,
573
00:26:36,920 --> 00:26:39,240
ela se oferece
ao Rei de Copas
574
00:26:39,880 --> 00:26:41,720
e, finalmente,
todos se emparelharam -
575
00:26:41,720 --> 00:26:43,360
um rei para cada rainha -
576
00:26:43,640 --> 00:26:46,440
e todos os casamentos
são estáveis.
577
00:26:49,000 --> 00:26:50,720
O Algoritmo de Gale-Shapley
578
00:26:50,720 --> 00:26:53,440
é, agora, usado
em todo o mundo.
579
00:26:53,440 --> 00:26:55,040
Na Dinamarca, para
emparelhar crianças
580
00:26:55,040 --> 00:26:56,680
e locais de creches.
581
00:26:56,720 --> 00:26:59,760
Na Hungria, para emparelhar
estudantes e escolas.
582
00:26:59,760 --> 00:27:03,240
Em Nova York, para alocar
rabinos em sinagogas.
583
00:27:03,320 --> 00:27:05,120
E na China,
Alemanha e Espanha,
584
00:27:05,120 --> 00:27:07,840
para emparelhar estudantes
com universidades.
585
00:27:10,240 --> 00:27:13,400
Enquanto isso, no Reino Unido,
ele levou ao desenvolvimento
586
00:27:13,400 --> 00:27:15,000
de um algoritmo
de emparelhamento que,
587
00:27:15,000 --> 00:27:18,640
para algumas pessoas,
salvou suas vidas.
588
00:27:22,840 --> 00:27:26,120
Aos 20 anos, Seraya,
no sul de Londres,
589
00:27:26,120 --> 00:27:28,960
foi diagnosticada com
falência crônica renal,
590
00:27:28,960 --> 00:27:31,440
e disseram-lhe que
precisava de um transplante.
591
00:27:32,800 --> 00:27:35,720
Eu fiquei na hemodiálise
durante 18 meses,
592
00:27:35,720 --> 00:27:36,840
e estava muito mal.
593
00:27:36,840 --> 00:27:40,160
Eu não conseguia trabalhar.
Não tinha vida social.
594
00:27:40,160 --> 00:27:41,480
Era, literalmente, hospital -
595
00:27:41,480 --> 00:27:44,040
três vezes por semana,
para tratamento - e casa.
596
00:27:45,320 --> 00:27:48,000
Um amigo íntimo
se dispôs a doar,
597
00:27:48,000 --> 00:27:51,080
mas seus tipos de tecido
não eram compatíveis.
598
00:27:53,320 --> 00:27:56,000
Em St. Albans, Tamir
estava seriamente doente,
599
00:27:56,000 --> 00:27:58,640
e sua esposa, Lyndsey,
desejava doar.
600
00:27:58,640 --> 00:28:00,760
Mas eles tinham
o mesmo problema.
601
00:28:01,880 --> 00:28:03,240
Fizemos todos os
testes sanguíneos
602
00:28:03,240 --> 00:28:04,520
e todas as análises,
603
00:28:04,520 --> 00:28:06,320
e foi revelado
que nós tínhamos
604
00:28:06,320 --> 00:28:08,120
grupos sanguíneos
incompatíveis.
605
00:28:10,080 --> 00:28:11,800
Muitas vezes,
pacientes renais
606
00:28:11,800 --> 00:28:13,080
que têm sorte o bastante
607
00:28:13,080 --> 00:28:14,720
para encontrar
um voluntário doador
608
00:28:14,720 --> 00:28:16,160
descobrem que há
uma incompatibilidade
609
00:28:16,160 --> 00:28:19,240
com o grupo sanguíneo ou
tipo de tecido do doador.
610
00:28:20,600 --> 00:28:24,360
Mas desde 2007,
o NHS tem usado
611
00:28:24,360 --> 00:28:26,440
um algoritmo de
emparelhamento especial,
612
00:28:26,440 --> 00:28:28,200
para encontrar
doadores dispostos
613
00:28:28,200 --> 00:28:29,360
possivelmente compatíveis
614
00:28:29,360 --> 00:28:32,200
para pacientes renais
de todo o Reino Unido.
615
00:28:35,240 --> 00:28:37,400
Quando encaramos esse
problema pela 1ª vez,
616
00:28:37,400 --> 00:28:41,240
realmente subestimamos
a complexidade.
617
00:28:41,240 --> 00:28:42,520
E, inicialmente,
618
00:28:42,520 --> 00:28:46,120
começamos apenas com
trocas entre dois pares,
619
00:28:46,120 --> 00:28:47,920
então, era bem simples,
620
00:28:47,920 --> 00:28:50,400
mas logo ficou óbvio
621
00:28:50,400 --> 00:28:53,480
que precisávamos de
algo bem mais complexo.
622
00:28:56,720 --> 00:28:59,760
Eu entrei em contato com
Rachel Johnson, no NHS,
623
00:28:59,760 --> 00:29:02,240
e, na época, nós nos
envolvemos, então,
624
00:29:02,240 --> 00:29:03,640
em tentar projetar algoritmos
625
00:29:03,640 --> 00:29:05,440
que permitiriam não só
trocas entre pares,
626
00:29:05,440 --> 00:29:08,360
mas, também, trocas
entre três pares.
627
00:29:09,920 --> 00:29:13,120
O algoritmo considera
diversos cenários.
628
00:29:13,720 --> 00:29:16,080
O mais simples é uma
troca de duas vias,
629
00:29:16,080 --> 00:29:18,800
com dois pares
trocando rins.
630
00:29:21,360 --> 00:29:24,280
Uma troca de três
vias é mais complicada,
631
00:29:24,280 --> 00:29:27,120
onde os rins
circulam em ciclo.
632
00:29:29,560 --> 00:29:32,360
Há 200 pacientes
633
00:29:32,360 --> 00:29:34,800
em cada um de nossos testes
de emparelhamento.
634
00:29:35,120 --> 00:29:36,400
Precisamos examinar
635
00:29:36,400 --> 00:29:39,280
todos os transplantes
possíveis.
636
00:29:40,040 --> 00:29:42,360
E sua quantidade
é surpreendente.
637
00:29:42,360 --> 00:29:44,680
Há, literalmente,
centenas, às vezes,
638
00:29:44,680 --> 00:29:47,000
milhares de possibilidades.
639
00:29:47,240 --> 00:29:49,840
É algo que não
conseguiríamos obter
640
00:29:49,840 --> 00:29:51,640
sem o algoritmo.
641
00:29:52,960 --> 00:29:55,280
Certo dia, Seraya
recebeu uma ligação
642
00:29:55,280 --> 00:29:56,960
de que um doador
fora encontrado
643
00:29:56,960 --> 00:29:59,600
a 640 km de distância,
com Linda -
644
00:29:59,600 --> 00:30:02,640
uma doadora em Bowness,
próximo a Edimburgo.
645
00:30:03,040 --> 00:30:06,720
O pai de meu marido
precisava de um novo rim.
646
00:30:06,720 --> 00:30:08,440
Ele já estava doente
há um tempo,
647
00:30:08,440 --> 00:30:11,320
e eu não era compatível.
648
00:30:11,640 --> 00:30:13,640
E, então, eu recebi
uma ligação telefônica,
649
00:30:13,640 --> 00:30:17,320
e foi quando tudo começou.
650
00:30:18,600 --> 00:30:20,480
Recebemos uma primeira
ligação telefônica,
651
00:30:20,480 --> 00:30:21,880
dizendo que fôramos
emparelhados
652
00:30:21,880 --> 00:30:23,520
em uma rede de três vias.
653
00:30:24,080 --> 00:30:26,600
Você fica com receio
do que virá pela frente,
654
00:30:26,600 --> 00:30:28,720
porque sua vida depende disso.
655
00:30:29,840 --> 00:30:31,560
Para os casais emparelhados,
656
00:30:31,560 --> 00:30:34,720
todas as operações precisavam
ocorrer simultaneamente.
657
00:30:34,960 --> 00:30:38,200
Era um enorme
desafio logístico.
658
00:30:38,200 --> 00:30:40,960
Quando meu doador foi ao
hospital, ligaram para checar
659
00:30:40,960 --> 00:30:43,440
que meu doador também
estava em Newcastle,
660
00:30:43,440 --> 00:30:44,640
dirigindo-se
ao centro cirúrgico.
661
00:30:44,640 --> 00:30:46,560
E elas aconteceram
ao mesmo tempo.
662
00:30:46,720 --> 00:30:49,160
E eles fizeram a ligação
e o rim foi extraído.
663
00:30:49,160 --> 00:30:51,000
Eu acho que ele
foi de motocicleta.
664
00:30:51,080 --> 00:30:53,160
Avisaram-nos que ele
iria de helicóptero,
665
00:30:53,160 --> 00:30:53,880
então, eu achava que,
666
00:30:53,880 --> 00:30:56,680
ao menos uma parte minha
fora de helicóptero,
667
00:30:56,680 --> 00:30:59,160
mas, não, ela fora
de motocicleta.
668
00:31:02,800 --> 00:31:06,080
E, eventualmente, acabamos
fazendo, em dezembro.
669
00:31:06,240 --> 00:31:08,280
O melhor presente de Natal!
670
00:31:09,040 --> 00:31:12,560
Pessoalmente, fico imaginando
os médicos ali atrás,
671
00:31:12,560 --> 00:31:14,800
emparelhando pessoas
dessa lista.
672
00:31:14,800 --> 00:31:17,840
Então, resulta
um pouco estranho
673
00:31:17,840 --> 00:31:20,240
que, no fim das contas,
tudo se deva à Matemática.
674
00:31:20,240 --> 00:31:23,160
É uma grande rede,
e ela é bem recente.
675
00:31:23,600 --> 00:31:26,840
Muitos anos atrás,
eu não teria essa chance.
676
00:31:27,040 --> 00:31:28,960
Eu me sinto muito
grata a Linda
677
00:31:28,960 --> 00:31:30,800
e, também, ao algoritmo.
678
00:31:31,120 --> 00:31:33,040
Eu sou muito grata.
679
00:31:34,400 --> 00:31:37,200
Até agora,
mais de 400 pacientes
680
00:31:37,200 --> 00:31:39,640
se beneficiaram
da rede do NHS
681
00:31:39,640 --> 00:31:42,520
e de seu algoritmo de
emparelhamento especial.
682
00:31:42,520 --> 00:31:45,280
Foi só quando começamos
a ver artigos na imprensa
683
00:31:45,280 --> 00:31:46,800
e começamos,
de fato, a pensar:
684
00:31:46,800 --> 00:31:48,560
"Oh, espere aí: essa
pessoa deve, na verdade,
685
00:31:48,560 --> 00:31:52,760
ser aquela que emparelhamos
em outubro, em nossa troca"
686
00:31:52,760 --> 00:31:55,560
que você, de fato,
começa a ver as histórias
687
00:31:55,560 --> 00:31:57,440
que estão por trás
dos dados anônimos.
688
00:31:57,440 --> 00:32:00,200
É bem engraçado, porque
David sempre teme
689
00:32:00,200 --> 00:32:03,200
que o algoritmo levará
muito tempo para processar.
690
00:32:03,200 --> 00:32:07,240
E ele só leva uns 30 minutos,
mas ele já fica preocupado.
691
00:32:07,240 --> 00:32:09,760
Mas, veja bem, 30 minutos...
692
00:32:09,760 --> 00:32:14,200
...é incrível podermos fazer
tudo isso em 30 minutos.
693
00:32:24,760 --> 00:32:27,000
Até agora, nós vimos
como os algoritmos
694
00:32:27,000 --> 00:32:29,680
são capazes de
feitos impressionantes.
695
00:32:30,400 --> 00:32:33,400
De resolver problemas
matemáticos abstratos
696
00:32:33,400 --> 00:32:35,160
a nos ajudar
a encontrar coisas
697
00:32:35,160 --> 00:32:36,880
na Rede Mundial
de Computadores.
698
00:32:37,000 --> 00:32:41,600
E a chave de todos esses
algoritmos é sua velocidade.
699
00:32:41,960 --> 00:32:43,960
A característica importante
de um bom algoritmo
700
00:32:43,960 --> 00:32:45,680
é que, primeiro,
ele esteja correto,
701
00:32:45,680 --> 00:32:46,920
mas quando sabemos
que ele está correto,
702
00:32:46,920 --> 00:32:49,400
também é importante que
ele funcione rapidamente.
703
00:32:49,400 --> 00:32:51,040
Não é legal ter um algoritmo
704
00:32:51,040 --> 00:32:54,440
que leve uma vida
inteira para rodar,
705
00:32:54,440 --> 00:32:57,160
se você precisa desses
resultados para amanhã.
706
00:32:57,720 --> 00:32:59,760
Esse algoritmo de
detecção de rostos
707
00:32:59,760 --> 00:33:02,560
é um exemplo de um
algoritmo eficiente.
708
00:33:02,560 --> 00:33:03,880
Como ele é eficiente,
709
00:33:03,880 --> 00:33:05,760
ele é capaz de rodar
em tempo real.
710
00:33:05,760 --> 00:33:08,040
E é isso o que o torna útil.
711
00:33:09,300 --> 00:33:11,280
Mas tal como na vida real,
712
00:33:11,280 --> 00:33:13,880
alguns problemas são mais
difíceis do que outros.
713
00:33:14,240 --> 00:33:15,600
De vez em quando,
714
00:33:15,600 --> 00:33:18,320
os algoritmos encontram
um desafio à altura.
715
00:33:18,920 --> 00:33:21,960
Acho que o equívoco mais
comum sobre algoritmos
716
00:33:21,960 --> 00:33:24,600
é crer que os algoritmos
podem fazer tudo.
717
00:33:24,600 --> 00:33:26,960
Eu acho que as pessoas
não conhecem os limites.
718
00:33:26,960 --> 00:33:29,280
Alguns problemas simplesmente
não podem ser resolvidos
719
00:33:29,280 --> 00:33:31,160
por algoritmos eficientes.
720
00:33:32,480 --> 00:33:35,040
Há alguns locais aonde
algoritmos eficientes
721
00:33:35,040 --> 00:33:36,600
não conseguem ir.
722
00:33:36,760 --> 00:33:39,760
Linhas na areia que
não podem ser cruzadas.
723
00:33:40,200 --> 00:33:43,560
O problema é saber que
problemas podem resolver,
724
00:33:43,560 --> 00:33:45,160
e quais não podem.
725
00:33:48,000 --> 00:33:51,160
Pegue esse Cubo de Rubic
e pense no desafio bem comum
726
00:33:51,160 --> 00:33:53,880
de tentar resolver um cubo
de dimensões arbitrárias.
727
00:33:53,880 --> 00:33:57,160
Então, por exemplo, com
50 quadrados de cada lado.
728
00:33:57,160 --> 00:33:58,520
Bem, você acharia que esse
729
00:33:58,520 --> 00:34:01,440
seria um problema
daqueles bem difíceis,
730
00:34:01,440 --> 00:34:04,280
mas, na verdade, ele está
no campo dos fáceis.
731
00:34:04,280 --> 00:34:05,880
Nós conhecemos um algoritmo
732
00:34:05,880 --> 00:34:08,120
que consegue resolver
o cubo geral de Rubic
733
00:34:08,120 --> 00:34:10,200
em uma quantidade
razoável de tempo.
734
00:34:12,960 --> 00:34:14,640
Apesar de parecer difícil,
735
00:34:14,640 --> 00:34:16,360
esse problema pode
ser resolvido
736
00:34:16,360 --> 00:34:18,480
por algoritmos eficientes.
737
00:34:22,440 --> 00:34:25,760
No entanto, eis um que
definitivamente não pode.
738
00:34:27,280 --> 00:34:30,240
Imagine um tabuleiro
de tamanho qualquer,
739
00:34:30,240 --> 00:34:32,680
e uma disposição de
peças no tabuleiro.
740
00:34:32,680 --> 00:34:34,320
O desafio é descobrir
741
00:34:34,320 --> 00:34:37,880
se o branco pode vencer
a partir dessa posição.
742
00:34:37,880 --> 00:34:40,240
Bem, damas é
um jogo bem fácil,
743
00:34:40,240 --> 00:34:42,320
mas foi provado
matematicamente
744
00:34:42,320 --> 00:34:43,960
que não há um algoritmo
745
00:34:43,960 --> 00:34:46,480
que consiga resolver esse
problema eficientemente.
746
00:34:46,480 --> 00:34:49,400
É um problema
inerentemente difícil.
747
00:34:51,040 --> 00:34:53,280
A única forma de resolver
esse quebra-cabeça
748
00:34:53,280 --> 00:34:55,360
é através do trabalho duro -
749
00:34:55,360 --> 00:34:58,760
descobrindo todas as
milhões de possibilidades.
750
00:34:59,760 --> 00:35:01,800
Então, esse problema
encontra-se claramente
751
00:35:01,800 --> 00:35:04,640
além do alcance de
algoritmos eficientes.
752
00:35:04,640 --> 00:35:07,000
Ele não pode ser
resolvido rapidamente.
753
00:35:09,960 --> 00:35:11,320
Mas para alguns problemas,
754
00:35:11,320 --> 00:35:14,600
sua dificuldade
não fica tão clara.
755
00:35:14,600 --> 00:35:19,600
Esse é um enorme Sudoku.
Ele tem 625 quadrados.
756
00:35:20,200 --> 00:35:22,360
Uma das coisas
legais no Sudoku
757
00:35:22,360 --> 00:35:24,240
é que quando você
encontra uma solução,
758
00:35:24,240 --> 00:35:27,960
é relativamente fácil ver
se ela está certa, ou não.
759
00:35:27,960 --> 00:35:30,560
E isso é verdadeiro,
por maior que ele seja.
760
00:35:32,120 --> 00:35:34,760
Nesse caso, basta eu
checar que cada fileira,
761
00:35:34,760 --> 00:35:38,400
coluna e bloco não contenha
um número duas vezes.
762
00:35:38,400 --> 00:35:40,760
O Sudoku pertence a um
categoria bastante
763
00:35:40,760 --> 00:35:42,440
especial de problemas,
764
00:35:42,440 --> 00:35:44,640
onde todos partilham
dessa característica:
765
00:35:44,640 --> 00:35:46,720
quando você
encontra uma solução,
766
00:35:46,720 --> 00:35:49,160
é sempre fácil checá-la.
767
00:35:49,760 --> 00:35:52,800
O mistério é se existe
um algoritmo eficiente
768
00:35:52,800 --> 00:35:55,800
capaz de, antes de tudo,
encontrar uma solução.
769
00:35:58,080 --> 00:36:02,640
E o Sudoku não está sozinho.
Há diversos problemas assim.
770
00:36:02,960 --> 00:36:05,280
O mais intensamente
estudado de todos eles
771
00:36:05,280 --> 00:36:08,520
é conhecido como o Problema
do Caixeiro Viajante.
772
00:36:13,000 --> 00:36:15,720
Um caixeiro viajante
viaja de porta em porta,
773
00:36:15,720 --> 00:36:17,600
de cidade em cidade,
vendendo de tudo:
774
00:36:17,600 --> 00:36:20,680
de escovas e aspiradores
de pó a vidros reforçados.
775
00:36:22,360 --> 00:36:24,680
Isso parece uma
tarefa bem fácil.
776
00:36:25,160 --> 00:36:26,920
Mas todos os
caixeiros viajantes
777
00:36:26,920 --> 00:36:28,840
enfrentam o mesmo dilema:
778
00:36:29,400 --> 00:36:32,280
Qual será a rota mais curta?
779
00:36:33,400 --> 00:36:35,320
Esse problema é tão importante
780
00:36:35,320 --> 00:36:37,360
que o Instituto Clay
de Matemática
781
00:36:37,360 --> 00:36:39,480
ofereceu US$ 1 milhão
782
00:36:39,480 --> 00:36:42,240
para quem conseguir encontrar
um algoritmo eficiente,
783
00:36:42,240 --> 00:36:45,040
ou provar que
não existe nenhum.
784
00:36:46,280 --> 00:36:49,000
O problema do caixeiro
viajante é assim:
785
00:36:49,000 --> 00:36:50,680
Imagine que
você é um vendedor
786
00:36:50,680 --> 00:36:52,480
e você precisa visitar
uma lista de cidades,
787
00:36:52,480 --> 00:36:54,800
representadas pelos
pontos vermelhos.
788
00:36:55,000 --> 00:36:57,440
O desafio é encontrar
a rota mais curta,
789
00:36:57,440 --> 00:36:59,560
de modo a visitar cada
cidade uma única vez,
790
00:36:59,560 --> 00:37:02,120
antes de retornar
ao seu ponto de partida.
791
00:37:02,240 --> 00:37:04,120
Bem, você poderia imaginar
que a melhor solução
792
00:37:04,120 --> 00:37:07,680
é simplesmente considerar
todas as rotas - dessa forma...
793
00:37:13,560 --> 00:37:15,960
O método de checar
todas as possibilidades
794
00:37:15,960 --> 00:37:17,960
é um tipo de algoritmo.
795
00:37:18,200 --> 00:37:20,360
E para três cidades,
ele funciona bem,
796
00:37:20,360 --> 00:37:23,960
porque há apenas três
rotas possíveis a checar.
797
00:37:26,880 --> 00:37:30,240
Mas e se colocássemos mais
duas cidades na lista?
798
00:37:32,560 --> 00:37:34,000
Com cinco cidades,
799
00:37:34,000 --> 00:37:36,840
existem 60 rotas
possíveis diferentes.
800
00:37:39,040 --> 00:37:40,640
E se colocássemos
mais uma cidade,
801
00:37:40,640 --> 00:37:43,720
então, haveria
360 rotas possíveis.
802
00:37:43,840 --> 00:37:45,560
E para 10 cidades,
803
00:37:45,560 --> 00:37:49,480
existiriam mais de 1.8 milhão
de rotas possíveis.
804
00:37:49,680 --> 00:37:51,640
Se nosso algoritmo
considerasse todas,
805
00:37:51,640 --> 00:37:54,520
checando cada uma, a uma
taxa de 10 por segundo,
806
00:37:54,520 --> 00:37:58,120
ele levaria dois dias antes
de encontrar a mais curta.
807
00:37:58,320 --> 00:38:00,160
Então, perceba que
o método de tentar
808
00:38:00,160 --> 00:38:02,000
todas as diferentes
possibilidades -
809
00:38:02,000 --> 00:38:04,480
um tipo de algoritmo de
força bruta, por assim dizer -
810
00:38:04,480 --> 00:38:06,760
é simplesmente impraticável.
811
00:38:07,600 --> 00:38:09,240
Se alguém descobrisse
um algoritmo rápido
812
00:38:09,240 --> 00:38:10,200
para o problema do caixeiro,
813
00:38:10,200 --> 00:38:12,680
isso seria bem significativo.
814
00:38:12,960 --> 00:38:14,320
Se um de meus
estudantes surgisse
815
00:38:14,320 --> 00:38:15,760
com um algoritmo eficiente
816
00:38:15,760 --> 00:38:17,400
para o problema do
caixeiro viajante,
817
00:38:17,400 --> 00:38:20,240
eu pediria que ele
o explicasse para mim,
818
00:38:20,440 --> 00:38:23,840
eu o mataria e reivindicaria
819
00:38:23,840 --> 00:38:26,040
o prêmio Clay - US$1 milhão.
820
00:38:26,240 --> 00:38:28,440
Mas eu acho que meus
estudantes estão a salvo.
821
00:38:29,520 --> 00:38:32,440
O problema tem aplicações
em diversas áreas.
822
00:38:32,880 --> 00:38:35,160
Da soldagem em
placas de circuito...
823
00:38:36,880 --> 00:38:40,360
...ao planejamento de rotas
de entrega de supermercados.
824
00:38:40,560 --> 00:38:42,720
Mas será que o problema
do caixeiro viajante
825
00:38:42,720 --> 00:38:45,920
já foi secretamente resolvido?
826
00:38:49,560 --> 00:38:50,920
Uma equipe de cientistas
827
00:38:50,920 --> 00:38:53,760
trabalhando no Instituto
Rothamsted, em Harpenden,
828
00:38:53,760 --> 00:38:55,480
recorreu à Natureza,
829
00:38:55,480 --> 00:38:58,040
para ver se descobrem
a resposta.
830
00:39:02,880 --> 00:39:05,280
Eles estão realizando
um experimento complexo
831
00:39:05,280 --> 00:39:07,680
para estudar como o problema
do caixeiro viajante
832
00:39:07,680 --> 00:39:10,520
é abordado pelas abelhas.
833
00:39:13,160 --> 00:39:15,800
As abelhas precisam
procurar o néctar,
834
00:39:15,800 --> 00:39:17,560
para que abasteçam
sua colméia.
835
00:39:17,560 --> 00:39:20,640
E, assim, elas precisam
visitar, provavelmente,
836
00:39:20,640 --> 00:39:22,800
centenas de flores
em cada viagem.
837
00:39:22,800 --> 00:39:25,280
O que elas querem fazer é
encontrar uma forma eficiente
838
00:39:25,280 --> 00:39:28,320
de se locomover entre todas
essas flores que elas visitam.
839
00:39:31,200 --> 00:39:32,560
A modesta abelha
840
00:39:32,560 --> 00:39:35,480
enfrenta seu próprio problema
do caixeiro viajante.
841
00:39:35,760 --> 00:39:38,440
As flores são como as cidades.
842
00:39:38,440 --> 00:39:41,280
E a abelha é o
caixeiro viajante.
843
00:39:41,440 --> 00:39:45,600
Uma abelha irá vasculhar
diversas vezes por dia.
844
00:39:45,600 --> 00:39:47,080
Então, ao longo do dia,
845
00:39:47,080 --> 00:39:50,640
realmente compensa usar a
rota mais eficiente possível.
846
00:39:51,320 --> 00:39:53,320
Então, o que estamos fazendo
é tentar descobrir
847
00:39:53,320 --> 00:39:55,240
exatamente que regras
elas estão usando
848
00:39:55,240 --> 00:39:58,240
para limitar
as possibilidades.
849
00:39:59,960 --> 00:40:02,320
Joe colocou 5 alimentadores,
850
00:40:02,320 --> 00:40:04,600
os quais desempenham
o papel das flores.
851
00:40:05,080 --> 00:40:07,360
Cada alimentador tem
néctar o bastante
852
00:40:07,360 --> 00:40:10,160
para garantir que a abelha
precise visitar todos os 5,
853
00:40:10,160 --> 00:40:12,720
para que seu estômago
fique cheio de mel.
854
00:40:12,840 --> 00:40:16,280
E como você realmente sabe
para onde ela está indo?
855
00:40:16,280 --> 00:40:18,880
Para isso, estamos usando
um Radar Harmônico.
856
00:40:18,880 --> 00:40:20,440
Então, conforme ele gira,
857
00:40:20,440 --> 00:40:22,120
ele está emitindo
um sinal de radar.
858
00:40:22,120 --> 00:40:24,320
E nós prendemos
uma pequena antena
859
00:40:24,320 --> 00:40:25,320
nas costas da abelha,
860
00:40:25,320 --> 00:40:27,880
a qual, reflete, então,
o sinal do radar.
861
00:40:27,880 --> 00:40:30,040
E, assim, isso nos
permite ver, exatamente,
862
00:40:30,040 --> 00:40:31,200
para onde a abelha foi,
863
00:40:31,200 --> 00:40:32,960
conforme ela
se move pelo campo.
864
00:40:34,000 --> 00:40:36,440
Então, como será
que a abelha lida
865
00:40:36,440 --> 00:40:38,080
com o problema do
caixeiro viajante?
866
00:40:38,080 --> 00:40:40,200
- Pronto.
- Ok, vamos ligá-lo, agora.
867
00:40:46,720 --> 00:40:48,360
Com 5 alimentadores,
868
00:40:48,360 --> 00:40:51,560
existe um total de
60 rotas possíveis.
869
00:40:51,560 --> 00:40:55,000
O caminho mais curto é
pelo perímetro externo.
870
00:40:57,760 --> 00:40:59,040
Esse mapa de calor
871
00:40:59,040 --> 00:41:02,120
mostra o percurso seguido
por uma única abelha.
872
00:41:02,320 --> 00:41:04,280
Inicialmente,
ela só está descobrindo
873
00:41:04,280 --> 00:41:06,240
as posições dos
alimentadores.
874
00:41:07,640 --> 00:41:10,960
A seguir, a abelha parece
alterar, metodicamente,
875
00:41:10,960 --> 00:41:12,440
diferentes partes da rota,
876
00:41:12,440 --> 00:41:15,040
para ver se ela
consegue encurtá-la.
877
00:41:16,680 --> 00:41:18,480
Após 20 jornadas,
878
00:41:18,480 --> 00:41:21,320
ela se concentra
em uma rota eficiente.
879
00:41:26,240 --> 00:41:29,760
Essa rota nem sempre é o
caminho mais curto de todos,
880
00:41:29,760 --> 00:41:32,240
mas, para a abelha,
é bom o bastante.
881
00:41:36,160 --> 00:41:39,520
É incrível que tão só
após alguns testes,
882
00:41:39,520 --> 00:41:42,320
ela tenha chegado em algo
eficiente o bastante
883
00:41:42,320 --> 00:41:44,520
para que ela se alimente.
884
00:41:44,520 --> 00:41:45,120
Sim, exatamente.
885
00:41:45,120 --> 00:41:47,760
Elas poderiam levar
dias ou, até mesmo,
886
00:41:47,760 --> 00:41:49,240
poderiam levar meses ou anos
887
00:41:49,240 --> 00:41:50,560
para testarem todas
as possibilidades,
888
00:41:50,560 --> 00:41:53,240
então, elas precisam achar
uma rota rapidamente,
889
00:41:53,240 --> 00:41:55,600
que seja repetida
diversas vezes,
890
00:41:55,600 --> 00:41:58,720
para que consigam
alimentos o bastante.
891
00:41:58,720 --> 00:41:59,680
Fantástico.
892
00:41:59,680 --> 00:42:00,560
Eu acho que a abelha
893
00:42:00,560 --> 00:42:01,960
acaba de se tornar
meu inseto favorito.
894
00:42:01,960 --> 00:42:05,000
- É uma matemática nata!
- Sem dúvidas.
895
00:42:06,640 --> 00:42:07,880
Sejamos claros.
896
00:42:07,880 --> 00:42:11,200
As abelhas não estão prestes
a ganhar US$1 milhão.
897
00:42:11,440 --> 00:42:13,480
Elas não resolveram,
miraculosamente,
898
00:42:13,480 --> 00:42:15,040
o problema do
caixeiro viajante,
899
00:42:15,040 --> 00:42:18,360
porque elas nem sempre
encontram a rota mais curta.
900
00:42:19,320 --> 00:42:21,920
Mas seu algoritmo é uma
abordagem inteligente.
901
00:42:22,080 --> 00:42:25,000
Na Matemática, isso é
conhecido como Heurística.
902
00:42:25,000 --> 00:42:26,880
Algoritmos que são eficientes,
903
00:42:26,880 --> 00:42:29,120
que não encontram
a solução perfeita,
904
00:42:29,120 --> 00:42:31,760
mas que chegam o mais
perto dela possível.
905
00:42:44,640 --> 00:42:46,480
A mesma abordagem heurística
906
00:42:46,480 --> 00:42:48,320
tem sido usada para
desenvolver um algoritmo
907
00:42:48,320 --> 00:42:50,520
para o aeroporto de Heathrow.
908
00:42:54,880 --> 00:42:58,440
Heathrow lida com mais
de 1.300 vôs por dia.
909
00:42:58,440 --> 00:43:00,760
É o aeroporto mais
movimentado da Europa.
910
00:43:12,560 --> 00:43:15,000
O desafio para o controle
de tráfego aéreo
911
00:43:15,000 --> 00:43:17,400
é maximizar o
número de aeronaves
912
00:43:17,400 --> 00:43:19,000
que partem a cada hora,
913
00:43:19,000 --> 00:43:20,960
e garantir que o
aeroporto opere
914
00:43:20,960 --> 00:43:23,600
de modo eficiente e seguro.
915
00:43:29,360 --> 00:43:33,280
Uma das principais decisões
é a ordem da decolagem.
916
00:43:33,400 --> 00:43:34,920
Estamos cuidando
da decolagem de um grupo
917
00:43:34,920 --> 00:43:36,320
de aeronaves de médio porte,
918
00:43:36,320 --> 00:43:39,480
as quais serão separadas
por um minuto de distância.
919
00:43:39,480 --> 00:43:42,200
E atrás delas,
você pode ver um 747,
920
00:43:42,200 --> 00:43:43,880
que é uma aeronave grande.
921
00:43:44,720 --> 00:43:47,240
Aeronaves medianas
precisam ser separadas
922
00:43:47,240 --> 00:43:50,360
da turbulência gerada
por aeronaves maiores.
923
00:43:50,360 --> 00:43:53,080
Então, ordenar
pelo tamanho é crucial.
924
00:43:53,720 --> 00:43:56,280
A sequência ideal
da decolagem envolve
925
00:43:56,280 --> 00:43:58,720
juntar grupos de aeronaves.
926
00:43:58,720 --> 00:44:01,200
Você quer que aviões grandes
sejam agrupados juntos,
927
00:44:01,200 --> 00:44:03,600
que aeronaves medianas
sejam agrupadas juntas.
928
00:44:03,600 --> 00:44:06,160
E isso permite que a separação
entre essas aeronaves
929
00:44:06,160 --> 00:44:07,400
seja minimizada.
930
00:44:10,400 --> 00:44:12,840
O outro fator que
precisa ser considerado,
931
00:44:12,840 --> 00:44:14,320
no planejamento da decolagem,
932
00:44:14,320 --> 00:44:16,240
é para onde
os aviões estão indo.
933
00:44:19,720 --> 00:44:21,080
Queremos que um se
dirija ao norte,
934
00:44:21,080 --> 00:44:22,200
que um vá para o sul,
935
00:44:22,200 --> 00:44:24,160
que o próximo vá para norte,
e, depois, para o sul.
936
00:44:24,160 --> 00:44:26,520
Se todas as aeronaves
fossem na mesma direção,
937
00:44:26,520 --> 00:44:28,560
a separação seria bem maior,
938
00:44:28,560 --> 00:44:31,040
e não conseguiríamos usar
as pistas com eficiência.
939
00:44:31,640 --> 00:44:33,040
Todos os controladores
estão sentados
940
00:44:33,040 --> 00:44:34,680
nas torres de
controle, pensando:
941
00:44:34,680 --> 00:44:36,520
"Eu tenho todos esses
aviões indo pro norte,
942
00:44:36,520 --> 00:44:38,400
todas essas aeronaves
indo pro sul.
943
00:44:38,400 --> 00:44:40,240
"Eu tenho essas,
as quais são maiores,
944
00:44:40,240 --> 00:44:42,200
então, eu quero tentar
agrupar todas as grandes,
945
00:44:42,200 --> 00:44:44,560
para que não passe de uma
grande para uma pequena".
946
00:44:44,560 --> 00:44:47,640
É um problema bem complicado
para eles pensarem.
947
00:44:50,360 --> 00:44:54,600
Em 2013, um algoritmo
se juntou à equipe.
948
00:44:54,600 --> 00:44:56,080
Seu trabalho é prever
949
00:44:56,080 --> 00:44:58,200
a ordem mais provável
de decolagem,
950
00:44:58,200 --> 00:45:00,320
e advertir o controle
de tráfego áereo,
951
00:45:00,320 --> 00:45:03,160
quando aeronaves devam
ser rebocadas dos portões.
952
00:45:03,360 --> 00:45:06,160
Fazer isso envolve nada
menos do que simular
953
00:45:06,160 --> 00:45:09,720
toda a operação de pousos
e decolagens do aeroporto.
954
00:45:11,160 --> 00:45:15,160
Implica em milhões de
cálculos por segundo.
955
00:45:21,600 --> 00:45:25,360
O algoritmo funciona
tentando prever
956
00:45:25,360 --> 00:45:27,880
com que ordem as aeronaves
deverão decolar.
957
00:45:28,200 --> 00:45:30,440
Se ele souber em que
ordem elas poderão decolar,
958
00:45:30,440 --> 00:45:32,760
então, ele poderia
retroceder e dizer:
959
00:45:32,760 --> 00:45:34,560
"Se você precisa
decolar, agora,
960
00:45:34,560 --> 00:45:37,080
então, precisa entrar, agora,
na pista de pouso,
961
00:45:37,080 --> 00:45:39,720
então, precisa concluir
o taxiamento, agora,
962
00:45:39,720 --> 00:45:42,320
então, precisa começar
o taxiamento, agora.
963
00:45:42,320 --> 00:45:45,600
Então, precisa cessar
o reboque, agora,
964
00:45:45,600 --> 00:45:47,760
então, precisa começar
o reboque, agora".
965
00:45:47,760 --> 00:45:50,120
E podemos retroceder desde
o momento da decolagem
966
00:45:50,120 --> 00:45:52,200
até quando deveria
começar a ser rebocada.
967
00:45:55,320 --> 00:45:57,040
A saída do algoritmo
968
00:45:57,040 --> 00:45:59,080
é repassada ao controle
de tráfego aéreo
969
00:45:59,080 --> 00:46:00,480
através do sistema
computadorizado
970
00:46:00,480 --> 00:46:01,720
interno do aeroporto,
971
00:46:01,720 --> 00:46:03,920
e mostrada para o
piloto, no portão,
972
00:46:03,920 --> 00:46:06,040
na forma do TSAT -
973
00:46:06,040 --> 00:46:08,400
o horário de reboque
recomendado.
974
00:46:09,880 --> 00:46:13,200
O piloto pode observar
todo o sistema de entrada,
975
00:46:13,200 --> 00:46:16,320
para ver qual o horário
previsto de decolagem.
976
00:46:17,560 --> 00:46:19,440
O maior benefício
do algoritmo
977
00:46:19,440 --> 00:46:20,800
é que ele significa
que você pode manter
978
00:46:20,800 --> 00:46:22,560
a aeronave parada
por mais tempo,
979
00:46:22,560 --> 00:46:24,760
sem que ela decole,
posteriormente.
980
00:46:24,920 --> 00:46:26,240
Então, não há prejuízo
981
00:46:26,240 --> 00:46:28,440
para os passageiros
em termos de atraso.
982
00:46:28,440 --> 00:46:31,360
Podemos dar a partida
nos motores mais tarde.
983
00:46:32,640 --> 00:46:35,400
De fato, se pouparmos
dois minutos de taxiamento,
984
00:46:35,400 --> 00:46:37,640
da pista até sua cabeceira,
ao fim de um ano,
985
00:46:37,640 --> 00:46:40,800
teremos uma economia de
£15 milhões em combustível.
986
00:46:42,040 --> 00:46:44,400
O algoritmo de
sequenciamento de Heathrow
987
00:46:44,400 --> 00:46:48,520
mostra o que pode ser obtido
com a abordagem heurística.
988
00:46:48,920 --> 00:46:50,240
Assim como as abelhas,
989
00:46:50,240 --> 00:46:51,800
o algoritmo não
está encontrando
990
00:46:51,800 --> 00:46:54,840
a solução absoluta
perfeita, o tempo todo,
991
00:46:55,040 --> 00:46:57,440
mas, no entanto, torna
um trabalho duro
992
00:46:57,440 --> 00:46:59,160
um pouco mais fácil.
993
00:47:00,160 --> 00:47:01,560
Estamos muito
orgulhosos do algoritmo,
994
00:47:01,560 --> 00:47:04,400
porque ele, atualmente,
modela o mundo real,
995
00:47:04,400 --> 00:47:06,000
e isso é útil.
996
00:47:16,040 --> 00:47:18,680
No início, algoritmos
eram criados
997
00:47:18,680 --> 00:47:21,720
por matemáticos,
para matemáticos.
998
00:47:21,960 --> 00:47:23,520
E durante o último século,
999
00:47:23,520 --> 00:47:26,920
algoritmos têm sido
criados para computadores.
1000
00:47:29,120 --> 00:47:31,080
Mas, talvez, nosso
relacionamento
1001
00:47:31,080 --> 00:47:34,480
esteja prestes a passar por
uma revolução dramática.
1002
00:47:39,240 --> 00:47:41,800
No Microsoft Research,
em Cambridge,
1003
00:47:41,800 --> 00:47:44,120
cientistas estão
usando novas técnicas
1004
00:47:44,120 --> 00:47:46,120
para desenvolver algoritmos...
1005
00:47:46,240 --> 00:47:47,480
...apagando a fronteira
1006
00:47:47,480 --> 00:47:50,920
entre o inventor
e o próprio algoritmo.
1007
00:47:56,480 --> 00:48:00,120
Esse é o Algoritmo de Rastreio
Esquelético via Kinect.
1008
00:48:00,120 --> 00:48:03,160
O incrível é que ele
é capaz de identificar
1009
00:48:03,160 --> 00:48:05,080
as diferentes partes
do meu corpo.
1010
00:48:05,080 --> 00:48:06,520
Então, você pode ver
que ele pintou
1011
00:48:06,520 --> 00:48:08,520
o topo de minha cabeça
de vermelho,
1012
00:48:08,520 --> 00:48:10,960
e minha mão direita,
aqui, em azul.
1013
00:48:10,960 --> 00:48:13,520
Você pode ver que ele
pintou meu pescoço de verde.
1014
00:48:13,520 --> 00:48:16,040
Esse algoritmo
nunca me viu antes,
1015
00:48:16,040 --> 00:48:18,440
nem sequer sabe como eu
me movo espacialmente,
1016
00:48:18,440 --> 00:48:20,480
mas simplesmente usando
os dados transmitidos
1017
00:48:20,480 --> 00:48:22,040
por essa câmera
especial, aqui,
1018
00:48:22,040 --> 00:48:25,080
medindo a distância da
câmera para o meu corpo,
1019
00:48:25,080 --> 00:48:28,240
ele é capaz de
produzir esse mapa.
1020
00:48:30,240 --> 00:48:32,200
Qualquer postura
que eu assuma,
1021
00:48:32,200 --> 00:48:34,160
usando nada mais
do que a entrada
1022
00:48:34,160 --> 00:48:36,400
dessa câmera especial com
sensor de profundidade,
1023
00:48:36,400 --> 00:48:39,160
o algoritmo é capaz de
identificar, precisamente,
1024
00:48:39,160 --> 00:48:40,680
pixel por pixel,
1025
00:48:40,680 --> 00:48:42,880
as diferentes
partes de meu corpo.
1026
00:48:46,360 --> 00:48:49,760
Ele foi desenvolvido para
o console XBox, da Microsoft,
1027
00:48:49,760 --> 00:48:50,880
para rastrear o movimento
1028
00:48:50,880 --> 00:48:53,800
da postura corporal de um
jogador em tempo real.
1029
00:48:58,120 --> 00:48:59,680
Mas tão notável quanto
1030
00:48:59,680 --> 00:49:01,560
o que esse algoritmo
é capaz de fazer,
1031
00:49:01,560 --> 00:49:04,560
é o processo por trás
de como ele foi criado,
1032
00:49:04,560 --> 00:49:07,440
como o pesquisador
Jamie Shotton explica.
1033
00:49:09,240 --> 00:49:12,440
O que está acontecendo
é que cada pixel na imagem
1034
00:49:12,440 --> 00:49:15,880
é fruto de um algoritmo
chamado Árvore de Decisões.
1035
00:49:15,960 --> 00:49:17,320
E você pode pensar
na Árvore de Decisões
1036
00:49:17,320 --> 00:49:19,520
como um jogo de 20 perguntas.
1037
00:49:19,520 --> 00:49:20,680
Então, a Árvore de Decisão
1038
00:49:20,680 --> 00:49:22,640
está, por exemplo, pegando
um pixel de minha mão
1039
00:49:22,640 --> 00:49:23,560
e tentando decidir:
1040
00:49:23,560 --> 00:49:25,120
"OK, eu preciso
colori-la de azul,
1041
00:49:25,120 --> 00:49:27,560
porque está na mão,
e não no corpo".
1042
00:49:27,560 --> 00:49:28,200
Exato.
1043
00:49:28,200 --> 00:49:29,600
A chave para uma
Árvore de Decisão
1044
00:49:29,600 --> 00:49:32,360
é o fato de que as
20 perguntas que você faz
1045
00:49:32,360 --> 00:49:35,400
não são as mesmas
para cada pixel
1046
00:49:35,400 --> 00:49:37,240
que estamos
tentando classificar.
1047
00:49:37,240 --> 00:49:39,960
E o conjunto completo das
questões possíveis
1048
00:49:39,960 --> 00:49:43,400
que poderiam ser
feitas é exponencial.
1049
00:49:43,400 --> 00:49:45,320
- São 2 elevado a 20.
- 20? Certo.
1050
00:49:45,320 --> 00:49:46,840
OK, isso dá mais de um
milhão de perguntas -
1051
00:49:46,840 --> 00:49:47,960
é um bocado de perguntas
1052
00:49:47,960 --> 00:49:49,240
que você precisa
programar nele.
1053
00:49:49,240 --> 00:49:51,040
Sim, levaríamos tempo demais
1054
00:49:51,040 --> 00:49:52,920
e estaríamos muito
propensos a erros,
1055
00:49:52,920 --> 00:49:55,120
como seres humanos,
ao programá-lo manualmente.
1056
00:49:55,120 --> 00:49:57,680
Então, o algoritmo está
se reprogramando, ou...?
1057
00:49:57,880 --> 00:49:59,080
Exatamente!
1058
00:50:02,720 --> 00:50:05,360
O algoritmo não foi
projetado por Jamie
1059
00:50:05,360 --> 00:50:06,200
mas, ao invés disso,
1060
00:50:06,200 --> 00:50:09,000
por um processo chamado
Aprendizado de Máquina.
1061
00:50:11,320 --> 00:50:13,320
Isso envolveu
mostrar ao algoritmo
1062
00:50:13,320 --> 00:50:15,560
milhões de imagens
de treinamento
1063
00:50:15,560 --> 00:50:17,440
de corpos em
diferentes posições
1064
00:50:17,440 --> 00:50:19,520
e de várias
formas e tamanhos -
1065
00:50:19,520 --> 00:50:21,560
dos mais gordos
aos mais magros,
1066
00:50:21,560 --> 00:50:23,840
dos mais baixos
aos mais altos.
1067
00:50:24,520 --> 00:50:25,640
E, a partir disso,
1068
00:50:25,640 --> 00:50:28,880
o algoritmo essencialmente
aprendeu via exemplos,
1069
00:50:28,880 --> 00:50:31,360
criando suas
próprias regras.
1070
00:50:34,080 --> 00:50:35,960
Onde nossa
inteligência entra,
1071
00:50:35,960 --> 00:50:37,320
como projetistas do sistema,
1072
00:50:37,320 --> 00:50:41,560
não está na programação
do algoritmo em si,
1073
00:50:41,560 --> 00:50:44,360
mas em projetar o conjunto
dos dados de treinamento,
1074
00:50:44,360 --> 00:50:46,920
para captar todos
os tipos de variações
1075
00:50:46,920 --> 00:50:48,360
que você esperaria ver,
1076
00:50:48,360 --> 00:50:49,880
quando empregamos
esse sistema
1077
00:50:49,880 --> 00:50:50,920
nas salas de estar
das pessoas,
1078
00:50:50,920 --> 00:50:52,000
para brincarem com seus jogos.
1079
00:50:52,000 --> 00:50:55,400
Bem, mas você sabe o que
o algoritmo está fazendo?
1080
00:50:55,400 --> 00:50:57,920
Nós temos uma idéia do que
ele está tentando fazer,
1081
00:50:57,920 --> 00:50:59,360
e de como ele está
basicamente funcionando,
1082
00:50:59,360 --> 00:51:01,200
mas, provavelmente,
não podemos entender,
1083
00:51:01,200 --> 00:51:02,960
exatamente,
o que está havendo.
1084
00:51:04,680 --> 00:51:07,200
A mesma abordagem do
Aprendizado de Máquina
1085
00:51:07,200 --> 00:51:10,000
tem sido usada em
outras aplicações.
1086
00:51:10,360 --> 00:51:12,600
Por exemplo, esse
algoritmo é capaz
1087
00:51:12,600 --> 00:51:14,960
de fazer algo que,
por um bom tempo,
1088
00:51:14,960 --> 00:51:17,080
acreditávamos ser uma
habilidade exclusiva
1089
00:51:17,080 --> 00:51:19,720
de neurocirurgiões
e radiologistas.
1090
00:51:19,720 --> 00:51:21,360
A partir de imagens
de ressonância,
1091
00:51:21,360 --> 00:51:23,640
o algoritmo é capaz de
identificar e mapear
1092
00:51:23,640 --> 00:51:25,960
um tumor cerebral em 3D.
1093
00:51:26,360 --> 00:51:28,120
O que significa que um
trabalho que, normalmente,
1094
00:51:28,120 --> 00:51:29,320
levaria uma hora
1095
00:51:29,320 --> 00:51:31,720
pode ser feito em uma
questão de minutos.
1096
00:51:34,320 --> 00:51:35,840
O Professor Chris Bishop
1097
00:51:35,840 --> 00:51:37,440
está interessado
em desenvolver
1098
00:51:37,440 --> 00:51:40,720
ainda mais o conceito de
Aprendizado de Máquina,
1099
00:51:40,840 --> 00:51:42,560
para criar algoritmos que
1100
00:51:42,560 --> 00:51:44,560
possam aprender da
mesma forma que nós,
1101
00:51:44,560 --> 00:51:47,000
diretamente através
da experiência.
1102
00:51:49,160 --> 00:51:50,680
Bem, eu creio que
essa demonstração
1103
00:51:50,680 --> 00:51:51,880
ilustra o caminho
1104
00:51:51,880 --> 00:51:53,960
que os algoritmos seguirão
nos próximos anos.
1105
00:51:53,960 --> 00:51:55,640
OK, eu posso ver
vários filmes, aqui -
1106
00:51:55,640 --> 00:51:57,800
o que o algoritmo irá fazer?
1107
00:51:57,800 --> 00:51:59,040
O que temos são
algumas das centenas
1108
00:51:59,040 --> 00:52:00,720
dos filmes mais
comumente vistos,
1109
00:52:00,720 --> 00:52:02,560
e o que ele irá
fazer é aprender
1110
00:52:02,560 --> 00:52:05,640
acerca de seus gostos
e aversões pessoais.
1111
00:52:06,180 --> 00:52:07,760
Ele já foi treinado,
1112
00:52:07,760 --> 00:52:10,120
então, há um Aprendizado
de Máquina nos bastidores,
1113
00:52:10,120 --> 00:52:11,440
mas ele já foi treinado
1114
00:52:11,440 --> 00:52:14,200
com dados oriundos de
cerca de 10.000 pessoas.
1115
00:52:14,200 --> 00:52:15,280
O que ele irá fazer, agora,
1116
00:52:15,280 --> 00:52:18,400
é aprender acerca
de suas preferências.
1117
00:52:18,400 --> 00:52:20,080
No momento, ele não conhece
nada a seu respeito,
1118
00:52:20,080 --> 00:52:21,320
então, esses filmes
foram dispostos
1119
00:52:21,320 --> 00:52:22,720
aleatoriamente na tela.
1120
00:52:22,720 --> 00:52:25,520
O que preciso que faça
é pegar um desses filmes -
1121
00:52:25,520 --> 00:52:27,680
um que você goste
ou um que não goste.
1122
00:52:27,680 --> 00:52:30,320
Se gostar dele, arraste-o
para a região verde.
1123
00:52:30,320 --> 00:52:32,800
Se não gostar dele,
para a região vermelha.
1124
00:52:32,800 --> 00:52:35,360
OK, certo. Rushmore!
Sou grande fã de Rushmore.
1125
00:52:35,360 --> 00:52:37,760
Você gosta de Rushmore?
Ok, certo.
1126
00:52:38,040 --> 00:52:39,200
Então, o que está
acontecendo, agora,
1127
00:52:39,200 --> 00:52:41,320
é que, se o filme estiver
perto do lado direito,
1128
00:52:41,320 --> 00:52:42,520
perto da região verde,
1129
00:52:42,520 --> 00:52:44,720
ele tem certeza que
você irá gostar dele.
1130
00:52:44,720 --> 00:52:46,800
Então, se ficar perto
da região vermelha,
1131
00:52:46,800 --> 00:52:48,320
ele tem certeza que
você não gosta dele.
1132
00:52:48,320 --> 00:52:50,840
No meio, são 50-50%.
Ele não tem certeza.
1133
00:52:51,240 --> 00:52:54,040
Então, se eu escolher
um filme, aqui, do meio...
1134
00:52:54,040 --> 00:52:56,000
Eu não sou um grande
fã de Austin Powers,
1135
00:52:56,000 --> 00:52:58,080
então, vamos jogá-lo para...
1136
00:52:58,080 --> 00:53:01,080
Certo, veja que começam
a se espalhar para os lados.
1137
00:53:01,080 --> 00:53:02,640
Está se tornando
mais confiante.
1138
00:53:02,640 --> 00:53:04,200
Sim, sim.
Ele é muito bom.
1139
00:53:04,200 --> 00:53:07,600
Sim, sou um grande fã
de Dr. Strangelove,
1140
00:53:07,600 --> 00:53:11,360
e, sim, um grande fã
de Woody Allen...
1141
00:53:11,360 --> 00:53:15,200
mas Spinal Tap... ele acha
que eu gosto disso.
1142
00:53:15,200 --> 00:53:16,120
Bem, isso é interessante.
1143
00:53:16,120 --> 00:53:18,240
Quando ele tinha certeza
de que você gostava,
1144
00:53:18,240 --> 00:53:19,640
e você confirmou
que gostava,
1145
00:53:19,640 --> 00:53:20,520
nada demais aconteceu,
1146
00:53:20,520 --> 00:53:23,080
porque ele não
aprendeu muita coisa.
1147
00:53:23,080 --> 00:53:24,760
Quando tinha certeza
de que você gostaria,
1148
00:53:24,760 --> 00:53:25,760
como no caso de Spinal Tap,
1149
00:53:25,760 --> 00:53:28,120
e você disse "não gosto",
houve uma grande mudança.
1150
00:53:28,120 --> 00:53:30,040
Ele está aprendendo
as coisas comigo.
1151
00:53:30,040 --> 00:53:31,800
Eu, de fato, estou
alterando o algoritmo
1152
00:53:31,800 --> 00:53:33,400
conforme interajo com ele.
- Exatamente.
1153
00:53:33,400 --> 00:53:36,240
Enquanto que o Kinect
foi treinado em laboratório
1154
00:53:36,240 --> 00:53:37,440
e, a seguir, ficou estático,
1155
00:53:37,440 --> 00:53:39,440
esse algoritmo
continua a se adaptar,
1156
00:53:39,440 --> 00:53:41,400
e continua a evoluir
ao longo de sua vida.
1157
00:53:41,400 --> 00:53:43,280
Quanto mais filmes
você classificar como
1158
00:53:43,280 --> 00:53:44,440
"gosto" ou "não gosto",
1159
00:53:44,440 --> 00:53:46,160
mais ele irá aprender
sobre sua personalidade
1160
00:53:46,160 --> 00:53:48,600
e mais capaz ele será de
fazer boas recomendações.
1161
00:53:48,600 --> 00:53:52,160
Esse algoritmo está começando
a parecer bem mais humano,
1162
00:53:52,160 --> 00:53:55,040
pela forma com que ele
interage com o mundo.
1163
00:53:55,040 --> 00:53:55,840
Esse é o seu objetivo?
1164
00:53:55,840 --> 00:53:58,160
Descobrir uma forma
de produzir algoritmos
1165
00:53:58,160 --> 00:53:59,520
que se assemelhem
à forma como nós
1166
00:53:59,520 --> 00:54:00,680
lidamos com o mundo?
- Exato.
1167
00:54:00,680 --> 00:54:03,160
É um passo a menos
na enorme jornada
1168
00:54:03,160 --> 00:54:04,080
de produzir máquinas
1169
00:54:04,080 --> 00:54:05,760
que sejam tão capazes
quanto o cérebro humano.
1170
00:54:05,760 --> 00:54:06,760
Temos um longo
caminho pela frente,
1171
00:54:06,760 --> 00:54:08,800
mas esse é um pequeno
passo nessa direção,
1172
00:54:08,800 --> 00:54:10,040
porque ele não
está mais fixado.
1173
00:54:10,040 --> 00:54:11,760
Ele segue aprendendo,
exatamente da mesma forma
1174
00:54:11,760 --> 00:54:14,680
que seguimos aprendendo
em nosso cotidiano.
1175
00:54:19,760 --> 00:54:21,240
Eu acho que estamos
apenas começando
1176
00:54:21,240 --> 00:54:24,400
a perceber o potencial
completo dos algoritmos,
1177
00:54:24,400 --> 00:54:26,800
e há apenas mais um local
que eu quero visitar,
1178
00:54:26,800 --> 00:54:28,920
o qual disseram que
me dará um vislumbre
1179
00:54:28,920 --> 00:54:31,880
do quanto eles são
capazes de fazer por nós.
1180
00:54:40,180 --> 00:54:44,240
É um mundo onde quase
tudo é automatizado.
1181
00:54:46,640 --> 00:54:49,320
Onde os algoritmos
estão no controle.
1182
00:54:49,640 --> 00:54:53,840
É o maior armazém
automatizado da Terra.
1183
00:54:53,840 --> 00:54:57,200
Ele pertence ao supermercado
varejista online Ocado
1184
00:54:57,200 --> 00:55:01,240
e representa o equivalente
a 45 supermercados.
1185
00:55:02,320 --> 00:55:04,320
Mais de 2 milhões de itens
1186
00:55:04,320 --> 00:55:06,560
fluem através desse
armazém, diariamente.
1187
00:55:06,560 --> 00:55:07,600
A todo momento,
1188
00:55:07,600 --> 00:55:09,720
há algo em torno
de 7.000 caixas
1189
00:55:09,720 --> 00:55:12,760
percorrendo 25
quilômetros de trilhos,
1190
00:55:12,760 --> 00:55:14,560
e controlando cada aspecto
1191
00:55:14,560 --> 00:55:18,920
desse espetáculo incrível
estão os algoritmos.
1192
00:55:25,400 --> 00:55:26,760
Cada uma dessas
caixas vermelhas
1193
00:55:26,760 --> 00:55:28,680
faz parte do
pedido de um cliente,
1194
00:55:28,680 --> 00:55:31,520
e eles podem sair daqui
1195
00:55:31,520 --> 00:55:33,600
para encontrar outros
itens que eles queiram,
1196
00:55:33,600 --> 00:55:34,840
através de todo o armazém,
1197
00:55:34,840 --> 00:55:36,560
até que tenham,
eventualmente terminado,
1198
00:55:36,560 --> 00:55:38,240
descarregando
tudo em uma van
1199
00:55:38,240 --> 00:55:41,120
e, a seguir, dirigindo por
nosso sistema de roteamento -
1200
00:55:41,120 --> 00:55:44,480
por uma rota que é,
em muitas formas,
1201
00:55:44,480 --> 00:55:45,960
resolver problemas como
1202
00:55:45,960 --> 00:55:47,240
o problema do
caixeiro viajante.
1203
00:55:47,240 --> 00:55:49,520
Há decisões sendo
tomadas por toda parte,
1204
00:55:49,520 --> 00:55:51,640
conforme uma caixa vermelha
passa por aqui e por ali...
1205
00:55:51,880 --> 00:55:54,440
A complexidade
por trás de tudo isso
1206
00:55:54,440 --> 00:55:56,840
está além do que
qualquer ser humano
1207
00:55:56,840 --> 00:55:59,040
poderia controlar ou resolver,
1208
00:55:59,040 --> 00:56:01,840
e é aí onde entram
esses algoritmos -
1209
00:56:01,840 --> 00:56:04,040
técnicas resolvedoras
de problemas -
1210
00:56:04,040 --> 00:56:05,960
para superar esses desafios.
1211
00:56:10,960 --> 00:56:12,560
Para onde quer que você olhe,
1212
00:56:12,560 --> 00:56:16,120
a mão invisível do
algoritmo está em ação.
1213
00:56:16,440 --> 00:56:17,920
Algoritmos de previsão
1214
00:56:17,920 --> 00:56:19,920
monitoram e
reabastecem o estoque
1215
00:56:19,920 --> 00:56:22,600
de mais de 43.000 produtos,
1216
00:56:22,600 --> 00:56:25,000
antecipando a
demanda dos clientes.
1217
00:56:26,560 --> 00:56:28,400
Algoritmos de controle
de sistemas
1218
00:56:28,400 --> 00:56:31,920
gerenciam o tráfego
das mais de 7.000 caixas
1219
00:56:31,920 --> 00:56:33,560
por todo o armazém.
1220
00:56:36,040 --> 00:56:39,040
E algoritmos de roteamento
controlam o movimento
1221
00:56:39,040 --> 00:56:42,080
da frota de
mais de 1.500 vans,
1222
00:56:42,080 --> 00:56:43,760
testando mais de 4 milhões
1223
00:56:43,760 --> 00:56:46,640
de diferentes combinações
de rota a cada segundo.
1224
00:56:48,000 --> 00:56:49,200
Você quase consegue ver
1225
00:56:49,200 --> 00:56:51,280
a mente da máquina
em operação,
1226
00:56:51,280 --> 00:56:52,480
e esse não é um
processo estático,
1227
00:56:52,480 --> 00:56:54,200
então, é por isso que
há uma enorme quantidade
1228
00:56:54,200 --> 00:56:55,920
de máquina de
aprendizado por aqui -
1229
00:56:55,920 --> 00:56:58,640
ou seja, é como um organismo
se auto-adaptando.
1230
00:56:58,640 --> 00:57:00,400
Ele está, constantemente,
precisando aprender,
1231
00:57:00,400 --> 00:57:02,200
a como melhorar.
1232
00:57:02,200 --> 00:57:04,480
E as pessoas não
conseguiriam fazer isso.
1233
00:57:04,480 --> 00:57:06,640
A máquina precisa
ajustar a si própria.
1234
00:57:10,560 --> 00:57:11,880
Então, quem você diria
1235
00:57:11,880 --> 00:57:13,960
que está, na verdade,
no controle de tudo isso?
1236
00:57:13,960 --> 00:57:15,040
Definitivamente,
1237
00:57:15,040 --> 00:57:17,280
são os algoritmos
que estão no controle.
1238
00:57:17,280 --> 00:57:19,800
Acho que estou ficando
com uma irritação algorítmica,
1239
00:57:19,800 --> 00:57:22,400
só de ver essa coisa incrível!
1240
00:57:24,240 --> 00:57:26,440
De algum modo,
esse armazém é como
1241
00:57:26,440 --> 00:57:28,800
um pequeno microcosmos
do mundo moderno.
1242
00:57:28,800 --> 00:57:30,320
Os algoritmos estão
controlando tudo -
1243
00:57:30,320 --> 00:57:33,360
motores de busca na Internet,
navegação via satélite
1244
00:57:33,360 --> 00:57:35,480
e até mantendo nossos
cartões de crédito a salvo.
1245
00:57:35,480 --> 00:57:37,480
Nosso mundo não funcionaria
1246
00:57:37,480 --> 00:57:40,120
sem o poder
desses algoritmos.
1247
00:57:45,280 --> 00:57:47,040
A Open University produziu
1248
00:57:47,040 --> 00:57:48,720
um pacote grauito
para você aprender,
1249
00:57:48,720 --> 00:57:50,200
criar e descobrir mais
1250
00:57:50,200 --> 00:57:53,160
acerca da tecnologia digital
do passado e do presente.
1251
00:57:53,160 --> 00:57:54,920
Para realizar seu
pedido, ligue para...
1252
00:57:58,440 --> 00:58:00,000
...ou siga o link abaixo
1253
00:58:00,000 --> 00:58:01,680
até a Open University.
1254
00:58:02,000 --> 00:58:07,500
Tradução e Legendagem:
VitDoc @docsPT
1255
00:58:07,500 --> 00:58:10,000
www.docspt.com