مروری بر مباحث کارشناسی ارشد مهندسی کامپیوتر طراحی الگوریتم

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

● روش های گوناگون طراحی یک الگوریتم

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

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

پنج نماد O (ا ُی بزرگ) ، o(ا ُی کوچک ) ، Ω ( امگا ) ، w (دبلیوی کوچک ) و Ө ( تتا) به ترتیب حد بالای پیچیدگی به ازای حداقل یک مقدار ، حدبالای پیچیدگی به ازای تمام مقادیر ممکن ، حد پایین پیچیدگی به ازای حداقل یک مقدار ، حد پایین پیچیدگی به ازای تمام مقادیر ممکن ، و حد متعارف ( حدی که هم در بالاترین و هم پایین ترین حدود بگنجد و در واقع اشتراک آن ها باشد ) را نشان می دهند و شامل تمام توابعی هستند که در آن حدود قرار می گیرند و برای تعریف آن می توان از این روابط کمک گرفت :

الف) وجود داشته باشد n و حداقل ۰<c به طوری که برای تمامn>=N که در آن N>=۰ داشته باشیم g(n)<=c*f(n) که در این صورت می گوییم : (f(n)) g(n)=O

ب) وجود داشته باشد n و حداقل یک ۰<c به طوری که برای تمامn>=N که در آن N>=۰ داشته باشیم g(n)>=c*f(n) که در این صورت می گوییم : (f(n))Ω g(n)= .

ج) وجود داشته باشد n و حداقل یک ۰<d,c به طوری که برای تمامn>=N که در آن N>=۰ داشته باشیم c*f(n)<=g(n)<=d*f(n) که در این صورت می گوییم : (f(n))Ω g(n)= .

د) وجود داشته باشد n و ۰<c به طوری که برای تمامn>=N و تمام مقادیر cکه در آن N>=۰ داشته باشیم g(n)<=c*f(n) که در این صورت می گوییم : (f(n)) g(n)=o

هـ) وجود داشته باشد n و ۰<c به طوری که برای تمامn>=N و تمام مقادیر cکه در آن N>=۰ داشته باشیم g(n)>=c*f(n) که در این صورت می گوییم : (f(n)) g(n)=w

▪ نکته : برای محاسبه پیچیدگی روابط می توانید از قضایای زیادی استفاده نمایید که مهم ترین آن ها قضیه Master می باشد که بسیار کاراست و در کتاب CLRS به وضوح توضیح داده شده است .

بنابراین روش های گوناگونی طراحی شده است تا به کمک آن ها الگوریتم هایی نوشته و براساس آن ها برنامه نویسی هایی انجام گیرد تا بهترین کارایی از لحاظ پیچیدگی زمانی و مکانی حاصل شود که روش های زیر از جمله مهم ترین آن ها بوده و در کتب طراحی الگوریتم مورد بحث قرار گرفته است :

الف) روش تقسیم و غلبه

ب) برنامه نویسی پویا

ج) روش حریصانه

د) روش عقبگرد

هـ) روش شاخه و حد

● روش تقسیم و غلبه

این روش از این منطق کمک می گیرد که می توان مسئله را به زیر مسائلی تقسیم نمود به طوری که حل زیر مسائل مستقل از مسئله اصلی است . مثلا فرض کنیم آرایه ای از اعداد مرتب را داریم که قصد داریم تا به کمک آن ها کلیدی را در آن جستجو کنیم . در هر مرحله آرایه را به دو زیر آرایه راست و چپ تقسیم می کنیم به طوری که زیر آرایه چپ دارای عناصر کوچکتر از زیر آرایه راست می باشند زیرا آرایه به صورت صعودی مرتب شده است . حال کلید را با عنصر میانی مقایسه می کنیم و اگر برابر نبود بررسی می کنیم که اگر بزرگتر از عنصر میانه بود در زیر آرایه راست و اگر کوچکتر از عنصر میانه بود در زیر آرایه چپ به دنبال آن می گردیم . حال فرض می کنیم آرایه ما آرایه سمت چپ و یا سمت راست است و بنابراین دوباره آن را به دو زیر آرایه تقسیم کرده و ادامه می دهیم . از آنجا که در هر مرحله آرایه نصف می شود لذا مرتبه آن O(log N)+۱ می باشد که N اندازه ورودی است .

