X
تبلیغات
الگوریتم

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

در اينجا دو تعريف را براي الگوريتم بيان مي‌كنيم:

۱- مجموعه‌ای خاص از روال منطقی و یا ریاضی ساده و خوب تبیین شده می‌باشد که می‌تواند در حل یک مسئله مشخص کمک کند. الگوریتم دستورالعملی برای یافتن پاسخ درست یک مساله سخت به وسیله شکستن آن مساله به مراحل ساده و آسان می‌باشد .
۲- هر روال محاسباتی خوش تعریفی است که مقداری, یا مجموعه‌ای از مقادیر را بعنوان ورودی می‌گیرد و مقداری, یا مجموعه‌ای از مقادیر را بعنوان خروجی تولید می‌کند. بنابراین یک الگوریتم یک توالی از گام‌های محاسباتی است که ورودی را به خروجی تبدیل می‌کند.
یک الگوریتم یابد سه شرط اساسی زیر را تأمین کند :

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

مثلا اين جوك معروف را در نظر بگيريد:

مي دوني يک فيل را چطوري با سه حرکت مي گذارند توي يخچال؟ اول در يخچال را باز مي کنند، بعد فيل را مي گذارند توش، بعد هم در يخچال را مي بندند.

شايد جواب اين جك ظاهرا يك الگوريتم باشد، اما اينطور نيست چون ويژگي دوم يعني قابل اجرا بودن را ندارد.

بررسی الگوریتم و مراحل پنج گانه برنامه نویسی:

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

الگوريتم های ميکرو در مقابل ماکرو
الگوريتم ها دارای ويژگی های متفاوتی می باشند . ما می توانيم در رابطه با  الگوريتم  استفاده شده  به منظور نوشتن يک برنامه مشخص صحبت نمائيم . از اين زاويه  ، ما  صرفا" در رابطه با الگوريتم  در سطح ماکرو(macro level)  ، صحبت نموده ايم . در چنين مواردی ، الگوريتم ارائه شده ، سعی در بدست آوردن جنبه های عمومی برنامه از طريق يک مرور کلی به برنامه در مقابل درگير شدن در جزئيات را  دارد.ما می توانيم در رابطه با الگوريتم ها ، از سطح "ميکرو" صحبت نمائيم . از اين زاويه ، به سطوح پايين تر رفته و به عوامل اساسی ونگهدارنده ای  که يک جنبه خاص از برنامه را با  يکديگر مرتبط می نمايد، صحبت کرد.  مثلا" در صورتيکه شما دارای داده هائی هستيد که می بايست قبل از استفاده  مرتب گردند ،الگوريتم های مرتب سازی متعددی در اين زمينه وجود داشته و  می توان يکی از آنها را بمنظور تامين اهداف مورد نظر خود انتخاب نمود. انتخاب يک الگوريتم مرتب سازی  ، صرفا" باعث حل شدن يکی از جنبه های متفاوت برنامه می گردد . پس از مرتب سازی داده ها ،می بايست از يک الگوريتم ميکرو ديگر بمنظور نمايش  داده  ها ی مرتب شده استفاده  گردد .
همانگونه که احتمالا" حدس زده ايد ، ما می توانيم تمام الگوريتم های ميکرو را بمنظور ايجاد يک الگوريتم ماکرو ، جمع آوری نمائيم . اگر ما با الگوريتم های ميکرو ، آغاز نمائيم ، و حرکت خود را بسمت نمايش ماکروی يک برنامه ، پيش ببريم ، کاری را انجام داده ايم که موسوم به طراحی " پايين به بالا" (buttom-up)  ، است . اگر ما فعاليت خود را با يک الگوريتم ماکرو آعاز و حرکت خود را بسمت پائين و الگوريتم های ميکرو ، ادامه دهيم ، طراحی از نوع " بالا به پايين " (top-down)  را انجام داده ايم .
شايد اين سوال مطرح گردد که  کدام روش بهتر است ؟ اگر شما تمام مقالاتی را که تاکنون در اين زمينه نوشته شده اند را  دنبال نمائيد ، هرگز به يک نتيجه قابل قبول دست نخواهيد يافت . هر رويکرد، دارای نکات مثبت و منفی مربوط به خود است . صرفنظر از رويکرد طراحی استفاده شده ، می بايست دارای الگوئی (طرحی) مناسب برای برنامه باشيم .حداقل، نيازمند يک اعلاميه از مسئله برنامه نويسی و يک طرح ( الگو) برای برخورد با مسئله ، خواهيم بود . پس از شناخت مسئله ، می توان  نحوه حل مسئله را  ترسيم کرد.  شناخت عميق و مناسب نسبت به  مسئله ای که قصد حل آن را داريم ، شرط اساسی و ضروری برای طراحی يک برنامه است .
با توجه به اينکه اين اعتقاد وجود دارد که شناخت جامع و کلی از مسئله ای که حل آن را داريم ، بخشی ضروری در اولين مرحله برنامه نويسی است ، ما در ادامه از رويکرد "بالا - پايين "، تبعيـت می نمائيم . فراموش نکنيم که  رويکرد فوق ، امکان مشاهده مجازی از هر مسئله برنامه نويسی را فراهم خواهد نمود.

مراحل پنج گانه
هر برنامه را صرفنظر از ميزان پيچيدگی آن ، می توان  به  پنج مرحله اساسی تجزيه کرد :

  • مقدار دهی اوليه

  • ورودی

  • پردازش

  • خروجی

  • پاکسازی

در ادامه به بررسی هريک از مراحل فوق ، خواهيم پرداخت .

مرحله مقداردهی اوليه
مرحله مقداردهی اوليه ، اولين مرحله ای است که می بايست در زمان طراحی يک برنامه  در رابطه با آن فکر کرد . مرحله فوق ، شامل تمامی عمليات مورد نيازی  است که برنامه می بايست قبل ازبرقراری ارتباط  با کاربر ، انجام دهد . در ابتدا ممکن است اين موضوع که عملياتی را قبل از برقراری  ارتباط با کاربر می بايست انجام داد ، تا اندازه ای عجيب بنظر رسد ولی احتمالا" برنامه های زيادی را مشاهده نموده ايد که در اين راستا عمليات مشابهی را انجام می دهند. مثلا" ،  در زمان استفاده از برنامه هائی نظير Word ، Excel و يا برنامه های مشابه ديگر ، با چنين مواردی برخورد نموده ايم . مثلا"  با انتخاب  گزينه منو File ، می توان  ليستی از فايل هائی را که با آنها کار کرده ايم در بخش انتهائی منوفوق ، مشاهده کرد. ( مشاهده آخرين فايل های  استفاده شده در يک برنامه خاص ، با استفاده از جادو! ميسر نشده است ) . برنامه مورد نظر شايد ، ليست فايل های اخير را از ديسک خوانده و آنها را به ليست مربوطه در منوی File ، اضافه کرده باشد . با توجه به اينکه ليست فايل های فوق ، می بايست  قبل از اينکه برنامه هر چيز ديگر را برای کاربر نمايش دهد ، خوانده و نمايش داده شوند ، می توان انجام عمليات فوق را نمونه ای از مرحله مقداردهی اوليه، در نظر گرفت.
يکی ديگر از عمليات متداول که به اين مرحله مرتبط می باشد ، خواندن فايل های Setup است . چنين فايل هائی ممکن است حاوی اطلاعاتی در رابطه با نام مسيرهائی باشند که بانک ها ی اطلاعاتی خاصی و يا فايل های  ذخيره شده  ديگری را  بر روی ديسک را مشخص می نمايند . با توجه به نوع برنامه ای که اجراء می گردد ، فايل های Setup می توانند شامل اطلاعاتی در رابطه با فونت های نمايش ، نام و محل چاپگر ، رنگ های زمينه و رويه ، وضوح تصوير صفحه نمايشگر و اطلاعات مشابهی ديگر باشند . ساير برنامه ها ممکن است مستلزم خواندن اطلاعاتی در رابطه با اتصالات شبکه ، مجوزهای امنيتی و دستيابی به اينترنت ، رمزهای عبور و ساير اطلاعات حساس ديگر باشند . در چنين مواردی فايل های Setup دارای نقشی مهم خواهند بود.
در زمان طراحی يک برنامه ، همواره  می بايست در رابطه با اطلاعاتی که يک برنامه قبل  آغاز خدمات و عمليات خود  به آنها نيازمند است ، انديشيد و برای آنان در مرحله مقداردهی اوليه راهکار مناسب را انتخاب کرد . مرحله مقداردهی اوليه احتمالا" جائی است که می بايست از طريق آن اقدام به ارائه راهکار مناسب در جهت پاسخ به نيازهای فوق ، کرد.

