Marostica Piazza degli Schacchi
M.C. Escher “Chess”
CONOSCERE CONOSCERSI
COMUNICARE
Maurits Cornelis Escher
(Olanda 17 Giugno 1898 – 27 Marzo 1972)
Ampia galleria delle opere:
http://www.nga.gov/collection/gall
ery/ggescher/ggeschermain1.html
disegno di Escher
Parte Sesta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
2
Mosse del cavallo
Possibili mosse del cavallo su una scacchiera
Parte Sesta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
3
Problema
• Si può fare il giro di tutte le caselle di una
scacchiera passando per ognuna una e una
sola volta e tornare con un’ultima mossa
nella posizione iniziale?
• Iniziare con scacchiere piccole.
Parte Sesta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
4
Esempi
•
•
•
•
•
•
2X3
3X3
3X4
….
….
8X8
Parte Sesta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
5
2X3
• Scacchiera minima
compatibile con le
mosse del cavallo.
• Non è possibile
ricoprire tutta la
scacchiera.
Parte Sesta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
6
3X3
• Si ricoprono tutte le
caselle?
• Avanti per la
soluzione.
• Non è possibile
ricoprire la scacchiera
Parte Sesta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
7
3X4
• Si ricoprono
tutte la
caselle?
• Avanti per la
soluzione.
Parte Sesta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
8
3X4
• Ecco tutte le
possibili mosse
• è possibile un
tour completo?
• Proviamo a
sciogliere il
grafo.
Parte Sesta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
9
3X4
• Grafo sciolto.
• Esiste un tour di tutti i vertici?
1
5
2
3
6
9
Parte Sesta
4
8
7
10
11
12
2
9
11
8
7
1
Conoscere - Conoscersi - Comunicare
Sonia Fiori
4
5
10
3
6
12
10
3X4
• Si, si ricopre la
tastiera
• ma non è un ciclo
chiuso, un
circuito. I vertici
2, 11, 10, 3 sono 7
dispari, allora per
il teorema di
Eulero……
11
8
1
Parte Sesta
2
9
4
5
10
Conoscere - Conoscersi - Comunicare
Sonia Fiori
3
6
12
11
3X4
• Cammino riportato sulla scacchiera
Parte Sesta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
12
8X8
Si può provare a costruire un circuito
collegandosi al sito:
www.midaslink.com/east/knight.htm
è difficile!!
Parte Sesta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
13
8X8 Strategia
Regola di H.C. Warnsdorff (1823-Germania):
• dalla casella occupata si individuano le caselle
raggiungibili
• da ognuna si calcolano le possibili mosse
• si sceglie la casella con il numero minore
Questa è una regola EURISTICA: procedimento
che sembra giusto ma di cui non si ha alcuna
garanzia.
Parte Sesta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
14
8X8 I casi buoni
La regola funziona fino a scacchiere 76X76
(verifica con calcolatori).
Perché non ha soluzione con scacchiere
con un numero dispari di caselle?
Il problema ha soluzione per scacchiere:
• 3X10 o 5X6 minima rettangolare
• 6X6 minima quadrata……
Parte Sesta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
15
Ancora lui
Eulero aveva determinato una soluzione del
problema per una scacchiera 8X8.
Osservare il
circuito
Parte Sesta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
16
Definizioni
• Cammino di Hamilton:
un cammino che passa da tutti i vertici una
e una sola volta.
• Circuito di Hamilton:
un cammino di Hamilton in cui il punto di
partenza e quello di arrivo coincidono.
Parte Sesta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
17
Sir William Rowan Hamilton
(Irlanda 1805 – 1865)
• Matematico, fisico e
astronomo molto precoce negli
studi, studiò molte lingue
straniere sia europee sia
orientali.
• All’età di 22 anni fu nominato
professore al “Trinity College”
di Dublino.
• Inventore del gioco “The
icosian game”
Parte Sesta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
18
The icosian game
Trovare un circuito di Hamilton del seguente grafo.
Questo è il grafo di un dodecaedro schiacciato su un piano
Parte Sesta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
19
I 5 solidi platonici
• tetraedro
• cubo o isaedro
• ottaedro
• dodecaedro
• icosaedro
per visione solidi in movimento
www.math.utah.edu/~alfeld/math/polyhedra/polyhedra.html
per sviluppo piano dei solidi:
http://www.cs.mcgill.ca/~sqrt/unfold/unfolding.html
Parte Sesta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
20
Platone
(Grecia 428 - 347 a.c.)
Filosofo greco, aveva abbinato i cinque
elementi della natura ai cinque solidi
• fuoco tetraedro
• terra cubo
• aria ottaedro
• acqua icosaedro
• quinta essenza dodecaedro
Disegno di Johannes Kepler (tedesco 1571 – 1630)
Parte Sesta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
21
Relazioni solidi platonici
nome
tipo faccia
Facce
Vertici
Spigoli
Tetraedro
triangolo
4
4
6
cubo
quadrato
6
8
12
ottaedro
triangolo
8
6
12
dodecaedro pentagono
12
20
30
icosaedro
20
12
30
Parte Sesta
triangolo
Conoscere - Conoscersi - Comunicare
Sonia Fiori
22
Alcuni solidi schiacciati
• tetraedro
• cubo
• dodecaedro
Parte Sesta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
23
Soluzione
14
Seguire i numeri
13
20
18
19
12
1
5
11
2
3
4
6
15
10
8
7
17
Parte Sesta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
9
16
24
Altri cammini
Trovare se esistono circuiti hamiltoniani per
gli altri solidi platonici
Gioco di Mines weeper
Parte Sesta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
25
Conclusione
Non esiste ancora una regola generale
dimostrata, cioè un teorema che ci assicuri
l’esistenza o meno di un cammino di
Hamilton di un qualunque grafo.
Parte Sesta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
26
Problemi NP = Problemi decisionali
Un problema è decisionale se dobbiamo
rispondere con un si o con un no, e la
risposta si è accompagnata da una
dimostrazione verificabile in modo
efficiente.
La verifica se un cammino è di Hamilton in
un grafo è un problema decisionale.
Ma….
Parte Sesta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
27
Ma….
…..dato un grafo G, G è privo di circuiti di
Hamilton?
• trovare tutti i circuiti
• verificare che non sono di Hamilton.
Il numero di circuiti e di verifiche in generale
diventa un numero enorme (ricordasi Giulio
che vuole visitare tutti i suoi amici)….
Parte Sesta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
28
Hard
…il problema è molto più difficile = NP Hard
Problemi P = trattabili
Problemi NP = difficili
Problemi NP-Hard = difficili in NP
Parte Sesta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
29
Esempi problemi NP-Hard
• mosse del cavallo in una scacchiera
• raccolta nettezza urbana caso misto
• cammini minimi con pesi negativi
• fori nelle schede elettroniche
• disegnare con il plotter un insieme di punti
• gioco “campo fiorito” o “minesweeper”
• …problema del commesso viaggiatore
• …
sono tutti problemi di ricerca di un cammino di
Hamilton
Parte Sesta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
30
Esempi problemi più facili P
• raccolta semplice nettezza urbana
• pulizia strade
• controllo linee elettriche
• cammino minimo
• …
sono tutti problemi di ricerca di un cammino
di Eulero
Parte Sesta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
31
Ultime ricerche
Esistono algoritmi tali che
problemi NP = problemi P ?
E’ una delle domande a cui i ricercatori
cercano di rispondere.
Uno dei 7 problemi del millennio
Parte Sesta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
32
Parole chiave
•
•
•
•
•
•
Euristica
Cammino di Hamilton
Circuito di Hamilton
Solidi platonici
Problemi NP
Problemi NP-Hard
Parte Sesta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
33
Fine
sesta parte
Parte Sesta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
34
NP-Hard
• Se si riuscisse a risolvere in modo efficiente
un problema NP-Hard allora sarebbero
risolti tutti i problemi NP.
• Un algoritmo efficiente per risolvere un
Problema NP-Hard, “Satisfiability” di
Stefhen Cook (Toronto-Canada 1971),
risolverebbe tutti gli altri problemi NP.
• Ma P = NP ?
Parte Sesta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
35
7 Problemi del millennio
alle pagine: www.claymath.org/millennium/ oppure
http://www.csapt.it/p/pr/premio_clay.html
si trovano 7 problemi non risolti:
1. Ipotesi di Riemann: la distribuzione dei numeri
primi all’interno dei numeri naturali segue una
legge? e in caso affermativo quale?
2. La teoria di Yang-Mills e l’ipotesi dei gap di
massa. Le equazioni di Y-M derivano dalla fisica
quantistica e furono formulate 50 anni fa per
descrivere tutte le forze della natura, eccettuata
la gravità.
Parte Sesta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
36
e ancora
3. P = NP cioè per uno qualsiasi dei problemi
difficili in NP esiste un algoritmo efficiente?
4. Le equazioni di Navier-Stokes. Le Equazioni di
Navier Stokes descrivono il comportamento dei
fluidi e dei gas. Sono state scoperte nel
diciannovesimo secolo ma ancora non sono state
comprese. Il problema è elaborare una teoria
matematica che consenta di comprenderle ed
analizzarle. Questa teoria sarebbe molto utile per
gli studi di aerodinamica.
Parte Sesta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
37
e infine
5. La congettura di Poincarè. Se tendiamo un
elastico interno ad una mela, possiamo contrarlo
fino a ridurlo ad un punto muovendolo
lentamente (senza strapparlo e senza staccarlo
dalla superficie)?
6. La congettura di Birch e Swinnerton-Dyer.
Quanti punti razionali ha una curva ellittica?
7. La congettura di Hodge. La Congettura Hodge
riguarda gli spazi proiettivi e le varietà
algebriche. I cicli di Hodge sono delle
combinazioni lineari razionali di cicli algebrici.
Parte Sesta
Conoscere - Conoscersi - Comunicare
Sonia Fiori
38