The knapsack problem is a problem in combinatorial optimisation.
Imagine you are going to visit your friends for whom you have bought lots of presents. So many, in fact, that you can’t fit them all in your luggage meaning you must leave some behind. If we decide to pack a combination of presents with the highest value but that doesn’t exceed the weight limit imposed by airline, how can we find such a combinations? This is the Knapsack Problem.
We could solve this by trying all the possible combinations, calculating their value and weight and then picking one that is below the weight limit but maximises the value. Whilst this is okay when we are dealing with a small number of items, it is simply unfeasible when the number of items is large as the number of combinations is too big. So, is there an algorithm which can work for any number of items that doesn’t take too long?
Computer scientists have a way of measuring the complexity of a problem by how fast the time taken grows as the size of the input increases. Polynomial growth, i.e. if the size of the input is n then the time taken grows by a factor of n^k, describes and ‘easy problem’; the growth is nowhere near as “explosive” as exponential growth, e.g. 2^n.
Whether or not a polynomial time algorithm exists to solve the knapsack problem is unknown, meaning it is in a class of problems called NP-Hard Problems.
Class P: problems that can be solved in polynomial time
Class NP: a potential solution can be checked in polynomial time
NP-Complete: within the NP class but particularly hard
NP-Hard: as least as hard as the NP class.
It is possible that the NP class = P class, though this is still unknown (and is one of the Millennium Prize Problems), hence the two diagrams above.
P.S. My posts may be more sporadic in the next month because I’m in exam term!
The Josephus Problem is a problem in computer science based on a counting-out game. The problem is named after Flavius Josephus, a Jewish-Roman historian from the 1st century, who tells the story like this:
“A company of 40 soldiers, along with Josephus himself, were trapped in a cave by Roman soldiers during the Siege of Yodfat in 67 A.D. The Jewish soldiers chose to die rather than surrender, so they devised a system to kill off each other until only one person remained. (That last person would be the only one required to die by their own hand.)
All 41 people stood in a circle. The first soldier killed the man to his left, the next surviving soldier killed the man to his left, and so on. Josephus was among the last two men standing, “whether we must say it happened so by chance, or whether by the providence of God,” and he convinced the other survivor to surrender rather than die.”
This story gives rise to an interesting maths problem: If you’re in a similar situation to Josephus, how do you know where to stand so you will be the last man standing?
This week’s final blog post is on Mary Somerville, born in 1780 in Scotland. She was a science writer who also studied mathematics and astronomy.
She was born to Admiral William George Fairfax, who was the vice admiral of the British Navy, and thus was frequently away at sea. Despite her family’s fortunate economic position, her education was “scant and haphazard”; she only studied her first simple arithmetic at the age of 13. She was enrolled on a writing course and at the same time began her study of algebra as she stumbled upon mysterious symbols in the puzzles of a women’s fashion magazine and was able to persuade her brother’s tutor to purchase some elementary literature on the subject for her.
Somerville married Samuel Greig,who was a member of the Russian Navy, in 1804 when she was 24 years old. However, he died in 1807 after only three years of marriage. His death, and inheritance, allowed Mary the rare opportunity to pursue her intellectual interests. Despite disapproval from her family and friends, she mastered J. Ferguson’s Astronomy and became a student of Newton’s Principia. She corresponded frequently with William Wallace, a Scottish mathematics master at a military college, who encouraged her to study mathematics.
In 1825, she conducted a scientific experiment on magnetism and presented her findings in a paper entitled “The Magnetic Properties of the Violet Rays of the Solar Spectrum“. Apart from the astronomical observations of Caroline Herschel, this was the first paper by a women to be read by the Royal Society and published in its Philosophical Transactions.
Furthermore, in 1827 she was requested by Lord Brougham to translate the “Mécanique Céleste” by Laplace for the ‘Society for the Diffusion of Useful Knowledge’. Somerville went beyond translation and popularising it so that could reach a larger audience by including simple illustrations and experiments so that most people could understand. It was hugely popular and made her incredibly famous – in recognition a portrait of her was commissioned and placed in the Great Hall of the Royal Society.
“I translated Laplace’s work from algebra into common language.”
She also popularised Newton’s Principia and published “On the Connexion of the Physical Sciences“(1834) and “Physical Geography” (1848). Physical Geography was preached against in York Cathedral, however it proved to be her most successful publication to date and was widely used in education for the next 50 years.
Her work granted her honorary membership to the Royal Astronomical Society alongside Caroline Herschel. They were the first women scientists to be awarded such recognition in the community.
Her last scientific book “Molecular and Microscopic Science” was published in 1869. After her death in 1972, her legacy still lives on:
Somerville is the name given to the lunar crater that lies east of the crater Langrenus;
5771 Somerville is a main belt asteroid discovered in 1987 by E. Bowell at Lowell Observatory;
Somerville Island in the Barrow Strait, Nunavut was named for her by Sir William Edward Parry in 1819;
Somerville College Oxford is also named for her;
Mary Somerville was recently in the news as the Royal Bank of Scotland announced that their new polymer £10 notes were going to feature her portrait, and are set to be issued in the second half of 2017.
“Her grasp of scientific truth in all branches of knowledge, combined with an exceptional power of exposition, made her the most remarkable woman of her generation.”
“… certainly the most extraordinary woman in Europe – a mathematician of the very first rank with all the gentleness of a woman … She is also a great natural philosopher and mineralogist.”
The Turing Machine was first described in a paper published in 1936 on computable numbers, by English mathematician Alan Turing, who called it an a-machine and presented it as a thought experiment.
What is a Turing Machine?
A Turing Machine is a theoretical computing machine with an infinitely long tape upon which it manipulates symbols according to the mathematical model that defines it.
This machine is made up of:
A line of cells (“tape”) that can move back and forth
An active element (“head”) that has a property (“state”) and that can change the property (“colour”) of the active cell underneath it
A set of instructions for how the head should modify the active cell and move the tape.
Depending on the symbol and its position on the finite table – represents an algorithm that is necessarily finite – the machine:
Writes a symbol (eg. a number) in the cell
Either moves the tape one cell left or right
Either continues or stops the computation.
With this hypothetical machine, Turing was able to prove properties of computation, and in particular, the uncomputability of Hilbert’s Entscheidungsproblem, also known as the decision problem.
Universal Turing Machine
Alan Turing was able to show that:
if there is a table U such that the head of a Turing machine is programmed in accordance with U;
and if any table P is translated and written out on the machine’s tape;
then the machine will behave as if its head had been programmed in accordance with P.
A Universal Turing Machine is an Turing machine whose head has been programmed in accordance with U.
There are many distinct Universal Machines, all with equivalent computational power, due to the fact that there are many tables that will act like U.
Turing Machines to Computers
The model of the Universal Turing Machine is considered to be the origin of the stored program computer (stores program instructions in electronic memory), which was used by John von Neumann in 1946 for the von Neumann architecture.
However, Turing’s greatest contributions to the development of the digital computer was his establishment of the idea of controlling the function of a computing machine by storing a program of instructions in the machine’s memory, and also his proof that a single, universal machine can carry out every computation.
Chaos theory is the study of dynamical systems, which are extremely sensitive to initial conditions. If we were to change these initial conditions slightly, the outcome would be extremely different, rendering long-term predictions almost impossible. In this post I will give a brief introduction on chaos theory and what it is used for.
Chaos theory originates from the studies of Henri Poincaré concerning the three-body problem (the problem of the motion of three objects in mutual gravitational attraction). In these studies, Poincaré concluded that there can be orbits which are non-periodic and yet they’re not forever increasing nor approaching a fixed point.
Later studies on non-linear differential equations were carried out by G.D. Birkhoff, A.N Kolmogorow, M.L Cartwright, J.E Littlewood, and S. Smale. Apart from Smale, who was probably the first pure mathematician to study nonlinear dynamics, all of these studies were inspired by physics; experiments had shown turbulence in fluid motion and non-periodic oscillation in radio circuits, but there was no theory to describe it.
Although there were some insights in the first half of the 20th century, chaos theory only became formalised after mid-century, after it became clear that linear theory could not describe the behaviour observed in some experiments. The main catalyst for this development was the electronic computer, as much of the mathematics in chaos theory requires repeated iteration of mathematical formulas, something that computers made practical and easy to do.
A pioneer of chaos theory was Edward Lorenz, whose interest was peaked through his work on weather prediction in 1961. He discovered that small changes in the initial conditions produced large changes in the long-term outcome. His discovery, named Lorenz attractors, showed that even detailed atmospheric modelling cannot make precise long-term weather predictions.
In 1982, Benoit Mandelbrot published ‘The Fractal Geometry of Nature‘ (more about fractals here), which became a classic of chaos theory. Following this, in 1987 James Gleick published the book ‘Chaos: Making a New Science‘, which became a best-seller and introduced the principles of chaos theory, as well as its history, to the general public (although it has been said that his description of its history under-emphasised important Soviet contributions).
What is a non-linear dynamical system?
A non-linear dynamical system will exhibit one or more of these behaviours:
it is forever at rest
it is forever expanding
it is in periodic motion
it is in quasi-periodic motion
it is in chaotic motion
The latter is the non-periodic complex motion which chaos theory is concerned with.
For a system to be considered to be chaotic it must satisfy the following properties:
it must be sensitive to initial condition: this is also called ‘the butterfly effect’
it must be topologically mixing: This means it will evolve in the same region for a certain period of time, then eventually overlap with any other given region. This highlights that two adjacent points in a complex system will eventually end up in very different positions after some time has passed.
Some systems seem to be too chaotic to recognise a pattern, however mathematicians began to discover that complex systems often seem to run through a sort of cycle, although situations are rarely repeated. Plotting systems in simple graphs showed that there often seems to be a situation that the system tried to achieve – an ‘equilibrium’. This point is called an attractor.
There is also such a thing as a strange attractor, which is a more dynamic ‘equilibrium’. The difference between these two is that an attractor represents a state to which the system finally settles, whilst a strange attractor represents a trajectory upon which the system runs from situation to situation without ever settling down. The Lorenz attractor described before is an example of a strange attractor.
The discovery of attractors was extremely important as it revealed the concept of self-similarity.
Random or Chaotic?
Chaotic sequences are generated deterministically from a dynamical system:
Random processes are fundamentally different; two successive realisations of a random process will give different sequences, even if the initial state is the same. A random process is non-deterministic.
“All methods for distinguishing deterministic and stochastic processes rely on the fact that a deterministic system always evolves in the same way from a given starting point.”
Chaotic theory has applications to many scientific areas including geology, biology, computer science, economics, engineering, meteorology, physics and politics.
Chaotic behaviour has been observed in many different man-made systems (electrical circuits, lasers, computer models of chaotic processes etc.), as well as in nature (weather, population growth in ecology and movement etc.).
Currently, chaotic theory is being applied to medical studies of epilepsy in order to predict seemingly random seizures by observing initial conditions.