انجمنصفحه اولجستجوی انجمن

[www]

(۱۸ اسفند ۱۳۹۱ ۱۱:۱۳ ب.ظ)mahdiii نوشته شده توسط:  سلام به همگی
من تخصصی رو بد ندادم. در ضمن بگم من هوش بودم اما نمی دونم چرا انقدر وقت کم آوردم. مخصوصا برای استعداد. من همیشه با مدیریت زمان مشکل دارم باید یه جوری حلش کنم. این وسواسیم بد دردیه.
چون سوالات ساختمان یکیه من سوالات ساختمانو اینجا می گذارم.
به نظر من سوالات ساختمان خوب بود (یعنی بد نبود) اما مثل همیشه به دقت زیادی نیاز داره اگه یکم بی دقتی کنی احتمال زدن گزینه غلط زیاده
-تعداد درختان AVL-> 6
-تعداد جابجایی عناصر در یک هرم کمینه که اول درج می کنیم و بعدش حذف که میشد ۷ تا که تو گزینه ها نبود. با یکی از بچه ها هم چک کردیم اما اگه حالات قرار دادن آخرین برگ در ریشه و سپس مرتب کردن هم مدنظر باشد میشه ۱۱ یا ۱۲/ من ۱۲ زدم دوستم همین طور.
-ارتفاع درخت قرمز سیاه ۲logn
-مرتب کردن مرتبه ها که logn^logn میشه همون n^loglogn که مسلما بزرگتر از n^3 هست و همچنین ۳ به تون logn.
n به توان ۳ هم از ۳ به تون logn بزرگتر است.
-
بقیه رو دوستان بگن. لطفا به تفکیک بگین منظورم ساختمان داده و طراحی الگوریتمو لطفا جدا بگین.

تعداد جابجایی ۵ می شد اول درخت را کامل بکشید بعد عملیات را انجام بدهید به ۵ می رسید.

[دیانا]

n به توان ۳ از ۳ به توان logn بزرگتر است؟ من گفتم شاید logn در توان مثل نمایی بشود و فکر میکردم همه گزینه ها غلط است اما کدوم زدم نمیدونم شماره گزینش یادتونه؟

[mmpf]

(۱۸ اسفند ۱۳۹۱ ۱۰:۵۵ ب.ظ)دیانا نوشته شده توسط:  هر سوالی که یادتون اومد بنویسید خودم شروع میکنم

۱- درخت قرمز-سیاه ----> ارتفاع ۲logn
۲- درخت قرمز-سیاه -----> رنگ گره ۴ قرمز ارتفاعش یادم رفت
۳- ضرب ماتریسا ۱۴۰۰۰
۴- فراخوانی تابع relax?
۵- تشخیص وجود دور همیلتونی و عدم تشخیصش؟
۶- ارتفاع گره ۴ در درخت جستجوی کمینه؟
۷-تشخیص تمام دورهای گراف در زمان چندجمله ای؟
۸-کوچکترین دنباله ای که x و y زیردنبالش باشند؟
۹- قرار دادن حجم کوچکتر در حجم بزرگتر؟
۱۰ - مرتب کردن logn به توان logn و ۳ به توان logn و n به توان ۳؟

---

خب تفاوت زیاده برای همین این روش اول a2 و a3 ضرب میکرد بعد a1 در این بعد شa4.a5 بعد اولین جواب در جواب این

۲/ من رو سیاه ارتفاع ۳ زدم
۳/؟؟؟
۴/ nm
۵/ NPC
۶/ ۱
۷/ راه حل چند جمله ای ندارد.
۸/نزدم
۹/نزدم
۱۰/ رو هم یادم که درست زدم و لی گزینه هاش یادم رفته.
۱۱/ ادغام در مجموع های مجزا؟ من nlogn زدم
۱۲/ یه دونه الگوریتم سریع هم داده بودن، که ۴ تا جمله گفته بود و تعداد گزاره های درست رو خوایته بود؟ من دو تا زدمم
۱۳/ هزینه سرشکنی برای جداول هش. من عدد ۳ رو زدم.
۱۴/ تعداد جابجایی ها در یک درخت min که به شکل آرایه بود ؟ من ۵ تا زدم.
۱۵/ یه دونه سوال فاکتور بارگیری هم بود مال زنجیر سازی بود یعنی ۲ تا گزاذه داده بودن، من زدم ۲ تاش هم درست.
۱۶/یه دونه الگوریتم هم بود که تا تعداد عدد های بزرگتر از x رو خواسته بود! من klogn زدم.
۱۷/یه سوال هم بود که من روش یادم نیست دقیق. فکر کنم اجتماع دو تا ارایه بود.( جوابش رو من (n+m) در logn زدم.
۱۸/ الگوریتم vertex cover رزو من راه حل چند جمله ندارد زدم.
۱۹/ یه عد ۱۳۹۱ بود! من ۲ به توان ۱۳۹۱ زدم.
۲۰/ یه دونه T(n-k داده بودن که ۴ تا مرتبه زمانی داده بودن. ۳ به توان n و دو به توان n و n به توان ۲
۲۱/ گراف بیشینه رو من فکر کنم اشتباه زدم مثل بقیه !! NPC
۲۲/ اگر عدد c را به یال ها اضافه کنیم و... من زدم یک گزینه درست بود. اونم مربوط به ضرب در عدد c.
۲۳/ تعداد درخت های avl رو ۶ تا زدم.
۲۴/یه دونه الگوریتم کاهش داده بودن که دو تا گزاره داشت. اگر الگوریتم b در زمان چند جمله ای حل شود و a یک NPC باشد انگاه ...
داده بود از ۲ تا گزاره کدام درست است.
یه کم فکر کنم بقیه هم شاید یادم اومد!
سیستم عامل هم تا کلید ها نیاد نمی شه گفت چون خیلی ...!!!

[mahdiii]

سوالای دیگه از ساختمان داده
(m+n)logn برای پیدا کردن عناصر غیر مشترک
nlogn برای ادغام n مجموعه مجزا به صورت لیست

[دیانا]

وای خدا احساس میکنم همه رو غلط زدم خداحافظ

---

دایجسترا هم بگید خلاص ! تو دور میفتاد؟

[mmpf]

نتونستم خودم رو نگه دارم. سیستم عامل :
۱/ call by value تو rpc هست و رفرنس رو از طریق copy انجام می دهیم.
۲/ سوالی که گفته بود پردازه ... برای mutual exclusion همه گزینه درست بودن. تقریبا مطمئنم
۳/ در مورد انتقال پردازه : من گزینه مربوط به انتقال فضای ادرس و داده در حال اجرای پردازه در کلاینت رو زدم. یعنی نمیشه.
۴/ الگوریتم لامپورت از ساعت بردار استفاده نمی کنه. تو یکی از گزینه ها گفته بود که کدام گزینه درست نیست.
۵/ یکی از سوالات هم در مورد گراف بود. که من زدم گراف جهت دار است که می تواند دور هم داشته باشد.
۶/ در مورد self stabilization : که گفته بود کدام گزینه نادرست است. من زدم مقدار دهی اولیه رو نمی خواد ( یعنی نادرست)
بقیه اش رو دوستان یاری کنند. من یادم نیست.

[دیانا]

و اون سواله که گفته بود یالهای منفی رو مثبت میکنیم ایا طول کوتاهترین مسیر و خود مسیر یکیه در هر دو گراف؟
که به نظرم قسمت دوم حلقه به جای + باید - میبود وگرنه یالها بازم منفی میشدکه!

---

من سیستم عامل اصلا نخوندم و جاب هم ندادم

شما کدوم دانشگاه بودید؟

---

درخت بیشینه که با کراسکال پیدا میشه

[mmpf]

(۱۸ اسفند ۱۳۹۱ ۱۱:۳۲ ب.ظ)دیانا نوشته شده توسط:  وای خدا احساس میکنم همه رو غلط زدم خداحافظ

---

دایجسترا هم بگید خلاص ! تو دور میفتاد؟

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

[دیانا]

چرا اینو قدسی گفته میتونه پیدا کنه

---

اون تابع relax ?

[mmpf]

(۱۸ اسفند ۱۳۹۱ ۱۱:۳۷ ب.ظ)دیانا نوشته شده توسط:  و اون سواله که گفته بود یالهای منفی رو مثبت میکنیم ایا طول کوتاهترین مسیر و خود مسیر یکیه در هر دو گراف؟
که به نظرم قسمت دوم حلقه به جای + باید - میبود وگرنه یالها بازم منفی میشدکه!

---

من سیستم عامل اصلا نخوندم و جاب هم ندادم

شما کدوم دانشگاه بودید؟

---

درخت بیشینه که با کراسکال پیدا میشه

کراسکال مگه مال کوتاهترین نیست/ من زدم NPC به این خاطر که گفتم کوتاهترین مسیر از یک راس به بقیه راس ها چند جمله ای اما طولانی ترین مسیر NPC. گفتم اینم شاید مثل اون باشه. عجب استدلالی.
من دانشگاه شاهد هستم.
اون مسیر برابر یا نه در ۲ تا گراف ؟ من نزدم ولی فکر می کنم برابر بود و در واقع ۲ تا جمله هم درست بود. شبیه الگوریتم johnson بود.

---

(۱۸ اسفند ۱۳۹۱ ۱۱:۴۲ ب.ظ)دیانا نوشته شده توسط:  چرا اینو قدسی گفته میتونه پیدا کنه

---

اون تابع relax ?

چی رو دکتر قدسی گفته می تونه پیدا کنه ؟
اون relax هم همون الگوریتم بلمن فورد که می شد ve یا همون nm

[دیانا]

کراسکال به جای مینیمم ها ماکزیمم انتخاب میکنه میشه درخت بیشینه اما طولانی ترین مسیر نمیشه پیدا کرد به این راحتی

درخت بیشینه بود یا طولانی ترین مسیر؟

---

دایجسترا اگه مثلا از مبدا یه یال منفی جلوش باشه

[mahdiii]

(۱۸ اسفند ۱۳۹۱ ۱۱:۲۱ ب.ظ)دیانا نوشته شده توسط:  n به توان ۳ از ۳ به توان logn بزرگتر است؟ من گفتم شاید logn در توان مثل نمایی بشود و فکر میکردم همه گزینه ها غلط است اما کدوم زدم نمیدونم شماره گزینش یادتونه؟

کافیه از دو طرف log بگیری به نتیجه من میرسی. حتی می تونی ۳ به توان logn رو ۴به توان logn بگیری بعد حلش کنی که در این صورت میشه
n^2 که بازم از n^3 کمتره. یعنی ۳ به توان logn کمتر از n^2 و بیشتر از n میشه.
۴ به توان logn برابر با ۲ به توان logn^2 میشه که میشه n^2

[mmpf]

(۱۸ اسفند ۱۳۹۱ ۱۱:۴۶ ب.ظ)دیانا نوشته شده توسط:  کراسکال به جای مینیمم ها ماکزیمم انتخاب میکنه میشه درخت بیشینه اما طولانی ترین مسیر نمیشه پیدا کرد به این راحتی

درخت بیشینه بود یا طولانی ترین مسیر؟

درخت بیشینه

شما درست می فرمائید. اول درست زده بودم گفتم این سوال راحت رو نمیدن بذار یه کم خلاقیت نشون بدم. پاک کردم اینو زدم. همه اش که اشتباه شد
من امیدم به زبان. حالا تخمین نمی زنم چون بگم مثلا ۷۰ می شه ۱۵/ فکر کنم استعداد های درخشان راحت تر از کنکور. استادم به من می گفت بیا ایران داک برت دارم، منم تو دل خودم می گفتم برو بابا. الان برم پیشش حالش رو بپرسم!!!
البته نتاسفانه من تو آزمون یه چشم دردی گرفتم که پدرم رو در اورده بود و رو کارائیم تاثیر داشت.

[دیانا]

نمیدونم چی به خودم بگم من اون ۳۰ تا پیچیدگی تو کرمن رو خونده بودم و همین استدلالا داشتم درست جواب میدادم سر جلسه خنگ بازی!

[mahdiii]

(۱۸ اسفند ۱۳۹۱ ۱۱:۲۰ ب.ظ)www نوشته شده توسط:  

(18 اسفند ۱۳۹۱ ۱۱:۱۳ ب.ظ)mahdiii نوشته شده توسط:  سلام به همگی
من تخصصی رو بد ندادم. در ضمن بگم من هوش بودم اما نمی دونم چرا انقدر وقت کم آوردم. مخصوصا برای استعداد. من همیشه با مدیریت زمان مشکل دارم باید یه جوری حلش کنم. این وسواسیم بد دردیه.
چون سوالات ساختمان یکیه من سوالات ساختمانو اینجا می گذارم.
به نظر من سوالات ساختمان خوب بود (یعنی بد نبود) اما مثل همیشه به دقت زیادی نیاز داره اگه یکم بی دقتی کنی احتمال زدن گزینه غلط زیاده
-تعداد درختان AVL-> 6
-تعداد جابجایی عناصر در یک هرم کمینه که اول درج می کنیم و بعدش حذف که میشد ۷ تا که تو گزینه ها نبود. با یکی از بچه ها هم چک کردیم اما اگه حالات قرار دادن آخرین برگ در ریشه و سپس مرتب کردن هم مدنظر باشد میشه ۱۱ یا ۱۲/ من ۱۲ زدم دوستم همین طور.
-ارتفاع درخت قرمز سیاه ۲logn
-مرتب کردن مرتبه ها که logn^logn میشه همون n^loglogn که مسلما بزرگتر از n^3 هست و همچنین ۳ به تون logn.
n به توان ۳ هم از ۳ به تون logn بزرگتر است.
-
بقیه رو دوستان بگن. لطفا به تفکیک بگین منظورم ساختمان داده و طراحی الگوریتمو لطفا جدا بگین.

تعداد جابجایی ۵ می شد اول درخت را کامل بکشید بعد عملیات را انجام بدهید به ۵ می رسید.

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