معماری کامپیوتر و سیستم‌های موازی: الگوی تقسیم و حل (Divide and Conquer) - کوییز

1. مسئله را به زیرمسائل کوچکتر تقسیم کرده، هر زیرمسئله را به صورت بازگشتی حل می کند و سپس نتایج را ترکیب می کند.
2. مسئله را به صورت خطی حل کرده و هر مرحله از حل را به صورت مستقل پیاده سازی می کند.
3. مسئله را به یک مسئله بزرگتر تبدیل کرده و سپس آن را به صورت تکراری حل می کند.
4. مسئله را با استفاده از روش های تصادفی به زیرمسائل کوچکتر تقسیم کرده و حل می کند.

گزینه صحیح: 1

توضیح: الگوی تقسیم و حل شامل سه مرحله اصلی است: تقسیم مسئله اصلی به زیرمسائل کوچکتر و مشابه، حل بازگشتی هر زیرمسئله، و ترکیب نتایج زیرمسائل برای به دست آوردن حل مسئله اصلی.

1. Bubble Sort
2. Insertion Sort
3. Merge Sort
4. Selection Sort

گزینه صحیح: 3

توضیح: Merge Sort مسئله مرتب سازی یک آرایه بزرگ را با تقسیم آن به دو نیمه، مرتب سازی بازگشتی هر نیمه و سپس ادغام (merge) دو نیمه مرتب شده، حل می کند.

1. هر زیرمسئله به صورت مستقیم و بدون فراخوانی مجدد الگوریتم حل می شود.
2. الگوریتم بر روی هر زیرمسئله کوچکتر به صورت تکراری اعمال می شود تا به حالت پایه برسد.
3. هر زیرمسئله به صورت مستقل و بدون توجه به سایر زیرمسائل حل می شود.
4. الگوریتم بر روی هر زیرمسئله کوچکتر به صورت بازگشتی اعمال می شود تا به حالت پایه برسد.

گزینه صحیح: 4

توضیح: منظور از حل بازگشتی این است که خود الگوریتم تقسیم و حل برای حل زیرمسائل کوچکتر نیز فراخوانی می شود، تا زمانی که زیرمسئله به اندازه کافی کوچک شود (حالت پایه) و به سادگی قابل حل باشد.

1. مرحله تقسیم
2. مرحله حل بازگشتی
3. مرحله ترکیب (Combine)
4. حالت پایه (Base Case)

گزینه صحیح: 3

توضیح: مرحله ترکیب (Combine) در الگوی تقسیم و حل، نتایج حاصل از حل زیرمسائل را به گونه ای با هم ترکیب می کند که حل مسئله اصلی به دست آید.

1. زمانی که مسئله به طور طبیعی به زیرمسائل کوچکتر مشابه قابل تجزیه باشد و ترکیب نتایج آسان باشد.
2. زمانی که مسئله ماهیت تکراری دارد و نیاز به حافظه زیادی دارد.
3. زمانی که مسئله قابل حل با روش های حریصانه (Greedy) باشد.
4. زمانی که مسئله دارای وابستگی های شدید بین مراحل حل باشد.

گزینه صحیح: 1

توضیح: شرط اصلی برای استفاده مؤثر از الگوی تقسیم و حل، قابلیت تجزیه مسئله به زیرمسائل مستقل و مشابه و هم چنین امکان ترکیب منطقی نتایج این زیرمسائل است.

1. مرحله ترکیب
2. مرحله تقسیم (Partitioning)
3. حالت پایه
4. مرحله حل بازگشتی

گزینه صحیح: 2

توضیح: در QuickSort، مرحله تقسیم (Partitioning) شامل انتخاب یک عنصر به عنوان محور (pivot) و سپس مرتب سازی عناصر آرایه به گونه ای است که عناصر کوچکتر از محور قبل از آن و عناصر بزرگتر از محور بعد از آن قرار گیرند.

1. محاسبه مجموع عناصر یک آرایه بزرگ
2. جستجوی دودویی (Binary Search)
3. پیدا کردن کوتاه ترین مسیر در یک گراف
4. حل مسئله برج هانوی (Tower of Hanoi)

گزینه صحیح: 4

توضیح: مسئله برج هانوی به طور کلاسیک با الگوی تقسیم و حل حل می شود. برای انتقال N دیسک، مسئله به انتقال N-1 دیسک به یک میله کمکی، انتقال دیسک N به میله مقصد و سپس انتقال N-1 دیسک از میله کمکی به میله مقصد تقسیم می شود.

1. با افزایش تعداد پردازنده های مورد نیاز برای حل هر زیرمسئله.
2. با تقسیم مسئله به زیرمسائل کوچکتر که می توانند به طور همز مان بر روی پردازنده های مختلف اجرا شوند.
3. با کاهش وابستگی بین مراحل حل و جلوگیری از اجرای موازی.
4. با افزایش اندازه هر زیرمسئله برای استفاده بهینه از حافظه.

گزینه صحیح: 2

توضیح: ماهیت قابل تقسیم الگوی تقسیم و حل، امکان اجرای موازی زیرمسائل را بر روی پردازنده های مختلف فراهم می کند، که منجر به کاهش زمان کلی اجرای مسئله می شود.

1. Linear Search
2. Binary Search
3. Jump Search
4. Exponential Search

گزینه صحیح: 2

توضیح: Binary Search با مقایسه مقدار مورد نظر با عنصر میانی آرایه مرتب شده، دامنه جستجو را به نصف کاهش می دهد و این فرآیند را به صورت بازگشتی یا تکراری ادامه می دهد، که نمونه ای از تقسیم و حل است.