مرحله ورودی
مرحله ورودی ، در حقيقت چيزی است که انتظار داريد باشد! مرحله فوق ،  شامل اخذ ( جمع آوری ) هر آنچيزی است که يک برنامه برای انجام فعاليت های خود به آنها  نياز خواهد داشت . دراکثر موارد، اگر استنباط مناسبی از عملياتی را که يک برنامه قصد انجام آنان  را دارد ، حاصل گردد، مشخص نمودن ليستی از ورودی ها ، کاری ساده خواهد بود. مثلا" اگر شما قصد نوشتن يک برنامه  وام را داريد ، می دانيد که می بايست از کاربر ميزان وام درخواستی ، بهره موردنظر و مدت  زمان وام ، درخواست گردد.
در حالات ديگر، لازم است در رابطه با نوع  ورودی هائی  که می بايست از کاربر اخذ گردد، بررسی لازم و مبتنی بر انديشه را دنبال نمود. مثلا" در صورتيکه قصدنوشتن يک برنامه دفترچه آدرس را داريد ، آيا می خواهيد نام فايل حاوی  دفترچه تلفن و محل ذخيره فايل مربوطه را در هر مرتبه که برنامه اجراء می گردد ، از کاربر درخواست نمائيد ؟ بعبارت ديگر برخی از مراحل ورودی می توانند و شايد می بايست ، توسط مرحله مقدار دهی انجام شوند. ماهيت واقعی ميزان اطلاعاتی که  می توان آنها را  در مرحله مقداردهی  خواند ، بستگی به رفتار  برنامه دارد. بعنوان يک قانون عمومی می توان به اين مورد اشاره داشت که اکثر کاربران تمايل دارند که اطلاعات تکراری در يک فايل  Setup و يا مقداردهی اوليه ذخيره گردد (در مقابل اينکه هر مرتبه که برنامه اجراء می گردد ، مجبور به ورود اطلاعات تکرای باشند ) .
فايل های Setup بسيار مناسب بوده و در هرموردی که امکان بخدمت گرفتن آنان منطقی بنظر می آيد ، می بايست از آنان استفاده گردد . برخی ديگر از اطلاعات اوليه دارای ماهيت خاص خود بوده و تا زمانيکه کاربر آنها را تايپ ننمايد ، شناخته نمی گردند .  در مثال وام اشاره شده  ،  می توان از TextBox های متعددی بمنظور احذ اطلاعات از کاربر و استفاده  از آنان در برنامه ، کمک گرفت . با توجه به اينکه کاربر می بايست با اين TextBox ها مرتبط تا اطلاعات موردنياز برنامه را وارد نمايد ، روشی را  که شما بمنظور ارائه  Textbox ,Labels ,Menus و ساير عناصر برنامه ، استفاده  می نمائيد ، يکی از بخش های مهم يک برنامه يعنی رابط کاربر ( user interface ) را مشخص خواهد کرد . فراموش نکنيم يکی از عوامل موفقيت هر نرم افزار ، بخش رابط کاربر آن  است . طراحی مناسب بخش فوق ، امروزه بعنوان تخصصی خاص در طراحی و پياد ه سازی نرم افزار مطرح و دارای جايگاه خاص خود است .

مرحله پردازش
مرحله پردازش ، شامل انجام عمليات  بر روی ورودی (ورودی ها ) ، بمنظور توليد نتايج مورد نظر برای برنامه است . در مثال وام ، برنامه پس از دريافت ورودی های مورد نظر ( ميزان وام ، درصد بهره و زمان وام ) آنها را از طريق يک معادله مالی بيکديگر مرتبط و پس از حل معادله ، نتيجه  مورد نظر حاصل خواهد شد( ميزان پرداخت ماهانه ) . بعبارت ديگر ، مرحله پردازش قادر به دريافت ورودی ، برخورد با آنها و توليد  پاسخ  مناسب به مسئله است . توجه داشته باشيد که مرحله پردازش همواره باعث نمايش چيزی بر روی نمايشگر نخواهد شد. هدف ، عمل ( عمليات )  برروی داده ( داده ها )  بمنظور توليد يک نتيجه ( نتايج )  است . در اين رابطه هيچگونه استثنائی وجود ندارد . در صورتيکه در برنامه ای از قبل می دانيم که مرحله پردازش زمان زيادی طول خواهد کشيد ، منطقی است  که فيدبک های لازم  بمنظور آگاهی کاربر از ميزان و درصد انجام پردازش ( پردازش ها )  در اختيار وی گذاشته شود ( در زمانيکه برنامه در حال اجراء است )  . در اين رابطه می توان از روش های متعددی استفاده کرد . ( ارائه يک ميله پيشرفت ، برآورد زمان تقريبی بمنظور اتمام عمليات ) .

مرحله خروجی
 مرحله فوق ، پاسخ ( پاسخ ها ی) مناسب و مورد انتظار را به کاربران مبنی بر حل مسئله مورد نظر ، ارائه می نمايد. تعداد زيادی ازبرنامه ها ، پاسخ  نهائی ( نتيجه ) خود را از طريق  يک Textbox ، نمايش و در اختيار کاربر قرار می دهند . ، مثلا" اگر برنامه ای نوشته شده است که قصد محاسبه و نمايش ميزان پرداخت ماهيانه يک وام دريافتی را داشته باشد ، می توان نتيجه بدست آمده (پرداخت ماهانه) را از طريق  يک textbox ، ارائه تا  پاسخی مناسب در ارتباط با  مرحله خروجی يک برنامه، داده شده باشد . ساير برنامه ها ممکن است دارای وضعيتی بمراتب پيچيده تر باشند .مثلا" می توان برنامه ای را در نظر گرفت که  نام ، آدرس ، شماره تلفن و ساير اقلام اطلاعاتی را از بانک اطلاعاتی خوانده و در ادامه آنها را بر روی صفحه نمايشگر ، نشان دهد. برنامه هائی اينچنين ، نيازمند شکل مناسبتری از نمايش خروجی بوده و نمی توان با استفاده از چند textbox به خواسته خود دست يافت ( ارائه يک خروجی مطلوب و انعطاف پذير) در اينگونه موارد می بايست از راهکارهای مناسبتری استفاده گردد . مثلا" می توان از جداول خاصی بمنظور نمايش اطلاعات مورد نظر استفاده کرد .( استفاده از grid و يا List box  که برنامه در صورت ضرورت آنان را تکميل نمايد ) . نکته مهمی که می بايست در رابطه با مرحله خروجی رعايت گردد ، آگاهی از اين موضوع است که با توجه به نمايش نتايج خروجی برای کاربر، بخش فوق را می توان جزئی از بخش رابط کاربر يک نرم افزار در نظر گرفت . در زمان ورود اطلاعات ( مرحله ورودی )  از عناصر متفاوتی بمنظور اخذ اطلاعات توسط کاربر در بخش رابط استفاده می گردد ، در مرحله خروجی ، بخش رابط کاربر با کاربر بگونه ای  ديگر مرتبط خواهد شد ( ارتباطی بمراتب غير فعالتر نسبت به مرحله ورود اطلاعات  ) .

