بخشی از پاورپوینت
اسلاید 1 :
آنچه كه در اين اسلايد مي خوانيم :
(شبكه فعاليت روي راس ها)AOV 1) نمايش شبكه
(شبكه فعاليت روي يال ها)AOE 2) نمايش شبكه
3) محاسبه ي زودترين زمان فعاليت
4) محاسبه ي ديرترين زمان فعاليت
اسلاید 2 :
AOV ) نمایش شبکه1
هر پروژه ای را می توان به چندين زيرپروژه كه فعاليت ناميده مي شود، تقسیم کرد .
به عنوان مثال :
یک دانشجوی رشته مهندسی نرم افزار برای گرفتن مدرک ناچار به موفقیت در چندین درس است.
پس هر درس به عنوان یک فعالیت در نظر گرفته می شود.
پيش نيازها روابط و اولويت موجود بين دروس را معين مي كنند .
اسلاید 3 :
مثال
به منظور روشن شدن روابط پيش نيازي مي توان از يك گراف جهتدار استفاده كرد، كه در آن :
- راس ها را نمایانگر دروس
- وهر یال جهتدار آن را نشان دهنده ی رابطه پیش نیازی قرار می دهیم .
حال اگر یک راس پیش نیاز راس دیگر باشد از راس اول یک یال به سمت راس دوم رسم می کنیم .
اسلاید 4 :
تعاریف
Ø
Øشبکه فعالیت روی راس(AOV) :این شبکه در واقع یک گراف جهتدار مانند G می باشد که راس های آن نمایانگر فعالیت ها و یالهای آن نمایانگر ارتباطات بین فعالیت ها می باشد.
Ø
Øراس i در یک شبکه AOV از گراف G راسی قبل از راس j خواهد بود اگر وتنها اگر مسیر جهتداری از راس i به راس j وجود داشته باشد.
Ø
Øراسi در یک شبکه AOV بلافاصله قبل از راس j است اگر و تنها اگر(i, j) یالی در G باشد.
Ø
اسلاید 5 :
تعاريف
Øرابطه متعدی:
رابطه ی نقطه (.) را یک رابطه ی متعدی گوییم اگر و تنها اگر برای تمام سه گانه های iو j و k داشته باشیم :
i . j & j . k i . k
Øرابطه غیرانعکاسی:
رابطه اي را روی مجموعه ی S غیر انعکاسی گوییم اگر برای تمامی مقادیر x در S , x . x نادرست باشد.
Ø رابطه ترتیبی :
رابطه ای که هم متعدی باشد و هم غیر انعکاسی يك رابطه ترتیبی نام دارد.
Ø
اسلاید 6 :
تعاريف - ادامه
رابطه ي ترتيبي تعريف شده توسط پيش نيازهاي درسي يك رابطه ي متعدي
است .
معلوم نيست .AOV اما اين موضوع در شبكه ي
اگر يك شبكه داراي چرخه باشد انگاه يك فعاليت وجود خواهد داشت كه بايد قبل از اغاز شدن كامل گردد و واضح است كه اين امرغيرممكن است .
هنگامي كه هيچ تناقضي از اين نوع موجود نباشد پروژه عملي است .
اسلاید 7 :
تعريف
ترتيب موضعي :
يك ترتيب خطي از راس هاي يك گراف است به نحوي كه به ازاي هر دو راس i و j اگر i يك راس تقدمي براي j در شبكه باشد انگاه i در اين ترتيب خطي پيش از j قرار مي گيرد .
الگوريتم ارائه شده براي آزمايش عملي بودن پروژه يك ترتيب خطي از راس ها (فعاليت ها) را به صورت V0,V1,…,Vn-2,Vn-1 توليد مي كند .
اسلاید 8 :
طراحي الگوريتم مرتب سازي موضعي
- در ابتدا راسي كه هيچ راس ديگري در شبكه قبل از ان قرار ندارد را با تمام يال هايي كه از ان خارج مي شود از شبكه حذف مي كنيم . اين مرحله تا زماني ادامه مي يابد كه همه ي راس هاي در شبكه حذف شوند .
1 //Input the AOV network . Let n be the number of vertices .
2 For ( int i=0 ; i<n ; i++ )
3 {
4 if ( every vertex has a predecessor)
5 return ; //network has a cycle and is infeasible .
6 pick a vertex V that has no predecessors ;
7 cout << V ;
8 delete V and all edges leading out of V from the network ;
9 }
اسلاید 9 :
الگوريتمي كامل تر براي مرتب سازي موضعي
اعمال لازم براي اين مسئله :
1- آيا يك راس، راس تقدمي است؟
2- چگونگي حذف يك راس با همه ي يال هاي متصل؟
- تعداد راس هاي ماقبل هر راس را ذخيره مي كنيم .
- پياده سازي با ليست هاي مجاورتي
–حذف همه يال هاي خارج شده از راس v را با كاهش تعداد راس هاي تاخيري بلافاصل راس v در ليست مجاورتي انجام داد .
–وقتي كه تعداد راس هاي تقدمي يك راس برابر با صفر شد راس آماده حذف است.
اسلاید 10 :
: Count[i] شامل درجه ورودي راس i مي باشد .
: HeadNodes[i] يك ليست پيوندي ازاعداد صحيح كه نشان دهنده يال هاي خروجي از راس i مي باشد .
هر گره ليست دو فيلد دارد :
فيلد data (شامل راس)
فيلد link .
وقتي يال < i,j> حذف مي شود تعداد مربوط به راس j يك واحد كاهش مي يابد .
ليست راس هايي كه داراي count (تعداد) صفر هستند در يك پشته نگهداري مي شود .
نحوه ي اتصال به پشته از طريق فيلد count گره هاي head مي باشد زيرا اين فيلد بعد از اين كه تعداد به صفر برسد بلا استفاده خواهد شد .