تفکر الگوریتمی پیشرفته و ساختمان‌داده‌ها

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

avataravataravatar

و ۳۳۷۴ نفر دیگر ثبت‌نام کرده‌اند.

آموزش تفکر الگوریتمی پیشرفته و ساختمان داده

بهترین نقطه آغاز

ورود به مسابقات المپیاد و ICPC

پایه‌ای محکم

برای ورود به حوزه‌ٔ علوم کامپیوتر

۸۰٪ مصاحبه‌های

شرکت گوگل بر پایه الگوریتم

معرفی

مخاطبین

پیش‌نیازها

سرفصل‌ها

پس از دوره

اساتید

0 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1

معرفی دوره

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

  • section item

    ۰

    کدآموز به این دوره اعتماد کرده‌اند

  • section item

    ۰

    داوریِ موفق کدهای ارسال‌‌شده برای تمرین‌ها

  • section item

    ۰

    تعداد پاسخ‌های مربیان به سوالات کدآموزان

  • section item

    4.83/5

    امتیاز کدآموزها به راهنمایی‌های مربیان

  • section item

    این دوره مناسب شما است اگر...

    مشتاقید به بازار پردرآمد برنامه‌نویسی و حوزه‌ی نرم‌افزار وارد شوید.

    برای پروژه‌های دانشگاهی یا کاری خود نیاز به یادگیری الگوریتم و ساختمان داده‌ها دارید.

    معتقدید یادگیری برنامه‌نویسی در دنیای امروز ضروریست.

    می‌خواهید الگوریتم پیشرفته و کار با ساختمان داده‌ها را برای همیشه به شکل اصولی بیاموزید.

  • section item

    این دوره مناسب شما نیست اگر...

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

    تجربه‌ی عملی چندین هزار خط کدنویسی برایتان ارزشی ندارد.

    حاضر نیستید در هفته ۶ ساعت برای یادگیری، پیشرفت و رشد خودتان زمان بگذارید.

    می‌خواهید الگوریتم پیشرفته و ساختمان‌ داده‌ها را به طور سطحی و گذرا بیاموزید.

  • پیش‌نیازها

  • لازم است...

    section item

    علاقه و پشتکار داشته باشید.

    section item

    مبانی برنامه‌نویسی را بشناسید.

  • لازم نیست...

    section item

    در رشته‌ی کامپیوتر تحصیل کرده باشید.

سرفصل‌های دوره

certificate
  • با گذراندن این دوره:

    • صدها خط کد زده‌اید و برنامه‌نویسی را به‌صورت عملی تجربه کرده‌اید.

    • بر روی مفاهیم پیشرفته الگوریتم و تجربه‌ی به‌کارگیری آن‌ها، تسلط ویژه‌ای پیدا کرده‌اید.

    • رشد چشمگیر و آمادگی بالایی در دروس ساختمان‌ داده‌ها و طراحی الگوریتم دانشگاه کسب کرده‌اید.

    • در مفاهیم برنامه‌نویسی به تسلطی رسیده‌اید که می‌توانید زبان‌های دیگر را در یک‌پنجم زمان یاد بگیرید.

    • توانایی حل سؤالات مسابقات الگوریتمی همانند ACM و ICPC را پیدا کرده و می‌توانید در این مسابقات شرکت کنید.

اساتید و مربیان دوره

teacher's avatar

حمیدرضا کامکاری

طراحی و تولید

دانشجوی کارشناسی ارشد علوم کامپیوتر دانشگاه Toronto کانادا | دستیار آموزشی دانشگاه Toronto
teacher's avatar

کیوان رضایی

طراحی و تولید

دانشجوی دکترای علوم کامپیوتر دانشگاه Maryland آمریکا | مدال طلای کشوری و نقره‌ی جهانی المپیاد کامپیوتر
teacher's avatar

محمدمهدی شکری

طراحی و تولید

مدیر محصول در کوئرا | مدال طلای المپیاد کشوری و مدال برنز ICPC جهانی
teacher's avatar

سید مهدی صادق شبیری

طراحی و تولید

دانشجوی کارشناسی مهندسی کامپیوتر دانشگاه صنعتی شریف
college

