دانلود پاورپوینت مثالی از یک الگوریتم در متلب

  دانلود پاورپوینت مثالی از یک الگوریتم در متلب

تحلیل الگوریتم ها(تحلیل در زبان متلب)

عنوان های پاورپوینت مثالی از یک الگوریتم در متلب  ، تحلیل الگوریتم ها(تحلیل در زبان متلب)عبارتند از :

مثالی از یک الگوریتم در متلب
تحلیل الگوریتم ها(تحلیل در زبان متلب)
مثالی از یک الگوریتم در متلب
تحلیل پیچیدگی زمانی الگوریتم‌ها
مرتبه الگوریتم

مروری بر روش‌های اثبات

مرتبه الگوریتم

تکه ها و قسمت های اتفاقی از فایل مثالی از یک الگوریتم در متلب  ، تحلیل الگوریتم ها(تحلیل در زبان متلب)

تحلیل الگوریتم ها(تحلیل در زبان متلب)
مثالی از یک الگوریتم در متلب
الگوریتم جستجوی ترتیبی
function [location] = SeqSearch(A,x)
len=length(A);
location=0;
for i=1:len
if A(i)==x
location=i;
break;
end
end
end

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

1) پیچیدگی زمانی الگوریتم در حالت معمولدانلود پاورپوینت مثالی از یک الگوریتم در متلب
تحلیل الگوریتم ها(تحلیل در زبان متلب)ی ترتیبی

W(n)=n
3) پیچیدگی زمانی الگوریتم در بهترین حالت
مانند جستجوی ترتیبی
B(n)=1

تحلیل پیچیدگی زمانی الگوریتم‌ها
4) پیچیدگی زمانی الگوریتم در حالت میانگین
توجه: یک مقدار میانگین را فقط زمانی می‌توان معمولی خواند که حالتهای واقعی از میانگین انحراف زیادی نداشته باشد.
مثال: جستجوی ترتیبی
حالت 1: x همواره در آرایه هست

تحلیل پیچیدگی زمانی الگوریتم‌ها

حالت 2: x ممکن است در آرایه نباشد. احتمال وجود x را در آرایه p درنظر می‌گیریم.

تحلیل پیچیدگی زمانی الگوریتم‌ها
در تحلیل پیچیدگی الگوریتم‌ها، پیچیدگی حافظه نیز قابل بحث است

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

مرتبه الگوریتم
در پاره‌ای از موارد رسیدن به تابع پیچیدگی با داشتن الگوریتم کار پیچیده‌ای است ولی ...
می‌توانیم شکل ساده‌ای از آن را که بیان کننده پیچیدگی مساله باشد را بدست آوریم.
مرتبه الگوریتم
تعریف O )
برای یک تابع پیچیدگی مفروض f(n) ، مانند n، log n،
مجموعه‌ای از توابع پیچیدگی g(n) است که برای آنها
به ازای یک ثابت حقیقی مثبت c
آنگاه یک عدد صحیح غیر منفی N وجود دارد
به قسمی که به ازای همه n≥N داریم g(n) ≤c×f(n)
روش نمایش: g(n) ϵ O(f(n))

مرتبه الگوریتم

نمایش به صورت دیاگرام:
د) مرتبه الگوریتم
در این شکل هرچند n2 + 10n در ابتدا مقادیری بیشتر از 2n2 دارند ولی برای n<=10 روند دیگری شکل می‌گیرد.
مرتبه الگوریتم
5n2 ∊ O(n2) ?
for n ≤ 0,
c = 5 and N = 0 √

n2 + 10n ∊ O(n2) ?
for n ≥ 1,
c = 11 and N = 1 √

