-
آرشیو :
نسخه پاییز 1397
-
موضوع :
مهندسی نرم افزار
-
نویسنده/گان :
احسان خراطی
-
چکیده :
آزمون یک راه اولیه برای اطمینان از نرمافزار، در سیستمهای حساس به ایمنی است. برای این منظور باید فرآیند آزمون را به اندازه کافی اجرا کرده و اثبات کرد که تمام سطوح آزمون پوشش میشوند. سطوح پوشش اغلب یا توصیه شدهاند یا براساس استانداردهای امنیتی و دستورالعملهای صنعتی وضع شدهاند. آزمون جهش، یک روش مکمل یا جایگزین برای اندازهگیری کارایی آزمون است. اما بهطور گستردهایی در نرمافزارهای صنعتی و یا حساس به ایمنی بکار نمیرود. در این مقاله، آزمون جهش در سیستمهای نرمافزاری هوایی که حساس به ایمنی هستند با پوشش اکثر نیازمندیها و با استفاده از عملگرهای سطح بالا در زبانهای C و Ada انجام میشود. همچنین در این مقاله موثرترین انواع جهش و منشا عدم موفقیتها شناسایی شده و سپس تحلیل و بررسی شده و تا بتوان رابطهای بین مشخصات برنامه نظیر تعداد خطوط کد و پیچیدگی مداری و پایداری جهش و جهشهای زنده مانده و خطاهای نهفته یافت.
نتایج نشان میدهد که آزمون جهش میتواند نسبت به تحلیل پوشش ساختاری سنتی و بررسی دستی موثرتر باشد و سبب بهبود فرآیند برنامهنویسی و تعریف نیازمندیها گردد. همچنین در زمینههای صنعتی نظیر نرمافزارهای هوایی نیز میتوان از آزمون جهش استفاده کرد.
واژگان کليدي: آزمون جهش، حساس به ایمینی، اطمینان، کارایی. بررسی وجود الگوریتم¬های موازی برای مسـأله¬ی DFS در گراف¬ها منجربه ایجاد تفکرات متعددی در این زمینه شده است. اولین الگوریتم برای DFS را Tarjan و Tarjan –Hopcroft ارائه نمودند، و دیگران نیز سعی در ارائه¬ی الگوریتم¬های موازی در این حوزه کوشیدند. در این مقاله ابتدا بررسی ذاتا" ترتیبی الگوریتم DFS توسط REIF صورت می¬پذیرد و سپس بررسی الگوریتم NC برای گراف¬های مسطح توسطSmith و انتها نیز بررسی الگوریتم RNC توسط Anderson & Aggarwal مورد تحقیق قرارمی¬گیرد. البته در انتهای مقاله نتایج بررسی هر کدام از الگوریتم¬های موازی برای جستجوی اول عمق گراف به تفکیک ارائه شده است.
-
کلید واژه :
الگوریتم موازی، جستجوی اول عمق گراف، مسائل NP-کامل و مسائل P-کامل
-
Title :
Investigate parallel algorithms to first search for graph depth
-
Abstract :
The study of the existence of parallel algorithms for the DFS problem in graphs has led to the creation of several ideas in this field. Tarjan and Tarjan-Hopcroft provided the first algorithm for DFS, and others tried to provide parallel algorithms in this area. This paper first examines the inherent "sequence" of the DFS algorithm by REIF, then Smith's study of the NC algorithm for flat graphs, and finally the study of the RNC algorithm by Anderson & Aggarwal. Which parallel algorithms are presented separately for the first search of graph depth
-
مراجع :
[1] Reif, J, H. (1985) Depth-first search is inherently sequential. Information Processing Letters,
20:229-234.
[2] Reif, J, H. (1984) On synchronous parallel computations with independent probabilistic choice.
SIAM Journal on Computing, 13(1):46-56.
[3] Smith, J, R. (1986) Parallel algorithms for depth-first searches I. planar graphs. SIAM Journal
on Computing, 15(3):814-830, August 1986.
[4] Aggarwal, A. (1988) Anderson, R. J., A random NC algorithm for depth first search.
Combinatorica, 8(1):1-12.
[5] Aggarwal, A. (1990) Anderson, R. J., Kao, M. Y., Parallel depth-first search in
general directed graphs. SIAM Journal on Computing, 19(2):397-409.
[6] Anderson, R, J. (1986) A parallel algorithm for depth-first search. Extended Abstract, Mathematical Science Research Institute.
[7] Anderson, R, J. (1987) A parallel algorithm for the maximal path problem. Combinatorica, 7(4):315-
326.
- صفحات : 26-45
-
دانلود فایل
( 941 KB )