سرفصل های درس یادگیری ماشین

نام بسته : یادگیری ماشین

—————————————————————

فهرست

فصل اول :مقدمه‌ای بر نظریه محاسبات                                        

مقدمات ریاضی و علامت‌گذاری مجموعه‌ها                 

سه مفهوم اساسی                   

برخی کاربردها                              

• فصل دوم : ماشین‌های متناهی
• پذیرنده‌های متناهی قطعی
• زبان‌ها و پذیرنده‌های متناهی قطعی
• زبان‌های منظم

پذیرنده‌های متناهی غیرقطعی              

معادل بودن پذیرنده‌های متناهی قطعی و غیرقطعی              

کاهش تعداد حالات در ماشین‌های متناهی      

• فصل سوم : زبان‌های منظم و گرامرهای منظم
• ارتباط بین عبارات منظم و زبان‌های منظم
• عبارات منظم برای زبان‌های منظم
• عبارات منظم برای توصیف الگوهای ساده
• گرامرهای منظم
• هم ارزی بین زبان‌های منظم و گرامرهای منظم
• فصل چهارم : خواص زبان‌های منظم
• خواص بستاری زبان‌های منظم
• سوالات مقدماتی درباره زبان‌های منظم

تشخیص زبان‌های غیرمنظم                          

• فصل پنجم : زبان‌های مستقل از متن

گرامرهای مستقل از متن                       

• اشتقاق‌های چپ‌ترین و راست‌ترین

تجزیه و ابهام      

• ابهام در گرامرها و زبان‌ها

گرامرهای مستقل از متن و زبان‌های برنامه‌نویسی               

• فصل ششم : ساده‌سازی گرامرهای مستقل از متن و شکل‌های نرمال

روش‌های تبدیل گرامرها                 

• حذف قوانین بی‌فایده
• حذف قوانین l

دو شکل نرمال مهم                  

یک الگوریتم عضویت برای گرامرهای مستقل از متن          

• فصل هفتم : ماشین‌های پشته‌ای

ماشین‌های پشته‌ای غیرقطعی                  

ماشین‌های پشته‌ای و زبان‌های مستقل از متن            

• گرامرهای مستقل از متن برای ماشین‌های پشته‌ای

ماشین‌های پشته‌ای قطعی و زبان‌های مستقل از متن قطعی      

گرامرهایی برای زبان‌های مستقل از متن قطعی        

• فصل هشتم : خواص زبان‌های مستقل از متن

دو لم تزریق                

خواص بستاری و الگوریتم‌های تصمیم‌گیری برای زبان‌های مستقل از متن              

فصل نهم :ماشین‌های تورینگ           

• ماشین‌های تورینگ به عنوان تراگذرها
• ترکیب ماشین‌های تورینگ برای انجام وظایف پیچیده
• تز تورینگ
• فصل دهم : مدل‌های دیگر ماشین‌های تورینگ
• گونه های جزئی در زمینه ماشین تورینگ
• ماشین‌های تورینگ با انتخاب توقف
• ماشین‌های تورینگ با نوار نیمه نامحدود
• ماشین تورینگ برون خط

ماشین‌های تورینگ با حافظه پیچیده‌تر             

ماشین‌های تورینگ غیرقطعی                     

یک ماشین تورینگ عمومی                    

ماشین‌های کراندار خطی                       

فصل یازدهم : سلسله مراتبی از زبان‌های صوری و ماشین‌ها         

زبان‌های بازگشتی و شمارش‌پذیر بازگشتی                      

گرامرهای بدون محدودیت                                  

گرامرها و زبان‌های حساس به متن                                  

سلسله مراتب چامسکی                       

• فصل دوازدهم : محدودیت‌های محاسبات الگوریتمی

برخی مسائلی که نمی‌توانند توسط ماشین‌های تورینگ حل شوند         

مسئله پس تناظر                    

• فصل سیزدهم : مدل‌های دیگر محاسبات
• توابع بازگشتی
• سیستم‌های پست

سیستم‌های بازنویسی                          

• فصل چهاردهم : مقدمه‌ای بر پیچیدگی محاسباتی

