مقالات علمي رياضي

[دوست ریاضی]

علامت سوال ریاضی در برابر ایدز

متخصصان عفونی و سایر پزشکان،تا مدت‌ها تئوری مشخصی درباره ایدز داشتند و آن این بود که ویروس ایدز می‌تواند به سلول‌هایی که نوع خاصی از گیرنده‌ها را دارد بچسبد، وارد آنها شود و آنها را آلوده کند .
این سلول‌های آلوده، که عمده آنها از رده گلبول‌های سفید خون هستند، یا خودشان از بین می‌روند، یا این که سلول‌های خودی را به جای بیگانه می‌گیرند و آنها را هم از بین می‌برند. شواهد بیولوژیک گوناگونی هم برای تایید این فرضیه وجود داشت .
اما حالا گروه دیگری از دانشمندان، این فرضیه را که در دنیای پزشکی مقبولیت عام یافته بود، زیر سؤال برده‌اند و تعجب خواهید کرد اگر بدانید این گروه، نه از بین پزشکان، که از بین ریاضیدانان بوده‌اند .
به گزارش بی‌بی‌سی، این ریاضیدانان، با کمک پزشکان، توانسته‌اند یک مدل ریاضی دربیاورند و به نوعی با حساب و کتاب نشان دهند که این فرضیه ، توجیه‌کننده سیر آهسته بیماری، در طی سال‌ها، نیست و اگر این فرضیه پیشنهادی درست می‌بود، بیماری باید ظرف مدت چند ماه، فرد را از پای در‌می‌آورد .
این حساب و کتاب‌ها، تمام فرضیات پیشین و مقبول بین دانشمندان را به چالش کشیده و زیر و رو کرده است.
البته این محققان، از کالج سلطنتی لندن و نیز دانشکده پزشکی آتلانتا، در گزارش خود در نشریه پلاس مدیسین آورده‌اند که این پژوهش فقط یک «مدل ریاضی» است و نمی‌تواند بگوید که واقعاً در بدن بیمار آلوده به ویروس چه اتفاقی می‌افتد و بنابراین تحقیقات گسترده‌‌تری از لحاظ فیزیوپاتولوژی لازم است تا سیر تکثیر و بیماری‌زایی ویروس را در بدن انسان روشن کند. این مطالعه، تنها به ما می‌گوید که باید در فرضیات قبلی خود تجدید نظر کنیم .

[saber57]

اگر امکان داره لینک مقاله رو قرار بدید . با تشکر
ایران هر گز نخواهد مرد تن تن ما ای وطن چون گرد آزادت کنیم و پس آباد آن سان که ایزدت به ما بسپرد

[maryam_tak]

''''ریاضیات نظری'''':تلفیق سنتهای فیزیک نظری و ریاضیات

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

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

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

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

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

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

[CppBuilder2006]

امروز ضروری است نقش اثبات در ادراک ریاضی دوباره بررسی شود و چارچوب مناسب و مفیدی برای این قبیل گرایش ها ایجاد گردد.

من اینو قبول دارم.
فکر می کنم کار ریاضی دان انجام کارهای جدید و خلاقیته نه خوندن اثبات. بررسی درست یا غلط بون یه اثبات رو کامپیوتر هم می تونه انجام بده. لازم نیست همه جا وسواس به خرج بدیم.

[amir_rahmani]

اصل کاوالیری درباره مساحت:
اگر فرض کنیم قاعده های دو شکل بر روی یک خط قرار گرفته باشند. اگر هر خطی موازی قاعده های دو شکل در آنها قطعه هایی با طول های مساوی ایجاد کند، مساحت های آن دو شکل برابر است.
با توجه به شکل دو شکل بر روی افق قرار گرفته اند. اگرهر خطی به موازات قاعده مانند d رسم کنیم و داشته باشیم: AB=CD، MN=PE ، آنگاه دو شکل هم مساحت هستند.

به نظرم من این اصل یک مشکل بزرگ دارد....
به این مثال توجه کنید....:
به جای این دو شکل دو مستطیل باشد و به این ترتیب:
مستطیل سمت چپ: AB= 4cm , AG=2 cm , GH=4cm, HB=2cm
مستطیل سمت راست : CD= 4cm , CP=3 cm , PO=4cm, PD=2cm
در این دو مستطیل هم CD=AB=4cm
و هم GH=PO =4cm
و هم GH موازی AB
وهم PO موازی CD

