1 - در این مسئله هدف نوشتن کد Naive Bayes در یک مسئله تصمیم گیری باینری است. داده مورد استفاده ( فایل ارسالی votr.txt ) دارای 325 مثال است که هرکدام شامل 16 مشخصه و یک خروجی ( همگی باینری ) می باشد. این داده نمایش دهنده رای آری ( یک منطقی ) یا نه ( صفر منطقی ) نمایندگان کنگره آمریکا به 16 طرح مختلف می باشد. این طرح ها به ترتیب عبارتند از :

• HANDICAPPED-INFANTS
• WATER-PROJECT-COST-SHARING
• ADOPTION-OF-THE-BUDGET-RESOLUTION
• PHYSICIAN-FEE-FREEZE
• EL-SALVADOR-AID
• RELIGIOUS-GROUPS-IN-SCHOOLS
• ANTI-SATELLITE-TEST-BAN
• AID-TO-NICARAGUAN-CONTRAS
• MX-MISSILE
• IMMIGRATION
• SYNFUELS-CORPORATION-CUTBACK
• EDUCATION-SPENDING
• SUPERFUND-RIGHT-TO-SUE
• CRIME
• DUTY-FREE-EXPORTS
• EXPORT-ADMINISTRATION-ACT-SOUTH-AFRICA

ستون هفدهم داده ارسالی نیز نشان دهنده دموکرات ( یک منطقی ) یا جمهوری خواه ( صفر منطقی ) بودن نماینده مورد نظر است. داده ارسالی را به 5 بخش مساوی تقسیم کنید ( بخش اول 65 سطر اول ، بخش دوم 65 سطر دوم و ... ) و با استفاده از Cross-Validation  میزان خطای الگوریتم Naive Bayes در دسته بندی را محاسبه نمایید. مشخص کنید وزن و تمایل هر یک از 16 مشخصه در دسته بندی چیست؟

2 - استفاده از نزدیکترین همسایه برای یادگیری

در این مسئله هدف استفاده از برنامه نویسی نزدیک ترین همسایه در دسته بندی بیماری غده تیروئید است. داده مورد استفاده دارای 100 مثال است که هر کدام شامل 7 مشخصه و یک خروجی می باشد. خروجی می تواند یکی از مقادیر 0 ( معادل عدم تشخیص بیماری ) یا 1 ، 2 یا 3 ( تشخیص بیماری با یکی از سه کلاس مختلف ) باشد. مشخصه ها نیز به ترتیب عبارتند از

• AGE
• ON THYROXINE
• TSH MEASURED
• TSH
• T3
• TT4 MEASURED
• TT4

که مشخصه های 2 ، 3 و 6 باینری و باقی مشخصه ها حقیقی هستند.

داده مورد نظر را به 5 بخش مساوی تقسیم کنید و با استفاده از Cross-Validation اثر تغییر k ( از مقادیر 1 تا 10 ) را بر روی متوسط خطای دسته بندی در الگوریتم k-Nearest Neighbor محاسبه نمایید. نمودار خطای متوسط بر حسب k را ترسیم نمایید. کمترین میزان خطا به ازای چه مقداری از k بست می آید.

این کار را در دو حالت انجام دهید : 1 - حالتی که داده غیرنرمالیزه وارد الگوریتم می گردد و 2 - حالتی که داده به گونه ای نرمالیزه می شود که میانگین هر یک از مشخصه ها صفر و واریانس آن ها واحد می گردد.

3 -

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

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

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

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 - روابط زیر را ثابت کنید.

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 کدام صحیح است؟

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 - نرخ رشد توابع زیر را به ترتیب صعودی مرتب کنید؟

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)

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

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

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