• بازدید : 77 views
  • بدون نظر
این فایل در ۱۰۲اسلاید قابل ویرایش تهیه شده وشامل موارد زیر است:

هر پروژه ای را می توان به چندين زيرپروژه كه فعاليت ناميده مي شود، تقسیم کرد .

    به عنوان مثال :

یک دانشجوی رشته مهندسی نرم افزار برای گرفتن مدرک ناچار به موفقیت در چندین درس است.
پس هر درس به عنوان یک فعالیت در نظر گرفته می شود.
پيش نيازها روابط و اولويت موجود بين دروس را معين مي كنند .
به منظور روشن شدن روابط پيش نيازي مي توان از يك گراف         جهتدار استفاده كرد، كه در آن :
– راس ها را نمایانگر دروس
– وهر یال جهتدار آن را نشان دهنده ی رابطه پیش نیازی قرار   می دهیم .
حال اگر یک راس پیش نیاز راس دیگر باشد از راس اول یک یال به سمت راس دوم رسم می کنیم .
شبکه فعالیت روی راس(AOV) :این شبکه در واقع یک گراف جهتدار مانند G می باشد که راس های آن نمایانگر فعالیت ها و یالهای آن نمایانگر ارتباطات بین فعالیت ها می باشد.

راس i در یک شبکه AOV از گراف G  راسی قبل از راس  j  خواهد بود اگر وتنها اگر مسیر جهتداری از راس i به راس j وجود داشته باشد.

راسi در یک شبکه AOV بلافاصله قبل از راس j است اگر و تنها اگر(i, j) یالی در G باشد.
رابطه متعدی:
    رابطه ی نقطه (.) را یک رابطه ی متعدی گوییم اگر و تنها اگر برای تمام سه گانه های  iو j و k داشته باشیم : 
i . j & j . k           i . k    
رابطه غیرانعکاسی:
       رابطه اي را روی مجموعه ی S غیر انعکاسی گوییم اگر برای تمامی مقادیر x در S  ,  x . x نادرست باشد.

 رابطه ترتیبی : 
       رابطه ای که هم متعدی باشد و هم غیر انعکاسی يك رابطه ترتیبی نام دارد.
رابطه ي ترتيبي تعريف شده توسط پيش نيازهاي درسي يك رابطه ي متعدي 
است .
 معلوم نيست .AOV اما اين موضوع در شبكه ي 

اگر يك شبكه داراي چرخه باشد انگاه يك فعاليت وجود خواهد داشت كه بايد قبل از اغاز شدن كامل گردد و واضح است كه اين امرغيرممكن است .
هنگامي كه هيچ تناقضي از اين نوع موجود نباشد پروژه عملي است .
ترتيب موضعي :
       يك ترتيب خطي از راس هاي يك گراف است به نحوي كه به ازاي هر دو راس i و j اگر i يك راس تقدمي براي j در شبكه باشد انگاه i در اين ترتيب خطي پيش از j قرار مي گيرد .
       
الگوريتم ارائه شده براي آزمايش عملي بودن پروژه يك ترتيب خطي از راس ها (فعاليت ها) را به صورت  V0,V1,…,Vn-2,Vn-1  توليد مي كند . 
در ابتدا راسي كه هيچ راس ديگري در شبكه قبل از ان قرار ندارد را با تمام يال هايي كه از ان خارج مي شود از شبكه حذف مي كنيم . اين  مرحله تا زماني ادامه مي يابد كه همه ي راس هاي در شبكه حذف شوند .

۱   //Input the AOV network . Let n be the number of vertices .
۲   For ( int i=0 ; i<n ; i++ )
۳   {
۴      if ( every vertex has a predecessor)
۵         return ; //network has a cycle and is infeasible .
۶      pick a vertex V that has no predecessors ;
۷      cout << V ;
۸      delete V and all edges leading out of V from the network ;
۹   } 
اعمال لازم براي اين مسئله :
۱- آيا يك راس، راس تقدمي است؟
۲- چگونگي حذف يك راس با همه ي يال هاي متصل؟

تعداد راس هاي ماقبل هر راس را ذخيره مي كنيم .

پياده سازي با ليست هاي مجاورتي
حذف همه يال هاي خارج شده از راس v را با كاهش تعداد راس هاي تاخيري بلافاصل راس v در ليست مجاورتي انجام داد . 
وقتي كه تعداد راس هاي تقدمي يك راس برابر با صفر شد راس آماده حذف است.

عتیقه زیرخاکی گنج