آموزش طراحی الگوریتم

ویدیو درس طراحی الگوریتم

220,000 تومان

رامین رضوی

۴۰ ساعت مشاهده و ثبت نام

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

320,000 تومان

رامین رضوی

۶۶ ساعت مشاهده و ثبت نام

تاریخچه ای از طراحی الگوریتم

از نظر واژه‌شناسی کلمه الگوریتم از الگوریزم (algorism) به دست آمده که خود از نام ریاضیدان شایسته ایرانی ابوجفعر محمدبن موسی الخوارزمی و به پاس خدمات او به توسعه دانش بشری اقتباس شده است. کلمه «الجبرا» در انگلیسی نیز از روی کتاب مشهور او به نام الجبر و مقابله گرفته شده است. ابوجعفر محمد بن موسی خوارزمی از دانشمندان شهیر ایران است که در نیمه دوم قرن دوم و اوایل قرن سوم هجری شمسی می‌زیسته و در علوم ریاضی و هیأت سرآمد دانشمندان دوران خود بوده است.

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

مقدمه ای از طراحی الگوریتم

امروزه واژه الگوریتم در علوم و مهندسی کامپیوتر معادل روش حل مسأله است. الگوریتم با این دید طراحی می‌گردد که بعد از تبدیل آن به یک زبان برنامه‌ نویسی (مثلا پایتون یا جاوا یا سی) به کامپیوتر داده شود که کامپیوتر آن را اجرا کند. الگوریتم را می‌توان به زبان طبیعی (مثلا نوشتن مراحل الگوریتم به فارسی)، زبانی مشابه زبان‌های کامپیوتری (شبه کد یا همان pseudocode) و حتی به صورت نمودارهای خاصی بیان نمود. بنابراین الگوریتم در این مرحله مستقیماً به وسیله کامپیوتر قابل تفسیر و اجرا نیست، اما پس از تبدیل آن به یک زبان برنامه‌ نویسی برای اجرا به کامپیوتر داده می‌شود. بنابراین توجه کنید که اجرا کننده الگوریتم کامپیوتر است. برای مطالعه بیشتر در مورد طراحی الگوریتم می‌توانید به صفحه ویکی پدیا مراجعه کنید.

زبان‌های کامپیوتری ابزار بیان الگوریتم‌ها برای کامپیوتر هستند و طراحی و بررسی کارایی الگوریتم‌ها برای حل مسائل و شناسایی مسائل قابل حل و غیرقابل حل همه زمینه‌هایی از علوم کامپیوتر می‌باشند که مستقیماً با علم الگوریتم مترادف است

عوامل متعددی بر سرعت اجرای الگوریتم تأثیر دارد، که می‌توان از سرعت کامپیوتر، میزان حافظه اصلی کامپیوتر و از همه مهم‌تر کیفیت الگوریتم نام برد.

برخی از مسائل بدون پیچیدگی هستند و راه‌ حل‌های مشخص و ساده‌ای دارند در حالیکه برای برخی دیگر از مسائل راه‌حل‌های مختلف وجود دارد و در نتیجه الگوریتم‌های متفاوتی می‌توان برایشان طراحی کرد. این الگوریتم‌ها کارایی و کیفیت یکسانی ندارند و از جنبه‌های گوناگون قابل مقایسه می‌باشند. همان‌گونه که توجه به کیفیت در همه زمینه‌ها از اهمیت بالایی برخوردار است، برای الگوریتم‌ها نیز چنین است. اهمیت طراحی و ارائه یک الگوریتم خوب برای مسائل پیچیده و مسائلی که دارای محاسبات زیاد و حجیمی هستند به اوج خود می‌رسد و تا آن‌جا پیش می‌رود که برای یک مسئله مشخص، یک الگوریتم ممکن است کاملاً کاربردی باشد، حال آنکه، الگوریتم دیگری که برای حل همان مسأله طراحی شده است کاملاً بی‌مصرف باشد.

