الگوریتم Kruskal برای یافتن درخت پوشای کمینه (Minimum Spanning Tree - MST)

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



🌟 گام‌های الگوریتم Kruskal:

1. مرتب‌سازی یال‌ها: ابتدا تمام یال‌های گراف را به ترتیب وزن از کم به زیاد مرتب می‌کنیم.

2. ایجاد مجموعه‌های ناپیوسته: برای هر رأس یک مجموعه مجزا تشکیل می‌دهیم (در ابتدا هر رأس به تنهایی یک مجموعه است).

3. اضافه کردن یال‌ها به MST:
- یال‌ها را یکی یکی از کمترین وزن به بزرگترین بررسی می‌کنیم.
- اگر اضافه کردن یک یال باعث ایجاد حلقه نشود، آن را به درخت پوشا اضافه می‌کنیم.
- اگر یال باعث ایجاد حلقه شود، آن را نادیده می‌گیریم.

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



⏱️ پیچیدگی زمانی الگوریتم:

الگوریتم Kruskal شامل دو بخش اصلی است:

1. مرتب‌سازی یال‌ها: با استفاده از الگوریتم‌های مرتب‌سازی سریع مانند Merge Sort یا Quick Sort، پیچیدگی زمانی این مرحله O(Elog E) است که E تعداد یال‌های گراف است.

2. جستجوی مجموعه‌ها و ترکیب آن‌ها: برای مدیریت مجموعه‌ها از ساختار داده‌ای Union-Find استفاده می‌شود که با بهینه‌سازی‌هایی مانند فشرده‌سازی مسیر (Path Compression) و اتحاد بر اساس رتبه (Union by Rank)، پیچیدگی زمانی این عملیات‌ها به O(α(V)) کاهش می‌یابد.

به طور کلی، پیچیدگی زمانی الگوریتم برابر است با:


O(E log E + E α(V))


که در آن E تعداد یال‌ها و V تعداد رأس‌های گراف است. از آنجایی که E log E سریع‌تر از E α(V) رشد می‌کند، پیچیدگی زمانی کلی O(E log E) است.



📊 ویژگی‌ها و کاربردها:

- نوع الگوریتم: حریصانه (Greedy)
- کاربردها:
- ساخت درخت پوشای کمینه در شبکه‌های ارتباطی.
- کاهش هزینه‌های طراحی شبکه.
- حل مسائل بهینه‌سازی گراف‌ها.

- محدودیت‌ها:
- مناسب برای گراف‌های پراکنده (Sparse). برای گراف‌های متراکم (Dense)، الگوریتم‌های دیگر مانند Prim ممکن است عملکرد بهتری داشته باشند.



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

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

یادآوری مهم برای ثبت‌نام کنکور کارشناسی ارشد

دوستان عزیز،
به اطلاع می‌رساند مهلت ثبت‌نام برای کنکور کارشناسی ارشد از ۲۲ مهر ۱۴۰۳ تا ۲۸ مهر ۱۴۰۳ می‌باشد. لطفاً برای جلوگیری از هرگونه مشکل در آخرین لحظات، هرچه سریع‌تر نسبت به ثبت‌نام خود اقدام نمایید.

🔹 مهلت ثبت‌نام: ۲۲ مهر ۱۴۰۳ تا ۲۸ مهر ۱۴۰۳
🔹 وب‌سایت ثبت‌نام: (سایت سنجش)


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

💠 https://t.me/Se_mohamad

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

1. مدل‌سازی ساختارهای پیچیده 🔄
گراف‌ها به ما اجازه می‌دهند تا روابط پیچیده بین اشیاء را به‌صورت ساده و قابل درک نشان دهیم. به عنوان مثال:
- در شبکه‌های اجتماعی 👥، کاربران به عنوان گره‌ها و دوستی‌ها به عنوان یال‌ها نمایش داده می‌شوند.
- در شبکه‌های حمل‌ونقل 🚗، شهرها گره‌ها و جاده‌ها یال‌ها هستند.

