استفاده از روش های نظریه گراف ها برای بهبود خوش وضعی ماتریس نرمی سازه ها

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

استفاده از روش های نظریه گراف ها برای بهبود خوش وضعی ماتریس نرمی سازه ها

پروژه رنگ آمیزی گراف با الگوریتم ژنتیک. doc

اختصاصی از فی فوو پروژه رنگ آمیزی گراف با الگوریتم ژنتیک. doc دانلود با لینک مستقیم و پر سرعت .

نوع فایل: word

قابل ویرایش 60 صفحه

چکیده:

مسائلی در دنیای واقعی وجود دارند که با توجه به اندازه ورودی ( اندازه ورودی به صورت تعداد کاراکتری تعریف می شود که برای نوشتن ورودی لازم است ) در بدترین حالت در زمان چند جمله ایی قابل حل نیستند . برای چنین مسائلی بدست آوردن جواب قطعی در مدت زمان مناسب و هزینه مناسب ، امکان پذیر نبود . بنابراین ایده روش ژنتیک سلولی در علم زیست شناسی ، کمک بسیار شایانی در بدست آوردن جواب بهینه و( درتکرارهای بیشتر جواب قطعی ) کرده است . الگوریتمهای ژنتیکی برای حل مسائل NP-Hard ، طراحی Neural Network ها ،Nonlinear dynamic system ها ،Stragety plannig و... بکار می روند.یکی از موارد استفاده GA در حل مسائل NP-Hard اعمال بر مساله GraphColoring است که ما در این مقاله در این مورد بحث خواهیم کرد.

الگوریتم ژنتیک ، تعاریف ژنتیکی علم زیست شناسی را بصورت انتزاعی و به تبعیت از ژنتیک سلولی پیاده سازی می کند.

مقدمه:

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

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

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

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

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

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

فهرست مطالب:

چکیده

مقدمه

اطلاعات اولیه علم ژنتیک در طبیعت

تاریخچه ژنتیک

تقسیم بندی علم ژنتیک

تغییرات نسبتهای مندلی

احتمالات

پیوستگی ژنها

جهش ژنی

ژنها و کروموزومها

. متابولیزم RNA

متابولیزم پروتئین

تنظیم بیان ژن

فناوری DNA نوترکیبی

 آشنایی با الگوریتم های ژنتیکی ( Genetic

Algorithms ) 

تاریخچه

زمینه زیست شناسی

 مسئله های بغرنج

مسائل NP

چند نمونه از مسائل NP   

 پیچیدگی محاسباتی و کنترل ناپذیری مقدمه

ای بر نظریه NP

کنترل ناپذیری

تعریف مجدد کنترل ناپذیری

سه گروه کلی مسائل

نظریه NP

مجموعه NP

مسائل NP کامل (NP_Complete)

معرفی یکی از مسائل NP

دسته بندی الگوریتمهای جستجو

الگوریتمهایی برای جستجوی آگاهانه

 الگوریتمهای جستجوی محلی

الگوریتم قطعی

الگوریتم حریصانه (Greedy Alg.) ابتدا همه

الگوریتم درخت پوشای حداقل (MST) ابتدا درخت

آتوماتاهای یادگیر

رفتار متقابل محیط و آتوماتای یادگیر

کاربرد آتوماتاهای یادگیر

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

ویرایش عملگرهای یک الگوریتم ژنتیک

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

تعاریف مقدماتی

 ژن

 کروموزوم

فضای جستجو

جمعیت ژنتیکی

تابع شایستگی

عملگرهای ژنتیک

انواع روشهای رمزگذاری کروموزوم

انواع روشهای انتخاب

انواع روشهای عمل برش

عملگر برش

انواع روشهای عمل جهش

عملگرجهش روی نمایش باینری

 پارامترهای کنترلی

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

احتمال برش و احتمال جهش

مقایسه GAs با تکنیکهای دیگر

مزایای الگوریتم ژنتیک در مقایسه با سایر

روشها

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

حل مساله  Graph-Coloring با استفاده از

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

توضیح

نکات جالب مسئله

هدف مسئله پیدا کردن حداقل رنگ برای گراف

ارائه یک راهکار برای حل مسئله فوق

 پارامترهای کنترلی

نتیجه گیری

 منابع و مراجع

منابع و مأخذ:

[1] D.S.Johnson, and L.A MeGeoch, " Exprimental Analysis of Heuristics for the STSP "

[2] D.E.Goldberg , " Genetict Algorithms in search , optimization and Machine Learning ", Reading MA:Addition-Wesley,1989.  

 [3] Mars,P.and Narenda.K.S, and Chrystall,M , "Learning Automata Control of Computer Communication Neworks ", proc.of Third Yale workshop on Application of Adoptive System Teheory, Yale Univercity , 1983.

[4] F.busetti ," Genetic Algorithms Overview "  

 [5] J. Cirasella D.S Johnson, L.A.McGeoch, and W. Zhang, " The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests ",in algorithm Engineering and Experimentation,Third International Workshop, ALENEX 200 Lecture Notes computer Science, Vol.2153,Spring,Berlin,2001,32-59.

[6] M.Grotschel, and O.Holland, " Solution of Large-Scale Symmetric Traveling salesman Problem", Mathematical Programming 51,1991,141-202.   

 [7] M.Padberg, and G.Rinaldi, "A Branch-And-cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems " ,SLAM Review 33,1991,60-100.   

 [8] M.Junger, G.Reinelt, and G.Rinaldi, " The Traveling Saleman Problem ", in:Handbooks in Operations Research and Management Science, Volume 7 (M.O.Ball, T.Mangnanti, C.L.Monma, and G.Nemhauser, eds), Elsevier Science B.V., 1995 ,225-330.  

 [9] Genetic Algorithms Principles And Perspectives A Guide to GA Theory

Colin R.Reeves Jonathan E.Rowe kluwer Academic Publishers

دانلود تحقیق کاربرد گراف درریاضی گسسته

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

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

مسئله کوتاهترین مسیر

فرض کنید به هر یال e ی گراف G عددی نسبت داده شده باشد، در این صورت عدد نسبت داده شده وزن هر سال و چنین گرافی را گراف وزن دار می‌نامیم. این اعداد تعبیرهای مختلفی در کاربردهای متفاوت می‌توانند داشته باشند، مثلا می‌تواند مقدار هزینه سفر از نقطه‌ای به نقطه دیگر یا معرفی مخارج ساختن یا نگهداری خطهای ارتباطی مختلف یا حتی بیانگر شدت دوستی بین دو فرد باشد. به عنوان مثال شبکه راه آهنی را تصور کنید شهرهای مختلف را به هم وصل می‌کند، هدف ما پیدا کردن مسیری با Min وزنی است که دو رأس را به هم وصل می کند که در اینجا وزنها معرف فاصله‌ها می‌باشند. الگوریتمی که به حل این مسئله می‌پردازد اولین بار توسط دیکسترا (1959) و بطور مستقل وایتینگ و هیلیه (1960) کشف کردند. این الگوریتم نه تنها کوتاهترین مسیر را می‌یابد بلکه کوتاهترین مسیر از به همه رأسهای گرا ف G را نیز پیدا می‌کند.

شامل 27 صفحه فایل word قابل ویرایش

تحقییق رشته ریاضی با موضوع شبکه ها و تطابق در گراف

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

شبکه ها

• شارش ها

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

تعریف 1-1 فرض کنیم N=(V,E) یک گراف سودار همبند بیطوقه باشد. N را یک شبکه یا یک شبکه حمل و نقل می‌نامند هرگاه شرایط زیر برقرار باشند:

(الف) رأس یکتایی مانند وجود دارد به طوری که ، یعنی درجه ورودی a، برابر 0 است. این رأس a را مبدأ یا منبع می‌نامند.

(ب) رأس یکتایی مانند به نام مقصد یا چاهک، وجود دارد به طوری که od(z)، یعنی درجه خروجی z، برابر با 0 است.

(پ) گراف N وزندار است و از این رو، تابعی از E در N، یعنی مجموعه اعداد صحیح نامنفی، وجود دارد که به هر کمان یک ظرفیت، که با نشان داده می‌شود، نسبت می‌دهد.

برای نشان دادن یک شبکه، ابتدا گراف جهت زمینه آن (D) را رسم کرده و سپس ظرفیت هر کمان را به عنوان برچسب آن کمان قرار می‌دهیم.

مثال 1-1 گراف شکل 1-1 یک شبکه حمل و نقل است. در این جا رأس a مبدأ و راس z مقصد است و ظرفیتها، کنار هر کمان نشان داده شده‌اند. چون ، مقدار کالای حمل شده از a به z نمی‌تواند از 12 بیشتر شود. با توجه به بازهم این مقدار محدودتر می‌شود و نمی‌تواند از 11 تجاوز کند. برای تعیین مقدار ماکسیممی که می‌توان از a به z حمل کرد باید ظرفیتهای همه کمانهای بشکه را درنظر بگیریم.

 تعریف 1-2 فرض کنیم یک شبکه حمل و نقل باشد تابع f از E در N، یعنی مجموعه اعداد صحیح نامنفی، را یک شارشبرای N می نامند هرگاه

الف) به ازای هر کمان و

