پروژه کاربرد الگوریتم ژنتیک درزمانبندی کارهای سیستم های چند پردازنده ای. doc

اختصاصی از زد فایل پروژه کاربرد الگوریتم ژنتیک درزمانبندی کارهای سیستم های چند پردازنده ای. doc دانلود با لینک مستقیم و پر سرعت .

نوع فایل: word

قابل ویرایش 71  صفحه

چکیده:

زمانبندی کارها در سیستم های چند پردازنده ای شامل نگاشت کردن کارهای موجود در یک Task Graph به هریک از پردازنده ها می باشد. یک Task Graph گرافی غیر چرخشی می باشد که هر یک از گره های آن شامل کارهای محاسباتی است که بین گره ها روابط تقدم و تاخر وجود دارد. آنچه که در این زمانبندی مهم است اینکه باید طوری صورت گیرد که مدت زمان اجرای کل کارها مینیمم گردد.

این مسئله که NP (غیرچند جمله ای) است دارای روش های حل مختلفی است که یکی از آنها الگوریتم ژنتیک می باشد.

در این پروژه یکی از روش های چند جمله ای  برای این مسئله ارائه گردیده است که برای پایه نمایش دو کروموزومی می باشد.

این روش با استفاده از یک محیط شبیه سازی پیاده سازی شده و نتایج حاصله قابل مشاهده می باشد.

مقدمه:

مسئله زمانبندی کارها درسیستم های چند پردازنده ای برپایه زمانبندی مجموعه ای از کارها که به صورت جزئی مرتبند بنا نهاده شده است . به زبان ساده زمانبندی به مفهوم تخصیص منابع موجود (مثلا پردازنده ها ) به کارهای محاسباتی است که بین این کارها ویژگی ترتیب جزئی برقرار است یعنی اینکه بین کارها تقدم وتاخر اجرا وجود دارد.

مجموعه Task  هایی که قراراست اجرا گردد برروی یک گراف غیرچرخشی (Direct Acyclic Graph)   بنامTask Graph  قراردارد.

هدف از نگاشت Task های موجود به هریک از پردازنده ها این است که اجرای کلیه Taskها درحداقل زمان ممکن گردد.

مسئله زمانبندی کارها به عنوان یک مسئله انتزاعی بررسی میگردد وزمینه های کاربردی این مسئله می تواند درپردازش موازی و زمانبندی حرکت قطارها وحل مشکل ترافیک شهری وکاربردهایی درخط تولید کارخانجات واقتصاد وتحقیق درعملیات ومواردی دیگرباشد. زمانبندی کارها به عنوان یک مسئله Np-Hard (غیر چندجمله ای )محسوب میگردد ووروش های مختلفی برای به دست آوردن جوابهای  Optimal بکارگرفته شده است.

یکی ازاین روش ها الگوریتم های ژنتیک می باشد که دارای ماهیت تصادفی بوده ومبتنی برمفاهیم ژنتیک بوده و برگرفته ازنظریه تکاملی داروین می باشد. اگوریتم های ژنتیکی باتقلید از مفهوم تکامل تدریجی باایجاد یکسری کروموزوم ها به عنوان اعضای جمعیت واعمال یکسری عملگرها مانند Selection  و Crossover و Mutation و تولید جمعیت جدید به ایجاد نتایج بهینه می پردازد.

دراین پایان نامه الگوریتم ارایه شده دارای ساختارنمایشی دوکروموزومی بوده و به  (Bi-Chromosal Genetic Algorithm)BCGA  معروف است.

البته الگوریتم های ژنتیکی وغیرژنتیکی دیگری برای حل مسئله زمانبندی کارها درسیستم چند پردازنده ای وجود دارد .

فهرست مطالب:

چکیده

1) مقدمه

2) اصول الگوریتم های ژنتیکی                                         

 1-2) تاریخچه  

2-2) صورت کلی الگوریتم های ژنتیکی

3-2) تعاریف مقدماتی الگوریتم های ژنتیکی

5-2) انواع عملگرها

6-2) شرایط توقف الگوریتم های ژنتیکی

7-2) پارامترهای الگوریتم ژنتیکی

3- تعاریف مربوط به مسئله زمان بندی چند پردازنده ای وGraph   Task

4) الگوریتم های ارائه شده برای مسا له زمانبندی کارها

1-4 )الگوریتم های غیرژنتیکی برای حل مسئله

2-4) الگوریتم های ژنتیکی برای حل مسئله

1-2-4) الگوریتم ژنتیکی PGA

2-2-4) الگوریتم ژنتیکی بانمایش رشته ای متغیر

فصل پنجم  الگوریتم ژنتیکی دوکروموزومی (BCGA) برای مسئله زمانبندی

1-5) نمایش کروموزوم ها  (Representation)

3-1-5) نگاشت کردن یک زمان بندی به جفت کروموزوم

 2-5) عملگرهای ژنتیکی به کاررفته درالگوریتم BCGA

3-5) محاسبه تابع Fitness

4-5) شرط خاتمه الگوریتم

5-5) پارامترهای دیگر الگوریتم

 6) نتایج محیط شبیه سازی شده

7) نتیجه گیری و راهکارهای آینده

  منابع

پیوست

منابع و مأخذ:

• X.yao "An Overview of evolutionary computation", Chinese Journal of Advanced Software Research (Allerton Press , INC , New york , 1996)
• A Comparison of General Approaches to Multiprocessor Scheduling - Parallel Processing Symposium, 1997. Proceedings., Ilth International
• Genetic Scheduling for Parallel Processor Systems:

Comparative Studies and

Performance Issues

Albert Y. Zomaya, Senior Member, IEEE, Chris Ward, and Ben Macey

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS, VOL. 10, NO. 8, AUGUST 1999

• yu – Kwong kwak and Ishfaq Ahmad , "Static Scheduling Algorithms for Allocating Directed Task Graphs to Multiprocessor",The university of hong kong And The Hong kong university of Science and Technology

پروژه کلاس بندی مسیر ها روی الگوریتم ((AODV)). doc

اختصاصی از زد فایل پروژه کلاس بندی مسیر ها روی الگوریتم ((AODV)). doc دانلود با لینک مستقیم و پر سرعت .

نوع فایل: word

قابل ویرایش 81 صفحه

مقدمه:

در شبکه های سیار دونوع معماری وجود دارد:شبکه های دارای ساختار(Single-hop) و شبکه های سیار و بدون ساختار (multi-hop) .شبکه های داری ساختار خود نیر از دو نوع می باشند که یکی شبکه های سلولی می باشد ودیگری شبکه های محلی  که کاربران برای ارتباط از یک ایستگاه یا یک کنترل کننده مرکزی استفاده می کنند.در شبکه های سیار نودها می توانند به طور دلخواه و وسیع حرکت کنندکه همین امر باعث شده است که آنهارا شبک های خود مختار نیز معرفی کنند.یکی از مسایل مهم در این شبکه ها اطمینان دریافت بسته (delivery) کارا بدون توپولوزی از قبل تعیین شده یا یک کنترل مرکزی می باشد.هرنود در این شبکه ها هم به عنوان میزبان وهم به عنوان مسیر یاب یا جلو برنده بسته عمل می کند.

