«قضیه اصلی» یا همان «قضیه مَستر» (Master Theorem) در حوزه «تحلیل الگوریتم‌ها» مطرح می‌شود. در این مقاله به این سوال پاسخ داده شده است که قضیه اصلی در طراحی الگوریتم چیست و چگونه برای حل مسائل بازگشتی به کار گرفته می‌شود.

فهرست مطالب این نوشته

قضیه اصلی در طراحی الگوریتم چیست ؟

در حیطه «تحلیل الگوریتم‌ها» (Analysis of Algorithms)، قضیه اصلی برای مسائل بازگشتی تقسیم و حل، تحلیل مجانبی (Asymptotic Analysis) را با استفاده از نماد O بزرگ برای انواع رابطه‌های بازگشتی فراهم شده است که در تحلیل بسیاری از الگوریتم‌های تقسیم و حل (Divide and Conquer Algorithms) رخ می‌دهند.

معرفی قضیه اصلی در طراحی الگوریتم

برای مثال می‌توان مسئله‌ای را در نظر گرفت که با استفاده از یک الگوریتم بازگشتی به صورت زیر قابل حل باشد:

procedure p(input x of size n):
if n < some constant k:
Solve x directly without recursion
else:
Create a subproblems of x, each having size n/b
Call procedure p recursively on each subproblem
Combine the results from the subproblems

الگوریتم فوق، مسئله را به صورت بازگشتی به تعدادی زیر مسئله (مسئله کوچک‌تر) تقسیم می‌کند. هر زیر مسئله اندازه‌ای برابر با $$ \frac n b $$ دارد. درخت راه حل برای هر فراخوانی بازگشتی دارای یک گره (Node) است. فرزندان آن گره سایر فراخوانی‌هایی هستند که به واسطه آن فراخوانی خاص ایجاد شده‌اند. برگ‌های درخت «وضعیت پایه» (Base Case) بازگشت به حساب می‌آیند. برگ‌ها زیرمسئله‌هایی هستند (با اندازه کم‌تر از k) که عملیات بازگشت ندارند. در مثال بالا، هر گره غیر برگ دارای $$ a $$ گره فرزند است.

درخت راه حل در الگوریتم بازگشتی

هر گره متناظر با اندازه زیرمسئله $$ n $$ مقداری کار انجام می‌دهد که به نمونه فراخوانی بازگشتی ارجاع داده و به وسیله $$ f(n) $$ مشخص می‌شود. کل مقدار کار انجام شده به وسیله تمام الگوریتم برابر با مجموع کار انجام شده توسط همه گره‌های درخت است. زمان اجرای یک الگوریتم مثل الگوریتم «p» در بالا با یک ورودی به اندازه «n» که معمولاً با $$ T(n) $$ نشان داده می‌شود را می‌توان به وسیله رابطه بازگشتی زیر نوشت:

$$T(n) = aT( \frac n b) + f(n)$$

در رابطه فوق، $$ f(n) $$ مدت زمانی برای ایجاد زیرمسئله‌ها و ترکیب نتایج آن‌ها در عملیات فوق به حساب می‌آید. این معادله می‌تواند به طور متوالی جایگزین خودش شود و جهت دستیابی به یک عبارت برای کل کار انجام شده گسترش داده شود. قضیه اصلی اجازه می‌دهد تا رابطه‌های بازگشتی بسیاری با این فُرم به طور مستقیم به نماد O بزرگ تبدیل شوند. این کار بدون بسط دادن رابطه بازگشتی انجام می‌شود.

رابطه فوق دارای چند شرط برای مقادیرش است. شروط مقادیر معادله قضیه اصلی به صورت زیر هستند:

$$a \geq 1$$

$$b > 1$$

$$f(n) > 0$$

برای مثال می‌توان دو معادله زیر را در نظر گرفت، این دو معادله را می‌توان با استفاده از قضیه اصلی حل کرد:

$$c + T(\frac n 2) \longrightarrow a=1,‎\,b=2\,‎‎‎‎‎‎and\,f(n)=c,$$

$$c + T(\frac n 2) \longrightarrow a=2,‎\,b=2‎‎\,‎‎‎‎‎‎and‎\,‎f(n)=n,$$

بسیاری از الگوریتم‌ها دارای پیچیدگی زمانی به صورت قضیه اصلی هستند. برای مثال در بحث زمان اجرای الگوریتم‌ها، می‌توان نشان داد که مرتبه زمانی الگوریتم مرتب‌سازی ادغام (Merge Sort Algorithm) به صورت زیر است:

$$T(n) = 2T(\frac n 2) + n$$

به صورت مشابه، روش پیمایش درخت دودویی (Binary Tree Traversal) نیز به مرتبه زمانی به صورت زیر و در فرم قضیه اصلی نیاز دارد:

$$T(n) = 2T(\frac n 2) + O(1)$$

در مقایسه $$\log _{b}a $$ با رفتار $$f(n)$$ می‌توان به این نتیجه رسید که قضیه اصلی در طراحی الگوریتم راه حل مناسبی برای بیشتر معادلات بازگشتی به شمار می‌رود. پیش از بررسی دقیق‌تر قضیه اصلی در طراحی الگوریتم ، ابتدا بهتر است به ارائه تعریفی از معادله بازگشتی (Recursion) و شرح چیستی آن پرداخته شود.

رابطه بازگشتی چیست؟

