خوارزمية ماركوف

في علم الحاسوب النظري ، تُعدّ خوارزمية ماركوف نظامًا لإعادة كتابة السلاسل النصية ، يستخدم قواعد شبيهة بالقواعد النحوية لمعالجة سلاسل الرموز. وقد ثبت أن خوارزميات ماركوف كاملة تورينج ، مما يعني أنها مناسبة كنموذج عام للحوسبة ، ويمكنها تمثيل أي تعبير رياضي من خلال ترميزه البسيط. سُميت خوارزميات ماركوف نسبةً إلى عالم الرياضيات السوفيتي أندريه ماركوف الابن.

ريفال هي لغة برمجة تعتمد على خوارزميات ماركوف.

الخوارزميات العادية لفظية، أي أنها مصممة ليتم تطبيقها على سلاسل مكتوبة بأبجديات مختلفة.

يتكون تعريف أي خوارزمية عادية من جزأين: الأبجدية ، وهي مجموعة من الرموز، والمخطط . تُطبق الخوارزمية على سلاسل من رموز الأبجدية. المخطط عبارة عن مجموعة مرتبة منتهية من صيغ الاستبدال . يمكن أن تكون كل صيغة إما بسيطة أو نهائية . تُمثل صيغ الاستبدال البسيطة بسلاسل من الشكل التالي:${\displaystyle L\to D}$، أين${\displaystyle L}$و${\displaystyle D}$هما سلسلتان عشوائيتان في الأبجدية. وبالمثل، يتم تمثيل صيغ الاستبدال النهائية بسلاسل من الشكل التالي:${\displaystyle L\to \cdot D}$.

فيما يلي مثال على مخطط خوارزمية عادي في الأبجدية المكونة من خمسة أحرف${\displaystyle |*abc}$:

