به حق برایتان می گویم : بنده نمی تواند خدمتگزاردو پروردگار باشد و هرچه بکوشد، باز یکی را بر دیگری ترجیح خواهد داد. همچنین خدا دوستی و دنیا دوستی، برای شما جمع نخواهد شد . [عیسی علیه السلام]
یکشنبه 86 بهمن 21 , ساعت 10:22 عصر

الگوریتم ژنتیک

 

هنگامی که لغت تنازع بقا به کار می‌رود اغلب بار ارزشی منفی آن به ذهن می‌آید. شاید همزمان قانون جنگل به ذهن برسد و حکم بقای قوی‌تر!
   البته برای آنکه خیالتان راحت شود می‌توانید فکر کنید که همیشه هم قوی‌ترین‌ها برنده نبوده‌اند. مثلا دایناسورها با وجود جثه عظیم و قوی‌تر بودن در طی روندی کاملا طبیعی بازی بقا و ادامه نسل را واگذار کردند در حالی که موجوداتی بسیار ضعیف‌تر از آنها حیات خویش را ادامه دادند. ظاهرا طبیعت بهترین‌ها را تنها بر اساس هیکل انتخاب نمی‌کند! در واقع درست‌تر آنست که بگوییم طبیعت مناسب ترین‌ها (Fittest) را انتخاب می‌کند نه بهترین‌ها.

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

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

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

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

   پس از اختراع اتومبیل به تدریج و در طی سال‌ها اتومبیل‌های بهتری با سرعت‌های بالاتر و قابلیت‌های بیشتر نسبت به نمونه‌های اولیه تولید شدند. طبیعیست که این نمونه‌های متاخر حاصل تلاش مهندسان طراح جهت بهینه‌سازی طراحی‌های قبلی بوده اند. اما دقت کنید که بهینه‌سازی یک اتومبیل تنها یک "اتومبیل بهتر" را نتیجه می‌دهد.

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

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

در این میان آنچه شاید بتواند تا حدودی ما را در فهم این مساله یاری کند مفهومیست به نام : تصادف یا جهش.

   به عبارتی طرح هواپیما نسبت به طرح اتومبیل یک جهش بود و نه یک حرکت تدریجی. در طبیعت نیز به همین گونه‌است. در هر نسل جدید بعضی از خصوصیات به صورتی کاملا تصادفی تغییر می‌یابند سپس بر اثر تکامل تدریجی که پیشتر توضیح دادیم در صورتی که این خصوصیت تصادفی شرایط طبیعت را ارضا کند حفظ می‌شود در غیر این‌صورت به شکل اتوماتیک از چرخه طبیعت حذف می‌گردد.

 در واقع می‌توان تکامل طبیعی را به این‌صورت خلاصه کرد: جست‌وجوی کورکورانه(تصادف یا Blind Search)+ بقای قوی‌تر.

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

   روش‌های کلاسیک ریاضیات دارای دو اشکال اساسی هستند. اغلب این روش‌ها نقطه بهینه محلی(Local Optima) را بعنوان نقطه بهینه کلی در نظر می‌گیرند و نیز هر یک از این روش‌ها تنها برای مساله خاصی کاربرد دارند. این دو نکته را با مثال‌های ساده‌ای روشن می‌کنیم.

   به شکل زیر توجه کنید. این منحنی دارای دو نقطه ماکزیمم می‌باشد. که یکی از آنها تنها ماکزیمم محلی ست. حال اگر از روش‌های بهینه‌سازی ریاضی استفاده کنیم مجبوریم تا در یک بازه بسیار کوچک مقدار ماکزیمم تابع را بیابیم. مثلا از نقطه 1 شروع کنیم و تابع را ماکزیمم کنیم. بدیهیست اگر از نقطه 1 شروع کنیم تنها به مقدار ماکزیمم محلی دست خواهیم یافت و الگوریتم ما پس از آن متوقف خواهد شد. اما در روش‌های هوشمند خاصه الگوریتم ژنتیک بدلیل خصلت تصادفی آنها حتی اگر هم از نقطه 1 شروع کنیم باز ممکن است در میان راه نقطه A به صورت تصادفی انتخاب شود که در این صورت ما شانس دست‌یابی به نقطه بهینه کلی (Global Optima) را خواهیم داشت.

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

