Algoritmga kirish

5-laboratoriya ishi 

Mavzu:Tyuring mashinasi tushunchasi 

Ishdan  maqsad:  Ushbu  laboratoriya  ishining  maqsadi  talabalar  qanday 

tyuring  mashinasi    va    ishlashni    o’rganishlari    kerak.    Shu    asosda    tyuring 

mashinasida dasturlar tuzishni o’zlashtirishlari kerak.  

Qo’yilgan  masala:  Talabalar  topshiriq  variantiga  mos  masalani tyuring 

mashinasi  qoidalari  yordamida  yechish  dasturini  yaratish  ko’nikmasiga  ega 

bo’lishlari kerak.  

Ish tartibi:  



  Tajriba ishi nazariy ma’lumotlarini o’rganish;  



 

Berilgan topshiriqniтп algoritmini ishlab chiqish;  



  Tyuring mashinasi uchun belgilahslarni kiritish;  



  Natijalarni tekshirish;  



  Hisobotni tayyorlash va topshirish.  

 

5.1.Tyuring mashinasi tushunchasi 

Tyuring mashinasi ikkita asosiy qismdan iborat: lenta va avtomatdan.  

 

Lenta  ma’lumotni  saqlashda  foydalaniladi.  Uning  uzunligi  cheksiz  va 

katachalarga  bo’lingan.  Katakchalar  nomerlanmagan.  Katakka  istalgan  belgi 

yoizhs yoki avval yozilgan belgini o’cjirib tashlash mumkin. Bo’sh katakni L harfi 

bilan belgilash kiritib olamiz.  

Avtomat  bu  tyuring  mashinasining  aktiv  qismi  sanaladi.  Har  bir  vaqt 

momentida bitta katakka suriladi va katakning qiymatini (tarkibini, ichini) ko’radi. 

Qaralayotgan  katak  va  uning  tarkibidagi  belgi  (simvol)  qaralayotgan  belgi  deb 

ataladi.  Lekin  qo’shni  kataklarning  tarkibini  bir  vaqtni  o’zida  ko’ra  olmaydi.  Har 

bir vaqt momentida avtomat o’zining bitta holatida bo’ladi.  

Bilgilash kiritamiz: S- qaralayotgan belgi, q- avtomatning joriy holati. Uning 

konfiguratsiyasi quyidagicha bo’ladi:   

 Avtomat 3 ta elementar amalni bajarishi mumkin:  

1) Qaralayotgan katakka yangi belgi yoizsh; 

2)  Chap  yoki o’ng tomonga qarab harakatlanish  (Bunda  avtomat bir nechta 

katakni sakrab o’ta olmaydi);  

3) Yangi holatga o’tish; 

Avtomat yuqorida kop’rib o’tilgan amallardan boshqa amalni bajara olmaydi. 

5.2.Tyuring mashinasining ishlash takti 

TM  har bir taktda quyidagi harakatlarni amalgam oshiradi: 

1.  Qaralayotgan katakka qandaydir S’ belgini yozib qo’yadi. 

2.  O’ng tomonga bir katak siljitish –R (Right) harfi bilan, chap tomonga siljish 

–L (Lift) harfi bilan, agar joydan qimirlamasa N harfi bilan belgilanadi. 

3.  Qandaydir q’ holatga o’tadi (yoki avvalgi holatida qoladi). 

Yuqorida keltirilgan amallarni formal ko’rinishi quyidagicha bo’ladi: 

S’, [L,R, N], q’ 

Masalan,  ushbu  *,L,q8  taktni    qaraymiz.  Bu  yerda  *-  qaralayotgan  katak,  L-bitta 

katak chapga harakat va q8 holatga o’tushni bildiradi.  

  

6-laboratoriya ishi 

Mavzu: Tabiiy Markov algoritmlari 

Ishdan maqsad: Tabiiy Markov  algoritmlarini o’rganish. 

Qo’yilgan masala: Topshiriq variantida berilgan masalani berilgan 

tuzilishdagi algoritmlar yordamida yechish. 

Qisqacha nazariy ma’lumot 

Ma’lum  bir  alifboga  asoslangan  algoritmik  so’zlarning  sinfi  sobiq  sovet  matemategi 

A.A.Markov  tomonidan  tabiiy  markov  lagoritmi  (TMA)  nomi  ostida  ishlab  chiqilgan.  Har  bir 

algoritm   

Нормальные  алгоритмы  Маркова  (далее —  НАМ),  введенные  советским  математиком 

А. А. Марковым,  представляют  собой  класс  алгоритмов,  применимых  к  словам 

некоторого  алфавита.  Каждый  НАМ  определяется  указанием  алфавита,  в  котором  он 

действует, и схемы НАМ. Алфавитом НАМ может служить любой конечный алфавит 

A

. 

Формулой  подстановки  в  алфавите 

A

  называется  выражение  типа 

p  →  q

  (простая 

подстановка, в эмуляторе обозначена как  ->) или 

p  ↦  q

  (заключительная подстановка, в 

эмуляторе  обозначена  как  =>),  где 

p

  и 

q

 —  некоторые  слова  в  алфавите 

A

,  называемые, 

соответственно, левой и правой частями формулы подстановки. Каждый НАМ в алфавите 

A

  имеет  конечное  число  формул  подстановки.  Их  записывают  в  виде  списка,  который 

называется схемой алгоритма.  

Применение  НАМ  к  некоторому  слову 

S

  заключается  в  следующем.  В  списке  формул 

подстановки ищется первая из тех формул, в которой левая часть входит в 

S

. Находится 1-