مرحله پاکسازی  ( Cleanup )
مرحله پاکسازی ، بمنظور خاتمه بخشيدن مودبانه يک برنامه، پس از تکميل عمليات مربوطه است. می توان اين مرحله را بعنوان مکمل مرحله مقداردهی اوليه در نظر گرفت .با اينکه تعداد زيادی از برنامه های ساده قادرند بسادگی و بدون انجام عمليات تکميلی توسط برنامه نويس ، خاتمه يابند ولی برنامه های پيچيده زيادی نيازمند برخی کمک ها در اين زمينه می باشند. مثلا" اگر برنامه ای يک فايل Setup را بمنظور مقداردهی برخی از متغيرها در زمان مرحله مقداردهی اوليه ، خوانده باشد ، مرحله پاکسازی می تواند شامل بهنگام سازی آندسته از متغيرهای موجود در فايل Setup باشد که نشاندهنده  آخرين اطلاعات کاربر است . مرحله پاکسازی ، اغلب شامل بستن فايل ها ( فايل های Setup و بانک اطلاعاتی)  است . برخی برنامه ها ميزان استفاده از برنامه توسط کاربران  را ثبت و اطلاعات مربوطه را در مکانهائی  که Log file ناميده می شوند ، ذخيره می نمايند( ثبت مشخصات افراديکه برنامه را اجراء نموده  بهمراه ساير اطلاعات مرتبط نظير  تاريخ و زمان آغاز و توقف برنامه ، در خيلی از برنامه ها به امری ضروری تبديل شده است ) .
يکی ديگر از انواع فايل های Log به  فايل های ثبت خطاء برمی گردد( error log file ) . هدف اين نوع از فايل ها ، ثبت اطلاعاتی در رابطه با هر نوع خطائی است که ممکن است در مدت زمان اجرای يک برنامه ، محقق گردد. برنامه نويسان با استفاده از محتويات اين نوع فايل ها ، قادر به اشکال زدائی برنامه خواهند بود .
عمليات واقعی و مورد نظری که می بايست در مرحله پاکسازی ، انجام گردد ، به نيازهای يک برنامه بستگی خواهد داشت . معمولا" اگر در برخی برنامه ها عمليات خاصی را در مرحله مقدار دهی اوليه انجام می هيم ، می بايست برخی از عمليات متناظر با آنان را  در مرحله پاکسازی انجام داد . باز نمودن و بستن فايل های مورد نياز در يک برنامه ، نمونه ای متداول از دو مرحله فوق می باشد .

آيا هر برنامه شامل پنج مرحله گفته شده است؟
در پاسخ به سوال فوق می بايست با صراحت پاسخ منفی داده شود. در اين راستا ، برنامه های متعددی وجود دارد که مثلا" به مراحل مقداردهی اوليه و يا پاکسازی ، نياز نخواهند داشت . مراحل مقداردهی اوليه و پاکسازی در مرحله طراحی برنامه های پيچيده مورد توجه جدی قرار خواهند گرفت. بموازات افزايش تجربه در نوشتن برنامه ، شناخت مناسبی در اين رابطه  بوجود می آيد(  کدام برنامه به تمام مراحل پنج گانه نياز و کداميک نياز ندارند).طراحان می بايست همواره يک مسئله  برنامه نويسی را با فرض وجود پنج مرحله ياد شده ،دنبال نمائيد . قطعا" حذف يک مرحله در  زمان طراحی بمراتب ساده تر از ناديده گرفتن ! اوليه آن خواهد بود.

پالايش يک طرفه   (  Sideways Refinement )
همانگونه که قبلا" اشاره گرديد ، ما علاقه مند به طراحی بالا به پايين می باشيم .( الگوريتم ماکرو بعنوان يک نقطه شروع در فرآيند طراحی برنامه) . پس از انتخاب رويکرد فوق  ، می بايست شناخت مناسبی نسبت به مسئله ای که قصد حل آن وجود دارد ، ايجاد گردد. تا رسيدن به  سطح ميکرو( ارائه الگوريتم های ميکرو) بمنظور حل مسئله مورد نظر راه زيادی را در پيش خواهيم داشت. بموازات حرکت از سطح مرور کلی برنامه به خصوصيات و ويژگی های يک برنامه ، می بايست دانش خود را نسبت به جرئيات مربوطه افزايش داد .
از پنج مرحله گفته شده ، می توان بمنظور نقطه شروع ديد ماکرو خود در زمان فرآيند طراحی استفاده کرد. درادامه ، می توان هر يک از مراحل را بدقت بررسی تا  جزئيات بيشتری در رابطه با مرحله مورد نظر ، مشخص گردد ( استخراج جزئيات لازم در رابطه با تحقق هر مرحله ) .  فرآيند  فوق ، " پالايش يک طرفه " ، ناميده می شود . در ادامه ، بمنظور شناخت مناسب فرآيند پالايش يک طرفه  ، به بررسی يک نمونه می پردازيم .
فرض کنيد ، کاربری دارای  يک فايل بانک اطلاعاتی است که در آن تمام قرار ملاقات های وی ، ذخيره شده اند . قرار ملاقات ها در بانک اطلاعاتی با نظم و ترتيب خاص ( تاريخ قرار ملاقات ) ذخيره شده اند . کاربر ، می خواهد قادر به مشاهده قرار ملاقات های خود بر اساس حروف الفبائی و بر اساس نام خانوادگی اشخاص مورد نظری که قصد ملاقات با  وی را دارند ، باشد. چگونه می توان از پالايش يک طرفه ، بمنظور طراحی يک را ه حل استفاده کرد؟

شبه کد ( Pseudo Code )
عمليات پالايش را می توان در رابطه با هر مرحله  با استفاده از "شبه - کد " ، دنبال کرد. شبه کد ،الگوريتمی برای بيان عملياتی است که می بايست  توسط يک روتين محقق گردد . در اين راستا از يک گرامر مشابه انگليسی ، استفاده می گردد . مثلا"  شبه کد ، روتين IsValidUser بصورت زير خواهد بود:

شبه کد روتين IsvalidUser                           

Is ValidUser()
  If  CurrentUserName Not in ValidUserList
        Display Invalid User Error Message
        Terminate Program
  Else
       Return ValidUserIDNumber
End

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

در بخش دوم اين مقاله ،  با متدولوژی UML)Unified Modeling Language ) آشنا خواهيم شد. UML ، يک متدولوژی  طراحی  متداول خصوصا" در زمينه  برنامه نويسی شی گراء است.

در حالت کلی الگوريتم ها بايد ويژگی های زير را داشته باشند:

الف) الگوريتم بايد ما را به نتيجه مورد نظر برساند.
ب) در زمان محدود پايان يابد.
ج) دستورالعملها بايد به ترتيب منطقی پشت سرهم قرار گيرند.
د) جملات الگوريتم ها بايد به صورت امری ، سؤالی باشند.
ه) هر الگوريتم بايد نقطه آغاز و پايان داشته باشد.

 مثال : الگوريتمی بنويسيد که دو عدد از ورودی دريافت شود و سپس تعيين شود که مجموع دو عدد بزرگتر از 20 است يا نه.