الگوریتم های مسیر یابی ری هیبرید یا ترکیبی جزالگوریتم هایی هستند که مطالعات زیادی بر روی این الگوریتم ها شده است.الگوریتم هایی چون Zone Routing Protocol (ZRP) و Zone-Based Hierarchical Link State Protocol(ZHLS) ازاین قبیل می باشند.در این پروتکلها مسیر یابی هم به صورت پرو اکتیو وهم به صورت ری اکتیو انجام می گیرد در هر یک از این ناحیه ها همه نودها رویکرد یکسانی دارند وبه صورت پرو اکتیو عمل می کنند.که استفاده از یک موقعیت سنج در پروتکل (ZHLS) کارایی خاص از لحاظ پهنای باند ایجاد کند.

الگوریتم هابی مسیر یابی کلاستری  مانند الگوریتمهای تقیسم منطقه ای تحقیقات وپیشرفت های چشم گیری داشته است که منجر به نتا یج خوبی شده است.که Cluster-Head Gateway Switch Routing Protocol (CGSR)و Cluster Based Routing Protocol (CBR) استفاده از کلاستر کردن نودها و انتخاب یک کلا ستر – هد و ایجاد جدول های کلاستر های همسایه برای هر نود و دردوازه های ارتباطی بین نودها منجر شده است که کاریی این الگوریتمها در شبکه های سیار موردی بالا باشد.در پرو تکل(CGSR) با استفاده از رویکرد توکنی و استفاده از CDMA برای Allocate Wireless Channels باعث ایجاد یک رویکرد حریصانه شده است که موجب کاهش تاخیر (Delay) شده است.

با این وجود امروزه تحقیقات زیادی روی پروتکل مسیر یابی AODV  انجام گرفته است که به نتایج خوبی رسیده است ولی اکثر این تحقیقات ونتایج بر روی خود مسئله مسیر یابی می باشد که ما در این تحقیق علاوه بر انجام بهترین تلاش برای مسیر یابی  اطمینان پذیری مسیر را بالا برده وترافیک شبکه را کنترل کرده که باعث بهتر شدن تعادل بار بر روی شبکه می شود.وبا ارائه فرمولی بر اساس شکست های لینک ازانتخاب چنین مسیر هایی در طول مسیر یابی اجتناب می کنیم.

فهرست مطالب:

مقدمه

 (1-1)شبکه های موردی

(2-1)انواع شبکه های بی سیم

(1-2-1)شبکه هایInfrastructure  Based

 (2-2-1)روشهای ارتباط بی سیم

)1-2-2-1)شبکه های بی سیم و درون سازمانی(  (  in door

(2-2-2-1)شبکه های بی سیم و بیرون سازمانی ( out door)

)3-1)کلاس بندی الگوریتم های مسیر یابی

(4-1)الگوریتم های پرواکتیو در مقابل ری اکتیو

)5-1)مسیر یابی کلاسترشده وسلسله مراتبی

)6-1)بررسی پروتکل های مسیر یابی پرواکتیو

)1-6-1)الگوریتم مسیر یابی  (DSDV)

  (2-6-1)الگوریتم مسیر یابیThe wireless Routiy

  (3-6-1)الگوریتم مسیریابیGSR))

)7-1)بررسی الگوریتم های مسیر یابی ری اکتیو

(1-7-1)الگوریتم مسیر یابی (AODV)

(2-7-1)الگوریتم مسیر یابی(DSR)

(8-1)الگوریتم مسیر یابیHybrid

(1-8-1)الگوریتم مسیریابی(CBRP)

)2-8-1)الگوریتم مسیر یابی(ZHLS)

فصل دوم

)2-1)درجه بندی نودها

(2-2)پیاده سازی رویکرد جدید بر روی الگوریتم های مسیریابی ری اکتیو(درجه بندی)

)3-2)پیاده سازی رویکرد جدید بر روی الگوریتم مسیر یابی پرواکتیو(درجه بندی)

(4-2)استفاده از شمارنده برای تعادل باردر شبکه

(5-2(پیاده سازی رویکرد جدید بر روی الگوریتم های ری اکتیو)شمارنده)

 (6-2)پیاده سازی رویکرد جدید بر روی الگوریتم های مسیریابی پرواکتیو(شمارنده)

(1-3)اشنایی مقدماتی با ns-2

(1-2-3)طریقه downloadکردن54

(2-2-3)نصب ns

 (3-3)شروع کار با ns

(1-3-3)اجرای ns

)2-3-3)معماری ns

(3-3-3)زبان کاربری OTCL

)4-3)نرم افزارnam

(1-4-3)پیکر بندی nam برای نمایش توپولو ی

(2-4-3)واسط کاربری

(3-4-3)مثالهای عملی

  (4-4-3)فرمانهای اولیهns 2

(1-4-4-3)مشخص کردن جریانهای ترافیک ومونیتور کردن لینک

(2-4-4-3)تعریف منابع ترافیک و گیرنده های ترافیک

(3-4-4-3)مشخص کردن جریانهای ترافیک

(4-4-4-3)مونیتور کردن یک لینک

(1-5-3)پیاده سازی نود های سیار در ns

(6-3)شبیه سازی وارزیابی نتایج شبیه سازی

(1-6-3)- تغییرات انجام گرفته بر روی AODV

(2-6-3)شبیه سازی

(6-3-3)- ارزیابی نتایج شبیه سازی

(7-3)  نتیجه گیری

(8-3)کار های بعدی

فهرست شکل ها:

شکل1-1 ارتباط بین ایستگاهابا نودها در شبکه های دارای ساختار

شکل2-1 شبکه بدون ساختار یازیربنا

شکل 3-1 نحوه مسیر یابی درDSDV

شکل 4-1 نمایش انتشار پیام درخواست مسیر

شکل 5-1 نحو ارسال RREP به مبداء

شکل6-1 ایجاد شکست لینک در شبکه

شکل7-1 مسیر یابی در ِDSR

شکل 8-1 نحوه مسیر یابی در CBR

شکل 9-1 منطقه ای با شعاع 2

شکل10-1 نحوه ارتباط بین پروتکل ها را نشان می دهد

شکل 11-1در سطح نود

شکل 12-1 در سطح ناحیه ای ارتباط بین ناحیه ها

شکل 13-1جدول مسیر در هر نود