رابطه بازگشتی به معنی «تعریف یک مسئله به وسیله خود معادله» است. این روش یک ابزار بسیار قدرتمند در نوشتن الگوریتم‌ها به حساب می‌آید. معادله بازگشتی به این دلیل که در آن نمونه‌های زیادی از عبارات بر حسب خودشان نوشته شده‌اند، کاملاً یک روش ریاضی است. برای مثال می‌توان دنباله (سری) فیبوناچی (Fibonacci Sequence) را در نظر گرفت که به صورت زیر نوشته می‌شود:

$$ F(i) = F(i-1) + F(i-2) $$

معادله بازگشتی | قضیه اصلی در طراحی الگوریتم

الگوریتم بازگشتی فرآیندی برای پردازش یا حل مسئله‌ای بر اساس (نسخه ساده‌تر) خود مسئله به حساب می‌آید. می‌توان به عنوان مثال ساده‌ای از زندگی روزمره با صورت مسئله «پیدا کردن راه خانه خود» عملیات زیر را برای حل آن در نظر گرفت:

  • اگر شخص در خانه باشد، حرکت را متوقف می‌کند.
  • اگر شخص بیرون از خانه و نزدیک به آن باشد، یک قدم به سمت خانه برمی‌دارد.
  • در صورتی که از مسیر خانه اطلاعی نداشته باشد، نیاز است که با روشی راه خانه خود را بیابد.

در این مثال راه‌حل پیدا کردن مسیر خانه دارای دو یا سه مرحله زیر است:

  • شخص به خانه نمی‌رود، چون در حال حاضر در خانه است.
  • یک روش بسیار ساده برای حل مسئله در نظر گرفته می‌شود.
  • در نهایت کل الگوریتم دوباره انجام می‌شود.

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

شرح قضیه اصلی در طراحی الگوریتم

در ابتدا برای شرح قضیه اصلی در طراحی الگوریتم یک رابطه بازگشتی به شکل زیر در نظر گرفته می‌شود:

$$T(n) = aT(\frac n b)$$

در معادله فوق، a تعداد فرزندان هر گره (Node) یعنی همان تعداد زیر مسئله‌ها را نشان می‌دهد و زمان اجرای هر یک از گره‌های اولیه با سه فرزند $$T( \frac n b)$$ است. درخت این معادله $$\log _{b}n $$ عمق دارد و عمق i شامل $$a^i$$ گره است. بنابراین، تعداد برگ‌ها (فرزندان) در درخت با معادله $$a^{\log _{b}n} = n ^ {\log _{b}a}$$ محاسبه می‌شوند و زمان اجرای الگوریتم $$\Theta(n ^ {\log _{b}a})$$ است.

شرح قضیه اصلی در طراحی الگوریتم به وسیله درخت

طبق تصویر فوق و به طور شهودی، قضیه اصلی استدلال می‌کند که اگر تابع مجانبی (Asymptotically) مثبت $$f(n)$$ به این تابع بازگشتی اضافه شود، تابعی به صورت زیر ایجاد می‌شود:

$$T(n) = aT( \frac n b) + f(n)$$

می‌توان فرم مجانبی $$T$$ را بر اساس مقایسه نسبی بین $$f$$ و $$\log _{b}n $$ تعیین کرد. قضیه اصلی در طراحی الگوریتم دارای حالت‌های گوناگونی است که در بخش بعدی به آن‌ها پرداخته می‌شود.

حالت‌های قضیه اصلی در طراحی الگوریتم

قضیه اصلی در طراحی الگوریتم دارای سه حالت گوناگون زیر است که برای حل هر مسئله یکی از این سه حالت انتخاب می‌شود:

  • حالت اول: اگر معادله $$f(n)=O(n ^ {\log _{b}a-\epsilon})$$ برای $$\epsilon>0$$ برقرار باشد، آن‌گاه زمان زیر برای رابطه برقرار است:

$$T(n)=\Theta(n ^ {\log _{b}a})$$

  • حالت دوم: اگر معادله $$f(n)=\Theta(n ^ {\log _{b}a})$$ برقرار باشد، آن‌گاه زمان زیر برای رابطه برقرار است:

$$T(n)=\Theta(n ^ {\log _{b}a}lg\,n )$$

  • حالت سوم: اگر معادله $$f(n)=\Omega(n ^ {\log _{b}a+\epsilon})$$ برای $$\epsilon>0$$ و اگر $$af(n/b) \leq cf(n)$$ برای $$c<1$$ و nهای بزرگ برقرار باشند، آن‌گاه زمان زیر برای رابطه برقرار است:

$$T(n)=\Theta(f(n))$$

با استفاده از این سه حالت، می‌توان به راحتی پاسخ معادله بازگشتی به فرم $$T(n) = aT( \frac n b) + f(n)$$ را به دست آورد. در بخش بعدی این مقاله به بررسی ایده‌ای پرداخته می‌شود که باعث ایجاد قضیه اصلی در طراحی الگوریتم شد.

ایده پشت پرده قضیه اصلی در طراحی الگوریتم چیست ؟

ایده‌ای که باعث ایجاد قضیه اصلی در طراحی الگوریتم شد و در پشت پرده آن قرار دارد بر اساس مقایسه $$n ^ {\log _{b}a}$$ با تابع $$f(n)$$ است. به صورت کلی می‌توان گفت که قضیه اصلی در طراحی الگوریتم بر اساس مقایسه ایجاد می‌شود. به اصطلاح عامیانه، قضیه اصلی اساساً به دنبال این موضوع است که بین $$f(n)$$ و $$n ^ {\log _{b}a}$$ کدام یک بر دیگری تسلط دارد. برای ساده و بهتر متوجه شدن سه حالت بخش قبل، سه حالت زیر ارائه شده است:

  • حالت اول: اگر تابع $$f(n)$$ تحت سلطه (کوچکتر از) $$n ^ {\log _{b}a}$$ باشد، آن‌گاه رابطه پیچیدگی زمانی زیر برقرار است:

$$T(n)=\Theta(n ^ {\log _{b}a})$$

طبق حالت اول بخش پیشین، در معادله $$f(n)=O(n ^ {\log _{b}a-\epsilon})$$ به عنوان بدترین حالت $$f(n)$$، معادله $$n ^ {\log _{b}a-\epsilon}$$ در نظر گرفته می‌شود که کمتر از $$n ^ {\log _{b}a}$$ است. بنابراین، $$n ^ {\log _{b}a}$$ زمان بیشتری می‌برد و در نتیجه تسلط پیدا می‌کند.

  • حالت دوم: اگر $$f(n)$$ و همچنین $$n ^ {\log _{b}a}$$ هر دو به یک اندازه وجود داشته باشند (برابر باشند). بنابراین زمانی که صرف این حالت می‌شود برابر با رابطه زیر است:

$$T(n)=\Theta(n ^ {\log _{b}a}lg\,n )$$

  • حالت سوم: طبق حالت سوم بخش پیشین، بهترین حالت $$f(n)$$ برابر با $$n ^ {\log _{b}a-\epsilon}$$ به حساب می‌آید. بنابراین، بهترین حالت $$f(n)$$ بزرگتر از $$n ^ {\log _{b}a}$$ است و از این رو $$f(n)$$ زمان بیشتری می‌برد و در نتیجه تسلط پیدا می‌کند (بزرگتر می‌شود). در نهایت می‌توان گفت که زمان رابطه در این حالت به صورت زیر است:

$$T(n)=\Theta(f(n))$$

در بخش بعدی این مقاله به شرح قضیه اصلی در طراحی الگوریتم به وسیله درخت بازگشتی پرداخته می‌شود.

تعریف قضیه اصلی در طراحی الگوریتم به وسیله درخت بازگشتی

قضیه اصلی در طراحی الگوریتم عمدتاً از روش درخت بازگشتی استفاده می‌کند. اگر درخت بازگشتی $$T(n) = aT( \frac n b) + f(n)$$ طراحی شود، تابع $$f(n)$$ در ریشه درخت قرار می‌گیرد و برگ‌های آن با $${\log _{b}a}$$ محاسبه می‌شوند و ارتفاع درخت را $${\log _{b}n}$$ نشان می‌دهد.

تعریف به وسیله درخت

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

تا به این بخش از مقاله مطالبی که ارائه شدند مبتنی بر $$n ^ {\log _{b}a}$$ بودند، با این که $$T(n)$$ برای قضیه اصلی در طراحی الگوریتم به وسیله $$f(n)$$ و $$T( \frac n b)$$ ایجاد شده است. در ادامه این مقاله، قبل از پرداختن به دلیل استفاده از $$n^{\log _{b}a}$$ در قضیه اصلی در طراحی الگوریتم ، مجموعه آموزش‌های ساختمان داده و طراحی الگوریتم فرادرس به علاقه‌مندان معرفی می‌شوند.

معرفی فیلم های آموزش ساختمان داده و طراحی الگوریتم فرادرس

مجموعه آموزش ساختمان داده و طراحی الگوریتم

