Basi Teoriche e Complessità Computazionale

Nella teoria dell'informazione, un algoritmo rappresenta un'entità astratta: una procedura ben definita e rigorosa costituita da una sequenza finita di passi elementari, progettata per trasformare un insieme di dati di input in un insieme di dati di output. Non è legato a uno specifico linguaggio di programmazione o a un'architettura hardware, ma costituisce la pura logica risolutiva.

Misurare l'efficienza di un algoritmo tramite approcci empirici (come il profiling) restituisce valori viziati dall'ambiente di esecuzione: architettura della CPU, carico del sistema operativo, ottimizzazioni del compilatore. L'Analisi Asintotica supera queste limitazioni studiando la crescita del costo computazionale in funzione della dimensione dell'istanza n, al tendere di n verso l'infinito.

La classificazione di un algoritmo avviene raggruppando la sua funzione di costo in gerarchie matematiche. Il termine dominante di un'equazione determina l'appartenenza a una classe (es. un polinomio di grado m apparterrà sempre alla classe O(n^m)). Analizziamo le classi fondamentali:

Algoritmi Iterativi

La valutazione della complessità di un programma iterativo si ottiene analizzando il costo delle singole istruzioni (o blocchi di istruzioni) e aggregandoli secondo le regole di composizione strutturale. Per procedere con il calcolo, si assume che le operazioni elementari abbiano costo costante O(1).

Gli algoritmi di ordinamento elementari, basati su confronti diretti, presentano un limite strutturale legato all'utilizzo di cicli annidati, che li confina nella classe di complessità quadratica O(n²). Ciononostante, differiscono sensibilmente nell'impatto sul sottosistema di memoria.

void selectionSort(int A[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int min = i;
        for (int j = i + 1; j < n; j++) {
            if (A[j] < A[min]) min = j; // Aggiornamento indice O(1)
        }
        exchange(A[i], A[min]); // Swap fuori dal ciclo interno
    }
}

void bubbleSort(int A[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = n - 1; j >= i + 1; j--) {
            if (A[j] < A[j-1]) 
                exchange(A[j], A[j-1]); // Swap all'interno del ciclo annidato
        }
    }
}

void algoritmo(int A[], int n) {
    int somma = 0;                              // [Peso: O(1)] Inizializzazione costante
    
    for (int i = 0; i < n; i++) {                 // [Peso: O(n)] Ciclo esterno eseguito n volte
        
        
        int k = trasformaParametro(n);            // [Peso: O(n)] Eseguita a ogni iterazione di i!
        
        for (int j = 0; j < k; j++) {              // [Peso: O(n)] Ciclo dipendente da k (che vale n)
            
            for (int w = 1; w < n; w *= 2) {         // [Peso: O(log n)] Ciclo interno con incremento esponenziale
                somma += A[i] + j + w;          // [Peso: O(1)] Operazione elementare
            }
        }
    }
    
    if (somma > 1000) {                         // [Peso: O(1)] Controllo condizionale
        stampaMessaggio();                      // [Peso: O(1)] Funzione a tempo costante
    }
}

Ricorsione e Divide et Impera

Una funzione ricorsiva è una funzione che per risolvere un problema richiama se stessa all'interno del proprio blocco di istruzioni. Affinché la ricorsione operi in maniera corretta e non causi errori di memoria (come lo Stack Overflow), deve rispettare regole strutturali ben precise:

Il tempo di esecuzione di un algoritmo ricorsivo (in particolare per il paradigma Divide et Impera) si calcola impostando un'equazione di ricorrenza. Lo strumento principale per risolverle è il Teorema del Maestro.

