Available online
Description
Essentially, this programme takes an overview of the whole course; particularly emphasising the course's approach to some large problems in combinatorics using algorithms. The examples chosen incl...ude traffic-flow problems, selecting placings at a meal-table, and tracing paths through a maze. The latter example uses the Hampton Court maze, where linking items in the programme were filmed.
Essentially, this programme takes an overview of the whole course; particularly emphasising the course's approach to some large problems in combinatorics using algorithms. The examples chosen incl...ude traffic-flow problems, selecting placings at a meal-table, and tracing paths through a maze. The latter example uses the Hampton Court maze, where linking items in the programme were filmed.
| Module code and title: | TM361, "Graphs, networks and design" |
|---|---|
| Item code: | TM361; 16 |
| First transmission date: | 14-10-1981 |
| Published: | 1981 |
| Rights Statement: | |
| Restrictions on use: | |
| Duration: | 00:25:00 |
| + Show more... | |
| Producer: | Ted Smith |
| Contributors: | K Appel; Roy Nelson; Richard Scott; Robin Wilson |
| Publisher: | BBC Open University |
| Keyword(s): | Algorithms; Combinatorics; Maze; Meal table; Traffic-flow problems |
| Footage description: | The programme opens with shots of Hampton Court Palace and the famous maze. Roy Nelson introduces the programme. He points out that there is an algorithm, Tarry's algorithm, which is an infallible method for finding a way out of any maze in reasonable time. Nelson does not go into details. The rest of the programme consists of a series of excerpts from earlier programmes which review certain classes of problems studied in the course. The first excerpt is one from TV9 in which Rook polynomials are used to deal with the probleme des menages. Shots of people sitting around a dinner table. Excerpt from TV4 reviews the problem of constructing error correction codes for transmission signals. The signal code from the Mariner 9 probe to Mars is used as an example. Excerpts from TV 12 reviews existence problems. The example in this case is the proof of the four colour map problem. Professors Appel and Haken, who came up with the proof, are interviewed. They discuss the techniques they used. Excerpt from TV11 in which two algorithms were examined and compared for solving transportation problems. Roy Nelson discusses the meaning of 'efficiency' as applied to algorithms. Excerpt from TV7 looks at computer models of the national electricity grid. The algorithm is used to predict demand on the grid at certain times and places. The excerpt emphasises the need for efficient algorithms for certain classes of problems. Excerpt from TV3 shows an example of a polynomial time algorithm, a fairly efficient method for solving problems. In this excerpt the minimum travel cost shortest route for a road network are calculated. Roy Nelson closes the programme with a discussion of problems such as the travelling salesman problem, which cannot be solved in polynomial time but require an inordinate amount of time to solve because N increases exponentially. |
| Production number: | FOUT125X |
| Videofinder number: | 1537 |
| Available to public: | no |