چارچوب کلی الگوریتم ژنتیک

   در دهه هفتاد میلادی دانشمندی از دانشگاه میشیگان به نام جان هلند ایده استفاده از الگوریتم ژنتیک را در بهینه‌سازی‌های مهندسی مطرح کرد. ایده اساسی این الگوریتم انتقال خصوصیات موروثی توسط ژن‌هاست. فرض کنید مجموعه خصوصیات انسان توسط کروموزوم‌های او به نسل بعدی منتقل می‌شوند. هر ژن در این کروموزوم‌ها نماینده یک خصوصیت است. بعنوان مثال ژن 1 می‌تواند رنگ چشم باشد ، ژن 2 طول قد، ژن 3 رنگ مو و الی آخر. حال اگر این کروموزوم به تمامی، به نسل بعد انتقال یابد، تمامی خصوصیات نسل بعدی شبیه به خصوصیات نسل قبل خواهد بود. بدیهیست که در عمل چنین اتفاقی رخ نمی‌دهد. در واقع بصورت همزمان دو اتفاق برای کروموزوم‌ها می‌افتد. اتفاق اول موتاسیون (Mutation) است. موتاسیون به این صورت است که بعضی ژن‌ها بصورت کاملا تصادفی تغییر می‌کنند. البته تعداد این گونه ژن‌ها بسیار کم می‌باشد اما در هر حال این تغییر تصادفی همانگونه که پیشتر دیدیم بسیار مهم است. مثلا ژن رنگ چشم می‌تواند بصورت تصادفی باعث شود تا در نسل بعدی یک نفر دارای چشمان سبز باشد. در حالی که تمامی نسل قبل دارای چشم قهوه‌ای بوده‌اند. علاوه بر موتاسیون اتفاق دیگری که می‌افتد و البته این اتفاق به تعداد بسیار بیشتری نسبت به موتاسیون رخ می‌دهد چسبیدن ابتدای یک کروموزوم به انتهای یک کروموزوم دیگر است. این مساله با نام CrossOver شناخته می‌شود. این همان چیزیست که مثلا باعث می‌شود تا فرزند تعدادی از خصوصیات پدر و تعدادی از خصوصیات مادر را با هم به ارث ببرد و از شبیه شدن تام فرزند به تنها یکی از والدین جلوگیری می‌کند.

 شکل 2: عملگرهای ژنتیک (Genetic Operators)

   بر اساس آنچه ذکر شد می‌توانیم مراحل الگوریتم ژنتیک را به صورت زیر توضیح دهیم. ابتدا باید راه حل‌های مختلف مساله را به صورت جمعیتی از کروموزوم‌ها نشان دهیم. هر کروموزوم نشان دهنده یک جواب مساله است. در واقع هدف الگوریتم دستیابی به کروموزم‌های بهینه (جواب‌ها) از طریق تولید مثل بهترین کروموزم‌ها در هر نسل است. کروموزوم‌ها اغلب به صورت یک رشته از صفر و یک ها(مقادیر باینری) نمایش می‌یابند که هر بیت از این رشته می‌تواند نمایشگر یک ژن باشد. البته نمایش‌های دیگری از کروموزوم به شکل درخت (Tree) یا لیست وجود دارد که فعلا به آنها نمی‌پردازیم.

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

   این دو کار در واقع مراحل آماده سازی جهت اجرای الگوریتم ژنتیک است. پس از انجام این دو کار یک جمعیت ابتدایی (نسل اولیه) از راه حل‌های ممکن داریم. برای شروع الگوریتم این نسل اولیه باید تولید مثل کند. تولید مثل در سه مرحله انجام می‌شود. مرحله اول انتخاب یا Selection است. در این مرحله بهترین کروموزوم‌ها (بر اساس تابع بهینگی) برای تولید مثل انتخاب می‌شوند. ذکر این نکته ضروریست که حتی در اینجا هم اندکی تصادف را باید دخیل کنیم. یعنی مثلا بهترین کروموزم‌ها را به احتمال 90% انتخاب کنیم. این احتمالاتی انتخاب کردن بهترین‌ها اندکی شانس بقا به کروموزم‌های ضعیف‌تر می‌دهد. اما شاید بپرسید چرا نباید با اطمینان بهترین‌ها را انتخاب کرد و همه ضعیف‌ترها را در هر نسل از بین برد؟

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

   پس از مرحله انتخاب نوبت به تولید مثل کروموزم‌های انتخاب شده می‌رسد. اینکار همان‌گونه که پیشتر گفتیم توسط دو عمل‌گر CrossOver و موتاسیون انجام می‌پذیرد. در مرحله CrossOver کروموزم‌های انتخاب شده به تصادف با یکدیگر ترکیب می‌شوند تا کروموزوم جدیدی را برای نسل بعدی تولید کنند. این ترکیب تاکنون به شیوه‌های مختلفی پیاده‌سازی شده است. ساده‌ترین شکل آن اینست که ابتدای یک کروموزم(یا همان رشته باینری) به انتهای کروموزوم دیگری بچسبد. به این ترتیب کروموزوم حاصل بخشی از خصوصیات هر دو را به ارث می‌برد.

   در مرحله موتاسیون مقدار بعضی ژن‌ها به تصادف عوض می‌شود. یعنی مثلا اگر کروموزوم‌های ما چنانکه گفتیم بوسیله رشته‌های صفر و یک نمایش داده شوند در هر کروموزوم تعداد صفر یا بیشتر ژن(بیت) انتخاب شده و مقدار آنها از صفر به یک یا برعکس تغییر می‌یابد. برای موتاسیون نیز روش‌های دیگری وجود دارد که روش گفته شده ساده‌ترین و در عین حال معمول‌ترین آنهاست. آنچه باید بدان دقت شود اینست که درصد موتاسیون معمولا بسیار کم در نظر گرفته می‌شود. مثلا چیزی کمتر از پنج درصد کروموزوم‌ها تحت تاثیر موتاسیون قرار می‌گیرند.

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

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

