You Well, thank you for coming.
I'm going to talk about polemino puzzles and algorithm design techniques in Russian, but you will be able to read it.
The talk is in the memoriam of Solomon Gollum,
a school of mathematics and engineering, father of poleminos, and regular participants of the gathering for gardening meetings.
brief history of polynomials,
due to published the dissection problem and the canton berry puzzles in 1907,
many polynomials problems under the name of dissection problems and appeared in the 1930s and 1940s in the British puzzle journals,
The name polynomials was introduced in 1953, than 20-year-old Harvard PhD student who later published his seminal monograph on the subject.
And, of course, Polyminos were popularized by Martin Gardner in his scientific American columns twice.
Some recreational problems with Polyminos.
There are hundreds of problems dealing with styling, but we also have Pintomeno Game, suggested by Gollum himself and solved by Hillary Orman.
And there are world famous tetras.
In one person game with stetraminos and invented by Russian program Alex C.
The main observation of my...
So despite the mathematical rather than computer science origins, some polynomial puzzles are excellent illustrations of important ideas in the design and analysis of algorithms.
Let's start with divide and conquer, which is a strategy that works by partitioning the problem into several small sub-problems.
solving each of them recursively and then combine the solutions to get a solution to the additional problem.
as a tiling with L-terminus, a 2 to the n by 2 to the n board with 1 missing square with L-terminus.
It's not only a example of a puzzle solved by divided in concrete,
it's also an excellent educational example of recursive algorithm,
which is better than the traditional examples of computing and factorial or solving the tau of Hanoi.
Another good example of applying divide and conquer is to divide the region in the shape
of an ultraminar into four to the k congruent regions.
So here in addition to using divide and conquer,
the algorithm takes advantage of the effects that an ultraminar is reptile,
determined and produced by golem for shapes that can be dissected into smaller copies of themselves.
The next strategy is decrease in conqueror,
which is worked by exploiting a relationship between a solution to a problem's instance and the small instances of the same problem.
Most computer science examples are either decreased by one or decreased by half.
path, polynomial no tiling provides other examples, such degrees by 3, degrees by 4, and degrees by 6.
One example is to tile an n by n board with straight terminals.
If n is not a multiple of 3, which a trivial case, we have an excellent example of applying degrees by 3.
The next strategy, transform a conquer, which is the solving strategy based on the idea of transformation.
A good example here, styling is region bounded by a polygonal line made up of vertical angle.
which can be solved by maximum cardinality-maching algorithm applied to the bipartite graph representing squares of the region.
I have a dynamic programming example.
When have to tie a tooth by a rectangle with dominoes,
and one can set up a typical dynamic programming recurrence which happens to be leading to Fibonacci sequence.
My last example is probably the most famous puzzle invented by Gollum.
It's so-called mutilated check board problem.
And the question is whether it's possible to tile with dominoes and ate by a check board with two one by one.
squares cut off from two diagonally opposite corners.
And the answer is no, and the proof is one sentence based on using coloring and parity as invariance.
Now, on a gift exchange, you will find two simple but elegant puzzles related to the topic
of my talk, and if you're interested in more examples.
You can find them either in monographs by golem or the book by Martin and Pauline Menose
or in my book on algorithmic puzzles or a paper I gave a couple of years back on this topic.
