МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Кафедра ЕОМ "Нормальні алгоритми Маркова" Лабораторна робота № 3 з дисципліни: "Алгоритми і методи обчислень " Львів – 2011 Мета: Дослідження роботи нормальних алгоритмів Маркова(НАМ), та дослідження її роботи на емуляторі машини нормальних алгоритмів Маркова. Теоретичні відомості: Нормальні алгоритми (нормальні алгоритми) — вербальні алгоритми, тобто, алгоритми, що перетворюють слова деякого (фіксованого) алфавіту. Поняття нормального алгоритма введене радянським математиком А. А. Марковим. Нормальний алгоритм Маркова (НАМ) — система послідовних застосувань, підстановок, які реалізують певні процедури отримання нових слів із базових, які побудовані на певному алфавіті. Будь який нормальний алгоритм визначається вказанням алфавіту, в якому він діє, та схеми нормального алгоритма. Алфавітом нормального алгоритма може бути довільний скінченний алфавіт A. Формулами підстановок в алфавіті A називаються вирази подібні p → q (проста пістановка) або p →• q (кінцева підстановка), де p та q — деякі слова в алфавіті A, які називаються лівою та правою частинами формули відповідно (вважається, що алфавіт A не містить символів → та →•). Кожний нормальний алгоритм в алфавіті A має скінченну кількість таких формул підстановок. Їх записуть у вигляді списку. Цей список називається схемою алгоритма. Застосування нормального алгоритма до слова s полягає в наступному, в заданому списку формул підстановок знаходять першу формулу, ліва частина якої входить до слова s. Знаходять перше входження цієї частини в слові s і замість цього входження підставляють праву частину формули. Це дасть нове слово s1, з отриманим словом s1 повторюють попередній крок. Цей процес може обірватись сам собою на деякому слові, в яке не входить ліва частина жодної з формул алгоритма. Крім того, постулють, що описаний вище процес зупиняється, коли до чергового слова застосувати одну із кінцевих формул підстановки, тобто, формул видуp →• q. Якщо процес закінчується, то отримане останнє слово є результатом застосування алгоритма до слова s. Можливості нормальних алгоритмів Доведено, що відносно виконуваних перетворень, нормальні алгорифми збігаються з іншими класами алгорифмів, введених для уточнення інтуїтивного поняття алгоритма, наприклад, з машинами Тюринга. Визначення алгорифмів у нормальному вигляді дуже схоже на числення, і це є дуже корисним у випадках, коли поняття числення в досліджуваному розділі математики або кібернетики широко застосовують, як, приміром, в математичній логіці або в математичній лінгвістиці. Використовуючи поняття нормального алгорифма, Марков та інші дослідники довели нерозв'язність цілого набору алгоритмічних проблем. Індивідуальне завдання: Зменшити число представлене в унітарній системі числення на 1. Алгоритм виконання роботи. Система підстановок у машині «Нормальних алгоритмів Маркова»:
Коментарі до алгоритму представлені паралельно з алгоритмом. Приклад виконання: У нас є заданий алфавіт А = {|}.Для прикладу введемо довільну кількість “|”. Припустимо у нас є така послідовність: ||||||| - сім послідовних знаків алфавіту А, 7-1=6, тобто нам треба залишити 6 “|”, для цього нам буде достатньо однієї операції, замінити “||” на “| Стрічка до виконання операцій:
Стрічка після виконання операцій:
Висновок. У даній лабораторній роботі я навчився працювати з машиною яка моделює роботу Нормальних алгоритмів Маркова. Зрозумів методи роботи з цією машиною та навіщо вона потрібна.