مزایا و معایب الگوریتم ژنتیک

   تا کنون به کلیت و نیز چگونگی پیاده سازی الگوریتم ژنتیک اشاره کردیم. اینک می‌خواهیم یک جمع بندی از مزایا و معایب این الگوریتم داشته باشیم. اولین خصوصیت مثبت این الگوریتم دستیابی به نقطه بهینه کلی (Global Optima) به جای نقطه بهینه محلی ست. یعنی همیشه در حد بسیار مطلوبی می‌توان به پاسخ این الگوریتم اعتماد کرد و اینکه پاسخی که می‌یابد به احتمال زیاد بهترین پاسخ ممکن است.

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

   هر چند خود الگوریتم ژنتیک برای حل مسائل بهینه‌سازی گسسته به کار می‌رود اما روش‌های مشابهی همچون استراتژی تکاملی و یا الگوریتم آب دادن فولاد(ُSimulated Annealing) وجود دارند که عینا در مورد مسائل پیوسته می‌توانند به کار روند.

   نحوه تعریف و پیاده‌سازی این الگوریتم نیز به گونه‌ایست که آن را بسادگی جهت اجرا بصورت موازی یا بر روی Multiprocessor ها مناسب می‌سازد.

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

 


یکشنبه 86 بهمن 21 , ساعت 10:22 عصر

الگوریتم ژنتیک

 

هنگامی که لغت تنازع بقا به کار می‌رود اغلب بار ارزشی منفی آن به ذهن می‌آید. شاید همزمان قانون جنگل به ذهن برسد و حکم بقای قوی‌تر!
   البته برای آنکه خیالتان راحت شود می‌توانید فکر کنید که همیشه هم قوی‌ترین‌ها برنده نبوده‌اند. مثلا دایناسورها با وجود جثه عظیم و قوی‌تر بودن در طی روندی کاملا طبیعی بازی بقا و ادامه نسل را واگذار کردند در حالی که موجوداتی بسیار ضعیف‌تر از آنها حیات خویش را ادامه دادند. ظاهرا طبیعت بهترین‌ها را تنها بر اساس هیکل انتخاب نمی‌کند! در واقع درست‌تر آنست که بگوییم طبیعت مناسب ترین‌ها (Fittest) را انتخاب می‌کند نه بهترین‌ها.

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

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

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

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

   پس از اختراع اتومبیل به تدریج و در طی سال‌ها اتومبیل‌های بهتری با سرعت‌های بالاتر و قابلیت‌های بیشتر نسبت به نمونه‌های اولیه تولید شدند. طبیعیست که این نمونه‌های متاخر حاصل تلاش مهندسان طراح جهت بهینه‌سازی طراحی‌های قبلی بوده اند. اما دقت کنید که بهینه‌سازی یک اتومبیل تنها یک "اتومبیل بهتر" را نتیجه می‌دهد.

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

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

