پاورپوینت فصل 1 مقدمه ای بر نظریه محاسبات (pptx) 49 اسلاید

دسته بندی : پاورپوینت

نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )

تعداد اسلاید: 49 اسلاید

قسمتی از متن PowerPoint (.pptx) :

فصل 1مقدمه ای بر نظریه محاسبات موضوع مورد بحث در این کتاب ، یعنی نظریه محاسبات ، سر فصل های متنوعی از جمله نظریه اتوماتا ، گرامرها و زبانهای صوری ، محاسبه پذیری و پیچیدگی را شامل میشود. مجموعه علائم و مقدمات ریاضی مجموعه گروهی از اعضا است که ساختاری غیر از عضویت ندارند. میگوییم x متعلق به مجموعه S است و مینویسیم x Є S . بالعکس ، عبارت S¢ x به این معناست که تعلق به مجموعه S نیست . مجموعه ها را میتوان با بیان توصیفی از اعضای ان در کروشه مشخص کرد. مجموعه ها یک مجموعه اگر حاوی تعداد متناهی از اجزا باشد ، مجموعه متناهی و در غیر اینصورت مجموعه نامتناهی میشود. اندازه یک مجموعه متناهی برابر با تعداد اعضا موجود در ان است و بصورت | S| نمایش داده میشود. مجموعه ها معمولا تعداد زیادی زیر مجموعه دارند. مجموعه تمام زیر مجموعه های مجموعه مفروض S ، مجموعه توانی S خوانده شده و بصورت 2S نشان داده میشود. اگر S متناهی باشد انگاه |s|2= |2s| نکته : ترتیب نوشتن اجزای یک زوج مهم است . نکته : حاصل ضرب دکارتی را میتوان روی بیش از دو مجموعه نیز تعریف نمود. S1*S2*…*Sn = {(x1,x2,…,xn) : xi Є Si } مجموعه ها را میتوان از طریق جداسازی به چند زیر مجموعه مجزا تقسیم کرد. S1US2U…USn = S هیچکدام از Si ها تهی نیستند. انگاه Sn,…,S2,S1 یک افراز (پارتیشن) از S خوانده میشوند. توابع و روابط تابع یا ضابطه ای است که به هر یک از اعضا یک مجموعه ، عضو منحصر به فردیاز مجموعه دیگر را نسبت میدهد. اگر f بیانگر یک تابع باشد ، انگاه مجموعه اول دامنه f و مجموعه دوم برد ان خوانده میشود و مینویسیم f : S1S2 فرض کنید که f(n)و g(n) دو تابع با دامنه ای از زیر مجموعه اعداد صحیح مثبت باشند. اگر عدد ثابت مثبت وجود داشته باشد که برای همه n های بزرگ f(n) ≤ cg(n) میگوییم که مرتبه رشدf حداکثر برابر g است و مینویسیم f(n)=O(g(n)) اگر f(n)| ≥ c|g(n)| | مثال 1-5 فرض کنید f(n)=2n2+3n n3 =(n)g h(n)=10n2+100 انگاه f(n)=O(g(n)) g(n)=Ω(h(n)) f (n)=ө(h(n))