در سایت فرادرس، دوره‌های آموزشی بر اساس موضوع در مجموعه‌های متفاوتی دسته‌بندی می‌شوند. یکی از این مجموعه‌ها آموزش ساختمان داده و طراحی الگوریتم است. علاقه‌مندان می‌توانند برای یادگیری درس‌های ساختمان داده و طراحی الگوریتم که قضیه اصلی در طراحی الگوریتم را هم شامل می‌شود از این مجموعه آموزشی استفاده کنند. در زمان تدوین این مقاله، مجموعه دوره‌های آموزش ساختمان داده و طراحی الگوریتم فرادرس حاوی بیش از ۱۱۰ ساعت محتوای ویدیویی و نزدیک به ۱۱ عنوان آموزشی مختلف است. دوره‌های مختلفی در زمینه‌های گوناگون مرتبط با ساختمان داده و طراحی الگوریتم در این مجموعه گردآوری شده‌اند. در ادامه، برخی از دوره‌های این مجموعه به طور مختصر معرفی شده‌اند:

  • فیلم آموزش طراحی الگوریتم به همراه حل مثال های عملی (طول مدت: ۸ ساعت و ۱۶ دقیقه، مدرس: مهدی اشرفی): در این دوره آموزشی علاقه‌مندان و دانشجویان با طراحی الگوریتم یعنی اساس کار نوشتن یک برنامه، طرز فکر و چگونگی رسیدن به هدف آن همراه با مثال‌های عملی آشنا می‌شوند. برای مشاهده فیلم آموزش طراحی الگوریتم به همراه حل مثال‌های عملی + کلیک کنید.
  • فیلم آموزش طراحی الگوریتم (مرور – تست کنکور ارشد) (طول مدت: ۱۴ ساعت و ۴۷ دقیقه، مدرس: دکتر فرشید شیرافکن): در این فرادرس، مفاهیم اصلی درس طراحی الگوریتم برای دانشجویان و علاقه‌مندانی ارائه شده است که قصد یادگیری این درس را برای کنکور دارند. جهت مشاهده فیلم آموزش طراحی الگوریتم (مرور – تست کنکور ارشد) + کلیک کنید.
  • فیلم آموزش حل روابط بازگشتی (طول مدت: ۴ ساعت و ۳۶ دقیقه، مدرس: دکتر فرشید شیرافکن): استفاده از این فرادرس به دانشجویانی پیشنهاد می‌شود که قصد یادگیری حل مسائل با روابط بازگشتی را دارند. برای مشاهده فیلم آموزش حل روابط بازگشتی + کلیک کنید.
  • فیلم آموزش رابطه های بازگشتی در طراحی الگوریتم و ساختمان گسسته (مرور – تست کنکور ارشد) (طول مدت: ۱ ساعت و ۵۴ دقیقه، مدرس: دکتر فرشید شیرافکن): آموزش رابطه‌های بازگشتی در طراحی الگوریتم و ساختمان گسسته یکی از مفاهیم اصلی است که در کنکورهای کارشناسی ارشد برای درس ساختمان گسسته و طراحی الگوریتم مورد سوال قرار می‌گیرد. از این رو، یادگیری رابطه‌های بازگشتی برای دانشجویان و متقاضیان کنکور پیشنهاد می‌شود. برای مشاهده فیلم آموزش رابطه های بازگشتی در طراحی الگوریتم و ساختمان گسسته (مرور – تست کنکور ارشد) + کلیک کنید.
  • فیلم آموزش ساختمان داده ها (مرور – تست کنکور ارشد) (طول مدت: ۲۰ ساعت و ۳۵ دقیقه، مدرس: دکتر فرشید شیرافکن): ساختمان داده‌ها یکی از در‌س‌های کنکور کارشناسی ارشد رشته کامپیوتر و فناوری اطلاعات و پیش‌ نیاز درس طراحی الگوریتم است. در این فرادرس، مباحث این درس تدریس شده و اکثر تست‌های کنکور کارشناسی ارشد دولتی بررسی شده‌اند. برای مشاهده فیلم آموزش ساختمان داده‌ها (مرور – تست کنکور ارشد) + کلیک کنید.
  • فیلم آموزش مروری بر پیچیدگی محاسبات Computational Complexity (طول مدت: ۱ ساعت و ۳ دقیقه، مدرس: سحر اردلان): با یادگیری پیچیدگی محاسبات، می‌توان در مسیر حل مسئله محدودیت‌های محاسبات را مورد بررسی قرار داد. برای یادگیری مبحث پیچیدگی محاسبات، این دوره آموزشی به دانشجویان و علاقه‌مندان معرفی شده است. برای مشاهده فیلم آموزش مروری بر پیچیدگی محاسبات Computational Complexity + کلیک کنید.

اکنون پس از معرفی برخی از فیلم‌های آموزش ساختمان داده و طراحی الگوریتم فرادرس، در بخش بعدی دلیل استفاده از $$n^{\log _{b}a}$$ مورد بررسی قرار می‌گیرد.

چرا از $$n ^ {\log _{b}a}$$ برای قضیه اصلی در طراحی الگوریتم استفاده می‌شود؟

همان‌طور که در بخش‌های قبلی ارائه شد معادله زیر نشان دهنده قضیه اصلی در طراحی الگوریتم است:

$$T(n) = aT(\frac n b) + f(n)$$

در رابطه فوق، عبارت $$aT( \frac n b)$$ در نظر گرفته می‌شود و $$T(n)’$$ زمان صرف شده توسط این عبارت به حساب می‌آید. عبارت $$aT( \frac n b)$$ به معنی این است که مسئله با اندازه $$n$$ به $$a$$ زیر مسئله دیگر یا بیشتر با سایز $$\frac n b$$ تقسیم می‌شود. بنابراین، زمان کامل صرف شده برای اندازه $$n$$ یعنی $$T(n)’ = a‎\; times ‎\;T( \frac n b) + f(n)$$ و $$T( \frac n b)$$ زمانی است که به وسیله هر زیر مسئله با سایز $$\frac n b$$ به دست می‌آید. بنابراین زمان کامل رابطه برابر است با:

$$T(n)’=aT( \frac n b)$$

برای تجزیه و تحلیل عبارت $$T( \frac n b)$$، اندازه آن به طور مجدد به $$a$$ زیر مجموعه یا بیشتر با اندازه $$\frac n {b^2}$$ تقسیم می‌شود. از این رو، عبارت زیر ایجاد خواهد شد:

$$T( \frac n b)=aT(\frac n {b^2})$$

$$\implies‎\: T(n)’=aT( \frac n b)=a^2T(\frac n {b^2}) $$

پس می‌توان به راحتی نوشت:

$$T(n)’=aT( \frac n b)=a^2T(\frac n {b^2})=a^3T(\frac n {b^3})=a^iT(\frac n {b^i})$$

بنابراین می‌توان بیان کرد که کل زمان صرف شده برای عبارت $$aT( \frac n b)$$ مقدار $$a^iT(\frac n {b^i})$$ است. در مرحله بعد عبارت زیر در نظر گرفته می‌شود:

$$n=b^k \implies‎\: k=\log _{b}n$$

در سطح i، اندازه هر زیر مسئله $$\frac n {b^i}$$ به حساب می‌آید. در آخرین سطح، اندازه زیر مسئله برابر با عدد یک است. یعنی:

$$\frac n {b^i}=1 \implies‎\: n={b^i} \implies‎\: \log _{b}n=i=k \implies‎\: i=k $$

