الگوریتمستان

نوشته‌های یک علاقه‌مند به حوزه‌های برنامه‌نویسی، الگوریتم، حل مسئله و ریاضیات دوست داشتنی

 
در صورت ناخوانا بودن نوشته‌ها، از مرورگر دیگری استفاده کنید.
نوشته‌ها با برچسب آموزش ساختمان داده‌ها نوشته‌ها با برچسب آموزش ساختمان داده‌ها - الگوریتمستان الگوریتمستان الگوریتمستان
نوشته‌ها با برچسب «

آموزش ساختمان داده‌ها

»
✤   دوره‌ی طراحی و تحلیل الگوریتم دانشگاه استنفورد

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

  

جلسه‌ی اول

۱- چرا مطالعه‌ی الگوریتم؟

۲- ضرب اعداد صحیح

۳- الگوریتم ضرب Karatsuba

۴- درباره‌ی دوره

ادامه ...
✤   مستندات دوره‌ی آمادگی مسابقات برنامه‌نویسی دانشگاه استنفورد

مستندات دوره‌ی «Introduction to Programming Contests» دانشگاه استنفورد با تدریس Jaehyun Park (مربی تیم‌های ACM-ICPC این دانشگاه) شامل اسلایدها، سوالات برگزیده برای تمرین در موضوعات مختلف ریاضیات، ساختمان داده‌ها و الگوریتم‌ها به همراه نکات برنامه‌نویسی از پیوند زیر قابل مشاهده و دریافت هستند:

CS 97SI: Introduction to Programming Contests

ادامه ...
✤   کتاب الکترونیکی ساختمان داده‌ها

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

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

  

» فصل ۱: مرتبه‌ی اجرایی

   نشان‌گذاری

   مرتبه‌ی اجرایی حلقه‌ها

   خواص سیگما

   نمادهای Ω و θ

ادامه ...
✤   ظرف‌ها در ++C

منظور از ظرف یا نگهدارنده (Container) ساختمان داده‌ای‌ست که دسته‌ای از اطلاعات را در خود نگه می‌دارد. آنچه که این ساختمان‌ها را از هم متمایز می‌کند، نوع تخصیص حافظه، نوع دسترسی و کارایی درج و حذف عنصر در آنها است که به برخی از آنها کاربری‌های ویژه می‌دهد.

در ادامه با انواع این نوع ساختمان داده‌ها در زبان برنامه‌نویسی ++C نسخه‌ی C++11 آشنا می‌شویم. با توجه به گسترده بودن این بحث، جزئیات بیشتر هر کلاس را در «پیوندها برای مطالعه‌ی بیشتر» بخوانید.

توجه: تمامی کلاس‌های بحث شده در کتابخانه‌ی قالب استاندارد (STL) تعریف شده و در فضای نام std قرار دارند.

ادامه ...
✤   درخت جستجوی دودویی

درخت دودویی (Binary Tree)

درختی است که هر گره آن دارای حداکثر دو گره فرزند است که به آنها فرزند راست و چپ گره گفته می‌شود. به همین ترتیب زیردرختی که فرزند راست در رأس آن قرار دارد زیردرخت راست و زیردرختی که فرزند چپ در رأس آن قرار دارد زیردرخت چپ گره نامیده می‌شوند.

  

درخت دودویی

  

درخت جستجوی دودویی (Binary Search Tree - BST)

درختی دودویی است که برای هر گره آن شروط زیر برقرار هستند:

1- مقادیر تمامی گره‌های زیردرخت راست - در صورت وجود - از مقدار گره بزرگتر هستند.

ادامه ...
✤   صف اولویت‌دار