0- شروع .
1- دو عدد a و b را از ورودی در يافت کن.
2- a+b را محاسبه کن.
3- آيا a+b>20 است؟ اگر بلی به مرحله 6 برو.
4- بنويس خير.
5- به مرحله 7 برو.
6- بنويس بلی.
7- پايان.

 با برنامه ريزی و ساماندهی دقيق می توان به راه حلی مناسب جهت حل يک مسئله به کمک کامپيوتر رسيد. هرگونه کم توجهی و بی دقتی در نوشتن الگوريتم ضمن بروز مشکلات بسيار، برنامه نويس را نيز از هدف خود دور خواهد کرد؛ لذا برای به هدف رسيدن بايد درک صحيح و کاملی از صورت مسئله داشت و سپس راه حل مورد نظر را به صورت الگوريتم بنويسيم. و در نهايت الگوريتم مورد نظر را به زبان برنامه نويسی مورد نظر تبديل کنيم. برای درک بهتر شيوه حل مسائل و نوشتن الگوريتم به مثالهای زير توجه کنيد:

 مثال : الگوريتمی بنويسيد که مجموع اعداد طبيعی مضرب 7 و کوچکتر از 50 را حساب کند.

برای نوشتن اين الگوريتم به دو خانه حافظه نياز داريم.

0- شروع.
1- در خانه حافظه sum عدد صفر را قرار بده.
2- در خانه حافظه index عدد 7 را قرار بده.
3- مقدار index را با مقدارsum جمع کن
و حاصل را در sum قرار بده.
4- مقدار 7 را با مقدار index جمع کن
و حاصل را در index قرار بده.
5- آياindex بزگتراز 50 است،اگر خير به مرحله 3 برو.
6- محتوای sum را چاپ کن.
7- پايان.

 در الگوريتم فوق همانند شکل مقادير حافظه sum و index تغيير می کند، تا اينکه سرانجام شرط " آيا index بزرگتر از 50 است " بلی می شود لذا محتوای sum در خروجی چاپ خواهد شد و الگوريتم به پايان می رسد. اما در مراحل قبلی شرط فوق خير می باشد، لذا همانند شکل فوق الگوريتم ادامه پيدا می کند.

 مثال : الگوريتمی بنويسيد که 1000 عدد را از ورودی دريافت کرده و کوچکترين را چاپ کند.

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

0- شروع.
1- min را دريافت کن.
2- i =1 .
3- a را دريافت کن.
4- اگر a
5- i = i + 1 .
6- اگر i>=1000 به مرحله 8 برو.
7- به مرحله 3 برو.
8- min را چاپ کن.
9- پايان.

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

 مثال : الگوريتمی بنويسيد که سه عدد از ورودی دريافت شود و تعيين شود که اين اعداد می توانند اضلاع مثلث باشند يا خير.

0- شروع.
1- a وb وc را از ورودی بگير.
2- اگر a>b+c به 7 برو.
3- اگر b>a+c به 7 برو.
4- اگرc>a+b به 7 برو.
5- بنويس " بلی ".
6- به 8 برو.
7- بنويس " خير ".
8- پايان.

 در عمل برای نمايش الگوريتم از يک فلوچارت ( شمای جريان عمليات ) استفاده می شود. در حقيقت فلوچارت روش تصويری و استاندارد نمايش الگوريتم است.

 *در رسم فلوچارت علائم و نمادهای استانداردی به کار می رود که هر کدام دارای معانی ويژه ای هستند:

*از شکل بيضی افقی برای شروع و پايان عمليات استفاده می شود.

*از شکل مستطيل برای نمايش مراحل پردازشی استفاده می شود و در داخل آن عمل مورد نظر نوشته می شود. اين نماد ممکن است چندين ورودی داشته باشد ولی تنها يک خروجی دارد.

*از متوازی الاضلاع برای نشان دادن ورودی يا خروجی استفاده می شود.

 

 

  

 

 

 

+ نوشته شده توسط در چهارشنبه پانزدهم اردیبهشت 1389 و ساعت 13:11 |

الگوریتم زمانبندی HRRN

          زمانبندی Highest Response Ratio Next) HRRN) نوعی زمانبندی انحصاری است که بعضی از مشکلات SJF را برطرف می‌سازد. در SJF نظر افراطی خوبی نسبت به کارهای کوتاه و برعکس نظر افراطی بدی نسبت به کارهای طولانی وجود دارد به طوری که ممکن است مشکل قحطی زدگی رخ دهد. در این زمانبندی اولویت ها دینامیک است.
کارهای کوتاهتر اولویت بیشتری داشته و زودتر اجراء می‌شوند. کارهای طولانی نیز که مدت زیادی در صف انتظار بوده اند اولیت بیشتری کسب کرده وبالاخره در یک زمان معین اجراء می‌شوند. بدین ترتیب مشکل قحطی زدگی برطرف می‌شود.

 

فرمول تشخیص بالاترین پاسخ :  R=((w+s)/s)

  W=  زمان انتظار برای پردازنده

S   =  زمان خدمت مورد انتظار

R   = نسبت پاسخ

 

مثال)

 

 

حل:

علامت # تعداد اجراها

علامت -  تعداد انتظارها

فرایند های درخواست کننده در زمان 0:

P0

به دلیل اینکه فرآیندی با فرایند P0 در حال رقابت نیست پس بدون استفاده از فرمول (R=((w+s))/s) فرایند P0 تا آخر اجرا شده و تمام می شود.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

#

#

#

P0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

-

P1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

20

19

18

17

16

15

14

13

12

11

10

9

8

7

6

5

4

3

2

1

0

 

همانطور که مشاهده می کنید فرایند P1 در زمان 2 وارد شده و منتظر تمام شدن زمان اجرای P1 می باشد

به دلیل اینکه به جز فرایند P1  فرایند دیگری وارد صف نشده است پس فرایند P1 هم به صورتی که در شکل زیر نشان داده شده اجرا شده و تمام می شود

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

#

#

#

P0

 

 

 

 

 

 

 

 

 

 

 

#

#

#

#

#

#

-

P1

 

 

 

 

 

 

 

 

 

 

 

 

 

-

-

-

-

-

P2

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

-

-

-

P3

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

-

P4

 

 

 

 

 

 

 

 

20

19

18

17

16

15

14

13

12

11

10

9

8

7

6

5

4

3

2

1

0

 

در این قسمت مشاهده می شود که سه تا فرایند P2,P3,P4 می خواهند اجرا شوند در این مرحله باید با استفاده از فرمول

 (R=((w+s))/s) فرایندی که بیشترین نسبت پاسخ(بیشترین مقدار R) را دارد را پیدا کنیم و آن فرایند از بین سه تا فرایند زودتر اجرا می  شود

حل:

P2:

 

W=5

S=4

          R=(w+s)/s è (5+4)/4 è R(P2)=2.25

P3:

 

W=3

S=5

          R=(w+s)/s è (3+5)/5 è R(P3)=1.6

P4:

 

W=1

S=2

          R=(w+s)/s è (1+2)/2 è R(P4)=1.5

 

همانطور که مشاهده می کنید فرایند P2 بیشترین نسبت پاسخ را دارد پس زود تر از همه اجرا می شود

 

 

 

دوباره نسبت پاسخ را بین دو فرایند باقیمانده(P3,P4) پیدا می کنیم

 

حل:

P3:

 

W=7

S=5

          R=(w+s)/s è (7+5)/5 è R(P3)=2.2

P4:

 

W=5

S=2

          R=(w+s)/s è (5+2)/2 è R(P4)=3.5

 

همانطور که ملاحظه می کنید فرایند P4 نسبت پاسخ بیشتری نسبت به فرایند P3 دارد وبه دلیل اینکه فرایند دیگری به جز این دو فرایند وجود ندارد اول فرایند P4 و سپس فرایند P3 به صورت زیر اجرا می شود.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

#

#

#

P0

 

 

 

 

 

 

 

 

 

 

 

#

#

#

#

#

#

-

P1

 

 

 

 

 

 

 

 

 

#

#

#

#

-

-

-

-

-

P2

 

 

 

 

#

#

#

