مدل‌های زبانی جدید مثل Claude از Anthropic، GPT از OpenAI، Llama و دیگر مدل‌ها، از معماری‌های Decoder-only به جای Encoder-Decoder استفاده می‌کنند. این معماری Decoder-only یا Auto-regressive در سال ۲۰۱۸ با عرضه مدل‌های GPT توسط OpenAI محبوب شد. بعدتر، سری Claude هم با همین معماری ساخته شد.

🤔 چرا معماری فقط رمزگشا (Decoder-only) محبوب شده است؟

در معماری Decoder-only، مدل به شکل Unsupervised و بر روی داده‌های متنی بدون برچسب آموزش داده می‌شود که به‌راحتی قابل دسترسی است. در این حالت، مدل برای پیش‌بینی توکن بعدی آموزش می‌بیند که داده‌های آموزشی را به آسانی در دسترس قرار می‌دهد.

📌 تفاوت اصلی؟
نحوه ترکیب اطلاعات Input Source در رمزگشا.

- Decoder-only از Unidirectional Cross Attention استفاده می‌کند که همزمان به هر دو ماتریس منبع و هدف توجه می‌کند.
- به دلیل توجه به تمام ویژگی‌ها در یک Attention، ماتریس خروجی لایه توجه به ماتریس منبع کمتر حساس می‌شود؛ به‌خصوص وقتی که مدل کلمات زیادی تولید کرده و جمله نسبتاً طولانی شده باشد.

این مشکل به نام Attention Degeneration شناخته می‌شود، که البته قابل حل است.



💡 مزایای مدل‌های فقط رمزگشا (Language Model یا LM) نسبت به رمزگذار-رمزگشا

1️⃣ از تکنیک Parameter Sharing استفاده می‌کند که باعث می‌شود پارامترها برای شبکه‌هایی که هر دو دنباله منبع و هدف را مدیریت می‌کنند، مشترک باشد. این کار اندازه مدل را کاهش داده و عملکرد را بهبود می‌بخشد.

2️⃣ مدل Decoder-only شامل مکانیزم Layer-wise Coordination است که به رمزگشا امکان می‌دهد به خروجی لایه‌های متناظر رمزگذار دسترسی داشته باشد، و به این شکل، به اطلاعات در سطوح مختلف منبع دسترسی پیدا کند.

3️⃣ ماتریس توجه برای Decoder-only یک ماتریس Full Rank است چرا که به شکل Triangular است. این ویژگی آن را از ماتریس توجه Encoder-Decoder برتر می‌سازد.



❓ آیا معماری Encoder-Decoder کاملاً منسوخ شده است؟ خیر!

مدل Encoder-Decoder در Machine Translation یا ترجمه ماشینی بهتر عمل می‌کند. این زمانی است که Input و Output از اساس متفاوت باشند یا هدف خروجی به‌طور قابل توجهی کوتاه‌تر از ورودی باشد. در چنین حالتی دو پشته مجزا مورد نیاز است. به عنوان مثال در ترجمه از انگلیسی به زبان‌های دیگر، معماری Encoder-Decoder بهتر کار می‌کند.

همچنین، مدل‌های فقط رمزگشا محدودیت‌هایی در Transfer Learning دارند.

🔍 جمع‌بندی:

اکثر Language Models جدید به سمت Generalization گرایش دارند. در نتیجه، مدل‌های فقط رمزگشا برای این هدف بهتر کار می‌کنند و نسبت به معماری سنتی Encoder-Decoder آسان‌تر آموزش داده می‌شوند.


📄 برای اطلاعات بیشتر و مقایسه تجربی میان ED و LM (Decoder-only) به مقاله زیر مراجعه کنید:

https://arxiv.org/pdf/2304.04052

#هوش_مصنوعی
📣👨‍💻 @AlgorithmDesign_DataStructuer

"یک نمایش مشترک با استفاده از ویژگی‌های Continuous و Discrete برای پیش‌بینی ریسک Cardiovascular Diseases روی اسکن‌های Chest CT"

Github: https://github.com/yhygao/cbim-medical-image-segmentation

Paper: https://arxiv.org/abs/2410.18610v1

Supported models: https://arxiv.org/abs/2203.00131

#هوش_مصنوعی
📣👨‍💻 @AlgorithmDesign_DataStructuer

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

#الگوریتم
📣👨‍💻 @AlgorithmDesign_DataStructuer

پروژه تحلیل قیمت املاک تهران 🏡📊

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

