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

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

مقدمه ای بر DSA

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

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

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

چگونه DSA را یاد بگیریم؟

اولین و مهمترین چیز این است که کل روش را به قطعات کوچک تقسیم کنید که باید به صورت متوالی انجام شوند. فرآیند کامل یادگیری DSA از ابتدا می تواند به 5 قسمت تقسیم شود:

1. حداقل یک زبان برنامه نویسی را یاد بگیرید (این را به انتخاب خودتان می سپاریم.)
2. ساختارهای داده را بیاموزید
3. الگوریتم ها را یاد بگیرید
4. با پیچیدگی های زمانی و مکانی آشنا شوید
5. تمرین مسائل در DSA

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

در اینجا مهمترین و مورد انتظارترین مرحله نقشه راه برای یادگیری ساختار داده و الگوریتم می آید – مرحله ای که شروع به یادگیری در مورد DSA می کنید.

موضوع DSA از دو بخش تشکیل شده است:

• ساختارهای داده
• الگوریتم ها 

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

1. در مورد پیچیدگی ها بیاموزید

در ساختارها و الگوریتم های داده (DSA)، هدف اصلی حل مسائل به طور موثر و کارآمد است. برای تعیین کارایی یک برنامه، به دو نوع پیچیدگی نگاه می کنیم:

1. پیچیدگی زمانی : به ما می گوید که کد ما چقدر زمان می برد تا اجرا شود.
2. پیچیدگی فضایی : به ما می گوید که کد ما چقدر از حافظه استفاده می کند.

نمادگذاری مجانبی

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

نشانه گذاری	توضیحات
Big-O (Ο)	بدترین سناریو را توصیف می کند و یک محدوده زمانی بیشتر از الگوریتم را ارائه می دهد.
امگا (Ω)	بهترین سناریو را توصیف می‌کند و محدوده زمانی کمتری از الگوریتم را ارائه می‌دهد.
تتا (θ)	میانگین پیچیدگی یک الگوریتم را نشان می دهد.

متداول ترین نماد مورد استفاده برای تجزیه و تحلیل کد Big O Notation است که محدودیت بالایی در زمان اجرا یا استفاده از حافظه در مورد اندازه ورودی ارائه می دهد.

موضوعات مرتبط:

• درک پیچیدگی زمانی با مثال های ساده
• پیچیدگی های زمانی ساختارهای داده مختلف
• نحوه تجزیه و تحلیل حلقه ها برای تجزیه و تحلیل پیچیدگی الگوریتم ها
• سوالات تمرینی در مورد تجزیه و تحلیل پیچیدگی زمانی

2. الگوریتم های ریاضی و بیتی

1 . الگوریتم های ریاضی

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

الگوریتم	توضیحات
GCD و LCM	بزرگترین مقسوم علیه مشترک و کوچکترین مضرب مشترک دو عدد
فاکتورسازی اولیه	تجزیه یک عدد را به عوامل اول آن
اعداد فیبوناچی	دنباله فیبوناچی، هر عدد حاصل جمع دو عدد قبلی است.
اعداد کاتالان	شمارش تعداد عبارات معتبر با تعداد معینی از جفت پرانتز
حساب مدولار	انجام عملیات حسابی بر روی اعداد با مدول یک مقدار معین.
تابع اویلر توتینت	تعداد اعداد صحیح مثبت را کمتر از یک عدد معین که نسبتاً اول هستند را می شمارد.
محاسبات nCr	ضریب دوجمله ای را محاسبه می کند، که نشان دهنده تعداد راه های انتخاب عناصر r از مجموعه ای از n عنصر است.
اعداد اول و تست های اولیه	اول بودن یک عدد معین را مشخص می کند و اعداد اول را به طور موثر پیدا می کند.
الگوریتم های غربال	همه اعداد اول را تا حد معین پیدا می کند.

موضوعات مرتبط:

• تمرین مسئله در الگوریتم ریاضی

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