#

#

-

-

-

-

-

-

-

-

-

P3

 

 

 

 

 

 

 

 

 

 

 

#

#

-

-

-

-

-

P4

 

 

 

 

 

 

 

 

20

19

18

17

16

15

14

13

12

11

10

9

8

7

6

5

4

3

2

1

0

 

خصوصیات الگوریتم HRRN:

 

·        تابع انتخاب:max(w+s/s)

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

·        توان عملیاتی: زیاد

·        زمان پاسخ: خوب

·        سربار: می تواند زیاد باشد

·        تاثیر بر روی فرآیند ها: توازن مناسب

·        گرسنگی: خیر

الگوریتم FeedBack (FB):

ااگر هیچ نشانه ای از طول نسبی فرایندها متفاوت نداشته باشیم هیچ یک از روشهای  HRRN ; SRT ; SPN را نمی توان بکار برد.

کار این الگوریتم به این صورت است که بر اساس قبضه کردن صورت می کیرد و از راهکار اولویت دهی پویا عمل می کند

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

 

پردازنده

CPU

RQ0

RQ1

RQn

آزاد سازی

قبضه کردن

صف مسدود

 

 در این روش فرایند هایی که کوتاه هستند زود تر اجرا می شوند و بدون این که به صف های بعدی(کم اولویت تر) وارد شوند تمام می شوند فرایند هایی که زمان اجرای زیادی را دارند کم کم به صف های پایین تر منتقل می شوند در این صورت است که فرایند های کوچکتر زود تر از همه اتمام می شوند

در داخل هر صف به استثنای صف کمترین اولویت یک راهکار ساده Fifo به کار گرفته می شود وقتی فرایندی در صف کمترین اولویت قرار گرفت نمی تواند به صف بعدی برود پس فرایند تا آخر در همان صف اجرا شده و تمام می شود

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

 

RQ0

RQ1

RQn

 

پردازنده

CPU

آزاد سازی

 

پردازنده

CPU

آزاد سازی

 

پردازنده

CPU

آزاد سازی

فرایند زمانبندی شده برای RQ0 می تواند به اندازه یک واحد زمانی اجرا و سپس قبضه شود فرایند زمانبندی برای RQ1 میتواند به اندازه دو واحد زمانی اجرا شود وهمین طور برای صفهای دیگر. در حالت کلی یک فرایند زمانبندی شده برای Rqi مجاز است قبل از قبضه شدن به اندازه 2 به توان i واحد زمانی اجرا شود.

 

خصوصیات الگوریتم FB:

•       تابع انتخاب:  ------------

•       حالت تصمیم گیری: با قبضه کردن

•       توان عملیاتی: تاکید نشده است

•       زمان پاسخ: تاکید نشده است

•       سربار: می تواند زیاد باشد

•       تاثیر بر روی فرآیند ها: به نفع فرایند های در تنگنای I/O

•       گرسنگی: امکان دارد از طریق جریمه کردن کارهایی که زمان طولانی تری برای اجرا دارند.

 

+ نوشته شده توسط مهدی شعبانی در دوشنبه ششم اردیبهشت 1389 و ساعت 10:44 |

الگوریتم ها

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

   در حالت کلی الگوریتم ها باید ویژگی های زیر را داشته باشند:

الف) الگوریتم باید ما را به نتیجه مورد نظر برساند.
ب) در زمان محدود پایان یابد.
ج) دستورالعملها باید به ترتیب منطقی پشت سرهم قرار گیرند.
د) جملات الگوریتم ها باید به صورت امری ، سؤالی باشند.
ه) هر الگوریتم باید نقطه آغاز و پایان داشته باشد.

   یکی از توانایی هایی که در کامپیوتر وجود دارد استفاده از خانه های حافظه است که می توان در آن اطلاعات را قرار داد و در هر لحظه از اجرای الگوریتم می توان محتویات آن را تغییر داده و مقدار جدیدی را در آن قرار دهیم این ویژگی کارایی ما را برای حل مسائل پیچیده تر افزایش می دهد.

مثال : الگوریتم تعویض چرخ پنچر شده یک اتومبیل.

0- شروع.

1- جک را زیر اتومبیل بگذارید.

2- پیچهای چرخ پنچر شده را باز کنید.

3- چرخ را خارج کنید.

4- چرخ یدک را به جای چرخ پنچر شده بگذارید.

5- پیچها را ببندید.

6- اگر پیچها سفت نشده اند به مرحله 5 برو.

7- جک را پایین بیاورید.

8- چرخ پنچر شده را در صندوق عقب اتومبیل بگذارید.

9- پایان.

مثال : الگوریتمی بنویسید که دو عدد از ورودی دریافت شود و سپس تعیین شود که مجموع دو عدد بزرگتر از 20 است یا نه.

0- شروع .

1- دو عدد a و b را از ورودی در یافت کن.

2- a+b را محاسبه کن.

3- آیا a+b>20 است؟ اگر بلی به مرحله 6 برو.

4- بنویس خیر.

5- به مرحله 7 برو.

6- بنویس بلی.

7- پایان.

   با برنامه ریزی و ساماندهی دقیق می توان به راه حلی مناسب جهت حل یک مسئله به کمک کامپیوتر رسید. هرگونه کم توجهی و بی دقتی در نوشتن الگوریتم ضمن بروز مشکلات بسیار، برنامه نویس را نیز از هدف خود دور خواهد کرد؛ لذا برای به هدف رسیدن باید درک صحیح و کاملی از صورت مسئله داشت و سپس راه حل مورد نظر را به صورت الگوریتم بنویسیم. و در نهایت الگوریتم مورد نظر را به زبان برنامه نویسی مورد نظر تبدیل کنیم. برای درک بهتر شیوه حل مسائل و نوشتن الگوریتم به مثالهای زیر توجه کنید:

مثال : الگوریتمی بنویسید که مجموع اعداد طبیعی مضرب 7 و کوچکتر از 50 را حساب کند.

برای نوشتن این الگوریتم به دو خانه حافظه نیاز داریم.

0- شروع.

1- در خانه حافظه sum عدد صفر را قرار بده.

2- در خانه حافظه index عدد 7 را قرار بده.

3- مقدار index را با مقدارsum جمع کن

          و حاصل را در sum قرار بده.

4- مقدار 7 را با مقدار index جمع کن

          و حاصل را در index قرار بده.

5- آیاindex بزگتراز 50 است،اگر خیر به مرحله 3 برو.

6- محتوای sum را چاپ کن.

7- پایان.

 

 

در الگوریتم فوق مقادیر حافظه sum و index تغییر می کند، تا اینکه سرانجام شرط " آیا index بزرگتر از 50 است " بلی می شود لذا محتوای sum در خروجی چاپ خواهد شد و الگوریتم به پایان می رسد. اما در مراحل قبلی شرط فوق خیر می باشد، لذا الگوریتم ادامه پیدا می کند.

مثال : الگوریتمی بنویسید که 1000 عدد را از ورودی دریافت کرده و کوچکترین را چاپ کند.

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

0- شروع.

1- min را دریافت کن.

2- i =1 .

3- a را دریافت کن.

4- اگر a

5- i = i + 1 .

6- اگر i>=1000 به مرحله 8 برو.

7- به مرحله 3 برو.

8- min را چاپ کن.

9- پایان.

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

مثال : الگوریتمی بنویسید که سه عدد از ورودی دریافت شود و تعیین شود که این اعداد می توانند اضلاع مثلث باشند یا خیر.

0- شروع.

1- a وb وc را از ورودی بگیر.

2- اگر a>b+c به 7 برو.

3- اگر b>a+c به 7 برو.

4- اگرc>a+b به 7 برو.

5- بنویس " بلی ".

6- به 8 برو.

7- بنویس " خیر ".

8- پایان.

 

فلوچارت

در عمل برای نمایش الگوریتم از یک فلوچارت ( شمای جریان عملیات ) استفاده می شود. در حقیقت فلوچارت روش تصویری و استاندارد نمایش الگوریتم است.

در رسم فلوچارت علائم و نمادهای استانداردی به کار می رود که هر کدام دارای معانی ویژه ای هستند.

از شکل بیضی افقی برای شروع و پایان عملیات استفاده می شود.

از شکل مستطیل برای نمایش مراحل پردازشی استفاده می شود و در داخل آن عمل مورد نظر نوشته می شود. این نماد ممکن است چندین ورودی داشته باشد ولی تنها یک خروجی دارد.

از نماد لوزی برای نشان دادن مراحل تصمیم گیری استفاده می گردد و شرط یا سؤال مورد نظر در داخل لوزی نوشته می شود.

از متوازی الاضلاع برای نشان دادن ورودی یا خروجی استفاده می شود.

+ نوشته شده توسط مهدی شعبانی در دوشنبه بیست و سوم فروردین 1389 و ساعت 10:36 |
يکي از مهم‌ترين مولفه‌ها در برنامه‌نويسي، بهينه بودن الگوريتم است. منظور از بهينه بودن اين است که با کمترين هزينه، بيشترين بازده را دريافت کنيم. منظور از هزينه، ميزان حافظه مصرفي و منظور از بازده، انجام سريع‌تر عمليات است. اين دو عامل معمولا رابطه مستقيم با يکديگر ندارند و معمولا سريع‌ترين الگوريتم‌ها، اگر هزينه پاييني داشته‌باشند، بسيار پيچيده‌اند و از طرف ديگر، الگوريتم‌هاي ساده (بازگشتي) هزينه بالايي دارند. روش‌هاي مختلفي براي مرتب سازي داده‌ها وجود دارد. از مولفه‌هاي مهم در الگوريتم‌هاي مرتب‌سازي ميزان مقايسه و ميزان جابه‌جايي است، در زير چند نمونه از آنها را بررسي مي‌کنيم:

الف) مرتب‌سازي انتخابي

در اين الگوريتم در هر مرحله عنصر بزرگتر پيدا مي‌شود (اگر مرتب سازي نزولي باشد کوچکترين عنصر) و با يک جابه‌جايي در جاي خود قرار مي‌گيرد، عمل مقايسه در مرحله اول به اندازه N-1 انجام مي‌شود (N تعداد داده‌هاي موجود است)، و در مرحله دوم به اندازه N-2. به‌همين ترتيب در مرحله iام N-i مقايسه بايد انجام شود، در کل n*(n-1)/2 مقايسه بايد انجام شود، و در هر مرحله حداکثر 1 جابه‌جايي انجام مي‌شود. در بهترين شرايط‌داده‌ها از اول بصورت مرتب شده هستند که در اين حالت هيچ جابه‌جايي صورت نمي‌گيرد؛ در بدترين حالت در هر مرحله يک جابه‌جايي داريم و حداکثر n-1 جا‌به‌جايي صورت مي‌گيرد. بدين ترتيب مرتبه اجرايي اين الگوريتم در بهترين و بدترين شرايط به ترتيب به صورت زير است:

O(N^2) مقايسه، O(1) جابه‌جايي

O(N^2) مقايسه، O(N) جابه‌جايي

مي‌توان اثبات کرد که در مرتب سازي صعودي اگر داده‌ها به‌صورت نزولي مرتب شده باشند، ميزان جابه‌جايي همان n*(n-1)/2 است ولي تعداد تعويض‌ها برابر n/2 است.


ب) مرتب‌سازي حبابي

در اين الگوريتم چندين بار داده‌هاي مورد نظر را بررسي مي‌کنيم، در هر مرحله هر عنصر با عنصر بعدي مقايسه مي‌شود اگر بزرگتر بود، با عنصر بعدي جابه جا مي‌شود، در پايان مرحله اول بزرگترين عنصر در آخرين خانه قرار مي‌گيرد. در مرحله بعد از خانه صفر تا خانه n-1 بررسي مي‌شود و به‌همين ترتيب تا اينکه به اولين عنصر که کوچکترين عنصر است برسيم. در اين الگوريتم مانند الگوريتم انتخابي ميزان مقايسه‌ها برابر n(n-1)/2 است و تعداد جابه‌جايي‌ها در بهترين حالت زماني است که داده‌ها مرتب شده باشند و ميزان جابه‌جايي برابر صفر مي‌گردد، در بدترين شرايط زماني است که داده‌ها به‌صورت معکوس مرتب شده‌باشند، که برابر n(n-1)/2 است، مرتبه اجرايي اين الگوريتم در بهترين و بدترين شرايط به ترتيب به صورت زير است:

O(N) مقايسه، O(1) جابه‌جايي

O(N^2) مقايسه، O(N^2) جابه‌جايي

ج) مرتب‌سازي خارجي

در اين الگوريتم به ترتيب عناصر 0 تا n خوانده شده و عنصر nام در جاي درست خود در زير آرايه از قبل مرتب شده x[0]، x[1]، ... x[n-1] قرار مي‌گيرد.

در مرحله اول، عنصر 0ام را در نظر مي‌گيريم که بطور بديهي مرتب است.

در مرحله دوم، عنصر 1ام را با عنصر 0ام مقايسه مي‌کنيم و در جاي مناسب خود قرار مي‌دهيم به‌طوري که عناصر 0ام و 1ام مرتب شده باشند.

در مرحله سوم، عنصر 2ام را با دو عنصر قبلي مقايسه کرده و در جاي خود قرار مي‌دهيم، به‌طوري که آرايه حاصله مرتب شده باشد. و در مرحله iام، عنصر iام را با کل آرايه. حال از مرحله i-1 مقايسه کرده و در جاي خود قرار مي‌دهيم به‌طوري که آرايه حاصل مرتب شده باشد.

در اين الگوريتم نيز ميزان مقايسه مانند دو الگوريتم ذکر شده برابر n*(n-1)/2 است، در بهترين شرايط داده‌ها مرتب شده هستند، که در اين حالت تعداد مقايسه‌ها برابر n-1 است و هيچ جابه‌جايي نيز صورت نمي‌پذيرد، مرتبه اجرايي اين الگوريتم در بهترين و بدترين شرايط به ترتيب به صورت زير است:

O(N) مقايسه، O(1) جا به جايي

O(N^2) مقايسه ، O(N^2) جا به جايي

د) مرتب‌سازي ادغامي

اساس اين الگوريتم از روش تقسيم و حل براي مرتب سازي استفاده مي‌کند، در اين روش مساله به چند مساله کوچکتر تقسيم مي‌شود، و با حل هر کدام از اين مساله‌هاي کوچک و ترکيب آنها با هم مساله اصلي حل مي‌شود. پس مي‌توان پي‌برد که بخشي از اين الگوريتم بصورت بازگشتي پياده‌سازي مي‌شود، نکته‌اي که قبل از توضيح روش کار بايد در نظر گرفت بحث ترکيب است، در اين الگوريتم حاصل هر مرحله با حاصل‌هاي ديگر بايد ترکيب شده تا نتيجه درست حاصل شود. در اين بحث از توضيح اين الگوريتم صرف نظر مي‌کنيم ولي اين الگوريتم براي دو آرايه x[s,m] و y[m+1,n] از مرتبه O(n-s+1) است که n-s+1 تعداد عناصري هستند که با هم ترکيب شده‌اند.

شرح الگوريتم