شکل 14-1 جدول مسیر یابی بین ناحیه ای

شکل 15-1 مثالی ازمسیر یابی

شکل 1-2-شبکه نمونه

شکل 2-2 – محاسبه درجه مسیر روی نودها

شکل1-3 - شمای کلی ns از دید کاربر

شکل 2-3- ایجاد و فراخوانی روال در tcl

شکل 3-3 - ایجاد شی و استفاده از ارث بری در otcl

شکل 4-3 –ایجاد یک لینک بین دو نود

شکل 5-3 – ترافیک عبوری بر روی لینک

شکل 8-3 –جریانهای ترافیکی

شکل 9-3 – مونیتور کردن لینک

شکل 10-3 – استفاده از صف SFQ

شکل11-3- نحوه محاسبه درجه مسیر

شکل12- 3- کلاسبندی مسیرروی نودکم ترافیک

شکل 13-3 – حالت اولیه از نودهای سیار

شکل 14-3- ترافیک بر روی شبکه سیار

شکل 15-3 –میانگین تعادل باربر روی شبکه

شکل 16-3- میزان بسته های گم شده بر روی شبکه

شکل 17-3 –میزان قابلیت اطمینان

شکل 18-3- میانگین تاخیر بروی شبکه

منابع و مأخذ:

[1] Charalampos Konstantopoulos a, Damianos Gavalas b, Grammati Pantziou cClustering in mobile ad hoc networks through neighborhood stability-based mobility prediction    2008                                         

[2] L. Hanzo (II.) and R. Tafazolli: A Survey of QoS Routing Solutions for Mobile Ad hoc Networks Centre for Communication Systems Research (CCSR) University of Surrey, UK 2006                           

[3] Apoorva Jindal, Member, IEEE, and Konstantinos Psounis, Member, IEEE:Discovering long lifetime routes in mobile ad hoc networks 2009

[4] Y. Ganjali and A. Keshavarzian , “Load Balancing in Ad Hoc Networks: Single path Routing vs. multipath Routing”, Proceedings of the IEEE INFOCOM'04

. Hong Kong

[5] T. Clausen, P. Jacquet, and L. Viennot. Analyzing control tra±c overhead versus mobility and data tra±c activity in mobile ad-hoc network protocols. ACM Wireless Networks journal (Winet), 10(4), july 2004.

[6]Navid Nikaein and Christian Bonnet: A Glance at Quality of Service Models for Mobile Ad Hoc Networks 2007

[7] Krishna Gorantala : Routing Protocols in Mobile Ad-hoc Networks 2007 Master’s Thesis in Computing Science, 10 credits Supervisor at CS-UmU: Thomas Nilsson Examiner: Per Lindstr¨om

[8] Jun Miao, U Teng Wong, and Ji Hui Zhang, “Survey of Multipath Routing Protocols for Wireless Mobile Ad Hoc Networks”, May 2002.

[9] http://wiki.uni.lu/secan-lab/Ad-Hoc+Protocols.htm

[10] R. Dube, C.D. Rais, K.Y Wang, and S.K. Tripathi, “Signal stability-based adaptive routing (SSA) for ad hoc mobile networks”, IEEE PersonalCommunications, Volum e: 4 Issue: 1 , Feb. 1997, pp 36 –45

 [11] C.E. Perkins, E.M. Royer, Ad-hoc on demand distance vector (AODV) routing, in: 2nd IEEE Annual Workshop on Mobile Computing Systems and Applications, 1999, pp. 90– 100.

 [12] S. Basagni, M. Mastrogiovanni, A. Panconesi, C. Petrioli, Localized protocols for ad hoc clustering and backbone formation: A performance comparison, IEEE Transactions on Parallel and Distributed Systems 17 (4) (2006) 292–306.

 [13] Y. Wang, W. Wang, X.-Y. Li, Distributed low-cost backbone formation for wireless ad hoc networks, in: Proceedings of the Sixth ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc 2005), May 2005, pp. 2–13.

[14] A.K. Saha, D.B. Johnson, Modeling mobility for vehicular ad-hoc networks, in: Proc. 1st ACM Workshop on Vehicular Ad Hoc Networks (VANET 2004), 2004, pp. 91–92 (poster paper).

[15] B. Ishibashi, R. Boutaba, Topology and mobility considerations in mobile ad hoc networks, Ad Hoc Networks 3 (6) (2005) 762–776.

الگوریتم تکاملی چند هدفه بر اساس تکامل تفاضلی MODE

اختصاصی از زد فایل الگوریتم تکاملی چند هدفه بر اساس تکامل تفاضلی MODE دانلود با لینک مستقیم و پر سرعت .

دانلود کد متلب الگوریتم تکاملی چند هدفه بر اساس تکامل تفاضلی 

Multi-objective Evolutionary Algorithm based on Differential Evolution

دارای توضیحات و معرفی اولیه تابع

دارای توضیحات به صورت خط به خط برنامه

مناسب برای شبیه سازی پایان نامه های دانشجویان ارشد

علاقه مندان کدنویسی متلب

پروژه کامپیوتر با عنوان الگوریتم های ژنتیک. doc

اختصاصی از زد فایل پروژه کامپیوتر با عنوان الگوریتم های ژنتیک. doc دانلود با لینک مستقیم و پر سرعت .

نوع فایل: word

قابل ویرایش 100 صفحه

مقدمه:

الگوریتمهای ژنتیک بخشی از تحولات رشته کامپیوتر هستند که دارای فضای رشد سریعی در عرصه هوش مصنوعی می باشند. بطوریکه می توان حدس زد، الگوریتمهای ژنتیک از تئوری داروین که در مورد تکامل تدریجی است، الهام گرفته اند. با نگاه دقیق به روند تکامل، یعنی روندی که طبیعت برای حل مسائل خود از آن استفاده می کند، می توان به ایده های جالب و قابل پیاده سازی رسید. جانوران برای ابقاء خود و ادامه حیات مجبور به سازگاری با محیط هستند. اطلاعات گرفته شده درطی هزاران سال از طبیعت در کروموزومها و در سطح پایین تر روی ژن ها و دی ان آ ها ذخیره می گردد. علم کامپیوتر،علمی است که اندیشه آن از زمان تفکر برای اولین ماشین محاسبه گر شروع شد. این علم روز به روز پیشرفت کرد. بطوریکه پیشرفت آن قابل مقایسه با علوم دیگر نیست. این علم تا جائی پیشرغت کرده است که تمامی زندگی روزمره بشررا تحت الشعاع قرار داده است. اعمالی که تا چندین سال پیش با تفکر و حتی نیروی خلاقیت بشر انجام می شد، امروز با استفاده از علم کامپیوتر انجام می گیرد و انجام چنین کارهایی توسط بشر کاری بیهوده و وقت گیر می باشد. علوم کامپیوتر تنها به پیشرفت در محدوده خود قانع نبوده و متخصصین این علم از علوم دیگری همچون ریاضی و زیست شناسی برای پیشرفت و بهبود آن استفاده می کنند. در این زمینه مکانیزم تکامل انسان و ارث بری خصوصیات از کروموزومها از طریق عملگرهای ژنتیکی توجه متخصصین علم کامپیوتر را به خود جلب کرده است، به گونه ای که آنها برای حل مسائلی که با روشهای معمولی پیدا کردن راه حلهای مناسب برای آنها سخت می باشد این دو علم را با هم ترکیب می کنند. الگوریتمهای ژنتیک بخشی از تحولات رشته کامپیوتر هستند که دارای فضای رشد سریعی در عرصه هوش مصنوعی می باشند. بطوریکه می توان حدس زد، الگوریتمهای ژنتیک از تئوری داروین که در مورد تکامل تدریجی است، الهام گرفته اند. با نگاه دقیق به روند تکامل، یعنی روندی که طبیعت برای حل مسائل خود از آن استفاده می کند، می توان به ایده های جالب و قابل پیاده سازی رسید. جانوران برای ابقاء خود و ادامه حیات مجبور به سازگاری با محیط هستند. اطلاعات گرفته شده درطی هزاران سال از طبیعت در کروموزومها ودر سطح پایین تر روی ژن ها و دی ان آ ها ذخیره می گردد.

فهرست مطالب:

7) سیستم های رده بندی کننده ی یادگیری

7-1)اهداف این فصل

7-2)مثال مقدماتی

7-3)زمینه ی کلی

7-4)ZCS : سیستم رده بندی کننده ی سطح صفر

7-5)XCS

7-5-1)انگیزه

7-5-2)شرح

7-6)تعمیم ها

7-7)مثال های کاربردی

7-7-1)مدل سازی تاجرهای بازار مالی

7-7-2)مسئله ی چندمرحله ای

8) کنترل پارامتر در الگوریتم های تکاملی15

8-1)اهداف این فصل

8-2)مقدمه

8-3)مثال هایی از تغییر پارامترها

8-3-1)تغییر سایز گام جهش

8-3-2)تغییر ضرایب پنالتی

8-3-3)خلاصه

8-4)طبقه بندی تکنیک های کنترل

8-4-1)چه چیزی تغییر می یابد؟

8-4-2)چگونه تغییرات بوجود می آیند؟

8-4-3)تغییر براساس کدام شواهد صورت می گیرد؟

8-4-4)حوزه ی تغییر چه چیزی می باشد؟

8-4-5)خلاصه

8-5)مثال هایی از تغییر پارامترهای EA

8-5-1)نمایش

8-5-2)تابع ارزیابی

8-5-3)جهش

8-5-4)ترکیب

8-5-5)انتخاب

8-5-6)جمعیت

8-5-7)تغییر همزمان پارامترهای متعدد

8-6)بحث

9) مسائل چندوجهی و توزیع خاص35

9-1)اهداف این فصل

9-2)مقدمه: مسائل چندوجهی و نیاز برای پراکندگی

9-2-1)مسائل چند وجهی

9-2-2)راندگی ژنتیک

9-2-3)محرک های بیولوژیکی و روش های الگوریتمی

9-2-4)فضای الگوریتمیک در مقابل فضای ژنتیک در مقابل فضای راه حل

9-2-5)خلاصه

9-3)اندازه گیری های ضمنی

9-3-1)چندین جمعیت پشت سرهم : EA های مدل جزیره

9-3-2)توزیع خاص درون یک جمعیت : EA های مدل انتشار

9-3-3)گونه های اتوماتیک با استفاده از محدودیت های جفت گیری

9-4)حفاظت از تنوع صریح

9-4-1)به اشتراک گذاری برازندگی

9-4-2)ازدحام (انبوهی)

9-5)الگوریتم های تکاملی چندمنظوره

9-5-1)مسائل بهینه سازی چند منظوره

9-5-2)تسلط و بهینه سازی پاراتو (Pareto)

9-5-3)راهکارهای EA برای بهینه سازی چند منظوره

9-6)مثال کاربردی: هم تکاملی توزیع شده ی زمانبندی های تولید کارگاهی

10) هیبریداسیون (پیوندزنی) با دیگر تکنیک ها : الگوریتم های ممتیک52

10-1)اهداف این فصل

10-2)تحرکی برای هیبریداسیون EA ها

10-3)مقدمه ی مختصری بر جستجوی محلی

10-3-1)اثر لامارک و بالدوین

10-4)ساختار الگوریتم ممتیک

10-4-1)مقداردهی اولیه ی هیوریستیک یا هوشمند

10-4-2)ترکیب در عملگرهای تغییر : ترکیب و جهش هوشمند

10-4-3)اجرای جستجوی محلی روی نتیجه ی حاصل از عملگرهای تغییر

10-4-4)هیبریداسیون در طول نگاشت ژنوتایپ به فنوتایپ

10-5)مباحث طراحی برای الگوریتم های ممتیک

10-5-1)حفظ تنوع

10-5-2)انتخاب عملگرها

10-5-3)استفاده از دانش

10-6)مثال کاربردی: برنامه ی زمانی چند مرحله ای ممتیک

11) نظریه66

11-1)اهداف این فصل

11-2)رقابت چندسطحی ها در فضاهای باینری: قضیه الگو

11-2-1)الگو چیست ؟

11-2-2)فرمول Holland برای SGA

11-2-3)تحلیل مبتنی بر الگوهای عملگرهای تغییر

11-2-4)تحلیل و حقه ی والش

11-2-5)انتقادها و گسترش های اخیر قضیه ی الگوها

11-2-6)پیوند ژنی : شناسایی و بازترکیب بلوک های سازنده

11-3)سیستم های پویا

11-4)تحلیل زنجیره مارکوف

11-5)روش های مکانیک آماری

11-6)روش های کاهش گرایی

11-7)تحلیل EA ها در فضاهای جستجوی پیوسته

11-8)قضیه های NO FREE LUNCH

12) کنترل محدودیت78

12-1)اهداف این فصل

12-2)مسائل محدود شده

12-2-1)مسائل بهینه سازی آزاد

12-2-2)مسائل مطلوبیت محدود

12-2-3)مسئله های بهینه سازی محدود شده

12-3)دو نوع مهم کنترل محدودیت

12-4)روش هایی برای کنترل محدودیت های موجود در EA ها

12-4-1)توابع پنالتی

12-4-2)توابع تعمیر

12-4-3)محدودسازی جستجو به منطقه ی امکان پذیر

12-4-4)توابع کدگشا

12-5)مثال کاربردی : گراف رنگ آمیزی با سه رنگ