// Funzione di fusione: unisce due sottoarray ordinati in un unico blocco ordinato
void merge(int A[], int l, int m, int r) {
    // Calcolo della dimensione del sottoarray sinistro e destro
    int n1 = m - l + 1;
    int n2 = r - m;
    
    // Creazione di array temporanei per il supporto (richiede O(n) memoria extra)
    int L[n1], R[n2];
    
    // Copia dei dati nei vettori di supporto temporanei
    for (int i = 0; i < n1; i++) L[i] = A[l + i];
    for (int j = 0; j < n2; j++) R[j] = A[m + 1 + j];
    
    // Indici di scorrimento: i per L, j per R, k per l'array principale A
    int i = 0, j = 0, k = l;
    
    // Fase di fusione ordinata: confronta gli elementi e rimettili in A
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            A[k] = L[i];
            i++;
        } else {
            A[k] = R[j];
            j++;
        }
        k++;
    }
    
    // Copia degli eventuali elementi rimanenti nel sottoarray sinistro
    while (i < n1) { 
        A[k] = L[i]; 
        i++; 
        k++; 
    }
    
    // Copia degli eventuali elementi rimanenti nel sottoarray destro
    while (j < n2) { 
        A[k] = R[j]; 
        j++; 
        k++; 
    }
}

// Funzione principale ricorsiva (Divide et Impera)
void mergeSort(int A[], int l, int r) {
    if (l < r) {
        // Trova il punto di mezzo per dividere a metà l'array
        int m = l + (r - l) / 2;
        
        // 1. DIVIDI & IMPERA: Scompone ricorsivamente la metà sinistra
        mergeSort(A, l, m);        
        
        // 2. DIVIDI & IMPERA: Scompone ricorsivamente la metà destra
        mergeSort(A, m + 1, r);   
        
        // 3. COMBINA: Fonde le due metà ordinate tramite la funzione merge
        merge(A, l, m, r);         
    }
}

void quickSort(int A[], int inf, int sup) {
    // Scegli il perno centrale
    int perno = A[(inf + sup) / 2];
    int s = inf, d = sup;
    
    // Partizionamento In-Place
    while (s <= d) {
        while (A[s] < perno) s++;
        while (A[d] > perno) d--;
        if (s > d) break;
        exchange(A[s], A[d]);
        s++; d--;
    }
    
    // Ricorsione sulle sottosezioni
    if (inf < d) quickSort(A, inf, d);
    if (s < sup) quickSort(A, s, sup);
}

Strutture ad Albero

A differenza delle strutture lineari (come array e liste), un albero è una struttura dati dinamica, gerarchica e intrinsecamente ricorsiva. Si compone di un insieme di nodi collegati da archi orientati, sviluppandosi a partire da un singolo nodo principale denominato radice (root).

Tipologie di Alberi

Visitare un albero significa percorrere la struttura per ispezionare tutti i nodi esattamente una volta. Poiché l'albero è ricorsivo, le visite si implementano naturalmente con funzioni ricorsive. Esistono tre ordini principali, determinati dal momento in cui viene processata l'etichetta del nodo padre rispetto alle chiamate sui figli.

Poiché ogni nodo viene visitato e processato una sola volta, tutte e tre le visite richiedono un tempo strettamente lineare rispetto al numero dei nodi: la loro complessità temporale è sempre O(n).

void preOrder(Node* tree) {
    if (!tree) return; // Caso base: albero vuoto
    
    cout << tree->label << " "; // 1. Esamina la radice
    preOrder(tree->left);       // 2. Visita il sottoalbero sinistro
    preOrder(tree->right);      // 3. Visita il sottoalbero destro
}

void inOrder(Node* tree) {
    if (!tree) return;
    
    inOrder(tree->left);        // 1. Visita il sottoalbero sinistro
    cout << tree->label << " "; // 2. Esamina la radice
    inOrder(tree->right);       // 3. Visita il sottoalbero destro
}

void postOrder(Node* tree) {
    if (!tree) return;
    
    postOrder(tree->left);      // 1. Visita il sottoalbero sinistro
    postOrder(tree->right);     // 2. Visita il sottoalbero destro
    cout << tree->label << " "; // 3. Esamina la radice in risalita
}

