موسسه علمی پژوهشی فری تز

کامپیوتر الگوریتم و محاسبات

کامپیوتر الگوریتم و محاسباتReviewed by Admin on Sep 14Rating:

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

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

 

کامپیوتر الگوريتم چيست؟

الگوريتم و محاسبات

الگوريتم دنباله اي است از دستورات که با اجراي آنها، هدف خاصي برآورده ميشود. در هر الگوريتم موارد زير قابل بيان است:

 

ورودي : ميتواند الگوریتم ورودي داشته يا نداشته باشد.

 

خروجي : بايد حداقل يک خروجي داشته باشد.

 

قطعيت : هر دستور بايد واضح و خالي از هر نوع ابهامي باشد.

 

محدوديت : الگوريتم بايد پس از طي مراحل محدودي خاتمه يابد.

 

کارايي : هر دستور بايد انجام پذير باشد، يعني بتوان آنرا بصورت دستي و با قلم وکاغذ اجرا کرد.

 

تفاوت برنامه (Program) و الگوريتم آن است که برنامه لزوما محدود نيست. مثلا سيستم عامل برنامه اي است که دائما در يک

 

سيکل انتظار است تا برنامه بعدي را اجرا کند.

 

 

الگوریتم

براي ارزيابي کارايي يک الگوريتم، دو مسئله داراي اهميت است:

 

۱٫ زمان اجراي الگوريتم

 

۲٫ حافظه مورد نياز الگوريتم

 

از بين اين دو عامل زمان اجرا از اهميت بيشتري برخوردار است. زمان اجرا به عوامل متعددي بستگي دارد از جمله:

 

سخت افزار : مثلا سرعت پردازنده هاي مختلف فرق ميکند.

 

کامپايلر : مثلا برنامه هاي نوشته شده به زبان C معمولا از مشابه پاسکال خود سريعتر هستند.

 

اندازه ورودي :مثلا در مرتب سازي يک آرايه، هر چه تعداد عناصر آرايه بيشتر باشد، زمان اجرا بيشتر است.

 

ترکيب يا ترتيب ورودي : در بررسي الگوريتم ها معمولا سه حالت وجود دارد : بهترين حالت (Best case) ، حالت متوسط (Average

 

case) و بدترين حالت (Worst case). مثلا براي مرتب سازي يک آرايه، اگر آرايه از قبل مرتب باشد معمولا بهترين حالت است.

 

پيچيدگي الگوريتم : ممکن است براي يک مسئله الگوريتم هاي مختلف با زمانهاي مختلف وجود داشته باشد.

 

اگر n اندازه ورودي باشد، زمان اجراي الگوريتم برحسب n را معمولا با T(n) نشان ميدهيم. اگر الگوريتم بيش از يک ورودي داشته

 

باشد که اندازه هايشان مثلا n و m باشد، زمان را با T(n , m) يا T(m , n) نشان ميدهيم.

 

براي محاسبه زمان اجراي الگوريتم ميتوان تعداد اجراي همه خطوط را محاسبه کرد (گام شماري). البته در بسياري از موارد،

 

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

 

ها براي محاسبه مرتبه لازم نيست تعداد اجراي همه خطوط محاسبه شوند، بلکه تعداد اجراي جمله اصلي (معمولا جملات داخل

 

حلقه) مرتبه را مشخص ميکنند.

 

براي محاسبه تعداد اجراي جمله اصلي در حلقه هاي for که انديس هايشان ۱ واحد افزايش مي يابد، ميتوان از سيگما (?)

 

استفاده کرد. به اين صورت که به ازاي هر حلقه ? قرار دهيد و جمله داخل حلقه را ۱ بگذاريد.

 

 

در بسياري از الگوريتم ها، تعداد اجراي جمله اصلي، متفاوت است و به شرايط بستگي دارد. در اين صورت بهترين حالت، حالت

 

متوسط و بدترين حالت براي الگوريتم مطرح ميشود.

 

دیدگاه شما

( الزامي )

(الزامي)