سلام
به نظر من که امتحان گراف بود نه ساختمان داده ها
سول 1 قطعا دایکسترا و بلمن فورد نمی شد . بین 3 و4 شانسی زدم
دوران 5 تا
قد هم n/2 چون هر کس جدید که وارد میشه یا از قبلی ها بلند تره یا کوتاهتره 1/2 ، اگه به ترتیب کوتاه به بلند قد وارد شن میشه n تا و از بزگ به کوچک میشه 1 ذخیره کردن و میانگین میشه n/2 و ( ولی خیلی ساده هست نه ؟ مشکوک میزنه !!!)
همبند قوی گزینه شاید تغییر نکنه یعنی سک گزینه زدم ، واسه بقیه مثال نقض زدم
من متاسفانه رشد n رادیکالn و n به توان لگاریتم3 رو یکی گرفتم و جوابو n رادیکالn *logn زدم ، یه حسی بهم گفت تو تعمیم قضیه اصلی می تونم اینکارو کنم و یه حس بود دیگه !
درج و حذف در هیپ هم قطعا logn میشه و چون با هر ترتیب n که به خوای درج یا حذف کنی باید درخت رو هیپی فای کن ، حتی اگه جای درج رو بدنی ( مساله ساختن هپیپ نیست که از On باشه ، هیپیفای کردن بود ، البته به نظر من )
اون سال 3n و x<Y طبق کتاب قدسی تو O(N) میشه x,y رو بدست آورد ( نمی خواد آرایه رو مرتب کنی ؛ از selection اسفتاده می کنیم)
شعاع r>d زدم ، چون واسه r>d/2 مثال نقض پیدا کردم ؛ مطمئن نیستم
کد هافمن 25 زدم چون حدکثر n-1 بالنذی طول درخت هافمن هستش
1393 رنگ رو زدم 11 ، گزینه 1 (کتاب قدسی با در خت 2 به توان 11 می تونه یازه ها رو در بیاری )
(15 اسفند 1393 07:50 ب.ظ)morelo نوشته شده توسط: [ -> ]۲ به توان لگاریتم ۳ در مبنای ۲ که میشه ۳/ T(n) = 3T(n/2)+n√n
نمیدونم چی بگم واقعا
اگه صورت سوال اینی که نوشتین باشه دقیقا جوابتون درسته... حالا اینکه من سر جلسه چطوری این سوالو خوندم که نتیجه این شد توان n کم میشه خدا داند
ساده ترین سوالاتو گند زدم
(15 اسفند 1393 08:29 ب.ظ)mhghna نوشته شده توسط: [ -> ]قد هم n/2 چون هر کس جدید که وارد میشه یا از قبلی ها بلند تره یا کوتاهتره ۱/۲ ، اگه به ترتیب کوتاه به بلند قد وارد شن میشه n تا و از بزگ به کوچک میشه ۱ ذخیره کردن و میانگین میشه n/2 و ( ولی خیلی ساده هست نه ؟ مشکوک میزنه !!!)
دوست من میانگین اینجوری حساب نمیشه... اون دقیقا میشه Ln n نمونش سال 92 با یه ادبیات دیگه اومده بود اگه مجانبی بود log میشد ولی چون دقیق خواسته بود میشد ln
سلام امیدوارم خوب امتحان داده باشین...
بله سوال n رادیکال اون رابطه بازگشتی من زدم n به توان log چون مقدار توانش بزرگتره حالا یادم رفته بود log3 چند میشه یه ساعت داشتم ححساب میکردم خخ. در هر صورت مقدارش بیشتر از ۱/۵ میشه ..دیشبشم نمیدونم چی شده بود حتی نیم ساعتم نخوابیدم خوابم نبرد..
( هنگ بودم برای سوالای ساده. لگ زمانی اضافه میشه که دو جمله از نظر مرتبه چندجمله ای مثل هم باشن..
اون هافمن میشه ۲۵
اونیکه گفته بود درخت avl تعریقشو عوض کرده بود و گفته بود اختلاف حداکثر دو باشه.. با مثال و فرمول میشد حل کرد . تو جوابش tn-3+tn-1 داشت
دوران زدم ۵ تا. برای همبند قوی زدم یکی یعنی میتونه تغییر نکنه.. کلا وقتی یه یال اضافه میشه میتونه تغییر نکنه و یا به تعدادی همبند قویو اضافه کنه. کم نمیکنه چون مسیری که قبلا در دور وجود داشته هنوزم وجود داره و حداکثر هم یکی اضافه نمیکنه میتونه بیشتر اضافه کنه.
منم پارتیشن مرتب سازی ادغامو زدم nlogn , اون x<y که گفته بود میخواهیم پیدا کنیم که 1/3 اعداد کمتر از x 1/3 بین و 1/3 بزرگتر باشن با on میشه همون الگوریتم seelection هست که میاد k/3 , 2k/3 کوچکترین عددو پیدا میکنه.
(15 اسفند 1393 09:22 ب.ظ)cavalier نوشته شده توسط: [ -> ]سلام امیدوارم خوب امتحان داده باشین...
بله سوال n رادیکال اون رابطه بازگشتی من زدم n به توان log چون مقدار توانش بزرگتره حالا یادم رفته بود log3 چند میشه یه ساعت داشتم ححساب میکردم خخ. در هر صورت مقدارش بیشتر از ۱/۵ میشه ..دیشبشم نمیدونم چی شده بود حتی نیم ساعتم نخوابیدم خوابم نبرد.. ( هنگ بودم برای سوالای ساده. لگ زمانی اضافه میشه که دو جمله از نظر مرتبه چندجمله ای مثل هم باشن..
اون هافمن میشه ۲۵
اونیکه گفته بود درخت avl تعریقشو عوض کرده بود و گفته بود اختلاف حداکثر دو باشه.. با مثال و فرمول میشد حل کرد . تو جوابش tn-3+tn-1 داشت
دوران زدم ۵ تا. برای همبند قوی زدم یکی یعنی میتونه تغییر نکنه.. کلا وقتی یه یال اضافه میشه میتونه تغییر نکنه و یا به تعدادی همبند قویو اضافه کنه. کم نمیکنه چون مسیری که قبلا در دور وجود داشته هنوزم وجود داره و حداکثر هم یکی اضافه نمیکنه میتونه بیشتر اضافه کنه.
منم پارتیشن مرتب سازی ادغامو زدم nlogn , اون x<y که گفته بود میخواهیم پیدا کنیم که ۱/۳ اعداد کمتر از x 1/3 بین و ۱/۳ بزرگتر باشن با on میشه همون الگوریتم seelection هست که میاد k/3 , 2k/3 کوچکترین عددو پیدا میکنه.
درخت AVL رو فکر کنم اشتباه میگین چون اگه رسم کنید اعداد زیر به دست میاد
AVL (0) = 1, AVL (1) = 2,AVL (2) = 3,AVL (3) =5, AVL (4) = 8, AVL (5) = 13 که همون AVL (h) <= AVL (h-1) +AVL (h-2) هستش
avl (5) میشه 12
با این چیزیکه نوشتین که راه خودتون اشتباه!!!
8+3!!! 13!!!
کساییکه دفترچه دارن لطفا بگذارن
(15 اسفند 1393 10:01 ب.ظ)cavalier نوشته شده توسط: [ -> ]avl (5) میشه ۱۲
با این چیزیکه نوشتین که راه خودتون اشتباه!!!
۸+۳!!! ۱۳!!!
کساییکه دفترچه دارن لطفا بگذارن
نه واسه 3 رو ننوشته بودم/ درست کردم
رسم کنید متوجه میشید
آها بچه ها اونی که ماتریس مجاورتی بود میشد n به توان 2
شما لطفا رسم کنین شکلشو بگذارین که میگین برای 5 میشه 13 و برای ششم بکشین ..
صورت مساله رو یه بار دیگه بخونین. گفته حداکثر اختلاف دو نه یک.
پس هر درخت با ارتفاع n با چسبوندن درخت با ارتفاع n-1 گره و درخت با ارتفاع n-3 و اضافه کردن ریشه به دست میاد.
اون چیزیکه شما میگی برای وقتیه که اختلاف حدکتر یک باشه که اون وقت میشد چسبوندن درخت با ارتفاع n-1 ,n-2 , اضافه کردن ریشه.
من که برای 5 تونستم با 12 تا نشون بدم!!
مسعود این شکلو ببین حداکثر یکی نیست. میتونه بیشتر اضافه بشه به اجزای همبند.
من زدم یکی ...میتونه تغییر نکنه. این شکلو ببین. اولی میبینی هیچی جز همبند قوی نداره اما با اضافه شدن یک یال سه تا همبند قوی اضافه شده دومیم نشون میده لزومی نداره حتما تعداد اجزا همبند تغییر کنه
میشه جواب آخر رو بگین؟
اگر هم 12 بشه بازم 13 از 12 بزرگتر یا مساویه
جوابها هم مساوی نداشت یعنی کوچکتر مساوی بود
اگز AVL طبیعی بود که AVL (h) = AVL (h-1) +AVL (h-2) +1 میشد که دو طرف رابطه مساوی هستن
من استدلالم خیلی واضح و شفاف بود لازم به مثال زدن نیست وقتی اثبات میشه!!!
که کافیه دو زیر درخت با ارتفاع n-1 , n-3 رو فرزند چپ و راست ریشه کنین. منظورتونو متوجه نمیشم وقتی مساوی هست خوب کوچکتر مساوی هم باشه مگه ایراد داره بگیم 2<=2 !!!
این جواب دقیقتره..همیشه بهترین گزینه مدنظره.
مثل سوالاییکه میگه a<2 , a<0.5 تو سال پیش که معلومه اگه a<0.5 باشه a<2 هم هست اما بهترین گزینه مدنظره و یا در مورد مرتبه های زمانی ...
(15 اسفند 1393 11:06 ب.ظ)cavalier نوشته شده توسط: [ -> ]مسعود این شکلو ببین حداکثر یکی نیست. میتونه بیشتر اضافه بشه به اجزای همبند.
من زدم یکی ...میتونه تغییر نکنه. این شکلو ببین. اولی میبینی هیچی جز همبند قوی نداره اما با اضافه شدن یک یال سه تا همبند قوی اضافه شده دومیم نشون میده لزومی نداره حتما تعداد اجزا همبند تغییر کنه
دوست عزیز من که نگفتم زیاد میشه، گفتم کم میشه
من سر جلسه 2 مثال زدم برا خودم:
اگر گراف فقط 1جزء همیند داشته باشه افزودن یال بی تاثیره
اگر گراف چند تا جزء باشه که فقط یکطرفه بهم وصل هستن ممکنه با افزودن 1 یال
بیش از یک مولفه همبند کم بشه.
(16 اسفند 1393 12:10 ق.ظ)cavalier نوشته شده توسط: [ -> ]استدلالتون اشتباس
اگر گراف فقط ۱جزء همیند داشته باشه افزودن یال بی تاثیره...
این مثال اشتباهیه و ربطی به این موضوع نداره یعنی میشه گرافهایی مثال زد که اگه جز همبندم ندارن و ... باز افزودن یال تاثیری نداشته باشه.
ولی کلا درسته که بگیم میتونه افزودن یال بی تاثیر باشه اما نه در این مثال و گفتن فقط !!!
بحثم در مورد بخش دوم هست شما میگین افزودن یال میتونه باعث بشه که تعداد اجزای قویا همبند کم بشه!!
چجوری امکان داره مگه با افزودن یال دورها از بین میرن؟؟ دورها هنوزم مثل قبل وجود دارن بین گره ها و بنابراین با افزودن یه یال اجزای همبند قوی کم نمیشن!
شاید منظورتون همبند عادی هست. اینجا فکر کنم گفته بود همبند قوی و نه همبند !!
استدلالم درسته، شما 1 مثال نقض بیاری تمومه.
تو مثالی که خودتون گذاشتید تمام راس ها خودشون یک جزء همیند قوی هستن چون اصلا دور نداریم و با افزودن اون یال قرمز بجای فکر کنم 5 گزاف همیند، 1 گراف همیند خواهیم داشت ( اگه اشتباه میگم بگید)
با سلام دوستان تعدادی تاپیک ایجاد شد که اگه امکانش هست برای بررسی بیشتر سوالات از اونها استفاده کنید:
درد و دل کردن:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
بررسی سوالات تخصصی گرایش علوم کامپیوتر:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
بررسی سوالات تخصصی گرایش IT:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
بررسی سوالات تخصصی گرایش نرم افزار:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
بررسی سوالات تخصصی گرایش هوش:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
بررسی سوالات تخصصی گرایش معماری:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
بررسی سوالات زبان عمومی:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
بررسی سوالات استعداد تحصیلی:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
لطفا از ایجاد تاپیک های اضافه خود داری کنید، با سپاس فراوان.
حالا بریم سراغ سوالات:
(15 اسفند 1393 05:52 ب.ظ)Masoud05 نوشته شده توسط: [ -> ]ساخت هیپ با n عنصر از مرتبه n هست. پس بطور سرشکن هزینه درج ۱ میشه!
تحلیل بنده به این صورت است که: اگه تمامی n عنصر رو یه باره بخواییم هیپ کنیم حرف شما درسته ولی ممکنه که وسطای کار یک delete داشته باشیم. بنابراین باید عناصر رو دونه به دونه در heap بریزیم که عملا از مرتبه ی log خواهد بود. همچنین برای حذف هم ممکنه که n-1 درج و تنها یک حذف داشته باشیم که اون حذف هم از مرتبه ی log خواهد بود.
(15 اسفند 1393 07:02 ب.ظ)morelo نوشته شده توسط: [ -> ]یک سوال هم بود که 3n و یافتن x<y که n تا کوچکتر و .... اگه اشتباه نکنم امگای nlogn میشد چون باید مرتب میشد
تحلیل بنده اینه که به راحتی میشه یه بار x و یه بار y را به عنوان pivot انتخاب کرد و در زمان n این تقسیم رو انجام داد ولی منظورشو از مرتبه ی میانگین n و مرتبه ی n نفهمیدم که چیست.
کدوم اولی یا دومی؟
فکر کنم شما تعریف همبند قویو رو فراموش کردین. برای اینکه ببینی یه گراف چند جز همبند قوی داره باید نعداد دورها رو بشمرین.
یعنی با انتخاب زیرمجموعه ای از راسها بتونیم از هر راس به راس دیگه بریم یعنی مسیر وجود داسته باشه
برای سوال یک هیچ دوری نداریم پس تعداد اجزای همبند میشه صفر
یعنی هیچ زیرمجموعه ای از راسها رو نمیشه انتخاب کرد که بشه از هر راس به راس دیگه بریم اما با اضافه کردن اون یال قرمز میبینین که تعداد دورها میشه سه تا پس سه جز همبند داریم. بنابراین با اضافه شدن یال تعداد اجزا بیشتر شد
دومیم که کلا نشون میده تعداد اجزای همبند میتونه با اضافه شدن یال تغییری نکنه در اینجا قبل و بعد از اضافه کردن یال تعداد اجزا صفر هست ..
منم نفهمیدم اون منظورش چیه از میانگین و O من زدم دوتا گزینه صحیحه
)
ولی سنجشم خوددرگیری داره. هنوز یاد نگرفته دقیق بگه نه مبهم
شاید منظورش در حالت میانگین و بدترین بود که هر دو به نظر ON هست
کی اون سواله NP HARD زد!!
تطابق بشینه منظورشو دقیق نفهمیدم. اگه اینو میفهمیدم منظورش چیه سوالرو جواب داده بودم
تعریف اجزای همبند قوی
اگر به ازای هر دو رأس دلخواه u و v، مسیری جهت‌دار از u به v یا از v به u، وجود داشته باشد.این گراف را قویاً همبند می‌نامیم، اگر به ازای هر دو رأس دلخواه u و v، مسیری جهت‌دار هم از u به v و هم از v به u داشته باشیم. مؤلفه‌های قوی، زیرگراف‌های قویاً همبند ماکسیمال هستند.
اون تعداد min cut در درخت میشه یک یعنی با برداشتن یک یال میشه درخت رو ناهمبند کرد درسته؟
و تعداد انتخاب اون میشه n-1 یال . یعنی یکی از اون n-1 یال رو برداریم .