با استفاده از عبارت فوق می‌توان $$T(n)’=$$ را بازنویسی کرد. عبارات زیر این بازنویسی را نشان می‌دهند:

$$T(n)’=a^iT(\frac n {b^i})=a^{\log _{b}n} {(\frac {b^i} {b^i})}(n=b^k=b^i)$$

$$=a^{\log _{b}n}(T(1))$$

$$=\Theta(a^{\log _{b}n})=\Theta(n^{\log _{b}a})$$

بدین ترتیب، مشاهده می‌شود که عبارت اول زمانی برابر با $$\Theta(n^{\log _{b}a})$$ صرف می‌کند و به همین دلیل است که با $$f(n)$$ مقایسه می‌شود. بنابراین مفهوم قضیه اصلی در طراحی الگوریتم تا به اینجا مورد بررسی قرار گرفت و دلیل استفاده از $$n^{\log _{b}a}$$ برای مقایسه در آن نیز شرح داده شد.

حالت‌های غیر قابل قبول برای قضیه اصلی در طراحی الگوریتم

برخی از معادلات به وسیله قضیه اصلی در طراحی الگوریتم قابل حل نیستند. در این بخش این معادلات ارائه شده‌اند:

  • معادلاتی به شکل زیر به وسیله قضیه اصلی حل نمی‌شوند:

$$T(n) = 2^nT(\frac n 2) + n^n$$

  • برای حل معادلات به وسیله قضیه اصلی باید تعداد زیر مسئله‌ها ثابت باشند، $$a$$ در معادله زیر ثابت نیست. پس در معادلاتی به فرم زیر از قضیه اصلی نمی‌توان استفاده کرد:

$$T(n) = 2T(\frac n 2) + \frac n {\log _{}n}$$

  • معادلات دارای تفاوت غیر چندجمله‌ای (Non Polynomial) مابین $$f(n)$$ و $$n^{\log _{b}a}$$ به وسیله قضیه اصلی در طراحی الگوریتم قابل حل نیستند:

$$T(n) = 0.5T(\frac n 2) + n$$

  • معادلاتی که به وسیله قضیه اصلی حل می‌شوند، نمی‌توانند کمتر از یک زیر مسئله داشته باشند ($$a<1$$)، بنابراین معادلاتی به فرم زیر با استفاده از قضیه اصلی حل نمی‌شوند:

$$T(n) = 64T(\frac n 8) – n^2{\log _{}n}$$

  • در معادلاتی که $$f(n)$$ مثبت نیست، نمی‌توان از قضیه اصلی استفاده کرد:

$$T(n) = T(\frac n 2) + n(2 – cos\:n)$$

پس از شرح مفاهیم قضیه اصلی در طراحی الگوریتم ، اکنون در ادامه نمونه‌ها و مثال‌هایی از قضیه اصلی برای یادگیری روش استفاده از آن ارائه شده است.

مثال‌های استفاده از قضیه اصلی در طراحی الگوریتم

در این بخش برای یادگیری بهتر و تفهیم قضیه اصلی در طراحی الگوریتم چند مثال همراه با راه‌حل آن‌ها ارائه شده است.

مثال قضیه اصلی در طراحی الگوریتم : مرتب‌سازی ادغام

الگوریتم مرتب‌سازی ادغام به صورت زیر نوشته می‌شود و می‌توان آن را با استفاده از قضیه اصلی حل کرد:

$$T(n) = 2T(\frac n 2) + n$$

در این مثال مقادیر زیر وجود دارند:

$$a=2$$

$$b=2$$

$${\log _{b}a} = \log _{2}2 = 1$$

حال در ادامه دو عبارت زیر از رابطه قضیه اصلی با همان عبارات از مثال فوق برابر قرار می‌گیرند:

$$n^{\log _{b}a} = n^{\log _{2}2} = {n}$$

$$f(n)=n$$

$$\implies‎\: n^{\log _{b}a} = {n} = f(n)$$

با مقایسه $$n^{\log _{b}a}$$ با $$f(n)$$ به نتیجه زیر می‌توان رسید:

$$\implies‎\: f(n)=\Theta(n^{\log _{b}a})$$

در این بخش می‌توان به صورت زیر و برای جواب نهایی از حالت دوم قضیه اصلی در طراحی الگوریتم استفاده کرد:

$$T(n)=\Theta(n ^ {\log _{b}a}lg\,n ) = \Theta(n‎\:lg‎\:n)$$

مثال قضیه اصلی در طراحی الگوریتم : پیمایش درخت دودویی

به طور مشابه با مثال اول، راه‌حل پیمایش درخت دودویی با رابطه زیر به وسیله قضیه اصلی در طراحی الگوریتم ایجاد می‌شود.

$$T(n) = 2T(\frac n 2) + O(1)$$

$$f(n)=O(1)$$

چون $${n^{\log _{b}a}}={n}$$، بزرگتر از مقدار ثابت $$a$$ است، بنابراین قضیه اصلی با حالت اول، پاسخ این مثال را به دست می‌آورد:

$$T(n)=\Theta(n ^ {\log _{b}a}) = \Theta(n‎)$$

مثال قضیه اصلی در طراحی الگوریتم : حل یک رابطه

  • حل رابطه زیر با استفاده از قضیه اصلی در طراحی الگوریتم در ادامه ارائه شده است:

$$T(n) = 2T(\frac n 2) + n^2$$

ابتدا مقادیر این عبارت استخراج می‌شوند:

$$a=2$$

