🏠 Home

Definizioni

Ultima modifica: 03/11/2025

1_intro

Problemi di Decisione e Modelli - Problema di decisione: Riguarda il fare le scelte ottimali, ovvero quelle che consentono di arrivare alla realizzazione di un sistema reale di qualità più elevata, il cui funzionamento dipende dalle scelte che si possono compiere. - Dati: Tutte le informazioni note a priori sul problema su cui il decisore non ha controllo. - Variabili: Tutte le grandezze i cui valori possono essere scelti dal decisore. Un assegnamento di valori a queste variabili corrisponde a una particolare realizzazione del sistema reale. - Vincoli: Condizioni che limitano i possibili valori che possono essere assegnati alle variabili, limitando quindi l’insieme di scelte del decisore. - Obiettivo: Il criterio di confronto tra le varie possibili realizzazioni del sistema reale, che misura la qualità di ogni realizzazione. - Modello del problema di decisione: Una rappresentazione astratta del sistema reale, dalla quale sono epurati tutti i dettagli non significativi al fine della risoluzione. - Modelli matematici dei problemi di decisione: Modelli nei quali le componenti del problema di decisione (dati, variabili, vincoli, obiettivo) sono tradotte in oggetti matematici.

Problemi di Ottimizzazione - Problemi di ottimizzazione: Problemi matematici le cui componenti principali sono un insieme (detto regione ammissibile e indicato con $S$) e una funzione $f: S \to R$ (detta funzione obiettivo). - Regione ammissibile ($S$): L'insieme dei punti che soddisfano i vincoli di un problema di ottimizzazione. - Funzione obiettivo ($f$): Una funzione $f: S \to R$. - Istanza del problema di ottimizzazione: Il problema ottenuto con determinati dati di input. - Problema di ottimizzazione (generico): L’insieme di tutte le istanze, ottenute facendo variare in tutti i modi possibili i dati di input. - Modelli di programmazione matematica: Modelli in cui le variabili del problema di decisione sono rappresentate come variabili matematiche a valori numerici (reali o interi), la regione ammissibile è descritta con equazioni/disequazioni e la funzione obiettivo è una funzione matematica delle variabili. - Soluzione ottima ($s^\star$): Un punto $s^\star \in S$ tale che $f(s^\star) \ge f(s) \forall s \in S$ (per il massimo) o $f(s^\star) \le f(s) \forall s \in S$ (per il minimo). - Valore ottimo del problema ($f(s^\star)$): Il valore della funzione obiettivo calcolato nella soluzione ottima $s^\star$. - Insieme delle soluzioni ottime ($S^\star$): L’insieme di tutti i punti $s^\star \in S$ che soddisfano la condizione di ottimalità per il problema dato (minimo o massimo). - Soluzione $\epsilon$-approssimata: Una soluzione ammissibile ($s \in S$) il cui valore della funzione obiettivo non differisce dal valore ottimo per più di $\epsilon f(s^\star)$. - Per problemi di minimo ($\epsilon \ge 0$): $S_\epsilon = {s \in S : f(s) \le (1 + \epsilon)f(s^\star), s^\star \in S^\star}$. - Per problemi di massimo ($\epsilon \ge 0$): $S_\epsilon = {s \in S : f(s) \ge (1 - \epsilon)f(s^\star), s^\star \in S^\star}$.

Algoritmi e Complessità - Algoritmi costruttivi: Algoritmi iterativi che aggiungono e/o tolgono pezzi di una soluzione parziale fino a ottenere una soluzione completa. - Senza revisione delle decisioni passate: Si possono solo aggiungere pezzi a una soluzione parziale, e un pezzo, una volta aggiunto, non viene più tolto. - Con revisione delle decisioni passate: Si possono anche rimuovere pezzi precedentemente aggiunti a una soluzione parziale. - Algoritmi di ricerca locale: Algoritmi iterativi che esplorano un vicinato ($N(s) \subseteq S$) di una soluzione ammissibile $s$ in cerca di una soluzione ammissibile migliore. - Algoritmi enumerativi: Algoritmi che enumerano (esplicitamente o implicitamente) tutte le possibili soluzioni ammissibili del problema. - Algoritmi di enumerazione implicita: Introducono condizioni che permettono di scartare interi sottoinsiemi della regione ammissibile senza valutare la funzione obiettivo $f$ in tutti i loro punti. - Algoritmi di ottimizzazione o esatti: Algoritmi che restituiscono una soluzione ottima e il suo valore ottimo per ogni istanza del problema di ottimizzazione. - Algoritmi di approssimazione: Algoritmi che restituiscono una soluzione $\epsilon$-approssimata e il suo valore della funzione obiettivo per ogni istanza. - Algoritmi euristici (Euristica): Algoritmi che restituiscono una soluzione ammissibile e il suo valore, spesso in tempi rapidi e di buona qualità, ma senza alcuna garanzia sulla distanza dal valore ottimo. - Dimensione di un’istanza ($\dim(I)$): Il numero di bit necessari per memorizzare i dati di input dell’istanza $I$. - Approccio worst-case: Associa a ogni dimensione $k$ delle istanze il massimo numero di operazioni richieste tra tutte le istanze di dimensione $k$. - Ordine di grandezza ($f(k) = O(g(k))$): Si legge ‘$f$ è dell’ordine di grandezza di $g$’ se $\exists C > 0 : f(k) \le Cg(k) \forall k$. - Complessità esponenziale: Un algoritmo per il quale il numero di operazioni $t_A(k)$ è dell’ordine di grandezza di $2^k$ oppure $k!$. - Complessità polinomiale: Un algoritmo per il quale $t_A(k)$ è dell’ordine di grandezza di $k^p$ per qualche intero positivo $p$.

