چکیده

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

کلمات کلیدی

1- آتاماتون سلولی 2- آتاماتون یادگیر 3- تناظر گراف

4- مدل مخفی مارکوف 5- آتاماتون قطعی 6- آتاماتون تصادفی

 

فهرست مطالب

عنوان..................................................................................................... صفحه

1- مقدمه..................................................................................................................................................

1-1-مقدمه..............................................................................................................................

2- آتاماتون سلولی...............................................................................................................................

2-1- مقدمه.............................................................................................................................

2-2- تاریخچه آتاماتون سلولی.........................................................................................

2-3- ساده ترین آتاماتون سلولی.....................................................................................

2-4- آتاماتون سلولی معکوس پذیر.................................................................................

2-5- آتاماتون سلولی Totalistic......................................................................................

2-6- استفاده از آتاماتون سلولی در علوم پنهان شناسی.............................................

2-7- آتاماتونهای وابسته....................................................................................................

2-8- آتاماتون سلولی در طبیعت.......................................................................................

2-9- خلاصه.......................................................................................................................................

3-آتاماتون یادگیر.................................................................................................................................

3-1- مقدمه.............................................................................................................................................

3-2-محیط..............................................................................................................................

3-2-1-تعریف محیط از دیدگاه منطقی.............................................................

3-2-1-1- موجودیتهای محیط منطقی.............................................

3-2-2- رده بندی محیط از دیدگاه خروجی آن...............................................

3-3- آتاماتون.......................................................................................................................

3-3-1- چگونگی عملکرد آتاماتون....................................................................

3-3-2- رده بندی آتاماتون بر اساس تابع گذار و تابع خروجی.................

3-3-2-1- آتاماتون قطعی..................................................................

3-3-2-2- آتاماتون تصادفی.............................................................

3-3-2-3- مثالی از آتاماتون قطعی..................................................

3-4- اتصال بازخوردی بین محیط و آتاماتون...............................................................

3-5- آتاماتون با ساختار ثابت و آتاماتون باساختار متغیر........................................

3-5-1- آتاماتون یادگیر با ساختار ثابت.........................................................

3-5-1-1- آتاماتون یادگیر دو حالته (L_2,2)....................................

3-5-1-2- آتاماتون حافظه دار – با دو عمل Testline))................

3-5-1-3- آتاماتون حافظه دار-با بیش از دو عمل Testline)).....

3-6- خلاصه..........................................................................................................................

4-تعريف مدل مخفي ماركوف............................................................................................................

4-1- مقدمه.............................................................................................................................

4-2- تعريف مدل مخفي ماركوف......................................................................................

4-3- فرضيات در تئوري HMM.......................................................................................

4-4- سه مسأله مبنايي در HMM: ..................................................................................

4-4-1 مساله تخمین و الگوریتم مورد استفاده .............................................

4-4-2- مسأله رمزگشايي و الگوريتم Viterbi:..............................................

4-4-3- مسأله يادگيري.......................................................................................

4-5- معيار Maximum Likelihood (ML):....................................................................

4-5-1- روش Baum-Welch...........................................................................

4-5-2- روش Gradient base...........................................................................

4-5-2-1- گذارهاي احتمالاتي در Gradient...................................

4-6- احتمال مشاهدات در Gradient.................................................................................

4-6-1- معيار Maximum Mutual Information (MMI)...........................

4-7- خلاصه..........................................................................................................................

5- حل مسائل تناظر گرافها و آتاماتون های یادگیر.........................................................................

5-1- مقدمه.............................................................................................................................

5-2- استفاده‌ از آتاماتون يادگير براي تناظر بين دو گراف..........................................

5-2-1- ساختن گراف‌هاي تصادفي...................................................................

5-2-2- آتاماتون يادگير و تناظر دو گراف......................................................

5-2-2-1- استفاده‌ از اتصال‌هاي مشابه Tsetline

به عنوان آتاماتون مهاجرت اشياء.......................................................

5-3- نتايج شبيه‌سازي‌هاي مختلف براي آتاماتون Tsetline.....................................

5-4- خلاصه..........................................................................................................................

6- نمونه برنامه های کاربردی شبیه ساز آتاماتون های سلولی..................................................

6-1- مقدمه.............................................................................................................................

6-2- برنامه pattern matching..........................................................................................

6-2-1- ارائه source code براي برنامه pattern matching......................

6-3- برنامه پياده سازي game of life توسط conway..............................................

6-3-1- ارائه source code براي برنامه conway ........................................

6-4- برنامه شبيه سازي آتاماتون سلولي.......................................................................

6-4-1- ارائه source code براي برنامه midi sampler..............................

6-5- پياده سازي conway بصورت trap door ...........................................................

6-5-1- ارائه source code براي trap door.................................................

6-6- پياده سازي conway بصورت population .........................................................

6-6-1- ارائه source code برنامه population..............................................