در این میان آنچه شاید بتواند تا حدودی ما را در فهم این مساله یاری کند مفهومیست به نام : تصادف یا جهش.

   به عبارتی طرح هواپیما نسبت به طرح اتومبیل یک جهش بود و نه یک حرکت تدریجی. در طبیعت نیز به همین گونه‌است. در هر نسل جدید بعضی از خصوصیات به صورتی کاملا تصادفی تغییر می‌یابند سپس بر اثر تکامل تدریجی که پیشتر توضیح دادیم در صورتی که این خصوصیت تصادفی شرایط طبیعت را ارضا کند حفظ می‌شود در غیر این‌صورت به شکل اتوماتیک از چرخه طبیعت حذف می‌گردد.

 در واقع می‌توان تکامل طبیعی را به این‌صورت خلاصه کرد: جست‌وجوی کورکورانه(تصادف یا Blind Search)+ بقای قوی‌تر.

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

   روش‌های کلاسیک ریاضیات دارای دو اشکال اساسی هستند. اغلب این روش‌ها نقطه بهینه محلی(Local Optima) را بعنوان نقطه بهینه کلی در نظر می‌گیرند و نیز هر یک از این روش‌ها تنها برای مساله خاصی کاربرد دارند. این دو نکته را با مثال‌های ساده‌ای روشن می‌کنیم.

   به شکل زیر توجه کنید. این منحنی دارای دو نقطه ماکزیمم می‌باشد. که یکی از آنها تنها ماکزیمم محلی ست. حال اگر از روش‌های بهینه‌سازی ریاضی استفاده کنیم مجبوریم تا در یک بازه بسیار کوچک مقدار ماکزیمم تابع را بیابیم. مثلا از نقطه 1 شروع کنیم و تابع را ماکزیمم کنیم. بدیهیست اگر از نقطه 1 شروع کنیم تنها به مقدار ماکزیمم محلی دست خواهیم یافت و الگوریتم ما پس از آن متوقف خواهد شد. اما در روش‌های هوشمند خاصه الگوریتم ژنتیک بدلیل خصلت تصادفی آنها حتی اگر هم از نقطه 1 شروع کنیم باز ممکن است در میان راه نقطه A به صورت تصادفی انتخاب شود که در این صورت ما شانس دست‌یابی به نقطه بهینه کلی (Global Optima) را خواهیم داشت.

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