${\displaystyle \left\{{\begin{matrix}|b&\to &ba|\\ab&\to &ba\\b&\to &\\{*}|&\to &b*&\\{*}&\to &c&\\|c&\to &c\\ac&\to &c|\\c&\to \cdot \end{matrix}}\right.}$

عملية تطبيق الخوارزمية العادية على سلسلة نصية عشوائية${\displaystyle V}$في أبجدية هذه الخوارزمية، توجد سلسلة منفصلة من الخطوات الأولية، تتكون مما يلي. لنفترض أن${\displaystyle V'}$هي الكلمة التي تم الحصول عليها في الخطوة السابقة من الخوارزمية (أو الكلمة الأصلية)${\displaystyle V}$(إذا كانت الخطوة الحالية هي الأولى). إذا لم يكن هناك طرف أيسر من صيغ الاستبدال يتم تضمينه في${\displaystyle V'}$ثم تنتهي الخوارزمية، وتُعتبر نتيجة عملها هي السلسلة${\displaystyle V'}$وإلا، فإن أول صيغة من صيغ الاستبدال التي يتم تضمين أطرافها اليسرى في${\displaystyle V'}$يتم اختياره. إذا كانت صيغة الاستبدال على الشكل التالي${\displaystyle L\to \cdot D}$ثم من بين جميع التمثيلات الممكنة للسلسلة${\displaystyle V'}$من الشكل${\displaystyle RLS}$(أين${\displaystyle R}$و${\displaystyle S}$(سلاسل عشوائية) السلسلة الأقصر${\displaystyle R}$يتم اختيارها. ثم تنتهي الخوارزمية وتُعتبر نتيجة عملها${\displaystyle RDS}$ومع ذلك، إذا كانت صيغة الاستبدال هذه على الشكل التالي${\displaystyle L\to D}$ثم من بين جميع التمثيلات الممكنة للسلسلة${\displaystyle V'}$على شكل${\displaystyle RLS}$الأقصر${\displaystyle R}$يتم اختيار السلسلة، وبعد ذلك${\displaystyle RDS}$يُعتبر هذا نتيجة للخطوة الحالية، ويخضع لمزيد من المعالجة في الخطوة التالية.

على سبيل المثال، عملية تطبيق الخوارزمية الموصوفة أعلاه على الكلمة${\displaystyle |*||}$ينتج عنه تسلسل الكلمات${\displaystyle |b*|}$،${\displaystyle ba|*|}$،${\displaystyle a|*|}$،${\displaystyle a|b*}$،${\displaystyle aba|*}$،${\displaystyle baa|*}$،${\displaystyle aa|*}$،${\displaystyle aa|c}$،${\displaystyle aac}$،${\displaystyle ac|}$و${\displaystyle c||}$وبعد ذلك تتوقف الخوارزمية عند النتيجة${\displaystyle ||}$.

للاطلاع على أمثلة أخرى، انظر أدناه.

أي خوارزمية عادية تُكافئ آلة تورينج ، والعكس صحيح - أي آلة تورينج تُكافئ خوارزمية عادية. يُطلق على صيغة من أطروحة تشيرش-تورينج، المُصاغة فيما يتعلق بالخوارزمية العادية، اسم "مبدأ التطبيع". 

أثبتت الخوارزميات العادية أنها وسيلة ملائمة لبناء العديد من فروع الرياضيات البنائية . علاوة على ذلك، تتضمن تعريفات الخوارزمية العادية عدداً من الأفكار المستخدمة في لغات البرمجة التي تهدف إلى معالجة المعلومات الرمزية ، كما هو الحال في لغة ريفال على سبيل المثال . 

القواعد عبارة عن سلسلة من أزواج السلاسل النصية، وعادة ما يتم تقديمها على شكل نمط → استبدال . قد تكون كل قاعدة عادية أو منتهية.

بافتراض وجود سلسلة نصية مُدخلة :

1. تحقق من القواعد بالترتيب من الأعلى إلى الأسفل لمعرفة ما إذا كان يمكن العثور على أي من الأنماط في سلسلة الإدخال .
2. إذا لم يتم العثور على أي منها، تتوقف الخوارزمية.
3. إذا تم العثور على واحد (أو أكثر)، فاستخدم أولها لاستبدال أقصى ظهور للنص المطابق في سلسلة الإدخال بنصه البديل .
4. إذا كانت القاعدة التي تم تطبيقها للتو قاعدة إنهاء، فإن الخوارزمية تتوقف.
5. انتقل إلى الخطوة 1.

لاحظ أنه بعد تطبيق كل قاعدة، تبدأ عملية البحث من جديد من القاعدة الأولى.

يوضح المثال التالي العملية الأساسية لخوارزمية ماركوف.

تُقدّم هذه القواعد مثالاً أكثر إثارة للاهتمام، حيث تُعيد كتابة الأعداد الثنائية إلى نظائرها الأحادية. على سبيل المثال، يُعاد كتابة العدد 101 إلى سلسلة من 5 خطوط متتالية.

• القواعد الرسمية

• كاراتشولو دي فورينو، أ. لغات معالجة السلاسل وخوارزميات ماركوف المعممة. في لغات وتقنيات معالجة الرموز، دي جي بوبرو (محرر)، دار نشر نورث هولاند، أمستردام، هولندا، 1968، ص  191-206.
• أندريه أندرييفيتش ماركوف (1903-1979) 1960. نظرية الخوارزميات. ترجمات الجمعية الرياضية الأمريكية، السلسلة 2، 15، 1-14. (ترجمة من الروسية، أعمال معهد ستيكلوف 38 (1951) 176-189 ^{[ 1 ]} )

• ياد ستوديو - بيئة تطوير متكاملة ومفسر لخوارزميات ماركوف (مفتوح المصدر)
• مترجم خوارزمية ماركوف
• مترجم خوارزمية ماركوف
• مترجمو خوارزمية ماركوف في شركة روزيتا كود
• A=B، لعبة تدور حول كتابة قواعد الاستبدال لخوارزمية ماركوف