Unplugged
Lezione 9
Problemi veramente difficili - Intrattabilità
Esistono problemi che sono veramente difficili anche per un computer? Sì!
Se è vero che esistono algoritmi che renono i programmi più efficienti, è anche vero che esistono problemi per i quali non esistono soluzioni efficienti, problemi (detti "intrattabili") per cui potrebbero essere necessari milioni di secoli di elaborazione per essere risolti. In questa lezione incontreremo il mistero più appassionante dell'informatica oggi, partendo dall'analisi degli alberi di Steiner.
Il problema dell'albero di Steiner è talvolta chiamato il "problema della rete più breve" perchè consiste nel trovare la rete più breve che collega un insieme di siti.
Sarebbe bello se si potesse dimostrare che non esiste un algoritmo efficiente per trovare la soluzione ottimale di un problema "intrattabile": magari solo in futuro qualche abile programmatore potrebbe sviluppare un trucco originale che risolva il problema.
Strade ghiacciate: gli alberi di Steiner
Nel nord del Canada in inverno gli spazzaneve realizzano strade sugli enormi laghi ghiacciati per mettere in comunicazione siti di perforazione. Con quel freddo si vogliono costruire il minor numero possibile di strade: dove realizzarle?
Osserva le tre figure precedenti:
- nella figura a) i tre punti rappresentano tre siti di perforazione;
- nella figura b) si nota che sono sufficienti due strade per mettere in comunicazione i tre siti: non è necessario che ogni sito debba comunicare con tutti gli altri (l'obiettivo consiste nel realizzare MENO STRADE POSSIBILI senza badare al tempo necessario per andare da un sito all'altro);
- nella figura c) è illustrata un'altra soluzione: creando un punto centrale di intersezione e sommando la lunghezza di tutte le strade (cioè di tutti i segmenti) si ottiene la LUNGHEZZA MINORE.
La soluzione c) è la SOLUZIONE MIGLIORE: la somma dei tre segmenti in c) è minore della somma dei due segmenti in b).
Il punto di intersezione aggiunto nella soluzione c) si chiama PUNTO DI STEINER, dal nome del matematico svizzero che, nella prima metà dell'Ottocento, è stato il primo a notare che la lunghezza totale può essere ridotta indroducendo nuovi punti.
Osserva ora i quattro punti della figura a) e le possibili strade con cui mettere in comunicazione tutti i punti. Se i 4 punti costituiscono i 4 vertici di un quadrato del lato di 1 metro:
- la figura b) mostra una soluzione con tre strade. La lunghezza totale è di 3 metri;
- la figura c) mostra una soluzione in cui le strade sono le diagonali del quadrato. La lunghezza totale è di 2.83 metri (puoi adoperare il teorema di Pitagora per dimostrarlo);
- la figura d) mostra una soluzione con due punti di Steiner che formano angoli di 120 gradi. La lunghezza totale è di 2.73 metri!!!
La figura d) è la SOLUZIONE MIGLIORE: la somma dei 5 segmenti è minore della somma delle diagonali della soluzione in c).
Qui a sinistra confronta invece le tre diverse soluzioni applicate ad un rettangolo di 2m x 1m:
- figura b): lunghezza tot = 4.00 m
- figura c): lunghezza tot = 4.47 m
- figura d): lunghezza tot = 3.73 m
In questo caso la soluzione c) peggiora la situazione ma, come in precedenza, la figura d) è la SOLUZIONE MIGLIORE!!!
Attività: Strade ghiacciate - Gli alberi di Steiner
Trova il percorso più breve con cui collegare i punti dell'ESEMPIO A e i punti dell'ESEMPIO B, individuando punti di Steiner.
ESEMPIO A
ESEMPIO B
Modalità di svolgimento
Viene eseguito l' esercizio intitolato Strade Ghiacciate - Gli alberi di Steiner.
Dopo la spiegazione iniziale, viene consegnato ad ogni studente un foglio contenente due esempi di punti attraverso cui realizzare il percorso più breve.
Gli esempi vengono presentati anche con GeoGebra, in modo che si possa verificare l'effettiva lunghezza del percorso realizzato. Vince chi trova il percorso più breve sia nell'esempio 1 che nell'esempio 2.
Clicca sui seguenti link per adoperare on-line l'app GeoGebra:
Se vuoi lavorare off-line con GeoGebra sul tuo PC, scarica qui di seguito i due file:
Come usare GeoGebra per risolvere il problema?
Dopo aver aperto GeoGebra:
- seleziona lo strumento SEGMENTO; clicca prima su un punto e poi su un altro punto per creare il segmento;
- nel riquadro a sinistra compare la definizione "segmento" con l'indicazione della sua LUNGHEZZA;
- crea ALTRI SEGMENTI in modo da ottenere un percorso che metta in comunicazione tutti i punti;
- contempla la possibilità di inserire nuovi punti intermedi (i PUNTI DI STEINER) e crea NUOVI SEGMENTI;
- annota la lunghezza di ogni segmento, esegui la SOMMA in Geogebra o adopera la calcolatrice del tuo PC;
- SCRIVI la lunghezza del tuo percorso sul foglio che ti è stato dato all'inizio della lezione e consegnalo ai docenti.