е  вхождение  левой  части  формулы  в 

S

  и  вместо  этого  вхождения  подставляется  правая 

часть формулы. Получается новое слово 

S'

. Cо словом 

S'

  производятся  те  же  действия  и 

т.д.  

Данный процесс обрывается в 2-х случаях:  



 

к очередному слову применена одна из заключительных формул подстановки;  



 

в слово не входит ни одна из левых частей формул подстановки. 

Получаемое последнее слово является результатом применения НАМ к исходному слову 

S

.  

Примеры на составление нормальных алгоритмов Маркова 

Пример  1.  В  произвольном  слове,  состоящем  из  букв 

{a, b, c}

,  все  подряд  стоящие 

одинаковые  буквы  заменить  одной  буквой  (например,  слово  «abbbcaa»  преобразовать  в 

«abca»). Схема НАМ. имеет вид:  

1. 

aa

 

→ 

 

a

 

2. 

bb

  

→ 

 

b

 

3. 

cc

  

→ 

 

c

 

(

загрузить в эмулятор

)  

Применение этой схемы с слову «abbbcaa» последовательно даст слова: «abbbca», «abbca» 

и  «abca»,  после  чего  выполнение  НАМ  завершится.  Для  проверки  данного  алгоритма 

загрузите его текст в эмулятор.  

Пример  2.  Удвоить  слово,  состоящее  из  одинаковых  символов  (для  определенности — 

«x»). Т.е. слово «x» надо преобразовать в «xx», слово «xx» — в «xxxx» и т.д.  

Схема НАМ для этого примера намного сложнее, чем для примера 1. Нельзя написать 

x 

→ xx

, т.к. в этом случае на каждом шаге НАМ к слову будет  добавляться символ  «x»  и 

этот процесс будет бесконечным. Необходимо контролировать удвоение каждого символа 

слова  так,  чтобы  каждый  символ  удвоился  только  один  раз.  Для  это  введём  маркер,  с 

помощью которого будем обеспечивать контекст применения удваивающего правила.  

1. 

*x

 

→ 

 

xx*

 

2. 

*

  

↦ 

  

3.   

→ 

 

*

 

(

загрузить в эмулятор

)  

Последнее  правило  вводит  «маркер»  '*'  (или  «курсор»),  который  с  помощью  первого 

правила «перескакивает» через текущий символ слова и удваивает его. Применение этой 

схемы,  например,  к  слову  «xx»  последовательно  даст  слова:  (3)  «*xx»,  (1)  «xx*x»,  (1) 

«xxxx*», (2) «xxxx» (в скобках указан номер применяемой формулы подстановки).  

Пример  3.  Дано  слово  в  алфавите 

{a, b, c}

.  Упорядочить  буквы  входного  слова  в 

лексикографическом порядке  

FOYDALANILGAN ADABIYOTLAR 

 1. Алфред  В.  Ахо.,  Джон  Э.  Хопкрофт,  Джефри  Д.  Ульман. Структура 

данных и алгоритмы//Учеб.пос., М. : Изд.дом: "Вильямс", 2000. 

2. Бакнелл  Джулиан  М.  Фундаментальные  алгоритмы  и  структуры  

данных в Delphi//СПб: ООО «ДиаСофтЮП», 2003. 560с.  

3.  Роберт    Седжвик.    Фундаментальные    алгоритмы    на    C++.    Анализ, 

Структуры данных, Сортировка, Поиск//К.: Изд. «ДиаСофт», 2001.- 688 с.  

4. Динман М.И. С++. Освой на примерах//СПБ.:БХВ-Петербург, 2006, 384.   

5. Шилдт,  Герберт.  Полный  справочник  по  С#//М.  :  Изд.  дом "Вильямc", 

2004, 752 с.  

6. Вирт Н. Алгоритмы и структуры  программы//М., Мир, 1985.  

7.  Лойко    В.И.    Структуры    и    алгоритмы    обработки    данных.    Учебное  

пособие для вузов.- Краснодар: КубГАУ. 2000. - 261 с., ил.  

8.  Knuth,    D.    E.    (1968).    The    Art    of    Computer    Programming    Vol.    I: 

Fundamental  Algorithms,  Addison  –  Wesley,  Reading,  Mass. (Русский  перевод: 

Кнут    Д.    Искусство    программирования    для    ЭВМ.    Том    1:    Основные  

алгоритмы.    –    М.,    «Мир»,    1976.    Русский    перевод    переработанного   

издания:  Кнут    Д.    Искусство    программирования.    Том    1:    Основные  

алгоритмы.  –  М., Издательский дом «Вильямс», 2000.)  

9. Джон  Бентли.  Жемчужины  программирования.  СПб.:  Питер, 2002.-272с.  

10. Акбаралиев  Б.Б.  Конспект  лекций  по  курсу  “Маълумотлар тузилмаси  

ва  алгоритмлар”  для  студентов  по  специальности  5521900 “Информатика 

и информационные технологии”, Ташкент, 2008 г.  

11.  Акбаралиев  Б.Б.  Методические  указания  к  лабораторным  работам    по 

курсу  “Маълумотлар  тузилмаси  ва  алгоритмлар”  для  студентов  по 

специальности  5521900  “Информатика  и  информационные  технологии”, 

Ташкент, 2008 г.  

12.  Xudoyberdiyev    M.X.,    Akbaraliyev    B.B.  “Ma’lumotlat    tuzilmasi    va 

algoritmlar”    fanidan    amaliy    mashg’ulotlar    uchun    topshiriqlar    (uslubiy 

ko’rsatmalari bilan). Toshklent, 2013 y.