12-5-1)روش غیرمستقیم

12-5-2)نگاشت ترکیبی – روش مستقیم

دانلود پروژه ارائه یک الگوریتم خوشه بندی برای توزیع مناسب کار و ارزیابی کارایی آن

اختصاصی از زد فایل دانلود پروژه ارائه یک الگوریتم خوشه بندی برای توزیع مناسب کار و ارزیابی کارایی آن دانلود با لینک مستقیم و پر سرعت .

با توجه به تحولات اخیر در تکنولوژی ارتباطات و نیاز روز افزون به توان پردازشی زیاد ، امروزه تصور مجموعه ای از کامپیوتر ها که به صورت یک کامپیوتر یکپارچه ،اما با قدرت بسیار بیشتر در حال کار هستند چندان بعید نیست. یک برنامه توزیع شده  می تواند به صورت مجموعه ای از پردازه های در حال اجرا که با تبادل پیام از طریق شبکه ارتباطی با یکدیگر همکاری می کنند تعریف شود.

 با این حال همواره بعنوان یک اصل، ساخت یک برنامه توزیع شده مشکلتر از برنامه متمرکز است. از جمله عواملی که باعث افزایش این پیچیدگی میشود مواجه شدن با برنامه نویسی تحت شبکه، همگام سازی پردازه ها، حل مساله انحصار متقابل بین آنها، افزایش تحمل پذیری خطا و اشکال زدایی میباشد. یکی از روش های مورد توجه در ساخت سیستم های توزیع شده، تبدیل اتوماتیک برنامه های ترتیبی به برنامه های توزیع شده است.

   در این پایان نامه روشی جدید برای توزیع اتوماتیک برنامه های ترتیبی با خوشه بندی کلاس های آن صورت می گیرد.تکنیک های خوشه بندی متنوعی تا کنون برای این منظور استفاده شده است که پس از بررسی مزایا و معایب هر یک روش جدیدی برای خوشه بندی معرفی شده است. پس از خوشه بندی معماری طوری بازسازی میشود که حداکثر همروندی در اجرای قطعات توزیع شده ایجاد شود لذا در این پروژه روشی برای بازسازی معماری سیستم های توزیعی علمی با ایجاد حداکثر همروندی در اجرای کد برنامه ها ارائه خواهد شد.         

واژه‌های کلیدی

خوشه بندی ، چسبندگی ، توزیع شده گی

  در سال های اخیر صنعت کامپیوتر رشد بسیار شگفت انگیزی داشته است. در طی دو دهه اخیر سرعت کامپیوتر های شخصی از چند دستور در ثانیه به چند میلیون دستور در ثانیه رسیده است در صورتی که قیمت آنها نیز از چند میلیون دلار به چند هزار دلار کاهش یافته است.

  افزایش نیاز به  سیستم هایی با کارائی بسیار زیاد و سرعت فوق العاده بالای شبکه ها (شبکه های ترابیتی)  سبب جلب علاقه محققان به پردازش های موازی و توزیع شده، شده است. از جمله دلایل افزایش توجه به سیستم های توزیع شده می توان به موارد زیر اشاره کرد:

1: پیشرفت تکنولوژی پردازش.

2: سرعت بالای شبکه ها.

3: انجام تحقیقات گسترده برای ارائه محیطهائی برای انجام محاسباتی توزیع شده.

  بعلاوه به نظر می رسد با افزایش  روزافزون نیاز به توان پردازشی سریعتر، هیچ بستر محاسباتی منفرد،  نمی تواند پاسخگوی این نیاز باشد بنابراین محیطهای پردازشی آتی باید بتواننداز منابع محاسباتی نا همگن موجود در شبکه استفاده کنند. فقط سیستم های موازی و توزیع شده امکان استفاده از  منابع مختلف موجود در شبکه را میسر می کنند.

 از سوی دیگر تحول چشم گیری نیز در صنعت شبکه های کامپیوتری به وجود آمده است. امروزه هزاران کامپیوتر می توانند از طریق یک شبکه LAN به یکدیگر متصل شده و در کسری از ثانیه داده های خود را با یکدیگر مبادله کنند. یا به کمک یک شبکه WAN میلیون ها کامپیوتر از سرتاسر دنیا  قادر به تبادل داده با یکدیگر هستند.با توجه به این تحولات، امروزه تصور مجموعه ای از کامپیوتر ها که به صورت یک کامپیوتر یکپارچه  اما با قدرت بسیار بیشتر ،چندان بعید نیست.

1-1. سیستم های توزیع شده

در حالت کلی تعریف زیر را می توان برای یک سیستم توزیع شده ارائه کرد:

  یک سیستم توزیع شده مجموعه ای از کامپیوتر های مستقل می باشند که برای انجام کارهای مختلف با یکدیگر همکاری کرده و به صورت یک سیستم واحد و قدرتمند برای کاربران دیده می شوند.

• مزایا و معایب سیستم های توزیع شده

  سیستم های کامپیوتری توزیع شده به وسیله پژوهشگران به طور گسترده مطالعه شده و مزایای زیادی در رابطه با آن گزارش شده است. به عنوان مثال پیشرفت های اخیر در تکنولوژی  شبکه ها و پردازه ها، دستیابی به مزایای زیر را امکان پذیر ساخته است :

1. افزایش کارایی: وجود چندین کامپیوتر در یک سیستم توزیع شده به برنامه کاربردی امکان پردازش و اجرا به صورت موازی را می دهد بنابراین سرعت اجرای برنامه کاربردی و کارایی سیستم افزایش می یابد برای مثال کارایی یک سیستم فایل می تواند به وسیله تکرار توابع آن بر روی چندین کامپیوتر بیشتر شود. تکرار سیستم فایل باعث می شود چندین برنامه کاربردی به سیستم فایل به صورت موازی دسترسی داشته باشند بعلاوه تکرار فایل ها ترافیک شبکه را بین سایت های مختلف توزیع کرده و تاخیر ناشی از صف بندی را کاهش می دهد.
2. به اشتراک گذاری منابع: به اشتراک گذاری منابع مقرون به صرفه بودن و امکان دسترسی کارا به منابع سیستم را فراهم میکند یعنی کاربران در عرض چند دقیقه می توانند منابع سخت افزاری و نرم افزاری گران و خاص منظوره را مانند سرورهای پایگاه داده ها، سرورهای پردازش، سرورهای پرینترو... را به اشتراک بگذارند.
3. افزایش توسعه پذیری: سیستم های توزیع شده می توانند به صورت سازگار با محیط طراحی شوند مثلا برای یک محاسبه سنگین، سیستم خود را به گونه ای سازمان دهی می کند که شامل تعداد زیادی از کامپیوترها و منابع باشد در صورتیکه برای پردازشهای کوچکتر فقط از چند منبع استفاده خواهد کرد بعلاوه در صورت لزوم محدودیتهائی مانند ظرفیت سیستم فایل و قدرت محاسبتی سیستم را می توان به سادگی با اضافه کردن کامپیوترها یا سرورهای بیشتر افزایش یابد.
4. افزایش قابلیت اطمینان، دسترسی راحت و تحمل پذیری خطا: وجود چندین منبع ذخیره سازی و محاسباتی در یک سیستم، ساخت سیستم توزیع شدۀ تحمل پذیر خطا را مقرون به صرفه و جالب می کند.

