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는 비디오 이중 자막 뿐만 아니라 웹 페이지의 단어 번역 및 전체 문장 번역 기능도 제공합니다.