صف اولویت‌دار (یا صف اولویتی - Priority Queue) از جمله ساختمان داده‌های بسیار پرکاربرد است. در صف عادی از تکنیک FIFO - مخفف First In First Out - استفاده می‌شود. در این تکنیک، مثل یک صف نانوایی، داده‌ها به ترتیب ورود پشت سر هم در صف قرار می‌گیرند. بنابراین اولین داده‌ی ورودی، اولین داده‌ی خروجی نیز خواهد بود. اما در صف اولویت‌دار برای هر داده، اولویتی - نه لزوما منحصربفرد - مشخص می‌شود. صف اولویت را می‌توان به اورژانس یک بیمارستان تشبیه کرد که هر بیمار با شدت بیماری بیشتر اولویت بیشتری برای رسیدگی دارد. سیستم عامل کامپیوتر هم برای مدیریت پردازش‌ها از صف‌های اولویت‌دار استفاده می‌کند.

ادامه ...
✤   درخت Heap

درخت دودویی کامل

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

  

به یک مثال دقت کنید:

  

درخت هیپ یا هرم یا کپه

  

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

  

نمایش درخت دودویی کامل

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

ادامه ...
✤   لیست پیوندی

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

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

ادامه ...
✤   آرایه پویای دو بعدی در ++C

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

به قطعه کد زیر توجه کنید:

  

ادامه ...
✤   آرایه‌ی ایستا و پویا در ++C

زبان ++C همانند اکثر زبان‌های برنامه‌نویسی دیگر، ساختاری به نام آرایه دارد که امکان تعریف مجموعه‌ای از متغیرهای هم‌نوع (اصطلاحا مجموعه عناصر همگن) را فراهم می‌کند. چنین ساختاری به صورت زیر تعریف می‌شود:

  

ادامه ...
کمی آمار
  • عمر سایت:  ۴۵۷۱ روز
  • تعداد امتیاز ثبت شده:  ۳۲۷۵ امتیاز
  • میانگین امتیازها:  ۴.۲۵ از ۵.۰۰
  • بازدید امروز:  ۲۳۳ بازدید
  • بازدید ۲۴ ساعت گذشته:  ۱۰۶۸ بازدید
  • بازدید ۷ روز گذشته:  ۸۵۴۳ بازدید
  • بازدید ۳۰ روز گذشته:  ۳۷۵۲۰ بازدید
  • بازدید ۱ سال گذشته: ۴۲۲۱۴۶ بازدید
  • کل بازدیدها: ۴۸۱۴۴۳۶ بازدید
برچسب‌ها
#آمادگی مسابقه برنامه‌نویسی  #آموزش الگوریتم  #مسئله‌های الگوریتمی  #برنامه‌نویسی ++C  #الگوریتم  #نمونه سوالات مسابقه برنامه‌نویسی  #حل مسئله‌‌ی الگوریتمی  #برنامه‌نویسی  #منبع آموزشی  #حل سوالات مسابقات برنامه‌نویسی  #الگوریتم‌های تقسیم و غلبه  #نمونه سوال مسابقه ACM  #الگوریتم‌های برنامه‌نویسی پویا  #الگوریتم‌های بازگشتی  #کتاب الکترونیکی  #آموزش ساختمان داده‌ها  #تکنیک‌های طراحی الگوریتم  #محاسبات ریاضی  #گراف  #دانلود کتاب  #حل سوالات ACM-ICPC  #الگوریتم‌های مرتب‌سازی  #سوالات مسابقات ACM-ICPC  #Python  #پیمایش گراف  #ساختمان داده  #کتاب مسابقات برنامه‌نویسی  #الگوریتم‌های گراف  #حل سوالات UVa Online Judge  #الگوریتم‌های مسیریابی  #الگوریتم‌های حریصانه  #درخت‌ها  #سوالات UVa Online Judge  #جستجوی اول سطح  #ماتریس  #الگوریتم‌های کوتاهترین مسیر  #درخت پوشا  #الگوریتم دایکسترا  #ویدئوی آموزشی  #معرفی وب‌سایت  #الگوریتم فلوید-وارشال  #مسئله‌ی کوله‌پشتی  #جستجوی اول عمق  #کتابخانه قالب استاندارد ++C  #صف  #سوالات مسابقات برنامه‌نویسی بیان  #الگوریتم‌های عقبگرد  #حل سوالات Timus Online Judge