Implementazione e valutazione delle prestazioni di algoritmi per il calcolo di cammini minimi su grafi

Dogan, Can (2018) Implementazione e valutazione delle prestazioni di algoritmi per il calcolo di cammini minimi su grafi. [Laurea], Università di Bologna, Corso di Studio in Ingegneria e scienze informatiche [L-DM270] - Cesena, Documento full-text non disponibile
Il full-text non è disponibile per scelta dell'autore. (Contatta l'autore)

Abstract

Lo scopo di questa tesi è di implementare e analizzare algoritmi paralleli su grafi. Gli algoritmi in oggetto sono quelli di Bellman-Ford per i cammini minimi da singola sorgente (Single-Source Shortest Paths), e di Floyd Warshall per i cammini minimi tra tutte le coppie di nodi (All-Pairs Shortest Paths). Analizzeremo a fondo entrambi gli algoritmi e vedremo come variano i tempi di esecuzione rispetto alle versioni seriali, e ne valuteremo la scalabilità. Per avere un’idea concreta di come e dove vengono utilizzati, vedremo alcune delle principali applicazioni che fanno uso di questi algoritmi. I capitoli saranno suddivisi nel seguente modo: la prima parte farà da introduzione e tratterà l’argomento sui grafi e i cammini, nella seconda parte si illustreranno gli algoritmi in dettaglio, nella terza parte si parlerà della piattaforma di parallelizzazione e delle implementazioni parallele degli algoritmi, infine nell’ultima parte verranno analizzate le prestazioni delle implementazioni proposte.

Abstract
Tipologia del documento
Tesi di laurea (Laurea)
Autore della tesi
Dogan, Can
Relatore della tesi
Scuola
Corso di studio
Indirizzo
Curriculum ingegneria informatica
Ordinamento Cds
DM270
Parole chiave
algoritmi,paralleli,cammini minimi,grafi,OpenMP,prestazioni
Data di discussione della Tesi
18 Ottobre 2018
URI

Altri metadati

Gestione del documento: Visualizza il documento

^