دانلود پاورپوینت : نظریه زبانها و ماشینها

بخشی از پاورپوینت

اسلاید 1 :

فصل اول: ریاضیات مقدماتی

اهداف رفتاري:

دانشجو پس  از مطالعه اين فصل با مفاهيم زير آشنا خواهد شد:

n مفاهیم نمادگذاری و مفهوم تابع

n نظریه مجموعه ها

n مفهوم استقراء ریاضی

n گراف و انواع آن

اسلاید 2 :

1-1 نمادگذاری

nنماد ┌x┐: اشاره به کوچکترین عدد صحیح بزرگتر یا مساوی عدد حقیقی x دارد.┌-3.7┐=-3                 

┌4.5┐= 5                                                      

نماد ┌x┐ را جزء صحیح بالای x می نامیم.

n نماد └x┘: اشاره به بزرگترین عدد صحیح کوچکتر یا مساوی عدد حقیقی x دارد. └-3.7┘=-4                

└4.5┘= 4                                                    

نماد └x┘ را جزء صحیح پایین x می نامیم.

اسلاید 3 :

1-2 توابع

تابع f: تشکیل شده از یک متغیر با قاعده و قانون می باشد که به ازاء یک مقدار x ، مقدار منحصر به فردی را به f(x) نسبت می دهد.

نمودار یک تابع: مجموعه ای است از کلیه زوجهای مرتب که بوسیله تابع تعیین می شوند.

دامنه یک تابع: مجموعه مقادیری است که تابع به ازاء آنها تعریف می شود

اسلاید 4 :

1-2 توابع

تابع جامع: تابعی که از XبهY یک رابطه دودویی روی X*Y را داراست.

تابع جزئی: رابطه بین X*Yاست وقتی که

                                                 єf [x,y2]و єf [x,y1]

تابع یک به یک: تابعی که در آن هر عنصر xبه یک عنصر مجزا در برد تصویر شود.

تابع f:X   Y پوشاست اگر که برد f کل مجموعهYباشد.

اسلاید 5 :

1-3 نظریه مجموعه ها

نماد є به معنای عضویت است. بطوریکه x є X مشخص می کند که x یک عضو یا عنصر مجموعه Xاست.

از دو براکت{ } برای تعریف یک مجموعه استفاده می شود.  

   X= { 1,2,3 }                                                             

مجموعه هایی که تعداد زیاد یا تعداد نامتناهی عضو دارند بایستی به صورت ضمنی تعریف شوند.

                 {n l n=m² for some natural number m}

اسلاید 6 :

1-3 نظریه مجموعه ها

یک مجموعه با اعضایش مشخص می شود.

زیر مجموعه: مجموعه Yزیر مجموعهXاست به طوری که

Y   X اگر هر عضو Y عضوی از X نیز باشد.

اگرY یک زیر مجموعه از Xباشد و X≠Yآنگاه به Yیک زیر مجموعه کامل X میگوئیم.

اسلاید 7 :

1-3 نظریه مجموعه ها

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

                                       XυY = { z l z є X or z є Y}

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

X-Y = { z l z є X and  z є Y}                                    

مکمل X نسبت به U مجموعه عناصری در U است که در X نمی باشد.

اسلاید 8 :

1-4 استقراء ریاضی

مفاهیم مورد استفاده در استقراء ریاضی

پایه استقراء: عبارت به ازاء n=1(یا هر مقدار اولیه دیگر) درست است.

فرض استقراء: عبارت برای هر عدد دلخواه n≥1(یا هر مقدار اولیه دیگر) درست است.

گام استقراء: اگر عبارت به ازاء n درست است، آنگاه به ازاء n+1نیز درست می باشد. 

اسلاید 9 :

1-6 گراف ها

گراف جهت دار: اگر هر لبه گراف دارای جهت باشد به آن گراف جهت دار(digraph)می گویند.

گراف وزن دار: اگر به لبه ها مقادیری تخصیص یافته باشدبه آن مقادیر وزن و به آن گراف،گراف وزن دار می گوییم.

مسیر(path): در یک گراف جهت داربه دنباله ای از گره ها که بین هر گره و گره بعدی یک لبه وجود داشته باشد گفته می شود.

اسلاید 10 :

1-6 گراف ها

چرخه(cycle): به مسیری که از یک گره شروع شده و به خودش باز می گردد گفته می شود.

گراف چرخه ای: اگر گرافی شامل یک چرخه باشد به آن گراف چرخه ای گفته می شود.

مسیر ساده: مسیری که از از یک گره دو بار عبور نکند.

طول(length)یک مسیر در یک گراف وزن دار برابر مجموع وزنهای مسیر است.