انجمنصفحه اولجستجوی انجمن

[Farid_Feyzi]

سلام
در این پست قصد دارم پاسخ تشریحی سوالات درس طراحی الگوریتم مربوط به آزمون دکتری ۹۲ رو قرار بدم.
از دوستانی که تو آزمون شرکت کرده بودن و یا دوستانی که امسال میخوان شرکت کنن، دعوت میشه که مشارکت داشته باشن و نظراتشونو راجع به سوالات بیان کنن.
مرسی

سوالات رو از اینجا دانلود کنید :

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

---

********************************************************************************​***********************

۳۱- گزینه ۲ صحیح است.
گزاره الف صحیح است زیرابا استفاده از الگوریتم زیر می توان زیردنباله مذکور را بدست آورد. بدیهی است که تعداد گامهای اجرای حلقه for برابر n بوده و هر گام در زمان [tex]O(1)[/tex] انجام می شود، بنابراین زمان اجرای کلی الگوریتم برابر [tex]O(n)[/tex]
است.



توضیح الگوریتم: در این الگوریتم اندیس های ابتدا و انتهای زیر دنباله ی جاری به ترتیب در seq_start و seq_end ذخیره می شوند و متغیرهای max_sec_start و نیز max_sec_end به ترتیب اندیس های ابتدا و انتهای زیر دنباله ای هستند که حاصلضرب عناصر آن ماکزیمم است. حاصلضرب عناصر زیردنباله جاری در متغیر this_prod ذخیره می شود و max_prod بزرگترین حاصلضرب زیردنباله های مشاهده شده را در خود نگه می دارد.

گزاره ب صحیح نیست.

---

********************************************************************************​***********************

۳۲- گزینه‌ی ۱ صحیح می‌باشد.

مسئله‌ی A بیانی دیگر از مسئله‌ی فروشنده‌ی دوره‌گرد می‌باشد، می‌دانیم که این مسئله ان‌پی-سخت می‌باشد.
مسئله‌ی B حالت تصمیم‌گیری مسئله‌ی فروشنده‌ی دوره‌گرد بوده و مسئله‌ای ان‌پی-کامل می‌باشد.

مسئله‌ی A را به دو صورت می‌توان توسط مسئله‌ی B حل نمود:

۱-با محاسبه‌ی جایگشت رئوس و وزن دور مربوطه و بررسی آن توسط ماشینی که مسئله‌ی B را حل می‌کند.

۲-با انجام جستجو در میان اعداد [M-0]، این روش ممکن است بسیار به پاسخ نزدیک شود ولی با توجه به حقیقی بودن وزن‌ها ممکن است هرگز به جواب نرسد.

گزینه‌ی ۴ نادرست می‌باشد، زیرا گرچه به کمک ماشین مربوطه نمی‌توان مسئله‌ی A را در زمان چندجمله‌ای حل نمود، ولی این امر توسط روش ۱ در زمان [tex]O(n!)[/tex] ممکن می‌باشد.‌

گزینه‌های ۲و۳ نیز با توجه به ان‌پی سخت بودن مسئله‌ی A امکان پذیر نمی‌باشند.

گرچه گزینه‌ی ۱ نیز چندان صحیح نیست ولی بهترین گزینه‌ی ممکن می‌باشد، زیرا در صورت استفاده از روش ۲ تعداد حالات پیش رو ناشمارا می‌باشد.

---

********************************************************************************​***********************

۳۳- گزینه‌ی ۲ صحیح می‌باشد.
یک روش برای حل این مسئله در زمان خطی با استفاده از روش حریصانه و به صورت زیر می‌باشد:

در ابتدا قبل از اجرای الگوریتم در زمان [tex]O(V E)[/tex] لیستی L از برگ‌های درخت را تهیه نموده و بیت مربوط به انتخاب آن‌ها را صفر می‌نماییم.
حال با داشتن لیست برگ‌های موجود در درخت به صورت زیر عمل می‌نماییم:

while L is not empty
f ← remove first leaf from L
if mark[f]==FALSE and parent[f]==NIL
mark[f]=TRUE
else if mark[f]==FALSE and parent[f]≠NIL
mark[parent[f]]=TRUE
remove f from T
if parent[f]≠NIL and parent[f]≠root[T] and children[parent[f]]==NIL
append parent[f] to L