اینم شکل:

[800908]

سلام
مقاله ای به نام "موسیقی فرکتالی (ایجاد موسیقی از اشکال فرکتالی)" در لینک زیر وجود دارد که جالب می باشد.
به دلیل داشتن برنامه کامپیوتری لینک آن را قرار می دهم:

برای مشاهده محتوا ، لطفا وارد شوید یا ثبت نام کنید

[sajadhoosein]

اجسام به هم نمی رسند


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

[sajadhoosein]

يك روش جديد براي حل مسايل برنامه ريزي خطي كسري


مسايل ماكزيمم سازي كسري خطي ، پژوهش و علاقه قابل ملاحظه اي را به خود اختصاص داده اند ، زيرا آنها در برنامه ريزي توليد ، برنامه ريزي مشاركتي ومالي ، برنامه ريزي بيمارستاني و مراقبت از سلامت مفيد مي با شند.
چند روش براي حل اين مسأله در سال 1962 پيشنهاد شد.
چارنز و كوپر روششان را كه تبديل اين
به يك برنامه خطي معادل بستگي داشت ، پيشنهاد دادند.
روش ديگري كه روش تابع هدف -- ناميده مي شود توسط بيت ران و نوواييز در سال 1973 كشف شد ، كه در آن حل اين مسأله كسري خطي بوسيله حل يك دنباله از برنامه هاي خطي فقط با محاسبه مجدد جدول محلي تابع هدف صورت مي پذيرد.
همچنين بعضي از جنبه هاي ارتباط دوگان و تحليل حساسيت در مسأله كسري خطي توسط بيت ران و مگنانت در سال 1976 به بحث گذاشته شد.
ساي نيز در سال 1981 در مقاله اش يك مطاله مفيد در مورد شرط بهينگي در برنامه ريزي كسري ارايه كرد.




2. تعاريف و نكات :

مسأله مربوط زماني بوجود مي آيد كه يك تابع كسري خطي بايد روي يك چند وجهي-ماكزيمم شود.
اين مسأله مي تواند به شكل رياضي به صورت زير فرمولبندي شود و با
نشان داده مي شود: (LFP)

: كه
C,d , b
اسكالر هستند.

متذكر مي شويم كه شرايط نامنفي در مجموعه محدوديت ها قرار مي گيرند.
:امين سطر ماتريس j
فرض مي شود كه مجموعه جواب شدني – يك مجموعه فشرده است يعني بسته و
كراندار مي باشد. علاوه بر اين
هرجا در --
اين مسأله مي تواند به شكل زير فرمولبندي شود:

دراينجا
امين سطر ماتريس – است كه در تباهيدگي بايد مورد توجه قرار گيرد. i
يك نقطه رأسي ازناحيه شدني – در بعضي از مجموعه هاي مستقل – خطي – قرار
مي گيرد .در(2.2) ما فرض خواهيم كرد كه


(*)


پس يك شكل معادل براي (2.2) مي تواند به صورت زير فرمولبندي شود:


(2.3)


اگر ما تعريف كنيم:

سپس (2.3 ) مي تواندبفرم زير نوشته شود:

كه:

در تعريف بالاي – مي توانيم به
برسيم.
با ضرب مجموعه محدوديت هاي اين مسأله دوگان بوسيله –كه



ما داريم:


در اين مورد موقعي كه
ماتريس – از درايه ها ي نا منفي تعريف مي شود بطوريكه
.اين ماتريس يك نقش مهم براي يافتن مقدار بهينه مسأله ماكزيمم
مقدار – روي بازه اعداد حقيقي كه بوسيله
تعريف مي شود
بطور ساده نمايش بالا مي تواند به شكل
نوشته شود.
همچنين يك زير ماتريس – از ماتريس داده شده – كه در
صدق مي كند براي تعيين مقدار دوگان مورد نياز براي حل
برنامه ريزي كسري (2.1) مهم خواهد بود.
اين مقادير دوگان براي يك نقطه – كه يك جواب بهينه مسأله بالا (2.5) است
به خوبي در شرايط 2و3 كان-تاكر صدق مي كنند. ما بايد داشته باشيم :

