کنکور ۹۶ دکترا لطفا همه داوطلبان شرکت کنند. - نسخهی قابل چاپ |
RE: کنکور ۹۶ دکترا لطفا همه داوطلبان شرکت کنند. - ahonari - 08 اسفند ۱۳۹۵ ۰۷:۰۰ ب.ظ
سلام سوال np قطعا گزینه ۴ صحیح است سوال pre , pos هم اگر رسم کنیم گزیمه یک جوابه (۰۷ اسفند ۱۳۹۵ ۰۷:۱۶ ب.ظ)computerman نوشته شده توسط: سلام دوستان np سخت قطعا جوابه اگر کامل باشه کاهش درجه ممکنه کامل نباشه |
RE: کنکور ۹۶ دکترا لطفا همه داوطلبان شرکت کنند. - computerman - 08 اسفند ۱۳۹۵ ۰۸:۲۷ ب.ظ
(۰۸ اسفند ۱۳۹۵ ۰۸:۲۲ ب.ظ)www نوشته شده توسط: با سلام عجب خب همون رادیکال n عنصر اول رو از کجا بیاریم که روش پارتیشن بزنیم؟؟؟ مگه هیپ مرتب شدس که پیداشون کنیم!!! (۰۸ اسفند ۱۳۹۵ ۰۷:۰۰ ب.ظ)ahonari نوشته شده توسط: سلام سوال np قطعا گزینه ۴ صحیح استمن زدن گزینه ۱ که میشد ۳ دفترچه خودم |
کنکور ۹۶ دکترا لطفا همه داوطلبان شرکت کنند. - alireza01 - 08 اسفند ۱۳۹۵ ۱۱:۰۲ ب.ظ
سوال ۴ میشه گزینه ۴ فک میکنم . |
کنکور ۹۶ دکترا لطفا همه داوطلبان شرکت کنند. - گلاره - ۰۸ اسفند ۱۳۹۵ ۱۱:۰۲ ب.ظ
سلام سوال هشت مگه هر سه تای اول صحیح نیست؟ مثال نقضی میتونین بیارین که ثابت کنید گزاره دوم و سوم صحیح نیست؟ |
RE: کنکور ۹۶ دکترا لطفا همه داوطلبان شرکت کنند. - www - 08 اسفند ۱۳۹۵ ۱۱:۰۵ ب.ظ
(۰۸ اسفند ۱۳۹۵ ۰۸:۲۷ ب.ظ)computerman نوشته شده توسط: [quote='www' pid='432078' dateline='1488124338'] عجب خب همون رادیکال 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 منفی باشد جهت عوض می شود رد گزینه۴ |
RE: کنکور ۹۶ دکترا لطفا همه داوطلبان شرکت کنند. - damash - 09 اسفند ۱۳۹۵ ۱۲:۲۲ ق.ظ
(۰۷ اسفند ۱۳۹۵ ۰۸:۴۱ ب.ظ)ADELZX نوشته شده توسط: برای سوال دوم نیز این پیدا کردن k امین عنصر در یک درخت هیپ از مرتب klogk می باشد منم همین گزینه رو زدم. (۰۷ اسفند ۱۳۹۵ ۱۰:۲۱ ب.ظ)robotic1981 نوشته شده توسط: ۵ رو شک داشتم نزدم سوال ۳ رو زدم logn و سوال ۴ هم زدم (n2) (۰۸ اسفند ۱۳۹۵ ۰۶:۴۰ ب.ظ)tabestan نوشته شده توسط:به نظر من هم جواب سوال ۱۴ گزینه۱ میشه. برای اطمینان میتونیم با درنظرگرفتن پیمایش میان ترتیب گزینه۱، و دو پیمایش که توی سوال داده شده، درخت رو ترسیم کنیم. به شکل پیوستی نگاه کنید ببینید من درست میگم یا نه.روی این شکل هر سه تا پیمایش رو امتحان کنید(08 اسفند ۱۳۹۵ ۰۶:۰۵ ب.ظ)robotic1981 نوشته شده توسط:بله، دلیل این قضیه اینه که اگر درخت گره تک فرزند داشته باشه، صرفا با این دو پیمایش نمیشه مشخص کرد که اون تک فرزند، به عنوان فرزند چپ محسوب میشه یا راست. اما در صورتی که گره تک فرزند وجود نداشته باشه، میشه یک درخت منحصربفرد را تعیین کرد.(08 اسفند ۱۳۹۵ ۰۵:۳۹ ب.ظ)mahditorki نوشته شده توسط: در مورد اینکه چطور میشه فهمید گره تک فرزند تداره علاوه بر مطلب قبل یاداوری کنم که : |
RE: کنکور ۹۶ دکترا لطفا همه داوطلبان شرکت کنند. - www - 09 اسفند ۱۳۹۵ ۱۲:۳۹ ق.ظ
(۰۹ اسفند ۱۳۹۵ ۱۲:۲۲ ق.ظ)damash نوشته شده توسط:جواب سوال ۳ هم به احتمال زیاد n میباشد. علاوه بر درخت مورب درختای دیگری هم وجود دارد که زمان آن n شود. مثلا فرض کنید عنصر x ریشه باشد و درخت فقط فرزند راست دارد اما فرزندان آن به صورت زیر هستند. یک فرزند راست و بقیه فرزند چپ ان فرزند راست باشند. در این صورت n منهای ۲ عنصر فرزند چپ فرزند راست اند.(07 اسفند ۱۳۹۵ ۰۸:۴۱ ب.ظ)ADELZX نوشته شده توسط: برای سوال دوم نیز این پیدا کردن k امین عنصر در یک درخت هیپ از مرتب klogk می باشد در مورد سوال ۵ گزینه ۴ درست است. در مورد سوال ۴ هم میتونم بگم الگوریتمی با زمان کمتر ازn2 میشه این کارو انجام داد. |
RE: کنکور ۹۶ دکترا لطفا همه داوطلبان شرکت کنند. - ADELZX - 09 اسفند ۱۳۹۵ ۱۲:۵۰ ق.ظ
(۰۸ اسفند ۱۳۹۵ ۱۱:۰۵ ب.ظ)www نوشته شده توسط: ارتفاع هیپ logn است و در سطح logn تعداد عناصر n/2 می باشد. پس تعداد عنصر در ارتفاع لگاریتم رادیکال ان برابر رادیکال ان تقسیم بر ۲ است. پس جمع عناصر ۱+۲+۴+۸+...+ رادیکال ان برابر مضربی از رادیکال ان است. الگوریتم پارتیشن هم برابر رادیکال ان می شود. با این حساب زمان این الگوریتم رادیکال ان می شود. این تحلیل شما خیلی دقیق نیست و ابهام دارد درخت هیپ یک درخت کامل است و ارتفاع آن حداکثر از درجه لگاریتم n می باشد، فرض وجود رادیکال nامین عدد کوچک در سطح رادیکال n درخت هیپ اشتباه است چون این ارتفاع در درخت کامل تعریف نشده است. با توجه به این موضوع قطعا رادیکال nامین عدد کوچک حداااکثر در سطح آخر درخت می باشد. نتیجه اینکه این رهیافت شما با الگوریتمی کمتر از پیچیدگی n قابل پیاده سازی نیست. |
کنکور ۹۶ دکترا لطفا همه داوطلبان شرکت کنند. - damash - 09 اسفند ۱۳۹۵ ۱۲:۵۶ ق.ظ
به نظرم سوال۹ جوابش گزینه۲ یعنی n میشه. چون گراف کامل هستش و برای رفتن به تمام رئوس بعدی، نیازی به بازگشت به راس قبلی نیست و از هر راس میشه به تمام رئوس رسید. سوال ۱۲ هم که با پریم و کراسکال قابل حله که جوابش یک میلیون میشه. سوال ۱۳ رو با شک زدم گزینه۱ یعنی nlogn، به نظر شما چه جوابی درسته و چرا؟!! سوال ۱۶ که به نظرم درجی بهترین الگوریتم برای آرایه از قبل مرتب شده هستش. چون حتی یک تعویض هم نداره. سوال ۱۷ رو گزینه۴ زدم. لطفا نظرتون رو در مورد این سوالها بگید که ایشالا بریم سوالات بعدی |
RE: کنکور ۹۶ دکترا لطفا همه داوطلبان شرکت کنند. - www - 09 اسفند ۱۳۹۵ ۱۲:۵۷ ق.ظ
(۰۹ اسفند ۱۳۹۵ ۱۲:۵۰ ق.ظ)ADELZX نوشته شده توسط:تعریف درخت کامل یعنی اینکه تا سطح n منهای ۱ درخت پر باشد و در سطح n از سمت چپ پر شده باشد. در این صورتی که شما می فرمایید مثال زیر را حل کنید مین هیپی دارای ۶۴ سطح است ۸ امین مینیمم را در سطح بیشتر از ۸ تونستین قرار بدین.(08 اسفند ۱۳۹۵ ۱۱:۰۵ ب.ظ)www نوشته شده توسط: ارتفاع هیپ logn است و در سطح logn تعداد عناصر n/2 می باشد. پس تعداد عنصر در ارتفاع لگاریتم رادیکال ان برابر رادیکال ان تقسیم بر ۲ است. پس جمع عناصر ۱+۲+۴+۸+...+ رادیکال ان برابر مضربی از رادیکال ان است. الگوریتم پارتیشن هم برابر رادیکال ان می شود. با این حساب زمان این الگوریتم رادیکال ان می شود. |
RE: کنکور ۹۶ دکترا لطفا همه داوطلبان شرکت کنند. - ADELZX - 09 اسفند ۱۳۹۵ ۰۱:۰۴ ق.ظ
(۰۸ اسفند ۱۳۹۵ ۰۱:۴۰ ق.ظ)computerman نوشته شده توسط: اقای mahditorki منم موافقم با نظرتون راجب به سوال ۳ در مورد سوال ۳ اگر یک حد بالایی برای تمامی حالت ها (از بهترین تا بدترین) بخواهیم ارائه دهیم قطعا رهیافت شما درسته و از مرتبه n است اما در مورد سوال ۲ که الان روش بحث وجود داره ، چون در صورت سوال به صورت صریح قید شده که بهترین گزینه انتخاب شود در نتیجه به صورت حدی klogk از klogn برای همه حالات بهینه تر و دقیق تر می باشد بنظر بنده بهتر بود که طراح محترم از نماد تتا به جای بیگ او استفاده می کردن |
RE: کنکور ۹۶ دکترا لطفا همه داوطلبان شرکت کنند. - computerman - 09 اسفند ۱۳۹۵ ۰۱:۳۱ ق.ظ
(۰۹ اسفند ۱۳۹۵ ۱۲:۵۶ ق.ظ)damash نوشته شده توسط: به نظرم سوال۹ جوابش گزینه۲ یعنی n میشه. چون گراف کامل هستش و برای رفتن به تمام رئوس بعدی، نیازی به بازگشت به راس قبلی نیست و از هر راس میشه به تمام رئوس رسید. ۹ و ۱۲ و ۱۶ رو ک زدم شبیه شما زدم |
کنکور ۹۶ دکترا لطفا همه داوطلبان شرکت کنند. - گلاره - ۰۹ اسفند ۱۳۹۵ ۰۹:۳۶ ق.ظ
خب بریم سراغ سیستم عامل. سییتم عامل چی زدین؟ ۳۱/ ۱ ۳۳/ ۱ ۳۴/ ۳ ۳۵/ ۲ من همینارو زدم شما چی زدین و کدوم گزینه ها درسته؟ |
RE: کنکور ۹۶ دکترا لطفا همه داوطلبان شرکت کنند. - ADELZX - 09 اسفند ۱۳۹۵ ۱۰:۱۹ ق.ظ
در مورد سوال ۶ اگر مقدار اولیه بینهایت که در ابتدای الگوریتم دایجسترا به فاصله هر گره نسبت داده شده رو نیز حساب کنیم با توجه به شبه کد الگوریتم برای هر گره ۲ بار مقدار فاصله آن نسبت به گره مبدا تغییر می کند که در مجموع تعداد به روز رسانی ها برای همه گره ها [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 می باشد اگر به وزن هریال ۳ واحد اضافه کنید کوتاهترین مسیر عوض می شود. رد گزینه ۱ سوال ۹ نیز این تحلیل صحیح است (۰۹ اسفند ۱۳۹۵ ۱۲:۵۶ ق.ظ)damash نوشته شده توسط: به نظرم سوال۹ جوابش گزینه۲ یعنی n میشه. چون گراف کامل هستش و برای رفتن به تمام رئوس بعدی، نیازی به بازگشت به راس قبلی نیست و از هر راس میشه به تمام رئوس رسید. |
RE: کنکور ۹۶ دکترا لطفا همه داوطلبان شرکت کنند. - computerman - 09 اسفند ۱۳۹۵ ۱۰:۴۴ ق.ظ
(۰۹ اسفند ۱۳۹۵ ۱۰:۱۹ ق.ظ)ADELZX نوشته شده توسط: در مورد سوال ۶ من با تحلیلتون راجب سوال ۶ موافقم چون هر بار در الگوریتم دایجسترا فاصله یک نود که کمترین مقدار را در میان مابقی دارد با مبدا تغییر میکند پس در کل دفعات O(n بار تغییر داریم که سرشکن شده آن O(1 است. |