2_grafi

Definizioni di Base - Grafo ($G$): Definito da un insieme di nodi $V$ e un insieme di archi $A \subset V \times V$. - Grafo orientato o Digrafo: Un grafo in cui ogni coppia $(i, j) \in A$ è ordinata (ovvero $(i, j) \ne (j, i)$). - Grafo non orientato: Un grafo i cui archi non sono coppie ordinate. - Predecessore (grafo orientato): Il nodo $i$ di un arco $(i, j)$. - Successore (grafo orientato): Il nodo $j$ di un arco $(i, j)$. - Nodi adiacenti (grafo non orientato): I nodi $i$ e $j$ di un arco $(i, j)$. - Archi adiacenti: Due archi che hanno un nodo in comune. - Grado del nodo $i$ ($\delta(i)$, grafo non orientato): La cardinalità dell’insieme dei nodi adiacenti a $i$. - In-degree del nodo $i$ ($\delta^-(i)$, grafo orientato): La cardinalità dell’insieme dei predecessori di $i$. - Out-degree del nodo $i$ ($\delta^+(i)$, grafo orientato): La cardinalità dell’insieme dei successori di $i$. - Grafo non orientato completo: Se esiste un arco che collega ogni coppia di nodi distinti. - Grafo orientato completo: Se esiste una coppia di archi di verso opposto che collega ogni coppia di nodi. - Matrice di incidenza nodo-arco (non orientato): Matrice in ${0, 1}^{|V| \times |A|}$ dove la componente è 1 se il nodo $k$ è un estremo dell'arco $(i, j)$, 0 altrimenti. - Matrice di incidenza nodo-arco (orientato): Matrice in ${0, 1, -1}^{|V| \times |A|}$ dove la componente è $+1$ se $k$ è il nodo iniziale ($i$), $-1$ se $k$ è il nodo finale ($j$), e 0 altrimenti.

Cammini, Cicli e Connessione - Cammino: Una sequenza di nodi $s_0 \to s_1 \to \cdots \to s_t$ in cui archi consecutivi esistono nel grafo (non orientati nel caso non orientato; nel verso corretto nel caso orientato, per un cammino orientato). - Lunghezza del cammino: Il numero $t$ di archi della sequenza. - Cammino elementare: Un cammino senza ripetizioni di nodi. - Cammino semplice: Un cammino senza ripetizioni di archi. - Ciclo: Ogni cammino $s_0 \to s_1 \to \cdots \to s_t$ in cui $s_0 = s_t$. - Nodo accessibile: Un nodo $j$ è accessibile da $i$ se esiste un cammino che li congiunge. - Componenti connesse: Le classi di equivalenza indotte dalla relazione di accessibilità sull’insieme dei nodi. I nodi all'interno di una classe sono tutti accessibili tra loro. - Grafo connesso: Un grafo con una singola componente connessa. - Circuito hamiltoniano: Un ciclo (orientato se il grafo è orientato) che tocca tutti i nodi del grafo una e una sola volta.