Un Albero Binario di Ricerca (spesso abbreviato in BST o ABR) introduce una rigorosa regola di ordinamento topologico: per ogni nodo p dell'albero, tutte le etichette presenti nel suo sottoalbero sinistro devono essere strettamente minori dell'etichetta di p, mentre tutte quelle nel sottoalbero destro devono essere strettamente maggiori.

Questa proprietà intrinseca garantisce che, se eseguiamo una Visita Simmetrica (In-Order) su un ABR, otterremo sempre la stampa dei valori in perfetto ordine crescente.

// Ricerca in un ABR: Complessità O(h)
Node* findNode(InfoType n, Node* tree) {
    if (!tree) return NULL; // Albero vuoto o elemento assente
    
    if (n == tree->label) return tree; // Match trovato!
    
    if (n < tree->label)
        return findNode(n, tree->left); // Scarto l'intera metà destra
    else
        return findNode(n, tree->right); // Scarto l'intera metà sinistra
}

Strutture Heap e Code di Priorità

Uno Heap (nello specifico un Max-Heap) è un albero binario quasi bilanciato che rispetta due regole strutturali rigorose:

1. Proprietà di Forma: Tutti i livelli dell'albero sono completamente riempiti, tranne eventualmente l'ultimo, i cui nodi devono essere addossati il più possibile a sinistra.
2. Proprietà di Ordine (Heap Property): In ogni sottoalbero, l'etichetta del nodo radice deve essere sempre maggiore o uguale a quella di tutti i suoi discendenti. Di conseguenza, il valore massimo assoluto si troverà sempre nella radice dell'albero.

Le manipolazioni dello Heap alterano la sua struttura, pertanto richiedono procedure di ripristino (fix-up e fix-down) per mantenere valida la Proprietà di Ordine.

void Heap::up(int i) {
    if (i > 0) { // Se non siamo sulla radice
        int padre = (i - 1) / 2;
        if (h[i] > h[padre]) { // Violazione della priorità
            exchange(i, padre);  // Scambia col padre
            up(padre);           // Continua la risalita ricorsivamente
        }
    }
}

void Heap::down(int i) {
    int son = 2 * i + 1; // Indice del figlio sinistro
    
    if (son == last) { // Ha solo il figlio sinistro
        if (h[son] > h[i]) exchange(i, last);
    } 
    else if (son < last) { // Ha entrambi i figli
        if (h[son] < h[son + 1]) son++; // Trova il figlio maggiore
        
        if (h[son] > h[i]) { // Se il figlio maggiore batte il padre
            exchange(i, son);
            down(son); // Continua la discesa
        }
    }
}

L'Heapsort è uno dei più eleganti algoritmi di ordinamento. Sfrutta le proprietà dello Heap per ordinare un array in-place (senza memoria aggiuntiva) garantendo un tempo asintotico ottimale di O(n log n). Si divide in due fasi:

void buildHeap(int* A, int n) {
    // Parte dall'ultimo nodo interno e risale alla radice
    for (int i = n / 2 - 1; i >= 0; i--) {
        down(A, i, n - 1);
    }
}

void heapSort(int* A, int n) {
    buildHeap(A, n); // Costruisce lo Heap in O(n)
    
    int last = n - 1;
    while (last > 0) {
        exchange(A, 0, last); // Sposta il massimo in fondo all'array
        last--;               // Riduci la dimensione logica dello Heap
        down(A, 0, last);     // Ripristina lo Heap nel range [0...last]
    }
}

Limiti Inferiori e Ordinamenti Lineari

Nella teoria della complessità computazionale, è fondamentale chiedersi se sia possibile creare un algoritmo di ordinamento più veloce di O(n log n). Per rispondere, si modella l'esecuzione di qualsiasi algoritmo basato su confronti diretti (come Merge Sort, Quick Sort o Heap Sort) attraverso un Albero di Decisione.