چارچوب کلی الگوریتم ژنتیک

   در دهه هفتاد میلادی دانشمندی از دانشگاه میشیگان به نام جان هلند ایده استفاده از الگوریتم ژنتیک را در بهینه‌سازی‌های مهندسی مطرح کرد. ایده اساسی این الگوریتم انتقال خصوصیات موروثی توسط ژن‌هاست. فرض کنید مجموعه خصوصیات انسان توسط کروموزوم‌های او به نسل بعدی منتقل می‌شوند. هر ژن در این کروموزوم‌ها نماینده یک خصوصیت است. بعنوان مثال ژن 1 می‌تواند رنگ چشم باشد ، ژن 2 طول قد، ژن 3 رنگ مو و الی آخر. حال اگر این کروموزوم به تمامی، به نسل بعد انتقال یابد، تمامی خصوصیات نسل بعدی شبیه به خصوصیات نسل قبل خواهد بود. بدیهیست که در عمل چنین اتفاقی رخ نمی‌دهد. در واقع بصورت همزمان دو اتفاق برای کروموزوم‌ها می‌افتد. اتفاق اول موتاسیون (Mutation) است. موتاسیون به این صورت است که بعضی ژن‌ها بصورت کاملا تصادفی تغییر می‌کنند. البته تعداد این گونه ژن‌ها بسیار کم می‌باشد اما در هر حال این تغییر تصادفی همانگونه که پیشتر دیدیم بسیار مهم است. مثلا ژن رنگ چشم می‌تواند بصورت تصادفی باعث شود تا در نسل بعدی یک نفر دارای چشمان سبز باشد. در حالی که تمامی نسل قبل دارای چشم قهوه‌ای بوده‌اند. علاوه بر موتاسیون اتفاق دیگری که می‌افتد و البته این اتفاق به تعداد بسیار بیشتری نسبت به موتاسیون رخ می‌دهد چسبیدن ابتدای یک کروموزوم به انتهای یک کروموزوم دیگر است. این مساله با نام CrossOver شناخته می‌شود. این همان چیزیست که مثلا باعث می‌شود تا فرزند تعدادی از خصوصیات پدر و تعدادی از خصوصیات مادر را با هم به ارث ببرد و از شبیه شدن تام فرزند به تنها یکی از والدین جلوگیری می‌کند.

 شکل 2: عملگرهای ژنتیک (Genetic Operators)

   بر اساس آنچه ذکر شد می‌توانیم مراحل الگوریتم ژنتیک را به صورت زیر توضیح دهیم. ابتدا باید راه حل‌های مختلف مساله را به صورت جمعیتی از کروموزوم‌ها نشان دهیم. هر کروموزوم نشان دهنده یک جواب مساله است. در واقع هدف الگوریتم دستیابی به کروموزم‌های بهینه (جواب‌ها) از طریق تولید مثل بهترین کروموزم‌ها در هر نسل است. کروموزوم‌ها اغلب به صورت یک رشته از صفر و یک ها(مقادیر باینری) نمایش می‌یابند که هر بیت از این رشته می‌تواند نمایشگر یک ژن باشد. البته نمایش‌های دیگری از کروموزوم به شکل درخت (Tree) یا لیست وجود دارد که فعلا به آنها نمی‌پردازیم.

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

   این دو کار در واقع مراحل آماده سازی جهت اجرای الگوریتم ژنتیک است. پس از انجام این دو کار یک جمعیت ابتدایی (نسل اولیه) از راه حل‌های ممکن داریم. برای شروع الگوریتم این نسل اولیه باید تولید مثل کند. تولید مثل در سه مرحله انجام می‌شود. مرحله اول انتخاب یا Selection است. در این مرحله بهترین کروموزوم‌ها (بر اساس تابع بهینگی) برای تولید مثل انتخاب می‌شوند. ذکر این نکته ضروریست که حتی در اینجا هم اندکی تصادف را باید دخیل کنیم. یعنی مثلا بهترین کروموزم‌ها را به احتمال 90% انتخاب کنیم. این احتمالاتی انتخاب کردن بهترین‌ها اندکی شانس بقا به کروموزم‌های ضعیف‌تر می‌دهد. اما شاید بپرسید چرا نباید با اطمینان بهترین‌ها را انتخاب کرد و همه ضعیف‌ترها را در هر نسل از بین برد؟

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

   پس از مرحله انتخاب نوبت به تولید مثل کروموزم‌های انتخاب شده می‌رسد. اینکار همان‌گونه که پیشتر گفتیم توسط دو عمل‌گر CrossOver و موتاسیون انجام می‌پذیرد. در مرحله CrossOver کروموزم‌های انتخاب شده به تصادف با یکدیگر ترکیب می‌شوند تا کروموزوم جدیدی را برای نسل بعدی تولید کنند. این ترکیب تاکنون به شیوه‌های مختلفی پیاده‌سازی شده است. ساده‌ترین شکل آن اینست که ابتدای یک کروموزم(یا همان رشته باینری) به انتهای کروموزوم دیگری بچسبد. به این ترتیب کروموزوم حاصل بخشی از خصوصیات هر دو را به ارث می‌برد.

   در مرحله موتاسیون مقدار بعضی ژن‌ها به تصادف عوض می‌شود. یعنی مثلا اگر کروموزوم‌های ما چنانکه گفتیم بوسیله رشته‌های صفر و یک نمایش داده شوند در هر کروموزوم تعداد صفر یا بیشتر ژن(بیت) انتخاب شده و مقدار آنها از صفر به یک یا برعکس تغییر می‌یابد. برای موتاسیون نیز روش‌های دیگری وجود دارد که روش گفته شده ساده‌ترین و در عین حال معمول‌ترین آنهاست. آنچه باید بدان دقت شود اینست که درصد موتاسیون معمولا بسیار کم در نظر گرفته می‌شود. مثلا چیزی کمتر از پنج درصد کروموزوم‌ها تحت تاثیر موتاسیون قرار می‌گیرند.

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

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

