بخشی از پاورپوینت
--- پاورپوینت شامل تصاویر میباشد ----
اسلاید 1 :
دنباله ای از 2n عمل بر روی داده ساختاری انجام می شود. هزینه عمل iام برابر i است. اگر i توانی از 2 باشد ، وگرنه برابر 1 است. میانگین هزینه یک عمل دلخواه (یعنی مجموع هزینه ها تقسیم بر تعدادشان) به کدام گزینه نزدیک تر است؟
1)2
2)n
3)3
4)2n
اسلاید 2 :
درخت فراگیر گلوگاه(د.ف.گلوگاه) T در یک گراف بدون جهت و وزن دار G یک درخت فراگیر (د.ف) است که وزن سنگین ترین یال آن نسبت به هر درخت فراگیر ( نه لزوما کمینه) دیگر کمینه باشد. می گوییم که مقدار یک درخت فراگیر گلوگاه ، وزن سنگین ترین یال آن درخت است. می دانیم که درخت فراگیر کمینه (د.ف.کمینه) و درخت فراگیر بیشینه (د.ف.بیشینه) به ترتیب درخت فراگیر با کمترین و بیشترین وزن (مجموعه وزن یالهای آن) ممکن هستند. کدامیک از گزینه های زیر درست است؟
1)هر د.ف.گلوگاه یک د.ف.کمینه است. 2) هر د.ف.کمینه یک د.ف.گلوگاه هم هست.
3) هر د.ف.بیشینه یک د.ف.گلوگاه است. 4) هر د.ف.گلوگاه یک د.ف.بیشینه است.
اسلاید 3 :
درخت فراگیر گلوگاه(د.ف.گلوگاه) T در یک گراف بدون جهت و وزن دار G یک درخت فراگیر (د.ف) است که وزن سنگین ترین یال آن نسبت به هر درخت فراگیر ( نه لزوما کمینه) دیگر کمینه باشد. می گوییم که مقدار یک درخت فراگیر گلوگاه ، وزن سنگین ترین یال آن درخت است. می دانیم که درخت فراگیر کمینه (د.ف.کمینه) و درخت فراگیر بیشینه (د.ف.بیشینه) به ترتیب درخت فراگیر با کمترین و بیشترین وزن (مجموعه وزن یالهای آن) ممکن هستند. کدامیک از گزینه های زیر درست است؟
1)هر د.ف.گلوگاه یک د.ف.کمینه است. 2) هر د.ف.کمینه یک د.ف.گلوگاه هم هست.
3) هر د.ف.بیشینه یک د.ف.گلوگاه است. 4) هر د.ف.گلوگاه یک د.ف.بیشینه است.
اسلاید 4 :
گزینه 2 صحیح است.
یک درخت پوشای گلوگاه از گراف غیر جهت دار G یک درخت پوشا است که یال با بیشترین وزنش ، در بین همه درخت های پوشای G مینیمم می باشد. می گوییم که مقدار یک درخت پوشای گلوگاه، وزن یالی است که بیشترین وزن را دارد.
اسلاید 5 :
یک گراف جهت دار G=(V,E) نشان دهنده یک شبکه کامپیوتری با n راس است که وزن هر یال (u,v) برابر احتمال خرابی(قطع کامل) آن یال است که با p(u,v) نشان می دهیم و داریم 0≤p(u,v)≤1 می خواهیم در این گراف احتمال خرابی قابل اعتمادترین مسیر از هر راس i به یک راس jرا پیدا کنیم. این مسیری است که احتمال خرابی آن کمینه است. فرض کنید که احتمال خرابی یالها مستقل از هم هستند. می خواهیم از الگوریتم Floyd برای حل این مساله به صورت زیر استفاده کنیم.
اسلاید 6 :
اگرPij احتمال خرابی یک مسیر بین دو راس i و j با کمترین احتمال خرابی باشد چه عبارتی در سطر (a) قرار دهیم تا الگوریتم کا کند؟
1) Pij=min { Pij , max{Pik , Pkj}}
2) Pij=min { Pij , min{Pik , Pkj}}
3) Pij=min { Pij , (Pik + Pkj)}
4) Pij=min { Pij , Pik * Pkj}
اسلاید 7 :
گزینه 4 صحیح است.
مسیر i به j باید بررسی شود که از راس k عبور کند بهتر است یا نکند. احتمال خرابی مسیر i به j اگر از k عبور کند برابر Pik* Pkj است (احتمال ها مستقل هستند پس ضرب می شوند)، از بین این دو مقدار مینیمم باید انتخاب شود.
اسلاید 8 :
یک ماتریس A به اندازه n*n را در نظر بگیرید که همه عناصر سطرهای از چپ به راست و همه ستون های آن از بالا به پایین به صورت غیر نزولی مرتب هستند. می خواهیم با مقایسه عناصر این ماتریس با x ، در صورت وجود مکان x را در ماتریس بیابیم. با حداکثر چند تا مقایسه می توان این کار را انجام داد؟
1)2n
2) n2
3)3n
4)n log n
اسلاید 9 :
فرض کنید G یک گراف بدون جهت باشد که هیچ دو یال آن دارای وزن یکسان نیستند کدام گزینه در مورد گراف G درست است؟ (دومین زیر درخت فراگیر مینیمم G ، یکی از زیر درخت های فراگیر G است که فقط وزن زیردرخت مینیمم از وزن آن کمتر باشد).
1)زیر درخت فراگیر مینیمم و دومین زیر درخت فراگیر مینیمم، هیچ یک لزوما یکتا نیستند.
2)زیر درخت فراگیر مینیمم و دومین زیر درخت فراگیر مینیمم هر دو یکتا هستند.
3)زیر درخت فراگیر مینیمم لزوما یکتا نیست، اما دومین زیر درخت فراگیر مینیمم، یکتا است.
4)زیر درخت فراگیر مینیمم یکتا است، اما دومین زیر درخت فراگیر مینیمم لزوما یکتا نیست.
اسلاید 10 :
فرض کنید n عدد صحیح داریم که تعداد تکرار آنها بسیار زیاد است به طوری که حداکثر O(log n) عدد متفاوت در میان این اعداد وجود دارد. با توجه به این شرایط، بهترین الگوریتم مرتب سازی مبتنی بر مقایسه که می توان برای این اعداد در نظر گرفت دارای چه هزینه ای است؟
1)Ѳ(n log n) می توان الگوریتمی را یافت.
2) Ѳ(n)می توان پیدا کرد.
3) Ѳ(n log log n)میتوان پیدا کرد.
4)با توجه به آنکه اثبات شده است که هیچ الگوریتمی مبتنی بر مقایسه کمتر از Ѳ(n log n) را نمی توان پیدا کرد، عملا در این مورد نیز هزینه Ѳ(n log n) است.