الگوریتم‌های بیتی الگوریتم‌هایی هستند که بر روی تک تک بیت‌های اعداد عمل می‌کنند. این الگوریتم‌ها نمایش دودویی اعداد را برای انجام کارهایی مانند دستکاری بیت، عملیات منطقی بیتی (AND، OR، XOR)، تغییر بیت‌ها و تنظیم یا پاک کردن بیت‌های خاص در یک عدد دستکاری می‌کنند. الگوریتم‌های بیتی معمولاً در برنامه‌نویسی، رمزنگاری و کارهای بهینه‌سازی سطح پایین استفاده می‌شوند ، جایی که نیاز به دستکاری کارآمد بیت‌ها است.

موضوع	توضیحات
تغییر بیت	بیت ها را با تعداد مشخصی از موقعیت ها به چپ یا راست جابه جا می کند.
شیفت چپ (<<)	بیت ها را به سمت چپ جابه جا می کند و به طور موثر عدد را در 2 ضرب می کند.
شیفت به راست (>>)	بیت ها را به سمت راست جابجا می کند و به طور موثر عدد را بر 2 تقسیم می کند.
استخراج بیت ها	استفاده از ماسک برای استخراج بیت های خاص از یک عدد صحیح.
تنظیم بیت ها	استفاده از ماسک برای تنظیم بیت های خاص بر روی 1 در یک عدد صحیح.
پاک کردن بیت ها	استفاده از ماسک برای تنظیم بیت های خاص روی 0 در یک عدد صحیح.
تغییر بیت ها	استفاده از XOR (^) برای جابجایی بیت های خاص در یک عدد صحیح.
شمارش بیت های مجموعه	شمارش تعداد بیت های مجموعه (1s) در یک عدد صحیح.

موضوعات مرتبط:

• آموزش الگوریتم های بیتی
• تمرین مسئله روی الگوریتم های بیتی

3. آرایه

آرایه یک ساختار داده خطی است که مجموعه ای از عناصر از همان نوع داده را ذخیره می کند. عناصر به حافظه پیوسته تخصیص داده می شوند که امکان دسترسی با زمان ثابت را فراهم می کند. هر عنصر دارای یک شماره شاخص منحصر به فرد است.

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

4. ماتریس/شبکه

ماتریس یک آرایه دو بعدی از عناصر است که در ردیف ها و ستون ها مرتب شده اند . این به صورت یک شبکه مستطیل شکل نشان داده می شود که هر عنصر در تقاطع یک ردیف و ستون قرار دارد.

• مفاهیم کلیدی:
  • ردیف : خطوط افقی عناصر در یک ماتریس.
  • ستون ها : خطوط عمودی عناصر در یک ماتریس.
  • ابعاد : تعداد سطرها و ستون ها در یک ماتریس (مثلاً یک ماتریس 3×4 دارای 3 سطر و 4 ستون است).
  • دسترسی عنصر : عناصر را می توان با استفاده از شاخص های ردیف و ستون (به عنوان مثال، M[2][3] به عنصر در ردیف 2، ستون 3 اشاره دارد).
• کاربردهای ماتریس/شبکه :
  • پردازش تصویر
  • تجزیه و تحلیل داده ها
  • مشکلات بهینه سازی
• پست های مرتبط:
  • آموزش ماتریس/گرید
  • 50 مشکل برتر در ماتریس/گرید برای مصاحبه
  • تمرین مسائل روی ماتریس/شبکه

5. رشته

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

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

6. پشته

پشته یک ساختار داده خطی است که از ترتیب خاصی پیروی می کند که در آن عملیات انجام می شود. سفارش ممکن است LIFO (آخرین در اولین خروج) یا FILO (اول در آخرین خروج) باشد . LIFO به این معنی است که عنصری که در آخر وارد می شود، اول بیرون می آید و FILO به این معنی است که عنصری که اول درج می شود، آخرین بیرون می آید.