مزایا و معایب الگوریتم ژنتیک

   تا کنون به کلیت و نیز چگونگی پیاده سازی الگوریتم ژنتیک اشاره کردیم. اینک می‌خواهیم یک جمع بندی از مزایا و معایب این الگوریتم داشته باشیم. اولین خصوصیت مثبت این الگوریتم دستیابی به نقطه بهینه کلی (Global Optima) به جای نقطه بهینه محلی ست. یعنی همیشه در حد بسیار مطلوبی می‌توان به پاسخ این الگوریتم اعتماد کرد و اینکه پاسخی که می‌یابد به احتمال زیاد بهترین پاسخ ممکن است.

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

   هر چند خود الگوریتم ژنتیک برای حل مسائل بهینه‌سازی گسسته به کار می‌رود اما روش‌های مشابهی همچون استراتژی تکاملی و یا الگوریتم آب دادن فولاد(ُSimulated Annealing) وجود دارند که عینا در مورد مسائل پیوسته می‌توانند به کار روند.

   نحوه تعریف و پیاده‌سازی این الگوریتم نیز به گونه‌ایست که آن را بسادگی جهت اجرا بصورت موازی یا بر روی Multiprocessor ها مناسب می‌سازد.

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

 


یکشنبه 86 بهمن 21 , ساعت 10:18 عصر
سلام به شما کاربر گرامی من رضا صمدی هستم  امیدوارم از این وبلاگ خوشتون بیاد!                                                                 

کاربر گرامی لطفا نظر خود را در قسمت نظر خواهی پر کنید؟



تدریس خصوصی دروس  کامپیوتر(آزاد،دولتی،پیام نور ، سما)


(ساختمان داده ها سی، سی شارپ ، ویژوال بیسیک ، پاسکال ،ذخیره و بازیابی ،سیستم عامل، matlab ، spss ،شبکه ،  sql،اسمبلی ، طراحی سایت و...)


 


پروژه های رشته کامپیوتر


(ساختمان داده ها ،سی ،ویژوال بیسیک ، پاسکال ،‍ سی شارپ ، دلفی ، مبانی مهندسی ، شیوه ارائه،  Access ، SPSSو ASP.NET و SQL و  HTML و front page ومبانی اینترنت و.....)


 


پروژه های دروس عمومی


 (زبان فارسی ،معارف ،اصول سرپرستی و کارآفرینی،تاریخ و...)


 




kaboy_omad2000@yahoo.com


 

سیستم‌های خبره ؟؟


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


 

 عامل‌های هوشمند ؟؟

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


SSL چیست ؟؟


•         SSL مخفف Secure Sockets Layer است.


•         SSL پروتکلی است که توسط شرکت Netscape ابداع و برای تبادل اسناد خصوصی در اینترنت توسعه یافته شده است.


•         SSL از یک کلید خصوصی برای به رمز در آوردن اطلاعاتی که بر روی یک ارتباط SSL منتقل می شوند استفاده می شود.


•         امروزه تمام مرورگرهای مدرن ( از جمله Internet Explorer ) این پروتکل را پشتیبانی می نمایند.


•         URLهایی که از SSL استفاده می کنند با https:// به جای http:// شروع می شود.


•         SSL پروتکلی است که پایین‌تر از لایه کاربرد یعنی لایه 4 از مدلTCP/IP و بالاتر از لایه انتقال یعنی لایه سوم از مدل TCP/IP قرار می‌گیرد .


 

آشوب چیست ؟؟

 

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

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


یکشنبه 86 بهمن 21 , ساعت 9:39 عصر
فرکتال چیست ؟؟
 
 

واژه ی فرکتال (fractal) از واژه لاتین fractus یا fractum (به معنی شکسته ) گرفته شده و به معنی سنگی است که به شکل نامنظم شکسته شده باشد.نمونه‌های بارز فرکتال‌ها عبارتند از:پشته های ابر و رشته کوه‌هاو البته رعد آسمان یا همان آذرخش ؛تنه و برگ درختان:سرخسها ؛ سیاهرگ ؛سطح کره ماه؛منظومه شمسی؛ستارگان و ... فرکتال ها در جا های گوناگون مانند ذخیره سازی فایل های تصویری،شناسایی و درمان بیماری های قلبی،پیش بینی وضعیت هوا و بازی های کامپیوتری مورد استفاده قرار می گیرند. فرکتال عبارت است از شیئ که دارای سه ویژگی زیر باشد:

1. در مقیاس میکروسکوپی بسیار پیچیده باشد.

2. دارای خاصیت خود متشابهی (Self_Similarity) باشد.

3. "بعد" آن صحیح نباشد

 
 
روبات چیست ؟؟
 

 

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

برای مثال در قسمت مونتاژ یک  کارخانه اتومبیل سازی، قسمتی هست که چرخ زاپاس ماشین را در صندوق عقب قرار می دهند، اگر یک انسان این کار را انجام دهد خیلی زود دچار ناراحتی هایی مثل کمر درد و ...می شود، اما می توان از یک ربات الکترومکانیکی برای این کار استفاده کرد و یا برای جوشکاری و سایر کارهای دشوار کارخانجات هم همینطور .
و یا ربات هایی که برای اکتشاف در سایر سیارات به کار میروند هم از انواع ربات هایی هستند که در جاهایی که حضور انسان غیرممکن است استفاده می شوند .
  علم رباتیک از سه شاخه اصلی تشکیل شده است :
         ·        الکترونیک ( شامل مغز ربات)
         ·        مکانیک (شامل بدنه فیزیکی ربات)
         ·        نرم افزار (شامل قوه تفکر و تصمیم گیری ربات)
اگریک ربات را به یک انسان تشبیه کنیم، بخشهایی مربوط به ظاهر فیزیکی انسان را متخصصان مکانیک می سازند ، مغز ربات را متخصصان الکترونیک توسط مدارای پیچیده الکترونیک طراحی و می سازند و کارشناسان نرم افزار قوه تفکر را به وسیله برنامه های کامپیوتری برای ربات شبیه سازی می کنند تا در موقعیتهای خاص ، فعالیت مناسب را انجام دهد.
می توانید چند ربات مثال بزنید؟
مثلاً ربات مسیریاب: دنبال یک خط سیاه در زمین سفید حرکت می کند .
یا ربات آتش نشان: آتش را پیدا می کند و آن را خفه می کند!

 
 
 

RUP چیست ؟؟

 

با پیشرفت تکنولوژی‌های مرتبط با کامپیوتر، نیاز هر چه بیشتر به گسترش علم نرم‌افزاری نیز احساس می‌شد که با پیدایش متدولوژیهای همانند SSADM 2 و روش آبشاری3 (چیو 2000) ‎آغاز شد. در ابتدا، این روشها مناسب بود و جوابگوی نیازهای آن زمان بودند ولی با افزایش داده‌ها و پیدایش مفاهیمی همچون شبکه، وب و غیره دیگر کارآیی لازم را جهت پیاده‌سازی و هدایت پروژه‌های نرم‌افزاری نداشتند. پس مفاهیم برنامه‌نویسی شیءگرا پا به عرصه وجود گذاشتند و در سال 1991 بطور جدی مورد مطالعه و بحث قرار گرفتند. استفاده از این روشها و متدهای برنامه‌نویسی، قدرت و انعطاف بسیاری را به برنامه‌ها داد و شرکتهای نرم‌افزاری توانستند با کاهش هزینه‌ها و بهینه‌سازی کدهای خود، نرم‌افزارهای قویتری را به بازار عرضه کنند ولی این روش جدید نیز نیاز به مدیریت و یکپارچگی داشت. پس روشها و متدولوژیهای جدیدی مطرح شد که شامل Booch، OMT، OSE و ... می‌باشند. در سال 2000 شرکت Rational روشی را تحت عنوان RUP مطرح ساخت (گروه کاسمیک 2003ب) که بعد از روش MSF شرکت مایکروسافت به دنیای نرم‌افزار عرضه شد و امروزه از طرفداران بسیاری برخوردار است. فرایند یکپارچه Rational در اصل یک متدولوژی است که در جهت کنترل و انجام پروژه‌های نرم‌افزاری در نظر گرفته شده است. در اصل این چارچوبی در جهت انجام صحیح و موفق پروژه‌های نرم‌افزاری می‌باشد که کلیه مراحل انجام یک پروژه که با معماری و آنالیز سازمان شروع شده و به تست نرم‌افزار و ارائه Gold Release ختم می‌شود را در بر می‌گیرد .

 

 


یکشنبه 86 بهمن 21 , ساعت 9:38 عصر

دوست عزیز اینم چند تا تست کنکوری از درس ساختمان داده ؟؟!

 

