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

[ahonari]

سلام سوال np قطعا گزینه ۴ صحیح است
سوال pre , pos هم اگر رسم کنیم گزیمه یک جوابه

---

(۰۷ اسفند ۱۳۹۵ ۰۷:۱۶ ب.ظ)computerman نوشته شده توسط:  سلام دوستان
دوستان جواب سوال هایی هم که زدید بگید
مثلا اون سوال NP-complete و یا اون سوالات پیچیدگی زمانی
و یا سوال اول تحخصصی ها و ...

np سخت قطعا جوابه اگر کامل باشه کاهش درجه ممکنه کامل نباشه

[computerman]

(۰۸ اسفند ۱۳۹۵ ۰۸:۲۲ ب.ظ)www نوشته شده توسط:  با سلام
در مورد سوال ۲ بهترین جواب ممکن میتونه رادیکال n باشه. الگوریتمش هم به این صورت است که بر روی رادیکال n عنصر اول الگوریتم پارتیشن برای عنصر k بزن آن عنصر پیدا می شود. و جواب ان برابر رادیکال n است.

عجب
خب همون رادیکال n عنصر اول رو از کجا بیاریم که روش پارتیشن بزنیم؟؟؟ مگه هیپ مرتب شدس که پیداشون کنیم!!!

---

(۰۸ اسفند ۱۳۹۵ ۰۷:۰۰ ب.ظ)ahonari نوشته شده توسط:  سلام سوال np قطعا گزینه ۴ صحیح است
سوال pre , pos هم اگر رسم کنیم گزیمه یک جوابه

---

(۰۷ اسفند ۱۳۹۵ ۰۷:۱۶ ب.ظ)computerman نوشته شده توسط:  سلام دوستان
دوستان جواب سوال هایی هم که زدید بگید
مثلا اون سوال NP-complete و یا اون سوالات پیچیدگی زمانی
و یا سوال اول تحخصصی ها و ...

np سخت قطعا جوابه اگر کامل باشه کاهش درجه ممکنه کامل نباشه

من زدن گزینه ۱
که میشد ۳ دفترچه خودم

[alireza01]

سوال ۴ میشه گزینه ۴ فک میکنم .

[گلاره]

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

[www]

(۰۸ اسفند ۱۳۹۵ ۰۸:۲۷ ب.ظ)computerman نوشته شده توسط:  [quote='www' pid='432078' dateline='1488124338']
با سلام
در مورد سوال ۲ بهترین جواب ممکن میتونه رادیکال n باشه. الگوریتمش هم به این صورت است که بر روی رادیکال n عنصر اول الگوریتم پارتیشن برای عنصر k بزن آن عنصر پیدا می شود. و جواب ان برابر رادیکال n است.

عجب
خب همون رادیکال n عنصر اول رو از کجا بیاریم که روش پارتیشن بزنیم؟؟؟ مگه هیپ مرتب شدس که پیداشون کنیم!!!
برای اینکار شما نیاز دارید عناصر تا سطح رادیکال ان+۱ عنصر را برداشته و بر روی آنها الگوریتم پارتیشن برای عنصر k انجام دهید.
ارتفاع هیپ logn است و در سطح logn تعداد عناصر n/2 می باشد. پس تعداد عنصر در ارتفاع لگاریتم رادیکال ان برابر رادیکال ان تقسیم بر ۲ است. پس جمع عناصر ۱+۲+۴+۸+...+ رادیکال ان برابر مضربی از رادیکال ان است. الگوریتم پارتیشن هم برابر رادیکال ان می شود. با این حساب زمان این الگوریتم رادیکال ان می شود.

---

(۰۸ اسفند ۱۳۹۵ ۱۱:۰۲ ب.ظ)گلاره نوشته شده توسط:  سلام
سوال هشت مگه هر سه تای اول صحیح نیست؟ مثال نقضی میتونین بیارین که ثابت کنید گزاره دوم و سوم صحیح نیست؟

