✅با سلام و عرض ادب. بنده خودم گرایش‌ نرم‌افزار زیرگرایش الگوریتم محاسبات (لینک پایان‌نامه‌ام) دانشگاه شریف رو خوندم و به طور تخصصی در دروس ساختمان داده‌ها+طراحی الگوریتم+نظریه زبان‌ها و ماشین‌ها مطالعه‌ی مراجع برتر این دروس و کورس‌های مربوط به این دروس رو گذروندم. دوره‌هایی که توسط بنده تهیه شدن از مقدمات‌ترین مطالب شروع کردیم تا مباحث پیشرفته و پرتکرار کنکور

⭐️شریف‌ِبرفی
ویدیو رو آقا مسعود تهیه کردند.

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

#غیردرسی

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

۱. روش ابتکاری زیر را برای مسئله‌ی vertex cover در نظر بگیرید: یک درخت جستجوی اول عمق (DFS tree) از گراف بسازید و تمام برگ‌ها را از این درخت حذف کنید.

اولا رئوس باقی‌مانده حتماً یک پوشش رأسی (vertex cover) برای گراف تشکیل می‌دهند.
اندازه‌ی این پوشش پیدا شده، حداکثر دو برابر اندازه‌ی پوشش بهینه (optimal) است.
این در کلاس گفته بودم خودمم.

۲. مسئله‌ی مجموعه‌ی احاطه‌گر (Dominating Set) به این صورت تعریف می‌شود: کمترین تعداد از رئوس را پیدا کنید به طوری که هر رأس در گراف، یا خودش انتخاب شده باشد و یا مجاور یک رأس انتخاب‌شده باشد. این مسئله ان‌‌پی تمام است.

۳.
یک آرایه به طول n داریم که مقدار خانه‌ی iام آن برابر ai است. از روی این آرایه یک گراف کامل بدون جهت وزن‌دار با n رأس به نام G می‌سازیم؛ به‌طوری‌که وزن یال بین دو رأس i و j برابر ai + aj است.
مرتبه یافتن درخت پوشای کمینه (MST) این گراف O(n) است.

۴. فرض کنید یک گراف بدون‌جهت وزن‌دار G=(V,E) داده شده است. مجموعه‌ای از یال‌ها F⊆E را یک مجموعهٔ پوشش‌دوری (Cycle Cover Set) می‌نامیم، اگر به ازای هر دور (Cycle) در گراف، حداقل یکی از یال‌های آن دور در F وجود داشته باشد.

الگوریتمی با زمان اجرای چندجمله‌ای ارائه دهید که مجموعهٔ پوشش‌دوری با کمترین مجموع وزن یال‌ها را پیدا کند.

با الگوریتم کروسکال یا پریم، Maximum Spanning Tree را پیدا کنید.
پاسخ برابر است با تمام یال‌هایی که در این درخت نیستند. مرتبه ElogE است.

@konkurcom

🌟 جزوه کل جلسات درسنامه نظریه زبان‌ها و ماشین‌ها
#نظریه

🚨🚨 با این ویدیو‌ها برای کنکور پیش‌رو در دروس ساختمان داده+طراحی الگوریتم+نظریه زبان +گسسته آماده بشین!

۱. پارت اول حل سوالات آیتی ۱۴۰۴

۲. پارت دوم حل سوالات آیتی ۱۴۰۴

۳. پارت اول حل سوالات ارشد مهندسی کامپیوتر ۱۴۰۴

۴. پارت سوم سوالات ساختمان داده+طراحی الگوریتم مهندسی کامپیوتر ۱۴۰۴

۵.پارت چهارم و آخر حل سوالات ساختمان داده+طراحی الگوریتم مهندسی کامپیوتر ۱۴۰۴


✅@konkurcom

✅ در ویدیوهای بنده، روش عقب‌گرد رو برای تولید همه‌ی جایگشت‌های ممکن دو سال پیش تدریس کرده بودم.

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

❇️@konkurcom

🆘
برای سال آينده درس مبانی کامپیوتر و برنامه‌سازی اضافه شده است. کلاس دکتر فضلی رو که این درس کامل تدریس کردند رو از دست ندین. خودم قبلا تو کلاس‌های دکتر بودم و عالیه کارشون👌 سرفصل‌شان همون سرفصل کنکوره

🙏🙏 با به اشتراک‌ گذاشتن مطالب ما با دوستانتون، این کمک به ما می‌کنید که مطالب مفید رو با انگیزه مضاعف پیدا و براتون قرار بدیم.

https://www.aparat.com/Sharif_Fundamentals_Of_Programmi/videos

🚨با سلام و عرض ادب. برای مشاوره در خصوص کنکور ارشد یا دکتری ۴۰۶ زمان از دست ندین و کافیه به این آیدی پیام بدین. کمک خوبی میشه بهتون با توجه به تجربه‌ای که دارم.
@mrostami1997

📌سلام، یه سری نکات میگم یادتون بمونه بد نیست:

۱. الگوریتم تقریبی برای یافتن پوشش رأسی (vertex cover) دارای ضریب تقریب ۲ است. اینو سر کلاس گفتم بودم جلسه اخر بحث LP.

۲. تعداد n نقطه در صفحه داده شده شده با چه مرتبه‌ای می‌توان پوشش محدب (convex hull) نقاط محاسبه کرد؟ با nlogn میشه این کارو کرد و اینو سرکلاس درس دادم

۳. تطابق کامل روی گراف دو بخشی رو به کمک مسئله شبکه شار میشه در زمان چند جمله‌ای میشه حل کرد! (تو حل تمرین گفته میشه)

۴. ادغام دوتا پوشش محدب همانند مرج دو آرایه مرتب در زمان O(n) امکان‌پذیر است.

۵. تعداد n نقطه در صفحه داده شده است، با مرتبه nlogn می‌توان MST آن و درخت پوشای بیشینه را محاسبه کرد. این مسئله معروفه به MST اقلیدسی.

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

۷. یافتن جفت نقاط نزدیک بهم در صفحه با nlogn ممکنه و کمتر از این ممکن نیست

۸. یافتن قطر نقاط در صفحه با nlogn ممکنه

۹. تطابق رشته رو میشه در زمان خطی میشه انجام داد!! یعنی O(n+m) که n  همان طول رشته ورودی و m پترنی هست که میخواییم داخل رشته جستجویش کنیم. معمولا طول پترن از طول رشته کمتر است و مرتبه n خواهد بود.

۱۰. حالت کلی مسئله TSP دارای ضریب تقریب ثابت نیست!


۱۱. ضرب دو عدد n بیتی صحیح در زمان

n^(1.5)
قابل محاسبه است (الگوریتم کاراتسوبا)

۱۲. حواستون به الگوریتم‌های تصادفی و تقریبی باشه کلی در موردشون تو کلاس صحبت کردم که چطوریه داستانشون


«منتظر بخش دوم باشید»

#الگوریتم