1-عبارت [a+(b-c)]*[(d-e)/(f+g-h)] رادر نظر می گیریم . اگر تبدیل یافته های preorder    و postorder     عبارت را کاراکتر

به کاراکتر مقایسه کنیم چند کاراکتر یکسان هستند ؟

1)    0               2)    3               3)   2                4)    4

 

 

2- درجه الگوریتم زیر چند است ؟

For  I ? 0 to  n do

{

j? I ; while j != 0 do j? j div 2 }

1) n^2              2) n log n                      3)  n + log n                  4) n

 

 

3- کدام گزینه درباره کراسکال و پریم برای ایجاد درخت پوشای کمینه درست است ؟

1) هر دو الگوریتم برای گراف های یکسان درخت پوشای یکسان تولید می کنند .

2) مجموع طول اضلاع درخت پوشا در هر دو الگوریتم یکسان است .

3) زمان اجرای هر دو الگوریتم مساوی است .

4) هر دو الگوریتم با رشد و به هم پیوستن یک جنگل از درختان ، درخت پوشا تولید می کنند .

 

 

4- فرض کنید الگوریتم مرتب سازی selection sort    روی عدد 8 زیر اعمال شود در گام سوم کدام دو عدد برای جابجایی انتخاب می شوند ؟

1) 66و33                      2) 55و88                      3) 44و66                      4) 44و33

 

 

5- پنج فایل مرتب شده به اندازه های 5و10و20و25و30  مفروضند می خواهیم از ادغام دو به ودی آنها یک فایل مرتب شده واحد شامل همه رکورد ها به دست اوریم . در هر ادغام رکورد های فایل های ورودی ممکن است چند بار از فایل خوانده و در فایل دیگر نوشته  شوند  . به هر کدام از این نوشتن و خواندن یک جابجایی می گویند . حد اقل تعداد کل این جابجایی ها برای ادغام همه فایل ها چقدر است ؟

1) 195              2) 200              3) 185              4) 215

 

 

6- معادل پسوندی عبارت +-*^abcd//ef+gh       کدام است ؟

1) ab^c*d-ef/gh+/+                  2)   +/+ab^cd*e-fg/h   

2) a^bcdef-/g+h/+                    4) a^bcd*e-f/+gh/+     

 

 

6- یک لیست خطی یک طرفه با دو اشاره گر  f و r   که به ترتیب به عنصر اول  و آخر لیست اشاره می کنند پیاده سازی شده است . هزینه کدام یک از اعمال زیر وابسته به تعداد عناصر لیست است ؟

1) درج یک عنصر در انتهای لیست              2) حذف اولین عنصر

3) حدف آخرین عنصر                               4) درج یک عنصر در ابتدای لیست

 

 

7- برای مرتب کردن آرایه ای به طول 2000  کدام یک از الگریتم های زیر پایین ترین زمان اجرا را در بدترین حالت دارد . در صورتی که مرتب سازی با استفاده از حافظه کمکی صورت پذیرد؟

1)  insertion-sort           2) merg-sort                 3)  quick sort                4)   heap sort

 

 

8- اگر یک گراف شامل n    گره و e  یال باشد مرتبه اجرایی الگوریتم dsf با استفاده از لیست همجواری و ماتریس همجواری عبارت است از :

1) O(n)وO(e)                2)  O(n^2) وO(e)          3) O(e)وO(n)                4) O(e)وO(n^2)

 

9- آرایه A  شامل n  عنصر مرتب ( ازاندیس 1 تا n ) ن عنصر نا مرتب ( از اندیس n+1 تاn+k ) است . کدامیک از الگوریتمهای زیر برای مرتب سازی A کمترین تعداد مقایسه را دارد؟ ( فرض کنید k  مستقل از  n  و بسیار کمتر از آن است ) .

1) heap sort                  2)  quick sort                3) insertion-sort            4)  merg-sort

 

 

10- در برنامه زیر تعداد دفعات تکرار دستور العمل شماره 3 بربر با کدام است ؟

1      for (k = 0 ; k<= n-1 ; k++ )

2      for ( I = 1  ; I <= n –k ; I ++ )

3       a[i][i+k] = k ;

1) (n(n+1))/2                2) n^2              3) (n^2)/2                     4) /2(n(n-1))

 



لیست کل یادداشت های این وبلاگ