2. حل مسائل مسیریابی و بهینه‌سازی 🚦
گراف‌ها ابزاری عالی برای یافتن بهترین مسیر هستند:
- در الگوریتم‌های مسیریابی 📍، مانند الگوریتم دایکسترا (Dijkstra)، کوتاه‌ترین مسیر بین دو گره در گراف محاسبه می‌شود.
- مسئله فروشنده دوره‌گرد 🤹، که به دنبال کم‌هزینه‌ترین مسیر بازدید از تمام شهرها است.

3. نمایش روابط پیچیده 🔗
گراف‌ها به‌خوبی روابط پیچیده میان داده‌ها را نشان می‌دهند. برای مثال، در تحلیل شبکه‌های اجتماعی 🌐 یا تعاملات بیولوژیکی 🧬 بین ژن‌ها و پروتئین‌ها، می‌توان تعاملات چندگانه را به وضوح مشاهده کرد.

4. کاربردهای گسترده در علوم مختلف 🌍
گراف‌ها در زمینه‌های گوناگون به کار می‌روند:
- هوش مصنوعی 🤖 و یادگیری ماشین برای مدل‌سازی و پردازش زبان طبیعی.
- زیست‌شناسی 🧬 برای بررسی تعاملات ژنتیکی.
- مهندسی نرم‌افزار 💻 برای نمایش وابستگی‌ها بین ماژول‌ها.

5. الگوریتم‌های کارآمد ⚙️
گراف‌ها به ما امکان می‌دهند تا مسائل پیچیده را با الگوریتم‌های کارآمد حل کنیم:
- الگوریتم BFS 🔍 (جستجوی سطح به سطح) و الگوریتم DFS 🔎 (جستجوی عمقی) برای پیمایش و جستجوی گراف‌ها.

6. حل مسائل پویایی شبکه‌ها 🌐
گراف‌ها می‌توانند پویایی شبکه‌ها را در طول زمان مدل‌سازی کنند:
- گراف‌های زمانی ⏳ برای نمایش تغییرات سیستم‌ها.
- الگوریتم‌های جریان بیشینه 💧 برای مدیریت بهینه جریان‌ها در شبکه‌ها مانند توزیع انرژی.

7. کاربردهای عملی و روزمره 📱
در زندگی روزمره هم گراف‌ها نقش دارند:
- مسیریابی GPS 🗺 برای یافتن بهترین مسیر بین نقاط مختلف.
- مدیریت شبکه‌های توزیع 🏗 برای اطمینان از تخصیص بهینه منابع.

نتیجه‌گیری ✔️
به طور کلی، گراف‌ها به دلیل سادگی در نمایش و حل مسائل مرتبط با روابط و اتصالات، ابزاری فوق‌العاده برای یافتن راه‌حل‌های بهینه هستند و در بسیاری از زمینه‌های علمی و کاربردی استفاده می‌شوند.

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

"دوره رایگان AI Python برای مبتدیان، برای مدت محدود توسط آندره"

https://www.deeplearning.ai/short-courses/ai-python-for-beginners/
#هوش_مصنوعی
📣👨‍💻 @AlgorithmDesign_DataStructuer

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

هنر مهندسی یعنی یه جسم ۳۵۰۰ تنی رو با سرعت ۶ هزار کیلومتر به سمت زمین برگردونی و اینجوری بگیری بغلت. زنده باد علم...

@silicon_brain | از هوش مصنوعی عقب نمانید

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

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

Are you ready for free online courses from the world’s #No1 university?

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

📑 - دوره ی تدریس سیگنال و سیستم ها
♾️ - مدرس: پروفسور آلن وی اوپنهایم
🏛 مؤسسه فناوری ماساچوست 𝐌𝐈𝐓

https://ocw.mit.edu/courses/res-6-007-signals-and-systems-spring-2011/download/


📣👨‍💻 @AlgorithmDesign_DataStructuer

پایتورچ را به صورت رایگان (و با کیفیت) یاد بگیرید!
یک دوره عالی برای یادگیری پایتورچ پیدا کردم که واقعا ارزشمند است. خواستم آن را با شما به اشتراک بگذارم.

https://howsam.org/downloads/pytorch-course/

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

