Diagrama gráfico del algoritmo.

Algorithm graph-scheme (GSA) es un gráfico dirigido finito conectado , cuyos vértices corresponden a operadores, y los arcos definen el orden de los vértices (operadores) del algoritmo, donde es el número de vértices del gráfico, es el número de arcos. En un sentido más amplio, los vértices de grafos corresponden no solo a vértices de operadores, sino también a vértices condicionales, iniciales y finales, etc. Al considerar algoritmos paralelos, se introduce el concepto de esquema de grafos de algoritmos paralelos (ParGSA), que incluye cuáles son conjunto. A veces se introducen [1] [2] [3] vértices de tipos adicionales en el GSA: uniones de arcos alternativos (un vértice apareado para un vértice condicional), vértices de operadores ficticios, vértices de marcado (para brindar la posibilidad de simular el ejecución del algoritmo por una red de Petri ), vértices de espera.

Sin embargo, ningún grafo dirigido compuesto por vértices de los tipos anteriores puede identificarse con un algoritmo correcto . Por ejemplo, más de un arco no puede salir de un vértice de operador. Por lo tanto, en la práctica, solemos limitarnos a considerar una subclase de esquemas de grafos de algoritmos que satisfacen las propiedades de seguridad, vivacidad y estabilidad. [4] Los algoritmos de transformación GSA, que son un subconjunto de algoritmos para el procesamiento de gráficos generales, suelen tener diferencias significativas debido al uso de propiedades especiales de GSA, lo que permite su simplificación, reducción de tiempo o complejidad de capacidad . [1] [3] [5]

Como parte del diagrama de grafos del algoritmo, se pueden distinguir elementos más grandes, representados por subconjuntos de sus vértices y arcos: ramas (cadenas lineales o secciones de vértices) y fragmentos (inicial, paralelo, alternativo, cíclico con pre, poscondición y interrupción). Una representación equivalente del esquema gráfico de un algoritmo correcto es un árbol de fragmentos , que refleja el orden de anidamiento de los fragmentos.

Véase también

Notas

  1. ↑ 1 2 Vatutin E. I., Zotov I. V. Construcción de una matriz de relaciones en el problema de partición óptima de algoritmos de control paralelos . Noticias de la Universidad Técnica Estatal de Kursk. Kursk. núm. 2, págs. 85–89. (2004). Archivado desde el original el 28 de abril de 2012.
  2. ↑ Zotov I. V., Titov V. S., Koloskov V. A. [et al.] Organización y síntesis de microprogramas multimicrocontroladores. Kursk: editorial "Kursk", 1999. 368 p. ISBN 5-7277-0253-4
  3. ↑ 1 2 Vatutin E. I., Zotov I. V., Titov V. S. [et al.] Problemas lógicos combinatorios de sintetizar particiones de algoritmos de control de lógica paralela en el diseño de multicontroladores lógicos. Kursk, editorial de la Universidad Técnica Estatal de Kursk, 2010. 200 p. ISBN 978-5-7681-0523-5
  4. ↑ Zakrevskiy A.D. Sobre la corrección de los algoritmos de control de lógica paralela // Izvestia de la Academia de Ciencias de la URSS. Cibernética técnica. - 1987. - Nº 4 . - S. 106-112 .
  5. ↑ Vatutin E. I., Zotov I. V., Titov V. S. Identificación de ocurrencias isomórficas de expresiones R al construir un conjunto de secciones de algoritmos de control de lógica paralela . Sistemas de información-medida y control. No. 11, T. 7. M .: "Ingeniería de radio". págs. 49–56. (2009). Archivado desde el original el 28 de abril de 2012.

Enlaces