کارایی محاسبات          

ماشین تورینگ و پیچیدگی           

خانواده‌های زبان و رده‌های پیچیدگی               

رده‌های پیچیدگی P و NP

منابع و مآخذ      

بخش هایی از بسته درسی یادگیری ماشین

• 1-1 مقدمات ریاضی و علامت‌گذاری مجموعه‌ها
• یک مجموعه، دسته‌ای از اعضاء است، که به جز عضویت دارای هیچ ساختاری نمی‌باشند. برای نشان دادن این که x یک عضو از مجموعه S است، می‌نویسیم x Î S. برای نشان دادن این که x عضو مجموعه S نیست، می‌نویسیم xÏS. یک مجموعه با محصور کردن اعضایش در نشان ابروهای پیچیده (آکولاد) نشان داده می‌شود.
• برای مثال، مجموعه اعداد صحیح 0 و 1 و 2 این گونه نمایش داده می‌شود:
• نقطه‌چین زمانی استفاده می‌شود که معنای آن واضح و روشن باشد. مثلاً {a, b, …, z} برای همه حروف الفبای کوچک انگلیسی، {2, 4, 6,…} نشان‌دهنده همه اعداد صحیح زوج می‌باشد. در زمانی که توضیح احتیاج داریم، ما از اشارات نزدیک‌تر و صریح‌تری استفاده می‌کنیم. در این صورت می‌نویسیم:
• برای مثال اخیر، این گونه می‌خوانیم: «S مجموعه‌ای است از همه iهایی که i بزرگتر از صفر بوده و i زوج است،» در ضمن روشن است که i یک عدد صحیح است.
• عملیات معمول بر روی مجموعه‌ها اجتماع ، اشتراک ، و تفاضل (-) است، که به صورت زیر تعریف می‌شوند:
• عمل اساسی دیگر متمم است. متمم مجموعه S با نمایش داده می‌شود. شامل تمامی عناصری است که در S نیست. برای یافتن این مفهوم، نیازمند شناخت مجموعه جهانی U شامل تمامی عناصر ممکن هستیم. اگر U مشخص باشد، آنگاه:
• مجموعه‌ای که هیچ عضوی ندارد، یا نامیده می‌شود و به شکل Æ نمایش داده می‌شود. از تعریف مجموعه روشن است که:
• قوانین مفید زیر، به قوانین دمورگان مشهورند:
• که در موارد زیادی استفاده می‌شوند.
• یک مجموع S₁ زیرمجموعه S گفته می‌شود، اگر تمامی عناصر S₁همگی در S موجود باشند. ما این گونه می‌نویسیم:
• اگر اما S دارای عنصری بود که در S₁وجود نداشت، آن گاه گوییم S₁یک زیرمجموعه محض از S است و می‌نویسیم:
• اگر S₁و S₂ دارای هیچ عضو مشترکی نباشند، بطوریکه ، آنها را دو مجموعه جدا از هم گویند.
• یک مجموعه را متناهی گویند اگر شامل تعداد محدودی از عناصر باشد، در غیر این صورت نامتناهی نامیده می‌شود. اندازه یک مجموعه متناهی، تعداد اعضای موجود در آن می‌باشد و بصورت |S| نمایش داده می‌شود.
• یک مجموعه دارای تعداد زیادی زیرمجموعه است. مجموعه همه زیرمجموعه‌های مجموعه S، مجموعه توانی S نامیده می‌شود و با 2^S نمایش داده می‌شود.
• مثال 1-1: اگر مجموعه S، {a, b, c} باشد، آنگاه مجموعه توانی آن اینگونه است:
• در اینجا 3=|S| و . این از یک نتیجه کلی حاصل می‌شود، اگر S مجموعه‌ای متناهی باشد، در این صورت:
• در بسیاری از مثال‌ها، عناصر یک مجموعه دنباله‌ای از عناصر چیده شده و مرتب شده مجموعه‌های دیگر هستند. به این گونه مجموعه‌ها، حاصلضرب دکارتی گویند. برای حاصلضرب دکارتی دو مجموعه، که خود مجموعه‌ای است از زوج‌های مرتب، می‌نویسیم:
• توابع و روابط
• یک تابع، قانون یا ضابطه‌ای است که عناصر یک مجموعه را بصورت یکتا به عناصر مجموعه دیگری مربوط می‌سازد. اگر f نشان‌دهنده یک تابع باشد، مجموعه اول را دامنه و مجموعه دوم را برد f گویند می‌نویسیم:
• که بیانگر این است که دامنه f یک زیرمجموعه S₁و برد آن یک زیرمجموعه از S₂می‌باشد. اگر دامنه تابع f همه S₁باشد، گوییم f یک تابع کلی روی S₁است، در غیر این صورت f را تابع جزئی گویند.
• در بسیاری از کاربردها، دامنه و برد توابع، مجموعه اعداد صحیح ثابت است. بعلاوه، ما اغلب علاقمند به بررسی رفتار این توابع به ازای مقادیر خیلی بزرگ آرگومانهایشان هستیم. در چنین مواردی، درکی از نرخ رشد ضروری است، و مرتبه سوم از علامت دامنه قابل استفاده است. فرض کنید f (n) و g (n) توابعی باشند که دامنه آنها زیرمجموعه‌ای از اعداد صحیح مثبت است. اگر یک ثابت مثبت c وجود داشته باشد طوریکه برای همه nها داشته باشیم:
• گوییم f از مرتبه حداکثر g است، و می‌نویسیم:
• در این صورت f از مرتبه حداقل g است، و از نماد زیر استفاده می‌کنیم:
• در نهایت اگر ثوابت c₁ و c₂ وجود داشته باشند بطوریکه
• و g از مرتبه دامنه یکسانی هستند، و می‌نویسیم:
• در این نماد مرتبه دامنه، ما از ضرایب ثابت و جملات از مرتبه پایین‌تر صرفنظر می‌کنیم، که با افزایش n قابل چشم‌پوشی می‌باشند.
• در نماد مرتبه دامنه، نشانگر = نباید به معنای تساوی تفسیر شود و عبارات مرتبه دامنه، نباید شبیه عبارات معمویل نگریسته شوند. دستکاری‌هایی مانند
• قابل قبول نیستند، و می‌توانند به نتایج نادرست منجر شوند. هنوز، اگر بدرستی استفاده شود، آرگومان‌های مرتبه دامنه می‌توانند موثر باشند.
• یک تابع را می‌توان بصورت مجموعه‌ای از زوج‌ها نمایش داد:
• که x₁ یک عضور در دامنه تابع و y₁ مقدار متناظر با آن در برد آن می‌باشد. برای آنکه یک مجموعه تابع باشد، هر x می‌تواند حداکثر یکبار به عنوان اولین مولفه یک زوج ظاهر شود. اگر این گونه نباشد، مجموعه یک رابطه نامیده می‌شود. رابطه بسیار کلی‌تر از تابع می‌باشد. در یک تابع، هر عضو دامنه فقط دارای یک عنصر متناظر در برد می‌باشد، در رابطه ممکن است چندین عنصر متناظر در برد وجود داشته باشد. یک نوع رابطه، رابطه هم ارزی می‌باشد که مشتقی از مفهوم تساوی (برابري) است. برای نمایش این که زوج (x,y) رابطه هم ارزی دارند، می‌نویسیم:
• رابطه هم ارزی با º نمایش داده می‌شود، اگر سه شرط زیر برقرار باشد:
• قانون بازتابی
• برای همه xها، xºx
• قانون تقارنی
• اگر xºy، آنگاه yºx
• قانون تعدی
• اگر xºy و yºz، آنگاه xºz
• گراف‌ها و درخت‌ها
• یک گراف، ساختاری است دارای دو مجموعه متناهی، مجموعه از رئوس و مجموعه از یال‌ها. هر یال زوجی از رئوس V است، 
• یالی از v_j به v_k است. گوییم که یال e_i، یک یال خروجی از v_j و یال ورودی به v_k است. چنین ساختاری را گراف جهت‌دار گوییم، زیرا ما به هر یال جهتی را (از v_j به v_k) نسبت داده‌ایم. گراف‌ها می‌توانند دارای برچسب باشند. برچسب می‌تواند نام و یا اطلاعات دیگری در بخش‌های دیگر گراف باشد. هر دوی یال‌ها و رئوس می‌توانند دارای برچسب باشند.
• گراف‌ها برای سهولت با نمودار نشان داده می‌شوند. به این صورت که رئوس بصورت دایره و یال‌ها بصورت پیکان‌هایی رئوس را به هم متصل می‌کنند. گراف با رئوس و یال‌های در شکل 1-1 نشان داده شده است.
• به دنباله‌ای از یال‌های راهی از i به n گویند. طول یک راه مساوی با تمام یال‌هایی است که از راس مبدا خارج و به راس مقصد می‌رسند. راهی که هیچ یالی در آن تکرار نشود، یک مسیر نامیده می‌شود. مسیر را ساده گویند هرگاه هیچ راسی در آن تکرار نشود. یک راه از v_i به خودش، بدون هیچ یال تکراری، یک چرخه با پایه v_i نامیده می‌شود. در یک چرخه با پایه v_i اگر بجز پایه هیچ راسی تکرار نشود آنگاه چرخه، ساده نامیده می‌شود. در شکل 1-1، مسیر ساده‌ای از ₁v به ₂­v است. دنبال یال‌های یک چرخه غیر ساده است. اگر یال‌های گراف دارای برچسب باشند، آنگاه می‌توان  در مورد برچسب یک راه صحبت کرد. این برچسب شامل یک رشته از برچسب یال‌هایی است که در طول مسیر پیمایش می‌شوند. سرانجام، یالی از یک راس به خودش را یک طوقه گویند. در شکل 1-1 طوقه‌ای روی راس ₃v وجود دارد.
• در چند فرصت، به الگوریتمی برای یافتن همه مسیرهای ساده بین دو راس مفروض (یا همه چرخه‌های ساده با پایه یک راس) مراجعه خواهیم کرد. اگر خودمان را چندان درگیر کارایی نکنیم، می‌توانیم به راحتی از روشی که گفته خواهد شد استفاده کنیم. با شروع از یک راس مفروض مثل v_i، همه یال‌های خروجی از این نقطه را لیست می‌کنیم مانند . ما همه مسیرهایی با طول یک که از v_i آغاز می‌شوند را داریم. برای تمامی رئوس v_k,v_l,… که به آنها رسیده‌ایم، تمامی یال‌های خروجی را مادامیکه در مسیر به هیچ یک از رئوسی که قبلاً در مسیر استفاده شده‌اند نرسیده باشیم، لیست می‌کنیم. بعد از انجام این عمل ما تمامی مسیرهای ساده‌ار را که با مبدا v_i هستند، خواهیم داشت. این عمل را تا جایی که امکان داشته باشد، ادامه می‌دهیم. از آنجایی که فقط تعداد محدودی از رئوس وجود دارد، تمامی مسیرهای ساده شروع شده از v_i را لیست کرده‌ایم. از بین مسیرهای ساده بدست آمده، آنهایی را انتخاب می‌کنیم که با راس مطلوب خاتمه یافته‌اند.
• درخت‌ها نوع خاصی از گراف هستند. درخت، گراف جهت‌داری است که چرخه ندارد، و یک گره خاص دارد که به آن ریشه گویند، طوریکه فقط یک مسیر از ریشه به سایر رئوس وجود دارد. روشن است که هیچ گونه یالی به ریشه وارد نمی‌شود، و رئوسی هستند که هیچ یالی از آنها خارج نمی‌شود. این رئوس برگ‌های درخت نامیده می‌شوند. اگر یک یال از v_i به v_j وجود داشته باشد، آنگاه v_i را والد v_j نامند، و v_j فرزند v_i خواهد بود. سطح هر راس، برابر با تعداد یال‌هایی است که در مسیر موجود از ریشه تا آن راس وجود دارند. ارتفاع درخت، بزرگترین شماره سطح همه رئوس است.
• روش‌های اثبات
• نیاز مهمی که برای خواندن مطالب این متن وجود دارد، استفاده و پیروی از مدارک و مستندات است. در اثبات‌های ریاضی ما بسیاری از قوانین مرسوم کاهشی و بسیاری از قوانین ساده که بصورت قدم به قدم می‌باشند را به کار می‌بریم. دو روش اثبات بسیار معمول وجود دارد که به شرح مختصر آنها می‌پردازیم. آنها اثبات بوسیله استقرا و اثبات بوسیله برهان خلف می‌باشند.
• استقرا، روشی است که در آن درستی تعدادی از جملات، از درستی چند نمونه خاص استنتاج می‌شود. فرض کنید که ما زنجیره‌ای از جملات را داریم که می‌خواهیم ثابت کنیم آنها درست می‌باشند. بعلاوه فرض کنید که شرایط زیر برقرار است:
• 1ـ برای برخی 1 k³، ما می‌دانیم که درست هستند.
• 2ـ مسئله طوری است که برای هر n³k، درستی درستی را ایجاب می‌نماید.
• ما می‌توانیم از استقرا برای نمایش اینکه هر جمله در زنجیره درست است، استفاده نماییم.
• در یک اثبات بوسیله استقرا، ما بصورت زیر بیان می‌کنیم: از شرط 1 می‌دانیم که k جمله درست است. سپس شرط 2 به ما می‌گوید که نیز باید درست باشد. ولی اکنون ما می‌دانیم که 1+k جمله اول درست هستند، بنابراین می‌توانیم شرط 2 را بکار ببریم تا ادعا کنیم که باید درست باشد، و مانند آن. ما صریحاً به این آرگومان ادامه نمی‌دهیم، زیرا الگو واضح است. زنجیره استدلال می‌تواند به هر جمله‌ای توسعه یابد. بنابراین، هر جمله درست است.
• جملات شروع پایه استقرا نامیده می‌شوند. گامی که P_n را با ₁P_n+ مرتبط می‌سازد، گام استقرا نامیده می‌شود. گام استقرا عموماً بوسیله فرض استقرا یعنی فرض درست بودن ، ساده‌تر می‌شود. در یک استدلال استقرائی صوری، ما هر سه بخش را صریحاً نشان می‌دهیم.
• مثال 1-4: یک درخت دودویی، درختی است که هیچ والدی نمی‌تواند بیش از دو فرزند داشته باشد. ثابت کنید که یک درخت دودویی با ارتفاع n دارای حداکثر ⁿ2 برگ است.
• اثبات: اگر ما بیشترین تعداد برگ‌های یک درخت دودویی با ارتفاع n را بوسیله l (n) تعریف کنیم، می‌خواهیم نشان دهیم که:
• پایه: روشن است که زیرا درخت با ارتفاع 0 دارای گره‌ای به جز ریشه نیست، یعنی حداکثر یک برگ دارد.
• فرض استقرا: برای
• گام استقرا: برای بدست آوردن یک درخت دودویی با ارتفاع 1+n از درختی دودویی با ارتفاع n، می‌توانیم حداکثر دو برگ را به هر برگ در درخت قبلی اضافه نماییم.
• بنابراین، ادعای ما برای 1+n نیز درست است. از آنجایی که n هر عددی می‌تواند باشد، این جمله برای همه nها درست باشد.
• استدلال بوسیله استقرا می‌تواند مشکل باشد، و به توجه داشتن به ارتباط نزدیکی بین استقرا و بازگشت‌پذیری در برنامه‌نویسی کمک می‌نماید. برای مثال، تعریف بازگشتی از یک تابع f(n)، که n هر عدد صحیح مثبت است، اغلب دارای دو بخش است. یک بخش شامل تعریف (1+f(n برحسب می‌باشد که متناظر با مرحله استقرار است. بخش دوم «فرار» از بازگشتی است، که بوسیله تعریف به صورت غیربازگشتی انجام می‌پذیرد، و متناظر با پایه استقرا است. مانند استقرا، بازگشت‌پذیری نیز به ما اجازه نتیجه‌گیری درباره همه نمونه‌ۀای مسئله را با تعدادی مقادیر آغازین و استفاده از طبیعت بازگشتی مسئله می‌دهد.

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

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