Anany Levitin - Polyomino Puzzles and Algorithm Design Techniques - G4G13 April 2018 - バイリンガル字幕
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,
if it is just review.
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.
Pajitna from 1984.
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.
In next example,
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.
Thank you.
さらなる機能をアンロック
Trancy拡張機能をインストールすると、AI字幕、AI単語定義、AI文法分析、AIスピーチなど、さらなる機能をアンロックできます。
主要なビデオプラットフォームに対応
TrancyはYouTube、Netflix、Udemy、Disney+、TED、edX、Kehan、Courseraなどのプラットフォームにバイリンガル字幕を提供するだけでなく、一般のウェブページでのAIワード/フレーズ翻訳、全文翻訳などの機能も提供します。
全プラットフォームのブラウザに対応
TrancyはiOS Safariブラウザ拡張機能を含む、全プラットフォームで使用できます。
複数の視聴モード
シアターモード、リーディングモード、ミックスモードなど、複数の視聴モードをサポートし、バイリンガル体験を提供します。
複数の練習モード
文のリスニング、スピーキングテスト、選択肢補完、書き取りなど、複数の練習方法をサポートします。
AIビデオサマリー
OpenAIを使用してビデオを要約し、キーポイントを把握します。
AI字幕
たった3〜5分でYouTubeのAI字幕を生成し、正確かつ迅速に提供します。
AI単語定義
字幕内の単語をタップするだけで定義を検索し、AIによる定義を利用できます。
AI文法分析
文を文法的に分析し、文の意味を迅速に理解し、難しい文法をマスターします。
その他のウェブ機能
Trancyはビデオのバイリンガル字幕だけでなく、ウェブページの単語翻訳や全文翻訳などの機能も提供します。