سیستم می تواند خرابی یک کامپیوتر را به وسیله تخصیص  وظایف آن به کامپیوتر دیگر تحمل کند بعلاوه سیستم می تواند به وسیله تکرار توابع یا منابع، در کامپیوتر های مختلف،  خطر از دست دادن آنها  را برطرف کند.

1. مقرون به صرفه گی: کارایی کامپیوترها تقریباً هر دو سال یک بار دو برابر شده، در صورتیکه قیمت آنها در دهه اخیر تقریبا در هر سال نصف شده است بعلاوه شبکه هایی با سرعت بسیار زیاد نیز به وجود آمده است که ساخت سیستم های توزیع شده را نسبت به سیستم های موازی بر اساس نرخ قیمت به کارایی مقرون به صرفه تر کرده است.

البته این پیشرفت ها به آسانی به دست نمی آید زیرا طراحی یک سیستم توزیع شده همه منظوره بسیار مشکلتر از طراحی یک سیستم متمرکز است. در طراحی یک سیستم توزیع شد چند منظوره تعداد زیادی از گزینه ها و مسائل باید در نظر گرفته شوند که پیکر بندی فیزیکی سیستم ،خصوصیات بستر محاسباتی، شبکه ارتباطی، زمان بندی وظایف، سیاست های تخصیص منابع و مکانیزم کنترل آن ها، ایجاد سازگاری و کنترل همروندی و امنیت، نمونه هایی از آنهاست. این مشکلات را می توان  ناشی از عدم بلوغ سیستم های توزیع شده، ناهماهنگی و رفتار مستقل کامپیوترها، پراکندگی جغرافیایی منابع سیستم و... دانست. این مشکلات در  زیر خلاصه شده اند:

1. فهم کامل تئوری محاسبات توزیع شده هنوز صورت نگرفته است. این موضوع نسبتاً جدید بوده و ما، قبل از اینکه به تئوری طراحی چنین سیستم های پردازشی تسلط پیدا کنیم باید تعداد زیادی سیستم توزیع شده معتبر با اهداف معمول و معماری های متفاوت را طراحی و آزمایش کنیم.
2. رفتار ناهماهنگ و مستقل منابع سیستم یا اجزای آن، کنترل نرم افزار را پیچیده می کند در حالیکه این امر در یک سیستم متمرکز محاسباتی کار ساده ای است. اگر کامپیوترها به صورت مشتری-خدمتگذار سازماندهی شوند، کنترل نرم افزار ساده تر و رفتار آن قابل پیش بینی تر خواهد بود با این حال این ساختار با یکی از مشخصات سیستم های توزیع شده که همان مستقل بودن کامپیوترها و اجرای آسنکرونن می باشد در تناقض است.
3. استفاده از شبکه های ارتباطی برای اتصال کامپیوترها به یکدیگر مرحله دیگری از پیچیده گی را معرفی می کند. طراحان سیستم توزیع شده نه تنها باید در طراحی سیستم های کامپیوتری و سیستم های نرم افزاری و سرویس ها ماهر باشد بلکه در طراحی شبکه ارتباطی مطمئن، ایجاد همزمانی ، سازگاری و برطرف کردن خطاها در یک سیستم پیچیده از کامپیوترهای ناهمگن و پراکنده از نظر جغرافیایی نیز تسلط داشته باشند. تعداد منابع استفاده شده در چنین سیستمهائی می تواند دهها، صدها و یا حتی هزاران منبع محاسباتی و ذخیره سازی باشد.

 یک سیستم توزیع شده حداقل بایداهداف زیر را برآورده کند:      1- به سادگی منابع موجود در شبکه را در اختیار کاربران قرار دهد.

2- کاربران نباید از این موضوع که منبع مورد استفاده آنها در کامپیوتر دیگری در شبکه قرار دارد مطلع شوند.(شفافیت)  

 3- سیستم توزیع شده باید باز باشد.

4- سیستم توزیع شده باید مقیاس پذیر باشد. 

شفافیت می تواند در جنبه های مختلف سیستم های توزیع شده مطرح شود.

• دستیابی: پنهان سازی تفاوت در ذخیره سازی داده ها و نحوه دسترسی به یک منبع
• محل : پنهان سازی مکان واقعی منابع در شبکه
• مهاجرت: پنهان سازی تغییر محل منابع یعنی در صورت تغییر محل منبع، کاربران از این امر مطلع نگردند.
• تجدید محل: پنهان سازی مهاجرت یک منبع در حال استفاده، از کاربر آن.
• تکرار: پنهان سازی تکرار منابع به گونه ای که کاربران از این امر مطلع نگردند.
• همروندی: پنهان سازی استفاده اشتراکی از یک منبع بین چند کابر. به گونه ای که کاربران احساس می کنند تنها استفاده کننده منبع می باشند.
• خطا: پنهان سازی بروز خطا در یک منبع و برطرف سازی آن از دید کاربران. به عبارتی کاربران از بروز خطا در قسمتی از سیستم و برطرف سازی آن آگاه نمی شوند.
• یکی از اهداف دیگر سیستم های توریع شده مخفی کردن این واقعیت از دید کاربران است که منابع مورد استفاده آنها در بین کامپیوتر های مختلف توزیع شده است. سیستمی که بتواند این مخفی سازی را به خوبی انجام دهد شفافیت گفته می شود.

مسائل مربوط به مقیاس پذیری نیز تا حد زیادی به میزان مولفه های متمرکز سیستم بستگی دارد. هر چه این میزان زیاد باشد مقیاس پذیر کردن سیستم مشکل تر خواهد بود.

با وجود این مشکلات موفقیت های محدودی در طراحی سیستم های توزیع شده با اهداف خاص مانند سیستم های بانکداری، سیستم حمل و نقل و انبارداری توزیع شده  به دست آمده است. با این حال طراحی یک سیستم توزیع شده  مطمئن همه منظوره که هم مزایای سیستم های متمرکز (استفاده و  مدیریت ساده ویکپارچگی) و هم مزایای سیستم های شبکه ای (وجود ارتباطات،توسعه پذیری ، قیمت وکارائی) را دارد هنوز هم یک کار چالش انگیز است.

