1 00:00:02,840 --> 00:00:03,840 Encoded by 2 00:00:04,040 --> 00:00:07,840 Without us noticing, modern life has been taken over. 3 00:00:10,080 --> 00:00:14,480 As we search for love, shop online, 4 00:00:14,480 --> 00:00:18,000 travel the world, 5 00:00:18,000 --> 00:00:20,320 even as we save lives, 6 00:00:20,320 --> 00:00:25,160 there are step-by-step instructions working quietly behind the scenes. 7 00:00:27,080 --> 00:00:30,440 More and more, they are ruling our lives. 8 00:00:30,440 --> 00:00:33,040 They're called algorithms. 9 00:00:34,400 --> 00:00:36,640 Algorithms are everywhere. 10 00:00:36,640 --> 00:00:39,680 These bite-sized chunks of maths have become central 11 00:00:39,680 --> 00:00:41,520 to our daily lives. 12 00:00:41,520 --> 00:00:44,800 But because they are invisible, we tend to take them for granted, 13 00:00:44,800 --> 00:00:46,320 even misunderstand them. 14 00:00:50,960 --> 00:00:52,080 LAUGHTER 15 00:00:53,200 --> 00:00:57,040 They are the secret to our digital world, and so much more. 16 00:00:58,720 --> 00:01:02,120 'In this programme, I'm going to show you some of my favourite 17 00:01:02,120 --> 00:01:05,880 'algorithms to reveal where they came from...' 18 00:01:05,880 --> 00:01:08,480 Algorithms are ancient. 19 00:01:08,480 --> 00:01:09,800 '..how they work...' 20 00:01:09,800 --> 00:01:11,920 The challenge is to find the shortest route... 21 00:01:11,920 --> 00:01:14,640 These are the rough instructions that you would use. 22 00:01:14,640 --> 00:01:17,800 ..for returning to your starting point. 23 00:01:17,800 --> 00:01:20,240 '..what they might be able to do in the future.' 24 00:01:20,240 --> 00:01:23,440 - The algorithm's kind of writing itself? Or...? - Absolutely. 25 00:01:23,440 --> 00:01:26,080 '..and how we can't live without them.' 26 00:01:26,080 --> 00:01:29,600 Even when we're baking a cake, we're following an algorithm. 27 00:01:29,600 --> 00:01:32,520 As a mathematician, I love algorithms. 28 00:01:32,520 --> 00:01:35,120 Not only are they impressive problem solvers, 29 00:01:35,120 --> 00:01:38,800 but also strangely beautiful, tapping into the mathematical 30 00:01:38,800 --> 00:01:42,200 order that underpins how the universe works. 31 00:01:42,200 --> 00:01:45,760 Welcome to the weird and wonderful world of algorithms. 32 00:01:54,600 --> 00:01:57,680 Most of us carry one of these around. 33 00:01:57,680 --> 00:02:00,160 Now, you might have noticed that when you take a photo 34 00:02:00,160 --> 00:02:05,800 with your phone, then it draws a box around any face, like this. 35 00:02:05,800 --> 00:02:09,480 This is the result of a special face-detection algorithm 36 00:02:09,480 --> 00:02:13,200 and it helps to keep the face in the photo in focus. 37 00:02:14,480 --> 00:02:18,280 'Like all algorithms, this one solves a problem. 38 00:02:18,280 --> 00:02:21,520 'In this case, finding a human face. 39 00:02:21,520 --> 00:02:24,760 'While it's not fooled by a face made of fruit, 40 00:02:24,760 --> 00:02:28,400 'it does detect a human face in a photo. 41 00:02:28,400 --> 00:02:31,200 'So, how does it do it? 42 00:02:31,200 --> 00:02:34,120 'At their root, algorithms are little more than 43 00:02:34,120 --> 00:02:37,280 'a series of step-by-step instructions. 44 00:02:37,280 --> 00:02:40,520 'This one works by methodically scanning the image 45 00:02:40,520 --> 00:02:43,520 'looking for four particular abstract patterns 46 00:02:43,520 --> 00:02:45,960 'associated with a face. 47 00:02:45,960 --> 00:02:48,280 'When these are detected one after another, 48 00:02:48,280 --> 00:02:52,520 'then the algorithm indicates it's found a human face.' 49 00:02:52,520 --> 00:02:56,880 The process taps into the underlying pattern behind all faces, 50 00:02:56,880 --> 00:02:59,520 no matter what shape or size. 51 00:02:59,520 --> 00:03:02,840 The end result is just one example of how algorithms have 52 00:03:02,840 --> 00:03:05,560 made our lives easier. 53 00:03:05,560 --> 00:03:09,000 - I'll do it! - I'll do it! - I was here first! - OK. 54 00:03:09,000 --> 00:03:10,600 So, off you go. 55 00:03:10,600 --> 00:03:14,240 'We tend to associate algorithms with computers, smartphones 56 00:03:14,240 --> 00:03:15,480 'and the internet. 57 00:03:15,480 --> 00:03:19,320 'But they are not exclusive to the world of technology. 58 00:03:19,320 --> 00:03:24,160 'My day job is Professor of Mathematics at Oxford University. 59 00:03:24,160 --> 00:03:26,920 'And one of the things I enjoy most is keeping 60 00:03:26,920 --> 00:03:29,120 'the students on their toes.' 61 00:03:29,120 --> 00:03:31,040 OK, I'll take one. 62 00:03:31,040 --> 00:03:33,920 Here, we're playing a mathematical game with a jar 63 00:03:33,920 --> 00:03:37,120 full of chocolates and one red hot chilli. 64 00:03:38,480 --> 00:03:42,720 'The aim is not to be left with the chilli at the end. 65 00:03:42,720 --> 00:03:44,360 'But what these students don't know, 66 00:03:44,360 --> 00:03:49,520 'is that I'm playing it with the help of an algorithm.' 67 00:03:49,520 --> 00:03:51,800 - OK. Ready? BOTH: - Yeah. 68 00:03:51,800 --> 00:03:54,560 Right, I'm going to go first, so remember, you can take one, 69 00:03:54,560 --> 00:03:57,200 two or three chocolates at a time. 70 00:03:57,200 --> 00:04:00,880 I'm not a greedy guy, so I'll just take one. Now, your turn. 71 00:04:00,880 --> 00:04:05,440 'Each player takes on their turn, between one and three chocolates.' 72 00:04:05,440 --> 00:04:09,120 You've taken two, OK. So, I'm going to take... I'll take two. 73 00:04:09,120 --> 00:04:12,280 'Whatever my opponent does, my algorithm that tells me 74 00:04:12,280 --> 00:04:14,200 'how to respond.' 75 00:04:14,200 --> 00:04:16,520 OK, I'll take two. 76 00:04:16,520 --> 00:04:19,080 And your turn again. SHE LAUGHS 77 00:04:19,080 --> 00:04:20,680 Oh, yeah. 78 00:04:20,680 --> 00:04:24,040 - So I'll take...three. - Three. And I'll take one. 79 00:04:24,040 --> 00:04:27,160 - And just a chilli left... - So, wait. Is that me? - Yeah, so you have 80 00:04:27,160 --> 00:04:29,640 - to eat the chilli. - Oh, no! - So, there you go. 81 00:04:29,640 --> 00:04:32,960 'Let me reveal how the algorithm I was using helped me win.' 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 So, the key is to think about grouping things in fours. 84 00:04:41,960 --> 00:04:46,720 13 chocolates divides into three groups of four, with one left over. 85 00:04:46,720 --> 00:04:50,160 So, by taking one chocolate in the first round and then four 86 00:04:50,160 --> 00:04:54,160 minus whatever the other player takes in the subsequent rounds, 87 00:04:54,160 --> 00:04:57,040 this algorithm ensures that the other player 88 00:04:57,040 --> 00:04:58,960 is always left with the chilli. 89 00:04:58,960 --> 00:05:01,080 The essence of a really good 90 00:05:01,080 --> 00:05:04,240 algorithm, its magic, if you like, is mathematics. 91 00:05:04,240 --> 00:05:07,440 The best algorithms are those that tap into the underlying 92 00:05:07,440 --> 00:05:10,400 mathematical structure hiding beneath a problem. 93 00:05:11,600 --> 00:05:13,080 OK, pop the chilli back. 94 00:05:14,480 --> 00:05:17,760 I'll be introducing you to some of the algorithms that have 95 00:05:17,760 --> 00:05:20,320 become the beating heart of modern life. 96 00:05:21,880 --> 00:05:24,920 But first, I want to show you that, for all their modern 97 00:05:24,920 --> 00:05:28,360 applications, algorithms are extremely old. 98 00:05:29,680 --> 00:05:33,600 In fact, they predate computers by thousands of years. 99 00:05:35,480 --> 00:05:38,280 The oldest algorithm we know of was devised 100 00:05:38,280 --> 00:05:40,480 to solve a mathematical problem. 101 00:05:40,480 --> 00:05:44,800 It was first written down by the Ancient Greek mathematician Euclid. 102 00:05:44,800 --> 00:05:47,520 Euclid's Algorithm, as it's known, 103 00:05:47,520 --> 00:05:50,680 is a method for finding the greatest common devisor. 104 00:05:52,360 --> 00:05:55,680 The greatest common devisor is the largest number that will 105 00:05:55,680 --> 00:06:00,280 divide into a pair of other numbers without leaving a remainder. 106 00:06:00,280 --> 00:06:03,000 So, in this case, four divides into both eight 107 00:06:03,000 --> 00:06:06,080 and 12 without a remainder. 108 00:06:06,080 --> 00:06:08,520 It's simple to find for small numbers, 109 00:06:08,520 --> 00:06:10,600 but much more tricky for large ones. 110 00:06:12,120 --> 00:06:15,480 While Euclid was the greatest mathematician of his day, 111 00:06:15,480 --> 00:06:18,640 his algorithm could have made him a fortune as a tiler. 112 00:06:19,840 --> 00:06:22,280 Let me show you why. 113 00:06:22,280 --> 00:06:25,440 Imagine you've got a rectangular-shaped floor 114 00:06:25,440 --> 00:06:26,760 and you want to find 115 00:06:26,760 --> 00:06:30,360 the most efficient way to tile it with square tiles. 116 00:06:30,360 --> 00:06:34,080 In other words, what's the largest square tile that will exactly 117 00:06:34,080 --> 00:06:38,040 divide the dimensions of the floor with nothing left over? 118 00:06:38,040 --> 00:06:40,440 This is, in fact, a geometric version 119 00:06:40,440 --> 00:06:43,080 of the greatest common devisor problem. 120 00:06:43,080 --> 00:06:46,280 The dimensions of the floor are the two numbers 121 00:06:46,280 --> 00:06:48,640 and the size of the tiles, which we're going to try 122 00:06:48,640 --> 00:06:51,960 and work out, is their greatest common devisor. 123 00:06:54,040 --> 00:06:57,480 We're going to follow Euclid's Algorithm step by step to show 124 00:06:57,480 --> 00:07:01,480 how it is able to find the perfect sized square tile for this floor. 125 00:07:02,920 --> 00:07:06,800 According to Euclid's Algorithm, we need to start filling the rectangle 126 00:07:06,800 --> 00:07:10,960 with square tiles corresponding to the smallest of the two dimensions. 127 00:07:13,760 --> 00:07:15,920 This is the first stage of the job. 128 00:07:17,160 --> 00:07:19,040 Euclid's Algorithm then tells us 129 00:07:19,040 --> 00:07:22,400 to do exactly the same thing again with this rectangle. 130 00:07:24,080 --> 00:07:28,520 At each stage, the algorithm tells us to select square tiles 131 00:07:28,520 --> 00:07:31,600 corresponding to the shortest side of the rectangle. 132 00:07:33,600 --> 00:07:38,880 So this time, our square tiles perfectly fill the leftover space. 133 00:07:38,880 --> 00:07:42,960 Now, my square tile has dimensions 15x15. 134 00:07:42,960 --> 00:07:45,720 So Euclid's Algorithm tells us 135 00:07:45,720 --> 00:07:50,440 that the greatest common devisor of 150 and 345 is 15. 136 00:07:53,240 --> 00:07:56,160 I'm not suggesting you use Euclid's Algorithm every time 137 00:07:56,160 --> 00:07:58,360 you need to order some tiles, 138 00:07:58,360 --> 00:08:02,480 but the amazing thing is that this simple step-by-step method 139 00:08:02,480 --> 00:08:06,440 finds the perfect square tile whatever the dimensions of the floor. 140 00:08:07,800 --> 00:08:11,640 Euclid's Algorithm may appear to be just a mathematical technique, 141 00:08:11,640 --> 00:08:16,400 but it very elegantly fulfils all the criteria for an algorithm. 142 00:08:16,400 --> 00:08:20,120 It's a precisely stated set of instructions, the procedure 143 00:08:20,120 --> 00:08:24,800 always finishes, and it can be proven that it works in all cases. 144 00:08:28,320 --> 00:08:31,800 The power of algorithms is that you don't have to reinvent 145 00:08:31,800 --> 00:08:36,480 the wheel each time. They're general solutions to problems. 146 00:08:36,480 --> 00:08:40,000 This holds as true for ancient algorithms as for modern ones. 147 00:08:45,320 --> 00:08:49,480 In 1998, in this garage in Menlo Park in California, 148 00:08:49,480 --> 00:08:52,440 an important piece of algorithmic history was made. 149 00:08:54,520 --> 00:08:58,560 Inside were two PHD students from Stamford University. 150 00:08:58,560 --> 00:09:00,760 Larry Page and Sergey Brin. 151 00:09:02,320 --> 00:09:05,640 Their aim was to come up with a search engine that could find 152 00:09:05,640 --> 00:09:08,480 things efficiently on the World Wide Web. 153 00:09:11,000 --> 00:09:13,880 Out of these humble beginnings, Google was born. 154 00:09:15,400 --> 00:09:18,760 But Google wouldn't be Google if it wasn't for the algorithm that 155 00:09:18,760 --> 00:09:21,600 Larry and Sergey created, called PageRank. 156 00:09:30,880 --> 00:09:34,040 PageRank was the algorithm at the heart of the first 157 00:09:34,040 --> 00:09:37,200 incarnation of the Google search engine. 158 00:09:37,200 --> 00:09:42,120 Now, technically, it's not a search algorithm, but a ranking algorithm. 159 00:09:42,120 --> 00:09:45,600 So when you type a query into a search engine, 160 00:09:45,600 --> 00:09:49,880 then there are literally millions of pages which will match that query. 161 00:09:49,880 --> 00:09:53,600 What PageRank does is to rank all of those pages so the one 162 00:09:53,600 --> 00:09:56,960 at the top is the one you're more likely to be interested in. 163 00:09:58,520 --> 00:10:01,440 Larry and Sergey came up with the idea to do PageRank 164 00:10:01,440 --> 00:10:05,880 and to use it as a ranking system to improve the quality of web search. 165 00:10:05,880 --> 00:10:07,800 I remember myself at the time, 166 00:10:07,800 --> 00:10:10,720 you used a web search engine like AltaVista. 167 00:10:10,720 --> 00:10:12,760 You would have to click the Next Page link 168 00:10:12,760 --> 00:10:14,880 a lot of times to find what you were looking for. 169 00:10:14,880 --> 00:10:17,280 PageRank was one of the reasons why Google was 170 00:10:17,280 --> 00:10:20,760 so much better than the existing search engines at the time. 171 00:10:21,800 --> 00:10:24,840 The inner workings of PageRank are hidden from view 172 00:10:24,840 --> 00:10:26,680 on the World Wide Web. 173 00:10:26,680 --> 00:10:30,360 So to reveal how it does its job, we're going to use the PageRank 174 00:10:30,360 --> 00:10:33,440 algorithm to rank the players of a football team. 175 00:10:34,600 --> 00:10:36,960 PageRank looks at two things. 176 00:10:36,960 --> 00:10:42,040 It looks at the incoming links to a web page, that is the other pages 177 00:10:42,040 --> 00:10:46,360 that link to the page, and it looks at how important those pages are. 178 00:10:51,960 --> 00:10:54,840 In our demonstration to show the cleverness of the PageRank 179 00:10:54,840 --> 00:10:59,280 algorithm, the players in the football team are the web pages 180 00:10:59,280 --> 00:11:02,880 and the passes between them are the web links. 181 00:11:02,880 --> 00:11:05,680 The input for the algorithm. 182 00:11:05,680 --> 00:11:09,240 Generally speaking, the PageRank algorithm will give a higher 183 00:11:09,240 --> 00:11:13,240 rank to a website if it's got a lot of links coming from other websites. 184 00:11:13,240 --> 00:11:16,000 So in the case of football, if a player gets more 185 00:11:16,000 --> 00:11:20,080 passes from the rest of the team, then they'll be ranked higher. 186 00:11:20,080 --> 00:11:21,680 It's not quite that simple. 187 00:11:21,680 --> 00:11:24,960 Because the PageRank algorithm actually gives more weight to 188 00:11:24,960 --> 00:11:28,880 a link from a website that itself has a high page rank. 189 00:11:28,880 --> 00:11:32,520 So actually, a pass from a popular player is worth more than 190 00:11:32,520 --> 00:11:35,960 a pass from a player who's hardly involved in the game at all. 191 00:11:37,120 --> 00:11:40,920 This is a visualisation of the algorithm at work. 192 00:11:40,920 --> 00:11:45,880 The stats are the players' current ranking. The output of the algorithm. 193 00:11:45,880 --> 00:11:50,280 And every time there's a pass, these rankings are updated. 194 00:11:50,280 --> 00:11:56,360 When Google uses this algorithm, it only changes once thing - the input. 195 00:11:56,360 --> 00:11:59,280 In place of passes, it uses web links. 196 00:12:01,280 --> 00:12:04,320 Note that the importance of a page depends on the importance 197 00:12:04,320 --> 00:12:06,480 of the pages that link to it. 198 00:12:06,480 --> 00:12:09,160 This means that you have to compute page rank for all 199 00:12:09,160 --> 00:12:11,240 the pages at the same time. 200 00:12:11,240 --> 00:12:14,200 And you actually have to repeat the computation because, each time, 201 00:12:14,200 --> 00:12:16,600 you'll update the importance of all the pages. 202 00:12:16,600 --> 00:12:19,040 And that in turn will influence 203 00:12:19,040 --> 00:12:22,120 the importance of the pages that those pages link to. 204 00:12:30,680 --> 00:12:33,840 At the end of the match, the job of the algorithm is done. 205 00:12:36,720 --> 00:12:39,880 If we wanted to search for the key player in the team, 206 00:12:39,880 --> 00:12:41,840 this is PageRank's answer. 207 00:12:43,800 --> 00:12:46,400 Player 11 has the highest PageRank score. 208 00:12:48,320 --> 00:12:50,640 I think the PageRank algorithm is probably 209 00:12:50,640 --> 00:12:52,560 my favourite algorithm of all time. 210 00:12:52,560 --> 00:12:54,960 And it's amazing that it can be applied not just to 211 00:12:54,960 --> 00:12:58,520 the World Wide Web, but analysing a football match, as well. 212 00:12:58,520 --> 00:13:01,320 But for me, it's the fact that there's a beautiful bit of 213 00:13:01,320 --> 00:13:03,880 mathematics at its heart that always seems to find 214 00:13:03,880 --> 00:13:05,960 the website I'm looking for. 215 00:13:08,120 --> 00:13:09,320 Within Google, I think 216 00:13:09,320 --> 00:13:14,320 PageRank is seen as a very important part of Google's early development. 217 00:13:15,520 --> 00:13:18,600 PageRank was the secret to why the search engine that Larry 218 00:13:18,600 --> 00:13:22,200 and Sergey built in the 1990s was so successful. 219 00:13:23,920 --> 00:13:28,640 Now, Google handles over 3.5 billion searches every day. 220 00:13:28,640 --> 00:13:31,960 It's the world's most poplar search engine. 221 00:13:31,960 --> 00:13:36,480 And the company is worth more than 450 billion. 222 00:13:37,560 --> 00:13:40,760 Not bad for two PhD students working out of a garage. 223 00:13:49,000 --> 00:13:52,600 Algorithms are simple step-by-step recipes. 224 00:13:52,600 --> 00:13:56,800 Inventing them requires incredible creativity and genius. 225 00:13:56,800 --> 00:14:01,000 But using them is just a matter of following instructions. 226 00:14:01,000 --> 00:14:04,600 And this is why algorithms are perfect for computers. 227 00:14:08,240 --> 00:14:10,200 Computers are just machines. 228 00:14:10,200 --> 00:14:14,000 They just do repetitive tasks at phenomenal speeds. 229 00:14:14,000 --> 00:14:15,560 Unbelievable speeds. 230 00:14:15,560 --> 00:14:20,080 So they're absolutely perfect for performing these repetitive tasks 231 00:14:20,080 --> 00:14:23,120 that are unambiguously defined 232 00:14:23,120 --> 00:14:27,320 and can be done in a finite amount of time. 233 00:14:29,040 --> 00:14:32,040 Computer code is basically making an algorithm specific. 234 00:14:32,040 --> 00:14:33,840 So the algorithm is the kind of idea. 235 00:14:33,840 --> 00:14:35,280 How would you solve the problem? 236 00:14:35,280 --> 00:14:37,680 These are the rough instructions that you would use. 237 00:14:37,680 --> 00:14:40,760 And then that can be translated into particular code. 238 00:14:43,920 --> 00:14:47,880 Lots of types of algorithms have been created with a computer in mind. 239 00:14:49,800 --> 00:14:53,360 And some of the most important are sorting algorithms. 240 00:14:54,880 --> 00:14:58,880 Now, the job of a sorting algorithm is to put things in order. 241 00:14:58,880 --> 00:15:00,560 And they have lots of uses. 242 00:15:00,560 --> 00:15:03,720 For example, on the internet, information gets 243 00:15:03,720 --> 00:15:08,720 broken down into packets of data which then get sent across the web. 244 00:15:08,720 --> 00:15:11,000 Now, to reassemble that data, 245 00:15:11,000 --> 00:15:15,120 sorting algorithms are absolutely crucial to putting this data 246 00:15:15,120 --> 00:15:18,720 back in the correct order so that we can view the picture, 247 00:15:18,720 --> 00:15:21,560 or read the email we've just been sent. 248 00:15:26,120 --> 00:15:30,000 This is the System Development Corporation in California. 249 00:15:30,000 --> 00:15:35,560 It's considered to be the world's first computer software company. 250 00:15:35,560 --> 00:15:40,680 And it was here in 1963 that two computer scientists first formally 251 00:15:40,680 --> 00:15:44,360 wrote down one of the most iconic sorting algorithms of all-time. 252 00:15:48,240 --> 00:15:50,280 It's called bubble sort. 253 00:15:50,280 --> 00:15:53,520 And here's an example of bubble sort in action, 254 00:15:53,520 --> 00:15:55,920 sorting blocks instead of numbers. 255 00:15:57,720 --> 00:16:01,200 It gets its name because with each round of the algorithm, 256 00:16:01,200 --> 00:16:05,240 the largest unsorted object bubbles to the top. 257 00:16:05,240 --> 00:16:09,000 Like all our algorithms so far, there's method in the madness. 258 00:16:14,760 --> 00:16:16,640 To see how this algorithm works, 259 00:16:16,640 --> 00:16:19,120 we're going to use it to sort eight objects. 260 00:16:20,760 --> 00:16:24,720 Now, the bubble sort algorithm says to consider the objects in pairs 261 00:16:24,720 --> 00:16:27,480 and swap them over if they're in the wrong order. 262 00:16:27,480 --> 00:16:31,840 So we're going to start at this end here and work our way to the top. 263 00:16:31,840 --> 00:16:35,880 So I consider these two, they're in the wrong order, so I swap them over. 264 00:16:37,560 --> 00:16:40,000 Consider the next pair, they're in the right order, 265 00:16:40,000 --> 00:16:42,280 so I leave them as they are. 266 00:16:42,280 --> 00:16:45,960 Consider this pair, they're in the wrong order, so I swap them. 267 00:16:48,920 --> 00:16:51,080 And we just continue doing this. 268 00:16:58,160 --> 00:17:01,600 Now the bubble sort algorithm says to go back to the beginning 269 00:17:01,600 --> 00:17:05,760 and repeat the process over and over again until the objects are in order. 270 00:17:19,800 --> 00:17:24,120 The algorithm stops when there are no pairs to swap round. 271 00:17:24,120 --> 00:17:27,880 So the bubble sort algorithm has successfully done its job. 272 00:17:27,880 --> 00:17:30,760 I've now got the objects perfectly ordered, 273 00:17:30,760 --> 00:17:32,640 according to ascending height. 274 00:17:34,160 --> 00:17:37,640 Bubble sort is elegantly simple and straightforward. 275 00:17:37,640 --> 00:17:41,880 But if the scale of the sorting task is huge, say, organising vast swathes 276 00:17:41,880 --> 00:17:45,720 of data, then there might be better sorting algorithms for the job. 277 00:17:50,800 --> 00:17:52,680 This is John von Neumann, 278 00:17:52,680 --> 00:17:56,560 the scientific genius who helped pioneer the modern computer, 279 00:17:56,560 --> 00:17:58,760 game theory, the atomic bomb 280 00:17:58,760 --> 00:18:02,200 and, as it turns out, invented a sorting algorithm. 281 00:18:04,760 --> 00:18:08,080 He devised it to work on this, one of the world's earliest 282 00:18:08,080 --> 00:18:11,880 electronic computers, which he'd helped design. 283 00:18:11,880 --> 00:18:14,800 The algorithm is called merge sort. 284 00:18:16,800 --> 00:18:21,200 The merge sort algorithm works on a principle of divide and conquer. 285 00:18:21,200 --> 00:18:26,280 And it consists of two parts. The first bit is the dividing part. 286 00:18:28,560 --> 00:18:31,920 This involves splitting everything into smaller groups. 287 00:18:35,240 --> 00:18:38,160 And now comes the conquering bit. 288 00:18:40,720 --> 00:18:43,640 The groups are now merged back together. 289 00:18:43,640 --> 00:18:47,480 But as I merge the two groups, I compare the sizes of the objects 290 00:18:47,480 --> 00:18:51,400 one pair at a time so that the merged group becomes sorted. 291 00:19:00,480 --> 00:19:03,240 Now, the merge sort algorithm might look rather similar to the 292 00:19:03,240 --> 00:19:07,240 bubble sort, but where it comes into its own is that with a larger 293 00:19:07,240 --> 00:19:10,280 number of objects, it's much, much faster. 294 00:19:10,280 --> 00:19:15,520 So let's see how merge sort compares in speed to bubble sort. 295 00:19:15,520 --> 00:19:18,040 It's time for a battle of the algorithms! 296 00:19:21,880 --> 00:19:26,000 Here we've got bubble sort on the bottom and merge sort on the top. 297 00:19:26,000 --> 00:19:28,760 And we've got them sorting 1,000 objects. 298 00:19:28,760 --> 00:19:31,840 Now, although they'll both produce the same end result, 299 00:19:31,840 --> 00:19:35,280 you can already see merge sort is getting there much faster. 300 00:19:35,280 --> 00:19:38,760 And this difference in performance gets more pronounced 301 00:19:38,760 --> 00:19:41,120 the more objects they're asked to sort. 302 00:19:53,040 --> 00:19:55,200 LAUGHTER 303 00:19:57,600 --> 00:19:59,560 Well, er... 304 00:19:59,560 --> 00:20:02,920 - I'm sorry, maybe... - No, no, no, no, no. 305 00:20:02,920 --> 00:20:05,000 I-I think...I think, er... 306 00:20:05,000 --> 00:20:08,400 I think the bubble sort would be the wrong way to go. 307 00:20:08,400 --> 00:20:10,160 LAUGHTER 308 00:20:10,160 --> 00:20:11,680 APPLAUSE 309 00:20:12,720 --> 00:20:15,360 Come on. Who told him this? 310 00:20:22,480 --> 00:20:24,760 Merge sort beats bubble sort hands down 311 00:20:24,760 --> 00:20:26,800 for sorting large amounts of data. 312 00:20:28,560 --> 00:20:31,200 But in the crazy world of algorithms, there are many, 313 00:20:31,200 --> 00:20:33,520 many different ways to sort. 314 00:20:36,000 --> 00:20:37,680 At the last count, 315 00:20:37,680 --> 00:20:41,160 there were over 20 different types of sorting algorithms. 316 00:20:42,920 --> 00:20:46,800 All weirdly achieving the same result, but by different means. 317 00:20:58,240 --> 00:21:02,680 - So there's bubble sort, there's merge sort. - Insertion sort. 318 00:21:02,680 --> 00:21:06,480 - There's heap sort, there's quick sort. - Timsort. 319 00:21:06,480 --> 00:21:07,840 You've got gnome sort. 320 00:21:07,840 --> 00:21:10,840 There's pigeonhole sort, which is also called radix sort. 321 00:21:10,840 --> 00:21:13,440 There's bogosort, which might never finish. 322 00:21:19,400 --> 00:21:23,320 There's no such thing as the best sorting algorithm. 323 00:21:23,320 --> 00:21:25,440 Each has its own pros and cons. 324 00:21:26,640 --> 00:21:28,080 And which one gets used 325 00:21:28,080 --> 00:21:31,080 often depends on the specifics of the problem. 326 00:21:32,760 --> 00:21:36,640 I think the beauty of studying algorithms is to try to aspire 327 00:21:36,640 --> 00:21:40,400 for solutions that are as elegant and efficient as possible. 328 00:21:40,400 --> 00:21:44,640 I actually think bubble sort's very pretty. I like it. 329 00:21:44,640 --> 00:21:46,320 Merge sort's beautiful. 330 00:21:49,520 --> 00:21:51,840 We really couldn't live without them. 331 00:21:51,840 --> 00:21:54,840 Sorting algorithms bring order to the world. 332 00:22:05,240 --> 00:22:07,920 So far, we've seen algorithms tackle the tiny 333 00:22:07,920 --> 00:22:11,280 problems of sizing our bathroom tiles and sorting our data. 334 00:22:12,920 --> 00:22:16,040 But how well do they cope with the messy world of love? 335 00:22:18,080 --> 00:22:20,880 Online dating is really popular these days. 336 00:22:20,880 --> 00:22:23,640 In fact, one survey suggests that over a third 337 00:22:23,640 --> 00:22:26,400 of recent marriages started online. 338 00:22:27,400 --> 00:22:30,800 How these dating websites work is that they use something called 339 00:22:30,800 --> 00:22:33,000 a matching algorithm. 340 00:22:33,000 --> 00:22:36,200 They search through the profiles, try to match people up according 341 00:22:36,200 --> 00:22:40,320 to their likes and dislikes, personality traits and so on. 342 00:22:40,320 --> 00:22:43,200 In fact, the algorithms seem to be better than humans. 343 00:22:43,200 --> 00:22:46,480 Because recent research has shown those who meet online 344 00:22:46,480 --> 00:22:49,160 tend to be happier and have longer marriages. 345 00:22:52,360 --> 00:22:56,640 I'll ask you to receive your prizes from His Majesty the King. 346 00:22:56,640 --> 00:23:01,080 In fact, matching algorithms have quite a lot to brag about. 347 00:23:01,080 --> 00:23:05,800 Because in 2012, for the first time, a Nobel Prize was awarded 348 00:23:05,800 --> 00:23:07,840 because of an algorithm. 349 00:23:07,840 --> 00:23:11,280 A matching algorithm created by the late David Gale 350 00:23:11,280 --> 00:23:13,480 and mathematician Lloyd Shapley, 351 00:23:13,480 --> 00:23:16,240 seen here receiving his share of the prize. 352 00:23:20,040 --> 00:23:23,720 The story begins in the 1960s when Gale and Shapley wanted to 353 00:23:23,720 --> 00:23:27,840 solve a problem concerned with college admissions. 354 00:23:27,840 --> 00:23:31,880 How to match up students to colleges so that everyone got a place. 355 00:23:32,880 --> 00:23:35,400 But, more importantly, was happy, even if 356 00:23:35,400 --> 00:23:37,480 they didn't get their first choice. 357 00:23:40,480 --> 00:23:44,160 They called it the stable marriage problem. 358 00:23:44,160 --> 00:23:46,680 The stable marriage problem goes like this. 359 00:23:46,680 --> 00:23:49,120 Suppose you've got four women and four men 360 00:23:49,120 --> 00:23:51,000 and they want to get married. 361 00:23:51,000 --> 00:23:54,000 Now, they've ranked each other according to their preferences. 362 00:23:54,000 --> 00:23:55,880 So, for example, the Queen of Hearts here, 363 00:23:55,880 --> 00:23:57,960 first choice is the King of Clubs. 364 00:23:57,960 --> 00:24:00,040 Second choice, King of Diamonds, 365 00:24:00,040 --> 00:24:02,840 and her last choice is the King of Hearts. 366 00:24:02,840 --> 00:24:06,080 So the challenge here is to play Cupid and pair up the kings 367 00:24:06,080 --> 00:24:09,920 and queens so that each one gets a partner, but, more importantly, 368 00:24:09,920 --> 00:24:12,520 so that the marriages are stable. 369 00:24:12,520 --> 00:24:15,640 A stable marriage means that the kings and queens don't 370 00:24:15,640 --> 00:24:20,640 necessarily get their first choice, but they get the best on offer. 371 00:24:20,640 --> 00:24:25,240 For example, if I paired the King of Hearts and the Queen of Hearts 372 00:24:25,240 --> 00:24:28,240 and the King of Spades and the Queen of Spades, 373 00:24:28,240 --> 00:24:31,040 this would be an unstable marriage. 374 00:24:31,040 --> 00:24:34,480 Because the King of Spades doesn't really like the Queen of Spades. 375 00:24:34,480 --> 00:24:36,640 He'd prefer the Queen of Hearts. 376 00:24:38,120 --> 00:24:40,040 The Queen of Hearts, in her turn, 377 00:24:40,040 --> 00:24:41,960 doesn't really like the King of Hearts. 378 00:24:41,960 --> 00:24:44,840 She'd prefer the King of Spades. 379 00:24:44,840 --> 00:24:48,120 So these two are going to run off together in this pairing. 380 00:24:51,960 --> 00:24:56,480 Where there's a problem, there's an algorithm not far behind. 381 00:24:56,480 --> 00:24:59,160 In 1962, Gale and Shapley came up with 382 00:24:59,160 --> 00:25:02,760 their Nobel-Prize-winning algorithm. 383 00:25:02,760 --> 00:25:09,560 A step-by-step recipe which always finds perfectly-stable marriages. 384 00:25:09,560 --> 00:25:11,240 So in the first round of the algorithm, 385 00:25:11,240 --> 00:25:14,440 the queens all proposed to their first-choice kings. 386 00:25:14,440 --> 00:25:18,720 So the Queen of Spades' first choice is the King of Spades. 387 00:25:18,720 --> 00:25:21,200 She proposes to the King of Spades. 388 00:25:21,200 --> 00:25:24,360 The Queen of Hearts' first choice is the King of Clubs, 389 00:25:24,360 --> 00:25:26,800 so she proposes to the King of Clubs. 390 00:25:26,800 --> 00:25:30,360 The Queen of Diamonds' first choice is the King of Spades. 391 00:25:30,360 --> 00:25:33,320 And the Queen of Clubs' first choice is also the King of Spades. 392 00:25:33,320 --> 00:25:36,600 So King of Spades seems to be the Darcy of this royal court. 393 00:25:37,800 --> 00:25:40,560 Now, the King of Spades has got three proposals. 394 00:25:41,720 --> 00:25:44,840 So he chooses his most popular queen, 395 00:25:44,840 --> 00:25:48,640 who is actually the Queen of Diamonds, and rejects the other two. 396 00:25:51,440 --> 00:25:55,600 So we have two provisional engagements, two rejections. 397 00:25:55,600 --> 00:25:59,280 We now remove the rejected queen's first choices. 398 00:25:59,280 --> 00:26:01,040 And it's time for round two. 399 00:26:02,480 --> 00:26:06,960 So the Queen of Spades is going to propose to the King of Diamonds. 400 00:26:06,960 --> 00:26:10,160 And the Queen of Clubs proposes to the King of Clubs. 401 00:26:11,560 --> 00:26:14,240 But now the King of Clubs has got two proposals 402 00:26:14,240 --> 00:26:17,440 and actually prefers the Queen of Clubs. 403 00:26:17,440 --> 00:26:20,280 So he rejects the Queen of Hearts, his provisional 404 00:26:20,280 --> 00:26:22,920 engagement on the first round of the algorithm, 405 00:26:22,920 --> 00:26:24,440 and we have to start again. 406 00:26:26,000 --> 00:26:28,080 In each round, the rejected queens 407 00:26:28,080 --> 00:26:31,360 propose to the next king on their list. 408 00:26:31,360 --> 00:26:34,480 And the kings always go for the best offer they get. 409 00:26:35,680 --> 00:26:40,000 In this round of the algorithm, she proposes to the King of Hearts 410 00:26:40,000 --> 00:26:44,040 and finally, everyone's paired up with a single queen and king 411 00:26:44,040 --> 00:26:45,960 and all the marriages are stable. 412 00:26:49,120 --> 00:26:53,440 The Gale-Shapley algorithm is now used all over the world. 413 00:26:53,440 --> 00:26:56,840 In Denmark, to match children to day-care places. 414 00:26:56,840 --> 00:27:00,040 In Hungary, to match students to schools. 415 00:27:00,040 --> 00:27:03,440 In New York, to allocate rabbis to synagogues. 416 00:27:03,440 --> 00:27:07,360 And in China, Germany and Spain, to match students to universities. 417 00:27:10,480 --> 00:27:13,560 Whilst in the UK, it's led to the development 418 00:27:13,560 --> 00:27:18,440 of a matching algorithm that, for some people, has saved their lives. 419 00:27:23,040 --> 00:27:26,800 At the age of 20, Seraya in south London was diagnosed 420 00:27:26,800 --> 00:27:31,120 with a chronic kidney disease and told she needed a transplant. 421 00:27:32,880 --> 00:27:37,000 I was on dialysis for 18 months and very unwell. 422 00:27:37,000 --> 00:27:40,240 I couldn't go to work. I had no social life. 423 00:27:40,240 --> 00:27:44,200 It was literally hospital three times a week for treatment and home. 424 00:27:45,440 --> 00:27:47,880 A close friend was willing to donate, 425 00:27:47,880 --> 00:27:50,880 but their tissue types were not compatible. 426 00:27:53,480 --> 00:27:55,840 In St Albans, Tamir was seriously ill 427 00:27:55,840 --> 00:27:58,840 and his wife, Lyndsey, wanted to donate. 428 00:27:58,840 --> 00:28:00,560 But they had the same problem. 429 00:28:02,000 --> 00:28:04,760 We went through all the blood tests and all the workup 430 00:28:04,760 --> 00:28:08,040 and it turned out that we were incompatible blood groups. 431 00:28:10,320 --> 00:28:13,080 Often, kidney patients who are fortunate enough 432 00:28:13,080 --> 00:28:16,080 to have a would-be donor find there's a mismatch 433 00:28:16,080 --> 00:28:18,920 between their donor's blood group or tissue type. 434 00:28:20,720 --> 00:28:26,280 But since 2007, the NHS has been using a special matching algorithm 435 00:28:26,280 --> 00:28:29,160 to find potential matches for willing donors 436 00:28:29,160 --> 00:28:31,480 to kidney patients all over the UK. 437 00:28:35,360 --> 00:28:37,640 When we first looked at this problem, 438 00:28:37,640 --> 00:28:41,320 we really underestimated the complexity. 439 00:28:41,320 --> 00:28:46,360 And originally, we just started with swaps between two pairs. 440 00:28:46,360 --> 00:28:48,120 So it was very simple, 441 00:28:48,120 --> 00:28:53,040 but it soon became obvious that we needed something much more complex. 442 00:28:56,920 --> 00:29:00,000 I became in touch with Rachel Johnson at the NHS 443 00:29:00,000 --> 00:29:02,720 and we then got involved at that stage in being able to design 444 00:29:02,720 --> 00:29:05,560 algorithms which would allow not just pair-wise exchanges, 445 00:29:05,560 --> 00:29:08,120 but also exchanges among three couples, as well. 446 00:29:10,080 --> 00:29:13,080 The algorithm considers several scenarios. 447 00:29:13,080 --> 00:29:15,400 The simplest is a two-way swap 448 00:29:15,400 --> 00:29:18,360 with two couples exchanging kidneys. 449 00:29:21,560 --> 00:29:23,840 More complicated is a three-way swap, 450 00:29:23,840 --> 00:29:26,720 where the kidneys get passed around in a cycle. 451 00:29:29,960 --> 00:29:34,960 There are 200 patients in each of our matching runs. 452 00:29:34,960 --> 00:29:38,960 We need to look for all the possible transplants. 453 00:29:40,200 --> 00:29:42,440 And it's surprising how many there are. 454 00:29:42,440 --> 00:29:44,440 There are literally, you know, hundreds, 455 00:29:44,440 --> 00:29:47,040 sometimes thousands of possibilities. 456 00:29:47,040 --> 00:29:51,400 It's something that just could not be achieved without the algorithm. 457 00:29:53,120 --> 00:29:57,120 One day, Seraya received the call that a match had been found 458 00:29:57,120 --> 00:30:02,200 400 miles away with Linda, a donor living in Bowness near Edinburgh. 459 00:30:03,720 --> 00:30:06,760 My husband's dad needed a new kidney. 460 00:30:06,760 --> 00:30:11,200 He'd been ill for a bit of time. And I wasn't a perfect match. 461 00:30:11,200 --> 00:30:17,000 And I then got a phone call and it was all go from there. 462 00:30:19,120 --> 00:30:20,920 We got the initial phone call saying 463 00:30:20,920 --> 00:30:23,520 we'd been matched up in the three-way pool. 464 00:30:23,520 --> 00:30:26,560 You're just nervous that it's not going to go ahead 465 00:30:26,560 --> 00:30:28,240 because your life depends on it. 466 00:30:29,960 --> 00:30:31,640 For the matching couples, 467 00:30:31,640 --> 00:30:35,080 all the operations had to happen simultaneously. 468 00:30:35,080 --> 00:30:38,280 It was a major logistical challenge. 469 00:30:38,280 --> 00:30:41,360 When my donor went to theatre, they called over to check 470 00:30:41,360 --> 00:30:44,600 that my donor was also in Newcastle going to theatre. 471 00:30:44,600 --> 00:30:46,960 And they both got it at the exact same time. 472 00:30:46,960 --> 00:30:49,400 And they make the call and the kidneys come out. 473 00:30:49,400 --> 00:30:51,160 I think they went by motorbike. 474 00:30:51,160 --> 00:30:53,120 We were told they might go by helicopter, 475 00:30:53,120 --> 00:30:56,680 so I thought at least one bit of me might have been in a helicopter, 476 00:30:56,680 --> 00:30:58,960 but, no, it went by motorbike. 477 00:31:02,880 --> 00:31:06,200 And it eventually went ahead, thankfully, in December. 478 00:31:06,200 --> 00:31:09,160 - The best Christmas present. - Hm! 479 00:31:09,160 --> 00:31:12,440 Personally, I just imagined it was doctors behind there 480 00:31:12,440 --> 00:31:14,880 matching people up off this list. 481 00:31:14,880 --> 00:31:17,640 So, yeah, it's a bit strange 482 00:31:17,640 --> 00:31:20,240 that it comes down to maths at the end of the day. 483 00:31:20,240 --> 00:31:23,720 It's a great scheme and it's still fairly recent. 484 00:31:23,720 --> 00:31:27,120 And many years ago, I wouldn't have had this chance. 485 00:31:27,120 --> 00:31:31,480 I feel a lot of gratitude to Linda and also to the algorithm. 486 00:31:31,480 --> 00:31:33,400 So, yeah, I'm very grateful. 487 00:31:34,680 --> 00:31:39,760 So far, more than 400 patients have benefited from the NHS scheme 488 00:31:39,760 --> 00:31:42,520 and its special matching algorithm. 489 00:31:42,520 --> 00:31:44,840 It was only when we actually seen media articles 490 00:31:44,840 --> 00:31:47,160 and we actually started to think, "Oh, hold on, 491 00:31:47,160 --> 00:31:49,480 "that person might have actually had that match 492 00:31:49,480 --> 00:31:53,080 "through the October matching run's pair-wise exchange," and so on, 493 00:31:53,080 --> 00:31:55,320 that you actually start to see the stories 494 00:31:55,320 --> 00:31:57,200 that are behind the anonymous data. 495 00:31:57,200 --> 00:32:00,560 It's quite funny because David's always really concerned 496 00:32:00,560 --> 00:32:03,400 that the algorithm will take a long time to run. 497 00:32:03,400 --> 00:32:07,280 And, you know, it's been up to 30 minutes and he gets concerned. 498 00:32:07,280 --> 00:32:10,440 But actually, 30 minutes, you know, to us, 499 00:32:10,440 --> 00:32:14,080 it's incredible that it can do all of that in 30 minutes. 500 00:32:25,000 --> 00:32:29,360 So far, we have seen how algorithms are capable of amazing feats. 501 00:32:30,440 --> 00:32:33,520 From solving abstract mathematical problems 502 00:32:33,520 --> 00:32:37,320 to helping us find stuff on the World Wide Web. 503 00:32:37,320 --> 00:32:41,240 And they key thing for all of these algorithms is their speed. 504 00:32:41,240 --> 00:32:44,480 So the important feature of a good algorithm is first 505 00:32:44,480 --> 00:32:47,440 that it'd better be correct, but once you know it's correct, 506 00:32:47,440 --> 00:32:49,400 it's also important that it runs quickly. 507 00:32:49,400 --> 00:32:52,600 There's no good having an algorithm that takes longer 508 00:32:52,600 --> 00:32:57,000 than your lifetime to run if you're wanting the result tomorrow. 509 00:32:58,320 --> 00:33:02,680 This face-detection algorithm is an example of an efficient algorithm. 510 00:33:02,680 --> 00:33:05,840 Because it's efficient, it's able to run in real time. 511 00:33:05,840 --> 00:33:07,720 And that's what makes it useful. 512 00:33:09,640 --> 00:33:14,160 But just as in real life, some problems are harder than others. 513 00:33:14,160 --> 00:33:17,480 Every now and then, algorithms meet their match. 514 00:33:19,200 --> 00:33:21,960 I think the most common misconception about algorithms 515 00:33:21,960 --> 00:33:24,280 is just that algorithms can do anything. 516 00:33:24,280 --> 00:33:27,240 I think people don't really know about the limits. 517 00:33:27,240 --> 00:33:30,760 Some problems simply cannot be solved by efficient algorithms. 518 00:33:32,640 --> 00:33:36,800 There are some places where efficient algorithms cannot go. 519 00:33:36,800 --> 00:33:40,000 Lines in the sand that can't be crossed. 520 00:33:40,000 --> 00:33:43,240 The trouble is knowing which problems they can solve 521 00:33:43,240 --> 00:33:44,680 and which they can't. 522 00:33:48,040 --> 00:33:51,320 Take this Rubik's Cube and imagine the more general challenge 523 00:33:51,320 --> 00:33:54,000 of trying to solve a cube of arbitrary dimensions. 524 00:33:54,000 --> 00:33:57,040 So, for example, with 50 squares down each side. 525 00:33:57,040 --> 00:33:58,520 Now, you might expect this 526 00:33:58,520 --> 00:34:01,600 to be one of the really fiendishly difficult problems, 527 00:34:01,600 --> 00:34:03,960 but actually, it belongs in the easy camp. 528 00:34:03,960 --> 00:34:08,000 We know an algorithm that can solve the general Rubik's Cube 529 00:34:08,000 --> 00:34:09,800 in a reasonable amount of time. 530 00:34:13,320 --> 00:34:14,680 Although it looks hard, 531 00:34:14,680 --> 00:34:17,920 this problem can be cracked by efficient algorithms. 532 00:34:22,800 --> 00:34:25,280 However, here's one that definitely can't. 533 00:34:27,400 --> 00:34:30,320 Imagine you've got a draughts board of arbitrary size 534 00:34:30,320 --> 00:34:32,800 and an arrangement of pieces on the board. 535 00:34:32,800 --> 00:34:34,360 The challenge is to work out 536 00:34:34,360 --> 00:34:38,240 whether white can force a win from this position. 537 00:34:38,240 --> 00:34:40,120 Now, draughts is a pretty easy game, 538 00:34:40,120 --> 00:34:42,400 but it's been mathematically proven 539 00:34:42,400 --> 00:34:46,640 that there's no algorithm that can solve this problem efficiently. 540 00:34:46,640 --> 00:34:49,040 It's an inherently difficult problem. 541 00:34:51,160 --> 00:34:55,600 The only way to solve this puzzle is through sheer hard slog - 542 00:34:55,600 --> 00:34:58,320 working out all the millions of possibilities. 543 00:35:00,080 --> 00:35:04,840 So this problem lies firmly beyond the reach of efficient algorithms. 544 00:35:04,840 --> 00:35:06,520 It can't be solved quickly. 545 00:35:10,240 --> 00:35:14,600 But for some problems, how hard they are is not clear cut. 546 00:35:14,600 --> 00:35:19,080 This is a large sudoku. It's got 625 squares. 547 00:35:20,320 --> 00:35:24,400 One of the nice things about sudoku is that once you've found a solution, 548 00:35:24,400 --> 00:35:28,040 it's relatively straightforward to check whether or not it's right. 549 00:35:28,040 --> 00:35:30,360 And this is true however large the puzzle. 550 00:35:32,360 --> 00:35:34,800 In this case, I've just got to check each row, 551 00:35:34,800 --> 00:35:38,280 column and block doesn't feature a number twice. 552 00:35:38,280 --> 00:35:42,240 Sudoku belongs to a very special category of problems 553 00:35:42,240 --> 00:35:44,840 that all share this characteristic. 554 00:35:44,840 --> 00:35:48,840 Once you've come up with a solution, it's always easy to check it. 555 00:35:49,880 --> 00:35:53,160 The mystery is whether there's an efficient algorithm 556 00:35:53,160 --> 00:35:55,520 to find the solution in the first place. 557 00:35:58,360 --> 00:36:02,520 And sudoku is not alone. There are lots of problems like this. 558 00:36:02,520 --> 00:36:05,040 The most intensely studied of them all 559 00:36:05,040 --> 00:36:08,480 is known as the travelling salesman problem. 560 00:36:13,360 --> 00:36:16,920 A travelling salesman travels door to door, city to city, 561 00:36:16,920 --> 00:36:20,480 selling anything from brushes and Hoovers to double-glazing. 562 00:36:22,520 --> 00:36:25,000 It sounds like a straightforward job. 563 00:36:25,000 --> 00:36:28,880 But all travelling salesmen face the same question. 564 00:36:28,880 --> 00:36:31,560 What's the shortest route to take? 565 00:36:33,520 --> 00:36:37,400 So important is this problem that the Clay Mathematics Institute 566 00:36:37,400 --> 00:36:42,120 has offered 1 million for whoever can find an efficient algorithm, 567 00:36:42,120 --> 00:36:44,520 or prove that none exists. 568 00:36:46,400 --> 00:36:49,000 The travelling salesman problem goes like this. 569 00:36:49,000 --> 00:36:50,520 Imagine you're a salesman 570 00:36:50,520 --> 00:36:55,120 and you've got to visit a list of cities represented by the red dots. 571 00:36:55,120 --> 00:36:57,640 The challenge is to find the shortest route 572 00:36:57,640 --> 00:37:02,040 so you visit each city once before returning to your starting point. 573 00:37:02,040 --> 00:37:04,520 Now, you might imagine the best thing is 574 00:37:04,520 --> 00:37:07,520 to just consider all the routes, like this. 575 00:37:13,960 --> 00:37:18,560 The method of checking all possibilities is a type of algorithm. 576 00:37:18,560 --> 00:37:20,440 And for three cities, it works fine 577 00:37:20,440 --> 00:37:23,640 because there are only three possible routes to check. 578 00:37:27,080 --> 00:37:30,200 But what if we add two more cities to the list? 579 00:37:32,920 --> 00:37:36,360 With five cities, there are 60 different possible routes. 580 00:37:39,160 --> 00:37:44,040 And if we add another city, then there are 360 possible routes. 581 00:37:44,040 --> 00:37:49,320 And for ten cities, there are over 1.8 million possible routes. 582 00:37:49,320 --> 00:37:51,600 If our algorithm chugged through them, 583 00:37:51,600 --> 00:37:54,720 checking all of these at a rate of ten per second, 584 00:37:54,720 --> 00:37:58,320 it would take two days before it found the shortest. 585 00:37:58,320 --> 00:38:01,720 So you can see a method of trying all the different possibilities, 586 00:38:01,720 --> 00:38:06,440 a kind of brute-force algorithm, if you like, is just simply impractical. 587 00:38:07,720 --> 00:38:10,880 If somebody found a fast algorithm for the travelling salesman problem, 588 00:38:10,880 --> 00:38:12,280 it would be hugely significant. 589 00:38:12,280 --> 00:38:15,240 If one of my students came up with an efficient algorithm 590 00:38:15,240 --> 00:38:17,320 for the travelling salesman problem, 591 00:38:17,320 --> 00:38:20,280 I would get him to explain it to me, 592 00:38:20,280 --> 00:38:23,200 I would kill him and then I'd go and claim 593 00:38:23,200 --> 00:38:25,720 the Clay prize, 1 million. 594 00:38:25,720 --> 00:38:28,360 But I think my students are safe. 595 00:38:29,680 --> 00:38:32,680 The problem crops up in lots of areas. 596 00:38:32,680 --> 00:38:35,000 From soldering circuit boards... 597 00:38:37,360 --> 00:38:40,680 ..to planning the routes for supermarket deliveries. 598 00:38:40,680 --> 00:38:45,320 But has the travelling salesman problem secretly already been solved? 599 00:38:49,960 --> 00:38:54,080 A team of scientists working at Rothamsted Research in Harpenden 600 00:38:54,080 --> 00:38:57,520 have turned to nature to see if it has found the answer. 601 00:39:03,200 --> 00:39:06,160 They're carrying out an elaborate experiment to study 602 00:39:06,160 --> 00:39:10,320 how the travelling salesman problem is tackled by the bumblebee. 603 00:39:13,480 --> 00:39:17,680 Bees have to forage for nectar in order to provision their hive. 604 00:39:17,680 --> 00:39:19,920 And so they have to visit 605 00:39:19,920 --> 00:39:22,520 possibly hundreds of flowers on each trip. 606 00:39:22,520 --> 00:39:25,240 What they want to do is find an efficient way 607 00:39:25,240 --> 00:39:28,040 to go between all these flowers that they visit. 608 00:39:31,360 --> 00:39:35,680 The humble bumblebee faces its own travelling salesman problem. 609 00:39:35,680 --> 00:39:38,360 The flowers are just like the cities. 610 00:39:38,360 --> 00:39:41,480 And the bee is the travelling salesman. 611 00:39:41,480 --> 00:39:45,600 One bee will go out foraging many, many times every day. 612 00:39:45,600 --> 00:39:47,360 So over the course of a day, 613 00:39:47,360 --> 00:39:51,680 it really helps to take the most efficient possible route. 614 00:39:51,680 --> 00:39:53,920 So what we're doing is trying to figure out 615 00:39:53,920 --> 00:39:58,000 exactly what rules they're using to narrow down the possibilities. 616 00:40:00,480 --> 00:40:04,160 Joe has laid out five feeders which play the role of flowers. 617 00:40:05,560 --> 00:40:10,200 Each feeder has just enough nectar to ensure the bee has to visit all five 618 00:40:10,200 --> 00:40:12,360 to give it a full honey stomach. 619 00:40:13,560 --> 00:40:16,280 And how are you actually knowing where it's going? 620 00:40:16,280 --> 00:40:18,960 For this, we're using a harmonic radar. 621 00:40:18,960 --> 00:40:22,280 So as that spins round and round, it's emitting a radar signal. 622 00:40:22,280 --> 00:40:25,200 And we've attached a small antenna to the back of the bee, 623 00:40:25,200 --> 00:40:27,880 which then reflects the signal from the radar. 624 00:40:27,880 --> 00:40:31,200 And so this allows us to see exactly where the bee has gone 625 00:40:31,200 --> 00:40:32,800 as she moves around the field. 626 00:40:34,240 --> 00:40:38,000 So, how does the bumblebee tackle the travelling salesman problem? 627 00:40:38,000 --> 00:40:40,120 OK, we're switching it on now. 628 00:40:47,080 --> 00:40:51,600 With five feeders, there are a total of 60 possible routes. 629 00:40:51,600 --> 00:40:54,480 The shortest is around the outer edge. 630 00:40:58,040 --> 00:41:02,520 This heat map shows the path taken by a single bee. 631 00:41:02,520 --> 00:41:06,240 At first, it's simply discovering the positions of the feeders. 632 00:41:07,920 --> 00:41:12,360 Then the bee appears to methodically change different parts of the route 633 00:41:12,360 --> 00:41:14,680 to see if it can make it shorter. 634 00:41:16,920 --> 00:41:20,760 Within 20 trips, it's honed in on an efficient route. 635 00:41:26,480 --> 00:41:29,840 This route is not always the absolute shortest, 636 00:41:29,840 --> 00:41:31,760 but, for the bee, it's good enough. 637 00:41:36,440 --> 00:41:40,040 That's amazing that just after a very few tries, they've got 638 00:41:40,040 --> 00:41:44,040 to something which is efficient enough for them to do their foraging. 639 00:41:44,040 --> 00:41:47,920 Yes, that's right. They can't spend days or even, you know, 640 00:41:47,920 --> 00:41:50,560 it could take months or years to try every possibility. 641 00:41:50,560 --> 00:41:52,920 So they have to very quickly find a route 642 00:41:52,920 --> 00:41:55,680 that they can do again and again and again 643 00:41:55,680 --> 00:41:59,800 - in order to efficiently provide food. - Fantastic. 644 00:41:59,800 --> 00:42:01,960 I think the bee's become my favourite insect now. 645 00:42:01,960 --> 00:42:05,520 - It's obviously a mathematician at heart. - Absolutely. 646 00:42:06,920 --> 00:42:11,640 Let's be clear. Bees are not about to be awarded 1 million. 647 00:42:11,640 --> 00:42:15,120 They've not miraculously solved the travelling salesman problem 648 00:42:15,120 --> 00:42:18,080 because they don't always find the shortest route. 649 00:42:19,400 --> 00:42:21,760 But their algorithm is a clever approach. 650 00:42:21,760 --> 00:42:25,080 In maths, it's known as heuristics. 651 00:42:25,080 --> 00:42:29,320 Algorithms that are efficient, that don't find the perfect solution, 652 00:42:29,320 --> 00:42:31,080 but get as close as they can. 653 00:42:44,520 --> 00:42:46,720 The same heuristic approach 654 00:42:46,720 --> 00:42:49,960 has been used to develop an algorithm for Heathrow airport. 655 00:42:51,400 --> 00:42:54,040 DISPATCHER: 'Clear for takeoff...' 656 00:42:54,040 --> 00:42:57,880 Heathrow handles over 1,300 flights a day. 657 00:42:57,880 --> 00:43:00,000 It's Europe's busiest airport. 658 00:43:00,000 --> 00:43:04,640 '..430 clear for takeoff. Surface wind 247 degrees at three knots.' 659 00:43:12,840 --> 00:43:15,120 The challenge for air traffic control 660 00:43:15,120 --> 00:43:18,640 is to maximise the number of aircraft departing every hour 661 00:43:18,640 --> 00:43:22,800 and ensure that the airport operates both efficiently and safely. 662 00:43:22,800 --> 00:43:29,400 '..behind the British Airways 747, line up 27 right behind.' 663 00:43:29,400 --> 00:43:33,520 One of the key decisions is the order of takeoff. 664 00:43:33,520 --> 00:43:36,680 We're currently departing a group of medium aircraft, 665 00:43:36,680 --> 00:43:39,680 which will be separated one minute apart. 666 00:43:39,680 --> 00:43:43,400 Behind that, then, you can see a 747, which is a large aircraft. 667 00:43:44,800 --> 00:43:48,200 Medium aircraft need to be separated from the turbulence 668 00:43:48,200 --> 00:43:50,360 produced by larger aircraft. 669 00:43:50,360 --> 00:43:52,720 So the ordering of sizes is crucial. 670 00:43:53,800 --> 00:43:56,120 The ideal sequence for takeoff involves 671 00:43:56,120 --> 00:43:58,840 really blocking together groups of aircraft. 672 00:43:58,840 --> 00:44:01,080 So you want large aircraft to be grouped together, 673 00:44:01,080 --> 00:44:03,440 medium aircraft to be grouped together. 674 00:44:03,440 --> 00:44:05,240 And that allows the separation 675 00:44:05,240 --> 00:44:07,640 between those aircraft to be minimised. 676 00:44:10,640 --> 00:44:14,160 The other factor that needs to be considered where planning takeoff 677 00:44:14,160 --> 00:44:16,040 is where the planes are heading. 678 00:44:19,920 --> 00:44:22,320 We want one to be going to the north, one to the south, 679 00:44:22,320 --> 00:44:24,360 the next going to the north, then the south. 680 00:44:24,360 --> 00:44:29,040 If all the aircraft were going in the same direction, the separation would be much greater 681 00:44:29,040 --> 00:44:31,560 and we wouldn't use the runways as efficiently. 682 00:44:31,560 --> 00:44:34,600 All controllers are sitting in the control towers thinking, 683 00:44:34,600 --> 00:44:37,880 "I've all these aircraft going north, all these going south. 684 00:44:37,880 --> 00:44:39,640 "I've got these that are large ones, 685 00:44:39,640 --> 00:44:42,200 "so I want to try and group all the large ones together 686 00:44:42,200 --> 00:44:44,600 "so I don't have to go from a large one to a small one." 687 00:44:44,600 --> 00:44:48,000 And it's a very complex problem to solve in their heads. 688 00:44:48,000 --> 00:44:50,440 '..906 November...' 689 00:44:50,440 --> 00:44:54,280 In 2013, an algorithm joined the team. 690 00:44:54,280 --> 00:44:58,240 Its job is to predict the most likely order for takeoff 691 00:44:58,240 --> 00:45:00,400 and advise air traffic control 692 00:45:00,400 --> 00:45:03,240 when aircraft should push back from the gates. 693 00:45:03,240 --> 00:45:06,240 To do this involves nothing less than simulating 694 00:45:06,240 --> 00:45:09,480 the entire outward-bound operation of the airport. 695 00:45:11,280 --> 00:45:14,240 Carrying out millions of calculations every second. 696 00:45:14,240 --> 00:45:17,040 FAINT DISPATCHER 697 00:45:21,720 --> 00:45:25,080 The algorithm works by trying to predict 698 00:45:25,080 --> 00:45:28,360 what order the aircraft are going to take off in. 699 00:45:28,360 --> 00:45:30,640 If it knows what order they can take off in, 700 00:45:30,640 --> 00:45:32,560 then it can work backwards and say, 701 00:45:32,560 --> 00:45:34,600 "If it needs to take off at this time, 702 00:45:34,600 --> 00:45:37,480 "then it needs to enter the runway queue at this time, 703 00:45:37,480 --> 00:45:39,840 "then it needs finishing its taxi at this time, 704 00:45:39,840 --> 00:45:42,520 "so it needs to start its taxi operation at this time. 705 00:45:42,520 --> 00:45:45,480 "In that case, it needs to finish its pushback by this time, 706 00:45:45,480 --> 00:45:47,600 "so it needs to start its pushback by this time." 707 00:45:47,600 --> 00:45:50,600 And it can work all the way back from what time it should take off 708 00:45:50,600 --> 00:45:52,640 to what time it should start pushing back. 709 00:45:55,440 --> 00:45:58,720 The output of the algorithm is given to air traffic control 710 00:45:58,720 --> 00:46:01,560 through the airport's internal computer system 711 00:46:01,560 --> 00:46:05,800 and displayed to the pilot at the gate in the form of the TSAT, 712 00:46:05,800 --> 00:46:07,800 the recommended pushback time. 713 00:46:10,000 --> 00:46:12,800 The pilot can look on the stand-entry system 714 00:46:12,800 --> 00:46:15,960 to actually see what time he is expecting to depart. 715 00:46:17,880 --> 00:46:21,200 The biggest benefit of the algorithm is that it means you can 716 00:46:21,200 --> 00:46:25,040 hold aircraft on stand for longer without them taking off any later. 717 00:46:25,040 --> 00:46:28,440 So there's no loss for any passengers in terms of delays. 718 00:46:28,440 --> 00:46:30,840 What you can do is you can start your engines later. 719 00:46:33,080 --> 00:46:35,480 In actual fact, if we save two minutes' taxi time 720 00:46:35,480 --> 00:46:37,840 on the way to the end of the runway, over a year, 721 00:46:37,840 --> 00:46:40,520 that's actually AŁ15 million worth of fuel savings. 722 00:46:42,280 --> 00:46:46,240 The Heathrow sequencing algorithm shows just what can be accomplished 723 00:46:46,240 --> 00:46:47,920 with the heuristic approach. 724 00:46:49,040 --> 00:46:52,320 Just like the bees, the algorithm is not finding 725 00:46:52,320 --> 00:46:55,360 the absolute perfect solution all the time, 726 00:46:55,360 --> 00:46:58,720 but nevertheless makes a tough job that bit easier. 727 00:47:00,320 --> 00:47:02,080 We're very proud of the algorithm 728 00:47:02,080 --> 00:47:05,720 because it actually now, we feel, models the real world and is of use. 729 00:47:16,120 --> 00:47:19,080 In the beginning, algorithms were created 730 00:47:19,080 --> 00:47:21,640 by mathematicians for mathematicians. 731 00:47:21,640 --> 00:47:23,800 And over the last century, 732 00:47:23,800 --> 00:47:26,400 algorithms have been created for computers. 733 00:47:29,240 --> 00:47:33,960 But perhaps our relationship is about to go through a dramatic revolution. 734 00:47:39,720 --> 00:47:41,920 At Microsoft Research in Cambridge, 735 00:47:41,920 --> 00:47:46,360 scientists are using new techniques to develop algorithms... 736 00:47:46,360 --> 00:47:50,400 blurring the boundary between inventor and the algorithm itself. 737 00:47:56,600 --> 00:47:59,920 This is the Kinect skeletal-tracking algorithm. 738 00:47:59,920 --> 00:48:02,760 The amazing thing is that it's able to identify 739 00:48:02,760 --> 00:48:04,920 the different parts of my body. 740 00:48:04,920 --> 00:48:08,360 So you can see it's coloured the top of my head in red 741 00:48:08,360 --> 00:48:11,040 and my right hand here in blue. 742 00:48:11,040 --> 00:48:13,560 You can see it's coloured my neck green. 743 00:48:13,560 --> 00:48:16,080 Now, this algorithm has never met me before, 744 00:48:16,080 --> 00:48:18,760 doesn't know how I'm going to move in space, 745 00:48:18,760 --> 00:48:22,040 but just using the data coming from this special camera here, 746 00:48:22,040 --> 00:48:25,520 measuring the distance from the camera to my body, 747 00:48:25,520 --> 00:48:28,120 it's able to produce this map. 748 00:48:30,520 --> 00:48:33,960 Whatever posture I take, using nothing more than the input 749 00:48:33,960 --> 00:48:36,360 from the special depth-sensing camera, 750 00:48:36,360 --> 00:48:39,360 the algorithm is able to accurately identify, 751 00:48:39,360 --> 00:48:42,760 pixel by pixel, the different parts of my body. 752 00:48:46,640 --> 00:48:49,720 It was developed for the Microsoft Xbox console 753 00:48:49,720 --> 00:48:53,640 to track the movement of a player's body posture in real time. 754 00:48:58,440 --> 00:49:01,600 But just as remarkable as what this algorithm can do 755 00:49:01,600 --> 00:49:04,480 is the process behind how it was created, 756 00:49:04,480 --> 00:49:07,080 as researcher Jamie Shotton explains. 757 00:49:09,640 --> 00:49:12,640 What's happening is that every pixel in the image, 758 00:49:12,640 --> 00:49:16,080 we are running an algorithm called a decision tree. 759 00:49:16,080 --> 00:49:19,520 And you can think of a decision tree as a game of 20 questions. 760 00:49:19,520 --> 00:49:22,560 So the decision tree is sort of taking a pixel, say, on my hand, 761 00:49:22,560 --> 00:49:25,320 and trying to decide, OK, I've got to colour that blue 762 00:49:25,320 --> 00:49:28,480 - because that's on the hand rather than on my body. - Yes. 763 00:49:28,480 --> 00:49:31,200 The key to a decision tree is the fact that the 20 questions 764 00:49:31,200 --> 00:49:33,880 that you ask are not the same 765 00:49:33,880 --> 00:49:37,000 for every pixel that we're trying to classify. 766 00:49:37,000 --> 00:49:39,680 And the full set of the possible questions 767 00:49:39,680 --> 00:49:43,080 that could be answered is exponential. 768 00:49:43,080 --> 00:49:46,360 - It's two to the twenty. - Right, OK. That's over a million questions, 769 00:49:46,360 --> 00:49:49,240 a lot of questions you're going to have to program in there. 770 00:49:49,240 --> 00:49:51,080 Yes. It would take far too long 771 00:49:51,080 --> 00:49:55,120 and be far too error-prone for us as humans to program that by hand. 772 00:49:55,120 --> 00:49:58,760 - So, the algorithm's kind of writing itself, or...? - Absolutely. 773 00:50:02,960 --> 00:50:05,520 The algorithm was not designed by Jamie 774 00:50:05,520 --> 00:50:08,960 but instead through a process called machine learning. 775 00:50:11,440 --> 00:50:15,720 It involved showing the algorithm millions of training images, 776 00:50:15,720 --> 00:50:19,320 of bodies in different poses and of various shapes and sizes, 777 00:50:19,320 --> 00:50:23,600 from the very fat to the very thin, the very short to the very tall. 778 00:50:24,640 --> 00:50:28,880 And from this, the algorithm essentially learned by example, 779 00:50:28,880 --> 00:50:31,040 devising its own rules. 780 00:50:34,200 --> 00:50:37,760 Where our intelligence comes in as the designers of the system 781 00:50:37,760 --> 00:50:41,240 is not in programming the algorithm, per se, 782 00:50:41,240 --> 00:50:44,200 but in designing the training data set 783 00:50:44,200 --> 00:50:48,160 to capture all of the kind of variations that we expect to see 784 00:50:48,160 --> 00:50:51,040 when we deploy this system in people's living rooms 785 00:50:51,040 --> 00:50:52,360 to play their games. 786 00:50:52,360 --> 00:50:55,600 So in the end, do you actually know what the algorithm is doing? 787 00:50:55,600 --> 00:50:57,800 We can get a sense of what it's trying to do 788 00:50:57,800 --> 00:50:59,400 and how it's roughly working, 789 00:50:59,400 --> 00:51:02,960 but we couldn't possibly really understand what exactly is going on. 790 00:51:04,960 --> 00:51:09,920 The same approach of machine learning has been used in other applications. 791 00:51:09,920 --> 00:51:14,680 For example, this algorithm is able to do something that for a long time 792 00:51:14,680 --> 00:51:19,560 was thought to be a skill exclusive to neurosurgeons and radiologists. 793 00:51:19,560 --> 00:51:22,800 From an MRI scan, the algorithm can identify 794 00:51:22,800 --> 00:51:26,480 and map a brain tumour in 3-D. 795 00:51:26,480 --> 00:51:29,280 Meaning that a job that normally takes an hour 796 00:51:29,280 --> 00:51:31,360 can be done in a matter of minutes. 797 00:51:34,640 --> 00:51:37,640 Professor Chris Bishop is interested in developing 798 00:51:37,640 --> 00:51:40,880 the concept of machine learning even further. 799 00:51:40,880 --> 00:51:44,680 To create algorithms that can learn just like we do, 800 00:51:44,680 --> 00:51:46,600 directly from experience. 801 00:51:49,160 --> 00:51:52,120 So this demonstration, I think, illustrates the direction 802 00:51:52,120 --> 00:51:54,120 that algorithms will go in the years ahead. 803 00:51:54,120 --> 00:51:57,640 OK, I can see a lot of films up here, so what is the algorithm going to do? 804 00:51:57,640 --> 00:52:00,760 We've got a couple of hundred of the most commonly watched films, 805 00:52:00,760 --> 00:52:02,240 and what it's going to do, 806 00:52:02,240 --> 00:52:06,600 it's going to learn about your personal likes and dislikes. 807 00:52:06,600 --> 00:52:08,080 It's already been trained, 808 00:52:08,080 --> 00:52:11,080 so it's a machine-learning algorithm behind the scenes, 809 00:52:11,080 --> 00:52:14,480 but it's already been trained on data from about 10,000 people. 810 00:52:14,480 --> 00:52:18,160 What it's going to do now is to learn about your preferences. 811 00:52:18,160 --> 00:52:20,200 At the moment it knows nothing about you, 812 00:52:20,200 --> 00:52:22,760 so these films are just arranged at random on the screen. 813 00:52:22,760 --> 00:52:25,440 What I need you to do is to find one of these films, 814 00:52:25,440 --> 00:52:28,120 either one that you like or one that you don't like. 815 00:52:28,120 --> 00:52:31,160 If you like it, you can drag it across to the green region, 816 00:52:31,160 --> 00:52:33,600 if you don't like it, across to the red region. 817 00:52:33,600 --> 00:52:35,600 Rushmore, I'm a big fan of Rushmore. 818 00:52:35,600 --> 00:52:37,560 You like Rushmore? OK, right. 819 00:52:37,560 --> 00:52:41,120 So what's happening now is that if a film is down the right-hand side 820 00:52:41,120 --> 00:52:44,760 - near the green region, it's very confident you'll like it. - OK. 821 00:52:44,760 --> 00:52:46,600 So down here close to the red region, 822 00:52:46,600 --> 00:52:48,560 it's very confident you won't like it. 823 00:52:48,560 --> 00:52:51,400 In the middle, it's 50-50. It doesn't really know. 824 00:52:51,400 --> 00:52:54,320 So if I choose a movie in the middle here, 825 00:52:54,320 --> 00:52:57,680 I'm not a great Austin Powers fan, so let's shoot that one... 826 00:52:57,680 --> 00:53:00,800 So you see, they're beginning to spread out sideways, 827 00:53:00,800 --> 00:53:04,480 - it's going to be a little bit more confident. - It's pretty good. 828 00:53:04,480 --> 00:53:07,480 I'm a big fan of Dr Strangelove 829 00:53:07,480 --> 00:53:11,480 and I'm a big fan of Woody Allen, 830 00:53:11,480 --> 00:53:14,520 but Spinal Tap, it thinks I'll like that. 831 00:53:14,520 --> 00:53:18,040 So that's interesting, so when it was confident you liked them 832 00:53:18,040 --> 00:53:19,800 and you said you liked them, 833 00:53:19,800 --> 00:53:22,920 not much happened because it didn't learn much. 834 00:53:22,920 --> 00:53:25,840 When it was confident you'd like it, in the case of Spinal Tap 835 00:53:25,840 --> 00:53:28,280 and you said, "I don't like it," there was a big change. 836 00:53:28,280 --> 00:53:30,200 It's learning things from me. 837 00:53:30,200 --> 00:53:33,080 I'm actually changing the algorithm as I interact with it. 838 00:53:33,080 --> 00:53:36,520 Exactly. Whereas Kinect was trained in the laboratory and then frozen, 839 00:53:36,520 --> 00:53:38,560 this algorithm continues to adapt 840 00:53:38,560 --> 00:53:41,280 and continues to evolve throughout its life. 841 00:53:41,280 --> 00:53:44,120 The more films that you rate as like and don't like, 842 00:53:44,120 --> 00:53:45,960 the more it knows about you personally 843 00:53:45,960 --> 00:53:48,760 and the better able it is to make good recommendations. 844 00:53:48,760 --> 00:53:52,320 This algorithm is beginning to feel much more human 845 00:53:52,320 --> 00:53:54,840 in the way that it interacts with the world. 846 00:53:54,840 --> 00:53:57,840 Is that your aim, to find a way to produce algorithms 847 00:53:57,840 --> 00:54:00,560 that are a bit like the way that we negotiate the world? 848 00:54:00,560 --> 00:54:03,720 Exactly. It's a step down that very long road to producing machines 849 00:54:03,720 --> 00:54:05,880 that really are as capable as the human brain. 850 00:54:05,880 --> 00:54:08,720 We've a long way to go, but this is a small step in that direction 851 00:54:08,720 --> 00:54:10,160 because it's not fixed any more. 852 00:54:10,160 --> 00:54:12,480 It's now continuing to learn just the same way 853 00:54:12,480 --> 00:54:14,800 that we continue to learn in our daily lives. 854 00:54:19,680 --> 00:54:21,680 I think we're just starting 855 00:54:21,680 --> 00:54:24,240 to realise the full potential of algorithms 856 00:54:24,240 --> 00:54:26,600 and I have one more place I want to visit, 857 00:54:26,600 --> 00:54:28,840 which I'm told will give me a glimpse 858 00:54:28,840 --> 00:54:31,760 of just how much they are able to do for us. 859 00:54:40,600 --> 00:54:43,600 It's a world where almost everything is automated. 860 00:54:46,920 --> 00:54:49,400 Where algorithms are in control. 861 00:54:49,400 --> 00:54:53,920 It's the largest automated grocery warehouse on earth. 862 00:54:53,920 --> 00:54:57,520 It belongs to the online grocery retailer Ocado 863 00:54:57,520 --> 00:55:01,000 and it's the equivalent of 45 supermarkets in one. 864 00:55:02,720 --> 00:55:06,600 Over two million items flow through this warehouse every day. 865 00:55:06,600 --> 00:55:10,360 At any one time, there are something like 7,000 crates 866 00:55:10,360 --> 00:55:12,800 going over 25 kilometres of track, 867 00:55:12,800 --> 00:55:18,360 and controlling every aspect of this astonishing spectacle are algorithms. 868 00:55:25,520 --> 00:55:29,120 Each of those red crates is part of a customer order 869 00:55:29,120 --> 00:55:32,880 and they may go on from here to find other items 870 00:55:32,880 --> 00:55:35,160 that they want across the warehouse, 871 00:55:35,160 --> 00:55:37,280 until they are eventually finished, 872 00:55:37,280 --> 00:55:41,360 loaded onto a van and then driven out by our routing system 873 00:55:41,360 --> 00:55:43,720 on a route, which in many ways, 874 00:55:43,720 --> 00:55:47,360 is solving problems like the travelling salesman problem. 875 00:55:47,360 --> 00:55:49,720 There are decisions being made all over the place 876 00:55:49,720 --> 00:55:52,240 as a red crate goes this way and then that way. 877 00:55:52,240 --> 00:55:55,600 The complexity behind all this is beyond 878 00:55:55,600 --> 00:55:58,760 what any human could control or solve, 879 00:55:58,760 --> 00:56:01,760 and that is where these algorithms, 880 00:56:01,760 --> 00:56:03,960 these problem-solving techniques come in 881 00:56:03,960 --> 00:56:05,920 to overcome those challenges. 882 00:56:11,000 --> 00:56:15,480 Everywhere you look, the invisible hand of the algorithm is at work. 883 00:56:16,560 --> 00:56:20,360 Forecasting algorithms monitor and replenish the stock 884 00:56:20,360 --> 00:56:24,720 of more than 43,000 products, anticipating customer demand. 885 00:56:26,760 --> 00:56:29,840 Control system algorithms manage the traffic 886 00:56:29,840 --> 00:56:33,320 of the more than 7,000 crates around the warehouse. 887 00:56:36,360 --> 00:56:39,800 And van routing algorithms control the movement of the fleet 888 00:56:39,800 --> 00:56:41,960 of over 1,500 vans, 889 00:56:41,960 --> 00:56:46,240 testing over four million different route combinations every second. 890 00:56:48,120 --> 00:56:51,160 You can almost see the mind of the machine at work 891 00:56:51,160 --> 00:56:54,360 and it's not a static process, so that's why there is a huge amount 892 00:56:54,360 --> 00:56:59,520 of machine learning in here, so it's like a self-adapting organism. 893 00:56:59,520 --> 00:57:02,200 It's constantly having to learn how to do it better. 894 00:57:02,200 --> 00:57:04,360 People couldn't do that. 895 00:57:04,360 --> 00:57:06,600 The machine has to tune itself. 896 00:57:10,640 --> 00:57:14,080 So who would you say was actually in control of the whole thing? 897 00:57:14,080 --> 00:57:17,400 Ultimately, it's the algorithms that are in control. 898 00:57:17,400 --> 00:57:19,960 I think I'm getting algorithmic hot flushes 899 00:57:19,960 --> 00:57:22,080 by looking at this amazing thing! 900 00:57:24,440 --> 00:57:26,560 In some sense, this warehouse is like 901 00:57:26,560 --> 00:57:28,880 a little microcosm of the modern world. 902 00:57:28,880 --> 00:57:32,640 Algorithms are running everything from search engines on the internet, 903 00:57:32,640 --> 00:57:35,680 sat nav, even keeping our credit cards secure. 904 00:57:35,680 --> 00:57:39,680 Our world wouldn't function without the power of these algorithms. 905 00:57:45,440 --> 00:57:48,920 The Open University have produced a free pack for you to learn, 906 00:57:48,920 --> 00:57:52,880 create and discover more about digital technology past and present. 907 00:57:52,880 --> 00:57:55,280 To order your copy, phone... 908 00:57:58,560 --> 00:58:00,080 ..or follow the link below 909 00:58:00,080 --> 00:58:01,680 to the Open University.