تفکر الگوریتمی پیشرفته و ساختمان‌داده‌ها

feature

۱۱۳ تمرین

feature

گواهی معتبر

feature

عضو پارک علم و فناوری شریف

و ۳۳۷۷ نفر دیگر ثبت‌نام کرده‌اند.

feature

۱۱۳ تمرین

feature

گواهی معتبر

feature

عضو پارک علم و فناوری شریف

سوالات متداول












آموزش الگوریتم پیشرفته و ساختمان‌داده ها در کوئرا کالج

آموزش الگوریتم پیشرفته

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

تعریف الگوریتم چیست؟

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

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

الگوریتم در ریاضی

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

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

کاربرد الگوریتم چیست؟

تا به اینجا در این مقاله به صورت کامل به این پرسش پرداختیم که الگوریتم چیست، در این قسمت می‌خواهیم بگوییم الگوریتم چه کاربردی دارد؟ در زیر به برخی از کاربردهای الگوریتم‌ها اشاره می‌کنیم:

 

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

معیارهای الگوریتم

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

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

ویژگی‌های الگوریتم

صرفاً نوشتن توالی دستورالعمل‌ها به عنوان یک الگوریتم برای انجام یک کار خاص کافی نیست. داشتن ویژگی‌های زیر در ارتباط با یک الگوریتم ضروری است:

 

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

الگوریتم در برنامه نویسی چگونه کار می‌کند؟

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

چندین الگوریتم در برنامه نویسی وجود دارد که عبارتند از:

  • تعریف کردن مسئله
  • جمع‌آوری اطلاعات (داده)
  • پردازش اطلاعات (داده)
  • استفاده از رویکرد منطقی
  • حل مسئله (راه‌حل)

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

ساختار الگوریتم‌ها

الگوریتم‌ها با توجه به ساختار منطقی که دارند در 3 دسته جا می‌گیرند:

  • دنباله ای (Sequence): ساختاری مرحله به مرحله، که ترتیب گام‌ها برای رسیدن به پاسخ در آن مشخص است.
  • شاخه ای ((Branching: این الگوریتم‌ها طبق قانون اگر-آنگاه در ریاضیات کار می‌کنند. به این صورت که پس از تعیین شرط، پاسخ با توجه به نتیجه شرط تعیین می‌شود.
  • حلقه ای (Loop): الگوریتم‌های حلقه ای یا تکراری، در تعداد دفعات مشخصی شرطی را در پروژه اعمال می‌کنند و پس از تمام شدن فرایند، برنامه را پایان می‌دهند.

انواع الگوریتم‌ها از نظر نوع مسئله

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

الگوریتم بازگشتی  (Recursive)

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

الگوریتم دینامیک  (Dynamic)

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

الگوریتم برگشت به عقب  (Backtracking)

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

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

الگوریتم تقسیم و حل (Divide and conquer )

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

به‌عنوان مثال مرتب‌سازی ادغامی ابتدا آرایه‌ای از مقادیر ورودی را دو قسمت کرده و به‌صورت بازگشتی، دوباره هر قسمت را دو قسمت می‌کند. این روند آن‌قدر ادامه پیدا می‌کند تا اعداد در دسته‌های کوچک‌تر صعودی یا نزولی مرتب شوند. سپس از ادغام زیر بخش های کوچک، آرایه مرتب‌شده‌ی بخش‌های بزرگ‌تر به‌ دست می‌آید.

الگوریتم حریصانه (Greedy)

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

مسئله خرد کردن سکه‌ها یکی از مثال‌های معروف در به‌کارگیری الگوریتم حریصانه است. این مسئله می‌گوید فرض کنید که شما باید مبلغی مثلاً 36 تومان را با سکه‌های 20 تومانی، 10 تومانی، 5 تومانی و 1 تومانی پرداخت کنید به طوری که کمترین تعداد سکه را بپردازید. کمترین تعدادی که بتوان با آن 36 تومان را پرداخت کرد پاسخی بهینه برای مسئله ما خواهد بود که در اینجا، برداشتن یک سکه از هر 4 مدل است.

الگوریتم بروت فورس (Brute force)

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