• عملیات روی پشته :
  • Push : یک عنصر را به بالای پشته اضافه می کند
  • Pop : عنصر بالای پشته را حذف و برمی گرداند
  • Peek : عنصر را در بالای پشته بدون حذف آن برمی گرداند
  • اندازه : تعداد عناصر موجود در پشته را برمی‌گرداند
  • IsEmpty : بررسی می کند که آیا پشته خالی است
• کاربردهای Stack :
  • فراخوانی تابع
  • ارزیابی بیان
  • عقب نشینی
  • لغو/دوباره عملیات
• موضوعات مرتبط در Stack:
  • آموزش پشته
  • 50 مشکل برتر در Stack for Interviews
  • مشکلات را در Stack تمرین کنید

7. صف

ساختار داده صف یک مفهوم اساسی در علوم کامپیوتر است که برای ذخیره و مدیریت داده ها در یک ترتیب خاص استفاده می شود. از اصل ” اول وارد، اول بیرون ” ( FIFO ) پیروی می کند، که در آن اولین عنصر اضافه شده به صف اولین عنصری است که حذف می شود.

• عملیات در صف :
  • Enqueue : یک عنصر را به پشت صف اضافه می کند
  • Dequeue : یک عنصر را از جلوی صف حذف می کند
  • Peek : عنصر جلویی را بدون حذف آن بازیابی می کند
  • IsEmpty : بررسی می کند که آیا صف خالی است
  • IsFull : بررسی می کند که آیا صف پر است
• نوع صف :
  • صف دایره ای : آخرین عنصر به اولین عنصر متصل می شود
  • صف دو طرفه (Deque) : عملیات را می توان از هر دو طرف انجام داد
  • صف اولویت : عناصر بر اساس اولویت مرتب می شوند
• کاربردهای صف :
  • زمان بندی کار
  • صف پیام
  • مدل سازی شبیه سازی
  • بافر داده ها
• موضوعات مرتبط:
  • آموزش صف
  • 50 مشکل برتر در صف مصاحبه
  • تمرین مشکلات در صف

8. بازگشت

بازگشت یک تکنیک برنامه نویسی است که در آن یک تابع خود را در تعریف خودش فراخوانی می کند. معمولاً برای حل مشکلاتی استفاده می شود که می توان آنها را به نمونه های کوچکتری از همان مشکل تقسیم کرد. به عنوان مثال: برج های هانوی (TOH) ، محاسبه فاکتوریل و دنباله فیبوناچی و غیره.

مراحل :

• Base Case : شرطی را تعریف کنید که تماس های بازگشتی را متوقف کند و راه حلی ارائه دهد.
• حالت بازگشتی : مراحلی را برای تجزیه مشکل به نمونه های کوچکتر و برقراری تماس های بازگشتی تعریف کنید.
• Return : راه حل را از تماس های بازگشتی برگردانید و آنها را برای حل مشکل اصلی ترکیب کنید.

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

موضوعات مرتبط:

• آموزش بازگشت
• توابع بازگشتی
• بازگشت دم
• 50 مشکل برتر در الگوریتم بازگشتی برای مصاحبه
• تمرین مشکلات روی الگوریتم بازگشت

9. الگوریتم عقبگرد

همانطور که قبلاً ذکر شد، الگوریتم Backtracking از الگوریتم Recursion مشتق شده است، با گزینه ای برای بازگشت در صورت شکست یک راه حل بازگشتی، یعنی در صورت شکست یک راه حل، برنامه به لحظه ای که در آن شکست خورده است ردیابی می کند و راه حل دیگری را ایجاد می کند. بنابراین اساساً تمام راه حل های ممکن را امتحان می کند و راه حل صحیح را پیدا می کند.

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