فرض کنید چهار راس a,b,c,d دارید هزینه a به b برابر ۴ و a به C برابر ۱ و c به d برابر ۱ و d به b برابر ۱ است کوتاهترین مسیرa به b برابر ۳ با راسهای acdb می باشد اگر به وزن هریال ۳ واحد اضافه کنید کوتاهترین مسیر عوض می شود. رد گزینه ۱
فرض کنید چهار راس a,b,c,d دارید هزینه a به b برابر ۲ و a به C برابر ۱ و c به d برابر ۱ و d به b برابر ۱ است کوتاهترین مسیرa به b برابر ۲ با راسهای ab می باشد اگر از وزن هریال ۳ واحد کم کنید کوتاهترین مسیر عوض می شود. رد گزینه ۳
برای ۳و۴ چون احتمال ایجاد دور منفی است کوتاهترین مسیر عوض می شود.
گزینه ۲ صحیح است. این هم اثباتش:
فرض کنید چهار راس a,b,c,d دارید هزینه a به b برابر w و a به C برابر x و c به d برابر y و d به b برابر z است فرض کنید کوتاهترین مسیرa به b برابر ۳ با راسهای acdb می باشد پس x+y+z<w اگر به هر یال عدد p ضرب شود داریم:
p(x+y+z)<wp و از طرفین p را حذف کنید جواب حاصل می شود.
اگر p منفی باشد جهت عوض می شود رد گزینه۴

[damash]

(۰۷ اسفند ۱۳۹۵ ۰۸:۴۱ ب.ظ)ADELZX نوشته شده توسط:  برای سوال دوم نیز این پیدا کردن k امین عنصر در یک درخت هیپ از مرتب klogk می باشد
جزئیات یک الگوریتم پیشنهادی برای آن در صفحه زیر موجود است

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

منم همین گزینه رو زدم.

---

(۰۷ اسفند ۱۳۹۵ ۱۰:۲۱ ب.ظ)robotic1981 نوشته شده توسط:  ۵ رو شک داشتم نزدم
۳ و ۴ رو نزدین؟

سوال ۳ رو زدم logn و سوال ۴ هم زدم (n2)

---

(۰۸ اسفند ۱۳۹۵ ۰۶:۴۰ ب.ظ)tabestan نوشته شده توسط:  

(08 اسفند ۱۳۹۵ ۰۶:۰۵ ب.ظ)robotic1981 نوشته شده توسط:  

(08 اسفند ۱۳۹۵ ۰۵:۳۹ ب.ظ)mahditorki نوشته شده توسط:  در مورد اینکه چطور میشه فهمید گره تک فرزند تداره علاوه بر مطلب قبل یاداوری کنم که :
N0=N2+1
پیدا کردن برگها هم گفته شد.

من مدرسان شریف و کتاب دکتر قدسی رو خوندم تو هردوش نوشته بود با pre و post نمیشه به درخت واحد رسید
من با اطمینان کامل این تست رو زدم

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

به نظر من هم جواب سوال ۱۴ گزینه۱ میشه. برای اطمینان میتونیم با درنظرگرفتن پیمایش میان ترتیب گزینه۱، و دو پیمایش که توی سوال داده شده، درخت رو ترسیم کنیم. به شکل پیوستی نگاه کنید ببینید من درست میگم یا نه.روی این شکل هر سه تا پیمایش رو امتحان کنید

[www]

(۰۹ اسفند ۱۳۹۵ ۱۲:۲۲ ق.ظ)damash نوشته شده توسط:  

(07 اسفند ۱۳۹۵ ۰۸:۴۱ ب.ظ)ADELZX نوشته شده توسط:  برای سوال دوم نیز این پیدا کردن k امین عنصر در یک درخت هیپ از مرتب klogk می باشد
جزئیات یک الگوریتم پیشنهادی برای آن در صفحه زیر موجود است

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

منم همین گزینه رو زدم.

---

(۰۷ اسفند ۱۳۹۵ ۱۰:۲۱ ب.ظ)robotic1981 نوشته شده توسط:  ۵ رو شک داشتم نزدم
۳ و ۴ رو نزدین؟

سوال ۳ رو زدم logn و سوال ۴ هم زدم (n2)

