Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2011
Тип роботи:
Лабораторна робота
Предмет:
Алгоритми та методи обчислень
Група:
КІ-25
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
"Нормальні алгоритми Маркова"
Лабораторна робота № 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 “|”, для цього нам буде достатньо однієї операції, замінити “||” на “|
Стрічка до виконання операцій:
Стрічка після виконання операцій:
Висновок.
У даній лабораторній роботі я навчився працювати з машиною яка моделює роботу Нормальних алгоритмів Маркова. Зрозумів методи роботи з цією машиною та навіщо вона потрібна.
19.11.2012 00:11-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора