بچه‌ها اون کد رو چی زدین؟
اون که گفته بود در نهایت k چند رو برمیگردونه ؟
من زدم الگوریتم تموم نمیشه یعنی با مثال به این جواب رسیدم.

آره منم مثال زدم دیدم تموم نمیشه یعنی به حالت اول برگشت!

(۳۰ بهمن ۱۳۸۹ ۱۱:۰۶ ب.ظ)afagh1389 نوشته شده توسط:  آره منم مثال زدم دیدم تموم نمیشه یعنی به حالت اول برگشت!

من با دو تا مثال دیدم اون ۳ تا نمیشه!
در نتیجه همینی که شما زدیو تو آخرین لحظه زدم.

دفترچه های کنکور کارشناسی ارشد کامپیوتر سال ۱۳۹۰

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

در مورد اون کد اره گزینه ۴ میشد کد تموم نمیشد.
در مورد اون سوال کا امین عنصر در اجتماع دو لیست میشه lgn
در مورد کد هافمن هم بگم که با جستجوی خطی میشه n به توان دو.

معیار دفترچه D است که در سایت لینکشو دوستان گذاشتن
نظرتون در مورد سوال ۳۱ چیه ؟ کدوم گزینه درست است ؟من خودم ۳ زدم

رو سوال چی بود؟

---

سوال ۳۰ هم من بین دو گزینه شک کردم بین ۲و۳ نزدم.
راستی بچه‌ها سوال ۳۲ گزینه ۲ جواب میشه؟
به نظر من که جواب ۲ میشه من اینو زدم.

۳۲ یا ۲ یا ۳ من روی عبارت آخر شک دارم . البته من نزدم

تو هر گرافی در نظر بگیری با هر کدوم الگوریتم کوتاهترین مسیر بری درست در میاد پس تنها یه عبارت درسته.

ملاک گزینه‌ها دفترچه ۵۰۱D است.

سوال ۳۱: گزینه ۳، [tex]f(i)=MAX\begin{Bmatrix} f(i-1), w_{i} f(i-2) \end{Bmatrix}[/tex]
در این سوال برای محاسبه f برای خانه i ام، توجه می کنیم که پوستر یا در خانه i‌ام نصب می شود یا خیر، اگر نصب نشود که مسلما بیشینه خانه‌ها تا خانه i - 1‌ام جواب خواهد بود. اگر پوستر روی خانه i‌ام نصب شود، اولا w آن به جواب اضافه خواهد شد و ثانیا چون یک پوستر روی دو تابلوی پشت سر هم نمی تواند نصب شود مجموع وزن i‌ام با بیشینه تا خانه i - 2‌ام جواب خواهد بود.

سوال ۳۲: گزینه ۱، (۲ گزاره درست است. با یه مقدار شانس!)
گزاره ۱ درست است. فرض کنیم یال e = uv در درخت باشد. همان رئوس u و v را در نطر می گیریم. اگر e کوتاهترین مسیر بین آن‌ها نباشد پس راسی مثل w وجود دارد که uw+wv < uv . توجه داریم که uvw یک دور تشکیل خواهند داد. حال با توجه به این که چنین دوری موجود است، اگر بخواهیم MST را بسازیم، یال uv نمی تواند در درخت باشد.(تناقض) چرا که یکی از روش های ساخت MST این است که در هر دور یال های با وزن ماکسیمم را حذف کنیم تا زمانی که گراف همبند باقی بماند. با این روش یال uv در MST نخواهد بود.
گزاره ۲ هم راه حلی به غیر از دایجسترا به ذهنم نرسید. (از BFS نمی توان استفاده کرد چون گراف وزن دار است، پس ممکن است وزن یال‌ها متفاوت باشد.) من این گزاره رو غلط فرض کردم.
گزاره ۳ درست است. اگر این دو یال در دو دور مجزا باشند، یا یکی یا هر دوی آن‌ها یال برشی باشند، مسلما هر دوی آن‌ها در MST خواهند بود. اگر هر دو در یک دور باشند، واضح است که دور با حداقل ۳ یال تشکیل می شود. در هر دوری که شامل هر دوی آن‌ها باشند، باید بقیه یال‌ها حذف شوند، چون بقیه مسلما وزن بیشتری نسبت به این دو دارند و حذف هر کدام از این دو موجب افزایش وزن کل MST خواهد شد.

سوال ۳۳: گزینه ۳، log n جواب است. برای پیدا کردن میانه (سوال CLRS) هزینه log n است. برای دیگر آماره‌ها با تغییراتی می توان به این زمان رسید.

سوال ۳۴: نزدم، ولی فکر کنم، ممکن است تمام نشود، جواب باشد.

سوال ۳۵: گزینه ۲، n^2 جواب است. در هر مرحله دو مینیمم را با تتای i (از ۱ تا n) پیدا می کنیم. آن‌ها را با عناصر انتهای آرایه تعویض کرده و در همان انتهای آرایه ادغام را انجام می دهیم. در هر مرحله طول آرایه به اندازه یک کم خواهد شد. هزینه اصلی پیدا کردن مینیمم هاست. اگر بخواهیم آرایه را ابتدا مرتب کنیم، ادغام و درج در آرایه در هر مرحله به همین هزینه منتهی خواهد شد.

سوال ۳۲ گزاره ۱ غلطه من سر کنکور این گزاره را رد کردم یک مثلث با دو وزن ۱ و یک وزن ۲ مثال بزن

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

درسته، نمی دونم چرا فرض کردم که گراف وزن هاش متفاوته...
ان شاا... که دومی و سوی درستند....

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

نظر من درباره سوال ۳۴:
من تا الان ۳ بار مثال زدم و هر سه بار به جواب رسیدم
با استفاده از این مثال‌ها میتونم دو گزینه ۲و۳ رو حذف کنم و تا الان بیشتر از logn زمان نبرده.
به نظر من جواب گزینه ۴ هست.
دوستان اگه مثال نقض دارن بگن که چک کنیم شاید من ذهنم همش یه مدل داره مثال میزنه

(۰۲ اسفند ۱۳۸۹ ۰۴:۰۳ ب.ظ)khoofi66 نوشته شده توسط:  نظر من درباره سوال ۳۴:
من تا الان ۳ بار مثال زدم و هر سه بار به جواب رسیدم
با استفاده از این مثال‌ها میتونم دو گزینه ۲و۳ رو حذف کنم و تا الان بیشتر از logn زمان نبرده.
به نظر من جواب گزینه ۴ هست.
دوستان اگه مثال نقض دارن بگن که چک کنیم شاید من ذهنم همش یه مدل داره مثال میزنه

منم سر جلسه مثال زدم و log n رو زدم
ولی مثال زیر رو حل کن
A[1]=3
A[2]=1
A[3]=2

منم دقیقاً سر امتحان همین آرایه را مثال زدم و در حلقه افتادم

منم خودم الان که چک کردم دیدم با این مثال جواب نمیده پس فعلاً در مورد درست و غلطی این سوال نظر نمیدم

سوال ۳۲
بله دوستان به خاطر همون قیده یالی وجود دارد به نظر من هم ۳۲ گزاره اول و آخر درسته گزاره وسط رو شک دارم که امیدوارم غلط باشه
البته از طرز گفتنش هم غلطه چون گفته E و نه در V+E در حالی که به لحاظ عقلی اگه با E بشه با V+E که مرتبه بالاتره حتما میشه

سوال تابلو ۳۱ و سوال ۳۳ هم با حل pspsکاملا موافقم

سوال ۳۴ هم در دور خواهد افتاد آرایه ای که من مثال زدم پنج خونه ای بود و هر n مرحله بدون مرتب شدن به حالت اول بر میگشت که البته دوستمون هم بالا یه مثال آورده براش

۳۵ رو نزدم

(۰۳ اسفند ۱۳۸۹ ۰۱:۰۰ ق.ظ)موج نوشته شده توسط:  سوال ۳۲
بله دوستان به خاطر همون قیده یالی وجود دارد به نظر من هم ۳۲ گزاره اول و آخر درسته گزاره وسط رو شک دارم که امیدوارم غلط باشه
البته از طرز گفتنش هم غلطه چون گفته E و نه در V+E در حالی که به لحاظ عقلی اگه با E بشه با V+E که مرتبه بالاتره حتما میشه

سوال تابلو ۳۱ و سوال ۳۳ هم با حل pspsکاملا موافقم

سوال ۳۴ هم در دور خواهد افتاد آرایه ای که من مثال زدم پنج خونه ای بود و هر n مرحله بدون مرتب شدن به حالت اول بر میگشت که البته دوستمون هم بالا یه مثال آورده براش

۳۵ رو نزدم

۳۲ گزاره وسط درست هم میشه!!!! شما فرض کنید از الگوریتم کراسکال بریم واسه این کار! همون طور که می دونید این الگوریم از o(v2) هست حالا فرض کنید گراف کامل باشه و o(e)=o(v2) پس می بینید که شدنیه! ما اگه از bfs واسه این کار بریم میشه از o(e+v)اما همون طور که گفتم با کروسکال و گراف کامل هم باشه میشه.

گزینه های احتمالی:
۳۱: ۳
۳۲: ۱
۳۳: ۲
۳۴: ۴
۳۵: ۲

آقای تنهایی میشه نظرتون رو در مورد سوال ۳۳ و ۳۴ بگین.
با تشکر

آره وسطی هم درسته.
چون گراف بیجهت هست در زمان v+e میشه مساله رو حل کرد.
حالا چون همبنده پس تعداد یالها از راسها همیشه بیشتره و در زمان eمیشه حلش کرد.

ولی به نظر من سوال ۳۲ همون گزینه ۱ درسته!
استدلال هم دوستان آوردن به جای ما!

سوال ۳۳: جواب درست گزینه دوم (البته به نظر من)

الگوریتمش خیلی پیچیده‌‍‏‏است و طاقت فرسا حوصله نوشتنش رو هم ندارم!. کسی مخالفتی داره بگه تا گزینه رو عوض کنیم!!

راهنمایی: هر بار میانه دو لیست رو می‌‍‏‏گیریم و با هم مقایسه می‌‍‏‏کنیم اگه میانه یکی بزرگتر از دیگری بود میانه‌‍‏‏شو دوباره می‌‍‏‏گیریم! بدون مهلت دادن! (و البته مقدار k رو که راحت میشه حساب کرد که الان با این دو میانه چنده) این عمل به اندازه logn * logn زمان می‌‍‏‏بره. سوال فوق العاده زیبایی است این سوال.

(۰۳ اسفند ۱۳۸۹ ۰۱:۰۷ ب.ظ)admin نوشته شده توسط:  سوال ۳۳: جواب درست گزینه دوم (البته به نظر من)

الگوریتمش خیلی پیچیده‌‍‏‏است و طاقت فرسا حوصله نوشتنش رو هم ندارم!. کسی مخالفتی داره بگه تا گزینه رو عوض کنیم!!

راهنمایی: هر بار میانه دو لیست رو می‌‍‏‏گیریم و با هم مقایسه می‌‍‏‏کنیم اگه میانه یکی بزرگتر از دیگری بود میانه‌‍‏‏شو دوباره می‌‍‏‏گیریم! بدون مهلت دادن! (و البته مقدار k رو که راحت میشه حساب کرد که الان با این دو میانه چنده) این عمل به اندازه logn * logn زمان می‌‍‏‏بره. سوال فوق العاده زیبایی است این سوال.

با الگوریتم موافقم منتها زمانش میشه logn نه به توان ۲ش.
در مورد سوال ۳۲ شما با گزاره دوم مشکلی دارین؟
توضیح من که بالا نوشتم مشکلی داره؟
دقت کنید که گراف بیجهت هست.

(۰۳ اسفند ۱۳۸۹ ۰۱:۰۷ ب.ظ)admin نوشته شده توسط:  سوال ۳۳: جواب درست گزینه دوم (البته به نظر من)

الگوریتمش خیلی پیچیده‌‍‏‏است و طاقت فرسا حوصله نوشتنش رو هم ندارم!. کسی مخالفتی داره بگه تا گزینه رو عوض کنیم!!

راهنمایی: هر بار میانه دو لیست رو می‌‍‏‏گیریم و با هم مقایسه می‌‍‏‏کنیم اگه میانه یکی بزرگتر از دیگری بود میانه‌‍‏‏شو دوباره می‌‍‏‏گیریم! بدون مهلت دادن! (و البته مقدار k رو که راحت میشه حساب کرد که الان با این دو میانه چنده) این عمل به اندازه logn * logn زمان می‌‍‏‏بره. سوال فوق العاده زیبایی است این سوال.

دکتر در حالت کل به نظرتون سوال ابهام نداره؟آرایه تک عنصری را در نظر بگیرید(این آرایه مرتبه دیگه)که با آرایه n-1 عنصری ترکیب میشه!حالا باید جای تک عنصر آرایه اول در مجموع n عنصر پیدا بشه که با رول partitioning در بدترین حالت از مرتبه n هستش،و پیدا کردن k امین عنصر از آرایه بدست اومده که مرتب هست از مرتبه ۱ هستش!پس الگوریتم در بدترین حالت از مرتبه n هست.که با توجه به اینکه
n زیر مجموعه n+logn هست،و تنها گزینه ای که می تونه جواب را پوشش بده همین گزینه هست!
اگر بدترین مرتبه حالت میانگین مد نظر باشه با استفاده از برنامه نویسیه تقسیم و غلبه می تونیم الگوریتمی از مرتبه log n بدست بیاریم.
باید دید منظور طراح چی بوده!
من خودم گزینه ۳ را زدم.

سوال ۳۲ گزینه یک در کتاب طراحی الگوریتم ارشد سپاهان گفته غلطه. صفحه شو دقیق براتون میگم.
سوال ۳۳ به نظر من ابتدا اجتماع را در lgn پیدا میکنیم سپس در lgn ما k امین عنصر را مییابیم جمع اینا میشه lgn.
۳۴- کد تموم نمیشه
۳۵- n به توان دو میشه.

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

عزیزم نا سلامتی خود جناب تنهایی مدیر تالار دکترای این رشته رو دارن
اگه قرار باشه به سپاهان استناد کرد به نظر من استناد به حرف دکتر بهتره
سوال ۳۲ بخش الف گفته که حتما دو راس وجود دارد که ... شما اگه به نظرت غلطه یه مثال نقض بیار که هیچ دو راسی با این شرایط نباشه ما هم با تمام وجود میپذیریم
درمورد سوال ۳۳ من هم lgn زدم از خدامه که حرف تو درست باشه
۳۴ نظرم همینه

ولی من هنوز با اقای تنهایی مخالفم!!!!

در سوال ۳۲ گفته شده که گراف وزن دار هست و مطمئنا نه در و O( E )l و نه در O( E + V )l الگوریتمی برای آن وجود ندارد.( دایسترا O( E log V )l و O( v ^ 2 )l خواهد بود. )

در مورد سوال ۳۳ هم که جناب تنهایی اظهار نظر فرمودند. دقت کنید که اگر بخوایم اجتماع دو لیست رو حساب کنیم O( n )l زمان میبره. راه حل دیگه این سوال دو باینری سرچ تودرتو هست که زمان آن O( logn ^ 2 )l خواهد بود.

برای سوال ۳۲ لطفا این فایل رو ببینید.
از کتاب clrs هست.
فصل ۲۴ صفحه ۶۴۲/

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

حل دو سوال طراحی الگوریتم

۳۱-چند تا از گزاره های زیر درست هستند؟
الف)اگر در یک گراف وزن دار بدون جهت یال e=(u,v) در درخت فراگیر کمینه باشد حتما دو راس وجود دارد که کوتاهترین مسیر بین آن دو از e می گذرد.
ب)مسیله‌ی یافتن همه‌ی کوتاهترین مسیرها از یک راس به بقیه‌ی راسها را در یک گراف وزندار بدون جهت و همبند با مجموعه‌ی یال هایe را می توان در O(e) و نه درO(e+v) بدست آوزد.
ج)در یک گراف وزن دار و ساده بدون جهت با وزن های نامساوی یال با سبک ترین وزن و یال دومین سبک ترین وزن هر دو در درخت فراگیر کمینه هستند.
جواب
گزینه الف نادرست است برای نشان دادن اشتباه بودن آن گراف زیر را مثال میزنم
چون شکل گراف نمیافتد یک گراف با چهار راس و پنج یال را با اطلاعات زیر در نظر بگیرید.[/code]

یال(a,b) وزن ۱ دارد.
یال(a,d) وزن۱- دارد.
بقیه یالها وزن ۲ دارند.
یالهای (a,b),(a,d),(c,d) دردرخت کمینه هستند. فرض میکنیم e=(c,d) باشد اما کوتاهترین مسیر بین هر دو راس از e نمیگذرد. کوتاهترین مسیر بین(a,b)=1و بین(a,d)=-1و بین(c,d)=l میباشد. با این اوصاف گزینه الف غلط است.لازم به ذکر است که برای کوتاهترین مسیر برابر (c,d)=(a,c)+(a,d) میباشد.
گزینه ب غلط است قسمت اخرباعث اشتباه بودنش هست چون با(e+v)هم انجام میشود در ضمن طولانی ترین مسیر هم با این زمان انجام پذیر است.
گزینه اخر درست است.
با این اوصاف تنها یک مورد درست است.
سوال۳۳-
دو آرایه مرتبa1,a2با مجموع تعدادn عنصرداده شده اند فرض کنید که عناصر مجزا هستند میخواهیم kامین عنصرa UNION b را به دست اوریم این کار را میتوان در کدام زمان زیر انجام داد؟

جواب:
با توجه مطلب گفته شده در فصل ۲۱ کورمن عملیات find,union هر کدام به زمان O(lgn) نیاز دارد. جواب این سوال میشهklgn.

---

راستی اگر کسی تو کشیدن شکل مشکلی داشت بگه براش ایمیل کنم.

(۰۴ اسفند ۱۳۸۹ ۰۱:۳۲ ب.ظ)www نوشته شده توسط:  حل دو سوال طراحی الگوریتم

۳۱-چند تا از گزاره های زیر درست هستند؟
الف)اگر در یک گراف وزن دار بدون جهت یال e=(u,v) در درخت فراگیر کمینه باشد حتما دو راس وجود دارد که کوتاهترین مسیر بین آن دو از e می گذرد.
ب)مسیله‌ی یافتن همه‌ی کوتاهترین مسیرها از یک راس به بقیه‌ی راسها را در یک گراف وزندار بدون جهت و همبند با مجموعه‌ی یال هایe را می توان در O(e) و نه درO(e+v) بدست آوزد.
ج)در یک گراف وزن دار و ساده بدون جهت با وزن های نامساوی یال با سبک ترین وزن و یال دومین سبک ترین وزن هر دو در درخت فراگیر کمینه هستند.
جواب
گزینه الف نادرست است برای نشان دادن اشتباه بودن آن گراف زیر را مثال میزنم
چون شکل گراف نمیافتد یک گراف با چهار راس و پنج یال را با اطلاعات زیر در نظر بگیرید.[/code]

یال(a,b) وزن ۱ دارد.
یال(a,d) وزن۱- دارد.
بقیه یالها وزن ۲ دارند.
یالهای (a,b),(a,d),(c,d) دردرخت کمینه هستند. فرض میکنیم e=(c,d) باشد اما کوتاهترین مسیر بین هر دو راس از e نمیگذرد. کوتاهترین مسیر بین(a,b)=1و بین(a,d)=-1و بین(c,d)=l میباشد. با این اوصاف گزینه الف غلط است.لازم به ذکر است که برای کوتاهترین مسیر برابر (c,d)=(a,c)+(a,d) میباشد.
گزینه ب غلط است قسمت اخرباعث اشتباه بودنش هست چون با(e+v)هم انجام میشود در ضمن طولانی ترین مسیر هم با این زمان انجام پذیر است.
گزینه اخر درست است.
با این اوصاف تنها یک مورد درست است.
سوال۳۳-
دو آرایه مرتبa1,a2با مجموع تعدادn عنصرداده شده اند فرض کنید که عناصر مجزا هستند میخواهیم kامین عنصرa UNION b را به دست اوریم این کار را میتوان در کدام زمان زیر انجام داد؟

جواب:
با توجه مطلب گفته شده در فصل ۲۱ کورمن عملیات find,union هر کدام به زمان O(lgn) نیاز دارد. جواب این سوال میشهklgn.

---

راستی اگر کسی تو کشیدن شکل مشکلی داشت بگه براش ایمیل کنم.

تعریف یال کمینه: یالی با کمترین وزن در یک گراف را می گویند

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

---

برای سوال ۳۱ اینم با شکل.

(۰۴ اسفند ۱۳۸۹ ۰۷:۳۱ ب.ظ)www نوشته شده توسط:  یال کمینه را تعزیفشو بلدیم لطفایاد نده سوالو دقیق بخون اینم مثال نقضش.
متاسفانه هر چقدم بخوای دلیل منطقی بیایی برخی نمیخوان قبول کنن حتما برا اینکه خودش اشتبا حل کرده نمیتونه بپذیره تا ادم‌ها تعصب روی چیزای غلط را داشته باشن نمیتونن مطلب جدید یاد بگیرن.
امیدوارم کسی ناراحت نشه و امیدوارم که سوال را دقیق بخونید.

---

برای سوال ۳۱ اینم با شکل.

سلام

مثال نقضتون برای این سوال درست به نظر نمیاد. چون کوتاه ترین مسیر بین a تا c از یال (c,d) عبور می کنه. من اثبات دقیق نکردم، ولی فکر می کنم که گزاره اول حتی برای گراف با یال های منفی هم درست باشه.

برای سوال ۳۳ اگر بخواهیم که اجتماع در زمان log انجام بشه و حتی کمتر امکان پذیر هست، ولی مساله این هست که در این حالت (یعنی اجتماع گیری با زمانی کمتر از n) با ساختمان داده پیچیده تری از یک آرایه سر کار داریم که غالبا هم یک درخت هست. حالا سوال اینه که آیا پیدا کردن k امین عنصر در این ساختمان داده با همون زمان logn که در آرایه انجام می شه امکان پذیر هست. من فکر می کنم که همون گزینه logn^2 درست باشه.

تو گراف که یال c,d) در درخت کمینه هست اما در بین کوتاهترین مسیرها نیست. یکم دقت کن.

(۰۵ اسفند ۱۳۸۹ ۰۱:۱۴ ب.ظ)www نوشته شده توسط:  تو گراف که یال c,d) در درخت کمینه هست اما در بین کوتاهترین مسیرها نیست. یکم دقت کن.

پیشنهاد میکنم شما یکم بیشتر دقت کنی. مثال نقض این سوال برای یال c->d بود که برای این یال هم دو راس a و c وجود دارند که کوتاهترین مسیر بین این دو راس از این یال میگذره.

دقت کن کلمه حتما باعث غلط شدن این گزینه شده است.

با توجه به گراف قبلی که ناقص بود این گراف را کامل کردم بیا اینم جواب الف که نشون میده این گزینه غلطه.

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

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

منم نظرم با www یکسانه.
دقیقا جمله مورد نظر رو چند جا خوندم که گفته بود غلطه.یکجا رو که دقیقا یادم هست تمرینهای اخر فصل کتاب الگوریتم یوسفی بود که از کتاب مرجع کپی کرده بود.و فکر کنم جوابش رو کامل داده بود و مثال نغز هم اورده بود.

ای خدا باز که بهونه میایین حالا با عوض کردن وزن‌ها میشه یک میلیون مثال نقض اورد. مثلا اگه میگین اون یال در درخت کمینه نمیشه وزنش را یک کنین باز جواب من درسته.

(۰۶ اسفند ۱۳۸۹ ۰۷:۲۳ ب.ظ)www نوشته شده توسط:  ای خدا باز که بهونه میایین حالا با عوض کردن وزن‌ها میشه یک میلیون مثال نقض اورد. مثلا اگه میگین اون یال در درخت کمینه نمیشه وزنش را یک کنین باز جواب من درسته.

دوست گرامی بهونه نیست!!! اگه منظورتون ۱ کردن وزن یال d,e هست که باز هم درست در میاد!! اما اگه منظورتون ۱ کردن وزن یالd,c هست بعد یگه d,e جزء درخت نمیشه و dc که ۱ است میشه و باز درست در میاد....یکم صبور باش

در مورد حلقه منفی برین فصل ۲۴ و۲۵کورمنو بخون ببین اونجا گفته میشه پس اگر مرجع نخوندین بهتون حق میدم اما اینو مطمین باشین.

---

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

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

---

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

من فرض اینی که حلقه منفی هم کار نداشته باشیم زدم!!!هنوز مثالهاتون مطمئن نیست!

این سوالو مطمینم بالاخره بازم میگم کلمه حتما را دقت کن .

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

شما هم به کلمه وجود دارد دقت کن...وجود دارددد...نه همه راس‌ها لزوما....البته اینو توی مثال هات نشون داده بودی اما مثال هات مثال نقض نبود.