n ∊ (n 2) ?
for n ≥ 1,
c = 1 and N = 1 √
مرتبه الگوریتم
مرتبه الگوریتم
تعریف Ω (Omega)
برای یک تابع پیچیدگی مفروض f(n) ، مانند n، log n
مجموعه‌ای از توابع پیچیدگی g(n) است که برای آنها
به ازای یک ثابت حقیقی مثبت c
آنگاه یک عدد صحیح غیر منفی N وجود دارد
به قسمی که به ازای همه n≥N داریم g(n) ≥c×f(n)
روش نمایش: g(n) ϵ Ω(f(n)

مرتبه الگوریتم
نمایش به صورت دیاگرام:

مرتبه الگوریتم
n2 + 10n ∊ Ω (n2) ?
for n ≥ 0,
c = 1 and N = 0 √

n3 ∊ Ω(n2) ?
For n ≥ 1,
c = 1 and N = 1 √

مرتبه الگوریتم

مرتبه الگوریتم
تعریف Θ (Theta)
برای یک تابع پیچیدگی مفروض f(n) ، مانند n، log n
مجموعه‌ای از توابع پیچیدگی g(n) است که برای آنها
به ازای ثابت‌های حقیقی مثبت c و d
آنگاه یک عدد صحیح غیر منفی N وجود دارد
به قسمی که به ازای همه n≥N داریم:
d×f(n) ≥g(n) ≥c×f(n)
روش نمایش: g(n) ϵ Θ(f(n))

مرتبه الگوریتم
به عبارتی دیگر:
g(n) ϵ O(f(n)) AND Ω(f(n)
یعنی:

مرتبه الگوریتم
نمایش به‌صورت دیاگرام:

مرتبه الگوریتم

مرتبه الگوریتم
ویژگیهای O:
1- اگر g(n) بتواند به صورت مجموع تعداد محدودی از توابع دیگر نوشته شود، در این صورت آن تابعی که بیشترین رشد را دارد، O را مشخص می‌کند
f(n)=9logn+5(log n)3+3n2+2n3

2n3ϵO(n3)

f(n)ϵO(n3)

مرتبه الگوریتم
ادامه ویژگیهای O:
2- ویژگی ضرب
اگر g1ϵO(f1) و g2ϵO(f2) در آن صورت:
g1g2 ϵ ?
O(f1f2)
3- ویژگی جمع
اگر g1ϵO(f1) و g2ϵO(f2) در آن صورت:
g1+g2 ϵ ?
O(f1+f2)
4- ویژگی ضرب در مقدار ثابت
اگر gϵO(f) در آن صورت:
kg ϵ ?
O(f)

مرتبه الگوریتم
ادامه ویژگیهای O:
5- می‌توان O را در بیان پیچیدگی محاسباتی نیز آورد
مثلا T(n)=O(n2)+55n3+2n+10
در این الگوریتم ابتدا مرتب‌سازی انجام می‌پذیرد و سپس کار ادامه می‌یابد

مرتبه الگوریتم
ویژگی های مرتبه:
1- g (n) ∊ O(f)n)) if and only if (اگر و تنها اگر)
f(n) ∊ Ω(g(n))

2- g(n) ∊ Θ (f(n)) if and only if
f(n)∊ Θ(g(n))

3- If b> 1 and a > 1, then loga n ∊ Θ (logb n).
این ویژگی نشان می‌دهد که تمامی تابع‌ها لگاریتمی در یک گروه پیچیدگی مشترک قرار دارند.