Per infrangere la barriera di O(n log n), è necessario abbandonare il paradigma dei confronti. Il Counting Sort è un algoritmo di ordinamento lineare che sfrutta le proprietà intrinseche dei dati: richiede che gli elementi da ordinare siano interi compresi in un intervallo noto [0, k].

void countingSort(int A[], int n, int k) {
    int C[k + 1];
    for (int i = 0; i <= k; i++) C[i] = 0; // Inizializzazione O(k)
    
    for (int j = 0; j < n; j++) C[A[j]]++; // Conteggio frequenze O(n)
    
    int j = 0;
    for (int i = 0; i <= k; i++) {       // Ricostruzione O(n + k)
        while (C[i] > 0) {
            A[j] = i;
            C[i]--;
            j++;
        }
    }
}

Il Radix Sort risolve il problema dell'elevato consumo di memoria del Counting Sort quando si trattano numeri grandi o stringhe. L'idea è di scomporre l'ordinamento in passate successive, lavorando su una singola cifra (o carattere) alla volta, partendo dalla cifra meno significativa verso quella più significativa (approccio LSD - Least Significant Digit).

// Sotto-routine di supporto stabile (Counting Sort per singola cifra)
void countSortByDigit(int A[], int n, int exp) {
    int output[n];
    int count[10] = {0};

    for (int i = 0; i < n; i++) {
        int digit = (A[i] / exp) % 10;
        count[digit]++;
    }

    for (int i = 1; i < 10; i++) {
        count[i] += count[i - 1];
    }

    for (int i = n - 1; i >= 0; i--) {
        int digit = (A[i] / exp) % 10;
        output[count[digit] - 1] = A[i];
        count[digit]--;
    }

    for (int i = 0; i < n; i++) {
        A[i] = output[i];
    }
}

// Funzione principale del Radix Sort (LSD)
void radixSort(int A[], int n) {
    if (n <= 0) return;
    
    int maxVal = A[0];
    for (int i = 1; i < n; i++) {
        if (A[i] > maxVal) maxVal = A[i];
    }

    // Itera per ogni cifra: unità (exp=1), decine (exp=10), centinaia (exp=100), ecc.
    for (int exp = 1; maxVal / exp > 0; exp *= 10) {
        countSortByDigit(A, n, exp);
    }
}

Hashing, Accesso Diretto e Dizionari

Gli algoritmi di ricerca tradizionali mostrano limiti strutturali: la ricerca lineare richiede un tempo O(n), mentre la ricerca binaria, pur raggiungendo O(log n), obbliga a mantenere l'array costantemente ordinato. Il metodo Hash rivoluziona questo approccio eliminando del tutto i confronti. L'obiettivo è calcolare matematicamente la posizione di memoria di un elemento, garantendo un tempo di ricerca ideale pari a O(1).

Per risparmiare memoria, si rilascia la proprietà di iniettività, accettando che la dimensione dell'array k sia molto più piccola dello spazio delle chiavi possibili. Questo genera inevitabilmente delle collisioni: chiavi diverse producono lo stesso indice, ovvero h(x₁) = h(x₂). L'Indirizzamento Aperto risolve il problema memorizzando tutti gli elementi all'interno dell'array stesso e cercando celle alternative quando si verifica una collisione.

// Inserimento con Scansione Lineare in C++
// A: array, k: dimensione, x: valore da inserire
int hashInsert(int *A, int k, int x) {
    int i = h(x); // Calcolo indice base, es. x % k
    int b = 0;    // Flag di successo
    
    for (int j = 0; !b && j < k; j++) {
        int pos = (i + j) % k; // Esplorazione circolare
        
        // -1 indica cella mai usata, -2 indica cella liberata
        if (A[pos] == -1 || A[pos] == -2) {
            A[pos] = x;
            b = 1; // Inserimento avvenuto
        }
    }
    return b;
}