اگر به دنبال یک منبع عالی برای مرور سریع الگوریتم‌ها و ساختارهای داده هستید، Algorithms and Data Structures Cheatsheet رو از دست ندید! این سایت یک راهنمای جامع و مختصر ارائه میده که بهتون کمک می‌کنه مفاهیم کلیدی رو به سرعت یاد بگیرید یا مرور کنید. حتماً بهش سر بزنید و از مطالبش بهره‌مند بشید!

https://algs4.cs.princeton.edu/cheatsheet/

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

ویژن ترنسفورمر (Vision Transformer یا به اختصار ViT) یک معماری مدل است که ترنسفورمرها، که در اصل برای پردازش زبان‌های طبیعی (NLP) طراحی شده‌اند، را برای داده‌های تصویری به کار می‌گیرد. برخلاف شبکه‌های عصبی کانولوشنی (CNNs) که سال‌ها در این زمینه غالب بوده‌اند، ویژن ترنسفورمرها نیازی به استفاده از کانولوشن‌ها برای پردازش تصاویر ندارند. به جای آن، تصاویر را به چندین بخش (پچ) تقسیم کرده، این پچ‌ها را مانند توالی‌های کلمات در نظر می‌گیرند، و سپس مدل ترنسفورمر را برای استخراج ویژگی‌ها به کار می‌گیرند.

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

Paper https://arxiv.org/abs/2010.11929
code https://github.com/google-research/vision_transformer

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

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

انواع گراف :

1. بدون جهت (Undirected): یال‌ها بدون جهت. 🎯
2. جهت‌دار (Directed): یال‌ها با جهت مشخص. ➡️
3. خلوت (Sparse): یال‌ها نسبت به گره‌ها کم. 🌿
4. متراکم (Dense): یال‌ها نسبت به گره‌ها زیاد. 🏗
5. بدون وزن (Unweighted): یال‌ها بدون وزن. ⚖️
6. وزندار (Weighted): یال‌ها وزندار. 🏋️
7. بدون دور (Acyclic): بدون دور. 🚫🔄
8. چرخه‌ای (Cyclic): دارای دور. 🔄
9. ساده (Simple): بدون حلقه یا یال موازی. ✅
10. غیر ساده (Non-simple): با حلقه یا یال موازی. 🚧
11. بدون برچسب (Unlabeled): بدون برچسب. ❌🏷
12. برچسب‌دار (Labeled): با برچسب. 🏷

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

ترانسفورمر دیفرانسیلی در مقابل ترانسفورمر معمولی

ترانسفورمر معمولی 🎯 تمایل به توجه به زمینه‌های نامربوط دارد، در حالی که ترانسفورمر دیفرانسیلی 🔍 توجه را به زمینه‌های مرتبط تقویت می‌کند و نویز را حذف می‌کند (بی‌توجهی به زمینه‌های نامربوط).

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

- مکانیزم توجه دیفرانسیلی (differential attention) نمرات توجه را به‌عنوان تفاوت بین دو نقشه توجه softmax جداگانه محاسبه می‌کند.
- این تفریق، نویز را حذف کرده و باعث ایجاد الگوهای توجه پراکنده می‌شود. 🌿

مزایای ترانسفورمر دیفرانسیلی

- ترانسفورمر دیفرانسیلی (DIFF Transformer) در مقایسه با ترانسفورمر معمولی در مقیاس‌های مختلف، چه از نظر افزایش اندازه مدل و چه از نظر تعداد داده‌های آموزشی، عملکرد بهتری دارد.
- مهم‌تر از آن، در کاربردهای عملی مانند مدل‌سازی با زمینه طولانی (long-context modeling) و بازیابی اطلاعات کلیدی (key information retrieval) مزیت‌های قابل توجهی دارد. 🧠📚

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

این ابزار برای کسانی که از PyTorch استفاده می‌کنند.

معرفی روش : VisualTorch
✅ یک ابزار اپن‌سورس در پایتون که به شما امکان می‌دهد مدل‌های PyTorch را خیلی سریع و آسان بصری‌سازی کنید.
✅ به جای بررسی دستی شبکه‌های عصبی‌تان، با این ابزار می‌توانید لایه‌ها، پارامترها و گراف‌های محاسباتی را به‌صورت تصویری مشاهده کنید. این کار به شما کمک می‌کند تا سریع‌تر دیباگ کرده و مدل‌هایتان را بهینه‌تر تنظیم کنید.