• انگیزش

      ایده شی گرایی از محبوب ترین روش های تولید نرم افزار است,که برای طراحی، توصیف و پیاده سازی سیستم های توزیع شده نیز بسیار سودمند است.[11] مزیت این روش برای ساخت سیستم های توزیع شده این است که میتوان کدهای برنامه را در اشیا کپسوله کرده و سپس اشیا را به ماژول های مستقلی دسته بندی کرد و هر ماژول را بر روی یک منبع محاسباتی مجزا مستقر نمود. با این حال به عنوان یک اصل [8]تولید یک برنامه توزیع شده، همواره سخت تر از ایجاد یک برنامه غیر توزیع شده است, که عملکردی معادل آن را دارد. به طوری که ساخت یک سیستم توزیع شده میتواند به یک کار خسته کننده  و مملو از خطا تبدیل شود.[4] با وجود اینکه امروزه  ابزار ها و تکنیک های بسیار مفیدی مانند[29] RPC ،[15] CORBA و[8] DCOM جهت ساخت سیستم های توزیع شده با کارایی بالا ارائه گشته اند، اما در حالت کلی فرایند ساخت یک سیستم توزیع شده از بدو پیدایش سیستم های توزیع شده تغیر اندکی کرده است : برنامه نویس برنامه را به ماژول های مختلفی تقسیم کرده، هر ماژول را به صورت مجزا پیاده سازی کرده و امکان برقراری ارتباط بین آنها را ایجاد می کند و در نهایت هر ماژول را  در یک کامپیوتر مستقل در شبکه مستقر میکند. برخی از چالش هایی که در رابطه با ساخت سیستم های توزیع شده پیش روی یک برنامه نویس یا طراح نرم افزار می تواند قرار گیرد عبارت اند از:

• پیچیدگی طراحی و پیاده سازی سیستم های توزیع شده.
• پیدایش نوع جدیدی از خطاها مانند خطاهای ناشی ازهمروندی و همگام سازی پردازه ها.
• مشکلات ناشی از سازگاری داده ها در کل سیستم.
• موازنه کار  بارگذاری شده در منابع موجود در سیستم.

      لذا اتوماتیک سازی فرایند تبدیل یک برنامه ترتیبی به یک برنامه قابل اجرا برروی یک محیط محاسباتی توزیع شده همواره به عنوان یک مساله باز تحقیقاتی مطرح بوده است. امروزه شبکه‌های کامپیوتری به واسطه پیشرفت تکنولوژی ارتباطات  توانسته‌اند جایگزین کامپیوترهای گران قیمت موازی­­گردند[1].

هنگام طراحی برنامه های توزیع شده برای مسائل کاربردی، اغلب الگوریتم ها به مجموعه ای از کارهای کلاسیک، و تکراری  تجزیه می شوند. از جمله کارهای بنیادی که در اغلب الگوریتم ها دیده می شوند می توان به انتشار[1] اطلاعات به تمام گره ها،ارسال پیام به برخی از گره ها[2]، سنکرون سازی عمومی تمام پردازه ها، شروع اجرای برخی رویداد ها، ضمن اجرای پردازه ها، یا انجام محاسبه ای که داده های مورد نیاز آن بین گره های مختلف توزیع شده، اشاره کرد. این عملیات ها معمولا با تبادل پیام بین پردازه ها انجام می گیرند.با طراحی زیر ساختی که بتواند این primitive ها را در اختیار برنامه های ترتیبی قرار دهد می توان نسخه توزیع شده ای از یک برنامه ترتِبی تولید کرد.

یکی از چالشهای مطرح در توزیع کد، میزان تسریع حاصل از توزیع می‌باشد[4] برنامه های علمی نیاز به کامپیوترهایی با توان محاسباتی بالا دارند. این نوع کامپیوترها معمولا بسیار گران قیمت میباشند. امروزه سعی برآن است تا بجای استفاده از سوپرکامپیوترها از شبکه ای با کامپیوترهای ارزان قیمت برای حل مسائل علمی استفاده شود. هدف ما توزیع کد برنامه ها جهت حصول حداکثر میزان همروندی در اجرای کد است در صورت موفقیت مسلما زمان اجرایی به حداقل ممکن کاهش خواهد یافت.

محاسبه زمان اجرای یک برنامه بصورت دقیق امکان ندارد، چون برحسب مسیرهای اجرایی[3] متفاوت در یک برنامه، زمان اجرای آن متفاوت خواهد بود. بیشترین و کمترین زمان اجرای یک برنامه، به طولانی‌ترین و کوتاهترین مسیر اجرایی برنامه از لحاظ زمانی بستگی خواهد داشت. هدف از یافتن اطلاعات مسیرهای اجرایی یک برنامه، تخمین زمان اجرای آن است.

  همانطور که بیان شد توزیع کد با هدف افزایش سرعت پردازش صورت می‌گیرد. بنابراین انتظار می‌رود کد توزیع شده نسبت به قبل سریعتر اجرا­ گردد. نکته قابل تامل این است که آیا توزیع صورت گرفته باعث تسریع شده است؟ میزان تسریع (تقویت توزیع) چقدر است؟ برای پاسخ به این سوالات باید مشخص گردد مدت زما ن اجرای برنامه، قبل و بعد از توزیع به چه میزان بوده است.

به هنگام توزیع، بخشی از برنامه در ایستگاه کاری راه دور اجرا می‌گردد. برای محاسبه زمانِ اجرای برنامه ترتیبی توزیع شده، باید مدت زمانیکه طول می کشد تا افراز[4] احضار شده در ایستگاه کاری راه‌دور اجرا گردد و مدت زمان سپری شده بین دستور احضار[5] تا اولین استفاده از نتیجه این احضار، تخمین زده شود و بر اساس مدت زمان احضار و ارسال نتایج، زمان اجرای توزیع شده محاسبه گردد. بعنوان مثال در مرجع [4] میزان تسریع توزیع محاسبه شده است. این عامل بر اساس زمان محاسبه شده  دو ایستگاه کاری بر روی لبه اتصال دهنده آنها، مشخص می شود.

1-3-  مراحل کلی تبدیل برنامه ترتیبی به برنامه توزیع شده

در حالت کلی برای تبدیل  یک برنامه ترتیبی به یک برنامه توزیع شده مراحل زیر پیموده می شود  

فهرست مطالب:

مقدمه ..........................................................  1

• فصل اول - مفاهیم اولیه .................................................. 2

   1-1. سیستم های توزیع شده ......................................................................................  3

      1-1-1. مزایا و معایب سیستم های توزیع شده..................................................   3

   1-2. انگیزش  ...............................................    6    

1-3. مراحل کلی تبدیل برنامه ترتیبی به برنامه توزیع شده ............................................    8    