Una soluzione radicale per evitare gli agglomerati è il Metodo della Concatenazione (Chaining). L'array primario A non memorizza direttamente le chiavi, ma ospita unicamente un set di k puntatori (spesso chiamati bucket). Qualsiasi elemento collida sul medesimo indice i viene istanziato dinamicamente in memoria e accodato a una lista concatenata a cui A[i] fa da nodo di testa.

Programmazione Dinamica e Algoritmi Greedy

La Programmazione Dinamica (Dynamic Programming) è una tecnica di ottimizzazione algoritmica ideata da Richard Bellman a metà del XX secolo. Essa interviene in tutti quegli scenari complessi in cui la tecnica del Divide et Impera fallisce miseramente: quando cioè i sottoproblemi in cui viene diviso l'input non sono strettamente disgiunti, ma si sovrappongono e si ripetono in continuazione.

Se provassimo a risolvere un problema con sottoproblemi sovrapposti usando una semplice ricorsione "top-down" pura, l'albero delle chiamate ricorsive esploderebbe con una complessità esponenziale ricalcolando decine di migliaia di volte gli stessi identici valori. La Programmazione Dinamica ribalta l'approccio adottando una strategia Bottom-Up (dal basso verso l'alto):

• 1. Risoluzione dei Casi Base: Si parte calcolando direttamente le soluzioni dei sottoproblemi più piccoli e immediati.
• 2. Memorizzazione (Tabulazione): I risultati di ogni sottoproblema risolto non vengono scartati, ma salvati metodicamente all'interno di una struttura di supporto in memoria (solitamente una matrice o un vettore).
• 3. Riutilizzo Incrementale: Per risolvere i problemi via via più grandi, l'algoritmo attinge direttamente ai valori già memorizzati in tabella, riducendo drasticamente il tempo di calcolo complessivo (spesso da esponenziale a polinomiale).

Caso Studio: Più Lunga Sottosequenza Comune (LCS / PLSC)

Il problema della PLSC (Longest Common Subsequence) consiste nel trovare la sequenza di caratteri più lunga che compare come sottosequenza in entrambe le stringhe di input α (lunghezza m) e β (lunghezza n). Nota bene: i caratteri non devono essere necessariamente contigui nelle stringhe originali, ma devono rispettare rigorosamente il loro ordine relativo.

Analizzando i prefissi delle due stringhe, la lunghezza L(i,j) della PLSC si definisce formalmente tramite la seguente ricorrenza matematica:

Come si ricostruisce effettivamente la Sottosequenza? (Backtracking)

Il codice di programmazione dinamica standard calcola la lunghezza della sottosequenza restituendo il valore numerico presente nell'angolo in basso a destra della matrice L[m][n]. Ma come facciamo a risalire ai caratteri che compongono la stringa comune?

Terminata la compilazione della tabella, si effettua un processo a ritroso (Backtracking) partendo dall'ultima cella in basso a destra (m, n) e risalendo verso la cella iniziale (0, 0) seguendo queste regole:

• Se i caratteri correnti delle due stringhe coincidono (a[i] == b[j]), quel carattere fa sicuramente parte della PLSC ottimale: lo salviamo nella stringa risultato e ci muoviamo diagonalmente in alto a sinistra (i-1, j-1).
• Se non coincidono, guardiamo la matrice e ci muoviamo verso la cella adiacente che possiede il valore numerico maggiore tra quella in alto (L[i-1][j]) e quella a sinistra (L[i][j-1]), simulando la scelta che ha generato quel massimo.

Implementazione C++ completa (Calcolo + Ricostruzione)

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

void stampaPLSC(string a, string b) {
    int m = a.length();
    int n = b.length();
    
    // Matrice per memorizzare i risultati dei sottoproblemi (inizializzata a 0)
    vector<vector<int>> L(m + 1, vector<int>(n + 1, 0));
    
    // Riempimento bottom-up della matrice
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (a[i - 1] == b[j - 1]) {
                L[i][j] = L[i - 1][j - 1] + 1; // Carattere comune trovato
            } else {
                L[i][j] = max(L[i - 1][j], L[i][j - 1]); // Prendo il massimo adiacente
            }
        }
    }
    
    // Ricostruzione della stringa comune (Backtracking dalla fine)
    int i = m, j = n;
    string plsc = "";
    
    while (i > 0 && j > 0) {
        if (a[i - 1] == b[j - 1]) {
            plsc += a[i - 1]; // Il carattere fa parte della sottosequenza
            i--; j--;
        } 
        else if (L[i - 1][j] > L[i][j - 1]) {
            i--; // Ci muoviamo verso l'alto
        } 
        else {
            j--; // Ci muoviamo verso sinistra
        }
    }
    
    // La stringa va invertita perché ricostruita al contrario
    reverse(plsc.begin(), plsc.end());
    
    cout << "Lunghezza PLSC: " << L[m][n] << endl;
    cout << "Sottosequenza: " << plsc << endl;
}