🔗 برای دانلود و استفاده، فقط کافیست به گیت‌هاب زیر مراجعه کنید 👇
https://github.com/willyfh/visualtorch

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

یک Heap یک نوع داده ساختار درختی است که ویژگی‌های زیر را دارد:

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

⚖️ ویژگی heap:
- Max-Heap: در هر گره، مقدار والد بزرگتر یا مساوی مقدار فرزندانش است. بنابراین، بزرگترین عنصر در ریشه قرار دارد.
- Min-Heap: در هر گره، مقدار والد کوچکتر یا مساوی مقدار فرزندانش است. بنابراین، کوچکترین عنصر در ریشه قرار دارد.

🚀 دسترسی سریع به ریشه: در heap، عنصر ریشه همیشه بزرگترین (در max-heap) یا کوچکترین (در min-heap) عنصر است که دسترسی به آن با زمان ثابت O(1) انجام می‌شود.

🛠 درج و حذف: عملیات درج و حذف در heap به صورت منطقی انجام می‌شود، به طوری که پس از هر عملیات، ساختار درخت و ویژگی heap حفظ می‌شود. این عملیات معمولاً در زمان O(log n) انجام می‌شوند، زیرا باید از ریشه به برگ یا بالعکس پیمایش کنیم.

💡 کاربردها:
- صف اولویت: heap اغلب برای پیاده‌سازی صف‌های اولویت استفاده می‌شود.
- الگوریتم‌های مرتب‌سازی: مثل Heap Sort که از ویژگی‌های heap برای مرتب‌سازی داده‌ها استفاده می‌کند.
- الگوریتم‌های مسیریابی: مثل الگوریتم دیکسترا برای پیدا کردن کوتاه‌ترین مسیرها.

این ویژگی‌ها heap را به یک داده ساختار کارآمد برای بسیاری از کاربردها تبدیل کرده‌اند. 🎯

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

دموکراتیزه کردن کارآمد مدل‌های زبانی بزرگ (LLMs) پزشکی برای ۵۰ زبان از طریق ترکیبی از متخصصان خانواده‌های زبانی

Github: https://github.com/freedomintelligence/apollomoe

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

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

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

✨ جزوه‌ای جامع و خلاصه از درس ساختمان داده از دانشگاه خواجه نصیرالدین طوسی، عالی برای مرور مطالب و همراه با نمونه سوالات کاربردی. 📝🔍
یک منبع مفید و ارزشمند برای آمادگی بهتر در امتحانات! 📚🚀

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

سلام دوستان عزیز👋🏻😉

امیدوارم حالتون خوب باشه. 🌟

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

پس بدون هیچ نگرانی سوالاتتون رو بپرسید و از راهنمایی‌های مفید ادمین استفاده کنید. موفق باشید! 💻📚

برای ارتباط با ادمین به آیدی زیر پیام بدید.👇🏻👇🏻

✅ @Se_mohamad

💡 توجه ترکیبی از سرها (MoH) روشی جدید برای بهبود کارایی توجه چندسر در ترنسفورمرهاست. MoH هر سر توجه را مانند یک متخصص می‌بیند و به هر توکن اجازه می‌دهد مرتبط‌ترین سرها را انتخاب کند. این روش بدون افزایش پارامترها، کارایی استنتاج را بهبود می‌بخشد. MoH به جای جمع ساده، از جمع وزنی استفاده کرده و انعطاف‌پذیری بیشتری ارائه می‌دهد.

توجه ترکیبی از سرها (MoH) در مدل‌های مختلف مانند ViT، DiT و LLMs نتایج چشمگیری داشته است. مثلاً MoH-ViT-B با فعال‌سازی 75٪ از سرهای توجه به دقت 84.9٪ در ImageNet-1K رسیده است.

همچنین مدل‌هایی مثل LLaMA3-8B با تنظیم به MoH، دقت بیشتری با سرهای کمتری دارند. MoH-LLaMA3-8B با 75٪ سرها، 2.4٪ بهتر از نسخه قبلی عمل کرده است.

https://arxiv.org/abs/2410.11842

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

پیچیدگی زمانی (Time Complexity) برای عملیات‌های مختلف روی پشته (Stack)

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