UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75834
останнє поновлення: 2016-11-29
за 7 днів додано 10

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваФормальні моделі алгоритмів та алгоритмічно обчислюваних функцій (реферат)
Авторdimich
РозділМатематика, алгебра, геометрія, статистика
ФорматWord Doc
Тип документуРеферат
Продивилось5055
Скачало412
Опис
ЗАКАЧКА
Замовити оригінальну роботу

Реферат на тему:

 

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

 

1. МАШИНИ З НАТУРАЛЬНОЗНАЧНИМИ РЕГІСТРАМИ

 

Машина з натуральнозначними регiстрами (скорочено МНР) є iдеалiзованою

моделлю комп’ютера. МНР мiстить, взагалі кажучи, нескiнченну кiлькiсть

регiстрiв, вмiстом яких є натуральнi числа. Регiстри нумеруємо

натуральними числами, починаючи з 0, позначаючи їх R0 , R1 , ..., Rn ,

... Вмiст регiстру Rn позначаємо ’Rn .

 

Послiдовнiсть (’R0 , ’R1, ..., ’Rn , ...) вмiстiв регiстрiв МНР

назвемо конфiгурацiєю МНР.

 

МНР може змiнити вмiст регiстрiв згiдно виконуваної нею команди.

Скiнченний список команд утворює програму МНР. Команди програми

послiдовно нумеруємо натуральними числами, починаючи з 1. Номер команди

в програмі називатимемо адресою команди. МНР-програму з командами I1 ,

I2 ,..., Ik будемо позначати I1I2...Ik. Довжину (кiлькiсть команд)

МНР-програми P позначимо |P|.

 

Команди МНР бувають 4-х типiв.

 

Тип 1. Обнулення n-го регiстру Z(n): ’Rn :( 0.

 

Тип 2. Збiльшення вмiсту n-го регiстру на 1 S(n): ’Rn :(’Rn+1.

 

Тип 3. Копіювання вмісту регістру T(m,n): ’Rn :(’Rm

 

(при цьому ’Rm не змiнюється).

 

Тип 4. Умовний перехiд J(m,n,q): якщо ’Rn =’Rm , то перейти до

виконання q-ї команди, iнакше виконувати наступну за списком

команду програми.

 

Число q в команді J(m,n,q) назвемо адресою переходу.

 

Команди типiв 1-3 називають арифметичними. Пiсля виконання

арифметичної команди МНР повинна виконувати наступну за списком команду

програми.

 

Виконання однiєї команди МНР назвемо кроком МНР.

 

Зауважимо, що формальними моделями алгоритмів є саме МНР-програми,

поняття МНР використовується для опису функціонування МНР-програм.

 

Виконання програми МНР починає, перебуваючи в деякiй початковiй

конфiгурацiї, з виконання 1-ї за списком команди. Наступна для виконання

команда програми визначається так, як описано вище. Виконання програми

завершується (програма зупиняється), якщо наступна для виконання

команда вiдсутня (тобто номер наступної команди перевищує номер

останньої команди програми). Конфiгурацiя МНР в момент завершення

виконання програми називається фiнальною, вона визначає результат

роботи МНР-програми над даною початковою конфiгурацiєю.

 

Якщо МНР-програма P при роботi над початковою конфiгурацiєю (a0, a1,

...) нiколи не зупиняється, цей факт позначаємо P(a0, a1, ...)(, якщо

ж коли-небудь зупиниться, цей факт позначаємо P(a0, a1,...)(. Якщо

МНР-програма P при роботi над початковою конфiгурацiєю (a0, a1, ...)

зупиняється iз фiнальною конфiгурацiєю (b0, b1, ...), цей факт

позначатимемо так: P(a0, a1, ...)((b0, b1, ...).

 

МНР-програми як моделі алгоритмів є фінітними об’єктами, тому обмежимося

розглядом скінченних конфігурацій. Конфiгурацiю вигляду (a0, a1, ...,

aп , 0, 0, ...), в якiй ’Rm= 0 для всiх m>n, назвемо скiнченною.

Таку конфігурацію позначаємо (a0, a1, ..., an ). Зрозуміло, що якщо

МНР-програма P починає роботу над скiнченною початковою конфiгурацiєю,

-----> Page:

0 [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