کنکور ارشد و دکتری کامپیوتر

🔥🔥 دوره‌های من رو با تخفیف مناسب میشه تهیه کرد، هر سوالی دارین می‌تونید به من پیام بدین:
@mrostami1997

⭐️ دقت کنید با دیدن حل تمرین‌ها و حل تست‌های من سر جلسه اکثر سوالات براتون آشنا خواهد بود...

#نظریه
#الگوریتم

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

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

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


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

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


#الگوریتم

📌سلام، از اونجایی که هر سال طراحان سوال حداقل یک سوال از طراحی الگوریتم ساختمان میدن که ممکنه حس کنید خارج از سرفصله تصمیم گرفتم یه سری نکات میگم یادتون بمونه بد نیست:

۱. الگوریتم تقریبی برای یافتن پوشش رأسی (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)
قابل محاسبه است (الگوریتم کاراتسوبا که در کلاس تدریس نشده است)

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

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

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

#الگوریتم

🔷 www.KonkorComputer.ir
🔷 @konkur_answer

🔥🔥 دوره‌های من رو با تخفیف ۷۰ درصدی میشه تهیه کرد، هر سوالی دارین می‌تونید به من پیام بدین:
@mrostami1997

⭐️ دقت کنید با دیدن حل تمرین‌ها و حل تست‌های من سر جلسه اکثر سوالات براتون آشنا خواهد بود...

#نظریه
#الگوریتم

از این به بعد با تماس مستقیم به این شماره با چت جی‌پی‌تی حرف بزنید یا پیام ارسال کنید

You can now talk to ChatGPT by calling 1-800-ChatGPT (1-800-242-8478) in the U.S. or by sending a WhatsApp message to the same number—available everywhere ChatGPT is.

https://x.com/OpenAI/status/1869462463848321264



T.me/safarname7