این گروه در ادامه این درس با Θ(lgn) مشخص می‌شود.
مرتبه الگوریتم
تعریف o )
برای یک تابع پیچیدگی مفروض f(n) ، مانند n، log n،
مجموعه‌ای از توابع پیچیدگی g(n) است که برای آنها
به ازای هر ثابت حقیقی مثبت c
آنگاه یک عدد صحیح غیر منفی N وجود دارد
به قسمی که به ازای همه n≥N داریم g(n) ≤c×f(n)
روش نمایش: g(n) ϵ o(f(n)

مرتبه الگوریتم
ویژگی های مرتبه:
4-If b > a > 0, then
این ویژگی نشان می‌دهد که ...
برخلاف توابع پیچیدگی لگاریتمی، توابع پیچیدگی نمایی در یک گروه پیچیدگی قرارندارند.

5- For all a > 0
این ویژگی نشان می‌دهد که ...
تابع پیچیدگی n! از هر تابع پیچیدگی نمایی بدتر است.
مرتبه الگوریتم
ویژگی های مرتبه:
6- ترتیب گروه‌ها پیچیدگی زیر را از چپ به راست درنظر بگیرید ...

k > j and b > a> 1.

چنانچه تابع پیچیدگی g(n) در گروهی سمت چپ گروهی که تابع پیچیدگی f(n) در آن قرار دارد باشد در این صورت:

مروری بر روش‌های اثبات
1) برهان مستقیم (Direct Proof)
در برهان مستقیم، نتیجه از ترکیب منطقی اصل‌ها، تعریف‌ها و تئوری‌های پیشین بدست می‌آید.
بطور مثال برهان مستقیم برای اثبات زوج بودن جمع دو عدد زوج بکار می‌رود:
برای هر ۲ عدد زوج صحیح x و y می‌توانیم بنویسیم x=2a و y=2b. جمع (x+y)=2a+2b=2(a+b) نیز طبق تعریف عددی زوج است. بنابراین جمع دو عدد زوج همواره زوج می‌باشد.
مروری بر روش‌های اثبات
2) اثبات استقرایی (Proof by Induction)
در اثبات استقرایی، ابتدا یک «حالت پایه» اثبات می‌شود.
سپس به کمک «فرض استقراء» مجموعه‌ای از حالات بعدی اثبات می‌شود که اصطلاحا «گام استقرا» گفته می‌شود.
از آنجایی که حالت پایه صحیح است، حالات دیگر بعدی هم با گام استقرا نشان‌داده می‌شود که صحیح هستند، حتی اگر همه آنها هم نتوانند به خاطر تعداد نا متناهیشان به صورت مستقیم اثبات شوند.
مروری بر روش‌های اثبات
3) اثبات با بر هان خلف (Proof by reductio ad absurdum)
در اثبات با برهان خلف، فرض می‌کنیم گزاره‌ای غلط است، سپس به یک تناقض منطقی می‌رسیم، پس نتیجه می‌گیریم که آن گزاره باید صحیح باشد. این روش یکی از متداول‌ترین روش‌های اثبات در ریاضی است.
4) اثبات از طریق ترانهش (Proof by Transposition)
اثبات از طریق ترانهش نتیجه «اگر p آنگاه q» را به وسیله اثبات گزاره «اگر نقیض q آنگاه نقیض p» برقرار می‌سازد.
و اثبات از طریق شبیه سازی، اثبات فرسایشی، اثبات احتمالاتی، اثبات ترکیبیاتی، اثبات غیر تمثیلی و اثبات ابتدایی

مرتبه الگوریتم
قضیه:
چنانچه g(n) ∊ o (f(n)) آنگاه

این بدان معنا است که ...
g(n) عضو مجموعه O(f(n)) است ولی ...
عضو Ω(f(n)) نمی‌باشد.
مرتبه الگوریتم
قضیه: چنانچهg(n) ∊ o (f(n)) باشد آنگاه g(n) ∊ O(f(n))-Ω (f(n))
اثبات:
به دلیل آنکه g(n)∊o(f(n)) ...
برای هر عدد مثبت حقیقی c، N ای وجود دارد که برای تمامی n>N

پس وقتی برای هر c این رابطه برقرار است پس c ای وجود دارد که ....
بنابراین :

(پس این بخش را با برهان مستقیم اثبات کردیم)
مرتبه الگوریتم
قضیه: چنانچهg(n) ∊ o (f(n)) باشد آنگاه g(n) ∊ O(f(n))-Ω (f(n))
در ادامه با برهان خلف نشان خواهیم داد که g(n) عضو Ω (f(n)) نیست.
چنانچه g(n) ∊ Ω(f(n)) باشد در اینصورت ....
در اینصورت ثابت حقیقی c > 0و N1 ای وجود دارند که برای تمامی n≥N1

اما چون g(n) ∊ o (f(n)) هست پس N2 ای وجود دارد که به ازای تمامی n ≥ N2

هردوی این معادله‌ها بایست برای تمامی n بزرگتر مساوی N1, N2 برقرار باشد.
این تناقض نشان می‌دهد که g(n) نمی‌تواند عضو Ω (f(n)) باشد.

مرتبه الگوریتم
قضیه: چنانچهg(n) ∊ o (f(n)) باشد آنگاه g(n) ∊ O(f(n))-Ω (f(n))
آیا دو مجموعه o (f(n)) و O (f(n)) – Ω (f(n)) با هم یکسانند؟
خیر
توابعی هستند که عضو O (f(n)) – Ω (f(n)) هستند ولی عضو o نیستند.
مثال بعدی این مطلب را نشان می‌دهد.
مرتبه الگوریتم
دانلود پاورپوینت مثالی از یک الگوریتم در متلب
تحلیل الگوریتم ها(تحلیل در زبان متلب)

30 تا 70 درصد پروژه | پاورپوینت | سمینار | طرح های کارآفرینی و  توجیهی |  پایان-نامه |  پی دی اف  مقاله ( کتاب ) | نقشه | پلان طراحی |  های آماده به صورت رایگان میباشد ( word | pdf | docx | doc | )