1) Algoritmi stocastici (Monte Carlo, Las vegas, Sherwood, Algoritmi genetici)
Algoritmi in cui è presente almeno un passo stocastico, che genera come uscita, al posto di un risultato deterministico, una distribuzione di probability su un insieme noto di risultati.
Sono molto usati in problemi di ottimizzazione e in problemi il cui comportamento esatto è impossibile da determinare. In questi secondo caso, alla soluzione esatta si sostituisce una simulazione del comportamento del sistema accoppiato con una stima dell’errore.
2) Soluzioni approssimate di problemi NP-Hard.
Quando si ha a che fare con un problema intrattatibile, un modo di procedere è quello di risolverlo in modo approssimato, facendo un compromesso tra l’esattezza della soluzione e la complessità computazionale.
Usando questo approccio è molto importante valutare la qualità dell’approssimazione, calcolando, quando possibile, di quanto si possono discostare, al massimo, la soluzione esatta e quella approssimata.
3) Reti complesse
Le reti complesse sono grafi con numeri di nodi e archi molto elevati (anche dell'ordine dei miliardi). Esse rappresentano sistemi complessi a struttura relazionale, del tipo di Internet, dei sistemi telefonici, delle reti di comunicazione e, con grande sviluppo negli anni più recenti, delle reti dociali (Facebook, Twitter, ...).
Data le dimensioni di una rete complessa, non è possibile studiarne il comportamento in modo dettagliato, ma, al contrario, si usano dei parameri globali per caratterizzarne le proprietà (distribuzione dei gradi, coefficiente di clustering, betweenness, ...).
Stocastic algorithms
Approximate solutions of NP-hard problems
Complex Nertworks
Seguici: