- فصل اول:
نوع داده انتزاعی(مجرد): ADT : وقتی در برنامه ایی به نوعی داده نیاز باشد که در آن زبان وجود ندارد برنامه نویس باید نوع مورد نظرش را ایجاد کند. نوع داده ایی را که برنامه نویس ایجاد می کند نوع داده انتزاعی می گویند.
ADT یک مدل ریاضی است که عملیاتی بر روی آن مدل تعریف می شود. هرنوع داده متشکل از چند مقدار و مجموعه ای از عملیات بر روی آنها است.
مانند نوع داده int که در زبان C عملیاتهایی مانند * + - = / > < و غیره برای آنها تعریف شده است.
در این درس انواع مختلفی از ADT ها را بوجود می آوریم مانند آرایه ها و ماتریس ها و درخت ها و غیره
1-1-نحوه تجزیه و تحلیل و سنجش کارایی یک برنامه:
تعریف : میزان حافظه یا پیچیدگی فضای یک برنامه مقدار حافظه مورد نیاز برای اجرای کامل یک برنامه است. مقدار زمان یا پیچیدگی زمانی یک برنامه مقدار زمانی از کامپیوتر است که برای اجرای کامل برنامه لازم است.
1-1-1- میزان حافظه (پیچیدگی حافظه): فضای مورد نیاز برای یک برنامه شامل موارد زیر است:
بخش ثابت که مستقل از بعضی خصیصه های ورودی و خروجی مانند تعداد وو اندازه است. این بخش شامل فضای دستورالعمل (کد برنامه) ، فضای لازم برای متغیرهای ساده و ثابت ها می باشد
بخش متغیر که شامل فضای مورد نیاز متغیرهای ساختاری برنامه که اندازه آن بستگی به نمونه مسئله ایی که حل می شود، دارد و فضای لازم برای متغیرهای مرجع که اندازه آنها نیز به خصیصه های نمونه بستگی دارد و فضای لازم برای پشته بازگشتی می باشد.
1-1-2-پیچیدگی زمانی:
زمان برنامه (T(P) ) مجموع زمان کامپایل و زمان اجرای برنامه است. زمان کامپایل برای یک برنامه فقط یک بار رخ می دهد در ضمن به خصیصه های نمونه بستگی ندارد. بنابراین زمان اجرا یک برنامه Tp مورد بررسی قرار می گیرد.
برای بدست آوردن زمان اجرای برنامه راه های مختلفی وجود دارد مثلا تعداد جمع ها و ضرب ها و تقسیمات و تفریقات یک برنامه را بدست آوریم و زمان را به صورت زیر محاسبه کنیم:
Tp= C1ADD(n) + C2Sub(n) + C3Mul(n) + C4Div(n)
که n نشان دهنده مشخصه های نمونه است. بدست آوردن چنین فرمول دقیقی یک کار غیر ممکن است زیرا زمان مورد نیاز برای جمع و ضرب و تفریق و تقسیم به عوامل متعددی بستگی دارد. در ضمن بین کامپیوتر های مختلف نیز متعدد است.
روش دیگری که برای بدست آوردن پیچیدگی زمانی یک برنامه استفاده می شود این است که تعداد مراحل برنامه را بشماریم. پیچیدگی زمانی یک برنامه را بر اساس تعداد مراحل آن بدست می آوریم.
برای بدست آوردن تعداد مراحل یک برنامه با توجه به نوع دستورات عمل می کنیم. مثلا دستورات انتساب را یک مرحله محسوب می کنیم. دستورات تکرار را با توجه به تعداد تکرارشان محاسبه می کنیم. دستورات تعریفی را جزء مراحل محسوب نمی کنیم. شرط IF را یک مرحله محسوب می کنیم. ص 35 و 36
تعداد مراحل فراخوانی یک تابع مساوی مجموع تعداد مراحل فراخوانی هر تابع است.
یک از روشهایی که برای محاسبه تعداد مراحل یک برنامه استفاده می شود استفاده از متغیری به نام count است که در ازای هر مرحله Count++ می شود
البته این روش نیز چندان دقیق نیست. مثلا ما دستور A:=5*2+4 –B رایک مرحله می گیریم و A:=8 را نیز یک مرحله می گیریم در صورتیکه از نظر زمانی با هم متفاوتند.
تعداد مراحل لزوما پیچیدگی جمله را منعکس نمی کند.
ولی در یک برنامه بزرگ می توان تعداد مراحل را با کمی اغماض پیچیدگی برنامه دانست و می توان برنامه ها را براساس پیچیدگی زمانی آنها با هم مقایسه کرد.
روش دیگر در کتاب بحث شده است که به روش S/e نام برده می شود که شباهت زیادی به روش Count دارد. ص41
تحقیق : پیچیدگی الگوریتم فیبوناچی 4n+1 است چرا؟
هدف از تعیین تعداد مراحل این است که بتوانیم پیچیدگی زمانی دوبرنامه که عمل مشابهی را انجام می دهند مقایسه کنیم و همچنین بتوانیم میزان افزایش زمان اجرا را وقتی مشخصات نمونه تغییر می کنند پیشگویی کنیم.
مثلا اگر پیچیدگی زمانی برنامه ایی 2n باشد و پیچیدگی زمانی برنامه دیگریn2 است کدام یک سریعتر است؟
البنه هر دوبرنامه یک الگوریتم است.
در مورد پیچیدگی زمانی یک برنامه تعاریف ریاضی(نشانه گذاری مجانبی) وجود دارد که در اینجا به اختصار بحث می شود تا بتوانیم عبارات با معنی(ولی غیردقیق) در مورد پیچیدگی زمانی یک برنامه بدست آوریم.
تعریف Big Oh : f(n) = O(g(n) است اگر و فقط اگر مقادیر ثابتی مانند C و n0 باشد که رابطه زیر برقرار باشد:
f(n) ≤C g(n) برای تمام n≥n0
مثال) فرض کنید f(n)=3n+2 باشد که دراین صورت اگر n0=2 باشد و C=4 باشد و g(n)=n رابطه زیر برقرار است
3n+2≤4 n
پس 3n+2=O(n)
البته می توان g(n) های دیگری نیز پیدا کرد که این خاصیت را داشته باشند.
3n+2 ≤ n2
C=1 و n0=4
ولی معمولا تابعی را به عنوان g(n) در نظر می گیرند که از بقیه کوچکتر باشد.
n≤n2
f(n)=O(g(n)) فقط نشان می دهد که g(n) حد بالایی مقدار f(n) است برای تمام n≥n0
قضیه: اگرf(n)=amnm+…+a1n+a0 در این صورت f(n)=O(nm)
تمرین: نشان دهید که n! = O(nn)
تعریف امگا: f(n)=Ω(g(n)) اگر و فقط اگر به ازای مقادیر ثابت C و n0 رابطه f(n)≥C.g(n) برای n≥n0 همیشه برقرار باشد.
مثال) مثلا 3n+2≥3.n است در ازای n≥1 3n+2= Ω(n)
10n2+4n+7≥n2 در ازای n≥1 یعنی 10n2+4n+7= Ω (n2) البته می توان نوشت که 10n2+4n+7= Ω (n)
اما معمولا تابعی را در نظر می گیرند که از بقیه بزرگتر باشد.
عبارت f(n)=Ω(g(n)) فقط نشان می دهد که g(n) یک حد پایین برای تابع f(n) است.
قضیه: اگرf(n)=amnm+…+a1n+a0 در این صورت f(n)= Ω (nm)
تعریف تتا: f(n)=θ(g(n)) است اگر و فقط اگر به ازای مقادیر c1 و c2 و n0 رابطه زیر درست باشد
c1.g(n)≤f(n) ≤c2.g(n) در ازای n≥n0
قضیه: اگرf(n)=amnm+…+a1n+a0 در این صورت f(n)= θ (nm)
نشانه گذاری تتا از امگا و Big oh دقیق تر است زیرا هم بعنوان کران بالا و هم بعنوان کران پایین f(n) می باشد.
سئوالی که مطرح می شود این است که این نشانه گذاری ها اگر یکی بخواهد دقیقا شمارش مراحل را انجام دهد، چه استفاده ایی دارد؟ پاسخ این است که پیچیدگی مجانبی(θ, Ω,O) بدون تعیین شمارش مراحل براحتی تعیین می گردد.