000007067 001__ 7067 000007067 005__ 20190219123658.0 000007067 037__ $$aTESIS-2012-040 000007067 041__ $$aspa 000007067 1001_ $$aCano Acosta, Elia Esther 000007067 24500 $$aTeoría de Grafos Aplicada al Análisis de Redes S4PR y Subclases$$bEl Problema de Cálculo de los Cerrojos Mínimos 000007067 260__ $$aZaragoza$$bUniversidad de Zaragoza, Prensas de la Universidad$$c2011 000007067 300__ $$a169 000007067 490__ $$aTesis de la Universidad de Zaragoza$$v2011-39$$x2254-7606 000007067 500__ $$aPresentado: 26 10 2011 000007067 502__ $$aTesis-Univ. Zaragoza$$bZaragoza, Universidad de Zaragoza$$c2011 000007067 506__ $$aby-nc-nd$$bCreative Commons$$c3.0$$uhttps://creativecommons.org/licenses/by-nc-nd/3.0/ 000007067 520__ $$aLa presente memoria utiliza la teoría de grafos en el análisis de redes s4pr. La necesidad de disponer de algoritmos eficientes para calcular los cerrojos mínimos u otros conjuntos de cerrojos para esta clase de redes es el motivo que ha conducido esta investigación. Para alcanzar el objetivo trazado se ha desarrollado como punto de partida las propiedades estructurales que poseen las redes s4pr, esto se ha hecho debido a que en todos los trabajos anteriores se utilizaban las mismas propiedades que poseen las redes de petri generales y no se tomaba ventaja de la estructura que este tipo de redes posee. De igual forma se han caracterizado los cerrojos mínimos en función del conjunto de recursos que estos poseen. A partir de los resultados antes mencionados se ha desarrollado una herramienta denominada relación de poda entre los cerrojos mínimos de un recurso la cual nos permite determinar el conjunto de lugares que un cerrojo mínimo de un recurso puede podar a otro cerrojo mínimo de un recurso. Esta herramienta nos permite obtener los cerrojos mínimos del conjunto de cerrojos que la red posee. Para representar esta relación se utiliza un grafo al cual se le ha llamado grafo de poda y tres funciones de etiquetado asociadas al mismo. Este grafo nos permite realizar el cálculo de cerrojos para un conjunto de recursos dado o el cálculo de cerrojos mínimos de una manera más eficiente al trabajar calculando y manipulando los subgrafos fuertemente conexos máximos del grafo. Por lo tanto, la memoria requerida es muy pequeña y del orden del tamaño del grafo de poda. Finalmente, se presenta la especialización de los algoritmos de cálculo de cerrojos mínimos con más de un recurso para las redes l-s3pr, s3pr y soar2 cuyo objetivo es obtener algoritmos que sean más eficientes que el desarrollado para las redes s4pr. Este trabajo contribuye en: 1. Nuevas propiedades estructurales para las redes s4pr. 2. Cotas inferior y superior de los cerrojos mínimos para las redes s4pr, l-s3pr, s3pr y soar2. 3. Caracterización de los cerrojos mínimos por el conjunto de recursos que contienen. 4. Nuevas herramientas: relación de poda y grafo de poda, que nos permiten obtener los cerrojos mínimos del conjunto de cerrojos que una red s4pr posee. 5. Algoritmo para calcular los cerrojos de una red s4pr que contengan determinados recursos. 6. Algoritmo para calcular los cerrojos mínimos para redes s4pr, l-s3pr, s3pr y soar2. 000007067 6531_ $$aredes s4pr 000007067 6531_ $$acerrojos mínimos 000007067 6531_ $$ateoría de grafos 000007067 700__ $$aColom Piazuelo, José Manuel$$edir. 000007067 7102_ $$aUniversidad de Zaragoza$$bInformática e Ingeniería de Sistemas 000007067 8560_ $$fzaguan@unizar.es 000007067 8564_ $$s1204663$$uhttps://zaguan.unizar.es/record/7067/files/TESIS-2012-040.pdf$$zTexto completo (spa) 000007067 909CO $$ooai:zaguan.unizar.es:7067 000007067 909co $$ptesis 000007067 909CO $$pdriver 000007067 9102_ $$aIngeniería de sistemas y automática$$bInformática e Ingeniería de Sistemas 000007067 980__ $$aTESIS