Strutture e Sotto-Grafi - Matching (grafo non orientato): Un sottoinsieme $M \subseteq A$ di archi tale che per ogni nodo $i \in V$, esiste al massimo un arco in $M$ incidente su $i$. In alternativa, un sottoinsieme di archi $M$ tali che tra essi non ci sia alcuna coppia di archi adiacenti. - Grafo bipartito (non orientato): Un grafo in cui l’insieme $V$ può essere partizionato in due sottoinsiemi $V_1$ e $V_2$ tali che ogni arco congiunge un nodo in $V_1$ con un nodo in $V_2$ (non contiene cicli di lunghezza dispari). - Grafo bipartito completo: Un grafo bipartito in cui per ogni coppia $i \in V_1, j \in V_2$ si ha che $(i, j) \in A$. - Grafo parziale di $G$: Dato $G = (V, A)$, un grafo $G' = (V, A')$ dove $A' \subseteq A$. - Sottografo di $G$: Un grafo $G'' = (V'', A'')$ dove $V'' \subseteq V$ e $A'' \subseteq A(V'')$ (archi di $A$ tra nodi in $V''$). - Albero (grafo non orientato): Un grafo connesso e aciclico (equivalente a connesso con $m = n-1$, o aciclico con $m = n-1$, o con un unico cammino tra ogni coppia di nodi). - Albero di supporto di $G$: Un grafo parziale $G' = (V, A')$ di $G$ che sia un albero. - Nodo radice: Un nodo identificato in un albero. - Nodo foglia: Un nodo che non ha successori/figli in un albero. - Albero binario: Un albero in cui l’out-degree di ogni nodo non supera 2 ($\delta^+(i) \le 2$). - Binary heap (Struttura dati): Un albero binario con una chiave associata a ciascun nodo, che soddisfa la proprietà Shape (livelli completi, tranne l’ultimo inserito da sinistra a destra) e la proprietà Heap (la chiave di un nodo è sempre almeno grande quanto quella dei suoi nodi figli).

3_spanning_tree

4_flusso_min_costo

Flusso e Basi (Capacità Illimitate) - Flusso di un arco ($x_{ij}$): La quantità di prodotto che viaggia lungo l’arco $(i, j)$. - Flusso ammissibile: Un assegnamento di flussi $x_{ij}$ tale che: 1) per ogni nodo $i$, la differenza tra flusso uscente e flusso entrante è $b_i$ (vincoli di bilancio); 2) $0 \le x_{ij} \le d_{ij}$. - Problema di flusso a costo minimo: Trovare un flusso ammissibile $x$ che minimizzi il costo di trasporto $\sum_{(i, j) \in A} c_{ij}x_{ij}$. - Base ($B$): Un sottoinsieme di $n-1$ archi che formano un albero di supporto di un grafo orientato $G$. - Archi in base/fuori base: Archi in $B$ / archi fuori $B$. - Soluzione di base associata a $B$: L’unica soluzione che rispetta i vincoli di bilancio, ottenuta fissando a 0 il flusso lungo gli archi fuori base. - Base ammissibile ($\mathcal{F}$): Una base $B$ se la soluzione di base associata $x(B)$ soddisfa $x(B)_{ij} \ge 0$ per ogni arco. - Coefficiente di costo ridotto ($\bar{c}_{ij}$): Associato a un arco fuori base $(i, j)$, misura la variazione di costo che si ottiene incrementando il flusso lungo $(i, j)$ da 0 a 1. - Condizione di ottimalità (capacità illimitate): Se $\bar{c}_{ij} \ge 0$ per ogni arco fuori base. In tal caso $x(B)$ è soluzione ottima. - Basi adiacenti: Una base $B'$ ottenuta da $B$ rimuovendo un arco e sostituendolo con un altro. - Condizione di illimitatezza (capacità illimitate): Si verifica se, incrementando un flusso lungo un arco $(i, j)$ con $\bar{c}_{ij} < 0$, il ciclo $C_{(i, j)}(B)$ generato è un ciclo orientato, permettendo al costo di trasporto di decrescere a $-\infty$. - Problema di I fase: Un problema ausiliario creato per trovare una base ammissibile iniziale, risolvendo il quale si può stabilire se il problema originario ha una regione ammissibile non vuota.

Triple e Soluzioni (Capacità Limitate) - Tripla ($T$): Una partizione dell’insieme di archi $A$ in tre sottoinsiemi $(B, N_0, N_1)$, dove $B$ è un albero di supporto, $N_0$ sono archi fuori base a valore nullo, e $N_1$ sono archi fuori base a valore pari alla capacità. - Soluzione di base associata alla tripla $T$: Soluzione che rispetta i vincoli di bilancio fissando a 0 il flusso sugli archi in $N_0$ e alla capacità $d_{hk}$ il flusso sugli archi in $N_1$. - Tripla ammissibile ($\mathcal{F}$): Una tripla $T$ se la soluzione associata $x(T)$ soddisfa $0 \le x_{ij}(T) \le d_{ij}$ per ogni arco. - Condizione di ottimalità (capacità limitate): Se $\bar{c}_{ij} \ge 0$ per ogni arco fuori base in $N_0$, e $\bar{c}_{ij} \le 0$ per ogni arco fuori base in $N_1$. In tal caso $x(T)$ è soluzione ottima.

5_flusso_max

6_matching

7_assegnamento

8_branch_and_bound

9_programmazione_dinamica

10_shortest_path

11_commesso_viaggiatore

12_insieme_indipendente_clique

13_complexity

14_knapsack

Generato il 03/01/2026 alle 16:36 - 🏠 Home