مشکل	توضیحات
مشکل تور نایت	یافتن دنباله ای از حرکات توسط یک شوالیه روی صفحه شطرنج به گونه ای که هر مربع را دقیقاً یک بار بازدید کند.
موش در پیچ و خم	یافتن مسیری از موقعیت شروع تا خروجی در پیچ و خم، با موانعی که به صورت دیوار نمایش داده می شوند.
مشکل N-Queen	قرار دادن N ملکه بر روی صفحه شطرنج N×N به طوری که هیچ دو ملکه به یکدیگر حمله نکنند.
مشکل جمع زیر مجموعه	تعیین اینکه آیا زیر مجموعه ای از مجموعه داده شده با مجموع معین وجود دارد یا خیر.
سودوکو	حل یک پازل شبکه ای 9×9 با اعداد از 1 تا 9 به طوری که هر سطر، ستون و زیرشبکه 3×3 شامل تمام ارقام بدون تکرار باشد.

مقاله مرتبط:

• آموزش عقب نشینی
• تمرین مشکلات روی الگوریتم Backtracking

10. الگوریتم تقسیم و غلبه

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

مراحل:

1. تقسیم : مسئله را به زیرمسئله های مستقل و کوچکتر تقسیم کنید.
2. Conquer : به صورت بازگشتی هر زیرمسئله را حل کنید.
3. ترکیب : راه حل های زیرمسئله ها را ادغام کنید تا جواب نهایی را به دست آورید.

مثال ها:

• Merge Sort: آرایه را به دو نیمه تقسیم می کند، هر نیمه را به صورت بازگشتی مرتب می کند و نیمه های مرتب شده را ادغام می کند.
• مرتب سازی سریع: یک عنصر محوری را انتخاب می کند، آرایه را بر اساس محور به دو زیرآرایه تقسیم می کند و هر زیرآرایه را به صورت بازگشتی مرتب می کند.

مقالات مرتبط:

• آموزش تفرقه بینداز
• تمرین مسائل در الگوریتم Divide And Conquer

11. الگوریتم های جستجو و مرتب سازی

1 . الگوریتم مرتب سازی

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

انواع مختلفی از الگوریتم های مرتب سازی وجود دارد. برخی از الگوریتم های پرکاربرد عبارتند از:

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

موضوعات مرتبط:

• آموزش مرتب سازی الگوریتم
• مرتب سازی برتر سوالات و مشکلات مصاحبه
• تمرین مسائل در الگوریتم مرتب سازی

2 . الگوریتم جستجو

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

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

12. لیست های پیوندی

لیست پیوندی یک ساختار داده خطی است که داده ها را در گره ها ذخیره می کند که توسط اشاره گر به هم متصل می شوند. بر خلاف آرایه ها، لیست های پیوندی در مکان های حافظه پیوسته ذخیره نمی شوند.

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

13. هش

هش کردن تکنیکی است که یک خروجی با اندازه ثابت (مقدار هش) از ورودی با اندازه متغیر با استفاده از فرمول های ریاضی به نام توابع هش تولید می کند . هش کردن برای تعیین یک فهرست یا مکان برای ذخیره یک آیتم در یک ساختار داده استفاده می شود که امکان بازیابی و درج کارآمد را فراهم می کند.

• مفاهیم کلیدی:
  • تابع هش : یک تابع ریاضی که یک ورودی را به مقدار هش نگاشت می کند.
  • جدول هش : ساختار داده ای که جفت های کلید-مقدار را ذخیره می کند، جایی که کلید یک مقدار هش و مقدار داده واقعی است.
  • برخورد : زمانی که دو کلید مختلف مقدار هش یکسانی تولید می کنند.
• انواع توابع هش :
  • روش تقسیم : ورودی را بر یک ثابت تقسیم می کند و از باقی مانده به عنوان مقدار هش استفاده می کند.
  • روش Mid Square : ورودی را مربع می کند و ارقام میانی را به عنوان مقدار هش می گیرد.
  • روش تاشو : ورودی را به بلوک‌هایی با اندازه مساوی تقسیم می‌کند و آنها را با هم جمع می‌کند تا مقدار هش را به دست آورد.
  • روش ضرب : ورودی را در یک ثابت ضرب می کند و قسمت کسری را به عنوان مقدار هش می گیرد.

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

14. درخت

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

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