🌟 مراحل کلیدی پروژه:
1. پیش‌پردازش داده‌ها: شناسایی و مدیریت داده‌های پرت، پاک‌سازی و استخراج ویژگی‌های کلیدی.
2. تحلیل اکتشافی داده‌ها: بررسی الگوهای قیمتی در محله‌های مختلف تهران و تحلیل ویژگی‌هایی مانند متراژ، سال ساخت و امکانات.
3. بصری‌سازی و ارائه نتایج: ایجاد نقشه‌های تعاملی برای نمایش توزیع آگهی‌ها و تحلیل روندهای قیمتی در مناطق مختلف تهران.
4. مدل‌سازی و پیش‌بینی قیمت: استفاده از الگوریتم Random Forest Regressor برای پیش‌بینی قیمت‌ها.

📊 ابزارها و کتابخانه‌های استفاده‌شده:
Python 🐍 | Pandas | Seaborn | Matplotlib | Folium | Scikit-learn | Geopy

💭 نکته مهمی که در این پروژه یاد گرفتم: مدیریت دقیق داده‌های پرت و اهمیت آن در افزایش دقت مدل‌های پیش‌بینی.

لینک دیتاست پروژه در سایت Kaggle موجود است.
https://www.kaggle.com/datasets/raoofiali/divar-house-adv-dataset

#هوش_مصنوعی
📣👨‍💻 @AlgorithmDesign_DataStructuer

❇️ 3D Reconstruction with Spatial Memory


🔗 Discover More:
* Source Code: GitHub
* Project Page: Spann3R
* Supplement Video: Try it here
* Paper: Read the paper

#هوش_مصنوعی
📣👨‍💻 @AlgorithmDesign_DataStructuer

✳️ معرفی الگوریتم‌های جستجو: DFS و BFS ✳️

🔹 DFS (Depth-First Search) - جستجوی عمق‌اول:

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

- پیچیدگی زمانی: در گراف‌های با ( n ) رأس و ( m ) یال، O(n + m)
- پیچیدگی فضایی: در حالت بدترین، O(n)
- کاربردها: حل پازل‌ها، یافتن مسیرها در گراف‌ها، و شناسایی اجزای متصل.



🔹 BFS (Breadth-First Search) - جستجوی عرض‌اول:

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

- پیچیدگی زمانی: در گراف‌های با ( n ) رأس و ( m ) یال، O(n + m)
- پیچیدگی فضایی: در حالت بدترین، O(n)
- کاربردها: یافتن کوتاه‌ترین مسیر، شبکه‌های اجتماعی و موتورهای جستجو.



📊 مقایسه کلی: DFS برای جستجوی عمیق در گراف و حل مسائل پازلی مفید است، در حالی که BFS برای پیدا کردن کوتاه‌ترین مسیرها به‌ویژه در گراف‌های بدون وزن به کار می‌رود.

#الگوریتم
📣👨‍💻 @AlgorithmDesign_DataStructuer

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

Paper : https://arxiv.org/abs/2211.14730

#هوش_مصنوعی
📣👨‍💻 @AlgorithmDesign_DataStructuer

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

#الگوریتم
📣👨‍💻 @AlgorithmDesign_DataStructuer

📘 جزوه هوش مصنوعی استاد زارچی
نیمسال 99 | دانشگاه صنعتی شریف

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

#هوش_مصنوعی
📣👨‍💻 @AlgorithmDesign_DataStructuer

Accelerating Transformers with Spectrum-Preserving Token Merging

Github: https://github.com/hchautran/PiToMe

Paper: https://arxiv.org/abs/2405.16148

Dataset: https://paperswithcode.com/dataset/flickr30k

#هوش_مصنوعی
📣👨‍💻 @AlgorithmDesign_DataStructuer

این ویدیو الگوریتم‌های مختلف مرتب‌سازی را به تصویر می‌کشد و به نمایش می‌گذارد که چگونه هر کدام از آن‌ها عملیات مرتب‌سازی را انجام می‌دهند. 🌟📊

#الگوریتم
📣👨‍💻 @AlgorithmDesign_DataStructuer

حتماً برای شما هم این سوال پیش آمده که مدل‌های بزرگ زبانی (LLM) چگونه اطلاعات را ذخیره می‌کنند. مثلاً یک مدل مانند ChatGPT چطور می‌تواند حجم زیادی از اطلاعات را از کل اینترنت جمع‌آوری و یاد بگیرد؟ این داده‌ها در کجای شبکه‌های عصبی ذخیره می‌شوند؟

