جواب تشریحی

الگوریتم های تقسیم و غلبه(ِDivide and Conquer):

روش تقسیم و غلبه,یک روش بالا و پایین (Top-Down)است.برای حل یک نمونه مسأله کلی ابتدا با تقسیم آن مسأله به زیر مسأله های کوچک تر(قابل حل) تلاش برای حل زیر مسأله ها شروع شده و نهایتاََ مسأله کلی نیز با حل زیر مسأله ها حل می شود .اصولا این روش به یک الگوریتم بازگشتی منجر می شود.

📣👨‍💻 @AlgorithmDesign_DataStructuer

هرم(Heap):

غالبا هرم ها را براي پياده سازي صف اولويت به كار مي برند.
در اين صف ها اگر قرار باشد عنصري حذف شود اين عنصر، عنصري است كه در
بالاترين(پايين ترين) اولويت باشد.
تعريف: يك درخت حداكثر(حداقل) درختي است كه مقدار كليد هر گره آن
كمتر(بيشتر) از مقادير كليد فرزندانش(در صورت وجود) نباشد.

هرم حداكثر (Heap Max )يك درخت دودويي كامل است كه يك درخت
حداكثر نيز باشد به این معنی می باشد که باید هر والدی از فرزندان خوب بزرگتر باشد.

هرم حداقل(Heap Min )يك درخت دودويي كامل است كه يك درخت حداقل
نيز باشدبه این معنی می باشد یعنی باید هر والد از فرزندان خود کوچیک تر باشد.

📣👨‍💻 @AlgorithmDesign_DataStructuer

پیمایش Inorder :
در این روش پیمایش ابتدا زیر درخت سمت چپ و سپس ریشه و بعداً زیر درخت سمت راست بازدید می شود. همیشه باید به یاد داشته باشیم که هر گره ممکن است خود یک زیردرخت را نشان دهد.

نکته : اگر یک درخت باینری به ترتیب پیمایش شود، خروجی مقادیر کلیدی مرتب شده را به ترتیب صعودی تولید می کند.

📣👨‍💻 @AlgorithmDesign_DataStructuer

تصاعد حسابی به همراه اثبات آن

مرتب سازی(Sort):
عملیات مرتب سازی برای هر آرایه از دو عمل مقایسه و جابه جایی (تعویض) تشکیل می شود. قسمتی از عملیات مرتب سازی که مقایسه برا اساس آن انجام میشود کلید نامیده می شود.

📣👨‍💻 @AlgorithmDesign_DataStructuer

چرا یادگیری درس الگوریتم مهم است؟

سرعت پردازنده ها در سال 1369 حدود 386MHZبوده است. در حالی که سرعت کامپیوتر های کنونی حدودا برابر 3.86GHZمی باشد.
در طول 30 سال سرعت پرازنده ها تنها 10 برابر شده است و پیشرفت چندانی حاصل نشده است.آنچه باعث می شود سرعت بالا نظر برسد ارتفای نرم افزار است.
اگر سیگنال با سرعت نور در پردازنده جابجا شود حداکثر سرعت5GHZرا خواهیم داشت بنابراین تا حدی میتوان سخت افزار را ارتفاء داد. برای افزایش سرعت باید فاصله را کم کنیم و پردازنده های کوچک بسازیم که باعث میشود پردازنده تحت پردازش زیاد داغ کند و به مدارات آن آسیب برسد. بنابریان به جای ارتفاع سخت افزار باید به دنبال بهینه سازی الگوریتم باشم تا بتوانیم سرعت بیشتری را با استفاده از الگوریتم با هزینه کمتر بسازیم.

📣👨‍💻 @AlgorithmDesign_DataStructuer

فرمول به دست آوردن تعداد تکرار حلقه

📣👨‍💻 @AlgorithmDesign_DataStructuer

رشد توابع:
منظور از رشد توابع در توابع سعودی , یعنی اگر n را به سمت بی نهایت ببریم کدام تابع زود تر به سمت بی نهایت میل میکند و منظور از رشد توابع در توابع نزولی یعنی اگر n را به سمت بینهایت ببریم کدام تابع دیر تر به صفر میل میکند یا نزدیک می شود.

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

📣👨‍💻 @AlgorithmDesign_DataStructuer

برخی از انواع رایج پیچیدگی زمانی

📣👨‍💻 @AlgorithmDesign_DataStructuer

گراف(Graphs):

هر گراف شامل دو مجموعه V و E می باشد. Vمجموعه ای متناهی و غیر تهی از راس ها و E مجموعه ای است از زوج راس ها که یال نامیده می شود.

به ترتیب (G)V و (G)E مجموعه راس ها و مجموعه یال های گراف G را نمایش می دهند.
G=(V,E)
در گراف های بدون جهت زوج راس های که هر یال را نمایش می دهند مرتب نیستند:
(u,v) = (v.u)
محدویت هایی که برای گراف تعریف می کنیم:
1-یک گراف فاقد از یک یال راس مانند v به خودش است. چنین یال هایی را خود یالی(Self edge) یا خود حلقه ای (Self loop) نیز می گویند. اگر خود یالی در گراف مجاز باشد در آن صورت یم شی داده به نام گراف خود یالی حاصل می شود.

2-در یک گراف یک یال نباید چند بار ظاهر شود. اگر این محدودیت را در نظر بگیریم دارای شی داده ای به نام گراف چند گانه(MultiGraph)خواهیم بود.

📣👨‍💻 @AlgorithmDesign_DataStructuer

متد ()peekبرای نگاه کردن به شی در بالای این پشته بدون حذف آن از پشته استفاده می شود.
در زیر نحوه استفاده از آن را در برنامه میبینم:

int peek() {
return stack[top];
}

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

📣👨‍💻 @AlgorithmDesign_DataStructuer

یکی از مثال هایی که می توان برای روش تقسیم و غلبه زد دنباله فیبونانچی می باشد. این دنبال از جمع دو عدد قبلی خود به دست می آید که کابردی های زیادی در صنعت نیز دارد که می توان در رمز گذاری , هنر , علوم رایانه , و ... اشاره کرد.
البته این الگوریتم بازگشتی که در روش تقسیم و غلبه می باشد بهیه نمی باشد زیرا مجموعه هایی هستند که چندین بار تکرار می شود برای همین اگر از عدد های بالا بخواهیم از این دنباله استفاده کنیم باعث می شود اگر ما ران کنیم زمان زیادی طول بکشد که ران شود.

📣👨‍💻 @AlgorithmDesign_DataStructuer

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

📣👨‍💻 @AlgorithmDesign_DataStructuer

برای بدست آوردن سوالاتی که از تقسیم و غلبه به دست می آید باید عبارات زیر را به خاطر سپرده باشید.
1-Divide:
مشکل اصلی را به مجموعه ای از مسائل فرعی تبدیل می کند.
2-Conquer:
هر زیرمسئله را به صورت جداگانه و به صورت بازگشتی حل کنید.
3-Combine:
راه حل های زیرمسائل را کنار هم قرار دهید تا راه حل کل مسئله را به دست آورید.

📣👨‍💻 @AlgorithmDesign_DataStructuer