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