ب) به ازای هر ، غیر از مبدأ a یا مقصد z ، (اگر کمانی مانند (v,w) وجود نداشته باشد، قرار می دهیم

مقدار تابع f برای کمان e، f(e) را می توان به نرخ انتقال داده در طول e، تحت شارش f تشبیه کرد. شرط اول این تعریف مشخص می‌کند که مقدار کالای حمل شده در طول هر کمان نمی تواند از ظرفیت آن کمان تجاوز کند، کران بالایی شرط الف راقید ظرفیت می‌نامند.

شرط دوم، شرط بقا نامیده می شود و ایجاب می کند که، مقدار کالایی که وارد رأس مانند v می شود با مقدار کالایی که از این رأس خارج می شود برابر باشد. این امر در مورد همه رأسها به استثنای مبدأ و مقصد بر قرار است.

مثال 1-2 در شبکه های شکل 1-2، نشان x,y روی کمانی مانند e به این ترتیب تعیین شده است که y , x=c(e) مقداری است که شارشی مانند f به این کمان نسبت داده است. نشان هر کمان مانند e در صدق می کند. در شکل 1-2 (الف)، شارش، وارد رأس می شود،5 است، ولی شارشی که از آن رأس خارج می شود 4=2+2 است. بنابراین، در این حالت تابع f نمی تواند یک شارش باشد. تابع f برای شکل 1-2 (ب) در هر دو شرط صدق می کند و بنابراین، شارشی برای شبکهء مفروض است.

توجه داشته باشید که هر شبکه، حداقل دارای یک شارش است، زیرا تابع fای که در آن به ازای هر داشته باشیم: در هر دو شرط تعریف
1-2 صدق می کند. این تابع، شارش صفر نامیده می شود.

تعریف 1-3 فرض کنیم f شارشی برای شبکه حمل و نقل N=(V,E) باشد.

الف) کمانی مانند e متعلق به این شبکه را اشباع شده می نامند هر گروه f(e)=c(e) اگر f(e)<c(e) این کمان را اشباع نشده می نامند.

ب) اگر a مبدأ N باشد، را مقدار شارش می نامند.

مثال 1-3 در شبکه شکل 1-2 (ب) فقط کمان اشباع شده است. هر یک از کمان‌های دیگر اشباع نشده است. مقدار شارش این شبکه

است. ولی آیا شارش دیگری مانند وجود دارد که به ؟

می‌گوئیم شارش fدر N، یک شارش ماکزیمم است، هر گاه هیچ شارش دیگری مانند در N با شرط وجود نداشته باشد.

هدف ما در ادامه، تعیین یک شارش ماکزیمم است. برای انجام این کار، ملاحظه می‌کنیم که در شکل 1-2 (ب) داریم.

درنتیجه، شارش کل خارج شده از مبدأ a شارش کل وارد شده به مقصد z برابر است.

نکته اخیر در مثال 1-3 شرط معقولی به نظر می‌رسد، ولی آیا در حالت کلی چنین وضعیتی روی می دهد؟ برای اثبات آن در مورد هر شبکه دلخواه به نوع خاصی از مجموعه های برشی که در قسمت بعد می‌آید، نیاز داریم.

 )

متن کامل را می توانید دانلود نمائید

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

ولی در فایل دانلودی متن کامل پایان نامه

همراه با تمام ضمائم (پیوست ها) با فرمت ورد word که قابل ویرایش و کپی کردن می باشند

موجود است

مقاله شبکه ها و تطابق در گراف

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

تعداد صفحات : 50

فرمت فایل : word (قابل ویرایش)

فهرست مطالب :

عنوان

مقدمه

فصل 1

شبکه ها

1-1 شارش ها

1-2 برش ها

1-3 قضیه شارش ماکزیمم – برش مینیمم

1-4 قضیه منجر

فصل 2

تطابق ها

2-1 انطباق ها

2-2 تطابق ها و پوشش ها در گراف های دو بخش

2-3 تطابق کامل

2-4 مسأله تخصبص شغل

تعریف 1-1 فرض کنیم N=(V,E) یک گراف سودار همبند بیطوقه باشد. N را یک شبکه یا یک شبکه حمل و نقل می‌نامند هرگاه شرایط زیر برقرار باشند:

(الف) رأس یکتایی مانند  وجود دارد به طوری که ، یعنی درجة ورودی a، برابر 0 است. این رأس a را مبدأ یا منبع می‌نامند.

(ب) رأس یکتایی مانند  به نام مقصد یا چاهک، وجود دارد به طوری که od(z)، یعنی درجة خروجی z، برابر با 0 است.

تعریف 1-2 فرض کنیم  یک شبکة حمل و نقل باشد تابع f از E در N، یعنی مجموعة اعداد صحیح نامنفی، را یک شارش برای N می نامند هرگاه

الف) به ازای هر کمان  و

ب) به ازای هر ، غیر از مبدأ a یا مقصد  z ،  (اگر کمانی مانند (v,w) وجود نداشته باشد، قرار می دهیم

تعریف 1-5 برش C در N، یک برش مینیمم است، اگر هیچ برش دیگری مانند  در N با شرط  وجود نداشته باشد.

اگر  یک شارش ماکزیمم و  یک برش مینیمم به عنوان حالت خاصی از قضیه 1-1

داریم:   (1-4)            

1-3 قضیه شارش ماکزیمم – برش مینیمم

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

  

فرض کنید f یک شارش در شبکه N باشد. به هر مسیر S در N، یک عدد صحیح نامنفی l(S) به صورت روبرو نسب می‌دهیم:

اگر t یک کمان رو به جلو از S باشد.

اگر t یک کمان معکوس از S باشد.

 

که در آن:

شارش اصلاح شده بر پایة S می ‌خوانیم.

در شکل 1-4 (ب) شارش اصلاح شده شبکه 1-4 (الف) بر پایه مسیر -f افزایشی  نشان داده شده است.

شکل 1-4 (الف) مسیر -f افزایشی S (ب) شارش اصلاح شده بر پایه f

در شکل (الف)

در شکل (ب)