دانلود پاورپوینت با موضوع خلاصه کتاب طراحی الگوریتمها مترجم جعفر نژاد قمی،
درقالب ppt و در 250 اسلاید، قابل ویرایش.
بخشی از متن پاورپوینت:
فصل اول: کارایی ، تحلیل و مرتبه الگوریتم ها
این کتاب در باره تکنیک های مربوط به حل مسائل است.
تکنیک ، روش مورد استفاده در حل مسائل است.
مسئله ، پرسشی است که به دنبال پاسخ آن هستیم.
بکار بردن تکنیک منجر به روشی گام به گام (الگوریتم ) در حل یک مسئله می شود.
منظورازسریع بودن یک الگوریتم، یعنی تحلیل آن از لحاظ زمان و حافظه.
نوشتن الگوریتم به زبان فارسی دو ایراد دارد:
1- نوشتن الگوریتم های پیچیده به این شیوه دشوار است.
2- مشخص نیست از توصیف فارسی الگوریتم چگونه
می توان یک برنامه کامپیوتری ایجاد کرد.
3-1 تحلیل الگوریتم ها
برای تعیین میزان کارایی یک الگوریتم را باید تحلیل کرد.
1-3-1 تحلیل پیچیدگی زمانی
تحلیل پیچیدگی زمانی یک الگوریتم ، تعیین تعداد دفعاتی است که عمل اصلی به ازای هر مقدار از ورودی انجام می شود.
T(n) را پیچیدگی زمانی الگوریتم در حالت معمول می گویند.
W(n) را تحلیل پیچیدگی زمانی در بدترین حالت
می نامند.
A(n) را پیچیدگی زمانی در حالت میانگین
می گویند.
تحلیل پیچیدگی زمانی برای حالت معمول برای الگوریتم(جمع کردن عناصرآرایه)
عمل اصلی: افزودن یک عنصر از آرایه به sum.
اندازه ورودی: n، تعداد عناصر آرایه.
T(n) = n
تحلیل پیچیدگی زمانی برای حالت معمول برای الگوریتم(مرتب سازی تعویضی)
عمل اصلی: مقایسه S [j] با S[i] .
اندازه ورودی: تعداد عناصری که باید مرتب شوند.
1مرتبه الگوریتم
الگوریتم ها یی با پیچیدگی زمانی ازقبیل n و100n
را الگوریتم های زمانی خطی می گویند.
مجموعه کامل توابع پیچیدگی را که با توابع درجه دوم محض قابل دسته بندی باشند، n²) ( θ می گویند.
مجموعه ای ازتوابع پیچیدگی که با توابع درجه سوم محض قابل دسته بندی باشند، n³) ( θ نامیده می شوند.
برخی از گروه های پیچیدگی متداول در زیر داده شده است:
θ(lg n) < θ (n) < θ (n lg n) < θ (n²) < θ (n³) < θ (2 ⁿ)
این کتاب در باره تکنیک های مربوط به حل مسائل است.
تکنیک ، روش مورد استفاده در حل مسائل است.
مسئله ، پرسشی است که به دنبال پاسخ آن هستیم.
بکار بردن تکنیک منجر به روشی گام به گام (الگوریتم ) در حل یک مسئله می شود.
منظورازسریع بودن یک الگوریتم، یعنی تحلیل آن از لحاظ زمان و حافظه.
نوشتن الگوریتم به زبان فارسی دو ایراد دارد:
1- نوشتن الگوریتم های پیچیده به این شیوه دشوار است.
2- مشخص نیست از توصیف فارسی الگوریتم چگونه
می توان یک برنامه کامپیوتری ایجاد کرد.
3-1 تحلیل الگوریتم ها
برای تعیین میزان کارایی یک الگوریتم را باید تحلیل کرد.
1-3-1 تحلیل پیچیدگی زمانی
تحلیل پیچیدگی زمانی یک الگوریتم ، تعیین تعداد دفعاتی است که عمل اصلی به ازای هر مقدار از ورودی انجام می شود.
T(n) را پیچیدگی زمانی الگوریتم در حالت معمول می گویند.
W(n) را تحلیل پیچیدگی زمانی در بدترین حالت
می نامند.
A(n) را پیچیدگی زمانی در حالت میانگین
می گویند.
تحلیل پیچیدگی زمانی برای حالت معمول برای الگوریتم(جمع کردن عناصرآرایه)
عمل اصلی: افزودن یک عنصر از آرایه به sum.
اندازه ورودی: n، تعداد عناصر آرایه.
T(n) = n
تحلیل پیچیدگی زمانی برای حالت معمول برای الگوریتم(مرتب سازی تعویضی)
عمل اصلی: مقایسه S [j] با S[i] .
اندازه ورودی: تعداد عناصری که باید مرتب شوند.
1مرتبه الگوریتم
الگوریتم ها یی با پیچیدگی زمانی ازقبیل n و100n
را الگوریتم های زمانی خطی می گویند.
مجموعه کامل توابع پیچیدگی را که با توابع درجه دوم محض قابل دسته بندی باشند، n²) ( θ می گویند.
مجموعه ای ازتوابع پیچیدگی که با توابع درجه سوم محض قابل دسته بندی باشند، n³) ( θ نامیده می شوند.
برخی از گروه های پیچیدگی متداول در زیر داده شده است:
θ(lg n) < θ (n) < θ (n lg n) < θ (n²) < θ (n³) < θ (2 ⁿ)
دانلود فایل”پاورپوینت خلاصه کتاب طراحی الگوریتمها مترجم جعفر نژاد قمی”