Algoritmi paralleli per il problema dell'Accoppiamento

Abstract realizzato su una tesi del corso di laurea in matematica

Per eventuali approfondimenti sul tema contattare Gian Paolo Bulgarini
Prefazione

Si supponga che una batteria di satelliti nello spazio rappresenti informazioni sulla terra riguardo le previsioni meteorologiche, l’inquinamento, l’agricoltura, le risorse naturali. Per avere a disposizione queste informazioni in tempo ragionevole, è necessario che questi dati vengano esaminati ad una velocità di almeno 10 elevato alla 13 operazioni al secondo. Si supponga di dover disporre di un’elaborazione delle immagini applicate alla medicina come per esempio un consulto di chirurghi che vuole vedere su un  display speciale la figura ricostruita in tre dimensioni del corpo del paziente nella preparazione di una operazione.  Essi hanno la necessità di ruotare l’immagine a loro piacimento, di ottenere una visione trasversale di un organo, di osservarlo nel dettaglio e di eseguire l’operazione simulata mentre ne guardano l’effetto, tutto senza toccare il paziente. 
Questo approccio può essere possibile  con un minimo di velocità di calcolo di 10 elevato alla 15  operazioni per secondo. In questi due esempi è evidente la necessità di poter disporre di una velocità di calcolo eccezionale  per elaborare una grande quantità di dati. Oggi non esistono calcolatori in grado di fornire le velocità di calcolo  richieste da queste applicazioni. Anche i cosiddetti super calcolatori hanno dei picchi di velocità che arrivano a pochi bilioni di operazioni al secondo. Nei passati cinquant’anni c’è stata una tremenda crescita di velocità di calcolo. La  maggior parte di questa è stata dovuta soprattutto all’uso di componenti elettronici sempre più veloci da parte delle ditte di costruzione di calcolatori. Però c’è da considerare un fattore limite. Il fattore di limitazione è una semplice legge della fisica che viene dalla velocità della luce nel vuoto che come è noto risulta approssimativamente uguale a 3 x 10 elevato alla 8  metri per secondo.  Praticamente, ci vuole più tempo per un segnale passare tra due di questi dispositivi distanti anche mezzo millimetro che per uno qualunque di essi per elaborare il segnale. Dunque, tutti i guadagni in velocità ottenuti usando componenti elettronici super veloci vengono persi quando un componente aspetta di ricevere l’ingresso da un altro.  D’altra parte non è possibile neanche avvicinare di molto i componenti poiché la fisica ci dice anche che la riduzione della distanza tra due dispositivi elettronici giunge ad un punto oltre il quale essi incominciano a interagire riducendo non solo la loro velocità ma anche la loro affidabilità. Sembra  che il solo modo per superare questo problema sia usare il parallelismo. L’idea qui è che se molte operazioni vengono eseguite simultaneamente allora il tempo speso per il calcolo può essere ridotto in modo significativo. 

 
 
INDICE 

Parte I         (Macchine e Algoritmi)

Parte II      (Il problema dell'Accoppiamento nei casi seriale e parallelo)
  • Capitolo  IV:    Il problema dell'Accoppiamento Massimo  nel caso Seriale 
  • Capitolo   V:    Il problema dell'Accoppiamento Massimo e massimale nel caso parallelo
  • Esempio di  evoluzione di un grafo nella ricerca del matching 
                                                  Copyright © 2000 GPB
                                       realizzazione: Gian Paolo Bulgarini
                               per informazioni contattare: webmaster@Bulgarini.it