$$b=2$$

$${\log _{2}2} = 1$$

$$\implies‎\: n^{\log _{b}a} = {n^1} = n$$

عبارات معادله برابر با همان عبارت در رابطه قضیه اصلی قرار می‌گیرند:

$$f(n)=n^2$$

همچنین، با مقایسه $$n^{\log _{b}a}$$ و $$f(n)$$ به نتیجه زیر می‌توان رسید:

$$\implies‎\: f(n)=\Omega(n^{1+\epsilon})\:(\epsilon=1)$$

اگر بقیه شرایط حالت سوم برای $$f(n)$$ برآورده شوند، این حالت در این سوال قابل اعمال است. شرط $$af(n/b) \leqslant cf(n)$$ در این مثال برای $$c<1$$ و nهای بزرگ وجود دارد. بنابراین برای یک n، عبارت زیر نوشته می‌شود. برای $$(c=\frac 1 2)$$:

$$af(\frac n b) = 2f(\frac n 2) = 2\frac {n^2} 4 = \frac {n^2} 2 \leq \frac 1 2(n^2) \: $$

بنابراین، شرط برای $$(c=\frac 1 2)$$ برقرار است و پاسخ نهایی به صورت زیر نوشته می‌شود:

$$T(n)=\Theta(f(n)) = \Theta(n^2‎)$$

مثال چهارم استفاده از قضیه اصلی در طراحی الگوریتم

معادله زیر با روش قضیه اصلی در طراحی الگوریتم حل می‌شود:

$$T(n) = 2T(\frac n 2) + \sqrt []{n}$$

مقادیر رابطه بالا به صورت زیر است:

$$a=2$$

$$b=2$$

$${\log _{2}2} = 1$$

$$\implies‎\: n^{\log _{b}a} = {n^1} = n$$

با جایگذاری عبارت این مثال رابطه قضیه اصلی پاسخ زیر به دست می‌آید، این مثال به وسیله حالت دوم قضیه اصلی حل شده است:

$$f(n) = \sqrt []{n}$$

$$\implies‎\: f(n) = \Theta(n^{1-\epsilon})$$

$$\implies‎\: T(n) = \Theta(n)$$

مثال پنجم استفاده از قضیه اصلی در طراحی الگوریتم

رابطه زیر در نظر گرفته شده است و با قضیه اصلی بررسی می‌شود:

$$T(n) = 3T(\frac n 4) + n‎\:lg‎\:n$$

مقادیر استخراج شده از این مثال به صورت زیر هستند:

$$a=3$$

$$b=4$$

$${4\log _{4}3} = 0.792$$

$$f(n)$$ به صورت زیر جایگذاری می‌شود و این مثال حالت سوم از قضیه اصلی را نشان می‌دهد:

$$f(n) = \Omega(n^{\log _{4}3+\epsilon})$$

برای $$(c=\frac 3 4)$$:

$$3(\frac n 4)\:lg\:(\frac n 4) \leq \frac 3 4n\:lg\:n = c\:\ast\:f(n)$$

$$\implies‎\: T(n) = \Theta(n\:lg\:n)$$

مثال ششم استفاده از قضیه اصلی در طراحی الگوریتم

معادله‌ای که برای این مثال بررسی می‌شود، به صورت زیر است:

$$T(n) = 2T(\frac n 2) + n‎\:lg‎\:n$$

مقادیر معادله فوق در ادامه نشان داده شده‌اند:

$$a=2$$

$$b=2$$

$${\log _{2}2} = 1$$

$$\implies‎\: n^{\log _{b}a} = {n^1} = n$$

$$f(n)$$ این مثال به صورت زیر است:

$$f(n) = n‎\:lg‎\:n$$

$$f(n)$$ باید چندجمله‌ای با ضریب $$n^\epsilon$$ باشد، اما در این مثال چندجمله‌ای است که با ضریب $$lg\:n$$ بزرگ‌تر در نظر گرفته می‌شود. بنابراین، قضیه اصلی در این مثال اعمال نمی‌شود.

مثال هفتم استفاده از قضیه اصلی در طراحی الگوریتم

رابطه مورد بررسی قرار گرفته در این سوال به صورت زیر است:

$$T(n) = 2T(\sqrt []{n}) + lg\:n$$

رابطه ارائه شده در این مثال به فرم $$aT( \frac n b) + f(n)$$ نیست، پس به صورت مستقیم نمی‌توان قضیه اصلی را روی آن اعمال کرد. اما می‌توان آن را به جایگزینی به فرمی تبدیل کرد که با قضیه اصلی قابل حل باشد. جایگزینی به صورت زیر انجام می‌شود:

$$lg\:n = m \implies‎\: n=2^m$$

با جایگزاری $$n$$ با $$n=2^m$$، معادله به فرم زیر تبدیل می‌شود و باید ساده شود تا بتوان آن را با قضیه اصلی حل کرد:

$$T(2^m) = 2T(2^{m/2})+m$$

در این مرحله $$S(m)$$ جایگزین $$T(2^m)$$ می‌شود:

$$\implies‎\: S(m) = 2S(\frac m 2)+m$$

اکنون، این رابطه فرم قضیه اصلی را دارد و دقیقا همان رابطه‌ای است که در مثال اول بررسی شد. پس در روش حل آن روشن است که:

$$S(m) = O(m\:lg\:m)$$

$$\implies‎\: T(n) = T(2^m) = S(m) = O(m‎\:lg‎\:m)$$

