تمرين ساده طراحي الگوريتم
چهارده سال پیش منتشر شده
تعداد بازدید: 12331
کد پروژه: 3102
شرح پروژه
الگوريتمي براي جستجوي ترتيبي کميت x در ارايه a با يک مولفه را به روش بازگشتي بنويسيد و مرتبه زماني آنرا محاسبه کنيد.
روابط باز گشتي زير را حل کنيد.
tn = 4tn-1 n > 1
t1 = 3
tn = 2tn-1 + 3tn-2 n>1 n
T1= 1
T0 = 0
الگوريتم جستجوي سه سه ايي را به روش تقسيم و حل بنويسيد . در اين الگوريتم به جاي اينکه هر بار مجموعه داده ها را به دو زير مجموعه (تقريبا مساوي ) تقسيم کنيم به سه زير مجموعه ( تقريبا مساوي ) تقسيم مي کنيم. مرتبه زماني الگوريتم را محاسبه کنيد.
حل مسائل به روش تقسيم و غلبه در چه مواردي از کارايي مناسب برخوردار است؟
الگوريتمي براي حل مسئله فروشنده دورگرد به روش برنامه نويسي پويا بنويسيد . الگوريتم ارائه شده را تحليل کنيد .
يک درخت جستجوي دودويي بهينه براي عناصر زير تشکيل دهيد . احتمال وقوع هر يک از عناصر زير داخل پرانتز نوشته شده است.
V1(./5) , V2(./15) , V3(./05) , V4(./35) , V5(./05) , V1(./35)
مفهوم اصل بهينگي در الگوريتم هاي برنامه سازي پويا را شرح دهيد.
يک الگوريتم نسبي زمانبندي کارهاي مهلت دار به زمان سرويس متغيير به روش حريص ارائه نمائيد.
با استفاده از روش بازگشت به عقب الگوريتمي براي حل مسئله m رنگ ارائه نماييد. اين الگوريتم بايد تمامي راههاي که بتوان رئوس يک گراف بدون جهت را ، m رنگ پيدا کند.(با اين شرايط که هيچ دو راس مجاوري همرنگ نباشد )
-------------------------------------
نمونه سوالات سال 1385
BIG O و ? و? هر يک از توابع زير را محاسبه کنيد.
الف) T(n)=3T(n/4)+n
(ب T(n) = 4T (n/4)+n2log 2n
اگر در الگوريتم merge sort هر بار ليست به صورت 9 به 1 تقسيم شود (يعني يک قسمت به 9 برابر قسمت ديگر باشد ) و در مرحله ترکيب اين دو ليست با هم ادغام شوند آنگاه پيچيدگي اين الگوريتم چيست؟
الگوريتم ضرب اعداد صحيح بزرگ را به گونه ايي تغيير دهيد که عدد صحيح N رقمي را تقسيم کند به سه عدد صحيح کوچکتر ، هر يک با N/3 رقم ( فرض کنيد N=3k) مورد نظر را تحليل کنيد.
فرض کنيد N فايل با اندازه هاي L1,L2,L3,L4,..LN موجود است . اگر احتمال درخواست فايل K برابر Pk باشد، آنگاه يک روش حريص به چه ترتيبي بايد اين فايلها را ذخيره کند تا حداقل متوسط زمان دستيابي تضمين شود؟(فايلها قرار است بر روي نوار ذخيره شوند)
براي حل مسئله کوله پشتي 0-1 يک الگوريتم بازگشت به عقب بنويسيد.
--------------------------------------
نمونه سوالات سال 1385
1. الگوريتم جستجوي ترتيبي در يک ارايه را به روش بازگشتي بنويسيد و مرتبه زماني آن را محاسبه کنيد.
2. اگر يک ارايه وجود داشته باشد که از مولفه اول تا n آن نامرتب باشد و از مولفه N تا k آن مرتب باشد با فرض کوچک يا بزرگ بودن مقدار k بهترين روشهاي مرتب سازي از نظر سرعت کدامند.
3. الگوريتمي به روش تقسيم و غلبه از مرتبه زماني (O log 3n) براي جستجوي کليد X در آرايه مرتب شده A[1..N] ارائه دهيد.
4. زير برنامه زير براي يک تابع بازگشتي استفاده شده است .
Int pascal(int a,b)
{
If (( A = = 0) OR (B = = 0) ) Then
return 1
else
return pascal( A-1 , B) + pascal( A , B-1)
}
با استفاده از روش برنامه سازي پويا تابع فوق را به نحوي پياده سازي کنيد که زمان اجراي آن
?( MIN (A ,B)) گردد.
5. مسئله کوله پشتي جزئي را به روش حريص طراحي کنيد ( در مسئله کوله پشتي جزئي دزد مجبور نيست کل يک کالا را بردارد ). به کمک الگوريتم ارائه شده نمونه مسئله زير را حل کنيد .
(P1,P2,P3)=(25,24,15),W=20 , (W1,W2 , W3) = (18,15,10)
W وزن قابل تحمل کوله پشتي
6. با استفاده از الگوريتم الف) نشان دهيد راشل ب)پريم يک درخت پوشاي مينيمم براي گراف رو بدست آوريد.
7. يک درخت جستجوي دودويي بهينه براي عناصر زير تشکيل دهيد .( ماتريس A را کامل کنيد )
P1=./3 , P2= ./4 , P3 = ./2 , P4=./1
8. ابتدا الگوريتم M رنگ را به روش بازگشت به عقب پياده سازي کنيد سپس به کمک آن تمام رنگ آميزيهاي ممکن گراف زير ، با استفاده از سه رنگ قرمز و سبز و آبي را محاسبه کنيد . عمليات را مرحله به مرحله نشان دهيد.
قابل تحویل:
مهارت ها و تخصص های مورد نیاز
مهلت برای انجام
5روز
وضعیت مناقصه
بسته
درباره کارفرما
عضویت پانزده سال پیش