پیشنهاد می‌کنم ویدئوی از 3blue1brown را ببینید! 📹✨

#هوش_مصنوعی
📣👨‍💻 @AlgorithmDesign_DataStructuer

📌 RAG Showdown: Vector vs. Graph - Shaping the Future of AI Applications! 🔥
پیاده‌سازی RAG (ترکیب بازیابی و تولید) با دو روش متفاوت امکان‌پذیر است: یکی با استفاده از دیتابیس برداری و دیگری با استفاده از گراف دانش. هر دو روش با هدف بازیابی داده‌های مرتبط و تولید پاسخ دقیق به کاربر استفاده می‌شوند، اما هر کدام ویژگی‌های خاص خود را دارند:

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

🔗 RAG با گراف دانش:
اینجا از روابط و ساختار داده‌ها استفاده می‌شود. جستجو در گراف انجام شده و نهادها و ارتباطات مرتبط استخراج می‌شوند. این روش برای حوزه‌هایی که نیاز به فهم عمیق روابط دارند، بسیار مفید است.

🔍 جمع‌بندی:
هر دو روش قابل پیاده‌سازی در پلتفرم‌های داده‌ای مانند SingleStore هستند و بسته به نیازهای شما، می‌توانید یکی از این روش‌ها را انتخاب کنید.

#هوش_مصنوعی
📣👨‍💻 @AlgorithmDesign_DataStructuer

🚀 الگوریتم بلمن فورد (Bellman-Ford)

الگوریتم بلمن فورد یکی از الگوریتم‌های مهم برای یافتن کوتاه‌ترین مسیرها در گراف‌های وزن‌دار است. 💡 این الگوریتم به شما اجازه می‌دهد که از یک رأس شروع کرده و مسیرهای با کمترین وزن را به تمام رأس‌های دیگر گراف پیدا کنید. یک ویژگی بارز بلمن فورد این است که با یال‌های دارای وزن منفی هم به خوبی کار می‌کند و حتی چرخه‌های منفی را هم می‌تواند شناسایی کند. 🔍

🎯 مراحل اجرای الگوریتم
مقداردهی اولیه: ابتدا فاصله (وزن مسیر) از رأس شروع به خودش برابر با صفر و برای سایر رأس‌ها بی‌نهایت در نظر گرفته می‌شود. 🟢

به‌روزرسانی وزن‌ها: الگوریتم برای هر یال در گراف، |V|-1 بار تکرار می‌شود، که در آن |V| تعداد رأس‌ها است. در هر مرحله، اگر مسیر کوتاه‌تری یافت شود، وزن آن مسیر به‌روزرسانی می‌شود. 🔄

بررسی چرخه‌های منفی: در پایان، همه یال‌ها یک بار دیگر بررسی می‌شوند. اگر وزنی تغییر نکرد، گراف چرخه منفی ندارد؛ در غیر این صورت، الگوریتم چرخه منفی را شناسایی کرده و می‌تواند اطلاع دهد که گراف شامل یک چرخه منفی است. ⚠️

⏱️ پیچیدگی زمانی
پیچیدگی زمانی الگوریتم بلمن فورد O(V×E) است، که در آن V تعداد رأس‌ها و E تعداد یال‌هاست. به دلیل این پیچیدگی زمانی، این الگوریتم نسبت به الگوریتم‌هایی مثل دایکسترا کمی کندتر است، اما می‌تواند یال‌های منفی را مدیریت کند. 🕰

🌐 کاربردهای بلمن فورد
شناسایی چرخه‌های منفی: این ویژگی در مدل‌سازی مسائل مالی و اقتصادی کاربرد دارد، جایی که چرخه‌های منفی ممکن است نشان‌دهنده فرصت‌های آربیتراژ یا خطاهای سیستمی باشند. 📉
یافتن کوتاه‌ترین مسیرها در شبکه‌های دارای وزن منفی: این ویژگی در شبکه‌های جریان کالا و مسیر‌یابی بهینه در سیستم‌های ارتباطی استفاده می‌شود. 🌍
📝 مثال کاربردی
فرض کنید یک گراف با یال‌های دارای وزن مثبت و منفی داریم. الگوریتم بلمن فورد می‌تواند از یک رأس شروع کرده و به تمامی رأس‌های دیگر دسترسی پیدا کند و اگر چرخه منفی‌ای وجود داشته باشد، آن را شناسایی کند. 🔄

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