در مرحله اول داده‌ها به N آرايه 1 عضوي تقسيم مي‌شوند و سپس عناصر دو به دو با هم ادغام مي‌شوند تا n/2 آرايه دو عضوي حاصل شود (اگر n عددي فرد باشد يک آرايه تک عضوي پديد مي‌آيد)، سپس اين n/2 آرايه را دو به دو با هم ترکيب کرده تا به يک ليست n عضوي مرتب برسيم، از اين رو به حداکثر Log n مرحله جهت مرتب‌کردن آرايه نياز دارد، مرتبه اجرايي اين الگوريتم همواره O(n*Log n) است، معمولا از اين الگوريتم براي فايل‌ها استفاده مي‌کنند.

A-Sorting-1

ح) مرتب‌سازي درختي

اين مرتب‌سازي بر اساس درخت BST (درخت جستجو دودويي) انجام مي‌شود، ابتدا در مورد درخت دودويي توضيح مختصري مي‌دهيم، درخت جستجوي دودويي يک درخت دودويي است که مي‌تواند تهي باشد، اگر تهي نباشد داراي خواص زير است، مقدار هر گره بزرگتر از زير درخت سمت چپ و کوچکتر از زير درخت سمت راست آن است. هر گره داراي يک کليد است و کليدها منحصر به فرد هستند (درخت جستجوي دودويي داراي عضو تکراري نيست).

درج هر داده در درخت BST به مدت O(Log N) انجام مي‌پذيرد و درج n داده O(n*Log n) انجام مي‌گيرد پيمايش inorder درخت جستجوي دودويي باعث نمايش ليست مرتب شده بصورت صعودي مي‌شود.

بدترين وضيعت در درخت جستجوي دودويي زماني است که داده‌هاي ورودي به‌صورت مرتب شده باشند (چه صعودي چه نزولي)، که درخت حاصل بصورت اريب ظاهر مي‌شود در اين حال اگر داده‌هاي تکراري نباشند براي درج n(n-1)/2 مقايسه بايد انجام شود و مرتبه زماني درج داده ها بصورت O(N2) است.

