اصول کامپیوتر ۱

اصول کامپیوتر ۱

اسلاید 1: اصول كامپيوتر 1الگوريتم، فلوچارت و برنامه

اسلاید 2: 2

اسلاید 3: 3الگوريتمالگوريتم: قدمهاي حل يك مسالهبرگرفته از نام ابومحمد بن موسي الخوارزميمولف كتاب الجبر و المقابلهدر كتب قديمي، بيشتر براي “الگوريتم اقليدس براي تعيين بزرگترين مقسوم عليه مشترك” بكار مي رفته است.

اسلاید 4: 4الگوريتم اقليدسالگوريتم اقليدس: دو عدد طبيعي m و n داده شده است. بزرگترين مقسوم عليه مشترك اين دو را پيدا كنيد.بزرگترين مقسوم عليه مشترك اعداد طبيعي m و n، بزرگترين عدد طبيعي است كه هر دوي m و n بر آن بخشپذير باشندعدد طبيعي N بر عدد طبيعي k بخشپذير است اگر، باقيمانده تقسيم N بر k صفر باشد

اسلاید 5: 5الگوريتم اقليدسE1: [find remainder] Divide m by n and let r be the reminder.(Clearly, 0 <=r <=n )E2: [it is zero?] if r =0 , the algorithm terminates, n is the answer E3: [Interchange] Set m  n , n  r and go back to step E1 ▐

اسلاید 6: 6flowchartE1:Find RemainderE2:Is it zeroE3: InterchangeYesNo

اسلاید 7: 7GW-Basic Program10 r = m mod n20 if r = 0 then print n : exit30 m=n : n= r : goto 10

اسلاید 8: 8الگوريتمهر الگوريتم اسمي دارد. در الگوريتم اقليدس، از E بعنوان اسم استفاده كرديم. اسم الگوريتم مي تواند بيش از يك حرف داشته باشد.قدمهاي هر الگوريتم با اين اسم و شماره ترتيب قدم نمايش داده مي شوندE1 و E2 و ....هر قدم عنوان كوتاهي دارد كه بطور خلاصه بيانگركاركرد آن قدم است.مثل find remainder

اسلاید 9: 9الگوريتم- عملگر انتسابمفهوم عبارت m n اين است كه مقدار فعلي m با مقدار موجود در n جايگزين شود به عملگر انتساب معروف استReplacement, Assignment, Substitutionمثال براي افزودن مقدار n به اندازه يك واحد، از عبارت n n+1 استفاده مي كنيماين عملگر خاصيت جابجايي ندارد. يعني m n با nm يكي نيست!جهت اين عملگر از راست به چپ است

اسلاید 10: 10الگوريتم- تست شرطمفهوم عبارت r=0 در قدم E2 اين است كه آيا عدد r برابر صفر است؟= به عملگر تست شرط معروف استEquality, Conditionدر برخي از زبانها مثل Basic از علامت (=) براي انتساب و تست شرط استفاده مي شودوظيفه برنامه نويس است كه كاربرد درست را استفاده كنداغلب زبانهاي پراستفاده، علايم متفاوتي براي عملگر انتساب و تست شرط استفاده مي كنند.

اسلاید 11: 11الگوريتم-پرشيك الگوريتم با دستوري كه كوچكترين شماره را دارد، شروع مي شود و اجراي دستورات به صورت ترتيبي ادامه مي يابد، مگر اينكه اجراي دستوري خارج از اين ترتيب صريحا قيد شوددر الگوريتم قبلي اجراي الگوريتم از E1 شروع مي شوددر قدم E2 در صورتي كه r=0 ، اجراي الگوريتم پايان مي يابد و دستور E3 اجرا نمي شوددر صورت اجراي دستور E3 اجراي الگوريتم از E1 ادامه مي يابدعلامت ▐براي نشان دادن پايان متن الگوريتم استفاده مي شود

اسلاید 12: 12الگوريتم-خلاصهيك الگوريتم داراي سه نوع دستور استانتسابشرطپرش و تكرارالگوريتم اقليدس، هر سه نوع دستور را داردتمام برنامه هاي كوچك و بزرگ از همين سه نوع دستور تشكيل يافته اندپيشنهاد Lovelace Ada

اسلاید 13: 13Lovelace AdaAugusta Ada King, Countess of Lovelace (Dec.10, 1815 – Nov 27, 1852), born Augusta Ada Byron, is mainly known for having written a description of Charles Babbages early mechanical general-purpose computer, the analytical engine(1842-1843). Click to read more in wikipedia

اسلاید 14: 14متغيرهاالگوريتمها معمولا تعدادي ورودي و حداقل يك خروجي دارندمتغيرها براي نگهداري مقادير مورد استفاده در الگوريتم استفاده مي شوندm، n و r متغيرهاي مورد استفاده الگوريتم اقليدس هستندبراي نمايش متغيرهاي ساده، از حروف الفباي لاتين استفاده مي شوندبا استفاده از انديس، متغيرهايي از جنس بردار و ماتريس را نيز مي توان نشان داد m1 نشان دهنده خانه اول بردار m است

اسلاید 15: 15شرايط يك الگوريتماجراي الگوريتم در هر صورت بايد پاياني داشته باشدالگوريتم اقليدس در هر بار اجرا، مقادير m , n كمتر مي شوند و نهايتا به صفر خواهند رسيد. بنابراين با اجراي E2 الگوريتم بالاخره پايان خواهد يافتتعريف دقيق: كار هر قدم الگوريتم بايد به صورت نا مبهم و دقيق تعريف شوداز عباراتي استفاده كنيد كه مطمئن شويد، خواننده معني دقيق آن را مي فهمدتعريف دقيق ورودي و خروجي

اسلاید 16: 16شرايط يك الگوريتم-ادامهكارايي: الگوريتم بايد هوشمندانه طراحي شده و از راه حلهاي كارا و قابل فهم براي انجام كارهاي مورد نظر استفاده كندقدم اول الگوريتم اقليدس را مي توان چنين نوشت:E1: [find remainder] Let r be m - n. بديهي است كه الگوريتم با اين تغيير دوباره درست كار خواهد كرد اما به دليل تكرار زياد عمل تفريق، الگوريتم كارايي سابق را نخواهد داشت

اسلاید 17: 17شرايط يك الگوريتم-ادامهدر عمل نه تنها به الگوريتم هاي پايان پذير نياز داريم، بلكه الگوريتم هايي را مي پسنديم كه در زمان معقول پايان يابندالگوريتم هاي خوب مورد نظر ماست!

اسلاید 18: 18تمرينچگونه مقادير دو متغير a و b را با هم جابجا مي كنيد؟بدون استفاده از حافظه كمكي اينكار را انجام دهيدچهار متغير (a,b,c,d) داده شده اند. مقادير اين متغير ها را به صورت (b,c,d,a) تغيير دهيد. يعني: مقدار جديد a برابر با مقدار قبلي b باشد مقدار جديد b برابر با مقدار قبلي c باشدمقدار جديد c برابر با مقدار قبلي d باشدمقدار جديد d برابر با مقدار قبلي a باشداينكار را با حداقل جابجايي ممكن انجام دهيد