Az algoritmus grafikon diagramja

Az Algorithm graph-scheme (GSA) egy véges összefüggő irányított gráf , amelynek csúcsai operátoroknak felelnek meg, és az ívek határozzák meg az algoritmus csúcsainak (operátorainak) sorrendjét, ahol a gráf csúcsainak száma, az ívek száma. Tágabb értelemben a gráfcsúcsok nem csak az operátorcsúcsoknak felelnek meg, hanem a feltételes, a kezdeti és a végső csúcsoknak is. A párhuzamos algoritmusok vizsgálatakor bevezetjük a párhuzamos algoritmus gráfséma (ParGSA) fogalmát, amely magában foglalja a rendszerint kombinált. Néha [1] [2] [3] további típusú csúcsokat vezetnek be a GSA-ba: alternatív ívek uniói (egy páros csúcs egy feltételes csúcshoz), fiktív operátorcsúcsok, jelölőcsúcsok (hogy lehetőség legyen a szimulációra az algoritmus végrehajtása Petri-hálóval ), várakozási csúcsok.

A fenti típusú csúcsokból álló irányított gráf azonban nem azonosítható megfelelő algoritmussal . Például egy operátorcsúcsból egynél több ív nem mehet ki. Ezért a gyakorlatban általában az algoritmusok gráfsémáinak egy alosztályának figyelembevételére szorítkozunk, amely kielégíti a biztonság, az élénkség és a stabilitás tulajdonságait. [4] A GSA transzformációs algoritmusok, amelyek az általános gráfok feldolgozására szolgáló algoritmusok egy részhalmazát képezik, gyakran jelentős különbségeket mutatnak a speciális GSA-tulajdonságok használatának köszönhetően, amelyek lehetővé teszik azok egyszerűsítését, az idő vagy a kapacitás bonyolultságának csökkentését . [1] [3] [5]

Az algoritmus gráfdiagramjának részeként megkülönböztethetők a nagyobb elemek, amelyeket csúcsainak és íveinek részhalmazai reprezentálnak: elágazások (lineáris láncok vagy csúcsszakaszok) és töredékek (kezdeti, párhuzamos, alternatív, ciklikus elő-, utófeltétellel, ill. félbeszakítás). A helyes algoritmus gráfsémájának egyenértékű reprezentációja a töredékek fája , amely tükrözi a töredékek egymásba ágyazott sorrendjét.

Lásd még

Jegyzetek

  1. ↑ 1 2 Vatutin E. I., Zotov I. V. Relációmátrix felépítése párhuzamos vezérlőalgoritmusok optimális particionálásának problémájában . A Kurszki Állami Műszaki Egyetem hírei. Kurszk. 2. szám, 85–89. (2004). Archiválva az eredetiből 2012. április 28-án.
  2. ↑ Zotov I. V., Titov V. S., Koloskov V. A. [et al.] Mikroprogramos multimikrovezérlők szervezése és szintézise. Kurszk: "Kursk" kiadó, 1999. 368 p. ISBN 5-7277-0253-4
  3. ↑ 1 2 Vatutin E. I., Zotov I. V., Titov V. S. [et al.] Párhuzamos logikai vezérlőalgoritmusok partícióinak szintetizálásának kombinatorikai-logikai problémái logikai multivezérlők tervezésében. Kurszk, a Kurszki Állami Műszaki Egyetem kiadója, 2010. 200 p. ISBN 978-5-7681-0523-5
  4. ↑ Zakrevskiy A.D. A párhuzamos logikai vezérlési algoritmusok helyességéről // A Szovjetunió Tudományos Akadémia Izvesztyija. Műszaki kibernetika. - 1987. - 4. sz . - S. 106-112 .
  5. ↑ Vatutin E. I., Zotov I. V., Titov V. S. R-kifejezések izomorf előfordulásának azonosítása párhuzamos logikai vezérlőalgoritmusok szekcióinak összeállítása során . Információ-mérő és vezérlő rendszerek. 11. szám, T. 7. M .: „Rádiótechnika”. 49–56. (2009). Archiválva az eredetiből 2012. április 28-án.

Linkek