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