ویدیو درس طراحی الگوریتم
تخفیف سه ماه طلایی تا ۳ آبان
30%ویدیو نکته و تست ساختمان داده و طراحی الگوریتم
تخفیف سه ماه طلایی تا ۳ آبان
30%تاریخچه ای از طراحی الگوریتم
از نظر واژهشناسی کلمه الگوریتم از الگوریزم (algorism) به دست آمده که خود از نام ریاضیدان شایسته ایرانی ابوجفعر محمدبن موسی الخوارزمی و به پاس خدمات او به توسعه دانش بشری اقتباس شده است. کلمه «الجبرا» در انگلیسی نیز از روی کتاب مشهور او به نام الجبر و مقابله گرفته شده است. ابوجعفر محمد بن موسی خوارزمی از دانشمندان شهیر ایران است که در نیمه دوم قرن دوم و اوایل قرن سوم هجری شمسی میزیسته و در علوم ریاضی و هیأت سرآمد دانشمندان دوران خود بوده است.
او بنیانگذار علم جبر در دنیا میباشد. اگر چه قبل از خوارزمی دانشمندان یونانی در زمینه جبر کارهای ابتدایی انجام داده بودند، لیکن اهمیت کارهای آنها در مقابل پژوهشهای خوارزمی ناچیز ارزیابی شده است. کلمه الگوریتم به افتخار خوارزمی و اهمیت کارهای او، به ویژه در تدوین روشهای سازمانیافته حل پارهای از مسائل عددی انتخاب گردیده است.
مقدمه ای از طراحی الگوریتم
امروزه واژه الگوریتم در علوم و مهندسی کامپیوتر معادل روش حل مسأله است. الگوریتم با این دید طراحی میگردد که بعد از تبدیل آن به یک زبان برنامه نویسی (مثلا پایتون یا جاوا یا سی) به کامپیوتر داده شود که کامپیوتر آن را اجرا کند. الگوریتم را میتوان به زبان طبیعی (مثلا نوشتن مراحل الگوریتم به فارسی)، زبانی مشابه زبانهای کامپیوتری (شبه کد یا همان pseudocode) و حتی به صورت نمودارهای خاصی بیان نمود. بنابراین الگوریتم در این مرحله مستقیماً به وسیله کامپیوتر قابل تفسیر و اجرا نیست، اما پس از تبدیل آن به یک زبان برنامه نویسی برای اجرا به کامپیوتر داده میشود. بنابراین توجه کنید که اجرا کننده الگوریتم کامپیوتر است. برای مطالعه بیشتر در مورد طراحی الگوریتم میتوانید به صفحه ویکی پدیا مراجعه کنید.
زبانهای کامپیوتری ابزار بیان الگوریتمها برای کامپیوتر هستند و طراحی و بررسی کارایی الگوریتمها برای حل مسائل و شناسایی مسائل قابل حل و غیرقابل حل همه زمینههایی از علوم کامپیوتر میباشند که مستقیماً با علم الگوریتم مترادف است
عوامل متعددی بر سرعت اجرای الگوریتم تأثیر دارد، که میتوان از سرعت کامپیوتر، میزان حافظه اصلی کامپیوتر و از همه مهمتر کیفیت الگوریتم نام برد.
برخی از مسائل بدون پیچیدگی هستند و راه حلهای مشخص و سادهای دارند در حالیکه برای برخی دیگر از مسائل راهحلهای مختلف وجود دارد و در نتیجه الگوریتمهای متفاوتی میتوان برایشان طراحی کرد. این الگوریتمها کارایی و کیفیت یکسانی ندارند و از جنبههای گوناگون قابل مقایسه میباشند. همانگونه که توجه به کیفیت در همه زمینهها از اهمیت بالایی برخوردار است، برای الگوریتمها نیز چنین است. اهمیت طراحی و ارائه یک الگوریتم خوب برای مسائل پیچیده و مسائلی که دارای محاسبات زیاد و حجیمی هستند به اوج خود میرسد و تا آنجا پیش میرود که برای یک مسئله مشخص، یک الگوریتم ممکن است کاملاً کاربردی باشد، حال آنکه، الگوریتم دیگری که برای حل همان مسأله طراحی شده است کاملاً بیمصرف باشد.
جالب است بدانید که الگوریتمهای خوب و با کیفیت بالایی که برای حل مسائل وجود دارند اکثرا از ویژگیهای سادگی و خوانایی نیز برخوردارند. به عبارت دیگر، راه حلهای واقعی مسائل، کارا، قابل فهم و ساده میباشند. در یک کلام، کارایی و کیفیت الگوریتم یعنی سادگی، زیبایی و خوانایی آن الگوریتم
در علوم کامپیوتر شناخت مسائل و تدوین الگوریتم آنها تا حدی اهمیت دارد که برخی از دانشمندان کامپیوتر، علوم کامپیوتر را معادل مطالعه الگوریتمها میدانند. آنها میگویند معماری و ساخت کامپیوتر همان شناخت، طراحی و پیادهسازی ماشینهایی است که قادرند الگوریتمها را اجرا کنند
درس طراحی الگوریتم
درس طراحی الگوریتم زیربنای علم برنامه نویسی است و یادگیری درست و کامل آن شما را به یک مهندس کامپیوتر متخصص و حرفهای تبدیل خواهد کرد. به همین علت درس طراحی الگوریتم یکی از دروس مهم مهندسی کامپیوتر است و به طور معمول در ترم 4 مقطع کارشناسی ارائه میشود. این درس به اندازهای مهم و حیاتی است که اگر دانشجویی در مقطع کارشناسی ارشد از رشته تحصیلی دیگری به یکی از گرایشهای مهندسی کامپیوتر وارد شده باشد، قطعاْ این درس را باید بعنوان درس جبرانی بگذراند. درس طراحی الگوریتم بعنوان یکی از دروس تخصصی منابع کنکور ارشد مهندسی کامپیوتر و آی تی محسوب میشود و به دلیل داشتن ضریب بالا میتواند رتبه شما را به طور قابل توجهی جابهجا کند. برای بررسی بیشتر اهمیت درس طراحی الگوریتم میتوانید به کارنامه های کنکور ارشد کامپیوتر و IT مراجعه نمایید.
پیشنیاز درس طراحی الگوریتم
از آنجا که درس طراحی الگوریتم درباره چگونگی حل مسائل مختلف است و به دنبال پیدا کردن راه حلی مناسب و بهینه برای آنهاست لذا به مهارتهای حل مسئله و هوش محاسباتی در افراد نیاز دارد. به همین دلیل دروس ریاضیات را میتوان به عنوان اصلیترین پیش نیاز درس طراحی الگوریتم دانست. حل مسائل پیچیده و مختلف در دروس ریاضی به پرورش فکر و تمرین دادن مغز کمک کرده و موجب میشود که روزبه روز خلاقتر عمل کنید. در طراحی الگوریتمها داشتن خلاقیت یکی از مهارتهای اصلی محسوب شده بطوریکه در مواقع رسیدن به بن بست همیشه یک راه حل مناسب به ذهنتان رسیده و شما را نجات خواهد داد.
درس طراحی الگوریتم چه پیشنیازهایی در دانشگاه دارد؟
در چارت درسی ارائه شده از سوی دانشگاهها،درس ساختمان داده بعنوان پیش نیاز درس طراحی الگوریتم در نظر گرفته شده است. توصیه میشود به دلیل پیوستگی مطالب، در ابتدا درس ساختمان داده را یاد بگیرید و بعد آموزش درس طراحی الگوریتم را شروع کنید و از برداشتن این دو درس به صورت همزمان (در موارد استثناء) خودداری نمایید.
درس طراحی الگوریتم پیشنیاز چه درسهایی در دانشگاه است؟
برای اخذ درس هوش مصنوعی (3 واحدی) لازم است که درس طراحی الگوریتم را بعنوان پیشنیاز گذرانده باشید. از آنجا که رشته هوش مصنوعی(AI) در خصوص بکارگیری الگوریتمها و روشهای پیچیده برای ساخت ماشینهای خودمختار(بتوانند به تنهایی تصمیم بگیرند) است، بنابراین یادگیری دقیق و صحیح درس طراحی الگوریتم ضروری میباشد. شما عزیزان میتوانید برای آشنایی بیشتر با مباحث هوش مصنوعی به مقاله هوش مصنوعی چیستهوش مصنوعی (AI) چیست؟ انواع، کاربردها، مزایا و معایبهوش مصنوعی یا Artificial Intelligence یا به اختصار AI، امروزه کاربردهای بسیاری پیدا کرده و به یکی از داغترین حوزههای بشر تبدیل شده است، اما با این وجود بسیاری از افراد با کاربردهای آن آشنایی کامل ندارند، به همین علت در این صفحه کاربردها، مزایا و معایب AI بطور کامل بررسی شده است در سایت کنکور کامپیوتر مراجعه نمایید.
فصلهای طراحی الگوریتم
سر فصل مطالبی که در درس طراحی الگوریتم مطرح میشود عبارت است از: تقسیم و غلبه، آنالیز استهلاکی، گراف، الگوریتمهای حریصانه، برنامه نویسی پویا، شبکه شار، نظریه NP، مجموعه های مجزا. البته مطالب دیگری مانند بدست آوردن مرتبه زمانی شبه کدها، بازگشتیها، درختها و ... وجود دارد که چون آنها بطور مفصل در درس ساختمان داده بررسی میشوند آنها را در اینجا بیان نکردیم. همین طور شما دانشجویان عزیز میتوانید برای مشاهده اهمیت فصل های طراحی الگوریتم و اینکه در سالهای اخیر از هر فصل چه تعداد تست مطرح شده به قسمت بودجهبندی سوالات کنکور ارشد مهندسی کامپیوتر و همچنین بودجه بندی سوالات کنکور ارشد فناوری اطلاعات مراجعه کنید.
- تحلیل الگوریتمها و زمانهای اجرا
- الگوریتم استراسن برای ضرب ماتریسها
- فشرده سازی : کد هافمن
- ضرب زنجیرهای ماتریسها، کوله پشتی
- بزرگترین زیر دنباله مشترک، بزرگترین زیر دنباله افزایشی
- درخت دودویی جست و جوی بهینه
- هرم فیبوناچی
- کوتاهترین مسیر بین تمام راسها، الگوریتمهای فلوید، وارشال و جانسون
- بهبود الگوریتم فورد‐فالکرسن، بهبودهای ادموندز و کارپ
- رده ی ان پی، اثبات ان پی ‐تمام بودن یک مسئله، قضیه ی کوک
- دور همیلتنی، رنگ آمیزی گراف، مجموع زیرمجموعه ها
- پشتههای باینومیال
- پشتههای فیبوناچی
مراجع درس طراحی الگوریتم
مرجع اصلی که برای طراحی الگوریتم در دانشگاههای معتبر تدریس میشود کتاب CLRS است، همچنین کتابهای Jeff_erickson، Kleinberg و sedgewick نیز در برخی از دانشگاههای ایران و جهان تدریس میشود، در زیر کتاب های مرجع طراحی الگوریتم را برای شما عزیزان قرار داده ایم تا براحتی بتوانید آنها را دانلود و از آنها استفاده کنید. برای دانلود سایر کتاب های مرجع رشته کامپیوتر به قسمت دانلود کتابهای رفرنس مهندسی کامپیوتر و فناوری اطلاعات دانلود کنید. البته خواندن کتابهای رفرنس به دانشجویانی که قصد شرکت در کنکور ارشد و دکتری کامپیوتر و آی تی را دارند زیاد توصیه نمیشود، دلیل این موضوع را نیزمیتوانید در قسمت پاسخ صوتی به سوالات متداول بیابید. دانشجویانی که قصد دارند برای کنکور این درس را بخوانند میتوانند از منابعی که در قسمت معرفی منابع ارشد مهندسی کامپیوتر معرفی شده استفاده کنند، گرچه در این درس کتاب کنکوری که کامل و بسیار روان باشد و نیاز تمامی دانشجویان با پایههای درسی مختلف را برآروده کند وجود ندارد ولی سعی شده از بین کتابهای موجود بهترینها را به شما عزیزان معرفی کنیم
کتاب های طراحی الگوریتم
چه نوع مسئلههایی با الگوریتمها حل میشوند؟
مرتب سازی دادهها تنها مسئلهای نیست که الگوریتمهایی برای آنها حل شدهاند، کاربردهای عملی الگوریتمها در همه جا وجود دارند و بسیار گسترده هستند، مثالهای کمی از کاربرد الگوریتم عبارتاند از:
- مطالعه تمامی ژنهای انسان، شناسایی 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): الگوریتم باید بتوانید به ازای همه ورودی ها جواب درست را به ما بدهد نه اینکه فقط به ازای ورودی های خاص پاسخ درست را تولید کند
مراحل حل مسئله در طراحی الگوریتم:
مراحل مختلف حل یک مسئله و در واقع نوشتن برنامه بصورت زیر است:
- تبدیل مسئله به یک مدل ریاضی (مدل انتزاعی) قابل حل توسط کامپیوتر
- طراحی الگوریتمی برای حل آن مسئله
- انتخاب داده ساختار(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، یعنی بالاترین ضریب در کنکور ارشد فناوری اطلاعات از این درس مطرح میشود که این تعداد تست با این ضریب بالا خود گویای اهمیت بسیار بالا درس طراحی الگوریتم در کنکور ارشد آی تی است. ساختمان داده و طراحی الگوریتم نه تنها مهم ترین درس در کنکور ارشد کامپیوتر و آی تی است بلکه مهم ترین و تاثیرگذارترین درس در کنکور دکتری رشته های نرم افزار، هوش مصنوعی، شبکه و رایانش و فناوری اطلاعات دانست، برای مشاهده تعداد تست و ضریب درس ساختمان داده و طراحی الگوریتم در کنکور دکتری کامپیوتر میتوانید به صفحه تعداد سوالات و ضریب دروس در کنکور دکترای کامپیوتر مراجعه کنید.
فیلم های طراحی الگوریتم
با توجه به سخت بودن درس طراحی الگوریتم و تعداد تستهای زیاد این درس به دانشجویان توصیه میشود حتما برای این درس فیلم های طراحی الگوریتم را تهیه کنند، در این فیلم ها بسیار روان و با زبان ساده تمامی مباحث طراحی الگوریتم بیان شده است. البته چون درس ساختمان داده پیش نیاز طراحی الگوریتم است و برای یادگیری خوب و کامل درس طراحی الگوریتم نیاز است تا دانش بسیاری از درس ساختمان داده داشته باشید، بنابراین سعی کنید ابتدا فیلم های درس ساختمان داده را مشاهده کنید و سپس فیلم های درس طراحی الگوریتم را مشاهده کنید. در زیر دو نمونه از فیلم های تدریس طراحی الگوریتم گذاشته شده است تا بتوانید کیفیت بالای فیلم را مشاهده کنید، برای مشاهده نمونه فیلم های رایگان بیشتر طراحی الگوریتم به قسمت فیلمهای طراحی الگوریتم مراجعه کنید.
نمونه فیلم از تدریس درس طراحی الگوریتم
طراحی الگوریتم جلسه 1
طراحی الگوریتم جلسه 1
طراحی الگوریتم جلسه 2
طراحی الگوریتم جلسه 3
طراحی الگوریتم جلسه 4
طراحی الگوریتم جلسه 5
طراحی الگوریتم جلسه 6
نظر برخی از رتبه های برتر کنکور ارشد کامپیوتر و آی تی در مورد کیفیت فیلمها
نظر رتبه 1 کنکور
نظر رتبه 2: خیلی کامل بودند
نظر رتبه 6 کنکور ارشد کامپیوتر
نظر رتبه 6 کنکور 1400
فیلم ها خیلی قابل فهم و روان است
رتبه 9 :فیلم ها بی نقص بود
از پایه ضعیف تا شریف
نظر رتبه 2 کنکور ارشد
نطر رتبه 10: کیفیت تدریس استاد رضوی خیلی خوبه
نظر رتبه 16: کیفیت تدریس خیلی عالی بود
جزوه کامل و ویدیوهای خیلی خوب
نحوه انتقال دانش استاد رضوی بینظیر است
ویدیوها خیلی جامع و کامل بودند
واقعا تدریس اساتید عالی بودند
نظر رتبه 8 کنکور 1400
نظر رتبه 2: معماری کامپیوتر و منطقی 100 زدم
نظر رتبه 13 کنکور ارشد کامپیوتر 1401
نظر رتبه 19: تدریس و فن بیان عالی است
نظر رتبه 12 کنکور ارشد کامپیوتر 1401
نظر رتبه 24: خیلی کامل و جامع است
فیلمها بی نظیر بود
نظر رتبه 45: کیفیت فیلم ها خوب بودن
همه دروس عالی تدریس شده بودند
نیار نیست کتاب تهیه کنید
فیلم ها با بیان شیوا و بدون ابهام بود
کیفیت بالا و هزینه مناسب
نظر رتبه 11 کنکور 1400
فیلمها بینیازم کرد
تدریس زیبا و بیان شیوا
فیلم درس و تست کافیست
فیلم های استاد رضوی از همه نظر عالی بودند
کیفیت و نحوه تدریس و قدرت بیان اساتید از همه نظر خوب بود
خیلی راضی بودم درسها خیلی عمیق تدریس میشد
از همه دروس خیلی راضی بودم
نظر پارسا شریعت
ویدیوها از نظر کیفیت عالی بودند
نظر رتبه 43 کنکور
از دروس استاد رضوی خیلی راضی بودم
نظر پیمان هاشمی
نظر رتبه 40 کنکور
تدریس از 0 تا 100
فیلم شما را جلو میاندازد
نظر رتبه 50 کنکور 1400
نظر رتبه 67 کنکور 1400
نظر ریحانه حسین زاده
نظر مرتضی اکبری
نظر رتبه 113 کنکور 1400
تاثیر منابع خوب
نظر سامان حسینی
تفاوت منابع مناسب
نظر رتبه 32 کنکور 1400
کیفیت بالا تدریس
نظر شیوا رضازاد
از روی مراجع نخوانید
فیلم ها خیلی مفهومی بودند
همه درس ها فوق العاده بود
از صفر تا صد و کامل هستند
آشنایی با استاد رضوی و کافه تدریس معجزه بود
فیلم ها جامع بودند
کل منابع من از کافه تدریس یا کنکور کامپیوتر بود
دروس واقعا فوق العاده بودند
درسها کامل و روان است
فیلم ها خیلی دقیق و جامع و کامل بودند
ویدیوها بسیار قابل فهم بودند
مطالبی که پوشش داده شده بود واقعا کامل بود
تدریس بسیار شیوا و روان و بدون ابهام
با پایه ضعیف هم فیلم ها را متوجه می شوید
فیلم ها خیلی به من کمک کرد
همه دروس را از کافه تدریس گرفتم
ویدیوهاشون خیلی به من کمک کرد
معرفی دوره درس و حل تست طراحی الگوریتم
درس ساختمان داده و طراحی الگوریتم بنیادی ترین درس رشته کامپیوتر و حتی یکی از بنیادی ترین درسهای بسیاری رشتههای علوم پایه و مهندسی است. اهمیت این درس از این حیث است که این درس نه تنها در کنکور ارشد کامپیوتر و آی تی و همچنین کنکور دکتری کامپیوتر تعداد تست بالایی را به خودش اختصاص داده بلکه این درس مهم ترین تاثیر را در آینده پژوهشی دانشجویان چه در ارشد و چه در دکتری و چه پس از آن نیز خواهد داشت، شما هیچ مقاله ای را در دنیای کامپیوتر پیدا نمیکنید که الگوریتمی در آن ارائه نشده باشد و با توجه به این کار دانشجویان ارشد و دکتری نیز همین پژوهش و مقاله دادن است برای فردی که میخواهد در این راه قدم بگذارد و در این راه موفق باشد بسیار مهم است که روی درس ساختمان داده و طراحی الگوریتم مسلط باشد.
متاسفانه در اکثر دانشگاههای کشور چندین مشکل در ارائه این درس وجود دارد
- مشکل اول این است که در دانشگاهها سر فصلی که وزارت علوم برای کنکور اعلام کرده بطور کامل تدریس داده نمیشود و یا اگر درس داده میشود بصورت روان و به نحوی که همه دانشجویان به سادگی متوجه شوند درس داده نمیشود، که اتفاقا اکثر سوالات نیز از همین مباحث است.
- مشکل دوم این است همان مباحثی هم که تدریس میشود بصورت 0 تا 100 و با جزییات زیاد و بصورت کنکوری تدریس داده نمیشود و بنابراین دانشجویان توانایی حل تستهای کنکور را پیدا نمیکنند.
از نگاه دانشجویان، قدرت بیان فوق العاده استاد رضوی و پوشش ۱۰۰ درصدی تمامی سرفصلها، نکات و تستها، ویدیوهای درس طراحی الگوریتم را به بهترین ویدیو آموزشی کشور در درس طراحی الگوریتم تبدیل کرده است. در حال حاضر فیلم آموزش طراحی الگوریتم استاد رضوی پرطرفدارترین و پرفروشترین طراحی الگوریتم کشور است و هر سال بیش از ۶۰۰۰ نفر این فیلم را تهیه میکنند، آموزش طراحی الگوریتم به زبان ساده و صفر تا صد دلیل محبوبیت آموزش طراحی الگوریتم است. در فیلمهای طراحی الگوریتم تهیه شده بر خلاف فیلمهای مشابه این فرض در نظر گرفته نشده که دانشجویان باید یکسری از مطالب را از قبل بلد باشند و همه چی از صفر توضیح داده شده است، به همین علت، تمامی دانشجویان با هر پایه و سطحی که دارند میتوانند از این فیلم بیشترین بهره را ببرند، حتی دانشجویانی که رشته لیسانس شان کامپیوتر نبوده است براحتی میتوانند از این فیلم استفاده کنند و درس طراحی الگوریتم را بصورت عمیق و مفهومی فرا گیرند.
دانشجویان عزیز توجه کنند که برای تهیه فیلم های طراحی الگوریتم نیاز به هیچ پیش نیازی ندارند و هر پیش نیازی که نیاز باشد در فیلم های الگوریتم داده گفته شده است.
درس ساختمان داده و طراحی الگوریتم درس حجیمی است و برای به تسلط رسیدن در این درس نیاز است ابتدا این درس را بصورت مفهومی و عمیق مطالعه کنید و سپس تعداد تست زیادی را حل کنید. در نکته و تست ساختمان داده و طراحی الگوریتم حدود 430 تست مفهومی کنکور ارشد کامپیوتر و آی تی و علوم کامپیوتر و همین طور کنکور دکتری بطور کامل بررسی شده است. تمامی نکات مطرح شده در کنکور ارشد و دکتری، به طور کامل و با چندین مرحله تکرار در فیلم های نکته و تست بیان شده اند
رامین رضوی
RAMIN RAZAVI
ایشان تا قبل از سال 94 بصورت حضوری در شهر تهران و بصورت پروازی در شهرهای مشهد، شیراز، اصفهان، گرگان و ... برای کنکور مقطع ارشد و دکتری تدریس میکردهاند، سپس در سال 94 با توجه به درخواستهای مکررِ شهرهای دیگر برای برگزاری کلاسهای آمادگی کنکور ارشد و دکتری تصمیم گرفت در جهت رفع کمبود امکانات آموزشی در شهرهای کوچک، برای اولین بار در کشور اقدام به برگزاری دورههای آموزشی آنلاین کند که ماحصل آن برقراری عدالت آموزشی طی این سالها و شرکت بیش از 24000 دانشپژوه در کلاسهای آنلاین ایشان و برگزاری 267 دوره آنلاین توسط ایشان بوده است.
در حال حاضر بیش از 90 درصد از رتبههای برتر کنکور ارشد کامپیوتر و آیتی هر سال از دانشجویان استاد رضوی هستند که این درصد موفقیت نه تنها در رشته کامپیوتر بلکه در هیچ رشته دیگری وجود نداشته است.
سرفصلهای دوره آموزشی طراحی الگوریتم
برای درس طراحی الگوریتم دو فیلم زیر وجود دارد
- فیلم درس طراحی الگوریتم
- فیلم حل تست و سوالات طراحی الگوریتم
ویدیو درس طراحی الگوریتم
تخفیف سه ماه طلایی تا ۳ آبان
30%ویدیو نکته و تست ساختمان داده و طراحی الگوریتم
تخفیف سه ماه طلایی تا ۳ آبان
30%در زیر سرفصلهای دوره طراحی الگوریتم با جزئیات آورده شده است، در زیر مشخص شده است که فیلم آموزش طراحی الگوریتم و همین طور حل تست طراحی الگوریتم چند جلسه است و هر جلسه چند ساعت است و شامل چه بخشها و مباحثی است:
بخش 1
1:50'الگوریتمهای تقسیم و غلبه - بررسی مرتبسازی درجی و مرتبسازی سریع - الگوریتم ضرب دو ماتریس
بخش 2
1:15'روش استراسن در ضرب دو ماتریس - مرتبه ی روش استراسن
بخش 1
1:20'یافتن Min یا Max در آرایه - پیدا کردن همزمان Min و Max، الگوریتم و مرتبه آن
بخش 2
1:20'روش جفت کردن اعداد برای یافتن Min و Max - کد جفت کردن اعداد وقتی n زوج است - یافتن دومین کوچکترین یا دومین بزرگترین ( 5 روش) - روش تورنومنت
بخش 1
1:15'یافتن k امین کوچکترین
بخش 2
1:40'بررسی زمان اجرا الگوریتم یافتن k امین کوچکترین با استفاده از Partition - الگوریتم بهینه یافتن k امین کوچکترین و بررسی زمان اجرا
بخش 1
1:45'ضرب چند جملهاییها (2 روش)
بخش 2
00:30'ادامه ضرب چند جملهاییها، بررسی زمان اجرا - ضرب اعداد بزرگ
بخش 1
1:45'الگوریتمهای حریصانه - خرد کردن سکه - کوله پشتی کسری (غیرصفر و یک) - کد کوله پشتی کسری و محاسبه مرتبه - کوله پشتی کسری با تفکر تقسیم وغلبه
بخش 2
1:10'الگوریتم هافمن - رسم درخت هافمن - مرتبه هافمن
بخش 1
1:45'انتخاب فعالیتها، تفکرهای مختلف
بخش 2
1:40'مسئله زمانبندی کارها: Simple task sceduling وtask sceduling problem with deadline و محاسبه مرتبه - شروع آنالیز استهلاکی - آنالیز تجمعی و بررسی چند مثال
بخش 1
1:30'آنالیز حسابرسی و بررسی چند مثال - ساخت صف با دو پشته
بخش 2
00:55'شروع برنامهنویسی پویا - چرا در حل بعضی مسائل از نقسیم و غلبه استفاده نمی کنیم ؟
بخش 3
1:05'یافتن جمله n ام فیبوناچی - الگوریتم ضرب زنجیرهایی ماتریسها
بخش 4
1:00'تعداد ضرب بهینه n ماتریس با استفاده از برنامهنویسی پویا و یافتن رابطه بازگشتی آن
بخش 5
1:00'ساخت یک BST بهینه با استفاده از برنامهنویسی پویا
بخش 1
1:30'مسئلهی LCS(Longest Common Subsequence) - حل LCS با برنامهنویسی پویا
بخش 1
2:00'مسئله ی LCS(Longest Common Subsequence) - حل LCS با برنامهنویسی پویا
بخش 2
1:20'مسئلهی Cut Rod (برش میله) - محاسبه مرتبهی Cut Rod به صورت برنامهنویسی پویا و تقسیم و غلبه
بخش 1
1:45'کولهپشتی 0 و 1 و راهحل برنامهنویسی پویا - مسئله خرد کردن سکه و راهحل برنامهنویسی پویا - شروع فصل گراف - تعاریف اولیه گراف - محاسبه تعداد یالها در گراف ساده n راسی در حالتهای مختلف
بخش 2
2:30'روشهای پیادهسازی گراف - ماتریس مجاورتی - لیست مجاورتی - حافظه مصرفی لیست و ماتریس - پیمایش گراف - پیمایشهای DFS و BFS
بخش 1
1:50'انواع یالهای حاصل از پیمایش گراف (back , cross ,forward) - شرط لازم و کافی برای وجود سیکل در گراف - رنگ کردن نودها و فهمیدن نوع یالها از روی این رنگها - کاربردهای DFS - الگوریتم یافتن ترتیب توپولوژیکی
بخش 2
1:25'ادامه کاربردهای DFS - الگوریتم یافتن مولفههای متصل قوی - الگوریتم BFS و کاربردهای BFS
بخش 1
2:00'درخت پوشای مینیمم (MST) - بررسی الگوریتمهای یافتن MST (کراسکال و پریم) - محاسبه مرتبه پریم و کراسکال
بخش 2
2:10'یافتن کوتاهترین مسیرهای هم مبدا در گراف وزندار - بررسی الگوریتمهای بلمن فورد و دایجسترا - کوتاهترین مسیرهای هم مبدا در DAG
بخش 1
2:00'نظریه NP
بخش 1
2:25'شبکه شار ( Flow Network)
بخش 1
1:25'مجموعههای مجزا
بخش 1
00:50'به دست آوردن مرتبه زمانی قطعه کدها
بخش 2
1:05'به دست آوردن مرتبه زمانی قطعه کدها
بخش 3
1:30'به دست آوردن مرتبه زمانی قطعه کدها - گام شماری
بخش 4
1:50'زمان اجرای یک الگوربتم - نمادهای مجانبی - مقایسه رشد توابع
بخش 5
2:15'نمادهای مجانبی - مقایسه رشد توابع
بخش 1
1:40'شروع فصل روابط بازگشتی - به دست آوردن مرتبه زمانی توابع بازگشتی - درخت بازگشت
بخش 2
1:45'به دست آوردن مرتبه زمانی توابع بازگشتی - درخت بازگشت
بخش 3
2:05'به دست آوردن مرتبه زمانی و حل توابع بازگشتی - درخت بازگشت - مساله برج هانوی
بخش 4
1:45'مساله برج هانوی - به دست آوردن مرتبه زمانی و حل توابع بازگشتی
بخش 1
1:40'به دست آوردن مرتبه زمانی و حل توابع بازگشتی - درخت بازگشت
بخش 2
1:25'به دست آوردن مرتبه زمانی و حل توابع بازگشتی
بخش 3
2:00'شروع فصل درخت - انواع پیمایشهای روی درخت - پیادهسازی روالهای بازگشتی روی درخت - رسم درخت با داشتن پیمایشها
بخش 4
1:30'انواع پیمایشهای روی درخت - پیادهسازی روالهای بازگشتی روی درخت - بررسی ارتفاع درخت دودویی
بخش 1
2:15'انواع پیمایشهای روی درخت - پیادهسازی روالهای بازگشتی روی درخت - هرم بیشینه - یافتن مرتبه یک نود
بخش 2
2:00'انواع پیمایشهای روی درخت - کمینه و بیشینه ارتفاع B-tree - AVL - درخت دودویی کامل - دنباله جستجو
بخش 3
2:05'انواع پیمایشهای روی درخت - ادغام 2 هیپ - درخت قرمز سیاه
بخش 4
1:35'هرم - Treap - درج در Treap - دوران
بخش 1
2:05'درخت قرمز سیاه - بررسی ارتفاع درخت دودویی
بخش 2
1:50'پیمایش روی درخت - یافتن Pred و Succ - رسم درخت با داشتن پیمایشها
بخش 3
00:55'AVL - MaxHeap - هزینه ادغام تعدادی لیست مرتب (2روش) - انتخاب داده ساختار مناسب برای انجام یک عملیات
بخش 4
1:05'بررسی پیمایش Postfix - انتخاب داده ساختار مناسب برای انجام یک عملیات
بخش 5
1:50'فرمول بازگشتی تعداد درختهای دودویی با n نود - درج در AVL
بخش 1
1:20'شروع مرتبسازی - مرتبه یافتن k امین مینیمم، k امین ماکزیمم، میانه - بررسی نامساوی مثلثی در یک مجموعه از اعداد - تعداد مقایسات برای یافتن میانه
بخش 2
00:45'ادغام k لیست مرتب - بررسی مرتبه مرتبسازی سریع
بخش 3
1:05'آرایه k مرتب - مرتبسازی سریع
بخش 4
1:55'آرایه k مرتب - الگوریتم مرتبسازی خستهکننده
بخش 5
1:20'سورتهای سه مرحلهایی - قضیهی 0 و 1
بخش 1
1:05'دنباله ی زیگراگی
بخش 2
1:15'تعداد وارونگی های یک آرایه n عنصری - روش تورنومنت - به دست آوردن مرتبه الگوریتم بازگشتی با روش کران یابی و بمب اتم – محاسبه تعداد مقایسات برای یافتن nامین ماکزیمم یا مینیمم
بخش 3
1:05'آرایه صعود نزول ( اره ایی ) - وارونگی نسبت به صعودی بودن
بخش 4
1:50'محاسبه تعداد وارونگی با استفاده از مرتبسازی درجی و مرتبسازی ادغامی - مرتب سازی k عدد مجزا - pancake Sort - Randomized-Quicksort - مرتبسازی مبنایی - ماتریس یانگ
بخش 1
1:20'شروع درهمسازی - درهمسازی باز با وارسی خطی - ترتیب درج عناصر در جدول - محاسبه میانگین تعداد برخوردهای دو عنصر در جدول
بخش 2
1:20'متوسط تعداد مقایسهها در جستجوی موفق و ناموفق - یافتن مینیمم در آرایه مرتب حلقوی
بخش 3
00:55'مرتبه یافتن بزرگترین زیر دنبالهی یک رشته
بخش 4
1:00'شروع آنالیز استهلاکی - پیادهسازی صف با استفاده از 2 پشته - محاسبه هزینه سرشکنی
بخش 1
1:45'محاسبه هزینه سرشکنی در مسائل - بررسی شمارنده k بیتی - بررسی الگوریتم استراسن
بخش 2
00:40'مرتبه زمانی محاسبه k امین عدد فیبوناچی - محاسبه هزینه جمع دو عدد، بهترین و بدترین حالت
بخش 3
00:40'محاسبه هزینه سرشکنی درج و حذف در جدول درهمساز پویا
بخش 1
1:15'ادامه محاسبه هزینه استهلاکی در مسائل - شروع گراف - DAG - جستجوی عمق اول (DFS) - ترتیب توپولوژیکی در گراف
بخش 2
1:10'بررسی انواع یالها در DFS و BFS - الگوریتم تشخیص بدون دور بودن گراف جهتدار - درخت پوشای کمینه
بخش 3
1:15'الگوریتمهای یافتن درخت پوشای کمینه - زمان ملاقات گرهها در DFS - الگوریتم یافتن همهی طولانیترین مسیرها از یک راس داده شده - بررسی انواع یالها در DFS و BFS
بخش 4
1:10'مرتبه یافتن قطر گراف - بررسی گذر و مدار اویلری - الگوریتم تشخیص همبندی در گراف
بخش 5
1:15'مقایسه الگوریتم های Prim و Kruskal - درخت فراگیر گلوگاه - دومین زیر درخت فراگیر کمینه
بخش 6
1:30'یافتن کوتاهترین مسیرها در گراف - تعریف برش و یالهای برش - قدرت یک درخت پوشا
بخش 7
1:00'ترتیب انتخاب یالها در Prim و Kruskal - نکاتی در مورد درخت پوشا کمینه
بخش 1
1:05'مرتبه محاسبه درخت پوشای بیشینه - بررسی سیکل و مسیر همیلتونی - به دست آوردن تعداد سیکلهای ساده در گراف مسطح - الگوریتم فلوید
بخش 2
1:15'درخت کوتاهترین مسیر - مرتبه بررسی دو بخشی بودن گراف - مرتبه یافتن تعداد اجزای همبند در گراف
بخش 3
00:30'الگوریتم بلمن فورد - مولفه متصل قوی درگراف
بخش 1
1:10'قضیه Master - محاسبه هزینه استهلاکی برای یک داده ساختار - پیاده سازی صف با دو پشته - مرتب سازی مبنایی
بخش 2
1:40'محاسبه هزینه استهلاکی برای یک داده ساختار - بررسی partition در مرتب سازی سریع - درهمسازی بسته - درج در لیست پیوندی - درخت هافمن
بخش 3
1:45'استفاده از الگوریتم Cutrod - تعداد فراخوانیها در یک رویه بازگشتی - تعداد عناصر و شرط پر بودن صف - مقایسه رشد توابع - مرتبسازی لیست پیوندی دو سویه - به دست آورن مرتبه برخی توابع بازگشتی خاص - کوله پشتی 0 و 1
بخش 4
1:30'محاسبه بزرگترین زیر دنبالهی صعودی - درخت Trie - هرم کمینه - محاسبه مرتبه تابع بازگشتی با تغییر متغیر
بخش 1
1:50'مقایسه رشد یکسری توابع خاص ( log n! , (logn)! , n ^ lglg n , n^n , lgn ^ lgn , lg* n , … ) - نمادهای مجانبی
بخش 1
1:25'تبدیل درخت عمومی به درخت دودویی معادل و پیمایش روی آن - بررسی هزینه جستوجوی ناموفق در درهمسازی باز و درهمسازی بسته - وزن کوتاهترین از راس i به راس j در صورت عبور از k یال
بخش 2
1:35'الگوریتم حریصانه اجرای پردازهها روی یک پردازنده - رابطه بازگشتی ساخت درخت دودویی جستجو - مسئله ژوزف - روش تقسیم و غلبه در محاسبه حاصلضرب دو عدد n بیتی
بخش 3
1:25'پیدا کردن زیر دنباله متوالی با حاصل ضرب بیشینه - بررسی ارتفاع درخت هافمن - الگوریتم خرد کردن پول با روش حریصانه - الگوریتمهای یافتن کوتاهترین مسیر بین راس i و j
بخش 1
1:20'مقایسه رشد توابع - بررسی نمادهای مجانبی - مرتبه زمانی قطعه کدها
بخش 2
00:50'مقایسه رشد توابع - مرتبه زمانی قطعه کدها - محاسبه طولcall stack برنامه - بررسی دقیق نمادهای مجانبی در یک مساله
بخش 3
1:40'مقایسه رشد توابع - مرتبه زمانی قطعه کدها - تعداد تکرار جمله اصلی
بخش 1
1:10'محاسبه مرتبه برخی روابط بازگشتی خاص - رابطه بازگشتی عدد nام کاتالان
بخش 2
1:20'محاسبه مرتبه برخی روابط بازگشتی خاص - روش نردبانی در محاسبه ب.م.م
بخش 3
1:15'نکاتی در رابطه با قضیه Master - محاسبه مرتبه برخی روابط بازگشتی خاص
بخش 1
00:40'انواع درخت (درخت متوازن، درخت کاملا متوازن، درخت کامل kتایی، درخت تکمیل، درخت پر)
بخش 2
00:35'تعداد درختهای دودویی متوازن با ارتفاع h
بخش 3
1:35'درخت 2 - کامل - تعداد حالات پرانتز گذاری عبارات ریاضی - بررسی هزینه حذف و درج و Find Closest در: لیست پیوندی مرتب یکطرفه، لیست پیوندی مرتب دو طرفه و لیست مرتب (آرایه)
بخش 4
1:50'کمینه ارتفاع درخت قرمز - سیاه - الگوریتمهای یافتن Pred و Succ - به دست آوردن مرتبه در AVL - درخت مرتبه آماری - درج و حذف در درخت قرمز - سیاه
بخش 1
1:20'ساخت Treap - حذف یک عنصر از هرم کمینه
بخش 2
1:20'رابطه بازگشتی حداقل تعداد گره برای ساخت AVL با ارتفاع h - رابطه بازگشتی میانگین ارتفاع درخت BST با n عنصر - تبدیل پیمایشهای درخت به یکدیگر
بخش 3
2:20'محاسبه حداکثر تعداد نابهجاییها در هرم کمینه متوازن - توضیح کامل B-Tree ( توضیح 2 نحوه ی پیادهسازی، چگونگی حذف یک عنصر، چگونگی درج یک عنصر).
بخش 1
1:25'هزینه جستجوی یک عدد در B-Tree - بررسی پیمایش PreOrder
بخش 2
1:40'بررسی داده ساختار Deap - ادغام 2 آرایه مرتب - رابطه بازگشتی تعداد درختهای جستجوی دودویی با n عنصر (کاتالان) - MinMaxHeap - هزینه بررسی اینکه آیا BST داده شده ،AVL است.
بخش 3
00:35'ادغام 3 آرایه مرتب و ساخت BST متوازن - بررسی پیمایشهای درخت - رابطه بازگشتی حداقل تعداد گره برای ساخت AVL با ارتفاع h.
بخش 1
2:25'شبکه شار
پی دی اف درس طراحی الگوریتم
هر یک از فیلمهای درس یا حل تست طراحی الگوریتم را تهیه کنید در داشبوردتان پی دی اف مربوط به آن دوره نیز قرار میگیرد و دانشجویان براحتی میتوانند جزوات را پرینت و هنگام تماشای فیلمهای درس و حل تست طراحی الگوریتم از جزوات خط ببرند و مطالب مهم را هایلایت کنند و در صورت نیاز میتوانید برای خودتان در کنار جزوات یاداشت برداری کنید.
فیلمهای رایگان
طراحی الگوریتم چیست؟
امروزه واژه الگوریتم در علوم و مهندسی کامپیوتر معادل روش حل مسأله است. الگوریتم با این دید طراحی میگردد که بعد از تبدیل آن به یک زبان برنامه نویسی (مثلا پایتون یا جاوا یا سی) به کامپیوتر داده شود که کامپیوتر آن را اجرا کند. الگوریتم را میتوان به زبان طبیعی (مثلا نوشتن مراحل الگوریتم به فارسی)، زبانی مشابه زبانهای کامپیوتری (شبه کد یا همان pseudocode) و حتی به صورت نمودارهای خاصی بیان نمود. بنابراین الگوریتم در این مرحله مستقیماً به وسیله کامپیوتر قابل تفسیر و اجرا نیست، اما پس از تبدیل آن به یک زبان برنامه نویسی برای اجرا به کامپیوتر داده میشود.
کتاب های مرجع طراحی الگوریتم چه هستند؟
مرجع اصلی که برای طراحی الگوریتم در دانشگاههای معتبر تدریس میشود کتاب CLRS است، همچنین کتابهای Jeff_erickson، Kleinberg و sedgewick نیز در برخی از دانشگاههای ایران و جهان تدریس میشود، در این صفحه میتوانید بصورت رایگان PDF تمامی کتاب های مرجع طراحی الگوریتم را دانلود و از آنها استفاده کنید
فیلم آموزشی طراحی الگوریتم چند ساعت است و درس طراحی الگوریتم شامل چه مباحث و فصولی است؟
فیلم های درس طراحی الگوریتم 40 ساعت است و شامل مباحث الگوریتم های تقسیم و غلبه، الگوریتم های حریصانه، الگوریتم های برنامه نویسی پویا، آنالیز استهلاکی، گراف، نظریه NP و جریان شار و مجموعه های مجزاست
آیا میتوان درس طراحی الگوریتم را مستقلا مطالعه کرد؟
بهتر است ابتدا تمام درس ساختمان داده و یا حداقل مباحث مربوط به بدست آوردن مرتبه زمانی شبه کدها، رشد توابع و الگوریتم های بازگشتی خوانده شود و سپس درس طراحی الگوریتم را بخوانید.
آیا در این فیلم ها درس طراحی الگوریتم بصورت روان آموزش داده شده است؟
در این فیلم مطالب از 0 تا 100 و با شیوه بسیار منحصر به فرد و به سادگی هر چه تمام تر آموزش داده شده است و به جرات میتوان گفت که برترین فیلم های طراحی الگوریتم کشور است