(۰۳ اسفند ۱۳۸۹ ۰۱:۰۷ ب.ظ)admin نوشته شده توسط: سوال ۳۳: جواب درست گزینه دوم (البته به نظر من)با الگوریتم موافقم منتها زمانش میشه logn نه به توان ۲ش.
الگوریتمش خیلی پیچیدهاست و طاقت فرسا حوصله نوشتنش رو هم ندارم!. کسی مخالفتی داره بگه تا گزینه رو عوض کنیم!!
راهنمایی: هر بار میانه دو لیست رو میگیریم و با هم مقایسه میکنیم اگه میانه یکی بزرگتر از دیگری بود میانهشو دوباره میگیریم!بدون مهلت دادن! (و البته مقدار k رو که راحت میشه حساب کرد که الان با این دو میانه چنده) این عمل به اندازه logn * logn زمان میبره. سوال فوق العاده زیبایی است این سوال.
در مورد سوال ۳۲ شما با گزاره دوم مشکلی دارین؟
توضیح من که بالا نوشتم مشکلی داره؟
دقت کنید که گراف بیجهت هست.
(۰۳ اسفند ۱۳۸۹ ۰۱:۰۷ ب.ظ)admin نوشته شده توسط: سوال ۳۳: جواب درست گزینه دوم (البته به نظر من)دکتر در حالت کل به نظرتون سوال ابهام نداره؟آرایه تک عنصری را در نظر بگیرید(این آرایه مرتبه دیگه)که با آرایه n-1 عنصری ترکیب میشه!حالا باید جای تک عنصر آرایه اول در مجموع n عنصر پیدا بشه که با رول partitioning در بدترین حالت از مرتبه n هستش،و پیدا کردن k امین عنصر از آرایه بدست اومده که مرتب هست از مرتبه ۱ هستش!پس الگوریتم در بدترین حالت از مرتبه n هست.که با توجه به اینکه
الگوریتمش خیلی پیچیدهاست و طاقت فرسا حوصله نوشتنش رو هم ندارم!. کسی مخالفتی داره بگه تا گزینه رو عوض کنیم!!
راهنمایی: هر بار میانه دو لیست رو میگیریم و با هم مقایسه میکنیم اگه میانه یکی بزرگتر از دیگری بود میانهشو دوباره میگیریم!
n زیر مجموعه n+logn هست،و تنها گزینه ای که می تونه جواب را پوشش بده همین گزینه هست!
اگر بدترین مرتبه حالت میانگین مد نظر باشه با استفاده از برنامه نویسیه تقسیم و غلبه می تونیم الگوریتمی از مرتبه log n بدست بیاریم.
باید دید منظور طراح چی بوده!
من خودم گزینه ۳ را زدم.
در سوال ۳۲ گفته شده که گراف وزن دار هست و مطمئنا نه در و 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 نوشته شده توسط: با توجه به گراف قبلی که ناقص بود این گراف را کامل کردم بیا اینم جواب الف که نشون میده این گزینه غلطه.
اگر ما رو متهم نکنی که "چون فلانی خودش یک چیزی زده نمی خواد قبول کنه!!"
، من نیمچه اثباتی که کرده بودم با مثال شما تطبیق دادم که ببینم کجا اشتباه کردم. خلاصه بخوام بگم مساله اینه که در گراف های وزن دار اما بدون جهت، کوتاه ترین مسیر بین هر زوج راس در مولفه های شامل یال منفی، منهای بینهایت خواهد بود و از اون جایی که مساله یافتن درخت پوشای کمینه هست، یک مولفه داریم. نتیجه اخلاقی باز هم این می شه که در سوالات کنکور از اون جایی که بسیاری از فرض‌ها ناقص بیان می شه و گاها بیان نمی شه، مخصوصا در سوالاتی تئوری از این دست، فقط می شه منتظر موند تا ببنیم که آقای طراح موقع نوشتن این سوال داشته به چی فکر می کرده!!!