جالب است بدانید که الگوریتم‌های خوب و با کیفیت بالایی که برای حل مسائل وجود دارند اکثرا از ویژگی‌های سادگی و خوانایی نیز برخوردارند. به عبارت دیگر، راه‌‌ حل‌های واقعی مسائل، کارا، قابل فهم و ساده می‌باشند. در یک کلام، کارایی و کیفیت الگوریتم یعنی سادگی، زیبایی و خوانایی آن الگوریتم

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

چه نوع مسئله‌هایی با الگوریتم‌ها حل می‌شوند؟

مرتب سازی داده‌ها تنها مسئله‌ای نیست که الگوریتم‌هایی برای آنها حل شده‌اند، کاربردهای عملی الگوریتم‌ها در همه جا وجود دارند و بسیار گسترده هستند، مثال‌های کمی از کاربرد الگوریتم عبارت‌اند از:

• مطالعه تمامی ژن‌های انسان، شناسایی 100000 ژن در DNA انسان، تعیین دنباله‌ای از 3 میلیارد زوج پایه‌ای شیمیایی DNA انسان، ذخیره این اطلاعات در پایگاه داده‌ها و تولید ابزارهایی برای تحلیل این داده ها از جمله مواردی است که نیازمند الگوریتم‌های حرفه‌ای است، با طراحی کارامد الگوریتم‌هایی برای حل این مسائل در وقت دکترها و دانشمندان این حوزه و همچنین در هزینه‌ها صرفه جویی می‌شود.
• اینترنت افراد مختلف در سراسر جهان را قادر می‌سازد سریعا به حجم زیادی از اطلاعات دستیابی داشته باشند. برای این کار الگوریتم‌های هوشمندی برای مدیریت و دستکاری اطلاعات استفاده شده‌اند. یافتن مسیرهای خوب برای ارسال و دریافت داده‌ها، بهینه سازی موتورهای جستجو برای یافتن هر چه سریعتر صفحاتی که کاربران به دنبال آنها هستند و غیره از جمله مسئله‌هایی است که در دنیای شبکه‌های کامپیوتری و اینترنت وجود دارد.
• تجارت الکترونیک موجب می‌شود کالاها و سرویس‌ها به‌ طور الکترونیکی مبادله شوند. توانایی نگهداری اطلاعاتی مثل شماره کارت اعتباری، کلمه‌های عبور و صورت حساب‌های خصوصی بانک‌ها ضروری هستند. رمزنگاری کلید عمومی (Public Ley Cryptography) و امضاهای دیجیتال (Digital Signature) فناوری‌هایی هستند که استفاده می‌شوند و مبتنی بر الگوریتم‌ها و نظریه اعداد هستند
• خیلی از مواقع در تجارت و همچنین صنعت نیاز است الگوریتم‌هایی ارائه دهیم که بهینه ترین راه ها را برای ما پیدا کند. بعنوان مثال یک شرکت نفتی ممکن است بخواهد بداند در کجاها باید چاه‌های نفت را ایجاد کند تا سودش ماکزیمم شود یا یک کاندیدای ریاست جمهوری ممکن است بخواهد محل‌های مناسبی را برای انجام تبلیغات انتخاباتی خود برای حداکثر کردن شانس برنده شدن اش پیدا کند. یا یک شرکت هواپیمایی ممکن است بخواهد خدمه‌های هواپیما هایش را طوری برای پروازها تعیین کند که کمترین هزینه را داشته باشد و تضمین شود که تمام پروازهایش پوشش داده شوند و همچنین مقررات دولتی در میزان زمان و بازه های مجاز استفاده از خدمه ها رعایت شوند. یا مثلا یک تامین کننده خدمات اینترنت (ISP) ممکن است بخواهد تعیین کند که منابع اضافی را در کجا مستقر نماید تا سرویس‌های اینترنت را بطور کارامد به مشتریان‌اش ارائه دهد.