بهترين حالت براي اين الگوريتم زماني است که داده ها نا مرتب بوده، که عمق درخت در حال متوازن (Log(n,2 قرار گيرد، در نتيجه زمان درج n داده همانطور که گفته شد برابر O(nLog n) است و زمان مرتب سازي برابر O(n*Log(n,2)) است.

+ نوشته شده توسط مهدی شعبانی در دوشنبه بیست و سوم فروردین 1389 و ساعت 10:22 |

الگوریتم مرتب‌سازی، در علوم کامپیوتر و ریاضی، الگوریتمی است که لیستی از داده‌ها را به ترتیبی مشخص می‌چیند.

پر استفاده‌ترین ترتیب‌ها، ترتیب‌های عددی و لغت‌نامه‌ای هستند. مرتب‌سازی کارا در بهینه سازی الگوریتم‌هایی که به لیست‌های مرتب شده نیاز دارند (مثل جستجو و ترکیب) اهمیت زیادی دارد.

از ابتدای علم کامپیوتر مسائل مرتب‌سازی تحقیقات فراوانی را متوجه خود ساختند، شاید به این علت که در عین ساده بودن، حل آن به صورت کارا پیچیده‌است. برای مثال مرتب‌سازی حبابی در سال ۱۹۵۶ به وجود آمد. در حالی که بسیاری این را یک مسئلهٔ حل شده می‌پندارند، الگوریتم کارآمد جدیدی همچنان ابداع می‌شوند (مثلاً مرتب‌سازی کتاب خانه‌ای در سال ۲۰۰۴ مطرح شد).

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

طبقه‌بندی

در علم کامپیوتر معمولاً الگوریتم‌های مرتب‌سازی بر اساس این معیارها طبقه‌بندی می‌شوند:

  • پیچیدگی (بدترین و بهترین عملکرد و عملکرد میانگین): با توجه به اندازهٔ لیست (n). در مرتب‌سازی‌های معمولی عملکرد خوب (O(n log n و عملکرد بد (O(n۲ است. بهترین عملکرد برای مرتب‌سازی (O(n است. الگوریتم‌هایی که فقط از مقایسهٔ کلیدها استفاده می‌کنند در حالت میانگین حداقل (O(n log n مقایسه نیاز دارند.
  • حافظه (و سایر منابع کامپیوتر) : بعضی از الگوریتم‌های مرتب‌سازی «در جا» هستند. یعنی به جز داده‌هایی که باید مرتب شوند، حافظهٔ کمی ((O(۱) مورد نیاز است؛ در حالی که سایر الگوریتم‌ها به ایجاد مکان‌های کمکی در حافظه برای نگه‌داری اطلاعات موقت نیاز دارند.
  • پایداری: الگوریتم‌های مرتب‌سازی پایدار ترتیب را بین داده‌های دارای کلیدهای برابر حفظ می‌کنند. فرض کنید می‌خواهیم چند نفر را بر اساس سن با یک الگوریتم پایدار مرتب کنیم. اگر دو نفر با نام‌های الف و ب هم‌سن باشند و در لیست اولیه الف جلوتر از ب آمده باشد، در لیست مرتب شده هم الف جلوتر از ب است.
  • مقایسه‌ای بودن یا نبودن. در یک مرتب‌سازی مقایسه‌ای داده‌ها فقط با مقایسه به وسیلهٔ یک عملگر مقایسه مرتب می‌شوند.
  • روش کلی : درجی، جابجایی، گزینشی، ترکیبی و غیره. جابجایی مانند مرتب‌سازی حبابی و مرتب‌سازی سریع و گزینشی مانند مرتب‌سازی پشته‌ای.
+ نوشته شده توسط مهدی شعبانی در دوشنبه بیست و سوم فروردین 1389 و ساعت 10:18 |

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

در اينجا دو تعريف را براي الگوريتم بيان مي‌كنيم:

 

1- مجموعه‌ای خاص از روال منطقی و یا ریاضی ساده و خوب تبیین شده می‌باشد که می‌تواند در حل یک مسئله مشخص کمک کند. الگوریتم دستورالعملی برای یافتن پاسخ درست یک مساله سخت به وسیله شکستن آن مساله به مراحل ساده و آسان می‌باشد .
۲- هر روال محاسباتی خوش تعریفی است که مقداری, یا مجموعه‌ای از مقادیر را بعنوان ورودی می‌گیرد و مقداری, یا مجموعه‌ای از مقادیر را بعنوان خروجی تولید می‌کند. بنابراین یک الگوریتم یک توالی از گام‌های محاسباتی است که ورودی را به خروجی تبدیل می‌کند.
یک الگوریتم یابد سه شرط اساسی زیر را تأمین کند :
  • لیست دستورالعمل‌ها باید محدود بوده و به اندازه‌ای کوتاه باشد تا قابل اجرا گردد.
  • هر دستورالعمل باید دارای قابلیت اجرا باشد، شما هم باید بتوانید اجرا کارهای یاد شده را به اجرا برسانید.
  • الگوریتم باید روند اجرا را قادر سازد تا در یک نقطه به پایان برسد.

مثلا اين جوك معروف را در نظر بگيريد:

مي دوني يک فيل را چطوري با سه حرکت مي گذارند توي يخچال؟ اول در يخچال را باز مي کنند، بعد فيل را مي گذارند توش، بعد هم در يخچال را مي بندند.

شايد جواب اين جك ظاهرا يك الگوريتم باشد، اما اينطور نيست چون ويژگي دوم يعني قابل اجرا بودن را ندارد.

+ نوشته شده توسط مهدی شعبانی در دوشنبه بیست و سوم فروردین 1389 و ساعت 10:16 |
آموزش الگوريتم نويسي - آموزش مقدماتي
در شبکه‌هاي کوچک، و در نقاطي که انتقال اطلاعات معمولا مستقيم است، مسيريابي چندان جدي گرفته نمي‌شود. اما هنگامي که شبکه‌ها از حالت‌هاي ايستگاه‌هاي کاري خارج مي‌شوند و کمي پيچيده‌تر مي‌شوند، در اين حالت، مسيريابي و انتخاب مسير بهينه براي ارسال بسته‌هاي اطلاعاتي، به يک امر مهم بدل مي‌شود. در شبکه‌هاي بزرگ، دستگاه‌هايي به‌عنوان مسيرياب1 وجود دارند که عمل مسيريابي را انجام مي‌دهند.
الگوريتم مسيريابي‌اي مناسب است که 6 ويژگي زير را داشته باشد: صحت عملکرد2، سادگي3، قابليت اطمينان4، پايداري5، عدالت6 و بهينگي7.

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

الگوريتم کوتاه‌ترين مسير

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

الگوريتم سيل‌آسا

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

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

الگوريتم سيل‌آسا به جز چند مورد خاص، از جمله سيستم‌هاي توزيعي که عملکردهاي موازي در آنها نياز است، کاربرد علمي ديگري ندارد.

الگوريتم بردار فاصله

در اين روش، مسيرياب‌ها در خود جدولي (برداري) ذخيره مي‌کنند با عنوان بردار فاصله که در آن بهترين فاصله تا هر مسيرياب ديگر در شبکه را ذخيره مي‌کنند. در اين صورت، تصميم‌گيري بهتري هنگام مسيريابي اتخاذ مي‌شود. اين جدول‌ها با اطلاعات مسيرياب‌هاي همسايه به‌روز مي‌شود. هر يک از عناصر اين جدول‌ها يک درايه دوبخشي دارند که يکي از آنها نشانگر خط خروجي مناسب براي رسيدن به مسيرياب مورد نظر و ديگري تخمين فاصله زماني تا آن مسيرياب است.

الگوريتم حالت لينک

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

الگوريتم حالت لينک، ساده است و مي‌توان به‌صورت زير آن را بيان کرد:

1. هر مسيرياب بايد همسايه‌هاي خود را شناسايي کرده و آدرس‌هاي شبکه‌شان را داشته باشد.

2. ميزان هزينه و يا تاخير همسايه‌هاي خود را بداند.

3. اطلاعاتي که از همسايه‌ها بدست آورده است را براي تمام مسيرياب‌هاي ديگر بفرستد.

4. کوتاه‌ترين مسير براي رسيدن به ديگر مسيرياب‌ها را محاسبه کند.

شناسايي همسايه‌ها به‌اين صورت انجام مي‌گيرد که پس از راه‌اندازي مسيرياب (بوت‌شدن) يک بسته سلام11 به تمام همسايه‌ها ارسال مي‌شود. مسيرياب‌هاي همسايه مشخصات خود را براي اين مسيرياب مي‌فرستند.

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

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

منابع

+ نوشته شده توسط مهدی شعبانی در دوشنبه بیست و سوم فروردین 1389 و ساعت 10:13 |
آموزش الگوريتم نويسي - آموزش مقدماتي
در شبکه‌هاي کوچک، و در نقاطي که انتقال اطلاعات معمولا مستقيم است، مسيريابي چندان جدي گرفته نمي‌شود. اما هنگامي که شبکه‌ها از حالت‌هاي ايستگاه‌هاي کاري خارج مي‌شوند و کمي پيچيده‌تر مي‌شوند، در اين حالت، مسيريابي و انتخاب مسير بهينه براي ارسال بسته‌هاي اطلاعاتي، به يک امر مهم بدل مي‌شود. در شبکه‌هاي بزرگ، دستگاه‌هايي به‌عنوان مسيرياب1 وجود دارند که عمل مسيريابي را انجام مي‌دهند.
الگوريتم مسيريابي‌اي مناسب است که 6 ويژگي زير را داشته باشد: صحت عملکرد2، سادگي3، قابليت اطمينان4، پايداري5، عدالت6 و بهينگي7.

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

الگوريتم کوتاه‌ترين مسير

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

الگوريتم سيل‌آسا

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

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

الگوريتم سيل‌آسا به جز چند مورد خاص، از جمله سيستم‌هاي توزيعي که عملکردهاي موازي در آنها نياز است، کاربرد علمي ديگري ندارد.

الگوريتم بردار فاصله

در اين روش، مسيرياب‌ها در خود جدولي (برداري) ذخيره مي‌کنند با عنوان بردار فاصله که در آن بهترين فاصله تا هر مسيرياب ديگر در شبکه را ذخيره مي‌کنند. در اين صورت، تصميم‌گيري بهتري هنگام مسيريابي اتخاذ مي‌شود. اين جدول‌ها با اطلاعات مسيرياب‌هاي همسايه به‌روز مي‌شود. هر يک از عناصر اين جدول‌ها يک درايه دوبخشي دارند که يکي از آنها نشانگر خط خروجي مناسب براي رسيدن به مسيرياب مورد نظر و ديگري تخمين فاصله زماني تا آن مسيرياب است.

الگوريتم حالت لينک

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

الگوريتم حالت لينک، ساده است و مي‌توان به‌صورت زير آن را بيان کرد:

1. هر مسيرياب بايد همسايه‌هاي خود را شناسايي کرده و آدرس‌هاي شبکه‌شان را داشته باشد.

2. ميزان هزينه و يا تاخير همسايه‌هاي خود را بداند.

3. اطلاعاتي که از همسايه‌ها بدست آورده است را براي تمام مسيرياب‌هاي ديگر بفرستد.

4. کوتاه‌ترين مسير براي رسيدن به ديگر مسيرياب‌ها را محاسبه کند.

شناسايي همسايه‌ها به‌اين صورت انجام مي‌گيرد که پس از راه‌اندازي مسيرياب (بوت‌شدن) يک بسته سلام11 به تمام همسايه‌ها ارسال مي‌شود. مسيرياب‌هاي همسايه مشخصات خود را براي اين مسيرياب مي‌فرستند.

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

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

منابع

+ نوشته شده توسط مهدی شعبانی در دوشنبه بیست و سوم فروردین 1389 و ساعت 10:13 |
آموزش الگوريتم نويسي - آموزش مقدماتي

يكي از مواردي كه هر الگوريتم نويسي بايد بداند، فلوچارت است. مبحثي بسيار ساده و در عين حال كاربردي! پس به بررسي اين مطلب مي پردازيم. مطالب زير از ويكيپديا استخراج شده اند.

فلوچارت چيست؟

فلوچارت یا روندنما (به انگلیسی: Flowchart) نموداری است برای نمایش داده‌ها، اطلاعات و روند کار یک الگوریتم بر روی آنها، به‌وسیله نمادهای خاصی و خطوط جهت‌دار بین آنها.

فلوچارت به چه کاری می‌آید؟

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

نمادهای مورد استفاده

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

  • آغاز و پایان
Oval_28Programmablaufplan291
  • ورودی و خروجی
Parallelogramm_28Programmablaufplan291
  • رابط
  • تصمیم گیری (شرطی)
Raute_28Programmablaufplan291
  • پردازش
Rechteck_28Programmablaufplan291
  • فراخوانی زیرالگوریتم
Rechteck_mit_
  • توضیحات اضافی و کمکی
  • تلفیق
  • ادغام
  • استخراج
  • ...

مثلا وقتي يك لامپ كار نميكنه مي توانيد از الگوريتم زير استفاده كنيد:

200px-LampFlowchart.svg1

خوب حالا سعي كنيد الگوريتم زندگيتون را بكشيد! تا مقاله ي بعد در پناه حق!

+ نوشته شده توسط مهدی شعبانی در دوشنبه بیست و سوم فروردین 1389 و ساعت 10:7 |
+ نوشته شده توسط مهدی شعبانی در یکشنبه بیست و دوم فروردین 1389 و ساعت 12:20 |


Powered By
BLOGFA.COM