سرفصل های درس نظریه علوم کامپیوتر

در سرفصل های درس نظریه علوم کامپیوتر میخوانیم :

نام بسته : نظریه علوم کامپیوتر

————————————————————————-

فهرست

فصل 1 : زبان ها، ماشین ها و گرامرها

1-1- معرفي زبان هاي رشته اي  

1-1-1- توابع رشته‌ها

 تمرين  

1-1-2- ساختار زبان‌ها

 تمرين

1-2- گرامرها و پذيرنده ها

1-2-1- گرامرها

1-2-2- ماشين پذيرنده متناهي

1-3- زبانهاي منظم 

1-3-1- الگوريتم تبديل NFA به DFA

1-3-2- كاهش تعداد وضعيت‌هاي DFA

 تمرين  

1-3-4- عبارت منظم

1-3-5- گرامرهاي منظم

 تمرين

1-3-6- ساختار زبانهاي منظم

1-3-6-1- تعيين عضويت در زبان منظم 

1-3-6-2- تشخيص زبان‌هاي غير منظم 

 تمرين  

1-4- زبانهاي مستقل از متن  

1-4-1- اشتقاق و پويش

     تمرین

1-4-2- گرامرهای نرمال

1-4-3- آتاماتاي پشته‌اي

      1-4-4- خواص خانواده زبان‌هاي مستقل از متن  

1-5- ماشین تورینگ

    1-5-1-گرامرهای نامقید 

     1-5-2- دسته بندی زبان ها و گرامرها  

        1-5-2-1- مقایسه ویژگی انواع زبان ها  

         1-5-2-2- انواع ماشین ها  

          1-5-2-3- انواع گرامرها

فصل 2 : توابع و برنامه ها

2-1- تابع 

2-2- توابع محاسبه پذیر 

2-3- برنامه ها

2-4- توابع بازگشتی اولیه:

2-4-1- تابع مینیمم سازی

 تمرین  

فصل 3 : مجموعه های بازگشتی و بازگشتی برشمردنی  

3-1- شمارش پذیری  

3-2- عددگذاری گودل:

3-3- مجموعه های بازگشتی  

3-4- کاهش پذیری  

         تمرین

منابع این بسته درسی

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

 فصل اول : زبانها، ماشين­ها  و گرامرها

1-1-          معرفي زبان­هاي رشته­اي

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

مجموعه همه رشته‌هاي توليد شده توسط يك الفباي خاص را با نماد خواهيم شناخت. بايد از اين سوال که آيا  فقط رشته­هاي متناهي را شامل مي­شود يا رشته­هاي نامتناهي را هم در بر مي­گيرد؟ به شکلي فرار کرد. براي اينکار تعريف : P^N ® S براي  مناسب خواهد بود. هر زير مجموعه از مانند L (L نماد عمومي براي زبان) يك زبان ناميده مي‌شود. به طور مثال اگر آنگاهيك زبان است.

تعريف 1: رشته­ تهي

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

1-1-1-               توابع رشته‌ها

الف- تابع الحاق (اتصال): اگر v و w دو رشته باشند.  رشته‌ي جديدي است كه با قرار گرفتن v در ادامه w به دست مي‌آيد.  زير رشته‌هايي براي رشته‌ي جديد به حساب مي‌آيند. زير رشته عبارت است از بخش پيوسته‌اي از يك رشته. ساختار جبري تابع الحاق را در زير نشان داده­ايم:

1. عضوي بي‌اثر عملگر: 
2. عملگرشركت‌پذير است:
3. عملگرآبلي(جابه‌جايي)  نيست: ، البته اگر الفباي L تك عضوي باشد. آبلي خواهد بود.
4. الحاق تواني:
5. رشته‌ي تواني:، نوع خاصي از الحاق تواني است.
6. اتصال وارون.
7. رشته­هاي وارون: ، شکل خاصي از اتصال وارون
8. رشته‌اي است كه از راست به چپ از روي r خوانده شود.

ب- تابع تقسيم: گاهي اوقات مي‌خواهيم از بخشي از يك رشته صرف‌نظر كنيم يا رشته‌اي را به بخش‌هايي تقسيم كنيم داريم:  در اينجا داريم:

ج- تابع Truncate: تابعي است كه سمت راست‌ترين علامت هر رشته را حذف مي‌كند. به طور مثال:

د- تابع even: اگر w رشته‌اي باشد even(w) رشته‌‌اي است كه از كنار هم قرار گرفته نشانه‌هايي كه در مكان‌هاي زوج w هستند به دست مي‌آيد.

ما مي‌توانيم انواع متفاوتي از تابع­هاي رشته را بسته به نوع كاري كه مي‌خواهيم انجام دهيم، تعريف نمائيم. در هر صورت بررسي ويژگي‌هاي هر عملگر مشابه موارد فوق خواهد بود.

بازار کار دکتری علوم کامیپوتر چه آینده ای خواهد داشت ؟

تمرين 1:

اگر در يك زبان برنامه‌نويسي توابع معرفي شده باشند الگوريتمي بيابيد كه يك رشته متناهي از ر ا گرفته و نشانه‌هاي b موجود در آن را الف- حذف كند ب- با a عوض نمايد. و نتيجه را به ما بدهد. در اين‌جا مي‌باشد.

1-1-2- ساختار زبان‌ها

اگر يك الفبا باشد و مجموعه همه رشته‌هايي كه با نمادهاي اين الفبا ساخته مي‌شوند. حال  مجموعه  را در نظر مي‌گيريم. اين مجموعه خانواده زير مجموعه‌هاي را به ما مي‌دهد، كه هر عضو آن يك زبان به شمار مي‌آيد. مثلاً اگر  باشدهر يک عضو  هستند.

توابع زيادي به شکل زير روي زبان‌ها تعريف شده اند.

الف- متمم يك زبان: که بصورت  است.       

مثال: 

در اينجا متمم يكديگرند نيز همين‌طورهستند.

ب- وارون يك زبان:    

وارون هر زبان نيز يك زبان است. مثلاً:  که البته در اينجا داريم:  البته لزوماً يك زبان با وارونش با هم برابر نمي‌باشند.

ج- ضرب دو زبان:  

برای مشاوره اینجا بزنید