مطالعه الگوریتم‌ها زمینه‌های متعدد زیر را شامل می‌شود

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

2. معتبرسازی یا اثبات درستی الگوریتم‌ها: یک الگوریتم در صورتی درست است که به ازای هر ورودی مناسب خروجی درستی دهد. بعد از طراحی الگوریتم لازم است نشان داده شود که الگوریتم فوق برای تمامی ورودی‌های مناسب جواب صحیح می‌دهد. هدف این است تا مطمئن شویم که الگوریتم ارائه شده، مستقل از زبان برنامه نویسی خاصی که ممکن است به آن زبان نوشته شود بطور صحیح عمل خواهد کرد.

3. تحلیل و ارزیابی کارایی الگوریتم‌ها:یک الگوریتم در زمان اجرا از cpu کامپیوتر برای اجرای عملیات و از حافظه برای ذخیره سازی برنامه‌ها و داده‌ها استفاده می‌کند. تحلیل الگوریتم‌ها به فرآیندی اطلاق می‌شود که تعیین می‌کند که الگوریتم مزبور به چه مدت زمان از cpu برای انجام محاسبات و عملیات (پیچیدگی زمانی) و به چه مقدار حافظه (پیچیدگی مکانی) برای ذخیره سازی داده‌ها یا برنامه نیاز دارد.

4. پیاده سازی: پس از مرحله معتبرسازی و تحلیل الگوریتم می‌توان آن را با یک زبان برنامه نویسی دلخواه پیاده سازی کرد

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

یک الگوریتم چه ویژگی‌هایی باید داشته باشد

تعریف دقیق‌تری از الگوریتم را می‌توان این گونه ارائه داد:

الگوریتم مجموعه‌ای است از قوانین که به طور دقیق دنباله‌ای از عملیات را برای انجام کاری بیان می‌کند، به گونه‌ای که هر عمل غیرمبهم و قابل انجام بوده و دنبال عملیات در زمانی متناهی قابل اجرا باشد. یک الگوریتم دارای 7 خصوصیت زیر می‌باشد:

1. ورودی (Input):یک الگوریتم می‌تواند چندین کمیت را بعنوان ورودی داشته باشد و یا هیچ ورودی نداشته باشد، یعنی از دنیای بیرون هیچ ورودی دریافت نکند

2. خروجی (Output):یک الگوریتم باید حداقل یک کمیت بعنوان خروجی داشته باشد

3. خاتمه پذیر باشد (Finiteness) یا اجرا شدن در زمان متناهی:پس از اینکه یک زمانی گذشت الگوریتم ما متوقف بشود و خروجی را به ما بدهد و اجرای آن تا بی‌نهایت ادامه پیدا نکند. به طورکلی دستورالعملی که زمان اجرای آن نامتناهی باشد و در نتیجه روشی که جهت اجرای آن به زمان نامتناهی نیاز داشته باشد الگوریتم نامیده نمی‌شود. بعنوان مثال چون ثابت نشده است که مجموعه اعداد اول متناهی است، پس نمی‌توان الگوریتمی تدوین کرد که کلیه اعداد اول را پیدا کند. به عبارت دیگر چنین روشی اگر تدوین گردد الگوریتم نامیده نخواهد شد.

4. درست باشد (Correctness):به ازای هر ورودی جواب درست متناظر با آن ورودی را به ما بدهد