در نهایت برای رسیدن به پاسخ صحیح، مقدار $$m$$ با $$lg\:n$$ جایگزین شده است و رابطه زیر ایجاد می‌شود:

$$\implies‎\: T(n) = O(lg‎\:n\:lg(lg\:n))$$

به این ترتیب در این مقاله سعی شد تا حد امکان به طور جامع به بررسی قضیه اصلی در طراحی الگوریتم پرداخته شود و همچنین مباحث پیرامون آن از جمله الگوریتم‌های بازگشتی و مثال‌هایی برای قضیه اصلی در طراحی الگوریتم بررسی شدند.

مفهوم ساختمان داده و طراحی الگوریتم

ساختمان داده یک قالب تخصصی برای سازماندهی، پردازش، بازیابی و ذخیره داده‌ها است. چندین نوع اولیه و پیشرفته از ساختمان داده‌ها وجود دارند که هر کدام از آن‌ها برای سازماندهی داده‌ها متناسب با یک هدف خاص طراحی شده‌اند. ساختمان داده‌ها و الگوریتم‌ها دسترسی و کار با داده‌های مورد نیاز را به روش‌های مناسب برای کاربران آسان می‌کنند. مهم‌تر از همه، ساختمان داده‌ها، سازماندهی اطلاعات را به گونه‌ای دقیق انجام می‌دهند که هم ماشین‌ها و هم انسان‌ها بتوانند آن‌ها را بهتر درک کنند.

طراحی الگوریتم | قضیه اصلی در طراحی الگویتم

در علوم کامپیوتر و برنامه نویسی کامپیوتر، یک ساختمان داده ممکن است در ذخیره داده‌ها برای انتخاب و طراحی آن‌ها از الگوریتم‌های گوناگونی استفاده کند. در برخی موارد، عملیات اساسی الگوریتم به طور کامل با طراحی ساختمان داده همراه است. هر ساختمان داده حاوی اطلاعاتی است در مورد مقادیر داده‌ها، روابط بین داده‌ها و در برخی موارد توابعی که می‌توانند روی داده اعمال شوند. سپس این داده‌ها با استفاده از یک الگوریتم مناسب بهینه‌سازی و استفاده می‌شوند. قضیه اصلی یکی از روش‌های حل معادلات و محاسبه زمان در طراحی الگوریتم به حساب می‌آید. اکنون در بخش پایانی این مقاله، برای آشنایی بیشتر و آموزش قضیه اصلی در طراحی الگوریتم ، دوره‌های فرادرسی که بیشترین ارتباط را با قضیه اصلی در طراحی الگوریتم و برنامه نویسی دارند به علاقه‌مندان معرفی شده‌اند.

معرفی فیلم های آموزش طراحی الگوریتم فرادرس

در این بخش انتهایی مقاله «قضیه اصلی در طراحی الگوریتم» برای یادگیری بیشتر، تعدادی از دوره‌های آموزش ساختمان داه، طراحی الگوریتم و روش‌های بازگشتی فرادرس به علاقه‌مندان معرفی شده‌اند. مفهوم قضیه اصلی در برخی از این دوره‌ها مورد بررسی قرار گرفته و آموزش داده شده است. در ابتدا به معرفی دوره آموزش حل روابط بازگشتی پرداخته می‌شود.

فیلم آموزش حل روابط بازگشتی

فیلم آموزش حل روابط بازگشتی

در ریاضیات، رابطه بازگشتی (Recurrence Relation)، دنباله‌ای است که به صورت بازگشتی تعریف می‌شود. در یک دنباله بازگشتی، معادله‌ای به نام رابطه بازگشتی ارائه می‌شود که با آن، جمله nام دنباله به جملات پیشین مرتبط می‌شوند. نام مقادیر چند جمله اول دنباله شرایط مرزی یا مقادیر اولیه است. برای یادگیری حل روابط بازگشتی، فیلم آموزش حل روابط بازگشتی، توسط دکتر فرشید شیرافکن پیشنهاد می‌شود. طول مدت این دوره نزدیک به پنج ساعت است و این دوره چهار درس را در بر می‌گیرد. سرفصل‌های این دوره شامل روابط بازگشتی، روش درخت بازگشت (Recursion Tree)، قضیه اصلی – تغییر متغیر و رابطه‌های بازگشتی همگن می‌شوند.

فیلم آموزش روش تقسیم و حل در طراحی الگوریتم (مرور – تست کنکور کارشناسی ارشد)

فیلم آموزش روش تقسیم و حل در طراحی الگوریتم (مرور - تست کنکور کارشناسی ارشد)

یکی از روش‌های پرکاربرد و محبوب برای طراحی الگوریتم‌ها روش «تقسیم و حل» به حساب می‌آید. در این فرادرس یک مرور اجمالی به روش تقسیم و حل در طراحی الگوریتم شده و سپس تست‌های کنکور دولتی حل شده است. قضیه اصلی در طراحی الگوریتم یکی از این روش‌ها به شمار می‌رود و برای یادگیری آن، دوره آموزشی روش تقسیم و حل در طراحی الگوریتم پیشنهاد می‌شود. در این دوره، علاوه بر حل تشریحی تست‌های کنکور، نکات کنکوری نیز برای حل سریع‌تر بیان می‌شوند. نکاتی که در اکثر منابع کنکور نمی‌توان آن‌ها را پیدا کرد و حاصل بیش از ۱۵ سال تدریس کنکوری است. این دوره نزدیک به دو ساعت و توسط دکتر فرشید شیرافکن تدریس می‌شود.
این فیلم آموزشی دو فصل را در بر می‌گیرد که شما ۱۱ درس روش تقسیم و حل هستند. سرفصل‌های این دوره شامل روش تقسیم و حل در طراحی الگوریتم از جمله قضیه اصلی، مرتب سازی ادغامی، الگوریتم پارتیشن بندی، مساله انتخاب، الگوریتم انتخاب k امین عنصر (میانه میانه‌ها)، یافتن k امین کوچک ترین کلید و سایر موارد و بررسی تست‌های کنکور کارشناسی ارشد مبحث روش تقسیم و حل در طراحی الگوریتم می‌شوند.

  • برای مشاهده فیلم آموزش روش تقسیم و حل در طراحی الگوریتم (مرور – تست کنکور کارشناسی ارشد) + اینجا کلیک کنید.

