Problema della connettività
Questa voce o sezione sull'argomento programmazione non cita le fonti necessarie o quelle presenti sono insufficienti.
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.
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 p sia connesso con q. In caso contrario, il programma dovrà semplicemente ignorare la coppia p-q e procedere con la coppia in ingresso successiva.
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 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 senza ulteriori connessioni. Non c'è alcuna garanzia che i cavi già presenti siano sufficienti per connettere tutti i punti della rete.
Un ulteriore 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, dati due nomi di variabili risultino equivalenti.[non chiaro] Si tratta di una di quelle applicazioni che hanno motivato storicamente l'elaborazione di algoritmi di connettività.