يا به طور ساده:

در اينجا – يك زير ماتريس ، ماتريس داده شده – فقط شامل ضرايب مجموعه محدوديت ها ي فعال در نقطه كنوني – است. همچنين از قضيه مكمل زايد داريم :
برا ي هر مجموعه بالااز محدوديت هاي فعال مقادير دوگان متناظر بايد مثبت باشند.ازاين رو يك زير ماتريس – از ماتريس – داده شده كه در
صدق مي كند براي يافتن مقادير دوگان مورد نياز براي تعيين
مجموعه محدوديت هاي فعال متناظر با مقادير دوگان مثبت بخاطر قضيه
مكمل زايد براي مجموعه بالا از محدوديت هاي فعال اهميت خواهد داشت.

روشمان را براي حل مسايل ( )بصورت زير خلاصه مي كنيم:
را محاسبه مي كنيم.
2- ماتريس – از درايه هاي نامنفي را كه – است پيدا مي كنيم.
3- يك زير ماتريس – از ماتريس داده شده – كه در –صادق باشد ر ا پيدا مي كنيم.
4-در سطر هاي – براي هر درايه مثبت محدوديت فعال متناظر در ماتريس- را تعيين مي كنيم.
5-يك دستگاه – از معادلات خطي را براي رسيدن به جواب بهينه – حل مي كنيم.بنابراين با استفاده از (2.6) به جواب بهينه مسأله () كه بوسيله (2.1)
تعريف مي شود مي رسيم.

3.نكته ها:
نكته(3.1):
ماتريس – از درايه هاي نامنفي كه – رابه عنوان ماتريس قطبي ، ماتريس – در نظر مي گيريم.
نكته(3.2):
با – در () مسأله بالا به يك مسأله برنامه ريزي خطي () تقليل مي يابد و از اين رو روشمان ميتواند براي حل – به عنوان حالت خاصي از – به استفاده از بحثي مشابه مورد استفاده قرار بگيرد.

4.به مثال زير توجه كنيد:





مسأله دوگان فعالند. محدوديت هاي 1 و 3



نتيجه گيري:

يك روش جديد براي حل توابع كسري خطي كه محدوديت هاي آن به شكل نامساوي هاي خطي اند ، داده شده است. هدف روش به طور اصلي حل جبري با استفاده از مفهوم دوگان مي باشد.
چون روش هاي پيشين كه بر پايه اطلاعات – هستند ممكن است در ضمن اينكه مسأله اندازه افزايش مي يابد مشكلاتي را داشته باشند ، بنظر مي رسد كه روش ما حساسيت كمتري نسبت به مسأله اندازه داشته باشد.

منبع:
برنامه ريزي خطي با يك هدف كسري :1973 – NOVAES . BITRAN
دوگان و تحليل حساسيت با تابع هدف كسري:1976- MAGNANTY . BITRAN
برنامه ريزي با توابع كسري خطي:1962-COOPER . CHANERS
شرط بهينگي در برنامه ريزي گويا. ( ژورنال قضيه بهينه سازي و كاربردها) :SING

[sajadhoosein]

هفت آسمانها


8 دايره و 8 كره ، 7 ميان دايره و 7 ميان كره در شكل توسعه يافته ستاره داوود ( 7 آسمانها )



در شكل توسعه يافته ستاره داوود ، خطوط در نقاطي با هم تقاطع دارند كه اگر نقطه مركزي را در نظر بگيريم ، ميتوانيم هشت دايره از آن نقطه رسم كنيم ، يعني شكل زير :






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



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

[sajadhoosein]

آشنایی با طراحی الگوریتم ها


تلاش بی پایان ذهن انسان های كنجكاو برای كشف ناشناخته ها و حل مسائل جالب یكی از جنبه های زیبای زندگی است. تاریخ علم نشان می دهد كه دانشمندان و ریاضیدانان متعددی عمر طولانی خود را وقف حل معماهای مختلف و شناسایی اسرارطبیعت و جامعه كرده و با حل هر مسأله نام خود را جاودانی كرده اند.
تكنولوژی كامپیوتر با توجه به پیشرفت جهشی خود در ۶۰ سال اخیر، هم به عنوان یك ابزار حل مسأله، هم به عنوان منبعی از كاربردهای متنوع آن، روز به روز جذاب تر شده و در این رابطه، الگوریتم به عنوان روش و مراحل حل مسأله، نقش كلیدی را در این فناوری ایفا می كند. یك مثال ساده برای الگوریتم، دستورالعمل های لازم برای روی هم قرار دادن قطعات مدل هواپیماست. این مونتاژ از قطعه خاصی شروع شده و سپس قطعات دیگر به ترتیب تا كامل شدن مدل، روی هم قرار می گیرند. یك برنامه كامپیوتری كه برای پیاده سازی و اجرای الگوریتم ها روی رایانه به كار می رود، مجموعه متناهی از دستوراتی است كه به ترتیب معینی از نخستین دستور به ترتیب تا انتها باید اجرا شوند.
این نوشته انواع الگوریتم ها را به صورت مختصر با عنوان مثال هایی برای هر كدام بررسی و مطالعه می كند. منظور از انواع الگوریتم ها، ارائه یك راه حل جامع و كارآمد برای مسائل مختلف است. الگوریتم ها هسته مركزی راه حل مسائل متعددی در بخش های علوم پایه، مسائل تجاری، رشته های مهندسی مانند طراحی پل ها، سدها، خودروها، هواپیماها، پیش بینی وضع جوی و نقشه های مربوطه، تجزیه و تحلیل ساختار مولكول ها و DNA، كشف ذخایر گاز و نفت و طراحی و بهینه سازی سیستم های كامپیوتری است.
از لحاظ تاریخی كلمه الگوریتم برگرفته از نام ریاضیدان معروف قرن نهم هجری، الخوارزمی است كه برای نخستین بار در كتاب معروف جبر و مقابله برای بعضی از مسائل ریاضی مانند معادلات خطی و معادلات درجه دوم، راه حل نوینی مطرح كرد كه تا آن مقطع زمانی ارائه نشده بود. الگوریتم به عنوان مراحل حل یك مسأله یا انجام یك كار، مجموعه ای متناهی از دستورالعمل هایی است كه برای رسیدن به خروجی های مطلوب با شروع از یك حالت اولیه به كار می رود.
در تعریف ریاضی الگوریتم به دستورالعمل ها یا رویه های خوش تعریف اطلاق می شود كه به وسیله ماشین تورینگ كه یك مدل انتزاعی از كامپیوترهای دیجیتال است، شبیه سازی و اجرا گردد.
روش های زیادی برای گروه بندی الگوریتم ها با توجه به قابلیت و توانایی های هر دسته وجود دارد. از یك دیدگاه كلی می توان الگوریتم ها را به دو گروه عمده الگوریتم های ترتیبی و الگوریتم های موازی تقسیم كرد.
● الگوریتم های ترتیبی
در این گروه از الگوریتم ها، رایانه فقط از یك پردازنده برای اجرای دستورالعمل ها به صورت ترتیبی (سریال) استفاده می كند. در این نوع رایانه ها كه به نام معماری فون نیومن معروف است، برنامه و داده ها در حافظه ذخیره می شوند. ریزپردازنده هر بار یكی از دستورات برنامه را بازیابی كرده، پس از تفسیر آن را اجرا می كند. چنین رایانه هایی را SLSD (جریان تك دستوری، جریان تك داده ای) می گویند. در اینجا به ۲ روش از الگوریتم های ترتیبی اشاره می شود.
▪ روش تقسیم و حل
در این روش، با استفاده از رویه های بازگشتی، مسأله اصلی را به زیرمسأله های كوچكتری تا جایی تقسیم می كنند كه امكان تقسیم مجدد آن وجود نداشته باشد. سپس با حل ساده ترین زیرمسأله ها و تركیب آنها با یكدیگر می توان به حل مسأله اصلی نائل شد. رویه بازگشتی، الگوریتمی است كه با استفاده از فراخوانی خودرویه، دستورات تشكیل دهنده آن را تا رسیدن به شرایط اولیه و خروج از آن، مكرر اجرا كند.
روش تقسیم و حل، یك روش طراحی بالا به پائین است، یعنی الگوریتم یك مسأله از سطح بالا به زیرمسأله ها تقسیم بندی می شود. به عنوان مثال می توان الگوریتم های جست وجوی دورویی در یك بردار (آرایه یك بعدی) یا در یك جدول (آرایه دوبعدی) ، مرتب سازی تركیب و مرتب سازی سریع ، مسأله برج های هانوی ، ضرب «ماتریس به روش استراسن»، عملیات محاسباتی مانند ضرب و جمع اعداد صحیح بسیار بزرگ و جدول مسابقات تیم ها در یك جام حذفی را با استفاده از روش تقسیم و حل انجام داد.
▪ الگوریتم برنامه نویسی پویا
در برنامه نویسی پویا به عنوان یك روش طراحی الگوریتم، چون راه حل مسأله از طریق تقسیم آن به زیرمسأله ها به دست می آید، مشابه روش تقسیم وحل است ولی برعكس آن، یك روش پائین به بالا یا یك روش جز به كل است، یعنی حل مسأله را از ساده ترین زیرمسأله شروع كرده و با قراردادن نتایج در یك آرایه، آنها را در محاسبات بعدی استفاده می كنند. در صورتی كه روش تقسیم و حل فاقد حافظه است. این روش طراحی الگوریتم، دارای شرایط بهینه سازی است وزیرمسأله ها هم بهینه هستند. به عنوان مثال، اگر برنامه نویسی پویا، برای مسأله كوتاه ترین مسیر كه با یك گراف مدل سازی می شود به كار می رود، هر زیرگرافی هم باید دارای ویژگی كوتاه ترین مسیر بین رأس های متشكله آن باشد. اگر اصل بهینه سازی برای یك مسأله مفروض، صدق كند می توان یك رابطه بازگشتی برای حل مسأله و زیرمسأله ها ارائه داد.
الگوریتم فلوید برای تعیین كوتاه ترین مسیر، ضرب زنجیری ماتریس ها، درخت های جست وجوی دورویی بهینه حاصل جمع بهینه لیستی از n عدد حقیقی، تعیین طولانی ترین زیر مشترك در دو رشته دلخواه و مسأله فروشنده دوره گرد (TSP) با استفاده از روش برنامه نویسی پویا قابل انجام هستند.
▪ الگوریتم های حریصانه
الگوریتم های حریصانه مشابه برنامه نویسی پویا، بیشتر برای حل مسائل بهینه سازی به كار می روند. با این اختلاف كه در برنامه سازی پویا از یك رابطه بازگشتی برای حل زیرمسأله ها استفاده می كنند. در روش حریصانه، تقسیم مسأله ها به زیر مسأله ها انجام نمی گیرد و روش تكرارشونده را به كار می برند.
در روش حریصانه در هر لحظه، با توجه به عناصر داده ای مفروض، عنصری را كه دارای ویژگی بهترین یا بهینه است (مانند كوتاه ترین مسیر، بالاترین ارزش، كمترین سرمایه گذاری، بیشترین سود و ...) انتخاب می كنند بدون این كه انتخاب های قبلی ما بعدی را در نظر بگیرد ولی انتخاب های بهینه محلی همواره منجر به راه حل بهینه سراسری نمی شود. این روش انتخاب، منجر به ارائه یك الگوریتم ساده و كارآمد می شود.
تعیین درخت های پوشالی مینیمم با استفاده از الگوریتم های پرایم، كروسكال محاسبه كوتاه ترین مسیر تك منبع با كاربرد الگوریتم دایجسترا ، مسأله زمان بندی مانند بهینه سازی زمان انتظار و سرویس به كاربران برای دسترسی به دیسك گردان ها در یك شبكه رایانه ای، تعیین حداكثر بهره برای مشتریان در یك زمان معین و مسأله كوله پشتی (كسری، صفرو یك) با استفاده از روش حریصانه قابل اجرا هستند.
الگوریتم عقبگرد
▪ الگوریتم عقبگرد، برای یافتن جواب مسأله ای با فضای جست وجو به طور گسترده ای به كار می رود و از آن به عنوان حالت اصلاح شده جست وجوی عمقی یك درخت نام می برند. در این روش، منظور از عقبگرد، پیدا كردن راه حل مسأله از طریق جست وجوی عمقی در درخت فضای حالت برای یافتن گره های امید بخش است. در صورتی كه موقع پیمایش درخت به یك گروه غیرامیدبخش برخورد كند كه منجر یه یافتن جواب مسأله نمی شود، باید به سمت ریشه درخت برگشته و عمل جست وجو را در دیگر شاخه ها ادامه داد. این فرآیند را هرس كردن درخت فضای حالت می نامند.
به عنوان مثال، مسأله n وزیر، استفاده از الگوریتم مونت كارلو برای نخستین كارآیی یك الگوریتم عقبگرد، مسأله حاصل جمع زیرمجموعه ها، مسأله رنگ آمیز گراف، مسأله مدارهای هامیلتونی، مسأله كوله پشتی صفر و یك با استفاده از راهبرد عقبگرد، قابل حل هستند.
▪ الگوریتم شاخه وقید
روش شاخه و قید با ایجاد درختی از زیرمسأله ها با توجه به مسأله اولیه و پیمایش درخت بدون قاعده خاصی، دنبال جواب های مسأله می گردد. این روش شكل بهبود یافته ای از الگوریتم عقبگرد است كه در آن شیوه خاصی را برای ملاقات گره ها اعمال نمی كند و در هر گره برای امیدبخش بودن آن گره، قید یا عددی را محاسبه می كند و فقط برای مسائل بهینه سازی استفاده می شود. به عنوان مثال مسأله كوله پشتی صفر و یك، بهترین جست وجو با هرس كردن، ایجاد یك تور بهینه و محاسبه طول آن، مسأله فروشنده دوره گرد و استنباط با عكس العمل استفاده از روش شاخه و قید اجرا می شود.
ا▪ لگوریتم جست وجو و پیمایش
این روش روی دو گروه از مسائل قابل اعمال هستند:
۱) روش های پیمایش
در روش های پیمایش، باید تك تك گره های یك درخت دودویی برای بررسی مقادیر عددی آنها ملاقات و بررسی جست وجو شوند.
۲) روش های جست وجو
روش های جست وجو كه حالت عمومی تری نسبت به روش های پیمایش هستند، می توانند روی رئوس یك گراف اعمال شوند.
جست وجو و پیمایش در درخت های دودویی و جست وجو و پیمایش گراف ها به صورت عرضی یا عمقی به وسیله این الگوریتم ها قابل حل هستند.
▪ الگوریتم ژنتیك
اخیراً دانشمندان رشته رایانه از نظریه تاریخی داروین برای حل مسائل علمی پیچیده استفاده می كنند تا بتوانند عملیات هوشمندانه را پیش ببرند. ۳ عامل اصلی نظریه داروین عبارتند از:
۱) تنوع: مشخصات والدین متفاوت با یكدیگر تركیب شده تا بتوانند موجودی را با خصوصیات برتر به وجود آورند.
۲) تصادف: عاملی است كه تغییراتی را در موجود فرزند ایجاد می كند.
۳) انتخاب: محیط، موجوداتی را گزینش می كند كه دارای شایستگی بالاتری از لحاظ ادامه حیات و تولید مثل باشند.
مدلسازی در الگوریتم ژنتیك بر پایه فرایند طبیعی تكامل و اصل بقای برتر است و مشابه طبیعت، عمل را با حفظ و تقویت جنس برتر و از بین رفتن جنس ضعیف انجام می دهد. در نتیجه منجر به ایجاد قدرتمندترین ساختار یا بهینه ترین آن برای بقا در محیط می شود. روش انتخاب ژنتیكی در طول میلیون ها سال، طبیعتی را پدید آورده كه براساس اصل بقای برتر و جهش سازنده قادر به حل پیچیده ترین مسائل از جمله ساختارهای پروتئینی برپایه بهترین جانشین آمینواسیدها عمل می كند.
منبع:مناف ـ شریف زاده
روزنامه ایران