Talk outline
How do we find jigsaw pieces fitting a certain set of requirements?
Has Red
Has Blue
Is Light
On side
Has a house
Has some blue
Red at the top
Not at a side
Dark
Snow
Has a window
Big bag of all possible properties a piece can have
Is Dark
Has Red at Top
One pile for each property
Where does it go?
Give me a piece which is not on a side, has some red at the top and a piece of house to the right.
I don’t have that combination in my index.
I’m sorry Alice.
Give me a piece with some red.
I found this
Has Blue & has Red
is Light & has Red
On side & has Red
Is Dark & has Red
Has Red at Top & has Red
Has Red & has blue
Has Blue & has blue
Is Light & has blue
On side & has blue
Is Dark & has blue
Has Red at Top & has blue
Has Red & is Light
Has Blue & is Light
Is Light & is Light
On side & is Light
Is Dark & is Light
Has Red at Top & is Light
Has Red & on side
Has Blue & on side
Is Light & on side
On side & on side
Is Dark & on side
Has Red at Top & on side
Has Red & is dark
Has Blue & is dark
Is Light & is dark
On side & is dark
Is Dark& is dark
Has Red at Top & is dark
Has Red & on red top
Has Blue & on red top
Is Light & on red top
On side & on red top
Is Dark & on red top
Has Red at Top & on red top
Has Red & has Red
36 pairs from 6 properties.
With 100 properties we get 10000 possible pairs.
If we have 100 properties and need all quadruples...
Puzzle copy 1
Puzzle copy 2
Puzzle copy 3
is Light & has Red
Is Dark & has blue
Has Red & is dark
Has Blue & on side
On side & is dark
Not side & red top
is Light & has Red
Is Dark & has blue
Has Red & is dark
Has Blue & on side
On side & is dark
Not side & red top
is Light & has Red
Is Dark & has blue
Has Red & is dark
Has Blue & on side
On side & is dark
Not side & red top
99,994 more
99,994 more
99,994 more
Has a house
Has some blue
Red at the top
Not at a side
Dark
Snow
Has a window
Where do I go?
Is Dark & has blue
Has Red & is dark
Not side & red top
Is Dark & has blue
Has Red & is dark
Not side & red top
Is Dark & has blue
Has Red & is dark
Not side & red top
Is Dark & has blue
Has Red & is dark
Not side & red top
Has Red & is dark
Not side & red top
Is Dark & has blue
Has Red & is dark
Puzzle copy 1
Puzzle copy 2
Puzzle copy 3
is Light & has Red
Is Dark & has blue
Has Red & is dark
Has Blue & on side
On side & is dark
Not side & red top
is Light & has Red
Is Dark & has blue
Has Red & is dark
Has Blue & on side
On side & is dark
Not side & red top
is Light & has Red
Is Dark & has blue
Has Red & is dark
Has Blue & on side
On side & is dark
Not side & red top
99,994 more
99,994 more
99,994 more
Where do I look?
Give me a piece which is dark, has some blue at the top and a piece of house to the right.
On side & is dark
J = |Requirement|/|Piece|
= 14/34 ~ 0.4
1
4
11
2
3
9
12
14
10
13
7
8
5
17
15
16
6
Requirement key:
Piece key:
9
10
9
13
Keys not equal!
Success probability:
~ J2 ~ 16%
Repeat ~ 16 times for 95% percent success probability.
Show Interactivity in mathematica
Tada!
You are now up to date with the state of the art.
Give me a piece which is not on a side, has some red at the top and a piece of house to the right.
I’m 95% sure there is no such piece.
Can you do the search again?
I’m afraid that will give exactly the same result, Alice.
Humans are good at “pattern match” type problems, but we also make mistakes sometimes.
But computers are not human...
RP = ZPP?
J = / ( + )
Requirement
Piece
How many worms do we need,
The golden question:
such that for any Piece and� Requirement with J ≥ some value,
there is at least one worm, which� visits k before it visits any ?
For = 1, and = 1, and k = 1, two worms suffice.
Find the smallest worm family for
= 1, = 2, k = 1!
This list might answer your question:
D | 3 | 4 | 5 | 6 | 7 | 8 |
| 3 | 3 | 4 | 4 | ... | ... |
I gave up after 7.
For = 1, and = 2, k = 1, and D=4 , three worms suffice.
1
2
3
4
3
2
1
4
4
2
1
3
Main results
Of Thesis
Techniques
Of General Construction
1
2
3
4
I know a method, that probably is useful.
I just keep taking random worms until I have a working family.
2
3
5
6
4
1
Problem:
4
2
3
6
5
1
1
2
4
3
6
5
2
4
3
1
6
5
5
2
6
1
3
4
5
4
3
6
2
1
Success!
A doubling trick:�For = 1, and = 1, k = 1, and D=4 �To = 2, and = 2, k = 2, and D=8
Necklace splitters
Two cuts always suffice!
Thank you!
Necklace splitters
For = 1, and = 2, k = 1, and D>5 , three worms don’t suffice.
Given a sequence of (n−1)2 + 1 numbers,
Then there are n which are in order or reverse order.
Example: 4, 5, 2, 3, 1
Example: 2, 4, 1, 3, 5
Given D = 5
Use worm 1 to make an order.
After worm 2, there are three in order. (3-1)2 + 1 = 5
After worm 3, there are two in order. (2-1)2 + 1 = 3
Hm, we can only prove it for D=17. :(
Krav
Brik
Delmængder
Motivation, Flere patenter uddelt�Orme�Algoritme�Konstruktioner, eksempler�Konstruktioner for 1+2?�Konstruktioner med halskæder
F
Hvad skal folk have ud af det?
Lære noget om datalogi?
Lære noget om kombinatorik?�Opleve noget sjovt matematisk?
Filosofisk, mennesker kan gøre ting effektivt, men laver fejl. Er det også en must for computere?
What is this about?
Algorithms for BIG DATA