Problema della connettività
Da Wikipedia, l'enciclopedia libera.
Il Problema della connettività è un cardine dell'informatica nello studio degli algoritmi. In via informale tale problema viene definito come problema delle connettività. Si supponga di avere a disposizione una sequenza di coppie di numeri interi, dove ogni intero rappresenta un oggetto di qualche tipo. La coppia p-q è da interpretare come l'oggetto p è connesso con l'oggetto q. Si assuma che la relazione è connesso con sia transitiva: cioè se p è connesso con q e q è connesso con r allora anche p è connesso con r.
[modifica] Logica dell'algoritmo
Il nostro obiettivo è quello di scrivere un programma che filtri le coppie estranee dall'insieme di partenza: avendo in ingresso la coppia p-q, il programma dell'algoritmo dovrà restituire in uscita tale coppia solo se le coppie che il programma ha esaminato in precedenza non implicano che è sia connesso con q. In caso contrario, il programma dovrà semplicemente ignorare la coppia p-q e procedere con la coppia in ingresso successiva.
[modifica] Esempi pratici
Si suppone che i numeri interi potrebbero rappresentare i calcolatori di una rete di grandi dimensioni e le coppie rappresentare le connessioni fra calcolatori. Il nostro algoritmo potrebbe essere impiegato per determinare se sia necessario stabilire ex-novo una connessione tra p e q o si possano utilizzare connessioni già esistenti. In questo tipo di applicazioni potrebbe essere necessario di esaminare milioni di nodi e miliardi di connessioni di rete.
Un'altro esempio è rappresentato dai punti di contatto di una rete elettrica e le coppie p-q potrebbero rappresentare i cavi che connettono tali punti. In questo caso il nostro programma potrebbe determinare se sia possibile connettere tutti i punti della rete suza ulteriori connessioni. Non c'è alcuna garanzia che i cavi già presenti siano sufficienti per connettere tutti i punti della rete.
Un'ulteriorie esempio di impiego di questo algoritmo è dato da ambienti di programmazione nei quali è consentito dichiarare come equivalenti nomi diversi di variabili. Il problema è quello di stabilire se a seguito di una sequenza di dichiarazioni di questo tipo, due dati nomi di variabili risultino equivalenti. Si tratta di una di quelle applicazioni che hanno motivato storicamente l'elaborazione di algoritmi di connettività .