6-7- پياده سازي يك نمونه آتاماتون سلولي خاص يك بعدي و دو حالته ..............

6-7-1- ارائه source code براي آتاماتوني يك بعدي و دو حالته.............

6-8- برنامه تجسم و creatur sampler............................................................................

6-8-1- ارائه source code براي برنامه creatur sampler........................

6-9- پياده سازي دو بعدي Conway...............................................................................

6-9-1- ارائه source code...............................................................................

6-10- پياده سازي يك آتاماتون سلولي دو حالته و دو بعدي عمومي......................

6-10-1 ارائه source code.............................................................................

6-11- برنامه شكار رنگهاي Dave....................................................................................

6-11-1 ارائه source code برنامه dave.........................................................

6-12 خلاصه..........................................................................................................................

ضمیمه.....................................................................................................................................................

قسمت اول ..............................................................................................................................

قسمت دوم...............................................................................................................................

قسمت سوم.............................................................................................................................

قسمت چهارم...........................................................................................................................

منابع.........................................................................................................................................................

 

 

 

 

فصل اول

 

مقدمه

1-1-مقدمه

بدون شك گسترش روز افزون علم چه در تئوري و چه در كاربرد، انسانها را موظف كرده زمينه هاي مختلف علوم را چه در سطح و چه در عمق گسترش دهند. در مورد آتاماتون سلولي و نيز آتاماتون يادگير و كاربردهاي آنها در متون آكادميك سخن بسيار گفته شده و در اين مجموعه ناچيز سعي شده با معرفي آنها و چند نمونه از كاربردهايشان، كليد ورود به اين زمينه بي انتها بدست آورده شود. آتاماتون سلولي مدلي است گسسته كه در تئوري شمارش پذيري، رياضيات و علوم نظري كاربردهاي زيادي دارد. شايد در سال 1940 كه STANISLAW ULAM در حال تحقيق در ازمايشگاه ملي LOS ALAMOS بود هرگز تصور نمي كرد كه روزگاري، مطالعه او روي شبكه هايي منظم با عناصري تاثير پذير از يكديگر تا حد بي حد گسترش يابد. چنانچه از اين مباحث بگذريم، نخستين چيزي كه چارچوب آتاماتون سلولي را شكل ميدهد عناصري سلولي شكل هستند كه رفتار هر يك از اين سلولها متاثر از وضعيت فعلي خود و همسايگانش مي باشد. اتاماتون سلولي ميتوان چندين بعد داشته باشد و هر سلول مي تواند پذيرای چندين حالت باشد. در فصل 2 اين مجموعه سعي شده ضمن تعريف آتاماتون سلولي تعدادي اندك از انواع آنها و نيز كاربردهايشان ذكر شود.

در فصل 3 نيز سعي شده ضمن تعريف آتاماتون يادگير، چند نوع از آنها ونيز نمونه هايي از يكي از انواع ان معرفي شود. در واقع اتاماتون يادگير يك ماشين حالتي است كه براي حل مسائل پيچيده و بهينه سازي و كنترل كردن مسائل قطعي، تصادفي و ياسيستمهاي نا مشخص بكار مي رود. براي يادگيري آتاماتون محيط نقش اساسي در پاسخ دهي و مطلع كردن آتاماتون دارد. در فصل 4 مدل مخفي ماركوف به تفصيل مورد بررسي قرار گرفته است. دليل اين امر شباهت بسيار بين مدل مخفي ماركوف و آتاماتون سلولي مي باشد.

در فصل پنجم در مورد كاربرد آتاماتون يادگير در تناظر گرافها سخن گفته شده است. اهميت اين كاربرد هنگامي بر ما مشخص مي شود كه بدانيم طبق روشهاي كلاسيك BACK TRACKING ، تعيين تناظر بين دو گراف داراي پيچيدگي زماني O(n!) خواهد بود! و در نهايت در فصل ششم، 10 برنامه كاربردي كه آتاماتونهاي سلولي مختلفي راشبيه سازي كرده اند به همراه كد منبعشان معرفي شده اند تا ضمن درك بهتر آتاماتون سلولي و نحوه عمل ان بتوان از نمونه كوچكي از كاربردهاي آن آگاه شد. در نهايت و در ضميمه، اصل منابع اينترنتي اين مجموع آورده شده است. تا چنانچه با گذر زمان آدرس آنها تغيير كند، بتوان براي يافتن مطالبي بيشتر به اين مراجع دسترسي داشت. لازم به ذكر است در اين مجموعه در موقعيتهایي به اين منابع ارجاع شده كه مطالب تنها جنبه تعريفي داشته و اين تعريفها بين مراجع مختلف استاندارد مي باشند . انتخاب اين منابع از سايتهاي اينترنتي تنها به دليل جمع و جور بودن و نيز نگارش ساده و در عين حال مختصر و مفيد آنها مي باشد.