0:00:04 > 0:00:07Without us noticing, modern life has been taken over.
0:00:10 > 0:00:14As we search for love, shop online,
0:00:14 > 0:00:18travel the world,
0:00:18 > 0:00:20even as we save lives,
0:00:20 > 0:00:25there are step-by-step instructions working quietly behind the scenes.
0:00:27 > 0:00:30More and more, they are ruling our lives.
0:00:30 > 0:00:33They're called algorithms.
0:00:34 > 0:00:36Algorithms are everywhere.
0:00:36 > 0:00:39These bite-sized chunks of maths have become central
0:00:39 > 0:00:41to our daily lives.
0:00:41 > 0:00:44But because they are invisible, we tend to take them for granted,
0:00:44 > 0:00:46even misunderstand them.
0:00:50 > 0:00:52LAUGHTER
0:00:53 > 0:00:57They are the secret to our digital world, and so much more.
0:00:58 > 0:01:02'In this programme, I'm going to show you some of my favourite
0:01:02 > 0:01:05'algorithms to reveal where they came from...'
0:01:05 > 0:01:08Algorithms are ancient.
0:01:08 > 0:01:09'..how they work...'
0:01:09 > 0:01:11The challenge is to find the shortest route...
0:01:11 > 0:01:14These are the rough instructions that you would use.
0:01:14 > 0:01:17..for returning to your starting point.
0:01:17 > 0:01:20'..what they might be able to do in the future.'
0:01:20 > 0:01:23- The algorithm's kind of writing itself? Or...?- Absolutely.
0:01:23 > 0:01:26'..and how we can't live without them.'
0:01:26 > 0:01:29Even when we're baking a cake, we're following an algorithm.
0:01:29 > 0:01:32As a mathematician, I love algorithms.
0:01:32 > 0:01:35Not only are they impressive problem solvers,
0:01:35 > 0:01:38but also strangely beautiful, tapping into the mathematical
0:01:38 > 0:01:42order that underpins how the universe works.
0:01:42 > 0:01:45Welcome to the weird and wonderful world of algorithms.
0:01:54 > 0:01:57Most of us carry one of these around.
0:01:57 > 0:02:00Now, you might have noticed that when you take a photo
0:02:00 > 0:02:05with your phone, then it draws a box around any face, like this.
0:02:05 > 0:02:09This is the result of a special face-detection algorithm
0:02:09 > 0:02:13and it helps to keep the face in the photo in focus.
0:02:14 > 0:02:18'Like all algorithms, this one solves a problem.
0:02:18 > 0:02:21'In this case, finding a human face.
0:02:21 > 0:02:24'While it's not fooled by a face made of fruit,
0:02:24 > 0:02:28'it does detect a human face in a photo.
0:02:28 > 0:02:31'So, how does it do it?
0:02:31 > 0:02:34'At their root, algorithms are little more than
0:02:34 > 0:02:37'a series of step-by-step instructions.
0:02:37 > 0:02:40'This one works by methodically scanning the image
0:02:40 > 0:02:43'looking for four particular abstract patterns
0:02:43 > 0:02:45'associated with a face.
0:02:45 > 0:02:48'When these are detected one after another,
0:02:48 > 0:02:52'then the algorithm indicates it's found a human face.'
0:02:52 > 0:02:56The process taps into the underlying pattern behind all faces,
0:02:56 > 0:02:59no matter what shape or size.
0:02:59 > 0:03:02The end result is just one example of how algorithms have
0:03:02 > 0:03:05made our lives easier.
0:03:05 > 0:03:09- I'll do it!- I'll do it!- I was here first!- OK.
0:03:09 > 0:03:10So, off you go.
0:03:10 > 0:03:14'We tend to associate algorithms with computers, smartphones
0:03:14 > 0:03:15'and the internet.
0:03:15 > 0:03:19'But they are not exclusive to the world of technology.
0:03:19 > 0:03:24'My day job is Professor of Mathematics at Oxford University.
0:03:24 > 0:03:26'And one of the things I enjoy most is keeping
0:03:26 > 0:03:29'the students on their toes.'
0:03:29 > 0:03:31OK, I'll take one.
0:03:31 > 0:03:33Here, we're playing a mathematical game with a jar
0:03:33 > 0:03:37full of chocolates and one red hot chilli.
0:03:38 > 0:03:42'The aim is not to be left with the chilli at the end.
0:03:42 > 0:03:44'But what these students don't know,
0:03:44 > 0:03:49'is that I'm playing it with the help of an algorithm.'
0:03:49 > 0:03:51- OK. Ready? BOTH:- Yeah.
0:03:51 > 0:03:54Right, I'm going to go first, so remember, you can take one,
0:03:54 > 0:03:57two or three chocolates at a time.
0:03:57 > 0:04:00I'm not a greedy guy, so I'll just take one. Now, your turn.
0:04:00 > 0:04:05'Each player takes on their turn, between one and three chocolates.'
0:04:05 > 0:04:09You've taken two, OK. So, I'm going to take... I'll take two.
0:04:09 > 0:04:12'Whatever my opponent does, my algorithm that tells me
0:04:12 > 0:04:14'how to respond.'
0:04:14 > 0:04:16OK, I'll take two.
0:04:16 > 0:04:19And your turn again. SHE LAUGHS
0:04:19 > 0:04:20Oh, yeah.
0:04:20 > 0:04:24- So I'll take...three.- Three. And I'll take one.
0:04:24 > 0:04:27- And just a chilli left...- So, wait. Is that me?- Yeah, so you have
0:04:27 > 0:04:29- to eat the chilli.- Oh, no! - So, there you go.
0:04:29 > 0:04:32'Let me reveal how the algorithm I was using helped me win.'
0:04:32 > 0:04:34It's the only way to learn.
0:04:35 > 0:04:40So, the key is to think about grouping things in fours.
0:04:41 > 0:04:4613 chocolates divides into three groups of four, with one left over.
0:04:46 > 0:04:50So, by taking one chocolate in the first round and then four
0:04:50 > 0:04:54minus whatever the other player takes in the subsequent rounds,
0:04:54 > 0:04:57this algorithm ensures that the other player
0:04:57 > 0:04:58is always left with the chilli.
0:04:58 > 0:05:01The essence of a really good
0:05:01 > 0:05:04algorithm, its magic, if you like, is mathematics.
0:05:04 > 0:05:07The best algorithms are those that tap into the underlying
0:05:07 > 0:05:10mathematical structure hiding beneath a problem.
0:05:11 > 0:05:13OK, pop the chilli back.
0:05:14 > 0:05:17I'll be introducing you to some of the algorithms that have
0:05:17 > 0:05:20become the beating heart of modern life.
0:05:21 > 0:05:24But first, I want to show you that, for all their modern
0:05:24 > 0:05:28applications, algorithms are extremely old.
0:05:29 > 0:05:33In fact, they predate computers by thousands of years.
0:05:35 > 0:05:38The oldest algorithm we know of was devised
0:05:38 > 0:05:40to solve a mathematical problem.
0:05:40 > 0:05:44It was first written down by the Ancient Greek mathematician Euclid.
0:05:44 > 0:05:47Euclid's Algorithm, as it's known,
0:05:47 > 0:05:50is a method for finding the greatest common devisor.
0:05:52 > 0:05:55The greatest common devisor is the largest number that will
0:05:55 > 0:06:00divide into a pair of other numbers without leaving a remainder.
0:06:00 > 0:06:03So, in this case, four divides into both eight
0:06:03 > 0:06:06and 12 without a remainder.
0:06:06 > 0:06:08It's simple to find for small numbers,
0:06:08 > 0:06:10but much more tricky for large ones.
0:06:12 > 0:06:15While Euclid was the greatest mathematician of his day,
0:06:15 > 0:06:18his algorithm could have made him a fortune as a tiler.
0:06:19 > 0:06:22Let me show you why.
0:06:22 > 0:06:25Imagine you've got a rectangular-shaped floor
0:06:25 > 0:06:26and you want to find
0:06:26 > 0:06:30the most efficient way to tile it with square tiles.
0:06:30 > 0:06:34In other words, what's the largest square tile that will exactly
0:06:34 > 0:06:38divide the dimensions of the floor with nothing left over?
0:06:38 > 0:06:40This is, in fact, a geometric version
0:06:40 > 0:06:43of the greatest common devisor problem.
0:06:43 > 0:06:46The dimensions of the floor are the two numbers
0:06:46 > 0:06:48and the size of the tiles, which we're going to try
0:06:48 > 0:06:51and work out, is their greatest common devisor.
0:06:54 > 0:06:57We're going to follow Euclid's Algorithm step by step to show
0:06:57 > 0:07:01how it is able to find the perfect sized square tile for this floor.
0:07:02 > 0:07:06According to Euclid's Algorithm, we need to start filling the rectangle
0:07:06 > 0:07:10with square tiles corresponding to the smallest of the two dimensions.
0:07:13 > 0:07:15This is the first stage of the job.
0:07:17 > 0:07:19Euclid's Algorithm then tells us
0:07:19 > 0:07:22to do exactly the same thing again with this rectangle.
0:07:24 > 0:07:28At each stage, the algorithm tells us to select square tiles
0:07:28 > 0:07:31corresponding to the shortest side of the rectangle.
0:07:33 > 0:07:38So this time, our square tiles perfectly fill the leftover space.
0:07:38 > 0:07:42Now, my square tile has dimensions 15x15.
0:07:42 > 0:07:45So Euclid's Algorithm tells us
0:07:45 > 0:07:50that the greatest common devisor of 150 and 345 is 15.
0:07:53 > 0:07:56I'm not suggesting you use Euclid's Algorithm every time
0:07:56 > 0:07:58you need to order some tiles,
0:07:58 > 0:08:02but the amazing thing is that this simple step-by-step method
0:08:02 > 0:08:06finds the perfect square tile whatever the dimensions of the floor.
0:08:07 > 0:08:11Euclid's Algorithm may appear to be just a mathematical technique,
0:08:11 > 0:08:16but it very elegantly fulfils all the criteria for an algorithm.
0:08:16 > 0:08:20It's a precisely stated set of instructions, the procedure
0:08:20 > 0:08:24always finishes, and it can be proven that it works in all cases.
0:08:28 > 0:08:31The power of algorithms is that you don't have to reinvent
0:08:31 > 0:08:36the wheel each time. They're general solutions to problems.
0:08:36 > 0:08:40This holds as true for ancient algorithms as for modern ones.
0:08:45 > 0:08:49In 1998, in this garage in Menlo Park in California,
0:08:49 > 0:08:52an important piece of algorithmic history was made.
0:08:54 > 0:08:58Inside were two PHD students from Stamford University.
0:08:58 > 0:09:00Larry Page and Sergey Brin.
0:09:02 > 0:09:05Their aim was to come up with a search engine that could find
0:09:05 > 0:09:08things efficiently on the World Wide Web.
0:09:11 > 0:09:13Out of these humble beginnings, Google was born.
0:09:15 > 0:09:18But Google wouldn't be Google if it wasn't for the algorithm that
0:09:18 > 0:09:21Larry and Sergey created, called PageRank.
0:09:30 > 0:09:34PageRank was the algorithm at the heart of the first
0:09:34 > 0:09:37incarnation of the Google search engine.
0:09:37 > 0:09:42Now, technically, it's not a search algorithm, but a ranking algorithm.
0:09:42 > 0:09:45So when you type a query into a search engine,
0:09:45 > 0:09:49then there are literally millions of pages which will match that query.
0:09:49 > 0:09:53What PageRank does is to rank all of those pages so the one
0:09:53 > 0:09:56at the top is the one you're more likely to be interested in.
0:09:58 > 0:10:01Larry and Sergey came up with the idea to do PageRank
0:10:01 > 0:10:05and to use it as a ranking system to improve the quality of web search.
0:10:05 > 0:10:07I remember myself at the time,
0:10:07 > 0:10:10you used a web search engine like AltaVista.
0:10:10 > 0:10:12You would have to click the Next Page link
0:10:12 > 0:10:14a lot of times to find what you were looking for.
0:10:14 > 0:10:17PageRank was one of the reasons why Google was
0:10:17 > 0:10:20so much better than the existing search engines at the time.
0:10:21 > 0:10:24The inner workings of PageRank are hidden from view
0:10:24 > 0:10:26on the World Wide Web.
0:10:26 > 0:10:30So to reveal how it does its job, we're going to use the PageRank
0:10:30 > 0:10:33algorithm to rank the players of a football team.
0:10:34 > 0:10:36PageRank looks at two things.
0:10:36 > 0:10:42It looks at the incoming links to a web page, that is the other pages
0:10:42 > 0:10:46that link to the page, and it looks at how important those pages are.
0:10:51 > 0:10:54In our demonstration to show the cleverness of the PageRank
0:10:54 > 0:10:59algorithm, the players in the football team are the web pages
0:10:59 > 0:11:02and the passes between them are the web links.
0:11:02 > 0:11:05The input for the algorithm.
0:11:05 > 0:11:09Generally speaking, the PageRank algorithm will give a higher
0:11:09 > 0:11:13rank to a website if it's got a lot of links coming from other websites.
0:11:13 > 0:11:16So in the case of football, if a player gets more
0:11:16 > 0:11:20passes from the rest of the team, then they'll be ranked higher.
0:11:20 > 0:11:21It's not quite that simple.
0:11:21 > 0:11:24Because the PageRank algorithm actually gives more weight to
0:11:24 > 0:11:28a link from a website that itself has a high page rank.
0:11:28 > 0:11:32So actually, a pass from a popular player is worth more than
0:11:32 > 0:11:35a pass from a player who's hardly involved in the game at all.
0:11:37 > 0:11:40This is a visualisation of the algorithm at work.
0:11:40 > 0:11:45The stats are the players' current ranking. The output of the algorithm.
0:11:45 > 0:11:50And every time there's a pass, these rankings are updated.
0:11:50 > 0:11:56When Google uses this algorithm, it only changes once thing - the input.
0:11:56 > 0:11:59In place of passes, it uses web links.
0:12:01 > 0:12:04Note that the importance of a page depends on the importance
0:12:04 > 0:12:06of the pages that link to it.
0:12:06 > 0:12:09This means that you have to compute page rank for all
0:12:09 > 0:12:11the pages at the same time.
0:12:11 > 0:12:14And you actually have to repeat the computation because, each time,
0:12:14 > 0:12:16you'll update the importance of all the pages.
0:12:16 > 0:12:19And that in turn will influence
0:12:19 > 0:12:22the importance of the pages that those pages link to.
0:12:30 > 0:12:33At the end of the match, the job of the algorithm is done.
0:12:36 > 0:12:39If we wanted to search for the key player in the team,
0:12:39 > 0:12:41this is PageRank's answer.
0:12:43 > 0:12:46Player 11 has the highest PageRank score.
0:12:48 > 0:12:50I think the PageRank algorithm is probably
0:12:50 > 0:12:52my favourite algorithm of all time.
0:12:52 > 0:12:54And it's amazing that it can be applied not just to
0:12:54 > 0:12:58the World Wide Web, but analysing a football match, as well.
0:12:58 > 0:13:01But for me, it's the fact that there's a beautiful bit of
0:13:01 > 0:13:03mathematics at its heart that always seems to find
0:13:03 > 0:13:05the website I'm looking for.
0:13:08 > 0:13:09Within Google, I think
0:13:09 > 0:13:14PageRank is seen as a very important part of Google's early development.
0:13:15 > 0:13:18PageRank was the secret to why the search engine that Larry
0:13:18 > 0:13:22and Sergey built in the 1990s was so successful.
0:13:23 > 0:13:28Now, Google handles over 3.5 billion searches every day.
0:13:28 > 0:13:31It's the world's most poplar search engine.
0:13:31 > 0:13:36And the company is worth more than 450 billion.
0:13:37 > 0:13:40Not bad for two PhD students working out of a garage.
0:13:49 > 0:13:52Algorithms are simple step-by-step recipes.
0:13:52 > 0:13:56Inventing them requires incredible creativity and genius.
0:13:56 > 0:14:01But using them is just a matter of following instructions.
0:14:01 > 0:14:04And this is why algorithms are perfect for computers.
0:14:08 > 0:14:10Computers are just machines.
0:14:10 > 0:14:14They just do repetitive tasks at phenomenal speeds.
0:14:14 > 0:14:15Unbelievable speeds.
0:14:15 > 0:14:20So they're absolutely perfect for performing these repetitive tasks
0:14:20 > 0:14:23that are unambiguously defined
0:14:23 > 0:14:27and can be done in a finite amount of time.
0:14:29 > 0:14:32Computer code is basically making an algorithm specific.
0:14:32 > 0:14:33So the algorithm is the kind of idea.
0:14:33 > 0:14:35How would you solve the problem?
0:14:35 > 0:14:37These are the rough instructions that you would use.
0:14:37 > 0:14:40And then that can be translated into particular code.
0:14:43 > 0:14:47Lots of types of algorithms have been created with a computer in mind.
0:14:49 > 0:14:53And some of the most important are sorting algorithms.
0:14:54 > 0:14:58Now, the job of a sorting algorithm is to put things in order.
0:14:58 > 0:15:00And they have lots of uses.
0:15:00 > 0:15:03For example, on the internet, information gets
0:15:03 > 0:15:08broken down into packets of data which then get sent across the web.
0:15:08 > 0:15:11Now, to reassemble that data,
0:15:11 > 0:15:15sorting algorithms are absolutely crucial to putting this data
0:15:15 > 0:15:18back in the correct order so that we can view the picture,
0:15:18 > 0:15:21or read the email we've just been sent.
0:15:26 > 0:15:30This is the System Development Corporation in California.
0:15:30 > 0:15:35It's considered to be the world's first computer software company.
0:15:35 > 0:15:40And it was here in 1963 that two computer scientists first formally
0:15:40 > 0:15:44wrote down one of the most iconic sorting algorithms of all-time.
0:15:48 > 0:15:50It's called bubble sort.
0:15:50 > 0:15:53And here's an example of bubble sort in action,
0:15:53 > 0:15:55sorting blocks instead of numbers.
0:15:57 > 0:16:01It gets its name because with each round of the algorithm,
0:16:01 > 0:16:05the largest unsorted object bubbles to the top.
0:16:05 > 0:16:09Like all our algorithms so far, there's method in the madness.
0:16:14 > 0:16:16To see how this algorithm works,
0:16:16 > 0:16:19we're going to use it to sort eight objects.
0:16:20 > 0:16:24Now, the bubble sort algorithm says to consider the objects in pairs
0:16:24 > 0:16:27and swap them over if they're in the wrong order.
0:16:27 > 0:16:31So we're going to start at this end here and work our way to the top.
0:16:31 > 0:16:35So I consider these two, they're in the wrong order, so I swap them over.
0:16:37 > 0:16:40Consider the next pair, they're in the right order,
0:16:40 > 0:16:42so I leave them as they are.
0:16:42 > 0:16:45Consider this pair, they're in the wrong order, so I swap them.
0:16:48 > 0:16:51And we just continue doing this.
0:16:58 > 0:17:01Now the bubble sort algorithm says to go back to the beginning
0:17:01 > 0:17:05and repeat the process over and over again until the objects are in order.
0:17:19 > 0:17:24The algorithm stops when there are no pairs to swap round.
0:17:24 > 0:17:27So the bubble sort algorithm has successfully done its job.
0:17:27 > 0:17:30I've now got the objects perfectly ordered,
0:17:30 > 0:17:32according to ascending height.
0:17:34 > 0:17:37Bubble sort is elegantly simple and straightforward.
0:17:37 > 0:17:41But if the scale of the sorting task is huge, say, organising vast swathes
0:17:41 > 0:17:45of data, then there might be better sorting algorithms for the job.
0:17:50 > 0:17:52This is John von Neumann,
0:17:52 > 0:17:56the scientific genius who helped pioneer the modern computer,
0:17:56 > 0:17:58game theory, the atomic bomb
0:17:58 > 0:18:02and, as it turns out, invented a sorting algorithm.
0:18:04 > 0:18:08He devised it to work on this, one of the world's earliest
0:18:08 > 0:18:11electronic computers, which he'd helped design.
0:18:11 > 0:18:14The algorithm is called merge sort.
0:18:16 > 0:18:21The merge sort algorithm works on a principle of divide and conquer.
0:18:21 > 0:18:26And it consists of two parts. The first bit is the dividing part.
0:18:28 > 0:18:31This involves splitting everything into smaller groups.
0:18:35 > 0:18:38And now comes the conquering bit.
0:18:40 > 0:18:43The groups are now merged back together.
0:18:43 > 0:18:47But as I merge the two groups, I compare the sizes of the objects
0:18:47 > 0:18:51one pair at a time so that the merged group becomes sorted.
0:19:00 > 0:19:03Now, the merge sort algorithm might look rather similar to the
0:19:03 > 0:19:07bubble sort, but where it comes into its own is that with a larger
0:19:07 > 0:19:10number of objects, it's much, much faster.
0:19:10 > 0:19:15So let's see how merge sort compares in speed to bubble sort.
0:19:15 > 0:19:18It's time for a battle of the algorithms!
0:19:21 > 0:19:26Here we've got bubble sort on the bottom and merge sort on the top.
0:19:26 > 0:19:28And we've got them sorting 1,000 objects.
0:19:28 > 0:19:31Now, although they'll both produce the same end result,
0:19:31 > 0:19:35you can already see merge sort is getting there much faster.
0:19:35 > 0:19:38And this difference in performance gets more pronounced
0:19:38 > 0:19:41the more objects they're asked to sort.
0:19:53 > 0:19:55LAUGHTER
0:19:57 > 0:19:59Well, er...
0:19:59 > 0:20:02- I'm sorry, maybe... - No, no, no, no, no.
0:20:02 > 0:20:05I-I think...I think, er...
0:20:05 > 0:20:08I think the bubble sort would be the wrong way to go.
0:20:08 > 0:20:10LAUGHTER
0:20:10 > 0:20:11APPLAUSE
0:20:12 > 0:20:15Come on. Who told him this?
0:20:22 > 0:20:24Merge sort beats bubble sort hands down
0:20:24 > 0:20:26for sorting large amounts of data.
0:20:28 > 0:20:31But in the crazy world of algorithms, there are many,
0:20:31 > 0:20:33many different ways to sort.
0:20:36 > 0:20:37At the last count,
0:20:37 > 0:20:41there were over 20 different types of sorting algorithms.
0:20:42 > 0:20:46All weirdly achieving the same result, but by different means.
0:20:58 > 0:21:02- So there's bubble sort, there's merge sort.- Insertion sort.
0:21:02 > 0:21:06- There's heap sort, there's quick sort.- Timsort.
0:21:06 > 0:21:07You've got gnome sort.
0:21:07 > 0:21:10There's pigeonhole sort, which is also called radix sort.
0:21:10 > 0:21:13There's bogosort, which might never finish.
0:21:19 > 0:21:23There's no such thing as the best sorting algorithm.
0:21:23 > 0:21:25Each has its own pros and cons.
0:21:26 > 0:21:28And which one gets used
0:21:28 > 0:21:31often depends on the specifics of the problem.
0:21:32 > 0:21:36I think the beauty of studying algorithms is to try to aspire
0:21:36 > 0:21:40for solutions that are as elegant and efficient as possible.
0:21:40 > 0:21:44I actually think bubble sort's very pretty. I like it.
0:21:44 > 0:21:46Merge sort's beautiful.
0:21:49 > 0:21:51We really couldn't live without them.
0:21:51 > 0:21:54Sorting algorithms bring order to the world.
0:22:05 > 0:22:07So far, we've seen algorithms tackle the tiny
0:22:07 > 0:22:11problems of sizing our bathroom tiles and sorting our data.
0:22:12 > 0:22:16But how well do they cope with the messy world of love?
0:22:18 > 0:22:20Online dating is really popular these days.
0:22:20 > 0:22:23In fact, one survey suggests that over a third
0:22:23 > 0:22:26of recent marriages started online.
0:22:27 > 0:22:30How these dating websites work is that they use something called
0:22:30 > 0:22:33a matching algorithm.
0:22:33 > 0:22:36They search through the profiles, try to match people up according
0:22:36 > 0:22:40to their likes and dislikes, personality traits and so on.
0:22:40 > 0:22:43In fact, the algorithms seem to be better than humans.
0:22:43 > 0:22:46Because recent research has shown those who meet online
0:22:46 > 0:22:49tend to be happier and have longer marriages.
0:22:52 > 0:22:56I'll ask you to receive your prizes from His Majesty the King.
0:22:56 > 0:23:01In fact, matching algorithms have quite a lot to brag about.
0:23:01 > 0:23:05Because in 2012, for the first time, a Nobel Prize was awarded
0:23:05 > 0:23:07because of an algorithm.
0:23:07 > 0:23:11A matching algorithm created by the late David Gale
0:23:11 > 0:23:13and mathematician Lloyd Shapley,
0:23:13 > 0:23:16seen here receiving his share of the prize.
0:23:20 > 0:23:23The story begins in the 1960s when Gale and Shapley wanted to
0:23:23 > 0:23:27solve a problem concerned with college admissions.
0:23:27 > 0:23:31How to match up students to colleges so that everyone got a place.
0:23:32 > 0:23:35But, more importantly, was happy, even if
0:23:35 > 0:23:37they didn't get their first choice.
0:23:40 > 0:23:44They called it the stable marriage problem.
0:23:44 > 0:23:46The stable marriage problem goes like this.
0:23:46 > 0:23:49Suppose you've got four women and four men
0:23:49 > 0:23:51and they want to get married.
0:23:51 > 0:23:54Now, they've ranked each other according to their preferences.
0:23:54 > 0:23:55So, for example, the Queen of Hearts here,
0:23:55 > 0:23:57first choice is the King of Clubs.
0:23:57 > 0:24:00Second choice, King of Diamonds,
0:24:00 > 0:24:02and her last choice is the King of Hearts.
0:24:02 > 0:24:06So the challenge here is to play Cupid and pair up the kings
0:24:06 > 0:24:09and queens so that each one gets a partner, but, more importantly,
0:24:09 > 0:24:12so that the marriages are stable.
0:24:12 > 0:24:15A stable marriage means that the kings and queens don't
0:24:15 > 0:24:20necessarily get their first choice, but they get the best on offer.
0:24:20 > 0:24:25For example, if I paired the King of Hearts and the Queen of Hearts
0:24:25 > 0:24:28and the King of Spades and the Queen of Spades,
0:24:28 > 0:24:31this would be an unstable marriage.
0:24:31 > 0:24:34Because the King of Spades doesn't really like the Queen of Spades.
0:24:34 > 0:24:36He'd prefer the Queen of Hearts.
0:24:38 > 0:24:40The Queen of Hearts, in her turn,
0:24:40 > 0:24:41doesn't really like the King of Hearts.
0:24:41 > 0:24:44She'd prefer the King of Spades.
0:24:44 > 0:24:48So these two are going to run off together in this pairing.
0:24:51 > 0:24:56Where there's a problem, there's an algorithm not far behind.
0:24:56 > 0:24:59In 1962, Gale and Shapley came up with
0:24:59 > 0:25:02their Nobel-Prize-winning algorithm.
0:25:02 > 0:25:09A step-by-step recipe which always finds perfectly-stable marriages.
0:25:09 > 0:25:11So in the first round of the algorithm,
0:25:11 > 0:25:14the queens all proposed to their first-choice kings.
0:25:14 > 0:25:18So the Queen of Spades' first choice is the King of Spades.
0:25:18 > 0:25:21She proposes to the King of Spades.
0:25:21 > 0:25:24The Queen of Hearts' first choice is the King of Clubs,
0:25:24 > 0:25:26so she proposes to the King of Clubs.
0:25:26 > 0:25:30The Queen of Diamonds' first choice is the King of Spades.
0:25:30 > 0:25:33And the Queen of Clubs' first choice is also the King of Spades.
0:25:33 > 0:25:36So King of Spades seems to be the Darcy of this royal court.
0:25:37 > 0:25:40Now, the King of Spades has got three proposals.
0:25:41 > 0:25:44So he chooses his most popular queen,
0:25:44 > 0:25:48who is actually the Queen of Diamonds, and rejects the other two.
0:25:51 > 0:25:55So we have two provisional engagements, two rejections.
0:25:55 > 0:25:59We now remove the rejected queen's first choices.
0:25:59 > 0:26:01And it's time for round two.
0:26:02 > 0:26:06So the Queen of Spades is going to propose to the King of Diamonds.
0:26:06 > 0:26:10And the Queen of Clubs proposes to the King of Clubs.
0:26:11 > 0:26:14But now the King of Clubs has got two proposals
0:26:14 > 0:26:17and actually prefers the Queen of Clubs.
0:26:17 > 0:26:20So he rejects the Queen of Hearts, his provisional
0:26:20 > 0:26:22engagement on the first round of the algorithm,
0:26:22 > 0:26:24and we have to start again.
0:26:26 > 0:26:28In each round, the rejected queens
0:26:28 > 0:26:31propose to the next king on their list.
0:26:31 > 0:26:34And the kings always go for the best offer they get.
0:26:35 > 0:26:40In this round of the algorithm, she proposes to the King of Hearts
0:26:40 > 0:26:44and finally, everyone's paired up with a single queen and king
0:26:44 > 0:26:45and all the marriages are stable.
0:26:49 > 0:26:53The Gale-Shapley algorithm is now used all over the world.
0:26:53 > 0:26:56In Denmark, to match children to day-care places.
0:26:56 > 0:27:00In Hungary, to match students to schools.
0:27:00 > 0:27:03In New York, to allocate rabbis to synagogues.
0:27:03 > 0:27:07And in China, Germany and Spain, to match students to universities.
0:27:10 > 0:27:13Whilst in the UK, it's led to the development
0:27:13 > 0:27:18of a matching algorithm that, for some people, has saved their lives.
0:27:23 > 0:27:26At the age of 20, Seraya in south London was diagnosed
0:27:26 > 0:27:31with a chronic kidney disease and told she needed a transplant.
0:27:32 > 0:27:37I was on dialysis for 18 months and very unwell.
0:27:37 > 0:27:40I couldn't go to work. I had no social life.
0:27:40 > 0:27:44It was literally hospital three times a week for treatment and home.
0:27:45 > 0:27:47A close friend was willing to donate,
0:27:47 > 0:27:50but their tissue types were not compatible.
0:27:53 > 0:27:55In St Albans, Tamir was seriously ill
0:27:55 > 0:27:58and his wife, Lyndsey, wanted to donate.
0:27:58 > 0:28:00But they had the same problem.
0:28:02 > 0:28:04We went through all the blood tests and all the workup
0:28:04 > 0:28:08and it turned out that we were incompatible blood groups.
0:28:10 > 0:28:13Often, kidney patients who are fortunate enough
0:28:13 > 0:28:16to have a would-be donor find there's a mismatch
0:28:16 > 0:28:18between their donor's blood group or tissue type.
0:28:20 > 0:28:26But since 2007, the NHS has been using a special matching algorithm
0:28:26 > 0:28:29to find potential matches for willing donors
0:28:29 > 0:28:31to kidney patients all over the UK.
0:28:35 > 0:28:37When we first looked at this problem,
0:28:37 > 0:28:41we really underestimated the complexity.
0:28:41 > 0:28:46And originally, we just started with swaps between two pairs.
0:28:46 > 0:28:48So it was very simple,
0:28:48 > 0:28:53but it soon became obvious that we needed something much more complex.
0:28:56 > 0:29:00I became in touch with Rachel Johnson at the NHS
0:29:00 > 0:29:02and we then got involved at that stage in being able to design
0:29:02 > 0:29:05algorithms which would allow not just pair-wise exchanges,
0:29:05 > 0:29:08but also exchanges among three couples, as well.
0:29:10 > 0:29:13The algorithm considers several scenarios.
0:29:13 > 0:29:15The simplest is a two-way swap
0:29:15 > 0:29:18with two couples exchanging kidneys.
0:29:21 > 0:29:23More complicated is a three-way swap,
0:29:23 > 0:29:26where the kidneys get passed around in a cycle.
0:29:29 > 0:29:34There are 200 patients in each of our matching runs.
0:29:34 > 0:29:38We need to look for all the possible transplants.
0:29:40 > 0:29:42And it's surprising how many there are.
0:29:42 > 0:29:44There are literally, you know, hundreds,
0:29:44 > 0:29:47sometimes thousands of possibilities.
0:29:47 > 0:29:51It's something that just could not be achieved without the algorithm.
0:29:53 > 0:29:57One day, Seraya received the call that a match had been found
0:29:57 > 0:30:02400 miles away with Linda, a donor living in Bowness near Edinburgh.
0:30:03 > 0:30:06My husband's dad needed a new kidney.
0:30:06 > 0:30:11He'd been ill for a bit of time. And I wasn't a perfect match.
0:30:11 > 0:30:17And I then got a phone call and it was all go from there.
0:30:19 > 0:30:20We got the initial phone call saying
0:30:20 > 0:30:23we'd been matched up in the three-way pool.
0:30:23 > 0:30:26You're just nervous that it's not going to go ahead
0:30:26 > 0:30:28because your life depends on it.
0:30:29 > 0:30:31For the matching couples,
0:30:31 > 0:30:35all the operations had to happen simultaneously.
0:30:35 > 0:30:38It was a major logistical challenge.
0:30:38 > 0:30:41When my donor went to theatre, they called over to check
0:30:41 > 0:30:44that my donor was also in Newcastle going to theatre.
0:30:44 > 0:30:46And they both got it at the exact same time.
0:30:46 > 0:30:49And they make the call and the kidneys come out.
0:30:49 > 0:30:51I think they went by motorbike.
0:30:51 > 0:30:53We were told they might go by helicopter,
0:30:53 > 0:30:56so I thought at least one bit of me might have been in a helicopter,
0:30:56 > 0:30:58but, no, it went by motorbike.
0:31:02 > 0:31:06And it eventually went ahead, thankfully, in December.
0:31:06 > 0:31:09- The best Christmas present.- Hm!
0:31:09 > 0:31:12Personally, I just imagined it was doctors behind there
0:31:12 > 0:31:14matching people up off this list.
0:31:14 > 0:31:17So, yeah, it's a bit strange
0:31:17 > 0:31:20that it comes down to maths at the end of the day.
0:31:20 > 0:31:23It's a great scheme and it's still fairly recent.
0:31:23 > 0:31:27And many years ago, I wouldn't have had this chance.
0:31:27 > 0:31:31I feel a lot of gratitude to Linda and also to the algorithm.
0:31:31 > 0:31:33So, yeah, I'm very grateful.
0:31:34 > 0:31:39So far, more than 400 patients have benefited from the NHS scheme
0:31:39 > 0:31:42and its special matching algorithm.
0:31:42 > 0:31:44It was only when we actually seen media articles
0:31:44 > 0:31:47and we actually started to think, "Oh, hold on,
0:31:47 > 0:31:49"that person might have actually had that match
0:31:49 > 0:31:53"through the October matching run's pair-wise exchange," and so on,
0:31:53 > 0:31:55that you actually start to see the stories
0:31:55 > 0:31:57that are behind the anonymous data.
0:31:57 > 0:32:00It's quite funny because David's always really concerned
0:32:00 > 0:32:03that the algorithm will take a long time to run.
0:32:03 > 0:32:07And, you know, it's been up to 30 minutes and he gets concerned.
0:32:07 > 0:32:10But actually, 30 minutes, you know, to us,
0:32:10 > 0:32:14it's incredible that it can do all of that in 30 minutes.
0:32:25 > 0:32:29So far, we have seen how algorithms are capable of amazing feats.
0:32:30 > 0:32:33From solving abstract mathematical problems
0:32:33 > 0:32:37to helping us find stuff on the World Wide Web.
0:32:37 > 0:32:41And they key thing for all of these algorithms is their speed.
0:32:41 > 0:32:44So the important feature of a good algorithm is first
0:32:44 > 0:32:47that it'd better be correct, but once you know it's correct,
0:32:47 > 0:32:49it's also important that it runs quickly.
0:32:49 > 0:32:52There's no good having an algorithm that takes longer
0:32:52 > 0:32:57than your lifetime to run if you're wanting the result tomorrow.
0:32:58 > 0:33:02This face-detection algorithm is an example of an efficient algorithm.
0:33:02 > 0:33:05Because it's efficient, it's able to run in real time.
0:33:05 > 0:33:07And that's what makes it useful.
0:33:09 > 0:33:14But just as in real life, some problems are harder than others.
0:33:14 > 0:33:17Every now and then, algorithms meet their match.
0:33:19 > 0:33:21I think the most common misconception about algorithms
0:33:21 > 0:33:24is just that algorithms can do anything.
0:33:24 > 0:33:27I think people don't really know about the limits.
0:33:27 > 0:33:30Some problems simply cannot be solved by efficient algorithms.
0:33:32 > 0:33:36There are some places where efficient algorithms cannot go.
0:33:36 > 0:33:40Lines in the sand that can't be crossed.
0:33:40 > 0:33:43The trouble is knowing which problems they can solve
0:33:43 > 0:33:44and which they can't.
0:33:48 > 0:33:51Take this Rubik's Cube and imagine the more general challenge
0:33:51 > 0:33:54of trying to solve a cube of arbitrary dimensions.
0:33:54 > 0:33:57So, for example, with 50 squares down each side.
0:33:57 > 0:33:58Now, you might expect this
0:33:58 > 0:34:01to be one of the really fiendishly difficult problems,
0:34:01 > 0:34:03but actually, it belongs in the easy camp.
0:34:03 > 0:34:08We know an algorithm that can solve the general Rubik's Cube
0:34:08 > 0:34:09in a reasonable amount of time.
0:34:13 > 0:34:14Although it looks hard,
0:34:14 > 0:34:17this problem can be cracked by efficient algorithms.
0:34:22 > 0:34:25However, here's one that definitely can't.
0:34:27 > 0:34:30Imagine you've got a draughts board of arbitrary size
0:34:30 > 0:34:32and an arrangement of pieces on the board.
0:34:32 > 0:34:34The challenge is to work out
0:34:34 > 0:34:38whether white can force a win from this position.
0:34:38 > 0:34:40Now, draughts is a pretty easy game,
0:34:40 > 0:34:42but it's been mathematically proven
0:34:42 > 0:34:46that there's no algorithm that can solve this problem efficiently.
0:34:46 > 0:34:49It's an inherently difficult problem.
0:34:51 > 0:34:55The only way to solve this puzzle is through sheer hard slog -
0:34:55 > 0:34:58working out all the millions of possibilities.
0:35:00 > 0:35:04So this problem lies firmly beyond the reach of efficient algorithms.
0:35:04 > 0:35:06It can't be solved quickly.
0:35:10 > 0:35:14But for some problems, how hard they are is not clear cut.
0:35:14 > 0:35:19This is a large sudoku. It's got 625 squares.
0:35:20 > 0:35:24One of the nice things about sudoku is that once you've found a solution,
0:35:24 > 0:35:28it's relatively straightforward to check whether or not it's right.
0:35:28 > 0:35:30And this is true however large the puzzle.
0:35:32 > 0:35:34In this case, I've just got to check each row,
0:35:34 > 0:35:38column and block doesn't feature a number twice.
0:35:38 > 0:35:42Sudoku belongs to a very special category of problems
0:35:42 > 0:35:44that all share this characteristic.
0:35:44 > 0:35:48Once you've come up with a solution, it's always easy to check it.
0:35:49 > 0:35:53The mystery is whether there's an efficient algorithm
0:35:53 > 0:35:55to find the solution in the first place.
0:35:58 > 0:36:02And sudoku is not alone. There are lots of problems like this.
0:36:02 > 0:36:05The most intensely studied of them all
0:36:05 > 0:36:08is known as the travelling salesman problem.
0:36:13 > 0:36:16A travelling salesman travels door to door, city to city,
0:36:16 > 0:36:20selling anything from brushes and Hoovers to double-glazing.
0:36:22 > 0:36:25It sounds like a straightforward job.
0:36:25 > 0:36:28But all travelling salesmen face the same question.
0:36:28 > 0:36:31What's the shortest route to take?
0:36:33 > 0:36:37So important is this problem that the Clay Mathematics Institute
0:36:37 > 0:36:42has offered 1 million for whoever can find an efficient algorithm,
0:36:42 > 0:36:44or prove that none exists.
0:36:46 > 0:36:49The travelling salesman problem goes like this.
0:36:49 > 0:36:50Imagine you're a salesman
0:36:50 > 0:36:55and you've got to visit a list of cities represented by the red dots.
0:36:55 > 0:36:57The challenge is to find the shortest route
0:36:57 > 0:37:02so you visit each city once before returning to your starting point.
0:37:02 > 0:37:04Now, you might imagine the best thing is
0:37:04 > 0:37:07to just consider all the routes, like this.
0:37:13 > 0:37:18The method of checking all possibilities is a type of algorithm.
0:37:18 > 0:37:20And for three cities, it works fine
0:37:20 > 0:37:23because there are only three possible routes to check.
0:37:27 > 0:37:30But what if we add two more cities to the list?
0:37:32 > 0:37:36With five cities, there are 60 different possible routes.
0:37:39 > 0:37:44And if we add another city, then there are 360 possible routes.
0:37:44 > 0:37:49And for ten cities, there are over 1.8 million possible routes.
0:37:49 > 0:37:51If our algorithm chugged through them,
0:37:51 > 0:37:54checking all of these at a rate of ten per second,
0:37:54 > 0:37:58it would take two days before it found the shortest.
0:37:58 > 0:38:01So you can see a method of trying all the different possibilities,
0:38:01 > 0:38:06a kind of brute-force algorithm, if you like, is just simply impractical.
0:38:07 > 0:38:10If somebody found a fast algorithm for the travelling salesman problem,
0:38:10 > 0:38:12it would be hugely significant.
0:38:12 > 0:38:15If one of my students came up with an efficient algorithm
0:38:15 > 0:38:17for the travelling salesman problem,
0:38:17 > 0:38:20I would get him to explain it to me,
0:38:20 > 0:38:23I would kill him and then I'd go and claim
0:38:23 > 0:38:25the Clay prize, 1 million.
0:38:25 > 0:38:28But I think my students are safe.
0:38:29 > 0:38:32The problem crops up in lots of areas.
0:38:32 > 0:38:35From soldering circuit boards...
0:38:37 > 0:38:40..to planning the routes for supermarket deliveries.
0:38:40 > 0:38:45But has the travelling salesman problem secretly already been solved?
0:38:49 > 0:38:54A team of scientists working at Rothamsted Research in Harpenden
0:38:54 > 0:38:57have turned to nature to see if it has found the answer.
0:39:03 > 0:39:06They're carrying out an elaborate experiment to study
0:39:06 > 0:39:10how the travelling salesman problem is tackled by the bumblebee.
0:39:13 > 0:39:17Bees have to forage for nectar in order to provision their hive.
0:39:17 > 0:39:19And so they have to visit
0:39:19 > 0:39:22possibly hundreds of flowers on each trip.
0:39:22 > 0:39:25What they want to do is find an efficient way
0:39:25 > 0:39:28to go between all these flowers that they visit.
0:39:31 > 0:39:35The humble bumblebee faces its own travelling salesman problem.
0:39:35 > 0:39:38The flowers are just like the cities.
0:39:38 > 0:39:41And the bee is the travelling salesman.
0:39:41 > 0:39:45One bee will go out foraging many, many times every day.
0:39:45 > 0:39:47So over the course of a day,
0:39:47 > 0:39:51it really helps to take the most efficient possible route.
0:39:51 > 0:39:53So what we're doing is trying to figure out
0:39:53 > 0:39:58exactly what rules they're using to narrow down the possibilities.
0:40:00 > 0:40:04Joe has laid out five feeders which play the role of flowers.
0:40:05 > 0:40:10Each feeder has just enough nectar to ensure the bee has to visit all five
0:40:10 > 0:40:12to give it a full honey stomach.
0:40:13 > 0:40:16And how are you actually knowing where it's going?
0:40:16 > 0:40:18For this, we're using a harmonic radar.
0:40:18 > 0:40:22So as that spins round and round, it's emitting a radar signal.
0:40:22 > 0:40:25And we've attached a small antenna to the back of the bee,
0:40:25 > 0:40:27which then reflects the signal from the radar.
0:40:27 > 0:40:31And so this allows us to see exactly where the bee has gone
0:40:31 > 0:40:32as she moves around the field.
0:40:34 > 0:40:38So, how does the bumblebee tackle the travelling salesman problem?
0:40:38 > 0:40:40OK, we're switching it on now.
0:40:47 > 0:40:51With five feeders, there are a total of 60 possible routes.
0:40:51 > 0:40:54The shortest is around the outer edge.
0:40:58 > 0:41:02This heat map shows the path taken by a single bee.
0:41:02 > 0:41:06At first, it's simply discovering the positions of the feeders.
0:41:07 > 0:41:12Then the bee appears to methodically change different parts of the route
0:41:12 > 0:41:14to see if it can make it shorter.
0:41:16 > 0:41:20Within 20 trips, it's honed in on an efficient route.
0:41:26 > 0:41:29This route is not always the absolute shortest,
0:41:29 > 0:41:31but, for the bee, it's good enough.
0:41:36 > 0:41:40That's amazing that just after a very few tries, they've got
0:41:40 > 0:41:44to something which is efficient enough for them to do their foraging.
0:41:44 > 0:41:47Yes, that's right. They can't spend days or even, you know,
0:41:47 > 0:41:50it could take months or years to try every possibility.
0:41:50 > 0:41:52So they have to very quickly find a route
0:41:52 > 0:41:55that they can do again and again and again
0:41:55 > 0:41:59- in order to efficiently provide food.- Fantastic.
0:41:59 > 0:42:01I think the bee's become my favourite insect now.
0:42:01 > 0:42:05- It's obviously a mathematician at heart.- Absolutely.
0:42:06 > 0:42:11Let's be clear. Bees are not about to be awarded 1 million.
0:42:11 > 0:42:15They've not miraculously solved the travelling salesman problem
0:42:15 > 0:42:18because they don't always find the shortest route.
0:42:19 > 0:42:21But their algorithm is a clever approach.
0:42:21 > 0:42:25In maths, it's known as heuristics.
0:42:25 > 0:42:29Algorithms that are efficient, that don't find the perfect solution,
0:42:29 > 0:42:31but get as close as they can.
0:42:44 > 0:42:46The same heuristic approach
0:42:46 > 0:42:49has been used to develop an algorithm for Heathrow airport.
0:42:51 > 0:42:54DISPATCHER: 'Clear for takeoff...'
0:42:54 > 0:42:57Heathrow handles over 1,300 flights a day.
0:42:57 > 0:43:00It's Europe's busiest airport.
0:43:00 > 0:43:04'..430 clear for takeoff. Surface wind 247 degrees at three knots.'
0:43:12 > 0:43:15The challenge for air traffic control
0:43:15 > 0:43:18is to maximise the number of aircraft departing every hour
0:43:18 > 0:43:22and ensure that the airport operates both efficiently and safely.
0:43:22 > 0:43:29'..behind the British Airways 747, line up 27 right behind.'
0:43:29 > 0:43:33One of the key decisions is the order of takeoff.
0:43:33 > 0:43:36We're currently departing a group of medium aircraft,
0:43:36 > 0:43:39which will be separated one minute apart.
0:43:39 > 0:43:43Behind that, then, you can see a 747, which is a large aircraft.
0:43:44 > 0:43:48Medium aircraft need to be separated from the turbulence
0:43:48 > 0:43:50produced by larger aircraft.
0:43:50 > 0:43:52So the ordering of sizes is crucial.
0:43:53 > 0:43:56The ideal sequence for takeoff involves
0:43:56 > 0:43:58really blocking together groups of aircraft.
0:43:58 > 0:44:01So you want large aircraft to be grouped together,
0:44:01 > 0:44:03medium aircraft to be grouped together.
0:44:03 > 0:44:05And that allows the separation
0:44:05 > 0:44:07between those aircraft to be minimised.
0:44:10 > 0:44:14The other factor that needs to be considered where planning takeoff
0:44:14 > 0:44:16is where the planes are heading.
0:44:19 > 0:44:22We want one to be going to the north, one to the south,
0:44:22 > 0:44:24the next going to the north, then the south.
0:44:24 > 0:44:29If all the aircraft were going in the same direction, the separation would be much greater
0:44:29 > 0:44:31and we wouldn't use the runways as efficiently.
0:44:31 > 0:44:34All controllers are sitting in the control towers thinking,
0:44:34 > 0:44:37"I've all these aircraft going north, all these going south.
0:44:37 > 0:44:39"I've got these that are large ones,
0:44:39 > 0:44:42"so I want to try and group all the large ones together
0:44:42 > 0:44:44"so I don't have to go from a large one to a small one."
0:44:44 > 0:44:48And it's a very complex problem to solve in their heads.
0:44:48 > 0:44:50'..906 November...'
0:44:50 > 0:44:54In 2013, an algorithm joined the team.
0:44:54 > 0:44:58Its job is to predict the most likely order for takeoff
0:44:58 > 0:45:00and advise air traffic control
0:45:00 > 0:45:03when aircraft should push back from the gates.
0:45:03 > 0:45:06To do this involves nothing less than simulating
0:45:06 > 0:45:09the entire outward-bound operation of the airport.
0:45:11 > 0:45:14Carrying out millions of calculations every second.
0:45:14 > 0:45:17FAINT DISPATCHER
0:45:21 > 0:45:25The algorithm works by trying to predict
0:45:25 > 0:45:28what order the aircraft are going to take off in.
0:45:28 > 0:45:30If it knows what order they can take off in,
0:45:30 > 0:45:32then it can work backwards and say,
0:45:32 > 0:45:34"If it needs to take off at this time,
0:45:34 > 0:45:37"then it needs to enter the runway queue at this time,
0:45:37 > 0:45:39"then it needs finishing its taxi at this time,
0:45:39 > 0:45:42"so it needs to start its taxi operation at this time.
0:45:42 > 0:45:45"In that case, it needs to finish its pushback by this time,
0:45:45 > 0:45:47"so it needs to start its pushback by this time."
0:45:47 > 0:45:50And it can work all the way back from what time it should take off
0:45:50 > 0:45:52to what time it should start pushing back.
0:45:55 > 0:45:58The output of the algorithm is given to air traffic control
0:45:58 > 0:46:01through the airport's internal computer system
0:46:01 > 0:46:05and displayed to the pilot at the gate in the form of the TSAT,
0:46:05 > 0:46:07the recommended pushback time.
0:46:10 > 0:46:12The pilot can look on the stand-entry system
0:46:12 > 0:46:15to actually see what time he is expecting to depart.
0:46:17 > 0:46:21The biggest benefit of the algorithm is that it means you can
0:46:21 > 0:46:25hold aircraft on stand for longer without them taking off any later.
0:46:25 > 0:46:28So there's no loss for any passengers in terms of delays.
0:46:28 > 0:46:30What you can do is you can start your engines later.
0:46:33 > 0:46:35In actual fact, if we save two minutes' taxi time
0:46:35 > 0:46:37on the way to the end of the runway, over a year,
0:46:37 > 0:46:40that's actually £15 million worth of fuel savings.
0:46:42 > 0:46:46The Heathrow sequencing algorithm shows just what can be accomplished
0:46:46 > 0:46:47with the heuristic approach.
0:46:49 > 0:46:52Just like the bees, the algorithm is not finding
0:46:52 > 0:46:55the absolute perfect solution all the time,
0:46:55 > 0:46:58but nevertheless makes a tough job that bit easier.
0:47:00 > 0:47:02We're very proud of the algorithm
0:47:02 > 0:47:05because it actually now, we feel, models the real world and is of use.
0:47:16 > 0:47:19In the beginning, algorithms were created
0:47:19 > 0:47:21by mathematicians for mathematicians.
0:47:21 > 0:47:23And over the last century,
0:47:23 > 0:47:26algorithms have been created for computers.
0:47:29 > 0:47:33But perhaps our relationship is about to go through a dramatic revolution.
0:47:39 > 0:47:41At Microsoft Research in Cambridge,
0:47:41 > 0:47:46scientists are using new techniques to develop algorithms...
0:47:46 > 0:47:50blurring the boundary between inventor and the algorithm itself.
0:47:56 > 0:47:59This is the Kinect skeletal-tracking algorithm.
0:47:59 > 0:48:02The amazing thing is that it's able to identify
0:48:02 > 0:48:04the different parts of my body.
0:48:04 > 0:48:08So you can see it's coloured the top of my head in red
0:48:08 > 0:48:11and my right hand here in blue.
0:48:11 > 0:48:13You can see it's coloured my neck green.
0:48:13 > 0:48:16Now, this algorithm has never met me before,
0:48:16 > 0:48:18doesn't know how I'm going to move in space,
0:48:18 > 0:48:22but just using the data coming from this special camera here,
0:48:22 > 0:48:25measuring the distance from the camera to my body,
0:48:25 > 0:48:28it's able to produce this map.
0:48:30 > 0:48:33Whatever posture I take, using nothing more than the input
0:48:33 > 0:48:36from the special depth-sensing camera,
0:48:36 > 0:48:39the algorithm is able to accurately identify,
0:48:39 > 0:48:42pixel by pixel, the different parts of my body.
0:48:46 > 0:48:49It was developed for the Microsoft Xbox console
0:48:49 > 0:48:53to track the movement of a player's body posture in real time.
0:48:58 > 0:49:01But just as remarkable as what this algorithm can do
0:49:01 > 0:49:04is the process behind how it was created,
0:49:04 > 0:49:07as researcher Jamie Shotton explains.
0:49:09 > 0:49:12What's happening is that every pixel in the image,
0:49:12 > 0:49:16we are running an algorithm called a decision tree.
0:49:16 > 0:49:19And you can think of a decision tree as a game of 20 questions.
0:49:19 > 0:49:22So the decision tree is sort of taking a pixel, say, on my hand,
0:49:22 > 0:49:25and trying to decide, OK, I've got to colour that blue
0:49:25 > 0:49:28- because that's on the hand rather than on my body.- Yes.
0:49:28 > 0:49:31The key to a decision tree is the fact that the 20 questions
0:49:31 > 0:49:33that you ask are not the same
0:49:33 > 0:49:37for every pixel that we're trying to classify.
0:49:37 > 0:49:39And the full set of the possible questions
0:49:39 > 0:49:43that could be answered is exponential.
0:49:43 > 0:49:46- It's two to the twenty.- Right, OK. That's over a million questions,
0:49:46 > 0:49:49a lot of questions you're going to have to program in there.
0:49:49 > 0:49:51Yes. It would take far too long
0:49:51 > 0:49:55and be far too error-prone for us as humans to program that by hand.
0:49:55 > 0:49:58- So, the algorithm's kind of writing itself, or...?- Absolutely.
0:50:02 > 0:50:05The algorithm was not designed by Jamie
0:50:05 > 0:50:08but instead through a process called machine learning.
0:50:11 > 0:50:15It involved showing the algorithm millions of training images,
0:50:15 > 0:50:19of bodies in different poses and of various shapes and sizes,
0:50:19 > 0:50:23from the very fat to the very thin, the very short to the very tall.
0:50:24 > 0:50:28And from this, the algorithm essentially learned by example,
0:50:28 > 0:50:31devising its own rules.
0:50:34 > 0:50:37Where our intelligence comes in as the designers of the system
0:50:37 > 0:50:41is not in programming the algorithm, per se,
0:50:41 > 0:50:44but in designing the training data set
0:50:44 > 0:50:48to capture all of the kind of variations that we expect to see
0:50:48 > 0:50:51when we deploy this system in people's living rooms
0:50:51 > 0:50:52to play their games.
0:50:52 > 0:50:55So in the end, do you actually know what the algorithm is doing?
0:50:55 > 0:50:57We can get a sense of what it's trying to do
0:50:57 > 0:50:59and how it's roughly working,
0:50:59 > 0:51:02but we couldn't possibly really understand what exactly is going on.
0:51:04 > 0:51:09The same approach of machine learning has been used in other applications.
0:51:09 > 0:51:14For example, this algorithm is able to do something that for a long time
0:51:14 > 0:51:19was thought to be a skill exclusive to neurosurgeons and radiologists.
0:51:19 > 0:51:22From an MRI scan, the algorithm can identify
0:51:22 > 0:51:26and map a brain tumour in 3-D.
0:51:26 > 0:51:29Meaning that a job that normally takes an hour
0:51:29 > 0:51:31can be done in a matter of minutes.
0:51:34 > 0:51:37Professor Chris Bishop is interested in developing
0:51:37 > 0:51:40the concept of machine learning even further.
0:51:40 > 0:51:44To create algorithms that can learn just like we do,
0:51:44 > 0:51:46directly from experience.
0:51:49 > 0:51:52So this demonstration, I think, illustrates the direction
0:51:52 > 0:51:54that algorithms will go in the years ahead.
0:51:54 > 0:51:57OK, I can see a lot of films up here, so what is the algorithm going to do?
0:51:57 > 0:52:00We've got a couple of hundred of the most commonly watched films,
0:52:00 > 0:52:02and what it's going to do,
0:52:02 > 0:52:06it's going to learn about your personal likes and dislikes.
0:52:06 > 0:52:08It's already been trained,
0:52:08 > 0:52:11so it's a machine-learning algorithm behind the scenes,
0:52:11 > 0:52:14but it's already been trained on data from about 10,000 people.
0:52:14 > 0:52:18What it's going to do now is to learn about your preferences.
0:52:18 > 0:52:20At the moment it knows nothing about you,
0:52:20 > 0:52:22so these films are just arranged at random on the screen.
0:52:22 > 0:52:25What I need you to do is to find one of these films,
0:52:25 > 0:52:28either one that you like or one that you don't like.
0:52:28 > 0:52:31If you like it, you can drag it across to the green region,
0:52:31 > 0:52:33if you don't like it, across to the red region.
0:52:33 > 0:52:35Rushmore, I'm a big fan of Rushmore.
0:52:35 > 0:52:37You like Rushmore? OK, right.
0:52:37 > 0:52:41So what's happening now is that if a film is down the right-hand side
0:52:41 > 0:52:44- near the green region, it's very confident you'll like it.- OK.
0:52:44 > 0:52:46So down here close to the red region,
0:52:46 > 0:52:48it's very confident you won't like it.
0:52:48 > 0:52:51In the middle, it's 50-50. It doesn't really know.
0:52:51 > 0:52:54So if I choose a movie in the middle here,
0:52:54 > 0:52:57I'm not a great Austin Powers fan, so let's shoot that one...
0:52:57 > 0:53:00So you see, they're beginning to spread out sideways,
0:53:00 > 0:53:04- it's going to be a little bit more confident.- It's pretty good.
0:53:04 > 0:53:07I'm a big fan of Dr Strangelove
0:53:07 > 0:53:11and I'm a big fan of Woody Allen,
0:53:11 > 0:53:14but Spinal Tap, it thinks I'll like that.
0:53:14 > 0:53:18So that's interesting, so when it was confident you liked them
0:53:18 > 0:53:19and you said you liked them,
0:53:19 > 0:53:22not much happened because it didn't learn much.
0:53:22 > 0:53:25When it was confident you'd like it, in the case of Spinal Tap
0:53:25 > 0:53:28and you said, "I don't like it," there was a big change.
0:53:28 > 0:53:30It's learning things from me.
0:53:30 > 0:53:33I'm actually changing the algorithm as I interact with it.
0:53:33 > 0:53:36Exactly. Whereas Kinect was trained in the laboratory and then frozen,
0:53:36 > 0:53:38this algorithm continues to adapt
0:53:38 > 0:53:41and continues to evolve throughout its life.
0:53:41 > 0:53:44The more films that you rate as like and don't like,
0:53:44 > 0:53:45the more it knows about you personally
0:53:45 > 0:53:48and the better able it is to make good recommendations.
0:53:48 > 0:53:52This algorithm is beginning to feel much more human
0:53:52 > 0:53:54in the way that it interacts with the world.
0:53:54 > 0:53:57Is that your aim, to find a way to produce algorithms
0:53:57 > 0:54:00that are a bit like the way that we negotiate the world?
0:54:00 > 0:54:03Exactly. It's a step down that very long road to producing machines
0:54:03 > 0:54:05that really are as capable as the human brain.
0:54:05 > 0:54:08We've a long way to go, but this is a small step in that direction
0:54:08 > 0:54:10because it's not fixed any more.
0:54:10 > 0:54:12It's now continuing to learn just the same way
0:54:12 > 0:54:14that we continue to learn in our daily lives.
0:54:19 > 0:54:21I think we're just starting
0:54:21 > 0:54:24to realise the full potential of algorithms
0:54:24 > 0:54:26and I have one more place I want to visit,
0:54:26 > 0:54:28which I'm told will give me a glimpse
0:54:28 > 0:54:31of just how much they are able to do for us.
0:54:40 > 0:54:43It's a world where almost everything is automated.
0:54:46 > 0:54:49Where algorithms are in control.
0:54:49 > 0:54:53It's the largest automated grocery warehouse on earth.
0:54:53 > 0:54:57It belongs to the online grocery retailer Ocado
0:54:57 > 0:55:01and it's the equivalent of 45 supermarkets in one.
0:55:02 > 0:55:06Over two million items flow through this warehouse every day.
0:55:06 > 0:55:10At any one time, there are something like 7,000 crates
0:55:10 > 0:55:12going over 25 kilometres of track,
0:55:12 > 0:55:18and controlling every aspect of this astonishing spectacle are algorithms.
0:55:25 > 0:55:29Each of those red crates is part of a customer order
0:55:29 > 0:55:32and they may go on from here to find other items
0:55:32 > 0:55:35that they want across the warehouse,
0:55:35 > 0:55:37until they are eventually finished,
0:55:37 > 0:55:41loaded onto a van and then driven out by our routing system
0:55:41 > 0:55:43on a route, which in many ways,
0:55:43 > 0:55:47is solving problems like the travelling salesman problem.
0:55:47 > 0:55:49There are decisions being made all over the place
0:55:49 > 0:55:52as a red crate goes this way and then that way.
0:55:52 > 0:55:55The complexity behind all this is beyond
0:55:55 > 0:55:58what any human could control or solve,
0:55:58 > 0:56:01and that is where these algorithms,
0:56:01 > 0:56:03these problem-solving techniques come in
0:56:03 > 0:56:05to overcome those challenges.
0:56:11 > 0:56:15Everywhere you look, the invisible hand of the algorithm is at work.
0:56:16 > 0:56:20Forecasting algorithms monitor and replenish the stock
0:56:20 > 0:56:24of more than 43,000 products, anticipating customer demand.
0:56:26 > 0:56:29Control system algorithms manage the traffic
0:56:29 > 0:56:33of the more than 7,000 crates around the warehouse.
0:56:36 > 0:56:39And van routing algorithms control the movement of the fleet
0:56:39 > 0:56:41of over 1,500 vans,
0:56:41 > 0:56:46testing over four million different route combinations every second.
0:56:48 > 0:56:51You can almost see the mind of the machine at work
0:56:51 > 0:56:54and it's not a static process, so that's why there is a huge amount
0:56:54 > 0:56:59of machine learning in here, so it's like a self-adapting organism.
0:56:59 > 0:57:02It's constantly having to learn how to do it better.
0:57:02 > 0:57:04People couldn't do that.
0:57:04 > 0:57:06The machine has to tune itself.
0:57:10 > 0:57:14So who would you say was actually in control of the whole thing?
0:57:14 > 0:57:17Ultimately, it's the algorithms that are in control.
0:57:17 > 0:57:19I think I'm getting algorithmic hot flushes
0:57:19 > 0:57:22by looking at this amazing thing!
0:57:24 > 0:57:26In some sense, this warehouse is like
0:57:26 > 0:57:28a little microcosm of the modern world.
0:57:28 > 0:57:32Algorithms are running everything from search engines on the internet,
0:57:32 > 0:57:35sat nav, even keeping our credit cards secure.
0:57:35 > 0:57:39Our world wouldn't function without the power of these algorithms.
0:57:45 > 0:57:48The Open University have produced a free pack for you to learn,
0:57:48 > 0:57:52create and discover more about digital technology past and present.
0:57:52 > 0:57:55To order your copy, phone...
0:57:58 > 0:58:00..or follow the link below
0:58:00 > 0:58:01to the Open University.