5. غیر مبهم بودن (Definiteness): در الگوریتم هر دستورالعمل باید بدون ابهام باشد و هر دستور العمل یک معنی بیشتر نداشته باشد و کاملا مشخص باشد. مفاهیمی از قبیل خیلی بزرگ، خیلی بلند، خیلی گرم، خیلی سرد، کمی آفتابی، و تا حدودی مسن برای افراد مختلف تفسیرهای متفاوتی دارد. برای کامپیوتر نیز دستورالعملی مانند «اگر مقدار A خیلی زیاد است آن را نصف کن»، مبهم و غیرقابل اجرا می باشد، مگر این که برای خیلی زیاد تفسیر مشخصی ارائه شده باشد. البته اگر الگوریتم را با یک زبان برنامه نویسی پیاده سازی کنیم چون زبان‌های برنامه نویسی ما Formal هستند، به این معنی که هر دستورالعمل یک معنا بیشتر ندارد، خود به خود این شرط برقرار خواهد شد

6. کارا باشد (Effectiveness):برای حل یک مسئله بیش از حد زمان و منابع مصرف نشود و با حداقل منابع سخت افزاری بتوانیم کاری که می‌خواهیم را انجام بدهیم

7. قابلیت تعمیم داشته باشد (Generality): الگوریتم باید بتوانید به ازای همه ورودی ها جواب درست را به ما بدهد نه اینکه فقط به ازای ورودی های خاص پاسخ درست را تولید کند

مراحل حل مسئله در طراحی الگوریتم:‌

مراحل مختلف حل یک مسئله و در واقع نوشتن برنامه بصورت زیر است:

1. تبدیل مسئله به یک مدل ریاضی (مدل انتزاعی) قابل حل توسط کامپیوتر
2. طراحی الگوریتمی برای حل آن مسئله
3. انتخاب داده ساختار(Data Structure) مناسب برای الگوریتمی که ارائه داده‌ایم، برای ذخیره و دستکاری داده های مسئله

مراحل حل مسئله در ساختمان داده و طراحی الگوریتم

تحلیل الگوریتم طراحی شده با توجه به داده ساختار انتخابی از نظر زمان اجرا و حافظه مصرفی برای اندازه‌های مختلف ورودیاگر نتایج تحلیل راضی کننده نباشد، لازم است به مرحله 2 برگردیم و مراحل طراحی الگوریتم و انتخاب داده ساختار مورد نیاز را تکرار کنیم. پس از نهایی شدن الگوریتم می‌توانید با استفاده از یک زبان برنامه نویسی الگوریتم را پیاده سازی کنیم و برنامه اش را بنویسیم (کد زنی کنیم). در زیر سعی می‌کنیم در مورد سه مورد بالا توضیحات بیشتری ارائه دهیم:

نحوه بیان الگوریتم:‌

زبان‌های برنامه‌سازی زیادی برای بیان الگوریتم‌ها طراحی و پیاده‌سازی گردیده‌اند. اغلب یک الگوریتم تا رسیدن به وضعیتی که بتوان آن را به کامپیوتر منتقل نمود مراحل مخلتفی را طی می‌کند. در اولین مرحله الگوریتم به زبان طبیعی (انسانی) تشریح می‌گردد. برای این مرحله، یک مثال ساده می‌تواند مؤثر باشد

مثال: همه ما با روش اقلیدسی به دست آوردن بزرگ‌ترین مقسوم علیه مشترک در عدد طبیعی آشنا هستیم. این روش را می‌توان به صورت زیر مرحله‌بندی کرد.

الف) دو عدد طبیعی را دریافت کن.

ب) اگر دو عدد مساوی هستند، یکی از آن‌ها جواب مسأله است، آن را بنویس و عملیات را متوقف کن.

پ) عدد بزرگ‌تر را بر عدد کوچک‌تر تقسیم کن، خارج قسمت و باقیمانده را پیدا کن.

ت) اگر باقیمانده تقسیم صفر است، مقسوم علیه جواب مسأله است، آن را بنویس و عملیات را متوقف کن.

ث) مقسوم علیه تقسیم قبل را بر باقیمانده آن تقسیم کن و خارج قسمت و باقیمانده را پیدا کن.

ج) عملیات را از مرحله (ت) ادامه بده.

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

فلوچارت پیدا کردم بزرگترین مقسوم علیه مشترک

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

روش های مختلفی که برای طراحی الگوریتم ها وجود دارد:‌

الگوریتم‌ها را با استفاده از روش‌های مختلفی می‌توان طراحی کرد که از جمله آنها می‌توان به موارد زیر اشاره کرد:

1) روش‌های مبتنی بر استقرا

o از جمله مسائلی که الگوریتم اش با استفاده از این روش طراحی می‌شوند عبارت اند از: مسئله ستاره مشهور، مسئله محاسبه درست اعداد فیبوناچی، مسئله کوچکترین دایره محیلی

2) تقسیم و حل (یا تقسیم و غلبه، Divide-and-conquer) : در این روش مسائل را به مسئله‌های کوچکتر تبدیل می‌کنیم، سپس مسئله‌های کوچکتر را حل می‌کنیم و بعد حل‌ این‌ها را با هم ادغام می‌کنیم تا حل مسئله اصلی بدست آید

o از جمله مسائلی که الگوریتم اش با استفاده از این روش طراحی می‌شوند عبارت اند از: مسئله ضرب چند جمله‌ای ها، مسئله ضرب ماتریس‌ها (استراسن)، مسئله محاسبه تعداد وارونگی‌ها، مسئله تورنومنت

3) برنامه نویسی پویا (Dynamic Programing) :در حل برخی از مسائل با روش تقسیم و حل مجبور می‌شویم برخی از زیر مسائل را بارها حل کنیم، برای اجتناب از این موضوع این مسائل را به جای آنکه مانند تقسیم و غلبه از بالا به پایین حل کنیم از پایین به بالا حل می‌کنیم

o از جمله مسائلی که الگوریتم اش با استفاده از این روش طراحی می‌شوند عبارت اند از: مسئله کوله پشتی، مسئله برش چوب، مسئله ضرب ماتریس‌ها، مسئله درخت دودویی جستجوی کمینه، مسئله یافتن بزرگترین زیردنباله مشترک یا همان Longest common subsequence problem(LCS)

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

o از جمله مسائلی که الگوریتم اش با استفاده از این روش طراحی می‌شوند عبارت اند از: مسئله خرد کردن سکه، مسئله کد هافمن، مسئله زمان بندی task ها روی پردازنده

ارزیابی کارایی الگوریتم ها:‌

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

الف) زمان لازم برای اجرای کامل الگوریتم

ب) میزان حافظه لازم در زمان اجرای الگوریتم

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

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

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

1. مرتبه زمانی اجرای کامل الگوریتم

2. مرتبه مکانی اجرای الگوریتم

برای تشریح مرتبه زمانی و مرتبه مکانی عاملی به نام اندازه مسأله باید تشریح گردد. فرض کنید الگوریتمی برای ضرب دو ماتریس مربعی n×n تهیه کرده و آن را به یک زبان کامپیوتری بیان کرده باشیم، روشن است که زمان اجرای آن برای حالتی که 10=n باشد کمتر از زمان اجرای آن روی همان کامپیوتر و همان امکانات برای حالتی که 100=n  باشد خواهد بود. همچنین مکان لازم برای ذخیره ماتریس‌های اولیه و ماتریس نتیجه در حالت اولیه کمتر از حالت دوم خواهد بود. در حالت اول، الگوریتم مسأله‌ای به اندازه کوچک‌تری را نسبت به حالت دوم حل کرده است. در اغلب مسائل زمان اجرای الگوریتم تابعی از اندازه مسأله است. به ندرت مسائلی وجود دارد که زمان اجرای آن‌ها مستقل از اندازه مسأله باشد.

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

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

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

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

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

درس طراحی الگوریتم یکی از دروس گسترده و پیچیده رشته کامپیوتر و آی تی است، برای فهم خوب و کامل طراحی الگوریتم ضروری ‌است که ابتدا برخی از قسمت های درس ساختمان داده خوانده شود. اگر نمی‌خواهید تمام درس ساختمان داده را قبل از درس طراحی الگوریتم مطالعه کنید، بهتر است حداقل قبل از شروع به خواندن درس طراحی الگوریتم بخش های مرتبه زمانی شبه کدها، رشد توابع، توابع بازگشتی و مرتب سازی ها را از درس ساختمان داده مطالعه کنید و بعد به مطالعه درس طراحی الگوریتم بپردازید. درس طراحی الگوریتم سخت و گسترده است و گستردگی درس طراحی الگوریتم به حدی است که خود دانشجویان نمی‌توانند به تنهایی این درس را بخوانند و از پس آن بر بیایند، اما خبر خوب اینکه، درست است که این درس کمی مشکل است اما تست‌های آسانی از آن در کنکور ارشد کامپیوتر و آی تی و همین طور کنکور دکترای کامپیوتر مطرح می‌شود و اگر دانشجویان این درس را بخوانند براحتی می‌توانند به سوالات این درس پاسخ دهند. برای نمونه می‌توانید از قسمت دانلود دفترچه‌های کنکور کامپیوتر، چند دفترچه را دانلود کنید و تست‌های طراحی الگوریتم مطرح شده در سال‌های اخیر را ببینید.
طراحی الگوریتم از اهمیت ویژه ای در کنکور ارشد کامپیوتر و آی تی برخوردار است، زیرا درس طراحی الگوریتم در کنکور ارشد مهندسی کامپوتر جز دروس تخصصی است و در همه گرایش ها یا ضریب 3 دارد و یا ضریب 4 دارد. با توجه به تغییرات اخیر کنکور ارشد مهندسی کامپیوتر هر درس تخصصی در هر گرایش ضریب متفاوتی دارد بنابراین طراحی الگوریتم نیز از این قاعده مستثنی نیست و این درس نیز در گرایش های مختلف دارای ضرایب متفاوتی دارد، برای برسی بیشتر در این مورد حتما به صفحه دروس آزمون کنکور ارشد کامپیوتر و ضرایب آن مراجعه کنید، فعلا مشخص نیست که در کنکور ارشد کامپیوتر چند تست از این درس مطرح می‌شود ولی حدس ما این است که احتمالا 7 تست از درس ساختمان داده و 7 تست نیز از درس طراحی الگوریتم مطرح شود. همچنین در کنکور فناوری اطلاعات نیز 6 تست با ضریب 4، یعنی بالاترین ضریب در کنکور ارشد فناوری اطلاعات از این درس مطرح می‌شود که این تعداد تست با این ضریب بالا خود گویای اهمیت بسیار بالا درس طراحی الگوریتم در کنکور ارشد آی تی است. ساختمان داده و طراحی الگوریتم نه تنها مهم ترین درس در کنکور ارشد کامپیوتر و آی تی است بلکه مهم ترین و تاثیرگذارترین درس در کنکور دکتری رشته های نرم افزار، هوش مصنوعی، شبکه و رایانش و فناوری اطلاعات دانست، برای مشاهده تعداد تست و ضریب درس ساختمان داده و طراحی الگوریتم در کنکور دکتری کامپیوتر می‌توانید به صفحه تعداد سوالات و ضریب دروس در کنکور دکترای کامپیوتر مراجعه کنید.

مراجع درس طراحی الگوریتم

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

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

فیلم های طراحی الگوریتم

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

نمونه فیلم از تدریس درس طراحی الگوریتم

طراحی الگوریتم جلسه 1

طراحی الگوریتم جلسه 2

طراحی الگوریتم جلسه 3

طراحی الگوریتم جلسه 4

طراحی الگوریتم جلسه 5

طراحی الگوریتم جلسه 6

نمایش بیشتر

نمایش کمتر

نظر برخی از رتبه های برتر کنکور ارشد کامپیوتر و آی تی در مورد کیفیت فیلم‌ها