طبقه بندی	توضیحات	تایپ کنید	توضیحات
با مدرک	درختان را می توان بر اساس حداکثر تعداد فرزندانی که هر گره می تواند داشته باشد طبقه بندی کرد.	درخت دودویی	هر گره حداکثر دو فرزند دارد.
		درخت سه تایی	هر گره حداکثر سه فرزند دارد.
		درخت N-ary	هر گره حداکثر N فرزند دارد.
با سفارش	درختان را می توان بر اساس ترتیب گره ها و زیردرخت ها طبقه بندی کرد	درخت جستجوی دودویی (BST)	فرزند چپ < والد < فرزند راست برای هر گره.
		پشته	درخت باینری تخصصی با خاصیت heap.
توسط تعادل	درختان را می توان بر اساس میزان متعادل بودن آنها طبقه بندی کرد.	درخت متعادل	ارتفاع درختان فرعی حداکثر یک تفاوت دارد. به عنوان مثال می توان به درختان AVL و درختان قرمز-سیاه اشاره کرد.
		درخت نامتعادل	ارتفاع درختان فرعی می تواند به طور قابل توجهی متفاوت باشد و بر عملکرد در عملیات هایی مانند جستجو و درج تأثیر بگذارد.

• کاربرد درختان:
  • سیستم های فایل
  • پایگاه های داده
  • اسناد XML
  • هوش مصنوعی
• پست های مرتبط:
  • آموزش درخت
  • 50 مشکل اصلی کدگذاری درختی
  • تمرین مشکلات روی درخت

15. پشته

Heap یک ساختار داده درختی باینری کامل است که ویژگی heap را برآورده می کند: برای هر گره، ارزش فرزندان آن کمتر یا برابر با مقدار خودش است . Heaps معمولا برای اجرای صف های اولویت استفاده می شود ، جایی که کوچکترین (یا بزرگترین) عنصر همیشه در ریشه درخت است.

• عملیات هیپ :
  • Insert : یک عنصر جدید به پشته اضافه می کند و در عین حال ویژگی های heap را حفظ می کند.
  • Extract-Max/Extract-Min : عنصر ریشه را حذف می کند و هیپ را بازسازی می کند.
  • Increase/Decrease-Key : مقدار یک گره را به روز می کند و پشته را بازسازی می کند.
• انواع هیپ :
  • Max-Heap : گره ریشه بیشترین مقدار را در بین فرزندان خود دارد.
  • Min-Heap : گره ریشه در بین فرزندان خود حداقل مقدار را دارد.
• کاربردهای Heap :
  • صف های اولویت دار
  • مرتب سازی
  • الگوریتم های نمودار (به عنوان مثال، الگوریتم دایکسترا)
• پست های مرتبط:
  • آموزش هیپ
  • 50 مشکل برتر در Heap for Interviews
  • تمرین مشکلات روی Heap

16. نمودار

گراف یک ساختار داده غیر خطی است که از مجموعه محدودی از راس ها (یا گره ها) و مجموعه ای از یال ها تشکیل شده است که یک جفت گره را به هم متصل می کند .

• پیمایش نمودار:
  • Breadth-First Search (BFS) : گره ها را سطح به سطح بازدید می کند.
  • Depth-First Search (DFS) : گره ها را به صورت بازگشتی بازدید می کند و هر بار یک شاخه را کاوش می کند.
• کاربردهای نمودارها :
  • شبکه های اجتماعی
  • نقشه ها و ناوبری
  • برنامه ریزی
  • داده کاوی
• پست های مرتبط:
  • نمایش نمودار
  • انواع نمودارها
  • آموزش نمودار
  • تمرین مسائل روی نمودار

19. الگوریتم های حریص

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

برخی از مشکلات مهم الگوریتم های حریص عبارتند از:

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

مقالات مرتبط:

• آموزش الگوریتم حریص
• تمرین مسائل روی الگوریتم Greedy

17. برنامه نویسی پویا

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

مفاهیم کلیدی:

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

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

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

