Vai ai contenuti. | Spostati sulla navigazione | Spostati sulla ricerca | Vai al menu | Contatti | Accessibilità

logo del sistema bibliotecario dell'ateneo di padova

De Stefani, Lorenzo (2012) On the space complexity of DAG computations. [Magistrali biennali]

Full text disponibile come:

[img]
Preview
PDF
949Kb

Abstract

In this thesis we have studied some issues related to the space complexity of Directed Acyclic Graphs (DAG) computations and in particular the possibility of obtaining a reduction of the amount of memory necessary to the evaluation of a DAG using computations with multiple assessments of the same vertex rather than strictly without recalculations. In the main result of the thesis, we introduce a method to obtain a significant upper bound for the space complexity of a DAG, based on the concept of DAG-vertex separator. By further developing this result according to the divide and conquer paradigm we obtain a decomposition of the DAG through which it is possible to observe a relationship between topological characteristics of the graph and its space complexity

Item Type:Magistrali biennali
Corsi di Diploma di Laurea:Scuola di Ingegneria > Ingegneria Informatica
Scuola di Ingegneria > Ingegneria Informatica
Uncontrolled Keywords:space, complexity, DAG, computations
Subjects:Area 09 - Ingegneria industriale e dell'informazione > ING-INF/05 Sistemi di elaborazione delle informazioni
Codice ID:39775
Relatore:Bilardi, Gianfrnaco
Data della tesi:17 April 2012
Biblioteca:Polo di Ingegneria > Biblioteca di Ingegneria dell'Informazione e Ingegneria Elettrica "Giovanni Someda"
Tipo di fruizione per il documento:on-line per i full-text

Solo per lo Staff dell Archivio: Modifica questo record