صفحه‌ها: ۱ ۲
سوال هشتم (*) {ادغام چندین سوال از ۶۰۰ سوال و کتاب نارنجی) سوال ۳۰/۱ و سوال ۴۱/۱ و سوال ۵ و ۷ از نارنجی
چه تعداد از عبارات زیر صحیح است ؟ {تشریح گزینه ها ضروریست}
۱)[tex]n\: !\: =\omega(2^n)[/tex]
۲)[tex]n\: !\: =o(n^n)[/tex]
۳)[tex]\log(n\: !)\: =\theta(n\: \log n)[/tex]
۴)[tex]n\: !=O(n^n)[/tex]
۵)[tex]3^{2^n}=\Omega(2^{3^n})[/tex]
۶)[tex]n^{2+\frac{1}{\sqrt{n}}}=O(n^2)[/tex]
۷)[tex]\sum^n_{i=1}i^k\log i=O(n^{k+1}\log^{k+1}n)[/tex]
۸)[tex]\sum^n_{i=1}\lceil\frac{1}{i}\rceil=O(n\: \log n)[/tex]
۱)۰
۲)۱
۳)۲
۴)۴
سوال نهم{سوال ۲۶ از کتاب نارنجی}
کدام عبارت صحیح است ؟
الف) [tex]\log^{\ast}(\log n)\in\omega(\log(\log^{\ast}n))[/tex]
ب ) اگر [tex]k.\ln k=\theta(n)[/tex] آن گاه [tex]k=\theta(\frac{n}{\ln n})[/tex]
پ ) [tex]\sqrt{n}\in\Omega(n^{\sin n})[/tex] یا [tex]\sqrt{n}\in O(n^{\sin n})[/tex]
۱)الف
۲)الف و پ
۳) الف و ب
۴)هر سه مورد
با ۶ تا ۱۰ سوال دیگر بخش اول به پایان میرسد، سوالات شامل ترتیب های رشد پیچیدگی تکه برنامه ها و مسائل استخراجی با ایده ی بازگشتی خواهد بود
پاسخ سوال نهم (سوال ۱-۲۶ از کتاب نارنجی پوران)
در مورد گزینه ی الف:
یه فرمولی هست که [tex]\log^{\ast}(\log n)=\log^{\ast}n\: -\: 1[/tex]
این فرمول از کجا اومده؟ [tex]\log^{\ast}[/tex] هر چیزی یعنی انقدر ازش لگاریتم بگیریم که به عددی کوچکتر از یک یا یک برسه، تعدادش میشه [tex]\log^{\ast}n[/tex] که معمولا برای اعداد خیلییی بزرگ هم بیشتر از ۶ نمیشه. حالا فرض کنیم که لگاریتم یه عدد رو داریم یعنی log n تا این جا یه مرحله رو انجام دادیم، حالا میایم از این log n، [tex]\log^{\ast}[/tex]ش رو حساب میکنیم، یعنی یه دونه از مراحل [tex]\log^{\ast}n[/tex] کمتر، که میشه [tex]\log^{\ast}n\: -1[/tex]. مثال می زنم.
n=16
[tex]\log16=3[/tex] یعنی باید یه بار لگاریتم بگیریم از ۱۶ که بشه ۴، بار دوم از ۴ لگاریتم بگیریم که بشه ۲ و بار سوم از ۲ لگاریتم بگیریم در مبنای ۲ که بشه ۱، سه بار لگاریتم گرفتیم تا برسیم به ۱، این سه تا میشه [tex]\log^{\ast}۱۶[/tex]
[tex]\log^{\ast}\log16=\log^{\ast}4=2[/tex]
حالا [tex]\log^{\ast}16=3[/tex]
خب پس این فرمول قابل درک هست:[tex]\log^{\ast}(\log n)=\log^{\ast}n\: -\: 1[/tex]
توی صورت سوال داریم که [tex]\log^{\ast}(\log n)\: \in\omega(\log(\log^{\ast}n))[/tex] حالا از اونجایی که [tex]\log^{\ast}(\log n)=\log^{\ast}n\: -\: 1[/tex] و این که می دونیم رشد [tex]\log(\log^{\ast}n)[/tex] از رشد [tex]\log^{\ast}n[/tex] کمتر هست پس این گزینه کاملا درسته.
گزینه ی دو:
فرض میکنیم تالی درست باشه، یعنی واقعا [tex]k=\theta(\frac{n}{\ln n})[/tex] خب پس به جای k توی عبارت [tex]k.\ln k[/tex]، معادلش رو مینویسیم.
[tex]k.\ln k=\frac{\: n}{\ln n}.\ln(\frac{n}{\ln n})[/tex]
می دونیم که [tex]\ln(\frac{x}{y})=\ln x-\ln y[/tex] پس عبارت بالا به صورت زیر میشه:
[tex]\frac{n}{\ln n}.\ln(\frac{n}{\ln n})=\frac{n}{\ln n}.(\ln n\: -\: \ln\: \ln n)=\frac{n.\ln n}{\ln n}-\frac{\: n}{\ln n}.\ln\ln n=n-\frac{n}{\ln n}.\ln\ln n=n.(1-\frac{\ln\ln n}{\ln n})[/tex]
که می دونیم رشد [tex]\frac{\ln\ln n}{\ln n}[/tex] از ۱ کمتر هست پس عبارت بالا میشه:
[tex]\theta(n)[/tex] که خب درسته.
پس این گزینه هم درسته.
گزینه ی سوم:
کلا وقتی می تونیم مرتبه ی بزرگی دو تا تابع رو با هم مقایسه کنیم که هر کدوم یا صعودی یا نزولی باشه، یه سری از توابع هستند که تناوبی هستند و توی یه بازه هایی صعودی هستند و یه بازه هایی نزولی بعد ممکنه نشه با بعضی از توابع مقایسه بشن.
توی این مثال: خب [tex]-1\: <\: \sin\: n\: <\: 1[/tex]
وقتی [tex]-1\: <\: \sin\: n\: <\: 0[/tex] اونوقت [tex]n^{\sin n}[/tex] معادل میشه با [tex]n^k\: \: (-1<k<0)[/tex] که یعنی توان n از یک کمتر هست، پس یعنی توی این بازه ی مشخص شده [tex]\sqrt[]{n}=omega(n^{\sin n})[/tex]
اما وقتی[tex]0\: <\: \sin\: n\: <\: 1[/tex] اونوقت [tex]n^{\sin n}[/tex] معادل میشه با [tex]n^k\: \: (0<k<1)[/tex] که یعنی توان n از یک بیشتر هست، پس یعنی توی این بازه ی مشخص شده [tex]\sqrt[]{n}=O(n^{\sin n})[/tex]
اگر شکل این دو تابع رو هم بکشیم متوجه میشیم توی یه بازه ای اولی بالای دومی هست و توی بازه ی بعدی بالعکس، پس نمیشه این دو تا رو مقایسه کرد و غلط هست سوال به کل.
پس گزینه ی سه درسته یعنی الف و ب درست هستند.
ضمن سپاس و در ادامه پاسخ کاربر Pure Liveliness :
۳)طبق قضیه ی استرلینگ داریم : [tex]\log(n!)\equiv n\: \log n[/tex] این هم ارزی در رشددرست بودن حالت سوم را نشان میدهد.
۴) تابع توضیحات عالی دوست عزیزمان این گزینه مانند حالت دوم قابل اثبات است
۵) باز هم به تبعیت از توضیحات کاربر Pure Liveliness :
میشود از طرفین رابطه لگاریتم گرفت : تا به حالت زیر برسیم :
[tex]2^n\log3\le3^n\log2[/tex] و نادرستی این گزینه نیز ثابت شود.
۶) میتوان گفت برای هر مقدار [tex]\epsilon[/tex] در توان افزایش قابل ملاحظه ای در پیچیدگی خواهیم داشت و در این مثال به ازای n0 که n>n0 باشد داریم : [tex]n^{2+\frac{1}{\sqrt{n}}}\ge n^2[/tex] که از مرتبه ی [tex]\Omega[/tex] خواهد بود.پس این گزینه نیز غلط است.
۷) در جستجوی پاسخ مناسب و ساده و کاربردی . . .(در حال تکمیل . . . )
پاسخ سوال هشتم (سوال ۱-۳۱ و ۱-۴۱ ۶۰۰ مساله ی دکتر قدسی و سوال ۵ و ۷ نارنجی پوران)
۱)[tex]n!=\omega(2^n)[/tex]
راه حل اول:
درست هست چون [tex]n!=n\times(n-1)\times(n-2)\times...\times3\times2\times1[/tex] که ضرب n عدد از ۱ تا n در هم هست.
[tex]2^n=\: 2\times2\times2\times....\times2[/tex] که ضرب n عدد ۲ در هم هست و مشخص هست که از ضرب ۱ تا n کمتر هست.
راه حل دوم:
لگاریتم میگیریم. [tex]\log_22^n=nlog_2^2=n[/tex] و [tex]\log_2n!=nlogn[/tex] که خب مشخص هست که nlogn از n بزرگتر هست.
۲)[tex]n!\: =\: O(n^n)[/tex]
درست هست چون طبق ۱ n! از ضرب ۱ تا n به دست میاد و [tex]n^n[/tex] از ضرب n تا n
با گرفتن log هم به همین نتیجه خواهیم رسید. گرچه همیشه این روش جواب نمیده. یعنی مثلا n با توان های مختلف رو اگه ازش log بگیریم، حاصل log هم مرتبه است ولی رشد به ازای توان های مختلف فرق داره.
۷)[tex]\sum^n_{i=1}i^k.\log k\: \in O(n^{k+1}.\log^{k+1}n)[/tex]
[tex]\sum_{i=1}^ni^k.\log i=1^k.\log1+2^k.\log2+3^k.\log3+....+n^k.\log n[/tex]
این سری تک تک جملاتش از [tex]n^k.\log n[/tex] کوچیکتر هست، از طرفی n تا جمله داریم از i=1 تا n
[tex]\sum^n_{i=1}i^k.\log k\: =1^k.\log1+....+n^k.\log n\: \le n.n^k.\log n\le n^{k+1}.\log^{k+1}n[/tex] که خب اثبات شد که [tex]\sum^n_{i=1}i^k.\log k\: \in O(n^{k+1}.\log^{k+1}n)[/tex]
۸)[tex]\sum^n_{i=1}floor(\frac{1}{i})=\theta(n)[/tex]
[tex]\sum^n_{i=1}ceil(\frac{1}{i})=ceil(\frac{1}{1})+ceil(\frac{1}{2})+ceil(\frac{1}{3})+…+ceil(\frac{1}{n})=1+1+1+...+1=n=\theta(n)[/tex]
چون علامت سقف رو پیدا نکردم نوشتم ceil
نکته: اگر علامت براکت نبود اوضاع فرق داشت، همیشه نمیشه از براکت توی مرتبه زمانی ها چشم پوشی کرد. می دونیم: [tex]\sum^n_{i=1}\frac{1}{i}=\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{n}=\ln n=\theta(\log n)[/tex]
پاسخ سوال ۴ )
این سوال با روش های مختلفی قابل حل است . اما روشی که شهود بیشتری میدهد روش درختی ست .
می دانیم برای n های بزرگتر از یک سرعت به مقدار ثابت رسیدن [tex]T(\sqrt{n})[/tex] در برابر [tex]T(\frac{n}{2})[/tex]
بسیار بیشتر میباشد .
مثلا برای n=1000 داریم :
[tex]T(\frac{n}{2})=T(\frac{1000}{2})=500,250,125,62.5,31.25,15.125,7.5,3.75,1.75[/tex]
[tex]T(\sqrt{n})=T(\sqrt{1000})=31.62,5.62,2.37,1.53[/tex]
در نتیجه ارتفاع درخت را [tex]T(\frac{n}{2})[/tex]
مشخص میکند که طول بیشتری دارد .
پس می توان در این رابطه از [tex]T(\sqrt{n})[/tex] صرف نظر کرد:
[tex]T(n)=T(\frac{n}{2})+n[/tex]
که با توجه به قضیه مستر مرتبه این رابطه [tex]\theta(n)[/tex] می باشد.[/align][/size]
سوال دهم (۳۰ کتاب نارنجی و ۵۱/۱ از ۶۰۰ سوال)
زمان اجرای رویه ی زیر چقدر است(بهترین گزینه را انتخاب کنید) :
کد:
ISPRME(N)
I=3
IF(N==2 or N==3)
then return true
if(n mod 2 ==0)
then return false
while (i^2 <=N)
do if (N mod i==0)
then return false
else i = i+2
return true۱) [tex]O(\log N)[/tex]
۲)[tex]\theta(\log N)[/tex]
۳)[tex]O(\sqrt{n})[/tex]
۴)[tex]\theta(\sqrt{n})[/tex]
سوال یازدهم (۵۹/۱از ۶۰۰ سوال و ارشد ۹۱)
هزینه ی زمانی تکه برنامه ی روبه رو کدام است؟ (دقت شود که مقادیر i/2 و j/3 به صورت کفِ مقادیر میباشند)
کد:
i=n
while i > 1
do i =i/2
i=j
while j>1 do j=j/3۱)[tex]O(\log^2n)[/tex]
۲)[tex]O(\log n)[/tex]
۳)[tex]O(n)[/tex]
۴) [tex]O(n^2)[/tex]
سوال دوازدهم(*)(۶۳/۱ از ۶۰۰ سوال)
آرایه A به طول n داده شده است که تمام درایه های آن در ابتدا صفر هستند.عمل درج روبه رو را n بار با مقادیر دلخواه x انجام میدهیم هزینه ی سرشکن شده ی هر عمل درج کدام است؟بهترین گزینه را انتخاب کنید
کد:
INSERT (X)
n=n+1 , t=x
[for i = 0 to [log n
do if A[i] <> 0
then t=t+A[i]
A[i] =0
else A[i] =t
returnپاسخ سوال دهم
برای شرط [tex]i^2\le\: N[/tex] میتوان گفت که چون i با سرعت بیشتری به N می رسد پس از مرتبه ی N نخواهد بود(در کتاب ۶۰۰ گزینه ها متفاوت از کتاب نارنجی هستند و مرتبه ی [tex]O(N)[/tex] نیز مطرح است ) یا میتوان گفت از طرفین رابطه [tex]i^2\le\: N[/tex] رادیکال میگیریم و البته با در نظر گرفتن این موضوع که i هر بار ۲ واحد اضافه میشود. که به دست می آید :
[tex]\frac{\sqrt{N}}{2}[/tex]
بنابراین مرتبه ی کد : [tex]O(\sqrt{N})[/tex] است.
پاسخ سوال یازدهم
حلقه ی بیرونی [tex]\log n[/tex] بار تکرار میشود و حلقه ی درونی [tex]\log i[/tex] چون در حلقه ی درونی i را داخل j قرار میدهیم.
سوال سیزدهم(*) سوال ۷۸-۱ از ۶۰۰
چند تا از گزاره های زیر درست است؟[
۱) تفاوت زمان اجرای هر الگوریتم قطعی در بدترین حالت و حالت میانگین تنها در ضریب ثابتشان است
۲)تابع های [tex]f(n)[/tex] و [tex]g(n)[/tex] وجود دارند به طوری که [tex]f(n)=O(g(n))[/tex] و [tex]f(n)=\omega(g(n))[/tex]
۳) اگر [tex]f(n)=\sqrt{n}[/tex] و [tex]g(n)=n.(n\: \mod\: 100)[/tex] در آن صورت [tex]f(n)=O(g(n))[/tex]
۱)۰
۲)۱
۳)۲
۴)۳
سوال چهاردهم (سوال ۱۳ فصل اول کتاب نارنجی)
فرض کنید آرایه [tex]A[1...n]\: [/tex] یا همه ی عناصرش صفر است یا [tex]\frac{n}{2}[/tex] صفر و [tex]\frac{n}{2}[/tex] یک، اگر بخواهیم با احتمال حداقل [tex]\frac{3}{4}[/tex] مشخص کنیم آرایه A کدام نوع است . باید چند درایه از A بخوانیم و بررسی کنیم؟
۱)[tex]\frac{n}{2}+1[/tex]
۲)[tex]\frac{n}{4}+1[/tex]
۳)۲
۴)۴
سوال چهاردهم پایان مبحث فصل اول(روابط بازگشتی)
در ادامه ی سوالات دو بخش مرتب سازی و تقسیم و غلبه و مرتبه های اماری به دلیل نزدیکی و تداخل مباحث با هم مورد بررسی دقیق قرار میگیرد،برای مرتب سازی هایی که از درخت استفاده میشود سعی بر آن است که مباحث مقدماتی لازم به کلی توضیح داده شود
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
پاسخ سوال سیزدهم
گزاره ی اول نادرست است ، چون الگوریتم مرتب سازی سریع یک مثال نقض مناسب برای آن است.
زمان اجرای این الگوریتم در بدترین حالت [tex]O(n^2)[/tex] و در حالت میانگین [tex]O(nlogn)[/tex] است.
نکته : در مرتب سازی سریع اگر لیست از قبل مرتب باشد یا به صورت معکوس مرتب باشد داریم : [tex]\theta(n^2)[/tex] چرا که در این دو حالت در هر فراخوانی از روال partition یک زیر لیست با [tex]Q(n-1)[/tex] و دیگری با [tex]Q(0)[/tex] (یک لیست تهی) فراخوانی میشود که در کل مرتبه ی زمانی برابر است با :
[tex]Q(n)=Q(n-1)+Q(0)+n-1[/tex] دقت کنید که n-1 از نتیجه ی مقایسه عنصور محوری با کل عناصر است. مرتبه ی این حالت در کل : [tex]\theta(n^2)[/tex] است.
مرتب سازی سریع در حالت میانگین و بهترین حالت از مرتبه ی [tex]\theta(nlogn)[/tex] است که در نتیجه ی حالتی است که عنصر میانه را در وسط لیست بگیریم که رابطه ی بازگشتی تقریبی زیر با مرتبه ی ذکر شده به دست آید.
[tex]Q(n)\simeq Q(\frac{n}{2})+Q(\frac{n}{2})+n-1[/tex]
(در حال تکمیل . . .)