matlabkhooneh

تمرینات درس ساختمان داده ها - پیچیدگی زمانی ( کد Das0001 )

1 - پیچیدگی زمانی قطعه کدهای زیر را با راه حل بدست آورید.

الف )

while (m!=n)
{
   if (m>n)
      m=m-n;
   else
     n=n-m;
}

ب )

for (i=1;i<=n;i=i*2)
{
   for (j=1;j<=n;j=j*2)
   {
      for (k=1;k<=j;++k)
      {
           System.out.println.("*");
      }
   }
}

ج )

for (i=1;i<=n;++i)
{
   for (j=1;j<=n;++j)
       x++;
   j=1;
   while (j<n)
      {
           x++;
           j=j*2;
      }
}

ت )

for (i=0;i*i<n;++i)
      System.out.println.("*");

2 - فرض کنید یک آرایه به طول n که شامل اعداد طبیعی است در اختیار دارید. الگوریتم مرتب سازی این آرایه به صورت زیر عمل می کند.

ابتدا کوچکترین عنصر را در آرایه پیدا می کند ، سپس index مقدار کوچکتر عوض می شود. این عمل را وقتی که آرایه مرتب شود تکرار می گردد.

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

3 - الگوریتم های زیر را توضیح دهید.

Quick Sort

Merge Sort

Insertion Sort

Selsction Sort

کدام یک از الگوریتم های بالا ، بهترین انتخاب برای مرتب سازی مقادیر بسیار زیادی از داده های نامرتب است؟ پیچیدگی زمانی آ را به صورت بازگشتی بدست آورید.

4 - نرخ رشد توابع زیر را از کمترین به بیشترین مرتب کنید.

\[ n!\;,\;nlg(n^5)\;,\;n^3\;,\;3^n\;,\;10^{lg\;n)}\;,\;(2n)^2\;,\;\sqrt{n}\;,\;\sqrt[4]{n}\]

5 - درستی یا نادرستی عبارات زیر را با ذکر دلیل بیان کنید.

\[ \begin{matrix}T(n)= 3n^2+3^n+n\;lg\;2\\T(n)= \theta (n^2) \\T(n)= \theta (3^n) \\T(n)= \Omega ((3^n)lg\;n) \\T(n)= O(n^3)\end{matrix}\]

6 - روابط بازگشتی زیر را حل کنید.

\[ \begin{matrix} T(n)=3T(\frac{n}{2})+n\\T(n)=2T(n-1)+\frac{n}{2}\end{matrix}\]

7 - روابط زیر را ثابت کنید.

\[ \begin{matrix} (2^n)=\Omega (n^2)\\3n^2+n=\theta (n^2)\end{matrix}\]

8 - رابطه بازگشتی کدهای زیر را نوشته و سپس آن را حل کنید.

الف )

public static void func(int n){
     if(n = = 1) return:
        for(int i=0 ; i<4 ; i++)
            func(n-1);
}

ب )

public static void func2(int n){
     if(n<=1) return:
         func2(n/2);
         func2(n/3);
         for(int i=0 ; i<n : i++)
            func3();
} // func3 = O(1)

9 - کدام یک از گزینه های زیر صحیح و کدام غلط است؟

  \[ \begin{matrix} n^3 log(n)=O(n^{3+\varepsilon })\;\;\;,\;\;\;\varepsilon >0\\\frac{n^2}{log(n)}=\Omega (n^2) \\ h(n)\in \Omega (g(n))\;\;,\;\; f(n) \in O(g(n))\;\;\Rightarrow \;\; f(n)\in \Theta(h(n))\\h(n)\in \Omega (g(n))\;\;,\;\; g(n) \in \Theta(h(n))\;\;\Rightarrow \;\; f(n)\in \Omega(h(n))\end{matrix}\]

10 -  به ازای k>1 و 0.5>epsilon کدام صحیح است؟

\[ \begin{matrix} k>1 \;\;\;,\;\;\; 0<\varepsilon <\frac{1}{2}\\ n^{\varepsilon }=O(\sqrt{n})=O(log(n!))=O((log(n))^k)\\ n^{\varepsilon }=O(\sqrt{n})=O((log(n))^k)=O(log(n!))\\O((log(n))^k)=n^{\varepsilon }=O(log(n!))=O(\sqrt{n})\\ O((log(n))^k)=n^{\varepsilon }=O(\sqrt{n})=O(log(n!))\end{matrix} \]

11 - آرایه A حاوی n بیت است. فرض کنید A یکی از دو گونه زیر است:

گونه 1 : نیمی از درایه های A حاوی بیت 0 و نیم دیگر حاوی بیت 1 بدون ترتیب خاصی است

گونه 2 : A در مجموع 2/3 صفر و 1/3 یک دارد.

به شما یک آراه مانند A داده شده است که با احتمال یک سان یا از نوع 1 و یا نوع 2 است. در بهترین حالت خداقل چند تا درایه باید بررسی شود تا گونهی آن با اطمینان مشخص شود؟

12 - مرتبه رابطه های زیر را بدست آورید؟

\[ \begin{matrix} T(n)=4\sqrt{n}T(\sqrt{n})+2n^2\\ T(n)=2T(\left \lfloor \sqrt{n}\right \rfloor) +log(n)\\S(n)=4S(\frac{\sqrt{n}}{3})+log^2 n\end{matrix}\]

13 - نرخ رشد توابع زیر را به ترتیب صعودی مرتب کنید؟

\[ (\frac{3}{2})^n\;\;,\;\; n^3\;\;,\;\;log^2 n\;\;,\;\;log(n!)\;\;,\;\;2^{2^n}\;\;,\;\;n^{\frac{1}{log(n)}}\]

14 - پیچیدگی قطعه کد زیر را بدست آورید؟

sum <-- 0
for i <-- 1 to n
    do for j<--1 to i^2
    if j mod i==0
        then for k<-- 1 to j do sum<-- sum+1

15 - در قطعه کد زیر تعداد مقایسه ( اجرای خط 6 ) بر حسب n چند است؟

i و j به ترتیب ابتدا و انتهای آرایه A

FindMax(A,i,j)
    n<--j-i+1
    if n==1 then return A[i]
    m1<-- FindMax(A,i,i+[n/2]-1)
    m2=FinaMax(A,i+[n/2],j)
    if m1<m2
    return m2
    else return m1

16 - در قطعه کد زیر ++x چندبار اجا می شود؟

for (i=3;i<=n;i=i*2)
    x++;

17 - زمان مصرفی قطعه کد زیر در چه حالتی بدترین و بهترین می باشد. مرتبه آن را بنویسید ( توضیح دهید )

for i<-- 2 to n do
    if k mod i==0 then
    for j<--1 to n do
         L<--L*k

18 - جستجوی دودویی را به صورت بازگشتی و غیربازگشتی نوشته و تابع زمانی آن ها را محاسبه نمایید. جهت تابع غیر بازگشتی پیچیدگی زمانی را هم محاسبه کنید.

19 - تابع محاسبه مجموع عناصر یک آرایه را محاسبه نمایید. جهت تابع غیربازگشتی پیچیدگی زمانی هم محاسبه کنید.

20 - خروجی تابع زیر به ازاء n=5 چند است؟ تابع زمانی آن را محاسبه کنید.

def f(n):
    if n<=0:
       return 1
    else:
       return f(n-1)+f(n//2)

21 - الگوریتم بازگشتی بنویسید که بزرگترین عنصر آرایه را برگرداند و پیچیدگی زمانی آن را محاسبه کند. (اول مساله را به صورت ریاضیاتی حل کنید یک راهکار ارائه دهید و با جزئیات بنویسید این می شود قسمت حل ریاضیاتی بعد با برنامه نویسی الگوریتمآن را می نویسید و بعد پیچیدگی زمانی آن را می نویسید.

22 - پیچیدگی زمانی الگوریتم مرتب سازی سریع را به صورت بازگشتی بنویسید و تحلیل کنید.( ابتدا خود الگوریتم رابازگشتی بنویسید و سپس تحلیل کنید.

23 - یک آرایه حداقل 10 عنصری به دلخواه بنویسید و مراحل اجرای الگوریتم تصادفی مرتب سازی سریع را بر روی آن نشان دهید

24 - یک گراف ساده با حداقل 10 راس به دلخواه رسم کنید و مراحل الگوریتم تصادفی محاسبه کات حداقل یا مینیمم را بر روی آن نشان دهید.

25 - برای مسئله هشت وزیر یک مرتبه الگوریتم مونت کارلو تخمین تعداد گره های فضای حالت هر شده را به صورت دستی اجرا کنید. جزئیات و نتیجه نهایی را بنویسید.

26 - برای مساله کوله پشتی دلخواهی که تعریف می کنید درخت فضای حالت را به صورت سطحی پیمایش و ترسیم کنید.

27 - برای مساله کوله پشتی دلخواه را به روش شاخه وحد به روش بهترین جستجو ترسیم وحل کنید.

28 - یک گراف پر با حداقل ده راس رسم کنید. مراحل الگوریتم حریصانه درخت پوشای کمینه را برای آن انجام دهید.

29 - مراحل اجرای الگوریتم دیکسترا بر روی گراف مسئله قبل بنویسید.

30 - الگوریتم کراسکال برای پیداکردن درخت پوشی کمینه را بر روی گراف قبل اجرا کنید.

31 - یک گراف نسبتا کامل بدون وزن با حداقل 8 راس رسم کنید و مراحل اجرای الگوریتم تقریبی پوشش رئوس را با جزئیات بنویسید

32 - یک گراف کامل وزن دار با حداقل شش راس رسم کنید مراحل اجرای الگوریتم تقریبی فروشنده دوره گرد را با جزئیات بنویسید.

33 - الگوریتم تقریبی Set Cover را مورد بررسی قرار داده و مثال هایی از آن را در پایتون کدویسی کنید.

34 -

35 -

36 -

37 -

38 -

39 -

40 -

41 -

42 -

43 -

44 -

45 -

46 -

47 -

48 -

49 -

50 -

| جهت سفارش پروژه ، تکلیف و آموزش ساختمان داده و طراحی الگوریتم ، مشاوره کنکور کارشناسی ارشد و دکتری کامپیوتر لطفا با متلب خونه تماس بگیرید، تا پس از بررسی هزینه خدمت شما اعلام گردد.

پشتیبانی ( تلفن ثابت دفتر متلب خونه ) : 02191307193  

تلگرام و ایتا :  09364847193

ارسال نظر آزاد است، اما اگر قبلا در بیان ثبت نام کرده اید می توانید ابتدا وارد شوید.
شما میتوانید از این تگهای html استفاده کنید:
<b> یا <strong>، <em> یا <i>، <u>، <strike> یا <s>، <sup>، <sub>، <blockquote>، <code>، <pre>، <hr>، <br>، <p>، <a href="" title="">، <span style="">، <div align="">
تجدید کد امنیتی
موضوعات
Designed By M A T L A B K H O O N E H