البته برای حل این مسئله می‌توان از الگوریتم خطی برنامه‌نویسی پویا برای محاسبه‌ی پوشش رأسی نیز استفاده نمود.

---

********************************************************************************​***********************

ادامه دارد...

[Farid_Feyzi]

۳۴- گزینه ۱ درست است.
با استفاده از مثال نقض زیر می توان نشان داد که هیچ یک از گزاره های ۱ و ۲ صحیح نیستند. گراف زیر را در نظر بگیرد. در این گراف کوتاهترین مسیر از گره ۱ به گره ۳ از گره ۲ رد می شود و طول آن برابر ۳- است.



با اجرای الگوریتم WEIGHTS گراف در دو مرحله به صورت زیر تبدیل می شود در این گراف طول کوتاهترین مسیر از گره ۱ به گره ۳ برابر صفر است و این مسیر از هیچ گره میانی ای رد نمی شود.

---

********************************************************************************​​***********************

۳۵-گزینه‌ی ۱ صحیح می‌باشد.
این مسئله را همانند مسئله‌ی طولانی‌ترین زیردنباله‌ی مشترک می‌توان توسط برنامه‌نویسی پویا و در زمان [tex]O(nm)[/tex]
محاسبه نمود.
قدم اول: بازای هر [tex]0\leq i \leq n[/tex] و [tex]0\leq j \leq m[/tex] ، فرض کنیم که [tex]X_{i}[/tex] بیانگر دنباله‌ی [tex]x_{1}... x_{i}[/tex] و [tex]Y_{j}[/tex] بیانگر دنباله‌ی [tex]y_{1}... y_{j}[/tex] باشد. لذا [tex]Y_{m}=Y , X_{n}=X[/tex] می‌باشد. عنصر [tex](0\leq i\leq n , 0\leq j\leq m) S[i,j][/tex] از ماتریس S را به عنوان طول کوتاه‌ترین ابردنباله‌ی، دنباله‌ی [tex]X_{i}[/tex] و [tex]Y_{j}[/tex] در نظر می‌گیریم. در نهایت پس از اتمام الگوریتم [tex]S[n,m][/tex] بیانگر طول کوتاه‌ترین ابردنباله‌ی دنباله‌های X و Y خواهد بود.
قدم دوم: بطور واضح کوتاه‌ترین ابردنباله‌ی مشترک یک دنباله‌ی s با هر دنباله‌ی خالی خود دنباله‌ی s خواهد بود. بنابراین بازای تمام مقادیر [tex]0\leq i \leq n[/tex] و [tex]0\leq j \leq m[/tex] خواهیم داشت: [tex]S[i,0]=i[/tex] و [tex]S[0,j]=j[/tex] .
حال برای هر مرحله از برنامه‌نویسی پویا داریم:
۱- اگر [tex]x_{i}=y_{j}[/tex] باشد، آنگاه می‌توان آن‌ها را با یک عنصر یکسان مشترک جایگزین نمود. به عبارتی افزودن [tex]x_{i}[/tex] به SCS دنباله‌های [tex]X_{i-1}[/tex] و [tex]Y_{j-1}[/tex] ، کوتاه‌ترین ابردنباله‌ی مشترک [tex]X_{i}[/tex] و [tex]Y_{j}[/tex] را می‌سازد که دارای طول [tex]S[i-1,j-1] 1[/tex] می‌باشد.
۲- اگر [tex]x_{i}\neq y_{j}[/tex] باشد، آنگاه یا باید [tex]x_{i}[/tex]را به SCS دنباله‌ی [tex]X_{i-1}[/tex] و [tex]Y_{j}[/tex] بیافزاییم و یا باید [tex]y_{j}[/tex] را به SCS دنباله‌های [tex]X_{i}[/tex] و [tex]Y_{j-1}[/tex] بیافزاییم. کمینه‌ی این دو حالت جواب مسئله می‌باشد
لذا رابطه‌ی بازگشتی به صورت زیر می‌باشد:
[tex]S[i,j]=min\left\{\begin{matrix} S[i-1,j] 1 & \\ S[i,j-1] 1 & \\ S[i-1,j-1] 1 & x_{i}=y_{j} \end{matrix}\right.[/tex]

---

********************************************************************************​​​***********************

۳۶- گزینه ۱ صحیح است.
مسئله اول به مسئله خوشه (Clique) معروف بوده و جز مسائل ان پی است که بهترین الگوریتم موجود برای حل آن از مرتبه [tex]n^{o(n)}[/tex] است.

مسئله دوم در واقع مسئله کوله پشتی صفر و یک است. این مسئله ان پی تمام است و بهترین الگوریتمی که تا به حال پیدا شده و آن را حل می کند نمایی است.

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

مسئله چهارم نیز در واقع مسئله تصمیم هامیلوتی بودن یگ گراف است که این مسئله نیز یک مسئله ان پی بوده و بهترین الگوریتم موجود برای حل آن از مرتبه [tex]O(n2^{n})[/tex] است.

---

********************************************************************************​​​​***********************

۳۷-گزینه ۲ صحیح است.
این مسئله با استفاده از روش برنامه نویسی پویا برای ضرب زنجیری ماتریس ها قابل حل است اما از آنجا که این راه حل طولانی است بهتر است از نکته زیر برای حل این گونه سئوالات استفاده شود.

نکته: سعی کنید ابتدا [tex]A_{i}\times A_{i 1}[/tex] هایی را انجام دهید که [tex]d_{i 1}[/tex] (بعد دوم ماتریس اول) بزرگتر،و [tex]d_{i}[/tex] و [tex]d_{i 1}[/tex] کوچکتر باشند.
در این مسئله ابتدا [tex]A_{2}\times A_{3}[/tex] انجام می شود و ماتریس X با ابعاد [tex]40 \times 5[/tex] حاصل می شود. تعداد ضرب ها در این مرحله برابر [tex]40 \times 20 \times 5 =4000[/tex] است. بعد از این مرحله مسئله تبدیل می شود به محاسبه کمینه حاصلضربهای [tex]A_{1} \times X \times A_{4} \times A_{5}[/tex] .
در گام ۲، [tex]A_{1} \times X[/tex] را انجام می دهیم که ماتریس Y با ابعاد [tex]30 \times 5[/tex] حاصل می شود. تعداد ضرب ها در این مرحله برابر [tex]30 \times 40 \times 5=6000[/tex] است. بعد از این مرحله مسئله تبدیل می شود به محاسبه کمینه حاصلضربهای [tex]Y \times A_{4} \times A_{5}[/tex] .
در گام ۳، [tex]A_{4} \times A_{5}[/tex] را انجام می دهیم که ماتریس Z با ابعاد [tex]5 \times 20[/tex] حاصل می شود. تعداد ضرب ها در این مرحله برابر [tex]5 \times 10\times 20=1000[/tex] است. بعد از این مرحله مسئله تبدیل می شود به محاسبه کمینه حاصلضربهای [tex]Y \times Z[/tex] .
در گام ۴، [tex]Y \times Z[/tex] انجام می شود که تعداد اعمال ضرب برای محاسبه آن برابر است با [tex]30 \times 5\times 20=3000[/tex] .
بنابراین تعداد کل ضرب های لازم برابر است با: ۱۴۰۰۰

---

********************************************************************************​​​​***********************

۳۸- گزینه ۴ صحیح است.
برای تشخیص اویلری بودن یک گراف می توان از قضیه زیر استفاده کرد:

قضیه: یک گراف اویلری است اگر و تنها اگر همبند بوده و درجه تمامی رئوس آن زوج باشد.
از آنجا که تشخیص همبند بودن یک گراف، و همچنین تشخیص اینکه درجه تمامی رئوس زوج است یا خیر هر دو در زمان چندجمله ای قابل انجام هستند بنابراین تشخیص اویلری بودن یک گراف جز مسائل پی (P) بوده و چون هر مسئله P در NP نیز هست، پس یک مسئله NP میباشد. با توجه به این مطلب بدیهی است که تشخیص اویلری نبودن یک گراف نیز در زمان چندجلمه ای قابل تشخیص بوده و این مسئله نیز جز مسائل P و در نتیجه NP است.
تشخیص همیلتنی بودن یک گراف جز مسائل ان پی کامل(NP-C) است زیرا می توان آن را در زمان چندجمله ای به مسئله فروشنده دوره گرد (TSP) کاهش داد و مسئله TSP نیز NP-C است. تشخیص همیلتونی نبودن یک گراف نیز جز مسائل ان پی است.

[Farid_Feyzi]

۳۹- گزینه ۳ صحیح است.

گزاره۱ نادرست است. زیرا اگر چه B میتواند در [tex]O(nlogn)[/tex] حل شود، اما ممکن است زمان کاهش نمونه A به B بیشتر باشد.

گزاره۲درست است.
برای حل این این قسمت به دو قضیه زیر توجه کنید:
قضیه ۱: اگر [tex]A\prec_{p} B[/tex] و B در زمان چندجمله ای قابل حل باشد ( B در زمان چندجمله ای قابل حل است- B عضو P است) آنگاه A نیز در زمان چندجمله ای قابل حل است.
قضیه ۲: اگر یک مسئله مانند A که A یک مسئله NP کامل است، پیدا شود که در زمان چندجمله ای قابل حل باشد ( A عضو P باشد) آنگاه P=NP (یعنی همه مسائل NP در زمان چندجمله ای قابل حل خواهند بود).

در این گزاره چون B در زمان چندجمله ای قابل حل است بنابر قضیه ۱ داریم A عضو P است و بنابر قضیه ۲ اگر A عضو NP کامل باشد، آنگاه P=NP خواهد بود.

---

********************************************************************************​​​​​***********************

۴۰- گزینه‌ی ۲ صحیح می‌باشد.

برای حل مسئله کافیست تا ابعاد هر دو جعبه را به صورت صعودی مرتب نموده و کوچک بودن هر درایه‌ی جعبه‌ی x از درایه‌ی متناظر جعبه‌ی y را بررسی نماییم. درصورتی که بازای درایه‌ای [tex]x_{i}>y_{i}[/tex] باشد، آنگاه هیچ جایگشتی وجود ندارد که شرط مسئله را برآورده کند. زیرا [tex]x_{j}[/tex] وجود ندارد که بتوان [tex]x_{i}[/tex] را با آن جابجا نمود. دلیل این امر در زیر آورده شده است:
اگر [tex]x_{j}<x_{i}[/tex] باشد، آنگاه [tex]y_{j}<y_{i}[/tex] بوده و در نتیجه [tex]x_{i}>y_{j}[/tex] خواهد بود.
اگر [tex]x_{j}>x_{i}[/tex] باشد، آنگاه [tex]x_{j}[/tex] هم بزرگتر از [tex]y_{i}[/tex] خواهد بود.
حالتی که [tex]x_{i}=x_{j}[/tex] باشد نیز بصورت مشابه امکان‌پذیر نمی‌باشد.

---

********************************************************************************​​​​​​***********************

۴۱- گزینه‌ی ۴ صحیح می‌باشد.
این مسئله کاملا مشابه مسئله‌ی یافتن درخت فراگیر کمینه می‌باشد. همانگونه که می‌دانیم الگوریتم‌های محاسبه‌ی درخت فراگیر کمینه در صورت وجود یال و یا دور منفی باز هم درخت مربوطه را به درستی محاسبه می‌نمایند. در نتیجه برای محاسبه‌ی درخت فراگیر بیشینه می‌توان یال‌ها را منفی نموده و درخت فراگیر کمینه را محاسبه نمود. روش دیگر تغییر الگوریتم‌های کروسکال و پریم در جهت ترجیح یال‌های با وزن بیشتر می‌باشد. به عنوان نمونه می‌توان در هر مرحله از الگوریتم کروسکال یال با بیشترین وزن غیر دوری را انتخاب نمود.

---

********************************************************************************​​​​​​​***********************

۴۲- گزینه‌ی ۲ صحیح می‌باشد.

برای درک بهتر درستی یا نادرستی ادعاها بهتر است دوگان مسئله یعنی مسئله‌ی برش کمینه را در نظر بگیریم.
گزاره‌ی الف درست می‌باشد. برای در ک بهتر این مورد بهتر است دوگان مسئله یعنی برش کمینه را در نظر بگیریم. در صورتی که ظرفیت یال‌ها را در مقدار ثابت c ضرب نماییم، مقدار هر برش نیز در ثابت c ضرب خواهد شد، لذا یال‌های مربوط به برش کمینه تغییری نکرده (در صورت یکتا بودن برش کمینه) و فقط مقدار آن در ثابت c ضرب می‌گردد. به عبارتی دیگر در صورتی که ظرفیت یال‌ها در ثابت c ضرب شود، مقدار شار بیشینه نیز در c ضرب می‌گردد.
گزاره‌ی ب نادرست می‌باشد. به عنوان مثال نقض اگر در شکل زیر به ظرفیت هر یال یک واحد افزوده شود، شار بیشینه ۲ واحد افزایش می‌یابد.
گزاره‌ی ج نادرست می‌باشد. مشابه مورد فوق به عنوان مثال نقض اگر از ظرفیت هر یال شکل زیر یک واحد کاسته گردد، شار بیشینه ۲ واحد کاسته می‌گردد.

---

********************************************************************************​​​​​​***********************

۴۳- گزینه ؟ صحیح است.
گزینه۱ نادرست است. مثال های نقض در کتاب های مرجع موجود است.

گزینه ۲ نادرست است زیرا در الگوریتم دایکسترا هنگامی یک گره انتخاب می شود انتخاب نهایی می شود و این گره در مراحل بعد مجددا انتخاب نخواهد شد و از آن جا که تعداد گره های گراف متناهی است الگوریتم هیچگاه در حلقه ی بینهایت نمی افتد.

گزینه ۳ درست/نادرست است. {اگر یال منفی به راس شروع متصل باشند، دایکسترا درست کار خواهد کرد}

گزینه ۴ نادرست است.

ظاهرا صورت این سوال اشکال داشته و گزینه ۴ به این صورت بوده است : اگر گراف یال منفی نداشته باشد، الگوریتم دایکسترا درست کار می کند.
در این حالت گزینه ۴ صحیح خواهد بود، در غیر این صورت گزینه ۳ میتواند نزدیک ترین گزینه صحیح باشد.

---

********************************************************************************​​​​​​​***********************

۴۴- گزینه ۴ صحیح است.
مثال های ساده ای می توان ارائه داد که الگوریتم الف برای آن کمینه است ولی الگوریتم ب برای آن کمینه نیست و همچنین مثالهای ساده ای دیگری نیز می توان ارائه داد که الگوریتم الف برای آن کمینه نیست ولی الگوریتم ب کمینه است. بنابراین در حالت کلی هیچکدام از این دو الگوریتم کمینه نیستند.

---

********************************************************************************​​​​​​​​***********************

۴۵- گزینه ۴ درست است.
برای اینکه مقادیر نهایی ذخیره شده در D برابر طول کوتاهترین مسیرها شوند باید از الگوریتم بلمن-فورد استفاده کرد. این الگوریتم برای محاسبه طول همه کوتاهترین مسیرها از راس مبدا (مانند راس ۱ در این سئوال) به سایر رئوس استفاده می شود که پس از مقداردهی اولیه D مطابق صورت سئوال، شبه کد زیر را اجرا می شود:



در شبه کد بالا مشخص است که تعداد فراخوانی های تابع Relax برابر [tex]m \times n[/tex] است. دلیل اینکه حلقه for باید n بار اجرا شود این است که از آنجا که وزن یال های گراف مثبت هستند و گراف فاقد دور منفی است بنابراین کوتاهترین مسیر از گره ۱ به هر یک از گره های دیگر حداکثر از n-1 گره میانی (شامل خود گره ۱) می گذرد و چون ممکن است چنین گره ای وجود داشته باشد بنابراین حلقه for باید n-1 بار اجرا شود تا طول کوتاهترین مسیر به این گره نهایی شود و یک بار دیگر نیز حلقه for باید اجرا شود تا مسیرهایی که از این گره نیز رد می شوند مقدار آن ها نهایی شوند. در هر بار اجرای حلقه for نیز چون طول مسیر از گره ۱ به هر گره مانند v از طریق یال هایی که به گره v وارد می شوند کمتر شود بنابراین باید برای همه یالها به روز رسانی را با فراخوانی تابع Relax انجام داد.