Transcript Very Natural Computing

Very Natural
Computing
Piotr Chrząstowski
Mimicking the nature
• Man always tried to learn from nature
some fresh ideas.
• The nature rewarded man with many
interesting and useful solutions.
• Sometimes it is quite worthy to look
around and discover „inventions” ready to
use.
Helicopter
Submarine
Polartec
Naps
Planes
How about algorithms?
• Is there any way to use the forces of
nature in order to increase our computing
abilities?
• Can we learn something just looking
around us?
• Does nature compute anything? Or maybe
computing is purely human attitude?
Natural Computing
• Genetic and evolutionary algorithms – using
natural selection to find better solutions
• Quantum computing – using quantum
mechanics to simulate nondeterminism
• Biological computing – DNA plays the role of a
processor
• Neural computing – constructing artificial neural
networks in order to mimic the learning process
of human brain.
Very Natural Computing
• We will use pure forces of nature. No real
algorithms will be needed.
• What is needed: a proper experiment
setting, and physics will provide us with
the solution.
Sorting
• Given n real numbers. List them from the largest
to the smallest.
• Solution: Cut the appropriate length sticks and let
them freely stand on the table. They are already
sorted. What is needed is to take one after one
from the tallest to the smallest.
• Gravity sorts in constant time! Only preparation of
data and presenting the result takes O(n) time.
Convex hull
• Problem: Find the smallest polygon surrounding
given set of points on Euclidean plane
• Solution: Draw the points on the plane and drive
nails in perpendicularly one at each of the
points. Use rubber stripe to surround the points.
The polygon is formed.
• Again, regardless of the number of points given,
it takes constant time for a rubber to determine
the convex hull.
Jacob Steiner
• Jacob Steiner (17961863)
• Swiss mathematician
• One of the greatest
geometers in the
history of
mathematics.
Steiner problem
• Given n points on the Euclidean plane.
Span these points with the smallest
amount of cable.
• Some extra points may be added, where
cable segments meet. They are called
Steiner points.
First attempts
Some improvements
Yet not the best...
The solution!
Shortest path joining vertices of a
triangle
Discrete Steiner problem
• Find the shortest Steiner tree on a grid
• A lot of research has been done in this
srea, but no satisfactory solution has been
found.
• This is an NP-complete problem
What is known about Steiner trees?
• Edges are segments,
• In each added point (Steiner point) exactly 3 edges
meet at angles 120º
• There are at most n-2 Steiner points needed to span
optimally n given points.
• Steiner problem is not compositional
• The ratio between the total length of the optimal Steiner
tree and the minimum spanning tree (without additional
points, easily computable for instance by Kruskal or Prim
algorithms) is at least √3/2≈0.87. This result known as
Gilbert and Pollak hypothesis from 1968 was proven as
late as in 1991 by Zhu and Hwang.
Related 3D problem
• 3D version of Steiner problem: find the
minimal surface that connects given set of
points.
• Even for such simple shape as 12 edges
of cube, the shape is extremely complex. It
does not contain any single piece of plane.
And in fact no rigorous proof is known that
this known shape is minimal.
Cube
Octahedron
Octahedron (2)
Octahedron (3)
The best!
Brain
• Human brain is a very natural computer
• It solves many problems incredibly fast,
and we often have no idea, how it does.
• It surprises us
Illusions -
Our brain is sometimes an
unpredictable processor