1-4. ساختار پروژه..........................................................................     9

   1-5. جمع بندی .......................................................................    10

• فصل دوم - تکنیک ها و ابزارهای مرتبط ............................................................ 11

   2-1.ابزارهای تبادل پیام در مقایسه با حافظه اشتراکی توزیع شده.....................................................    13

2-1-1. تبادل پیام ....................................................................................................................    13

        2-1-2. خصوصیات مطلوب یک سیستم تبادل پیام..............................................................   14

 2-1-3. طبقه بندی ابزارهای تبادل پیام.......................................................................................     14

    2-2. توزیعگر های اتوماتیک ..............................................................................................        17

 2-2-1. ابزار های نیمه اتوماتیک ..............................................................................................................     17 

 2-2-2. ابزار های تمام اتوماتیک .............................................................................................................     18

        2-2-3. توزیع بایت­ کد جاوا بر مبنای تحلیل­ وابستگی به صورت اتوماتیک ..............................................     21  

2-4. مطابقت اندازه گره در محیط برنامه نویسی شی­گرا به صورت پویا توسط روش اسکوپ .........................     24  

2-5.افرازبندی در سیستم توزیع شده شی گرا به صورت پویا .........................................................................     25

      2-5-1. معیارهای دسته بندی اشیاء .....................................................................................     26

      2-5-2. الگوریتم خوشه بندی مشتق شده از الگوریتم حریصانه lo,s  ...............................

       2-5-3. دسته بندی اشیاء موجود در خوشه ها .............................................................     29

    2-6. نتیجه گیری .................................................................................................................  30

3- فصل سوم - استخراج گراف فراخوانی ..........................................................................  31

2-ساخت گراف فراخوانی   

3-1. ساخت گراف جریان فراخوانی ............................................................................................................  32

3-2-1.   الگوریتم های  تعین مقصد فراخوانی ..................................................................................  34

3-2-2.  روش آنالیز نوع ایستاتیک .................................................................................................  34

روش آنالیز سلسله مراتب کلاس ...........................................................................................................     35

3-2-3.  روش آنالیز نوع سریع ........................................................................................................37

3-2-4. روش آنالیز نوع سریع حساس به جریان برنامه ....................................................................37

3-2. استخراج گراف فراخوانی جهت ساخت گراف کلاسها ...................................................................41

3-3.  مقایسه روش های ساخت گراف فراخوانی .........................................................................................  43

3-4.  وزن گذاری گراف فراخوانی ............................................................................................................  45

• استراتژی وزن گذاری یال های گراف فراخوانی توابع ......................................................................  46
• برآورد زمان اجرای کد های ترتیبی .................................................................................................  50
  • روش های برآورد زمان اجرای کد های ترتیبی ......................................................................  51
  • برآورد زمان اجرای کدهای برنامه باآنالیز متن برنامه................................................................  51
  • تعیین سرحد تکرار حلقه­ها و فراخوانی­های بازگشتی ............................................................... 57
  • حذف مسیرهای اجرا نشدنی ..................................................................................................  57
  • بهینه سازی کامپایلرها و تخمین زمان اجرای برنامه ..................................................................  57
  • نحوه شناسایی حلقه های تکرار ................................................................................... 65
  • تشخیص حلقه های تکرار ................................................................................................. 71
  • تخمین تعداد تکرار حلقه ها .............................................................................................. 71
  • انتشار مقادیر .................................................................................................................... 71
• یافتن نقاط همگام سازی ................................................................................................................. 73
• بررسی نتیجه الگوریتم پیشنهادی برروی یک برنامه نمونه................................................................. 76
• جمع بندی ......................................................................................................... 80

3-7-3.   تخمین ایستای زمان اجرای برنامه ها ...................................................................

.           زبان های برنامه سازی و تخمین زمان اجرا .......................................................  58

3-8.           رعایت میزان دقت تخمین در زمان اجرا ...................................................................... 58

3-9.           معیارهای موجود در تخمین طولانی ترین زمان اجرا .......................................................................... 59

3-10-1.            تحلیل جریان داده ................................................................................. 59

3-10-2.            تحلیل کاهش بازگشتی .......................................................................................... 61

3-10-3.            حجم زیاد اطلاعات ......................................................................................... 62

3-10-4.            استفاده از کد Object برنامه ............................................................................ 63

3-10.  بایت کد جاوا و محاسبه زمان اجرای دستورالعملها ........................................................................... 63

3-11. محاسبه زمان اجرای حلقه ها ........................................................................... 64

12.  انتشار دامنه مقادیر ........................................................................................... 67

3-13.  دستورات شرطی و نحوه شناسایی آنها ........................................................ 68

3-14. محاسبه زمان اجرای کل برنامه با استفاده از روش پیشنهادی   .................................. 70

15-4.  محاسبه زمان اجرای توابع موجود در یک دور از گراف...................................................  71

• فصل چهارم - خوشه بندی ............................................................................................. 81
  • خوشه بندی سلسله مراتبی ............................................................................................... 82
  • خوشه بندی سلسله مراتبی پایین به بالا (تلفیق) .................................................................... 85
  • روش های ادغام خوشه ها در خوشه بندی پایین به بالا .......................................................... 88
    • Single Linkage..................................................................................
    • Simple Average Linkage .................................................................................
    • Weighted Average Linkage .......................................................................
    • سه روش مفید دیگر (Median, Centroid, Wards ) ............................................
  • تکنیک های یافتن تعداد خوشه های بهینه ..................................................................................... 94
    • جدول تلفیق (جدول ادغام) ........................................................................................... 94
    • تراز تلفیق .......................................................................................................... 96
    • نمودار dendrogram ..............................................................................................
    • تعیین تعداد خوشه های بهینه ................................................................................... 98
  • تکنیک های پیدا کردن نقطه پیچش در نمودار جدول تلفیق......................................................... 100
  • روش پیشنهادی در این پایان نامه جهت خوشه بندی .................................................................. 103
    • الگوریتم پیشنهادی برای خوشه بندی کلاس ها ............................................................ 103
  • جمع بندی ..................................................................................................................... 106
  • محیط پیاده سازی شده .................................................................................................... 109
  • مقایسة روش خوشه بندی پیشنهادی با روش حریصانه متداول.................................................... 111

          مقدمه ................................................................................................................................... 

            Complete Linkage ...................................................................................................

             Group Average Linkage ............................................................................             

فصل پنجم - پیاده سازی و ارزیــابــی ......................................................................................             

فصل ششم - نتیجـه‌گیـری .......................................................................................................         

نتیجه گیری ...........................................................................................................................        

کارهای آتی .......... .............................................................................................................

منابع و مراجع .......................................................................................................................................

شامل 125 صفحه فایل WORD قابل ویرایش