مقالات مرتبط:

• جدول بندی در مقابل حافظه سازی
• چگونه یک مشکل برنامه نویسی پویا را حل کنیم؟
• آموزش برنامه نویسی پویا
• 50 مشکل کدنویسی برنامه نویسی پویا برای مصاحبه
• تمرین مسائل روی الگوریتم برنامه نویسی پویا

18. الگوریتم های نمودار

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

موضوع	توضیحات موضوع	الگوریتم	توضیحات الگوریتم
پیمایش نمودار	تکنیک های بازدید از تمام رئوس در یک نمودار.	جستجوی اول عمق (DFS)	قبل از عقب نشینی، تا آنجایی که ممکن است در امتداد هر شاخه کاوش می کند.
		جستجوی اول عرض (BFS)	رئوس همسایه را قبل از رفتن به سطح بعدی رئوس کاوش می کند.
حداقل درختان پوشا	Minimum Spanning Trees کوچک‌ترین درخت‌هایی هستند که همه گره‌ها را در یک نمودار بدون تشکیل چرخه به هم متصل می‌کنند و با افزودن کوتاه‌ترین یال‌های ممکن به دست می‌آیند.	الگوریتم کروسکال	حداقل درخت پوشا را برای یک نمودار وزنی متصل پیدا می کند. کوچکترین لبه وزنی را اضافه می کند که چرخه ای تشکیل نمی دهد.
		الگوریتم پریم	همچنین یک درخت پوشا حداقل برای یک نمودار وزنی متصل پیدا می کند. این کوچکترین لبه وزن را اضافه می کند که دو درخت را به هم متصل می کند.
مرتب سازی توپولوژیکی	مرتب‌سازی توپولوژیکی یک ترتیب خطی رئوس در یک گراف غیر چرخه‌ای جهت‌دار (DAG) است، به‌طوری‌که برای هر یال جهت‌دار از راس u تا راس v، u قبل از v در ترتیب قرار می‌گیرد.	الگوریتم کان	الگوریتم کان نظم توپولوژیکی یک گراف غیر چرخه ای جهت دار (DAG) را پیدا می کند.
		الگوریتم مبتنی بر DFS	الگوریتم مبتنی بر DFS از جستجوی Depth-First برای انجام مرتب‌سازی توپولوژیکی در یک گراف غیر چرخه‌ای جهت‌دار (DAG) استفاده می‌کند.
کوتاه ترین مسیر	کوتاه‌ترین مسیر در یک گراف، مسیری است که بین دو رأس در گراف وجود دارد که دارای حداقل مجموع وزن‌ها در لبه‌های آن در مقایسه با سایر مسیرهای بین همان دو راس است.	الگوریتم دایکسترا	الگوریتم حریص برای یافتن کوتاه ترین مسیر بین تمام گره ها در زمان O(E * V logV).
		الگوریتم فلوید-وارشال	کوتاه ترین مسیر را بین تمام جفت گره ها در زمان O(V^3) پیدا می کند.
		الگوریتم بلمن فورد	کوتاه ترین مسیر را از یک منبع در زمان O(V * E) پیدا می کند.
		الگوریتم جانسون	کوتاه ترین مسیرها را بین تمام جفت رئوس در زمان O(V^2 logV + V * E) پیدا می کند.
اجزای قوی به هم متصل	یک مولفه به شدت متصل (SCC) یک گراف جهت دار، مجموعه حداکثری از رئوس است به طوری که یک مسیر از هر رأس در مجموعه به هر رأس دیگر در مجموعه وجود دارد.	الگوریتم کوساراجو	الگوریتم کوساراجو یک الگوریتم دو گذری است که به طور موثر مولفه های متصل قوی (SCC) یک گراف جهت دار را پیدا می کند.
		الگوریتم ترجان	الگوریتم ترجان یکی دیگر از الگوریتم های کارآمد برای یافتن SCC در یک گراف جهت دار است.

موضوعات مرتبط:

