Por favor, use este identificador para citar o enlazar este ítem:
http://cicese.repositorioinstitucional.mx/jspui/handle/1007/2684| Análisis probabilístico de algoritmos para contracción de grafos Probabilistic analysis of algorithms for graph contraction | |
| Daniel Fajardo Delgado | |
| Jose Alberto Fernandez Zepeda | |
| Acceso Abierto | |
| Atribución | |
| Análisis de algoritmos,Algoritmos por computadora,Análisis combinatorio,Evaluación de modelos | |
| En el presente trabajo se hace un análisis probabilístico del tiempo de ejecución del algoritmo de simulación de un DR-Mesh en un LR-Mesh elaborado en [Cárdenas-Haro, 2001]. Dicho algoritmo reproduce el comportamiento de un ciclo de máquina de un DR-Mesh acíclico de N × N procesadores en un LR-Mesh de O (N × N) procesadores. Se obtiene que el tiempo de ejecución promedio de este algoritmo es O (log n) u.t. Esto sirve para corroborar la conjetura que hace Cárdenas-Haro respecto a la eficiencia de su simulación. La contribución que se obtiene al comprobar formalmente la rapidez del algoritmo es sumamente relevante, ya que es la simulación más eficiente en su tipo. En esta tesis se utilizan métodos y/o técnicas para analizar grafos generados aleatoriamente y que modelan a un problema real. Asimismo, se definen criterios de comparación de grafos para determinar si el modelo de Cárdenas-Haro representa fielmente a un patrón de conexiones reales de un DR-Mesh. Dichos criterios se basan principalmente en características del grafo que se evalúa, tales como: regularidad, número de nodos, alcanzabilidad, distribución del grado de entrada/salida de los nodos y diámetro del grafo. In this work, we present a probabilistic analysis of the execution time of the simulation of parallel models DR-Mesh on LR-Mesh proposed by [C´ardenas-Haro, 2001]. This algorithm simulates the behavior of a machine cycle of an acyclic N × N DR-Mesh on an O (N × N) LR-Mesh. The average execution time for this algorithm is O (log n) u.t. This helps to confirm the conjeture of C´ardenas-Haro respect to the efficiency of his simulation. The main contribution of this work is to provide a formal proof of the execution time of this simulation, wich is the most efficient simulation for these models. In this thesis we design methods and/or techniques to analyze randomized generated graphs that model a real problem. Similarly, we define comparison criterion to determine if the C´ardenas-Haro’s model represents accuratelly real connection patterns of a DR-Mesh. These criterion are based mainly on the graph’s characteristics such as: regularity, nodes number, reachability, input/output degree distribution of the nodes, and graphs diameter. | |
| CICESE | |
| 2003 | |
| Tesis de maestría | |
| Español | |
| Fajardo Delgado, D.2003.Análisis probabilístico de algoritmos para contracción de grafos.Tesis de Maestría en Ciencias.Centro de Investigación Científica y de Educación Superior de Ensenada, Baja California.99 pp. | |
| TECNOLOGÍA DE LOS ORDENADORES | |
| Aparece en las colecciones: | Tesis - Ciencias de la Computación |
Cargar archivos:
| Fichero | Tamaño | Formato | |
|---|---|---|---|
| 158151.pdf | 839.24 kB | Adobe PDF | Visualizar/Abrir |