#الگوریتم
📣👨‍💻 @AlgorithmDesign_DataStructuer

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



🌟 مرتب‌سازی انتخابی (Selection Sort)
- بازگشتی نیست و از پشته استفاده نمی‌کند.
- پیچیدگی فضایی: O(1) (فقط فضای ثابت نیاز دارد).



🛁 مرتب‌سازی حبابی (Bubble Sort)
- بازگشتی نیست و نیازی به پشته ندارد.
- پیچیدگی فضایی: O(1) (فضای ثابت).



✍️ مرتب‌سازی درجی (Insertion Sort)
- بازگشتی نیست و از پشته استفاده نمی‌کند.
- پیچیدگی فضایی: O(1) (صرفاً فضای ثابت).



📐 مرتب‌سازی ادغامی (Merge Sort)
- بازگشتی است و برای فراخوانی‌های بازگشتی از پشته استفاده می‌کند.
- پیچیدگی فضایی: (O(n (نیازمند آرایه موقت)، فضای پشته: O(log n).



⚡️ مرتب‌سازی سریع (Quick Sort)
- بازگشتی است و از پشته استفاده می‌کند.
- پیچیدگی فضایی در بدترین حالت: O(n)؛ در حالت متوسط: O(log n)).



🔺 مرتب‌سازی هرمی (Heap Sort)
- غیربازگشتی است و از پشته استفاده نمی‌کند.
- پیچیدگی فضایی: O(1) (فقط فضای ثابت نیاز دارد).


به طور خلاصه، الگوریتم‌های بازگشتی مثل Merge Sort و Quick Sort به پشته نیاز دارند، در حالی که سایر الگوریتم‌های غیربازگشتی بدون استفاده از پشته و در فضای ثابت اجرا می‌شوند.

#الگوریتم
📣👨‍💻 @AlgorithmDesign_DataStructuer

Shortest Path Algorithms Explained (Dijkstra's & Bellman-Ford)

#الگوریتم
📣👨‍💻 @AlgorithmDesign_DataStructuer

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

Paper : https://www.researchgate.net/publication/382528886_Translating_Old_Persian_cuneiform_by_artificial_intelligence_AI

#هوش_مصنوعی
📣👨‍💻 @AlgorithmDesign_DataStructuer

انگیزه یادگیری تئوری در داده‌کاوی و یادگیری ماشین

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

هدف این راهنما

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

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

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

پیشنهاد من: رویکرد "از بالا به پایین"

ابتدا مهارت‌های برنامه‌نویسی را یاد بگیرید، با ابزارهای PyData مثل Pandas، sklearn و Keras کار کنید، پروژه‌های واقعی انجام دهید و از مستندات کتابخانه‌ها و آموزش‌های آنلاین بهره ببرید. با این روش، وقتی در کار عملی به مشکلات برمی‌خورید، نیاز به مبانی تئوری را بهتر درک می‌کنید؛ در این مرحله، مطالعه ریاضیات برایتان مفهومی‌تر و جذاب‌تر خواهد بود.

معرفی منابع

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

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

1-Khan Academy Linear Algebra series (beginner-friendly).
2-Coding the Matrix course (and book).
3-3Blue1Brown Linear Algebra series.
4-fast.ai Linear Algebra for coders course, highly related to modern ML workflow.
5-The first course in Coursera Mathematics for Machine Learning specialization.
6-“Introduction to Applied Linear Algebra — Vectors, Matrices, and Least Squares” book.
7-MIT Linear Algebra course, highly comprehensive.
7-Stanford CS229 Linear Algebra review.

- حساب دیفرانسیل و انتگرال
در یادگیری ماشین، حساب دیفرانسیل و انتگرال برای تعریف و ایجاد توابعی استفاده می‌شود که هدف و کارایی الگوریتم‌ها را مشخص می‌کنند؛ این توابع به عنوان توابع هزینه یا هدف شناخته می‌شوند.

1-Khan Academy Calculus series (beginner-friendly).
2-3Blue1Brown Calculus series.
3-The second course in Coursera Mathematics for Machine Learning specialization.
4-The Matrix Calculus You Need For Deep Learning paper.
5-MIT Single Variable Calculus.
6-MIT Multivariable Calculus.
7-Stanford CS224n Differential Calculus review.

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

1-Khan Academy Statistics and probability series (beginner-friendly).
2-Seeing Theory: A visual introduction to probability and statistics.
3-Intro to Descriptive Statistics from Udacity.
4-Intro to Inferential Statistics from Udacity.
5-Statistics with R Specialization from Coursera.
6-Stanford CS229 Probability Theory review.

#هوش_مصنوعی
📣👨‍💻 @AlgorithmDesign_DataStructuer

📄 اگر به موضوع شبکه‌های عصبی پیچشی (CNN) برای طبقه‌بندی داده‌ها علاقه‌مند هستید، این فایل PDF می‌تواند منبع بسیار مفیدی برای شما باشد. این فایل به طور خلاصه و کاربردی، نحوه عملکرد CNNها و استفاده از آن‌ها در مسائل طبقه‌بندی داده‌ها را توضیح می‌دهد. با مطالعه این فایل، می‌توانید دید بهتری نسبت به ساختار و کاربرد CNNها پیدا کنید و آن‌ها را در پروژه‌های خود به کار بگیرید. 🌐📊

حتماً مطالعه‌اش کنید و اگر سوالی داشتید، در بخش نظرات بپرسید! 🧑‍💻📚

#هوش_مصنوعی
📣👨‍💻 @AlgorithmDesign_DataStructuer

تصویر 👆🏻👆🏻به شکلی ساده و گویا رابطه‌ی بین کلاس‌های پیچیدگی در علوم کامپیوتر را نشان می‌دهد و فرض می‌کند که P!=NP است. در ادامه توضیح مختصری برای هر بخش ارائه می‌شود:

🔹 کلاس P: این کلاس شامل مسائلی است که می‌توان آن‌ها را با الگوریتم‌های قطعی و در زمان چندجمله‌ای (polynomial time) حل کرد. به عبارت دیگر، این مسائل برای کامپیوترها قابل حل هستند و زمان زیادی نیاز ندارند. این دسته از مسائل ساده‌تر هستند و الگوریتم‌های کارآمدی برای آن‌ها وجود دارد.
💡 مثال: مسئله‌ی "کوتاه‌ترین مسیر" که در آن می‌خواهیم کوتاه‌ترین مسیر بین دو نقطه را پیدا کنیم.

🔹 کلاس NP: این کلاس شامل مسائلی است که اگر جوابشان به ما داده شود، می‌توانیم در زمانی چندجمله‌ای (با استفاده از یک الگوریتم) آن را تأیید کنیم، اما پیدا کردن جواب خود مسئله ممکن است زمان زیادی ببرد. این بدان معناست که اگر جوابی داشته باشیم، تأیید آن آسان است؛ ولی یافتن جواب قطعی ممکن است زمان‌بر باشد.
💡 نکته: NP شامل P هم می‌شود؛ چراکه اگر بتوانیم مسئله‌ای را سریع حل کنیم، قطعاً می‌توانیم جواب آن را هم سریع تأیید کنیم.

🔸 کلاس NP-کامل (NP-Complete): این دسته از مسائل، پیچیده‌ترین مسائل در NP هستند. این مسائل هم در NP هستند و هم ویژگی خاصی دارند که اگر بتوانیم یک مسئله NP-کامل را در زمانی چندجمله‌ای حل کنیم، می‌توانیم تمام مسائل NP را نیز در زمانی چندجمله‌ای حل کنیم. این مسائل برای پژوهشگران و متخصصان علوم کامپیوتر چالش‌برانگیز هستند.
💡 مثال: مسئله‌ی "پوشش رأس" (Vertex Cover) که یک مسئله‌ی کلاسیک NP-کامل است و پیدا کردن راه‌حل آن به‌ویژه برای ورودی‌های بزرگ دشوار است.

🔸 کلاس NP-سخت (NP-Hard): این کلاس شامل مسائلی است که سختی آن‌ها حداقل به اندازه‌ی مسائل NP-کامل است، اما لزوماً در NP نیستند. به این معنی که حتی ممکن است نتوانیم به راحتی جواب آن‌ها را تأیید کنیم. این دسته شامل مسائلی مانند "مشکل توقف تورینگ" (Turing Halting Problem) است که در آن حتی تأیید کردن جواب نیز دشوار و در برخی موارد غیرممکن است.
💡 مثال: "مشکل توقف تورینگ" که یکی از پیچیده‌ترین مسائل محاسباتی است.

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

#الگوریتم
📣👨‍💻 @AlgorithmDesign_DataStructuer