موضوع مقاله: الگوریتم مارکوف | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم مارکوف | مقدمه: در علوم نظری کامپیوتر، الگوریتم مارکوف یک سیستم بازنویسی رشته‌ای است که قوانین گرامر-مانندی را بر روی رشته‌ای از نمادها اعمال می‌کند. | ## بخش 1: الگوریتم مارکوف | الگوریتم مارکوف به عنوان یک تورینگ کامل نشان داده شده‌است که به این معنی است که آن‌ها به عنوان یک مدل کلی از یک سری محاسبات مناسب هستند که می‌توانند بیانگر هر عبارت ریاضی از علامت ساده خود باشد. توصیف الگوریتم‌های عادی، کلامی هستند که به عنوان کلماتی که در الفباهای مختلف به کار برده می‌شوند، در نظر گرفته می‌شود. تعریف هر الگوریتم عادی شامل دو بخش است: یکی تعریف الفبای الگوریتم (الگوریتم برای کلمات این نمادهای الفبایی به کار برده خواهد شد) و دیگری تعریف برای طرح آن است. طرح الگوریتم عادی یک مجموعه محدود از فرمول‌هایی است که به اصطلاح به آن‌ها فرمول جایگزینی می‌گوییم که هر کدام می‌تواند ساده یا نهایی باشد. یک فرمول جایگزینی ساده کلماتی هستند به شکل ، که و دو کلمه دلخواه در الفبای الگوریتم هستند (که به ترتیب سمت چپ و سمت راست در فرمول جایگزینی نامیده می‌شوند) به‌طور مشابه فرمول جایگزینی نهایی کلماتی هستند به شکل ، هستند که و دو کلمه دلخواه در الفبای الگوریتم هستند. یک مثال از طرح الگوریتم عادی که شامل الفبای پنج حرفی است می‌تواند مانند طرح زیر باشد. روند استفاده از الگوریتم عادی برای یک کلمه دلخواه در الفبای الگوریتم، یک توالی گسسته از مراحل ساده است که شامل موارد زیر است. | ## بخش 2: الگوریتم مارکوف | فرض کنیم کلمه‌ای است که در مرحله قبلی الگوریتم به دست آمده‌است، (یا کلمه اصلی ، اگر مرحله فعلی قدم اول شماست). اگر در بین فرمول‌های جایگزینی، سمت چپی وجود نداشته باشد که شامل باشد، کار الگوریتم تکمیل شده و نتیجه این الگوریتم کلمه در نظر گرفته می‌شود. در غیر این صورت گزینه‌هایی هستند که در سمت چپ آن‌ها قسمتی از ظاهر شده‌است اولین گزینه را انتخاب می‌کنیم، اگر فرمول جایگزینی یه شکل باشد پس از بین تمام حالت‌های مختلفی که می‌توان را به شکل نشان داد حالتی را انتخاب می‌کنیم که کوچکترین طول را داشته باشد، بعد از اعمال آن قانون نتیجه مرحله فعلی می‌شود و به سراغ مرحله بعد می‌رویم. حال اگر این فرمول جایگزینی به شکل باشد، پس از انجام مراحل قبل که جواب آن به ختم می‌شود و کار الگوریتم به پایان می‌رسد. برای مثال در طول فرایند به‌کارگیری الگوریتم با استفاده از طرح بالا، روی کلمه به ترتیب کلمات ، ، ، ، ، ، ، ، ، و ظاهر می‌شود، پس از آن الگوریتم با نتیجه متوقف می‌شود. هر الگوریتم عادی معادل ماشین تورینگ است و بالعکس، هر ماشین تورینگ معادل الگوریتم عادی است. یک نسخه از تز چرچ-تورینگ که در رابطه با الگوریتم عادی فرموله شده‌است، اصل نرمالیزاسیون نامیده می‌شود. | ## بخش 3: الگوریتم مارکوف | الگوریتم‌های عادی ثابت کرده‌اند که ابزار مناسبی برای ساخت بسیاری از بخش‌های برساخت‌گرایی ریاضیات هستند. علاوه بر این، به‌طور ذاتی الگوریتم‌های عادی در تعدادی از ایده‌های مربوط به اداره اطلاعات نمادها در زبان‌های برنامه‌نویسی استفاده شده‌است. با توجه به یک رشته ورودی: قوانین را از بالا به پایین بررسی کنید تا ببینید که آیا هیچ‌یک از الگوهای موجود در رشته‌های ورودی یافت می‌شود. اگر یک یا بیشتر از یک قانون یافت شده‌است، از اولین آن‌ها استفاده کنید و به جای سمت چپ قانون در رشته ورودی سمت راست آن را جایگزین کنید. مثال دیگر این قوانین مثالی جالب تر را ارائه می‌دهد، آن‌ها اعداد دودویی را به شکل تعداد معادلی خط بازنویسی می‌کنند. | ## جمع‌بندی | قوانین "||۰" <- "۰|" "|۰" <- "۱" "" <- "۰" رشته نماد "۱۰۱" اجرا اگر الگوریتم برای مثال بالا اجرا شود.