فیلم آموزش طراحی الگوریتم

فیلم آموزش آموزش طراحی الگوریتم

درس طراحی الگوریتم، یکی از درس‌های مهم رشته کارشناسی کامپیوتر به حساب می‌آید و از درس‌های بسیار پر اهمیت این رشته است. در این فرادرس، طراحی الگوریتم در عین سادگی بسیار کامل آموزش داده می‌شود و اکثر مباحث و موضوعات مهم در آن پوشش داده شده‌اند. این دوره آموزشی با توجه به دو منبع مهم این درس یعنی کرمن و نیپولیتان جمع‌آوری شده و طول مدت این دوره نزدیک به ۱۵ ساعت است.
این فرادرس توسط دکتر فرشید شیرافکن تدریس می‌شود و هشت درس را در بر می‌گیرد. در بخش آخر درس دوم این دوره آموزشی، قضیه اصلی به طور کامل مورد بررسی قرار گرفته است. از جمله سرفصل‌های مهم این دوره، مرتبه اجرایی، رابطه‌های بازگشتی، روش تقسیم و حل، روش حریصانه، روش عقبگرد – روش شاخه و قید، الگوریتم‌های گراف و سایر موارد را شامل می‌شوند.

فیلم آموزش ساختمان داده ها

فیلم آموزش ساختمان داده ها

ساختمان داده‌ها، یکی از درس‌های مهم و پایه‌ای دانشگاه مخصوصا در مقطع کارشناسی است که پیش‌ نیاز درس‌های مختلف رشته کامپیوتر به حساب می‌آید. این درس مفاهیم مهمی را برای یادگیری درس طراحی الگوریتم ارائه می‌دهد و به عنوان مبحثی که نکات فراوانی دارد، در کنکور کارشناسی ارشد و دکتری کامپیوتر از درس‌های با ضرایب بالا است. برای یادگیری درس ساختمان داده‌ها، فیلم آموزش ساختمان داده‌ها، توسط دکتر فرشید شیرافکن پیشنهاد می‌شود. طول مدت این دوره نزدیک به ۱۱ ساعت است و این دوره ۹ درس را در بر می‌گیرد. برخی از سرفصل‌های این دوره مرتبه اجرایی، زیر برنامه‌های بازگشتی، صف و پشته، لیست پیوندی، درخت، گراف، مرتب‌سازی، درهم‌سازی و سایر موارد هستند.

فیلم آموزش رابطه های بازگشتی در طراحی الگوریتم و ساختمان گسسته (مرور – تست کنکور ارشد)

فیلم آموزش رابطه های بازگشتی در طراحی الگوریتم و ساختمان گسسته (مرور - تست کنکور ارشد) 

در این فرادرس رابطه‌های بازگشتی در طراحی الگوریتم و ساختمان گسسته که یکی از مفاهیم اصلی و سرفصل‌های کنکور کارشناسی ارشد و وزارت علوم برای درس ساختمان گسسته و طراحی الگوریتم هستند، مورد بحث قرار می‌گیرد. طول مدت این دوره نزدیک به دو ساعت و مدرس آن دکتر فرشید شیرافکن است. این فرادرس دو فصل را در بر می‌گیرد. فصل اول این دوره شامل رابطه‌های بازگشتی می‌شود و در این فصل قضیه اصلی در طراحی الگوریتم آموزش داده شده است و در فصل دوم آن به بررسی تست‌های کنکور کارشناسی ارشد مبحث رابطه‌های بازگشتی پرداخته می‌شود.

  • برای مشاهده فیلم آموزش رابطه های بازگشتی در طراحی الگوریتم و ساختمان گسسته (مرور – تست کنکور ارشد) + اینجا کلیک کنید.

جمع‌بندی

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

اگر این مطلب برای شما مفید بوده است، آموزش‌ها و مطالب زیر نیز به شما پیشنهاد می‌شوند:

بر اساس رای 9 نفر
آیا این مطلب برای شما مفید بود؟
شما قبلا رای داده‌اید!
اگر بازخوردی درباره این مطلب دارید یا پرسشی دارید که بدون پاسخ مانده است، آن را از طریق بخش نظرات مطرح کنید.

سیده مریم خلیل الهی دانش‌آموخته کارشناسی ارشد رشته مهندسی کامپیوتر، گرایش هوش مصنوعی از دانشگاه خوارزمی تهران است؛ به حوزه هوش مصنوعی و شبکه‌های عصبی علاقه دارد و در مجله فرادرس به عنوان تولیدکننده محتوا در زمینه‌های علوم کامپیوتر، برنامه‌نویسی و هوش مصنوعی فعالیت می‌کند.

نظر شما چیست؟

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *