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

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

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

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

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

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

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

✅ پاسخ سوالات نظریه مهندسی کامپیوتر ۱۴۰۵

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

۴۷. گزینه سوم. مشابه درسنامه بود!

۴۸. گزینه اول. اولی درست ممکنه. دومی غلط فرض کنید زبان ال‌دو تهی باشه انگاه تو شرایط گفته شده گزاره صدق میکنه. سومی غلط چون فرض کنید زبان M2 تهی باشد آنگاه اشتراکش با هر چی تهی‌ است اما DFAهاشون یکی نیست!

ادیت: ۴۹. گزینه چهارم. به قضیه رایس تو کلاس برگردین همه خصوصیات نابدیهی تورینگ تصمیم ناپذیره! اینکه رشته اپسیلون رو بپذیره تصمیم ناپذیره چون این معادله با پذیرش رشته با طول صفر که تصمیم ناپذیره. پذیرش زبان منظم هم طبق رایس تصمیم ناپذیره. گزینه چهارم داخل کتاب سیپسر هست و چون عدد ثابتی داره این گزینه، میشه تمام رفتار ماشین رو بررسی کرد و تصمیم گرفت.

۵۰. گزینه دوم. خواص DCFLهاست.
موردی بود اطلاع بدین مرسی. معذرت بابت تاخیر🙏

✅ طبق این فایل، ۹ تست از ۱۲ تست داده‌ساختار و الگوریتم ارشد مهندسی کامپیوتر ۱۴۰۵ مشابه مطالب کلاس آمد.

🙏🙏 این اتفاق به پاس اعتماد شماست و من صد خودمو میزارم.



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

❇️این سرفصل دانشگاه شریف و وزارت علوم هستش. دوره بنده طبق این سرفصل هستش.

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

✅ در این فایل تعداد و شباهت سوالات داده الگوریتم کنکور مهندسی کامپیوتر ۱۴۰۵ با دوره‌های بنده رو می‌تونید مشاهده بفرمایید.

✅با افتخار و اختلاف تنها گروهی هستیم که الویت ما فروش نیست و هر ساله تطابق سوالات کنکور با مطالبی که تدریس میشه قرار داده میشه تا کیفیت را مطابق شواهد مقایسه کنید نه پیام‌های تلگرامی.

انتخاب مدرس نباید بر اساس تبلیغات باشد؛ باید بر اساس کیفیت محتوا و شواهد باشد.

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