نمونه دیگر نیز الگوریتم مرتب سازی آرایه به روش ادغام است که از مرتبه O(N log N ) می باشد . الگوریتم مرتب سازی سریع نیز در بدترین حالت که آرایه به صورت نزولی مرتب شده باشد O(N^۲) بوده و در حالت میانگین O(N log N ) می باشد .

▪ نکته : این الگوریتم ها در کتب طراحی الگوریتم از جمله دو کتاب ریچارد نیپولیتان و CLRS بیان شده است .

● برنامه نویسی پویا

مسئله را به زیر مسائلی تقسیم می کنیم به طوریکه میان مسئله nام و مسئله n-۱)) ام رابطه ای وجود داشته باشد و سپس گام به گام از جمله اول شروع کرده و به سمت جلو حرکت می کنیم . مکانیسم آن نیز به این طریق است که فرضا اگر بخواهیم کوتاهترین مسیر میان I و j را پیدا کنیم آن را به دو زیر مسیر I تا k و k تا j تقسیم کرده و بررسی می کنیم که کوتاهترین مسیر در این سه گروه کدام است (i…………k…………j )

به عنوان مثال برای این که تعداد ضرب های لازم برای ضرب ماتریس های A(i) تا A(j) را پیدا کنیم ، این رابطه میان زیر مسائل برقرار است :

M[i][j]=mim(M[i][k]+M[k+۱][j]+d(i-۱)*d(k)*d(j) I

M[i][j]=۰ i>=j

که در آن d(i-۱)وd(k)وd(j) تعداد سطر های ماتریس ها می باشند .

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

● روش حریصانه

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

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

الگوریتم پریم در هر مرحله : یالی با کمترین وزن را انتخاب می کند به طوری که:

الف ) کم ترین وزن را میان سایر یال ها داشته باشد

ب) قبلا انتخاب نشده باشد

ج) با یال های انتخابی قبلی تشکیل دور ندهد ( زیرا در این صورت درخت نیست . ) . این الگوریتم در هر مرحله یک درخت ایجاد می کند .

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

● روش عقبگرد

این روش از درخت فضای حالت استفاده می کند به این صورت که هر کدام از گره های آن یک حالت ممکن را نشان می دهند و بنابراین هر مسیر از گره ریشه به برگ ، یک حل کاندید به شمار خواهد رفت . یکی از کاربردهای آن در مسئله n وزیر است یعنی چگونه n وزیر را روی یک صفحه شطرنجی n*n قرار بدهیم به طوری که همدیگر را گارد ندهند . در این صورت گره j ام سطح iام درخت یعنی معرف وزیر ردیف iام و ستون jام صفحه شطرنج خواهد بود . حال از گره ریشه شروع کرده و با یک پیمایش پیشوندی اگر به گرهی غیر امیدبخش یعنی گرهی که باعث شود دو وزیر یکدیگر را گارد بدهند ، به عقب بر می گردیم و الا به سمت برگ ها حرکت می کنیم .

دو وزیر در ردیف I وk و ستون j زمانی یکدیگر را گارد می دهند که یا روی یک ردیف و یک ستون باشند و یا هم قطر باشند یعنی COL(i)-COL(j)=|i-k| برقرار باشد .

● روش شاخه و حد

این روش ، شکل اصلاح شده روش عقبگرد می باشد زیرا در روش عقبگرد مجبور به پیمایش تمام گره ها هستیم که بسیاری از آن ها بی مورد است (در روش عقبگرد کل گره هایی که پیمایش می شوند برابرند با : ( [n^(n+۱)-۱]/[(n-۱)] لذا در روش الگوریتم های شاخه و حد ، الگوریتمی پیمایش می شود که شرطی را برآورده سازد ، یعنی ابتدا محاسبه می کنیم که آیا گرهی امیدبخش است و در صورت امید بخش بودن ، آن را پیمایش می کنیم .

توسط محمد کریم رضایی

http://honar-computer.blogfa.com