Algorithm Design
Spring 1397
Instructor: Kamal Mirzaie
Description
“To make a computer do anything, you have to write a computer program. To write a computer program, you have to tell the computer, step by step, exactly what you want it to do. The computer then ‘executes’ the program, following each step mechanically, to accomplish the end goal. When you are telling the computer what to do, you also get to choose how it’s going to do it. That’s where computer algorithms come in. The algorithm is the basic technique used to get the job done.”
Algorithm design is a specific method to create a mathematical process in solving problems. Applied algorithm design is Algorithm Engineering. Algorithm design is identified and incorporated into many solution theories of operation research, such as dynamic programming and divide-and-conquer. Techniques for designing and implementing algorithm designs are algorithm design patterns, such as template method pattern and decorator pattern, and uses of data structures, and name and sort lists. Some current day uses of algorithm design can be found in internet retrieval processes of web crawling, packet routing and caching. - From Wikipedia, the free encyclopedia
The study of algorithms is one of the central areas of Computer Science. Algorithmic ideas arise frequently in the several sub-areas within computer science as well as beyond; a small sample of these areas include computer systems and networks, data mining, computer vision, social networks, economics and biology. This course encompasses most aspects of the study of algorithms, though some areas are covered in more detail than others. Algorithm types we will consider include:
- Brute Force Algorithms
- Simple Recursive Algorithms
- Divide and Conquer Algorithms
- Simple Iterative Algorithms
- Dynamic Programming Algorithms
- Greedy Algorithms
- Backtracking Algorithms
- Branch and Bound Algorithms
- Advanced Topics in Algorithm Design
Grading
Your performance will be assessed by assignments, quizzes, class participation and final exam. Their weights are:
- Final Exam: 80%
- Project Report: 20%
Assignments have to be typed, if you want them corrected. All of students must work on assignments individually. The assignments play a crucial part in understanding the course material and must be turned in by class time on the due date for full credit. Participation means coming to class, asking questions, taking part in discussions and so on.
References
Recommended Textbooks
[1] R. Neapolitan , "Foundations Of Algorithms" , 5th Edition, Jones & Bartlett Learning, 2015.
[2] T. Cormen, C. Leiserson, R. Rivest and C. Stein , (CLRS) "Introduction to Algorithms" , Third Edition, MIT press, 2009.
Other References:
[3] Kleinberg and Eva Tardos, "Algorithm Design" , 2006.
[4] G. Brassard and P. Bratley, "Fundamental of Algorithms" , First Edition, Prentice Hall, 1996.
[5] H. S. Wilf, "Algorithms and Complexity" , Internet Edition, Summer, 1994.
[6] Peter Gacs and L. Lovasz, "Complexity of Algorithms" , Lecture Notes, Spring 1999.
[7] Lothaire, "Applied Combinatorics on Words" , 2004.
Films
Useful Links
Dictionaries:
eBooks:
Courses:
Sorts, Searchs:
Peoples:
If you have any comments and suggestions about the class and my teaching course, or you know any links about this course, you can send me a mail. I would really appreciate your feedback. Also, If you happen to find an incorrect or non-functional link, please inform me.
Description - Lectures - Grading - References - Films - Useful Links
Last Update: 96/12/01
:: موضوعات مرتبط:
طراحي الگوريتم ها (کارشناسی)
:: برچسب‌ها:
الگوریتم,
طراحی الگوریتم ها,
آنالیز الگوریتم ها
به نام خدا
بعد از صرف وقت و انرژی برای انجام یک پروژه، تجاربی حاصل می شود که قطعا برای دیگران رهگشا بوده و کار صعب ایشان را اگر نه آسان، لااقل مسیر آن را روشن می سازد. با اینکه در کلاس توضیحات کافی داده می شود اما آنچه اغلب در انجام پروژه طراحی الگوریتم ها مشاهده می شود سردرگمی دانشجویان در انجام پروژه این درس است. شاید دلیل آن ناشناخته ماندن هدف از این درس است. سعی شده است در چند بند و بصورت آموزشی موارد لازم که سوالات بیشتر دانشجویان را شامل می شود به تبیین مراحل و چگونگی انجام پروژه برای این درس پرداخته شود.
1) پروژه خواسته شده شامل موارد زیر است
1. کد برنامه
2. شبه کد برنامه(pseudocode)
3. الگوریتم برنامه
4. تابع پیچیدگی و مرتبه آن :مرتبه یک قطعه کد با توجه به حلقه ها در قطعه کد اصلی برنامه بدست می آید. ممکن است برای مثال تابع پیچیدگی کل کد یک برنامه 12n^3+5n باشد اما قطعه کد اصلی برنامه دارای تابع پیچیدگی 2n^2 باشد. تابع پیچیدگی از روی کد برنامه بدین ترتیب محاسبه می گردد که اگر حلقه ها درون هم باشند گام های حلقه ها، که البته لزوما هم یکسان نیستند، در هم ضرب شده و اگر متوالی باشند گام های حلقه ها با هم جمع می شوند. برای مثال در مثال یاد شده فوق کل برنامه می تواند دارای 12 حلقه for بوده که هرکدام دارای 3 حلقه for تودرتو باشند و نیز دارای 5 حلقه for متوالی باشد. و در قطعه کد اصلی احتمالا فقط 2 حلقه for داریم که هرکدام دارای 2 حلقه for تودرتو می باشند. همچنین واضح است 12n^3+5n از مرتبه n^3 و همچنین 2n^2 از مرتبه n^2 می باشد.
5. منحنی نمودار برنامه: بدین صورت که یک طرف آن ورودی برنامه و طرف دیگر زمان بدست آمده برچسب خواهد خورد. البته مناسب است که نمودار دیگری با استفاده از تابع پیچیدگی رسم گردد تا در صورت درستی تابع، یکسان بودن رشد نمودار دیده شود.( یکبار بصورت شهودی بوسیله عملیات زمانگیری، یکبار بوسیله محاسبات ریاضی).
با بدست آوردن مقادیر می توان در برنامه Excel نمودار آن را به هر طریقی که مورد نظر است(تغییرات یک متغیر یا مقایسه تغییرات چند متغیر) مشاهده کرد. کافیست داده ها را در ستون ها(برای هر متغیر یک ستون) متناظر باهم نوشته و سپس از زبانه Insert و در قسمت Scatter نوع نمودار و شکل آنرا تعین نمود.
6. بررسی شود که برنامه با کدام یک از روش هایی که در کلاس بحث شده، انجام گرفته است.
2) نحوه ی زمانگیری
اصولا زمانگیری دو گونه است:
1. بوسیله تنظیم دستی زمان در برنامه
2. بوسیله ساعت سیستم
ما در اینجا به شرح روش دوم می پردازیم. این روش بدین صورت است که ابتدا تعداد کلاک اجرای برنامه رابدست آورده و بر تعداد کلاک در هر ثانیه تقسیم می کنیم. نتیجه با دقت میلی ثانیه خواهد بود.
در این روش ضمن اضافه کردن تابع کتابخانه ای time.h به ابتدای برنامه، قبل از اجرای قطعه کد اصلی برنامه باید این خط را اضافه نمود:
clock_t start = clock();
و در پایان قطعه کد اصلی برنامه :
printf("\nTime elapsed: %f\n", ((double)clock() - start) / CLOCKS_PER_SEC);
لازم به ذکر دو نکته در استفاده از این قطعه کد است:
یکم اینکه اگر قسمت اول کد از ابتدای برنامه استفاده گردد زمانگیری دقیق نبوده و یا اشتباه خواهد بود. بدین صورت که زمان اضافی شامل مکث کاربر جهت ورودی داده را نیز ثبت خواهد کرد، که این مورد نظر نیست.
دوم اینکه اگر در برنامه خواهان دوبار زمانگیری در یک برنامه باشیم، کافیست نام متغیر زمانگیری را بدین صورت برای بار دوم به بعد تغییر دهیم:
clock_t start1 = clock();
و در چاپ نیز بدین صورت با همان نام ایجاد شده:
printf("\nTime elapsed: %f\n", ((double)clock() – start1) / CLOCKS_PER_SEC);
و همینطور الی آخر برای دیگر زمانگیری ها.
3) تسهیل عملیات زمانگیری
چیزی که بمرور در هنگام زمانگیری با آن مواجه خواهید شد که بنظر خسته کننده می رسد، تکرار دادن ورودی های بزرگ و بزرگتر است ضمن اینکه بطور دقیق نمی دانیم ممکن است چقدر طول بکشد(البته تقریبی آن با تابع پیچیدگی ممکن است). در اینجا راهی که بنظر می رسید این است برنامه را بدین صورت بازنویسی کرد که قطعه اجرایی مورد نظر ما را چند بار در برنامه با ورودی مورد نظرمان تکرار کنیم و در هر بار به روش گفته شده برای زمانگیری های مکرر در یک برنامه، عمل زمانگیری را انجام دهیم. با این روش می توان با یکبار اجرای برنامه بدون نیاز به مراجعات پی در پی، مقصود حاصل می گردد.
اما نکته ای که لازم به توجه است این است که در برنامه هایی که چاپ بدفعات انجام می پذیرد(مثل برج های هانوی) بعد از دومین ورودی بزرگ و چاپ زمان، دیگر اولین زمانگیری قابل رویت نیست. دو راه پیشنهاد می گردد:
راه یکم آنکه چاپ ها را به آخر برنامه موکول کنیم. البته باید زمان هر ورودی را منهای زمان ورودی قبلی بکنیم تا زمان آن مرحله بدست آید.
راه دوم راه متداولتری است. بدین صورت که زمان هر مرحله در متغیری بطور جداگانه ذخیره و در انتها چاپ می کنیم. در یک مثال بطور کامل با این روش آشنا خواهیم شد.
برای قطعه کد زیر می خواهیم عملیات زمانگیری را انجام دهیم:
#include
#include
int main()
{
int n, x;
printf( "How many disks? " );
scanf( "%d", &n );
printf("\n");
for (x=1; x < (1 << n); x++)
printf( "move from tower %i to tower %i.\n",(x&x-1)%3, ((x|x-1)+1)%3 );
getch();
return 0;
}
می خواهیم به ازای مقادیر 14و 15و 16 و17 و18 و 19 برای n عملیات زمانگیری را در یک بار اجرای برنامه انجام دهیم.با تغییرات گفته شده که در کد برنامه ایجاد می کنیم برنامه بصورت زیر درخواهد آمد:
#include
#include
#include
int main()
{
int n, x;
float t,t1,t2,t3,t4,t5; //متغیرها برای هرکدام از زمانگیری ها
n=14;
clock_t start = clock();
for (x=1; x < (1 << n); x++)
printf( "move from tower %i to tower %i.\n",(x&x-1)%3, ((x|x-1)+1)%3 );
t=(((double)clock() - start) / CLOCKS_PER_SEC); // ذخیره زمان برای ورودی14
n=15;
clock_t start1 = clock();
for (x=1; x < (1 << n); x++)
printf( "move from tower %i to tower %i.\n",(x&x-1)%3, ((x|x-1)+1)%3 );
t1=((double)clock() - start1) / CLOCKS_PER_SEC; // ذخیره زمان برای ورودی15
n=16;
clock_t start2 = clock();
for (x=1; x < (1 << n); x++)
printf( "move from tower %i to tower %i.\n",(x&x-1)%3, ((x|x-1)+1)%3 );
t2=((double)clock() - start2) / CLOCKS_PER_SEC; // ذخیره زمان برای ورودی16
n=17;
clock_t start3 = clock();
for (x=1; x < (1 << n); x++)
printf( "move from tower %i to tower %i.\n",(x&x-1)%3, ((x|x-1)+1)%3 );
t3=((double)clock() - start3) / CLOCKS_PER_SEC; // ذخیره زمان برای ورودی17
n=18;
clock_t start4 = clock();
for (x=1; x < (1 << n); x++)
printf( "move from tower %i to tower %i.\n",(x&x-1)%3, ((x|x-1)+1)%3 );
t4=((double)clock() - start4) / CLOCKS_PER_SEC; // ذخیره زمان برای ورودی18
n=19;
clock_t start5 = clock();
for (x=1; x < (1 << n); x++)
printf( "move from tower %i to tower %i.\n",(x&x-1)%3, ((x|x-1)+1)%3 );
t5=((double)clock() - start5) / CLOCKS_PER_SEC; // ذخیره زمان برای ورودی19
printf("\nTime elapsed: %f\n", t); // چاپ زمان ها بترتیب
printf("\nTime elapsed: %f\n", t1);
printf("\nTime elapsed: %f\n", t2);
printf("\nTime elapsed: %f\n", t3);
printf("\nTime elapsed: %f\n", t4);
printf("\nTime elapsed: %f\n", t5);
getch();
return 0;
}
که نتیجه اجرای مطابق شکل زیر است
راه سوم راه بهتر و حرفه ای تر بوده ضمن آنکه بدین دلیل که معمولا زمانگیری عملی طولانی خواهد بود، ممکن است در حین انجام این عمل برنامه به هر دلیل متوقف شود و زمانگیری های انجام شده قبلی نیز از بین بروند، بهتر است از فایل در برنامه استفاده شود. بدین صورت که بعد از هربار چاپ، زمانگیری انجام شده در فایل متنی ذخیره گردد. بدین ترتیب زمانگیری تا مرحله انجام شده محفوظ خواهد بود.
4) عموما برنامه هایی که توسط خود دانشجویان نوشته می شود بدون توجه به این موضوع انجام می گیرد که در هنگام زمانگیری نیاز به دادن ورودی های بسیار بزرگ نیز وجود دارد. و این بی توجهی باعث بروز خطاهایی مانند سرریز(overflow) می شود. بهتر است از ابتدا برنامه ها را بصورت پویا و با استفاده از آرایه پویا یا پشته(تابع بازگشتی هم از پشته استفاده می کند) انجام داد.
همچنین باید این موضوع برای دانشجویان روشن شود که همه برنامه ها لزوما برای محیط آزمایشی تدریس نیستند. یعنی واقعا می شود برنامه هایی داشت با توان قبول ورودی های بسیار بسیار بزرگ که به درستی جواب می دهند.
5) مکث در هنگام چاپ
برنامه ها با ساختمان داده هایی که ابتدا محاسبات باید کامل انجام شود سپس چاپ در خروجی انجام پذیرد در هنگام دادن ورودی های بزرگ برای چاپ با مکث مواجه می شویم. گاهی این مکث بسیار طولانی می شود. اما برنامه هایی که از پشته و یا تابع بازگشتی بنحوی استفاده می کنند بدین صورت که در هر بار بازگشت چاپ داریم این مکث را ندارند. چون زمان محاسبات بین چاپ ها تقسیم شده و محسوس نیست.
6) چگونه ورودی بزرگ برای برنامه با ورودی های ترتیبی وارد کنیم؟
وقتی برنامه ای با آرایه پویا می نویسیم که توانایی گرفتن تا حتی یک میلیون عدد را داشته و محاسباتی انجام می دهد با این سوال مواجه می شویم که چطور ورودی ها را بدهیم؟
پاسخ در تابع رندوم است. به این صورت که برای هر خانه ی آرایه یک عدد رندوم تولید کرده و آنرا درون آن خانه می ریزیم. نحوه کار بدین ترتیب است:
printf("kafe maghadir:");//برای انتخابی کردن کف و سقف مقادیر رندوم که داخل آرایه پویا می ریزیم
printf("saghfe maghadir:");
srand(time(0)); //برای اینکه اعداد تصادفی تولید شده در هر بار متفاوت باشد
for (i = 0; i < n; i++ )// ایجاد اعداد رندوم به تعداد ورودی خواسته شده
int rand100 = rand()%(b-a+1)+a;
*(z+i)=rand100; //قرار دادن هر مقدار تولید شده در یک خانه از آرایه پویا که از اشاره گر استفاده شده
قطعه کد فوق در ابتدا بازه تولید اعداد رندوم را از کاربر گرفته و کمترین را در a و بیشترین را در b قرار می دهد. سپس با استفاده از تابع رندوم و کف و سقفی که به آن داده ایم آماده ایجاد اعداد رندوم به تعداد عناصر آرایه پویای z است. در حلقه هربار عدد رندوم در بازه داده شده تولید شده و بترتیب به عناصر آرایه پویا نسبت داده می شود.
اعداد رندوم بصورت پیشفرض در هر بار یکسان تولید می شوند. در صورت تمایل برای ایجاد اعداد تصادفی متنوع در هر بار باید ایجاد کننده اعداد تصادفی( random seed ) تغییر کند. بنابراین از تابع srand(int seed) استفاده شده است. که میتوان مقدار seed را در هربار از کاربر پرسید تا هربار اعداد تولید شده متفاوت باشند. اما راه بهتر برای تولید اعداد تصادفی متفاوت آن است که seed را بوسیله ساعت سیستم یعنی با time(0) در هربار متمایز کنیم، بدون آنکه لازم باشد از کاربر بخواهیم.
7) طرح یک سوال:
چرا چاپ؟
چرا در زمانگیری باید چاپ داشته باشیم؟ آیا واقعا چاپ لزومی دارد؟
بسیاری از برنامه ها اصلا چاپ های متوالی ندارند و حتی برای ورودی های بسیار بزرگ هم محاسبات آن بیش از چند دقیقه بطول نخواهد انجامید.
بعنوان مثال در برنامه های برجهای هانوی درصورتی که چاپ متوالی حرکات دیسک را نداشته باشیم براحتی تا حدود 40 دیسک را در مرز دقیقه خواهیم داشت. درحالیکه با چاپ برای 27 دیسک در بهترین حالت(الگوریتم دودویی) 7 ساعت و 20 دقیقه طول می کشد. مشخص است که اکثر زمان مربوط به عمل چاپ کردن است. چاپ کردن چه ارزشی دارد؟ اصلا ارزشی در محاسبات زمانگیری الگوریتم ها دارد؟
برای آزمایش تغییر جزئی در برنامه ایجاد می کنیم. \n های پایان printf ها را برداشته و عبارت توضیحی چاپ را کوتاه می کنیم. نتیجه بسیار تامل برانگیز است. در حالت قبلی برای 22 دیسک زمان در الگوریتم بازگشتی 1، زمان 836.609 ثانیه ثبت شده است. اما در حالتی که تغییرات یاد شده اعمال گشته زمانگیری عدد 629.766 ثانیه را نشان می دهد.
بنظر می رسد بهتر است اگر برنامه قابلیت محاسبه ورودی های بسیار بالا را دارد، یا از چاپ صرفه نظر شود یا عبارت چاپ در نهایت کوتاهی انجام شود تا فقط صحت برنامه آزمایش گردد. در هر حال منحنی ورودی- زمان تغییر محسوسی نخواهد داشت. بدین ترتیب زمان کمتری صرف زمانگیری خواهد شد.
8) این پست یا ابه اصطلاح راهنما باز گذاشته می شود تا تجربیات ارزشمند دیگر دوستان در ادامه آن ثبت گردد. بارزترین نکته آنکه از زبان c بعنوان پایه استفاده شده است اما در این درس از زبان های برنامه نویسی دیگر نیز می توان استفاده کرد. امید است بمرور بدل به راهنمای جامع و کاملی گردد تا دانشجویان بطور کامل از اطلاعات مفید آن بهره کافی ببرند.
بازدیدکنندگان این پست می توانند نظرات تکمیلی خود را از طریق نظرات همین پست، ارسال کنند.
علی آیت اللهی نصرآبادی
:: موضوعات مرتبط:
طراحي الگوريتم ها (کارشناسی)