Grazie alla tabulazione bottom-up, la complessità temporale di questo algoritmo si stabilizza saldamente su O(m · n), evitando del tutto l'esplosione combinatoria esponenziale.

Mentre la Programmazione Dinamica esplora esaustivamente lo spazio dei sottoproblemi per trovare la soluzione ottima (valutando molteplici alternative e combinazioni), l'approccio Greedy (Goloso) adotta una filosofia opposta, di tipo Top-Down incrementale.

In un algoritmo greedy, l'intero problema viene risolto compiendo una serie di scelte sequenziali. A ogni passo, l'algoritmo sceglie l'alternativa che appare localmente ottimale in quel preciso istante, senza preoccuparsi delle conseguenze future o dei passi precedenti. Una volta compiuta una scelta, essa è definitiva e non viene mai riconsiderata.

Esercizio Guidato: Compressione con l'Algoritmo di Huffman

Per comprendere appieno la potenza e la logica di un algoritmo greedy, analizziamo un caso pratico reale. Supponiamo di voler comprimere la stringa di testo:

Fase 1: Analisi delle Frequenze dei Caratteri
Contiamo quante volte compare ciascun carattere all'interno della stringa (lunghezza totale = 11 caratteri):

• Carattere A: f = 5
• Carattere B: f = 2
• Carattere R: f = 2
• Carattere C: f = 1
• Carattere D: f = 1

Fase 2: Applicazione della Strategia Greedy (Costruzione Bottom-Up del Min-Heap)
L'algoritmo inserisce tutti i caratteri in una Coda di Priorità (organizzata come Min-Heap in base alla frequenza). A ogni iterazione, applica la regola golosa:

1. Estrazione 1: I due caratteri meno frequenti sono C (1) e D (1). Vengono estratti e uniti in un nodo genitore con frequenza `1 + 1 = 2`. Nella coda ora abbiamo: B(2), R(2), (CD:2), A(5).
2. Estrazione 2: Estraiamo i due elementi con frequenza minima corrente, ovvero B (2) e R (2), e li fondiamo in un nodo con frequenza `2 + 2 = 4`. Nella coda abbiamo: (CD:2), (BR:4), A(5).
3. Estrazione 3: Estraiamo il blocco `(CD:2)` e l'elemento `(BR:4)`, unendoli in un nuovo sottoalbero con frequenza `2 + 4 = 6`. Rimangono in coda: A(5) e l'albero complesso con radice 6.
4. Estrazione 4 (Finale): Uniamo gli ultimi due alberi rimasti `A(5)` e il blocco precedente (`6`), ottenendo la radice globale dell'albero con frequenza totale 11.

