Algoritmi di ottimizzazione
1) Copertura e partizione di un insieme :
La copertura di un insieme è un insieme costituito da sottoinsiemi tali da coprire tutto l´insieme di partenza, se questi sottoinsiemi non hanno alcuna intersezione tra loro si ha una partizione.
2) Differenza tra cammino e percorso:
Un cammino è un susseguirsi di vertici e connessioni, si distingue dal percorso in quanto per quest´ultimo ogni vertice può essere attraversato soltanto una volta.
3) Grafo connesso:
Tutte le coppie di vertici sono collegate da almeno un percorso.
4) Insieme stabile di vertici e colorazione :
Un insieme stabile di vertici è un insieme costituito da vertici che non hanno alcuna connessione tra loro. La colorazione è una partizione in sottoinsiemi stabili.
5) Differenza tra grafo diretto ed indiretto :
In un grafo diretto i vertici le connessioni sono unidirezionali mentre in un grafo indiretto esse sono bidirezionali.
6) Matrice di incidenza :
È la matrice che si ottiene da un grafo mettendo sulle righe i vertici e sulle colonne le connessioni, nelle intersezioni si pone un 1 se la connessione entra nel vertice, un –1 se ne esce ed uno 0 se non vi arriva.
7) Matrice di adiacenza e matrice dei pesi :
È una matrice quadrata che si ottiene da un grafo mettendo i vertici sia in ordinata che in ascissa e ponendo poi un 1 o uno 0 nell´incrocio a seconda che tra i dati vertici vi sia un collegamento o meno, se invece il grafo è pesato, si mettono i pesi corrispondenti nelle intersezioni.
8) Problema decisionale :
È un problema che ammette una soluzione binaria, vero o falso.
9) Problema di ottimizzazione :
È un problema la cui soluzione si misura in termini di una funzione costo o obiettivo che a seconda del problema deve essere massimizzata o minimizzata, solitamente il problema viene ridotto ad una sequenza di problemi decisionali.
10) Algoritmo e sue tipologie :
È una procedura computazionale avente un insieme di ingressi e di uscite , un numero finito di istruzioni e viene eseguito in un numero finito di passi, in base alla precisione della soluzione si hanno i seguenti tipi di algoritmi :
a) algoritmo esatto fornisce sempre la soluzione esatta
b) algoritmo euristico fornisce una soluzione prossima all´ottimo nel caso vi sia una eccessiva complessità computazionale del problema
11) Complessità di un algoritmo :
Tiene conto delle dimensioni della memoria necessaria a svolgere le operazioni e del tempo che si impiega per giungere alla soluzione, viene espressa in termini di O[f(n)] dove n è la dimensione del problema , in genere algoritmi polinomiali sono più fattibili che non algoritmi esponenziali tuttavia occorre tener conto di una costante moltiplicativa che potrebbe ribaltare la situazione ad esempio per n piccolo. L´algoritmo ottimo ha complessità O[n] .
12) Classificazione degli algoritmi in base alle caratteristiche dello spazio delle soluzioni :
Si parla di programmazione lineare LP nel caso si debba ottimizzare una funzione lineare sottoposta a dei vincoli lineari, si ha invece la programmazione lineare intera ILP nel caso il vettore incognito appartiene all´insieme dei numeri interi, in tal caso si giunge alla soluzione arrotondando la soluzione ottenibile mediante la programmazione lineare. Un ulteriore sottocaso della programmazione lineare intera è la programmazione lineare binaria ZOLP nella quale il vettore della soluzione è binario.
13) Classi di algoritmi di ottimizzazione :
Gli algoritmi di ottimizzazione si suddividono nelle tre seguenti classi :
a ) tecniche enumerative ricercano la soluzione in tutto il dominio della funzione , il problema può essere risolto suddividendolo in problemi più semplici.
b1 ) tecniche numeriche indirette cercano il minimo della funzione iterativamente risolvendo equazioni non lineari , la algoritmo si arresta quando il gradiente si annulla.
b2 ) tecniche numeriche dirette cercano il minimo della funzione lasciandosi guidare dal gradiente.
c ) tecniche numeriche probabilistiche sono tecniche enumerative che utilizzano per la ricerca informazioni addizionali, un esempio è il Simulated Annealing e gli algoritmi genetici.
14) Problema di cammino minimo e massimo :
È un problema tipico che si può rappresentare mediante un grafo diretto connesso e pesato, si ha un vertice sorgente e si deve cercare il percorso minimo nel grafo che porta ad uno qualsiasi degli altri vertici. La complessità del problema è O[n2] ed in genere si utilizza la algoritmo di Bellman-Ford consistente nell´inizializzare il cammino minimo con i pesi delle connessioni dal vertice sorgente e nella aggiornare iterativamente i pesi durante il cammino.
15) Problema della colorazione :
Viene rappresentato mediante un grafo nel quale le connessioni rappresentano delle incompatibilità tra i processi rappresentati dai vertici ad esempio per un loro utilizzo contemporaneo della stessa risorsa. Lo scopo è trovare il minimo numero di colori che consentono la colorazione del grafico o in altri termini ad esempio trovare il minimo numero di risorse che consente l´esecuzione di tutti i processi.
16) Algoritmo del gradiente :
La ricerca di un minimo della funzione costo non è un problema semplice in quanto può capitare che il minimo trovato sia soltanto un minimo locale, è quanto accade con questo algoritmo, infatti il minimo locale viene ricercato a partire da un punto x0 nel quale la funzione vale y0 , ci si sposta un pò a sinistra ed un pò a destra, se in uno dei due punti il costo è inferiore, tale punto diviene il nuovo minimo e la algoritmo prosegue, altrimenti si è individuato il minimo assoluto che come affermato precedentemente potrebbe invece essere soltanto un minimo locale e la algoritmo non è in grado di accorgersene. Appartengono a questa categoria i seguenti algoritmi per la ricerca della migliore disposizione di un certo numero di oggetti :
a) Constructive Initial Placement viene scelto un oggetto in base al numero di altri oggetti cui deve esser connesso, viene collocato in modo da minimizzare la lunghezza totale dei collegamenti rispetto al posizionamento precedente.
b) Pairwise Interchange posiziona tutti gli oggetti casualmente, poi ne seleziona due li scambia e se la lunghezza dei collegamenti non diminuisce li rimette a posto.
c) Neighboorhood Interchange è come il Pairwise Interchange ma stavolta gli oggetti scambiati sono adiacenti.
d) Steinberg´s Algorithm seleziona un insieme di oggetti che non ha collegamenti comuni e li si rimuove
e) Force Directed Relaxation ad ogni oggetto viene associato un vettore forza in base alla distanza degli oggetti cui deve essere collocato, si cerca di posizionare l´oggetto in un punto in cui la forza che su di esso agisce è nulla.
17) Algoritmo del simulated annealing :
È un algoritmo che consente la ricerca del minimo assoluto anche in presenza di minimi locali, in pratica se la differenza di costo Dc , tra il minimo precedente e il punto candidato ad essere il nuovo minimo, è negativa allora il candidato diviene il nuovo minimo altrimenti se è positiva il candidato ha ugualmente una probabilità non nulla di essere accettato, in particolare si utilizzano le funzioni di distribuzione di Boltzmann
oppure di Dirac 
in cui T è la temperatura che inizialmente viene scelta alta in modo da accettare molti stati per poi decrescere di passo in passo secondo la legge 
con a compreso tra 0,95 e 0,8 .
18) Regole genetiche :
Si tratta di regole tratte dalla genetica e che sono considerate alla base della evoluzione umana, esse sono :
a) l´evoluzione agisce sui cromosomi e non sugli esseri viventi che codifica.
b) si riproducono con maggiore probabilità i cromosomi che codificano strutture che meglio si adattano alla ambiente.
c) l´evoluzione è concentrata nella riproduzione dove mutazione e ricombinazione alterano i cromosomi dei figli rispetto a quelli dei genitori
d) la nuova generazione viene creata a partire da quella attuale e dal suo patrimonio genetico indipendentemente dal percorso evolutivo.
19) Algoritmo genetico :
Innanzitutto occorre codificare i cromosomi, in genere essi vengono codificati in binario e mediante Grey in modo che soluzioni numericamente vicine abbiano rappresentazioni con minima distanza di Hamming, viene quindi inizializzata la popolazione e valutata per tutti la funzione costo, si tiene traccia della migliore dopodiché si passa alla generazione di una nuova popolazione, in particolare scelti due cromosomi con criteri probabilistici legati alla bontà della loro soluzione, essi vengono tagliati in maniera probabilistica e con tali pezzi il processo di ricombinazione genera 2 figli, la mutazione poi consente di cambiare in maniera casuale ma con probabilità comunque bassa dei bit dei cromosoma figli. La popolazione deve rimanere costante quindi occorre eliminare una coppia di cromosomi appartenenti alla generazione precedente, a tal fine si utilizza ancora un criterio probabilistico in modo che individui con una soluzione migliore abbiano maggiore probabilità di sopravvivere. Alla fine di ogni ciclo viene poi valutata la soluzione migliore al fine di verificare se si è raggiunta la condizione di arresto del processo.