جواب سوال ۳ هم به احتمال زیاد n میباشد. علاوه بر درخت مورب درختای دیگری هم وجود دارد که زمان آن n شود. مثلا فرض کنید عنصر x ریشه باشد و درخت فقط فرزند راست دارد اما فرزندان آن به صورت زیر هستند. یک فرزند راست و بقیه فرزند چپ ان فرزند راست باشند. در این صورت n منهای ۲ عنصر فرزند چپ فرزند راست اند.
در مورد سوال ۵ گزینه ۴ درست است.
در مورد سوال ۴ هم میتونم بگم الگوریتمی با زمان کمتر ازn2 میشه این کارو انجام داد.

[ADELZX]

(۰۸ اسفند ۱۳۹۵ ۱۱:۰۵ ب.ظ)www نوشته شده توسط:  ارتفاع هیپ logn است و در سطح logn تعداد عناصر n/2 می باشد. پس تعداد عنصر در ارتفاع لگاریتم رادیکال ان برابر رادیکال ان تقسیم بر ۲ است. پس جمع عناصر ۱+۲+۴+۸+...+ رادیکال ان برابر مضربی از رادیکال ان است. الگوریتم پارتیشن هم برابر رادیکال ان می شود. با این حساب زمان این الگوریتم رادیکال ان می شود.

این تحلیل شما خیلی دقیق نیست و ابهام دارد

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

نتیجه اینکه این رهیافت شما با الگوریتمی کمتر از پیچیدگی n قابل پیاده سازی نیست.

[damash]

به نظرم سوال۹ جوابش گزینه۲ یعنی n میشه. چون گراف کامل هستش و برای رفتن به تمام رئوس بعدی، نیازی به بازگشت به راس قبلی نیست و از هر راس میشه به تمام رئوس رسید.
سوال ۱۲ هم که با پریم و کراسکال قابل حله که جوابش یک میلیون میشه.
سوال ۱۳ رو با شک زدم گزینه۱ یعنی nlogn، به نظر شما چه جوابی درسته و چرا؟!!
سوال ۱۶ که به نظرم درجی بهترین الگوریتم برای آرایه از قبل مرتب شده هستش. چون حتی یک تعویض هم نداره.
سوال ۱۷ رو گزینه۴ زدم.
لطفا نظرتون رو در مورد این سوالها بگید که ایشالا بریم سوالات بعدی

[www]

(۰۹ اسفند ۱۳۹۵ ۱۲:۵۰ ق.ظ)ADELZX نوشته شده توسط:  

(08 اسفند ۱۳۹۵ ۱۱:۰۵ ب.ظ)www نوشته شده توسط:  ارتفاع هیپ logn است و در سطح logn تعداد عناصر n/2 می باشد. پس تعداد عنصر در ارتفاع لگاریتم رادیکال ان برابر رادیکال ان تقسیم بر ۲ است. پس جمع عناصر ۱+۲+۴+۸+...+ رادیکال ان برابر مضربی از رادیکال ان است. الگوریتم پارتیشن هم برابر رادیکال ان می شود. با این حساب زمان این الگوریتم رادیکال ان می شود.

این تحلیل شما خیلی دقیق نیست

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

نتیجه اینکه این رهیافت شما با الگوریتمی کمتر از پیچیدگی n قابل پیاده سازی نیست.

تعریف درخت کامل یعنی اینکه تا سطح n منهای ۱ درخت پر باشد و در سطح n از سمت چپ پر شده باشد. در این صورتی که شما می فرمایید مثال زیر را حل کنید مین هیپی دارای ۶۴ سطح است ۸ امین مینیمم را در سطح بیشتر از ۸ تونستین قرار بدین.

[ADELZX]

(۰۸ اسفند ۱۳۹۵ ۰۱:۴۰ ق.ظ)computerman نوشته شده توسط:  اقای mahditorki منم موافقم با نظرتون راجب به سوال ۳
چون از O استقاده کرده و O یعنی همه حالت یه الگوریتم حداکثر به این پیچیدگی برسن و به نطر من هم O)nمیشهنا

