چه طوری الگوریتم یک مسأله را پیدا کنید؟
سوالی که برای خیلی از ما پیش میاد اینکه برای حل یک سوال چه طوری باید الگوریتم آن را بدست بیاریم .راه حل برای بدست آوردن الگوریتم یک مسأله به صورت زیر میباشد:
1-ایده
2-پیاده کردن ایده
3-از درست بوده ایده اطمینان خاطر کنیم
4-پیچیدگی آن را بدست آوریم
5-بعد از انجام مراحل بالا با استفاده از یکی از زبان های برنامه نویسی آن را تست کنیم

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


📣👨‍💻 @AlgorithmDesign_DataStructuer

جواب:
همان طور که مشاهده می کنید جواب گزینه 1 می باشد.
الگوریتم های بازگشتی دارای مزایای زیادی هستند به همان صورت هم دارای معایبی هستند که از آن ها میتوان به اتلاف حافظه یعنی فضای زیادی را اشغال میکنند,عدم بهینه بودن آن ها یعنی ما میتوانم آن مسأله را با الگوریتم بهینه تر با هزینه کمتر حل کنیم ,همچینن میتوان به زمان اجرای بالای آن ها پرداخت که بعضی از الگوریتم های بازگشتی زمان اجرای زیادی دارند و ممکن است هزینه زیادی برای ما داشته باشد.

📣👨‍💻 @AlgorithmDesign_DataStructuer

صف(Queue):

صف یک ساختار داده انتزاعی است که تا حدودی شبیه به Stacks است. برخلاف پشته ها، یک صف در هر دو انتهای آن باز است. یک سر همیشه برای درج داده ها (enqueue) و دیگری برای حذف داده ها (dequeue) استفاده می شود. صف از First-In-First-Out پیروی می کند، به عنوان مثال، آیتم داده ای که ابتدا ذخیره شده است، ابتدا قابل دسترسی خواهد بود.
یک مثال واقعی از صف می تواند یک جاده یک طرفه تک خطی باشد، جایی که وسیله نقلیه ابتدا وارد می شود، اول از آن خارج می شود. نمونه های واقعی بیشتری را می توان به عنوان صف در پنجره های بلیط و ایستگاه های اتوبوس مشاهده کرد.

📣👨‍💻 @AlgorithmDesign_DataStructuer

جست و جوی خطی در ارایه ها:
تابع بالا مقدار Xرا در آرایه n عنصریA ,به روش مقایسه تک تک عناصر آرایه , جست و جو می کند .در صورت وجود اندیس آرایه (خانه حاوی X) و در صورت پیدا نکردن آن عدد1- را بر می گرداند.

📣👨‍💻 @AlgorithmDesign_DataStructuer

جواب تشریحی

الگوریتم های تقسیم و غلبه(ِ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