تالار گفتمان مانشت - مسائل حل شده كامل(طراحی الگوریتم)

یه نکته ریز؟!

Tue, 15 Jan 2013 21:00:19 +0000

چرا [tex]Lg(n!)= \Omega (nlgn)[/tex]
??!

محاسبه زمان اجرای الگوریتم بازگشتی

Tue, 08 Jan 2013 14:26:06 +0000

با توجه به تابع بازگشتی زیر مرتبه زمان را بیابید:

مقایسه مرتب بودن مرتبه های زمانی

Fri, 30 Nov 2012 06:43:14 +0000

لطفا بگید کدوم یک از دوتای زیر درست مرتب شدند؟
اولی:
[tex]n^{1000}<(1.005)^{n} ==
دومی:
[tex](1.005)^{n}
==
به نظر خودم دومی درست هست.اما نمی دونم چرا توی راهیان ارشد اولی رو زده
=

مرتبه زمانی 2

Tue, 27 Nov 2012 10:56:42 +0000

باسلام
t(nرا تتا برحسب بدست آورید
[tex]\left \{ \right.t(n)=2t(\left [ n/logn \right ]) 3n [/tex]
t(1)=1 t(2)=2

مرتبه زمانی

Sun, 25 Nov 2012 13:29:03 +0000

باسلام
چرا حلقه داخلی ربطی به حلقه خارجی نداره؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟؟

for(int i=0;i
( for(int i=0;i }
/*process a*/
}

سوال طراحی الگوریتم (Binary search)

Thu, 22 Nov 2012 12:18:00 +0000

در جستجوی دو دو یی ، اگر Sn و Pn به ترتیب میانگین مقایسات لازم در جستجوی موفق و ناموفق باشند آنگاه رابطه زیر برقرار است :

Sn=[(1+1/n)Pn]-1

چطور این رابطه اثبات می شود ؟؟؟؟؟؟؟

مقایسه پیچیدگی 2 تابع

Mon, 19 Nov 2012 11:32:45 +0000

سلام میشه بگید چطوری این دو تا رو میشه مقایسه کرد؟
n^logn
و (n^(4/3

تعداد درخت پوشا در درخت کامل Kn

Sat, 10 Nov 2012 10:29:01 +0000

تعداد درخت پوشا در درخت کامل Kn
پیوست رو نگاه کنید .

Untitled.png
اندازه فایل: 23.44 KB

پیچیدگی زمانی 3 قطعه کد تقریبا مشابه!

Fri, 09 Nov 2012 06:42:29 +0000

سلام
کتاب پوران پژوهش یه مثال داره که فکرمو خیلی مشغول کرده
در هر سه کد تعداد اجرای خط x=x+1 را بدست میاورد.

tarahi.jpg
اندازه فایل: 9.85 KB

[tex]n n-1 n-2 ... (n-\frac{n}{2} 1)=\frac{3n^{2} 2n}{8}=\Theta (n^{2})[/tex]

tarahi1.jpg
اندازه فایل: 9.96 KB

[tex]\frac{n}{2} \frac{n}{4} \frac{n}{8} ...=n*\frac{\frac{1}{2}}{1-\frac{1}{2}}=\Theta (n)[/tex]

tarahi2.jpg
اندازه فایل: 9.16 KB

[tex]n \frac{n}{2} \frac{n}{4} \frac{n}{8} ... \frac{n}{n}=\Theta (nlogn)[/tex]

پیچیدگی عبارت بازگشتی

Fri, 09 Nov 2012 06:36:50 +0000

سلام؛
در جواب تحلیل پیچیدگی این عبارت بازگشتی:
[tex]T(n) = T(n/5) log^2n[/tex]
نوشته:
[tex]T(n) = O(log^3(n))[/tex]
ولی راه حلش رو ننوشته. لطفا راهنمایی بفرمایید.
با تشکر

مسئله انتخاب فعالیت ها به روش حریصانه و تفاوت بلمن فورد و فلوید

Thu, 08 Nov 2012 21:37:43 +0000

(ابتدا از مدیریت محترم به دلیل اینکه سوالم رو بد جا پرسیده بودم عذر می خوام)
آیا الگوریتم حریصانه برای مسئله انتخاب فعالیت ها جواب بهینه می دهد یا خیر؟
در کتاب مقسمی در تمرین ها نوشته که در کتاب آقای قلی زاده اثبات شده که جواب بهینه می دهد، اما هم در تست های کتاب الگوریتم مقسمی و هم یکی از اساتید مثال نقضی آوردند که جواب بهینه را نمی دهد؟
لطفا با دلیل راهنمایی کنید.
و سوال دوم اینکه درباره فلوید می گن که در گراف با وزن منفی بدون دور منفی درست کار می کند و قدرت تشخیص دور منفی را هم دارد، درباره الگوریتم Bell man Ford نیز همین را نوشته اند آیا درسته یعنی این موضوع اشتباه است که بلمن فورد در گراف با دور منفی درست کار می کند و همان هایی که برای فلوید گفته اند برای بلمن فورد هم صادق است؟ در این صورت که دیگر بلمن فورد و فلوید فرقی نمی کنند؟!
ممنون و سپاسگزارم

بدست آوردن خارج قسمت و باقی مانده!!!

Sat, 27 Oct 2012 13:37:46 +0000

سلام!
استاد بهم گفت برو الگوریتم "چگونگی بدست آوردن خارج قسمت و باقی مانده ی یه عدد رو بر 10به توان m" بنویس!
کسی بلده؟

یعنی:

A rem 10^m
A divit 10^m

ممنون میشم اگه کسی اطلاعی داره راهنماییم کنه!

دانشجویان ارشد لطفا راهنمایی کنند !!!

Sat, 20 Oct 2012 06:27:09 +0000

با سلام

میخواستم در این مثال روش حل مسئله Bellman-Ford رو برام توضیح بدید.

با تشکر

تعیین نزدیکترین زوج نقاط در فضای دو بعدی(چرا 6 نقطه؟))

Tue, 16 Oct 2012 07:07:49 +0000

الگوریتم:
.1 در ابتدا نودها را در این فضا بر اساس مختصه x شان مرتب می کنیم
-2 سپس با نظر گرفتن یک خط فرضی مجموعه نقاط را به دو قسمت چپ و راست که هر کدام دارای. n/2 عنصر هستند تقسیم می کنیم
-3 دو زیر مسئله چپ و راست را حل کرده تا کمترین فاصله در هر دو زیر مسئله تولید شود و سپس جواب حل دو زیر مسئله را s 1 و s2 می نمامیم.

S=min(s1,s2) -1
-1 حال اگر شبیه روش یک بعدی فاصله نزدیکترین نقطه از نقاط چپ و راست خط را نیز در محاسبات داخل کنیم ممکن است به جواب صحیح نرسیم . لذا در این مسئله با اضافه کردن یکسری شرایط سعی می کنیم تعداد مقایسه ها را کم کنیم
می توان به اندازه S از خط وسط از هر دو طرف یک محدوده در نظر گرفت و تعداد نقاط داخل این باریکه را با هم مقایسه کرد که در نتیجه باز در بدترین شرایط تمام n/2 نقطه سمت چپ و n/2 نقطه سمت راست خط وسط در این باریکه ها قرار دارند و لذا مرتبه زمانی O(n^2) خواهد شد ولی می توان برای هر نقطه واقع در باریکه سمت چپ مانند p فقط نقاط واقع در مستطیل به طول 2s و عرضs حاصل شود. بدیهی است که که حداکثر تعداد نقاط واقع در این ناحیه مستطیلی شکل برابر با 6 نقطه است! و لذا برای هر نقطه در باریکه سمت چپ فقط باید با فاصله آن با 6 نقطه در باریکه سمت راست محاسبه کرد و این فواصل را نیز در محاسبه کمترین فاصله دخیل کرد.
حال سوال اینجاست چرا برابر با 6 نقطه است؟

این سیکما رو چطوری حلش کرده؟؟؟

Mon, 08 Oct 2012 20:06:17 +0000

3.jpg
اندازه فایل: 62.81 KB

مشکل از کتاب clrs

Sun, 07 Oct 2012 08:30:24 +0000

سلم بچه ها
اونایی که کتاب clrs دارن ص 169 تمرین 3-3-6 روی درخت صفحه قبلیش جواب نمیده؟؟ قضیه چیه؟

طراحی الکوریتم/مجانبها2

Mon, 01 Oct 2012 10:11:16 +0000

با سلام
[tex]if f=\left | n^{^{2}}sin n \right | then f(n)=o(n) or f(n)=\Omega (n)[/tex]

پاسخ این سوال نوشته اگر n طبیعی باشه درست هست در غیر اینصورت نه ممنون میشم دلیلش رو بگید چون من اصلا متوجه پاسخش نشدم
با سپاس

طراحی الکوریتم/مجانبها

Mon, 01 Oct 2012 09:54:18 +0000

با سلام
دوستان ممنون میشم بگید این رابطه درست است یا نه و چرا؟
[tex]2^{2n}= o(2^{n})[/tex]

با سپاس

طراحی الگوریتم - مرتبه زمانی

Sun, 30 Sep 2012 15:28:14 +0000

وقتی پیچیدگی زمانی یک تابع رو با (T (n نمایش میدیم، منظورمون بدست آوردن مقدار تابع نیست، بلگه تعداد دفعات تکرار تابع هست.

خوب خالا سوال من اینه:
اگر تابع ما از پیچیدگی زمانی (T (n-1) X T (n-1 داشته باشه. منظور این هست که در هر Tn تابع ذوبار T n-1 خواهد بود یعنی تشکیل یک درخت دودویی کامل میده با مرتبه زمانی (O (2^n و یا منظور این هست که باید مقادیر (T (n-1 در T n-1 بشه؟

توی کتاب (مقسمی صفحه 26) گفته شده (T (n-1) X T (n-1 داری پیچیدیگی زمانی (O (2^n هست. اگر اینطوره یعنی تفاوتی نمی کنه عملگر بین (T (n ها ضرب باشه یا جمع؟

چون برای (T (n-1) + T (n-1 هم پیچیدگی زمانی (O (2^n هست.

حل روابط بازگشتی(لطفاً سریع جواب بدید)

Tue, 14 Aug 2012 20:15:02 +0000

سلام

این قسمت که با خط قرمز مشخص کردم چی شده؟؟؟؟؟؟؟؟

15082012024.jpg
اندازه فایل: 51.28 KB