راس میگینا
برای سوال ۲ که هر دو گزینه ۳ و ۴ درسته ک
به نظرم روی کلید اولیه اومد اعتراض کنیم ممکنه به خاطر کلمه "بهترین" بگن نه هر دوش امکان پذیر نیست؟

در مورد سوال ۳ اگر یک حد بالایی برای تمامی حالت ها (از بهترین تا بدترین) بخواهیم ارائه دهیم قطعا رهیافت شما درسته و از مرتبه n است

اما در مورد سوال ۲ که الان روش بحث وجود داره ، چون در صورت سوال به صورت صریح قید شده که بهترین گزینه انتخاب شود در نتیجه به صورت حدی klogk از klogn برای همه حالات بهینه تر و دقیق تر می باشد
بنظر بنده بهتر بود که طراح محترم از نماد تتا به جای بیگ او استفاده می کردن

[computerman]

(۰۹ اسفند ۱۳۹۵ ۱۲:۵۶ ق.ظ)damash نوشته شده توسط:  به نظرم سوال۹ جوابش گزینه۲ یعنی n میشه. چون گراف کامل هستش و برای رفتن به تمام رئوس بعدی، نیازی به بازگشت به راس قبلی نیست و از هر راس میشه به تمام رئوس رسید.
سوال ۱۲ هم که با پریم و کراسکال قابل حله که جوابش یک میلیون میشه.
سوال ۱۳ رو با شک زدم گزینه۱ یعنی nlogn، به نظر شما چه جوابی درسته و چرا؟!!
سوال ۱۶ که به نظرم درجی بهترین الگوریتم برای آرایه از قبل مرتب شده هستش. چون حتی یک تعویض هم نداره.
سوال ۱۷ رو گزینه۴ زدم.
لطفا نظرتون رو در مورد این سوالها بگید که ایشالا بریم سوالات بعدی

۹ و ۱۲ و ۱۶ رو ک زدم شبیه شما زدم

[گلاره]

خب بریم سراغ سیستم عامل. سییتم عامل چی زدین؟
۳۱/ ۱
۳۳/ ۱
۳۴/ ۳
۳۵/ ۲
من همینارو زدم شما چی زدین و کدوم گزینه ها درسته؟

[ADELZX]

در مورد سوال ۶
اگر مقدار اولیه بینهایت که در ابتدای الگوریتم دایجسترا به فاصله هر گره نسبت داده شده رو نیز حساب کنیم با توجه به شبه کد الگوریتم برای هر گره ۲ بار مقدار فاصله آن نسبت به گره مبدا تغییر می کند که در مجموع تعداد به روز رسانی ها برای همه گره ها [tex]2n[/tex] می باشد.
از این رو هزینه سرشکنی تعداد به روز رسانی ها [tex]\frac{2n}{n}[/tex] می باشد که از مرتبه [tex]O(1)[/tex] می باشد.

---

برای سوال ۸ نیز این تحلیل صحیح است

(۰۸ اسفند ۱۳۹۵ ۱۱:۰۵ ب.ظ)www نوشته شده توسط:  فرض کنید چهار راس a,b,c,d دارید هزینه a به b برابر ۴ و a به C برابر ۱ و c به d برابر ۱ و d به b برابر ۱ است کوتاهترین مسیرa به b برابر ۳ با راسهای acdb می باشد اگر به وزن هریال ۳ واحد اضافه کنید کوتاهترین مسیر عوض می شود. رد گزینه ۱
فرض کنید چهار راس a,b,c,d دارید هزینه a به b برابر ۲ و a به C برابر ۱ و c به d برابر ۱ و d به b برابر ۱ است کوتاهترین مسیرa به b برابر ۲ با راسهای ab می باشد اگر از وزن هریال ۳ واحد کم کنید کوتاهترین مسیر عوض می شود. رد گزینه ۳
برای ۳و۴ چون احتمال ایجاد دور منفی است کوتاهترین مسیر عوض می شود.
گزینه ۲ صحیح است. این هم اثباتش:
فرض کنید چهار راس a,b,c,d دارید هزینه a به b برابر w و a به C برابر x و c به d برابر y و d به b برابر z است فرض کنید کوتاهترین مسیرa به b برابر ۳ با راسهای acdb می باشد پس x+y+z<w اگر به هر یال عدد p ضرب شود داریم:
p(x+y+z)<wp و از طرفین p را حذف کنید جواب حاصل می شود.
اگر p منفی باشد جهت عوض می شود رد گزینه۴

