Міністерство  освіти і науки  України

Полтавський національний технічний  університет

Ім. Юрія Кондратюка

Факультет інформаційних та телекомунікаційних технологій і систем 
 
 
 
 

Розрахунково-графічна робота

з дисципліни «Теория алгоритмів»  
 
 
 
 
 
 

   Виконав:      студент групи 202-ТН

          Фомичов  Д. С.

                                                                                                                                                                                   

  Викладач:      Гвоздик Д.М

                                                                                  

                            
 
 
 
 

Полтава 2010

 

Оглавление

 

Постановка задачі

     Розробити програму для виконання бінарних логічних операцій NOT і OR алгоритмом Маркова. 

 

     

Теорія

Нормальні алгоритми

Нормальні алгорифми (нормальні алгоритми) — вербальні алгоритми, тобто, алгоритми, що перетворюють слова деякого (фіксованого) алфавіту. Поняття нормального алгорифма введене радянським математиком А. А. Марковим.

Нормальний  алгорифм Маркова (НАМ) — система послідовних застосувань, підстановок, які реалізують певні процедури отримання нових слів із базових, які побудовані на певному алфавіті.

Визначення нормального алгорифма

Будь який нормальний алгорифм визначається вказанням алфавіту, в якому він діє, та схеми нормального алгорифма. Алфавітом нормального алгорифма може бути довільний скінченний алфавіт A. Формулами підстановок в алфавіті A називаються вирази подібні p → q (проста пістановка) або p →• q (кінцева підстановка), де p та q — деякі слова в алфавіті A, які називаються лівою та правою частинами формули відповідно (вважається, що алфавіт A не містить символів → та →•).

Кожний нормальний алгорифм в алфавіті A має скінченну кількість таких формул підстановок. Їх записуть у вигляді списку. Цей список називається схемою алгорифма.

Принцип дії

Застосування нормального  алгорифма до слова s полягає в наступному.

• В заданому списку формул підстановок знаходять першу формулу, ліва частина якої входить до слова s. Знаходять перше входження цієї частини в слові s і замість цього входження підставляють праву частину формули. Це дасть нове слово s₁.
• З отриманим словом s₁ повторюють попередній крок.

Цей процес може обірватись сам собою на деякому слові, в  яке не входить ліва частина жодної з формул алгорифма. Крім того, постулють, що описаний вище процес зупиняється, коли до чергового слова застосувати одну із кінцевих формул підстановки, тобто, формул видуp →• q. Якщо процес закінчується, то отримане останнє слово є результатом застосування алгорифма до словаs.

Приклад роботи

В якості прикладу схеми  нормального алгоритму можна  навести наступну схему в алфавіті з п'яти літер |*abc:

При застосуванні алгорифма  з наведеною вище схемою до слова | * | | будуть отримуватись слова:

1. | b * | ,
2. ba | * | ,
3. a | * | ,
4. a | b * ,
5. aba | * ,
6. baa | * ,
7. aa | * ,
8. aa | c,
9. aac,
10. ac |
11. c | | ,
12. | | .

Результатом застосування буде слово | | .

 

Алгоритм  програми

     #include<iostream>

     #include<string>

     using namespace std;

     int main(){

           cout<<"Choose your destiny:"<<endl;

           cout<<"1. OR"<<endl;

           cout<<"2. NOT"<<endl;

           int d;

           cin>>d;

           if(d==1){

           char code[256];

           cout<<"Enter code: ";

           cin>>code;

           string mass;

           mass=code;

           cout<<mass<<endl;

           int i=0;

           while(i<256){

                 if ( (code[i]=='/') && (code[i+1]=='a') ){

                       code[i]='a';

                       code[i+1]='/';

                       i=-1;

                       cout<<code<<endl;   

                 }

                 if ( (code[i]=='/') && (code[i+1]=='b') ){

                       code[i]='b';

                       code[i+1]='/';

                       i=-1;

                       cout<<code<<endl;   

                 }

                 if ( (code[i]=='1') && (code[i+1]=='a') ){

                       code[i]='a';

                       code[i+1]='1';

                       i=-1;

                       cout<<code<<endl;   

                 }

                 if ( (code[i]=='0') && (code[i+1]=='a') ){

                       code[i]='a';

                       code[i+1]='0';

                       i=-1;

                       cout<<code<<endl; 

                 }

                 if ( (code[i]=='1') && (code[i+1]=='b') ){

                       code[i]='b';

                       code[i+1]='1';

                       i=-1;

                       cout<<code<<endl;   

                 }

                 if ( (code[i]=='0') && (code[i+1]=='b') ){

                       code[i]='b';

                       code[i+1]='0';

                       i=-1;

                       cout<<code<<endl;  

                 }

                  if ( (code[i]=='a') && (code[i+1]=='1') ){

                       code[i]='x';

                       for(int j=i+1; j<256; j++){

                             code[j]=code[j+1];

                       }

                       i=-1;

                       cout<<code<<endl;   

                 }

                 if ( (code[i]=='a') && (code[i+1]=='0') ){

                       code[i]='x';

                       for(int j=i+1; j<256; j++){

                             code[j]=code[j+1];

                       }

                       i=-1;

                       cout<<code<<endl;   

                 }

                 if ( (code[i]=='b') && (code[i+1]=='1') ){

                       code[i]='x';

                       for(int j=i+1; j<256; j++){

                             code[j]=code[j+1];

                       }

                       i=-1;

                       cout<<code<<endl;   

                 }

                 if ( (code[i]=='b') && (code[i+1]=='0') ){

                       code[i]='y';

                       for(int j=i+1; j<256; j++){

                             code[j]=code[j+1];

                       }

                       i=-1;

                       cout<<code<<endl;   

                 }

                 if ( (code[i]=='/') && (code[i+1]=='1') ){

                       code[i+1]='a';

                       i=-1;

                       cout<<code<<endl;   

                 }

                 if ( (code[i]=='/') && (code[i+1]=='0') ){

                       code[i+1]='b';

                       i=-1;

                       cout<<code<<endl;

                 }

                 i++;

           } 

           i=0;

           while(i<256){