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

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

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

#غیردرسی

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

۱. روش ابتکاری زیر را برای مسئله‌ی 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)
قابل محاسبه است (الگوریتم کاراتسوبا)

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


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

#الگوریتم

۱۳. بلمن فورد پیچیدگی حافظه n+m رو داره. اگر حافظه گراف ورودی رو هم حساب کنیم

اگر حساب نکنیم پیچیدگی حافظه n است اون ارایه معروف...

یادتون باشه تو اسلایدها مورد اول رو ذکر شده اگر اومد اولی رو بزنید هر چند تغییر میکنه کلید بعدا!


۱۴. دایکسترا حافظه n رو لازم داره هیپ میسازه و n هستش کلا مرتبه پیچیدگی حافظه‌اش. باز هم اگر گراف ورودی رو حساب کنیم میشه مثل مورد قبلی.

۱۵. حواستون به d-heap که سرکلاس حل کردم باشه اونجا اگر درجه هر نود تو هیپ رو افزایش بدیم مرتبه ‌ها کلا تغییر میکنه مثلا مین هیپ dتایی، مرتبه حذف کمینه
dlogn
در مبنای d خواهد بود! حواستون باشه به اینا خلاصه.
«بخش سوم و پایانی»

۱۶. از روش FFT یا تبدیل فوریه سریع استفاده می‌کنیم تا ضرب دو چندجمله‌ای رو تو nlogn انجام بدیم

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

۱. مرتبه یافتن زوج‌های نامرتب (a,b) در ارایه طوری که a، حداقل bبار و b حداقل aبار در آرایه تکرار شده باشد، nlogn است.

۲. یافتن زوج‌هایی در ارایه حاوی اعداد طبیعی طوری که مجموع‌شان در آرایه هست با مرتبه ان دو امکان پذیره!

۳. میخواهیم در آرایه بررسی کنیم که تعداد تکرار هر عنصر در آرایه یکتاست یا خیر، یعنی عنصر دیگری نباشید که به اندازه او در آرایه تکرار شده باشد nlogn،

۴. پیدا کردن عددی در آرایه که حداقل k عدد از آن کوچکتر یا مساوی باشند هست با کمک مقایسه‌ای n

۵. یافتن بزرگترین زیر ارایه که تعداد یک‌هایش از تعداد ۰‌هایش بیشتر باشه تو مرتبه n
ممکنه

۶. یافتن kامین عنصر پر تکرار در آرایه، با مرتبه
n
ممکن است!!


#الگوریتم

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

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

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

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

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

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


✅@konkurcom