---

سوال ۹ نیز این تحلیل صحیح است

(۰۹ اسفند ۱۳۹۵ ۱۲:۵۶ ق.ظ)damash نوشته شده توسط:  به نظرم سوال۹ جوابش گزینه۲ یعنی n میشه. چون گراف کامل هستش و برای رفتن به تمام رئوس بعدی، نیازی به بازگشت به راس قبلی نیست و از هر راس میشه به تمام رئوس رسید.

[computerman]

(۰۹ اسفند ۱۳۹۵ ۱۰:۱۹ ق.ظ)ADELZX نوشته شده توسط:  در مورد سوال ۶
اگر مقدار اولیه بینهایت که در ابتدای الگوریتم دایجسترا به فاصله هر گره نسبت داده شده رو نیز حساب کنیم با توجه به شبه کد الگوریتم برای هر گره ۲ بار مقدار فاصله آن نسبت به گره مبدا تغییر می کند که در مجموع تعداد به روز رسانی ها برای همه گره ها [tex]2n[/tex] می باشد.
از این رو هزینه سرشکنی تعداد به روز رسانی ها [tex]\frac{2n}{n}[/tex] می باشد که از مرتبه [tex]O(1)[/tex] می باشد.

---

برای سوال ۸ نیز این تحلیل صحیح است

(۰۸ اسفند ۱۳۹۵ ۱۱:۰۵ ب.ظ)www نوشته شده توسط:  فرض کنید چهار راس a,b,c,d دارید هزینه a به b برابر ۴ و a به C برابر ۱ و c به d برابر ۱ و d به b برابر ۱ است کوتاهترین مسیرa به b برابر ۳ با راسهای acdb می باشد اگر به وزن هریال ۳ واحد اضافه کنید کوتاهترین مسیر عوض می شود. رد گزینه ۱
فرض کنید چهار راس a,b,c,d دارید هزینه a به b برابر ۲ و a به C برابر ۱ و c به d برابر ۱ و d به b برابر ۱ است کوتاهترین مسیرa به b برابر ۲ با راسهای ab می باشد اگر از وزن هریال ۳ واحد کم کنید کوتاهترین مسیر عوض می شود. رد گزینه ۳
برای ۳و۴ چون احتمال ایجاد دور منفی است کوتاهترین مسیر عوض می شود.
گزینه ۲ صحیح است. این هم اثباتش:
فرض کنید چهار راس a,b,c,d دارید هزینه a به b برابر w و a به C برابر x و c به d برابر y و d به b برابر z است فرض کنید کوتاهترین مسیرa به b برابر ۳ با راسهای acdb می باشد پس x+y+z<w اگر به هر یال عدد p ضرب شود داریم:
p(x+y+z)<wp و از طرفین p را حذف کنید جواب حاصل می شود.
اگر p منفی باشد جهت عوض می شود رد گزینه۴

---

سوال ۹ نیز این تحلیل صحیح است

(۰۹ اسفند ۱۳۹۵ ۱۲:۵۶ ق.ظ)damash نوشته شده توسط:  به نظرم سوال۹ جوابش گزینه۲ یعنی n میشه. چون گراف کامل هستش و برای رفتن به تمام رئوس بعدی، نیازی به بازگشت به راس قبلی نیست و از هر راس میشه به تمام رئوس رسید.

من با تحلیلتون راجب سوال ۶ موافقم
چون هر بار در الگوریتم دایجسترا فاصله یک نود که کمترین مقدار را در میان مابقی دارد با مبدا تغییر میکند پس در کل دفعات O(n بار تغییر داریم که سرشکن شده آن O(1 است.