• آموزش نمودار
• 50 مشکل اصلی کدنویسی نمودار برای مصاحبه
• تمرین مسئله روی الگوریتم های نمودار

19 . جستجوی الگو

جستجوی الگو یک تکنیک اساسی در DSA است که برای یافتن رخدادهای یک الگوی خاص در یک متن خاص استفاده می شود.

در زیر برخی از الگوریتم های استاندارد جستجوی الگو آورده شده است:

الگوریتم	توضیحات	پیچیدگی زمانی
Brute-Force	این الگو را با هر زیر رشته ای از متن مقایسه می کند	O(mn)
کنوت-موریس-پرات	از یک تابع شکست از پیش محاسبه شده برای پرش از مقایسه های غیر ضروری استفاده می کند	O(m + n)
بویر مور	این الگو را از راست به چپ مقایسه می‌کند و از نویسه‌ها بر اساس آخرین عدم تطابق پرش می‌کند	O(mn)
رابین-کارپ	از هش برای بررسی سریع موارد بالقوه استفاده می کند	O(m + n)

موضوعات مرتبط:

• آموزش جستجوی الگو
• تمرین مسئله در جستجوی الگو

20. الگوریتم شاخه و کران

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

مسائل استاندارد در الگوریتم شاخه و کران:

مشکل منحصر به فرد	توضیحات
0/1 کوله پشتی با استفاده از Branch and Bound	جزئیات پیاده سازی رویکرد شاخه و کران برای حل مشکل کوله پشتی 0/1.
0/1 کوله پشتی با استفاده از کمترین هزینه شاخه و محدود	حل مسئله کوله پشتی 0/1 با استفاده از تکنیک شاخه و کران با کمترین هزینه.
8 مشکل پازل با استفاده از شاخه و کران	استفاده از شاخه و باند برای حل مشکل پازل 8، یک بازی پازل کشویی محبوب.
مسئله N ملکه با استفاده از Branch و Bound	استفاده از شاخه و مقید برای یافتن راه حل برای مسئله N کوئینز، یک مسئله شطرنج کلاسیک.

موضوعات مرتبط:

• آموزش الگوریتم شاخه و کران

21. الگوریتم های هندسی

الگوریتم های هندسی دسته ای از الگوریتم ها هستند که مسائل مربوط به هندسه را حل می کنند. الگوریتم های هندسی برای حل طیف وسیعی از مسائل در علوم کامپیوتر ضروری هستند، مانند:

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

موضوعات مرتبط:

• تمرین مسئله روی الگوریتم های هندسی

22. الگوریتم های تصادفی

الگوریتم های تصادفی الگوریتم هایی هستند که از تصادفی بودن برای حل مسائل استفاده می کنند. آنها از ورودی های تصادفی برای دستیابی به اهداف خود استفاده می کنند که اغلب به راه حل های ساده تر یا کارآمدتر منجر می شود.

انواع الگوریتم های تصادفی:

• لاس وگاس : همیشه یک نتیجه درست ایجاد می کند، اما زمان اجرا تصادفی است.
• مونت کارلو : ممکن است با احتمال کمی نتیجه نادرست ایجاد کند، اما زمان اجرا معمولا سریعتر است.

الگوریتم های مهمی که از الگوریتم های تصادفی سازی استفاده می کنند:

الگوریتم	توضیحات
QuickSort	یک الگوریتم مرتب‌سازی تصادفی با پیچیدگی زمانی متوسط ​​O (n log n).
فهرست پرش	یک ساختار داده تصادفی که عملیات جستجو و درج سریع را فراهم می کند.
فیلتر شکوفه	یک ساختار داده احتمالی برای تست عضویت مجموعه کارآمد

برگه های تقلب مشکل را تمرین کنید

لیست های انتخاب شده از مشکلات از مقالات زیر:

• نقشه راه DSA توسط Sandeep Jain
• برگه SDE – راهنمای کامل برای آماده سازی SDE
• GeeksforGeeks Master Sheet – لیست تمام برگه های تقلب