Grafdiagram af algoritmen

Algoritme graf-skema (GSA) er en endelig forbundet rettet graf , hvis toppunkter svarer til operatorer, og buerne definerer rækkefølgen af ​​toppunkterne (operatorerne) af algoritmen, hvor er antallet af grafens toppunkter, er antallet af buer. I bredere forstand svarer grafhjørnepunkter ikke kun til operatorhjørner, men også til betingede, indledende og endelige knudepunkter osv. Når man betragter parallelle algoritmer, introduceres konceptet med et parallelt algoritmegrafskema (ParGSA), som omfatter hvilke som normalt er kombineret. Nogle gange introduceres [1] [2] [3] hjørner af yderligere typer i GSA: foreninger af alternative buer (et parret toppunkt for et betinget toppunkt), fiktive operatorpunktpunkter, markering af toppunkter (for at give mulighed for at simulere udførelse af algoritmen af ​​et Petri-net ), ventende hjørner.

Imidlertid kan ingen rettet graf sammensat af toppunkter af ovennævnte typer identificeres med en korrekt algoritme . For eksempel kan mere end én bue ikke gå ud af et operator-toppunkt. Derfor begrænser vi os i praksis normalt til at overveje en underklasse af grafskemaer af algoritmer, der tilfredsstiller egenskaberne sikkerhed, livlighed og stabilitet. [4] GSA-transformationsalgoritmer, som er en delmængde af algoritmer til behandling af generelle grafer, har ofte betydelige forskelle på grund af brugen af ​​specielle GSA-egenskaber, som tillader deres forenkling, reduktion af tid eller kapacitetskompleksitet . [1] [3] [5]

Som en del af grafdiagrammet for algoritmen kan større elementer skelnes, repræsenteret ved delmængder af dens toppunkter og buer: grene (lineære kæder eller sektioner af toppunkter) og fragmenter (initial, parallelle, alternative, cykliske med præ-, postbetingelse og afbrydelse). En ækvivalent repræsentation af grafskemaet for en korrekt algoritme er et træ af fragmenter , som afspejler fragmenternes indlejringsrækkefølge.

Se også

Noter

  1. ↑ 1 2 Vatutin E. I., Zotov I. V. Konstruktion af en matrix af relationer i problemet med optimal opdeling af parallelle kontrolalgoritmer . Nyheder fra Kursk State Technical University. Kursk. nr. 2, s. 85–89. (2004). Arkiveret fra originalen den 28. april 2012.
  2. ↑ Zotov I. V., Titov V. S., Koloskov V. A. [et al.] Organisering og syntese af mikroprogram multimikrocontrollere. Kursk: forlaget "Kursk", 1999. 368 s. ISBN 5-7277-0253-4
  3. ↑ 1 2 Vatutin E. I., Zotov I. V., Titov V. S. [et al.] Kombinatorisk-logiske problemer med at syntetisere partitioner af parallelle logiske kontrolalgoritmer i design af logiske multicontrollere. Kursk, forlag af Kursk State Technical University, 2010. 200 s. ISBN 978-5-7681-0523-5
  4. ↑ Zakrevskiy A.D. Om rigtigheden af ​​parallelle logiske kontrolalgoritmer // Izvestia fra USSR's Videnskabsakademi. Teknisk kybernetik. - 1987. - Nr. 4 . - S. 106-112 .
  5. ↑ Vatutin E.I., Zotov I.V., Titov V.S. Identifikation af isomorfe forekomster af R-udtryk ved konstruktion af et sæt af sektioner af parallelle logiske kontrolalgoritmer . Informationsmåle- og kontrolsystemer. nr. 11, T. 7. M .: "Radioteknik". s. 49–56. (2009). Arkiveret fra originalen den 28. april 2012.

Links