پاورپوینت کارایی ، تحلیل و مرتبه الگوریتم ها

بخشی از پاورپوینت

اسلاید 1 :

کارایی ، تحلیل و مرتبه الگوریتم ها

درس طراحی الگوریتم ها

اسلاید 2 :

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

اسلاید 3 :

هدف از مطالعه درس طراحی الگوریتم
پرسش های مطرح شده:
آیا الگوریتمی که ارائه می شود درست است یا خیر؟
چگونه الگوریتم های مربوط به یک مسئله مقایسه می شوند؟
کارایی (efficiency) هر الگوریتم چگونه تعیین می شود؟
برای این کار نیاز به تحلیل الگوریتم ها داریم.

اسلاید 4 :

تفاوت دروس طراحی الگوریتم و ساختمان داده ها
مروری بر درس ساختمان داده ها

یادآوری مفاهیم اولیه ریاضیات ( سری ∑، لگاریتم log و . )

اسلاید 5 :

تعریف الگوریتم
دنباله ای از دستورات که با اجرای مرحله به مرحله آنها می توان به نتیجه مورد نظر دست یافت.
خصوصیات هر الگوریتم:
داراي ورودي است.
داراي خروجي است.
داراي ترتيب (توالي) است.
واضح و صريح است. ( بدون ابهام مي باشد).
محدود است.

اسلاید 6 :

تعریف مسئله
مسئله: سؤالی که به دنبال پاسخ آن هستیم.
1. مرتب سازی یک لیست S متشکل از n عدد به ترتیب غیر نزولی. پاسخ دنباله مرتب از n عدد می باشد.

2. تعیین اینکه آیا عدد x در لیست S متشکل از n عدد وجود دارد یا خیر. در صورت وجود پاسخ ”بله“ و در غیر این صورت پاسخ برابر با ”خیر“ خواهد بود.
پارامترهای مسئله

اسلاید 7 :

تعریف نمونه مسئله
مسائلي كه شامل پارامترها هستند بيانگر كلاسي از مسائل مي باشند.
نمونه مسئله: هر انتساب خاصي از مقادير به پارامترها
راه حل يك نمونه مسأله: پاسخ سؤال پرسيده شده توسط مسأله در آن نمونه مسئله
نمونه مسئله 1: n = 6 , S = {8 , 13, 5, 11, 7, 10}
راه حل: {5, 7, 8, 10, 11,13}

اسلاید 8 :

الگوریتم درست/نادرست
چنانچه الگوریتمی بتواند برای هر نمونه از ورودی، خروجی درست را تولید کند و متوقف شود، آن الگوریتم درست (correct) است.
چناچه نرخ خطای الگوریتم های نادرست قابل کنترل باشد می توان از آنها نیز استفاده کرد.

اسلاید 9 :

حل مسئله
حل مسئله فرایندیست شامل 3 بخش:
تعیین پارامترهای مسئله
بیان الگوریتم
پاسخ مسئله

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

اسلاید 10 :

بیان الگوریتم
يك الگوريتم براي مسأله 2 (جستجو):
با شروع از اولین عنصر S به ترتیب x را با هر یک از عناصر S مقایسه کن تا اینکه x را پیدا کنی یا به انتهای لیست برسی. اگر x پیدا شد پاسخ ”بله“ و در غیر این صورت پاسخ ”خیر“ را تولید کن.

معایب نوشتن الگوریتم ها به زبان طبیعی
مشکل بودن نوشتن و درک الگوریتم های پیچیده
مشکل بودن ترجمه آن به یک زبان برنامه نویسی

لذا الگوریتم ها را توسط شبه کدهایی از یک زبان برنامه نویسی بیان می کنیم.

اسلاید 11 :

شبه کد
بیان الگوریتم جستجوی ترتیبی به صورت شبه کد:
در شبه كد هر گاه بتوانيم مراحل را با وضوح بيشتر با استفاده از روابط رياضي و توضيحات انگليسي نشان مي دهيم.
if ( low ≤ x ≤ high ) {
…
{

exchange x and y ;
ساختار كنترلي غير استاندارد:

repeat ( n times) {
…
}

اسلاید 12 :

تمرین در کلاس
توجه: برای هر الگوریتم ورودی و خروجی را تعیین کنید.
الگوریتم جمع عناصر یک آرایه
الگوریتم ضرب ماتریسها
الگوریتم مرتب سازی عناصر به ترتیب غیر نزولی ( exchange sort- مرتب سازی تعویضی)

اسلاید 13 :

پاسخ

اسلاید 14 :

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

اسلاید 15 :

الگوریتم جستجوی ترتیبی
Void seqsearch ( int n, const keytype S[ ], keytype x,
index &location)
{
location = 1;
while (location <= n && S[location] ! = x)
location++;
if (location > n )
location = 0 ;
}

اسلاید 16 :

الگوریتم جستجوی دودویی
Binary search
شرط انجام این جستجو داشتن یک آرایه مرتب است.
تقسیم آرایه به دو نیمه و مقایسه با عنصر میانی

اسلاید 17 :

مقایسه دو الگوریتم[1]
Linear search:
Binary search:
با فرض داشتن آرایه 32 عنصری
32 مقایسه در بدترین حالت

اسلاید 18 :

الگوریتم دنباله فیبوناچی
محاسبه جمله nام فیبوناچی (بازگشتی)
محاسبه جمله nام فیبوناچی (تکراری)
محاسبه n+1 جمله
محاسبه بیش از جمله

اسلاید 19 :

الگوریتم جمله n اُم فیبوناچی (بازگشتی)
با رسم درخت بازگشتی واضح است که این الگوریتم بسیار ناکارآمد می باشد.

اسلاید 20 :

الگوریتم جمله n اُم فیبوناچی (بازگشتی) .
T(n) : تعداد جملات محاسبه شده در درخت بازگشتی
با افزودن 2 واحد به n، تعداد جملات درخت بیش از 2 برابر می شود.
T(n) > 2 × T(n-2)
> 2 × 2 × T(n-4)
> 2 × 2 × 2 × T(n-6)
.
.
> 2 × 2 × 2 × … × 2 ×T(0)

T(n) > 2n/2