Fase 3: Assegnazione dei Codici Binari (Attraversamento dell'Albero)
Assegnando convenzionalmente il bit 0 ai rami sinistri e il bit 1 ai rami destri dell'albero binario così costruito, otteniamo codici a lunghezza variabile (i cosiddetti codici prefissi), dove i caratteri più frequenti come la 'A' ricevono stringhe di bit cortissime, mentre quelli rari ricevono codici più estesi, ottimizzando drasticamente lo spazio di memorizzazione complessivo.

// Implementazione C++ della funzione Greedy per l'Algoritmo di Huffman
Node* huffmanCostruisciAlbero(vector<pair<char, int>>& caratteri) {
    // Min-Heap basato sulla frequenza minima dei nodi
    priority_queue<Node*, vector<Node*>, CompareNodi> minHeap;
    
    // Inserimento iniziale di tutti i nodi foglia nel Min-Heap
    for (auto par : caratteri) {
        minHeap.push(new Node(par.first, par.second));
    }
    
    // Iterazione Greedy: si ripete fino a quando non resta un unico albero
    while (minHeap.size() > 1) {
        // Scelta Greedy: estrae i due elementi con frequenza minore
        Node* sinistro = minHeap.top(); minHeap.pop();
        Node* destro = minHeap.top(); minHeap.pop();
        
        // Crea un nuovo nodo genitore sommando le frequenze
        Node* genitore = new Node('\0', sinistro->frequenza + destro->frequenza);
        genitore->sinistro = sinistro;
        genitore->destro = destro;
        
        // Reinserisce il nuovo albero parziale nel Min-Heap
        minHeap.push(genitore);
    }
    
    return minHeap.top(); // Restituisce la radice finale dell'albero di Huffman
}

Grafi, Reti e Cammini Minimi

Mentre gli alberi modellano gerarchie rigide (rapporti uno-a-molti), un Grafo G = (V, E) è la struttura dati fondamentale per rappresentare relazioni complesse (molti-a-molti). È composto da un insieme V di Vertici (o Nodi) e un insieme E di Archi (o Spigoli) che li collegano. Se gli archi possiedono un verso di percorrenza, si parla di grafo orientato; se presentano un "costo" di attraversamento, si parla di grafo pesato.

// Visita in Profondità (DFS) ricorsiva con Liste di Adiacenza
void nodeVisit(int i, int mark[], Node* graph[]) {
    mark[i] = 1; // 1. Marca il nodo corrente come visitato
    esamina(i);  // 2. Esegue l'operazione sul nodo (es. stampa o elaborazione)
    
    // 3. Scorre la lista concatenata dei nodi adiacenti (successori)
    for (Node* g = graph[i]; g != NULL; g = g->next) {
        int j = g->nodeNumber;
        
        // 4. Se il vicino 'j' non è mai stato visitato, scende in ricorsione profonda
        if (!mark[j]) {
            nodeVisit(j, mark, graph);
        }
    }
}

Dato un grafo non orientato, pesato e connesso, il Minimo Albero di Copertura (MST) è un sottografo aciclico che collega tutti i vertici utilizzando il set di archi che garantisce la somma dei pesi minima in assoluto. È il problema classico del cablaggio delle reti (es. collegare n città con la minima quantità di fibra ottica).

Il calcolo del cammino minimo da una singola sorgente è il fondamento della navigazione GPS moderna. L'Algoritmo di Dijkstra identifica il percorso minimo per viaggiare da un nodo sorgente verso tutti i restanti nodi, procedendo per "rilassamenti" successivi. Premi il tasto Passo Successivo per vedere l'algoritmo in azione su un grafo di esempio partendo dal nodo sorgente A.

Implementazione C++ dell'Algoritmo di Dijkstra

Di seguito è riportata l'implementazione efficiente in C++ che utilizza una lista di adiacenza (vector) e una coda di priorità (priority_queue) per mantenere la complessità temporale ottimale a O((V + E) log V).

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

// Definizione di una coppia (peso, nodo destinatario) per la lista di adiacenza
typedef pair<int, int> Arco;

// Funzione principale di Dijkstra
void dijkstra(int V, int sorgente, vector<vector<Arco>>& adj) {
    // Vettore delle distanze minime inizializzato a infinito
    vector<int> distanza(V, 1e9);

    // Min-heap per estrarre con efficienza O(log V) il nodo con distanza minima (Greedy choice)
    priority_queue<Arco, vector<Arco>, greater<Arco>> pq;

    // La distanza della sorgente da se stessa è 0
    distanza[sorgente] = 0;
    pq.push({0, sorgente});

    while (!pq.empty()) {
        int u = pq.top().second;
        int d = pq.top().first;
        pq.pop();

        // Se la distanza estratta è maggiore della minima nota, salta
        if (d > distanza[u]) continue;

        // Scansione dei nodi adiacenti (Rilassamento degli archi)
        for (auto& arco : adj[u]) {
            int v = arco.second;
            int pesoArco = arco.first;

            // Se troviamo un percorso più breve verso v
            if (distanza[u] + pesoArco < distanza[v]) {
                distanza[v] = distanza[u] + pesoArco;
                pq.push({distanza[v], v});
            }
        }
    }

    // Stampa dei risultati finali
    cout << "Distanze minime dalla sorgente " << sorgente << ":" << endl;
    for (int i = 0; i < V; i++) {
        cout << "Nodo " << i << " -> Distanza: " << distanza[i] << endl;
    }
}

Problemi Difficili e Teoria della NP-Completezza

Finora abbiamo analizzato algoritmi efficienti in grado di risolvere problemi in tempi polinomiali (es. O(n), O(n log n), O(n²)). Esistono tuttavia intere categorie di problemi reali per i quali, allo stato attuale della scienza computazionale, si conoscono unicamente soluzioni basate sulla forza bruta con tempi di esecuzione esponenziali o fattoriali (es. O(2ⁿ) o O(n!)). Per classificarli, la teoria della complessità si focalizza sui Problemi Decisionali, ovvero questioni la cui risposta ammette esclusivamente un esito binario: SÌ o NO.

Il Problema del Commesso Viaggiatore è uno dei problemi di ottimizzazione combinatoria più celebri nell'ambito degli algoritmi e della complessità computazionale. Esso richiede di trovare il percorso di minore lunghezza che un commesso viaggiatore deve seguire per visitare tutte le città una e una sola volta per poi fare ritorno alla città di partenza.

Dal punto di vista dell'efficienza, questo problema rientra nella categoria dei problemi difficili (NP-completi). Gli algoritmi conosciuti oggi per risolverlo richiedono di esplorare tutte (o quasi) le combinazioni possibili di spostamento, facendo impennare i tempi di calcolo verso una complessità di tipo esponenziale o fattoriale. All'aumentare anche di poche unità nel numero delle città, la forza bruta diventa impraticabile per qualsiasi calcolatore.

È evidente che P ⊆ NP: tutti i problemi facili da risolvere sono anche facili da verificare. Il più grande enigma irrisolto dell'informatica teorica chiede se valga l'inverso: P = NP? (problema del millennio premiato con un milione di dollari dal Clay Mathematics Institute). Se un giorno venisse dimostrato che esiste un algoritmo polinomiale per risolvere anche un solo problema intrattabile, cadrebbe l'intera barriera e risulterebbe che ogni problema verificabile è anche risolvibile rapidamente.

Come Affrontare i Problemi Difficili nella Realtà

Poiché i sistemi software industriali affrontano quotidianamente problemi intrattabili (ottimizzazione logistica, crittografia, pianificazione), l'ingegneria del software ricorre a metodologie di mitigazione:

• Algoritmi di Approssimazione: Rinunciano alla soluzione perfetta e matematica in favore di una soluzione vicina all'ottimo, calcolata però in tempi rapidi e certi.
• Algoritmi Probabilistici: Sfruttano scelte casuali per esplorare lo spazio delle soluzioni riducendo drasticamente il tempo medio di calcolo.
• Intelligenza Artificiale ed Euristiche: Reti neurali e tecniche di ricerca avanzata (come Branch and Bound o algoritmi genetici) per "potare" i rami inutili dell'albero delle decisioni.