ساخت پاوپوینت با هوش مصنوعی
کم تر از 5 دقیقه با هوش مصنوعی کافه پاورپوینت ، پاورپوینت بسازید
برای شروع ساخت پاورپوینت کلیک کنید
شما در این مسیر هستید :خانه / محصولات / Powerpoint / دانلود پاورپوینت تحلیل وبررسی روش تقسیم و حل (Divide and Conquer) (کد16668)
سفارش انجام پاورپوینت - بهترین کیفیت - کم ترین هزینه - تحویل در چند ساعت 09164470871 ای دی e2proir
دانلود پاورپوینت تحلیل وبررسی روش تقسیم و حل (Divide and Conquer) (کد16668)
شناسه محصول و کد فایل : 16668
نوع فایل : Powerpoint پاورپوینت
قابل ویرایش تمامی اسلاید ها دارای اسلاید مستر برای ویرایش سریع و راحت تر
امکان باز کردن فایل در موبایل - لپ تاپ - کامپیوتر و ...
با یک خرید میتوانید بین 342000 پاورپینت ، 25 پاورپوینت را به مدت 7 روز دانلود کنید
هزینه فایل : 105000 : 54000 تومان
فایل های مشابه شاید از این ها هم خوشتان بیاید !!!!
توضیحات محصول دانلود پاورپوینت تحلیل وبررسی روش تقسیم و حل (Divide and Conquer) (کد16668)
دانلود پاورپوینت تحلیل وبررسی روش تقسیم و حل (Divide and Conquer)
دانلود پاورپوینت تحلیل وبررسی روش تقسیم و حل (Divide and Conquer)
روش تقسیم و حل (Divide and Conquer)
عنوان های پاورپوینتتحلیل وبررسی روش تقسیم و حل (Divide and Conquer)عبارتند از :
تحلیل وبررسی روش تقسیم و حل (Divide and Conquer)
روش تقسیم و حل (Divide and Conquer)
روش تقسیم و حل
الف) جستجوی دودویی
ب) مرتب‌سازی ادغامی (Merge Sort)
روش تقسیم و حل
ج) مرتب‌سازی سریع (Quick Sort) یا Partition Exchange Sort
ج) مرتب‌سازی سریع
د) ضرب ماتریس‌های استراسن (Strassen's Matrix Multiplication )
ه) اعمال محاسباتی روی اعداد صحیح بزرگ
و) تعیین مقادیر آستانه
کجا نمی‌توان از روش تقسیم‌وحل استفاده کرد؟
تکه ها و قسمت های اتفاقی از فایل دانلود پاورپوینت تحلیل وبررسی روش تقسیم و حل (Divide and Conquer)
روش تقسیم و حل (Divide and Conquer)
روش تقسیم و حل (Divide and Conquer)
شیوه حل در این روش به این صورت است که:
به صورت بازگشتی ...
مساله به دو یا بیشتر زیر مساله از نوع همان مساله (یا مساله‌ای که در حل مساله اصلی مرتبط است) تقسیم (divide) می‌شود و ...
اینکار (شکستن و تقسیم‌کردن) تا آنجایی ادامه می‌یابد که ...
مساله به اندازه‌ای ساده شود که بتواند مستقیما حل شود (conquer). سپس ...
پاسخ‌های زیرمساله‌ها با هم ترکیب می‌شوند تا پاسخی برای مساله اصلی فراهم سازند.
روش تقسیم و حل (Divide and Conquer)
فهم و طراحی الگوریتم‌های D&C، مهارت پیچیده‌ای است که نیازمند فهم خوب از ماهیت مساله دارد.
روش تقسیم و حل (Divide and Conquer)
توجه:
به هنگام نوشتن الگوریتم‌های بازگشتی در سطح مسئله فکر می‌کنیم و
می‌گذاریم تا جزئیات را زبان برنامه نویسی با استفاده از Stack بر عهده گیرد
هنگام طراحی الگوریتم‌های تقسیم و حل معمولا همین گونه فکر می‌کنیم و آن را به صورت یک روال بازگشتی می‌نویسیم
روش تقسیم و حل (Divide and Conquer)
برخی از مولفین می‌گویند که عنوان روش تقسیم و حل حتما می‌بایست به روش‌هایی تعلق گیرد که مساله را به دو یا بیشتر زیرمساله تقسیم می‌کند و ...
چنانچه مساله به تنها یک زیرمساله دیگر شکسته شود به آن روش، کاهش و حل (Decrease and Conquer) می‌گویند.
کوئیز از جلسه قبل)
تابع زیر را درنظر بگیرید:
نشان دهید که:
روش تقسیم و حل
سابقه تاریخی علت نام‌گذاری این روش:
در سال 1805، ارتشی از سربازان روسی و اتریشی با بیش از 15 هزار نفر به جنگ با ناپلئون آمدند.
ناپلئون با حمله به قلب سپاه آنها و تقسیم نیروهای دشمن به دو بخش بر آنها پیروز شد.
در واقع ناپلئون با تقسیم (Divide) سپاه بزرگ به دو سپاه کوچکتر و پیروز شدن بر تک‌تک آنها موفق شد بر آن سپاه بزرگ غبه یابد (Conquer)
الف) جستجوی دودویی
اگر x برابر عنصر میانی آرایه بود جستجو تمام است. در غیر این صورت ...
آرایه را به دو زیر آرایه تقسیم کن که هریک حدودا نصف آرایه اولیه‌اند.
اگر x کوچکتر از عنصر میانی بود کار را در زیرآرایه چپی و اگر x بزرگتر از عنصر میانی بود، کار را در زیر آرایه راستی ادامه می‌دهیم
حل مسئله را از حل مسئله زیر آرایه به دست آور
الف) جستجوی دودویی
x=18
الف) جستجوی دودویی
function position=recbinsearch(x,low,high)
global A;
mid=floor((low+high)/2);
if (A(mid)==x)
position=mid;
else
if x<A(mid)
newlow=low; newhigh=mid-1;
else
newhigh=high; newlow=mid+1;
end
if (newhigh>=newlow)
high=newhigh; low=newlow;
position=recbinsearch(x,low,high);
else
position=0;
end
end
end
الف) جستجوی دودویی
تحلیل پیچیدگی در بدترین حالت:
سوال) بدترین زمان کی رخ می‌دهد؟
الف) المان مورد جستجو در لیست نباشد؟
ب) المان مورد جستجو از تمامی المان‌های لیست بزرگتر باشد؟
mid=floor((low+high)/2); ….
مثلا در لیست [1 2 3 4 5] چنانچه دنبال 6 بگردیم چند جستجو نیاز است؟
دنبال 0 بگردیم چند جستجو نیاز است؟
الف) جستجوی دودویی
تحلیل پیچیدگی در بدترین حالت:
الف) جستجوی دودویی
اثبات پیچیدگی در بدترین حالت با استقرا:
فرمول بازگشتی روبرو را درنظر بگیرید:
برای تعدادی از n ها tn را می‌توانیم محاسبه کنیم:
به نظر می‌رسد که رابطه زیر برقرار باشد:
الف) جستجوی دودویی
اثبات پیچیدگی در بدترین حالت:
با استقرا نشان می‌دهیم که این رابطه صحیح است.
پایه استقرا: (برای n=1)
فرض استقرا:
فرض می‌کنیم برای n>0 دلخواهی که توانی از 2 است رابطه زیر برقرار باشد:
الف) جستجوی دودویی
گام استقرا:
به دلیل آنکه فرمول بازگشتی که به دنبال اثبات آن هستیم تنها برای اعدادی که توانی از 2 هستند مصداق دارد بنابراین ...
عدد بعدی که بعد از n درنظر می‌گیریم باید ...
2n باشد.
بنابراین باید نشان دهیم که :
چنانچه 2n را در رابطه بازگشتی قرار دهیم ...
الف) جستجوی دودویی
تحلیل پیچیدگی در بدترین حالت:
با استقرا نشان دادیم که رابطه زیر برای زمانیکه n، توانی از 2 باشد برقرار است:
در حالت کلی چنانچه این شرط محدودکننده را برداریم رابطه زیر اثبات خواهد شد که:
ب) مرتب‌سازی ادغامی (Merge Sort)
ب) مرتب‌سازی ادغامی (Merge Sort)
function result=merge(A,B)
lena=max(size(A));lenb=max(size(B));
result=zeros(1,lena+lenb);
ia=1;ib=1;k=1;
while(ia<=lena && ib<=lenb)
if A(ia)<B(ib)
result(k)=A(ia);
دانلود پاورپوینت تحلیل وبررسی روش تقسیم و حل (Divide and Conquer)
روش تقسیم و حل (Divide and Conquer)
end
روش تقسیم و حل
کوئیز از جلسه قبل)
با استقرا نشان دهید که پیچیدگی زمانی در الگوریتم جستجوی دودویی در بدترین حالت با روش تقسیم و حل برابر است با W(n)=logn+1
(اثبات را برای زمانیکه nها توانی از 2 هستند انجام دهید)
توجه: مراحل در شیوه اثبات استقرایی را با دقت بیان کنید.
ب) مرتب‌سازی ادغامی (Merge Sort)
پیچیدگی زمانی در بدترین حالت:
بدترین زمان مربوط به حالتی است که ...
حلقه while در تابع merge به اتمام برسد در حالیکه ...
یکی از ایندکس‌ها مانند ia به مقدار lena+1 برسد در حالیکه ایندکس دیگری مانند ib برابر با lenb باشد.
چراکه عملیات اصلی (مقایسه المانها با هم) بیشترین تکرار را خواهد داشت
ب) مرتب‌سازی ادغامی (Merge Sort)
پیچیدگی زمانی در بدترین حالت:
ب) مرتب‌سازی ادغامی (Merge Sort)
پیچیدگی زمانی در بدترین حالت:
ب) مرتب‌سازی ادغامی (Merge Sort)
قضیه:
تابع پیچیدگی T(n) که بصورت افزایشی است و شرایط زیر را دارد را درنظر بگیرید:
که b ≥ 2 و k ≥ 0 ثابت‌های صحیحی هستند و a، c و d ثابت‌هایی هستند که
a > 0, c > 0 و d ≥ 0 آنگاه:
ب) مرتب‌سازی ادغامی (Merge Sort)
در قضیه گفته شده داشتیم:
همچنین چنانچه رابطه بازگشتی به دوصورت زیر تغییر کند:
در این صورت نتایج با "big O“ یا Ω به جای Θ تغییر خواهد کرد.
ب) مرتب‌سازی ادغامی (Merge Sort)
پیچیدگی زمانی در بدترین حالت:
ج) مرتب‌سازی سریع (Quick Sort) یا Partition Exchange Sort
فرض کنید آرایه زیر شامل لیستی از اعداد به صورت زیر باشد:
آرایه را به گونه‌ای پارتیشن‌بندی می‌کنیم که تمامی المان‌های که کوچکتر از المان محوری هستند در سمت چپ آن و المان‌های بزرگتر از آن در سمت راستش قرار بگیرند:
هرکدام از زیرآرایه‌ها را مرتب می‌کنیم:
ج) مرتب‌سازی سریع (Quick Sort)
function [A,ppoint]=partition(A)
len=length(A);
pitem=A(1);
ppoint=1;
for i=2:len
if A(i)<pitem
ppoint=ppoint+1;
temp=A(ppoint);A(ppoint)=A(i);A(i)=temp;
end
end
temp=A(1);A(1)=A(ppoint);A(ppoint)=temp;
end
ج) مرتب‌سازی سریع (Quick Sort)
function S=quickSort(A)
len=length(A);
if (len>1)
[A,ppoint]=partition(A);
S(1:ppoint-1)=quickSort(A(1:ppoint-1));
S(ppoint)=A(ppoint);
S(ppoint+1:len)=quickSort(A(ppoint+1:len));
else
S=A;
end
end
ج) مرتب‌سازی سریع (Quick Sort)
تحلیل پیچیدگی زمانی در بدترین حالت:
ج) مرتب‌سازی سریع (Quick Sort)
تحلیل پیچیدگی زمانی در حالت میانگین:
ج) مرتب‌سازی سریع (Quick Sort)
تحلیل پیچیدگی زمانی در حالت میانگین:
یکی از ویژگی‌های توابع لگاریتمی:
ج) مرتب‌سازی سریع
کوئیز از جلسه قبل)
لطفا برای لیست A=[5 1 6 0 7 2 3 9 8 4]; الگوریتم مرتب‌سازی سریع را اجرا کنید و لیست مرتب شده را بدست آورید.
برای این منظور گام‌های شکل‌گیری تقسیم و حل را بر اساس دو الگوریتم quickSort و partition به صورت درخت ترسیم نمایید.
توجه: نیازی به نشان دادن گام‌های الگوریتم partition نمی‌باشد، بلکه در هر بخش از درخت تقسیم و حل نتیجه آن را بیاورید.
د) ضرب ماتریس‌های استراسن (Strassen's Matrix Multiplication )
فرض کنید که می‌خواهیم ماتریس C که حاصلضرب دو ماتریس 2*2 A و B است را بدست آوریم.
استراسن فرمول‌هایی به صورت زیر ارائه کرده‌است که با بهره‌گیری از آنها می‌توان ماتریس C را محاسبه نمود.
Strassen determined that if we let
د) ضرب ماتریس‌های استراسن
این روش برای ماتریس‌های 2*2 چندان جالب نیست
فرمول‌های استراسن به گونه‌ای هستند که می‌توانیم ماتریس‌های بزرگتر را به صورت افراز 4 ماتریس کوچکتر در نظر گرفت
د) ضرب ماتریس‌های استراسن
د) ضرب ماتریس‌های استراسن
د) ضرب ماتریس‌های استراسن
function C=sterasen(A,B)
n=max(size(A));
if (n==2)
C=A*B;
else
A11=A(1:n/2,1:n/2);
A12=A(1:n/2,n/2+1:n);
A21=A(n/2+1:n,1:n/2);
A22=A(n/2+1:n,n/2+1:n);
B11=B(1:n/2,1:n/2);
B12=B(1:n/2,n/2+1:n);
B21=B(n/2+1:n,1:n/2);
B22=B(n/2+1:n,n/2+1:n);
د) ضرب ماتریس‌های استراسن
تحلیل پیچیدگی زمانی تعداد جمع‌ها و تفریق‌ها در حالت معمول
این روش برای ضرب دو ماتریس 2×2، به 7 عمل ضرب و 18 عمل جمع و تفریق نیاز دارد
کوئیز از جلسه قبل)
اگر فرمول‌های استراسن برای ضرب دو ماتریس 2*2 به صورت زیر باشد، تابعی با نام sterasen بنویسید که دو ماتریس A و B را از ورودی بگیرد و حاصلضرب آن دو را در C با شیوه تقسیم‌وحل برگرداند.
ه) اعمال محاسباتی روی اعداد صحیح بزرگ
انجام اعمال محاسباتی روی اعداد صحیحی که بزرگتر از حدی هستند که سخت‌افزار کامپیوتر می‌تواند آنها را نمایش دهد.
نوشتن الگوریتمی با زمان خطی که جمع و تفریق اعدادی صحیح با چنین ساختاری را انجام دهند مشکل نمی‌باشد.
ه) اعمال محاسباتی روی اعداد صحیح بزرگ
ضرب اعداد صحیح بزرگ:
ه) اعمال محاسباتی روی اعداد صحیح بزرگ
بنابراین چنانچه دو عدد با n رقم به صورت زیر داشته باشیم:
در این صورت ضرب آنها را به صورت زیر می‌توان نوشت:
به عنوان مثال دو عدد زیر را در نظر بگیرید:
ه) اعمال محاسباتی روی اعداد صحیح بزرگ
function R=largeIntProd(U,V) دانلود پاورپوینت تحلیل وبررسی روش تقسیم و حل (Divide and Conquer)
روش تقسیم و حل (Divide and Conquer)
تحلیل پیچیدگی زمانی در بدترین حالت:
زمانی اتفاق می‌افتد که هیچکدام از دو عدد صحیح هیچ رقمی برابر صفر نداشته باشند.
ه) اعمال محاسباتی روی اعداد صحیح بزرگ
بهبود:
در تابع largeIntProd که نوشته شد، می‌بایست سه مقدار زیر را محاسبه می‌کردیم ...
که عملا این تابع به صورت بازگشتی می‌بایست چهار بار صدا زده می‌شد:
چنانچه تغییر متغیری به صورت زیر انجام دهیم ...
آنگاه خواهیم داشت ...
در این حالت برای محاسبات دیگر نیاز به چها ضرب نیست. بلکه تنها سه ضرب انجام می‌شود. هرچند که تعدادی جمع و ضرب انجام می‌شود ولی زمان آنها در محاسبات خطی است.
ه) اعمال محاسباتی روی اعداد صحیح بزرگ
تحلیل پیچیدگی زمانی در بدترین حالت:
زمانی است که هیچ یک از دو عدد صحیح رقمی برابر با صفر نداشته باشند
اگر n توانی از 2 باشد آنگاه x، y، w و z همگی n/2 رقم خواهند داشت
با توجه به مثالی که در جدول زیر آورده شده است:
ه) اعمال محاسباتی روی اعداد صحیح بزرگ
در آخرین الگوریتم ارائه شده 3 بار فراخوانی prod را داریم:
همانند تحلیل پیچیدگی که برای حالتی که دارای 4 بار فراخوانی prod بود، دیگر عملیات‌ها نظیر sum و shift دارای پیچیدگی زمانی خطی (cn) نسبت به n می‌باشند.
بنابراین رابطه زیر را داریم:
ه) اعمال محاسباتی روی اعداد صحیح بزرگ
بر اساس قضیه بیان شده در داریم:
همچنین
نشان می‌دهیم که در داریم:
پس در نهایت:
ه) اعمال محاسباتی روی اعداد صحیح بزرگ
برای مرتبه پیچیدگی محاسباتی در اینگونه بیان می‌کنیم که ...
بر اساس قضیه بیان شده خواهیم داشت:
و همچنین:
کوئیز از جلسه قبل)
هدف آن است تا برای ضرب اعداد صحیح بزرگ با رویکرد تقسیم‌وحل الگوریتمی ارائه دهیم. رابطه زیر داده شده است:
الف)
رابطه را به گونه‌ای تغییر دهید که در رابطه جدید پیچیدگی محاسباتی کاهش یابد.
ب) سپس براساس رابطه (الف) تابعی با نام prod بنویسید که با رویکرد تقسیم‌وحل مساله را ضرب دو عدد صحیح بزرگ را حل می‌کند
و) تعیین مقادیر آستانه
فرآیند بازگشتی از لحاظ زمانی سربار به همراه دارد:
1) قرار دادن پارامترها در پشته قبل از فراخوانی
2) بازیابی پارامترها از پشته پس از پایان فراخوانی
بنابراین بحث این است که اگر مثلا می‌خواهیم 8 عدد را مرتب کنیم آیا سربار اضافه شده ارزش آن را دارد که:
به جای Ɵ(n2) (مرتب سازی تعویضی)،
از Ɵ(nlog n) (مرتب سازی ادغامی) استفاده کنیم؟
بنابراین در این بخش روشی را بیان می‌کنیم که تعیین می‌کند که الگوریتم به ازای چه مقادیری از n (مقدار آستانه)، آنقدر سریع است که دیگر
نیاز به تقسیم کردن نمونه نباشد.
و) تعیین مقادیر آستانه
چون تعیین مقدار آستانه به هزینه سربار مربوط می‌شود، بنابراین تعیین مقدار آستانه به کامپیوتری بستگی دارد که برنامه در آن اجرا می‌شود
پس از تعیین مقدار آستانه (threshold) می‌گویی برای n<=t از الگوریتم بدون بازگشتی و برای n>t از روش بازگشتی (تقسیم‌وحل) استفاده می‌کنیم.
و) تعیین مقادیر آستانه
فرض می‌کنیم روی کامپیوتر مورد نظر، زمانیکه مرتب‌سازی ادغامی برای
1- تقسیم (فراخوانی پشته)
2- ترکیب (بازیابی مقادیر از پشته و merge)
نیاز دارد، 32nµs باشد.
پس:
دانلود پاورپوینت تحلیل وبررسی روش تقسیم و حل (Divide and Conquer)
روش تقسیم و حل (Divide and Conquer)
اگر پس از حل معادله مقادیر زیر را بدست آوریم:
t زوج است، یعنی .... پس از حل معادله داریم t=64
t فرد است، یعنی .... پس از حل معادله داریم t=70
چون دو مقدار t با هم برابر نیستند پس هیچ مقدار آستانه‌ای وجود ندارد
اگر n عددی زوج بین 64 و 70 باشد باید یکبار دیگر تقسیم کرد و
اگر n عددی فرد بین 64 و 70 باشد از رویکرد بدون بازگشتی استفاده می‌کنیم
کجا نمی‌توان از روش تقسیم‌وحل استفاده کرد؟
در موارد زیر باید از روش تقسیم و حل پرهیز کرد:
1- نمونه‌ای به اندازه n به دو یا چند نمونه به اندازه تقریبا n تقسیم می‌شود
2- نمونه‌ای به اندازه n به n نمونه به اندازه تقریبا n/c (c مقدار ثابتی است) تقسیم می‌شود
دانلود پاورپوینت تحلیل وبررسی روش تقسیم و حل (Divide and Conquer)
روش تقسیم و حل (Divide and Conquer)
30 تا 70 درصد پروژه | پاورپوینت | سمینار | طرح های کارآفرینی و توجیهی | پایان-نامه | پی دی اف مقاله ( کتاب ) | نقشه | پلان طراحی | های آماده به صورت رایگان میباشد ( word | pdf | docx | doc | )
