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

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

#غیردرسی

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

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

معرفی منابع رایگان کنکور

✅برای سال آينده درس مبانی کامپیوتر و برنامه‌سازی اضافه شده است. کلاس دکتر فضلی رو که این درس کامل تدریس کردند رو از دست ندین. خودم قبلا تو کلاس‌های دکتر بودم و عالیه کارشون👌 سرفصل‌شان همون سرفصل کنکوره
https://www.aparat.com/Sharif_Fundamentals_Of_Programmi/videos


✅ویدیوها درسنامه و حل تمرین ساختمان گسسته دکتر ضرابی زاده دانشگاه شریف. لینک درس

راه‌کارهایی جهت حفظ آرامش خود قبل از برگزاری کنکور:

✍️1. قبل برگزاری کنکور خودتونو نبازید.😊

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

✍️2. استرس میگیرین بگید: من میرم سرجلسه هر درسی هرچقدر زدم عالیه.

✍️3. نزارید جو کنکور شمارو تسلیم خودش کنه هنوز زوده برا تسلیم شدن (یعنی وقت هست برا تسلیم شدن ولی الان وقتش نیست).

✍️4. اونی که خیلی خوب خونده الزاماً شریفی شدنش تضمین نشده، سیاستی که شما در مواجه با کنکور اتخاذ میکنید حرف اول اخر خواهد زد، باید بدونید از سوادتون چطور و در کجا استفاده میکنین، مثلا اگر یه درس رو خوب خوندین وقتی تمام زمانتون تخصیص میدین به این، این اشتباهه محضه دیگه. توانایی‌شو دارین اما شما قراره کنکور بدین و این کار خوب نیست.

✍️5. حل نکردن سوال سرجلسه الزاماً مضر نخواهد بود😊 خیلی پیش‌آمد های خوبی میتونه داشته باشه حل نکردن برخی سوالات کنکور!!!

✍️6. تعداد سوالات زیاده یعنی شما فرصت خیلی زیادی دارین برای قبول شدن😊.

#هم‌افرایی

✅ تدریس و آموزش دروس داده‌ساختار و الگوریتم

✅✅ پارت اول ریاضیات پیش‌نیاز درس

#داده‌ساختار
#الگوریتم

✅ تدریس و آموزش نظریه زبان‌ها و نظریه محاسبات

✅✅ مبحث زبان‌ها

#نظریه‌زبان
#نظریه‌محاسبات

✅✅ سرفصل دروس داده‌ساختار و الگوریتم برای کنکور ۴۰۶

مقدمات 
ریاضی پایه
سطوح انتزاع
مراحل مختلف حل مسئله و انتزاع
داده‌مدل‌ها، داده‌گونه‌ها، داده‌ساختارها، داده‌گونه‌ی انتزاعی، شی‌ء

تحلیل الگوریتم
تحلیل زمانی الگوریتم: مرتب‌سازی درجی
رشد توابع
روش‌های تحلیل سرشکن

تقسیم و حل
مرتب‌سازی ادغامی، محاسبه‌ی تعداد نابجایی، زیردنباله‌ی متوالی، ضرب اعداد
قضیه اصلی

تحلیل الگوریتم‌های تصادفی 
محاسبه‌ی میانه‌ی تقریبی، مسئله‌ی استخدام

داده‌ساختارهای پایه 
صف و پشته
لیست پیوندی

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

مرتب‌سازی 
درخت تصمیم و کران پایین
مرتب‌سازی هرمی
مرتب‌سازی سریع (تحلیل تصادفی)
مرتب‌سازی با تعداد مقایسه‌های بهینه
مرتب‌سازی خطی: شمارشی، مبنایی، سطلی
مرتب‌سازی خارجی (اختیاری)

مرتبه‌ی آماری 
محاسبه‌ی کمینه و بیشینه
انتخاب k-امین عنصر (الگوریتم تصادفی و قطعی)

درهم‌سازی 
درهم‌سازی زنجیره‌ای
درهم‌سازی سراسری
درهم‌سازی باز
درهم‌سازی کامل

داده‌ساختارهای پیشرفته
مجموعه‌های مجزا
درخت‌های دودویی متوازن: درخت قرمز-سیاه
درخت بازه

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


#داده‌ساختار
#الگوریتم

❇️ دوستانی که روز پنج‌شنبه و جمعه کنکور دارند و کلاس‌های منو تهیه کردند حتما همین الان به بنده پیام بدهند:
@mrostami1997

✅ نظر و منابع مطالعاتی رتبه برتر کنکور کامپیوتر جناب ذوالفقاری در خصوص منبعی که خوندن.

🤖دانش‌جوی دکتری هوش مصنوعی دانشگاه شریف

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

📝 لینک پاسخ‌نامه ایشون

#داده‌ساختارالگوریتم