68834

Алгоритми

Лекция

Информатика, кибернетика и программирование

Частковий алгоритм зупиняється на даному вході якщо існує таке натуральне число t що після виконання t необов’язково різних команд цього алгоритму або не виявиться жодної команди яку можна виконати або остання команда є зупинитись.

Украинкский

2014-09-26

95 KB

2 чел.

Лекція 4

Алгоритми

У попередніх лекціях  згадувалось  про  задачі,  що  не  мають   алгоритмічного розв’язку. Для того, щоб пояснити зміст  такого  ствердження,  треба розглянути, що таке є алгоритм.

Поняття  алгоритму - центральне у питаннях, пов’язаних з обчисленнями. Розглянемо неформально цей термін. Спочатку зупинимося на більш загальному понятті  часткового  алгоритму.  Взагалі  кажучи, частковий алгоритм складається зі скінченої кількості команд,  кожна з  яких  може  виконуватись  автоматично  за  фіксований  час  та  з фіксованими витратами пам’яті.  У  часткового  алгоритму  може  бути будь-яка кількість входів та виходів.

Щоб бути  точнішими,  треба  означити  терміни  команда,  вхід, вихід. Але поки що будемо сприймати ці поняття  інтуїтивно.  Гарним прикладом  часткового  алгоритму  є  програма,  що  написана  деякою машинною мовою.

Означення 4.1. Частковий алгоритм зупиняється на даному  вході, якщо  існує  таке  натуральне  число   t,  що  після  виконання    t (необов’язково різних)  команд  цього  алгоритму  або  не  виявиться жодної  команди,  яку  можна  виконати,  або   остання   команда   є «зупинитись». Частковий алгоритм, що  зупиняється  на  всіх  входах, тобто на всіх значеннях вхідних даних,  називають  усюди  означеним алгоритмом або просто алгоритмом.

У загальному випадку кожний  вхід  або  вихід  алгоритму  можна розглядати як послідовність символів скінченого алфавіту 

 = {a1 , a2 , … , an}.

Оскільки  множина  символів   скінчена, елементи її можна пронумерувати. Наприклад, індекс символу можна вважати номером цього символу. Для множини послідовностей символів з  можна  побудувати функцію кодування  F(),   *, що  встановлює  взаємно  однозначну відповідність  між  множиною  вказаних  послідовностей  та  множиною натуральних чисел. Функція  F() означається таким чином. Нехай

= (b1, b2, … , bk),                      

де  bj  ,  j = 1, k.

Тоді

F() = 2N(b1) 3N(b2)  …  pkN(bk),

де  pi  (i = 1, k)  - iпросте число, а  N(bj) - номер символу bj.

Взаємно  однозначна відповідність випливає  з  основної  теореми арифметики (теореми  про  тільки  одне  розкладання  натурального числа).

Теорема 4.1. Довільне натуральне число, що не дорівнює одиниці, можна подати тільки одним чином  як  добуток  упорядкованих  простих чисел.

Так  само,  як  вхід  або  вихід,  опис  алгоритму  теж   можна розглядати як послідовність символів  деякого  скінченого  алфавіту. Тому за допомогою функції  F(A)  можна кодувати  будь-який  алгоритм  A.

Частковий алгоритм визначає деяке відображення множини входів у множину виходів. Відображення, що визначається частковим алгоритмом, називається частково-рекурсивною  функцією  або  просто  рекурсивною функцією. Якщо алгоритм усюди означений, то відображення називається загальнорекурсивною функцією.

Про  множину  (область  значень),  що  визначається   частковим алгоритмом, кажуть, що її можна рекурсивно перелічити.  Множина,  що визначається усюди означеним алгоритмом, називається рекурсивною.

Існує багато форм опису алгоритмів, серед яких основні [1]:

1) програми для машин Тюрінга;

2) граматики Хомського типу 0;

3) алгоритми Маркова;

4) лямбда-обчислення;

5) системи Поста;

6) ТАГ-системи;

7) більшість мов програмування.

Усі  ці  форми  потенційно   еквівалентні,   тобто   дозволяють описувати один і той же клас об’єктів.

Машина Тюрінга

Машина Тюрінга є абстрактною  моделлю  обчислювальної  машини. Вона має тільки одну структуру даних - лінійний  масив   Т   змінної довжини, що називається стрічкою. Кожний  елемент  стрічки  містить один символ (одну літеру) і має певний номер  або  індекс.  Є  також ціла змінна  Н, що називається головкою читання і показує на  деякий елемент  Т. Цю структуру зображено на рис.4.1.

 індекс …   -2    -1    0     1     2    3          …         248  249                 

             …    8    5     a      .     b     7           …           3      c       …

     H  (головка

         читання)

Рис.4.1. Структура машини Тюрінга.

Машина  Тюрінга  може  виконувати  тільки   декілька   простих операцій:

1. Вона може одержати значення  Т(Н), порівняти його  з  деякою відомою  літерою  і  виконати  ту  чи  іншу  операцію  залежно   від результату порівняння.

2. Вона може  присвоїти   Т(Н)   нове  значення  -  деяку  нову літеру.

3. Вона  може  збільшити  або  зменшити  значення   Н   на   1, викликати  тим  самим просування індексу уперед, до наступного елементу стрічки, або  повернення  його  назад,  до   попереднього елемента. Якщо ця операція призводить до виходу  Н  за межі стрічки, то остання подовжується у відповідному напрямку шляхом  додавання нового елементу, що містить спеціальний символ  #  (кінець стрічки). Індексом цього нового елементу є чергове значення  Н.

4. Вона може зупинитись.

Проблема. Алгоритмічна нерозв’язність

Означення 4.2. Проблема - це твердження (предикат) істинне або хибне залежно від значень змінних, що містяться у ньому.

Приклад: «Ціле число  x  менше, ніж ціле число  y».

Означення 4.3. Окремий випадок проблеми - це набір  значень  її змінних.

Для  наведеного вище  прикладу окремим  випадком  проблеми  є будь-яка упорядкована пара цілих чисел.

Відображення множини окремих випадків проблеми у множину {так, ні} називається розв’язком  проблеми. Якщо це відображення можна подати  алгоритмом, то кажуть, що проблема має алгоритмічний розв’язок. У протилежному випадку проблема алгоритмічного розв’язку не має і називається алгоритмічно нерозв’язною.  Одним  з  видатних досягнень математики   ХХ   століття  стало  відкриття  алгоритмічно нерозв’язних проблем.

Одним з прикладів саме такої проблеми є проблема відповідностей Поста.

Окремий випадок  проблеми  відповідностей  Поста над алфавітом  - це скінчена множина  K  пар з   M  = + x +   (тобто множина пар непустих ланцюжків над алфавітом ). Проблема  полягає у з’ясуванні того, чи  існує  скінчена  послідовність  необов’язково різних пар  (x1 , y1), (x2 , y2), … , (xm , ym), що належать  до   K   та задовольняють умові 

x1 x2xm   = y1 y2ym.

Таку послідовність називають  розв’язком  для  даного  окремого випадку проблеми відповідностей.

Приклад   окремого  випадку  проблеми  відповідностей  над алфавітом  {a, b}

{(abbb, b), (a, aab), (ba, b}

Для цього прикладу послідовність  (a, aab), (a, aab), (ba, b), (abbb, b)  -  розвязок.

Для окремого випадку

{(ab, aba), (aba, baa), (baa, aa)}

розв’язку нема, тому що коли у послідовність входить перша пара, загальна кількість букв   a   у  перших  компонентах  менша,  ніж  у других, а коли третя  - букв  b  у перших компонентах більше.

Існує частковий алгоритм, що у деякому розумінні "розв’язує" проблему відповідностей. А саме,  можна лінійно упорядкувати усі послідовності пар ланцюжків, що можна побудувати за поданим  окремим випадком проблеми. Потім можна перевіряти для кожної  послідовності, чи  є  вона  розв’язком.  Знайшовши  першу  послідовність-розв’язок, алгоритм зупиниться з відповіддю  "так". Якщо такої послідовності не існує, цей частковий алгоритм ніколи не зупиниться.

Можна показати, що усюди  означеного  алгоритму  для  розв’язання проблеми відповідностей над  алфавітом,  що  містить  не  менш  двох символів, не існує [1].

Розглянемо іншу проблему, що не має алгоритмічного розв’язку, і доведемо цей факт.

Теорема 4.2. Не існує алгоритму  P, що для кожного поданого на вхід часткового алгоритму  A  дає відповідь  "так" тоді і  тільки  тоді, коли алгоритм  A  є усюди означеним.

Доведення. Припустимо, Р  існує. Тоді можна побудувати алгоритм  Q, що працює таким чином.

Вхід. Будь-який частковий  алгоритм   A,  що  має  одну  вхідну змінну.

Вихід. (1) "ні", якщо

(а) A  не є алгоритмом,

 (б) A - алгоритм, і A(F(A)) = "так";

   (2) "так" в усіх інших випадках.

Метод.  (1) Якщо  Р(A) = «ні», видати «ні» і зупинитися.

   (2) Якщо  Р(A) = «так», застосувати  A  до самого  себе, тобто обчислити  A(F(A)) = A(A).

   (3) Якщо  A(A) = «так», видати «ні».

   (4) Якщо  A(A) = «ні», видати «так».

   (5) Зупинитись.

Q  є усюди означеним алгоритмом з одним входом.  Якщо  на  вхід Q  подати  F(Q), то одержуємо суперечність, тому що  на  виході  не може бути ні «так», ні «ні». Тому зроблене припущення неправильне, і цим завершується доведення.

Деякі інші проблеми,  що  не  мають  алгоритмічного  розв’язку, розглянемо, використовуючи ще одну модель обчислювальної машини.

Машина з необмеженою пам’яттю (МНП)

Ця машина має пам’ять, що складається з  нескінченої  кількості регістрів: R1, R2, … ,  і  вміст  кожного  регістра  Ri  є  ri - довільне ціле невід’ємне число : ri X N =       = N  {0},  де   N  -  множина натуральних  чисел.  Структуру  пам’яті  МНП  умовно  зображено   на рис. 4.2.

 R1                r1

 R2                    r2

 R3              r3

 Rn               rn

Рис.4.2. Структура пам’яті машини з необмеженою пам’яттю.

    У  цій  машині  використовуються  тільки   дві   операції   над регістрами 

Ri + 1 Ri ,    Ri – 1 Ri ,

яким відповідають такі зміни вмісту регістра

    Ri + 1 Ri         ri :=  ri + 1;

                                ri :=  ri - 1, якщо  ri  >  0,

    Ri - 1 Ri           r i := ri, якщо  ri  =  0.                                                                                               

Крім  операцій,  що  змінюють  вміст  регістрів  для  керування роботою машини за  допомогою  програми,  необхідна  ще одна операція - порівняння  ri  з  0.

Для того, щоб  на  вхід  машини  надходили  команди,  уводиться спеціальний механізм - програмний  лічильник. Він реалізується за допомогою одного з регістрів, а усі інші  регістри  використовуються для зберігання інформації.  Стан  програмного  лічильника  є  адреса чергової команди. Тому функція  f  переходу  машини  з  одного  стану  в інший має вигляд 

f : Q x P    Q x P,

де Q - множина станів пам’яті, а  Р  -  множина  станів  програмного лічильника. Елемент відображення  

f : (qa, pb ) (qc, pd )

означає: зі стану  пам’яті  qa  виділити  команду  за  адресою  pb, перевести машину у  стан   qc  (виконати  команду)  і  встановити  у програмному лічильнику значення pd.

Множина регістрів  разом  з  означеними  операціями  і  складає машину з необмеженою пам’яттю (МНП). Програма  для  МНП  є  скінчена сукупність операцій, пронумерованих від  1  до деякого  n   N.

Приклади алгоритмічно нерозв’язних проблем

Теорема  4.3. (про   алгоритмічну   нерозв’язність  задачі самозастосування).  Для  машини  з  необмеженою  пам’яттю  не  існує програми, яка для будь-якої поданої програми  А  при її кодуванні  a =  F(А)   буде  зупинятись  з  вихідним  значенням  0,  якщо   А(a)  зупиняється (тобто програма  А  зупиняється,  якщо  вхідне  значення дорівнює  a), і з вихідним значенням  1, якщо  А(а)  не зупиняється.

Доведення.  Будемо   будувати   доведення   від   супротивного. Припустимо, що така програма існує: назвемо її  В. В(а)  зупиняється з результатом  0, якщо  а  приводить  програму  А  до припинення,  і з результатом  1  у протилежному випадку.

Перетворимо програму  В  таким  чином.  Замінимо  команду  зупинки умовною петлею так, що коли вихідний  регістр  має  значення  0,  ця команда обминається; у іншому разі - зупинка.  Назвемо  цю  програму  С. С(х) зупиняється (і має те ж саме значення, що  і  В(х))  тоді  і тільки тоді, коли вихідне значення дорівнює  1. Блок-схему  програми  С  зображено на рис.4.3.

 

так

                     ні

Рис.4.3. Блок-схема програми  С.

Розглядаючи  С при  вхідному  значенні с  = F(С),  одержуємо суперечність: оскільки  С(с) зупиняється тоді і  тільки  тоді,  коли С(с) = В(с) =1, але  В(с) = 1 тоді і  тільки  тоді,  коли   С(с)  не зупиняється. Звідси прямує, що  С  не може існувати, а тому і  В  не існує.

Теорема 4.4. (про  алгоритмічну   нерозв’язність   проблеми припинення). Для машини з необмеженою пам’яттю  не  існує  програми, яка за довільним входом, що складається з програми і даних, визначає, чи зупиняється програма на цих даних.

Доведення. Припустимо, що така програма В  існує. На  її  вхід повинні подаватися дані  двох  видів:  а  =  F(А)  -  код  довільної програми  А  і   х  =  F(Х)  -  код  вхідних  даних  для   А.   Такі комбіновані дані можна закодувати за допомогою двох простих чисел  р та  q: paqx.

Згідно з припущенням  В(paqx)  зупиняється  з  результатом   0, якщо  А(х) зупиняється, і зупиняється з результатом  1,  якщо  А(х) не зупиняється. У окремому випадку, коли  Х = А, одержуємо  х = а, і тому програма  В(paqa) = С(а)  розв’язує проблему  самозастосування, що суперечить попередній теоремі.

Проблема припинення є класичним результатом про нерозв’язність в теорії  комп’ютерів.  Подібним  чином  доводиться  нерозв’язність таких проблем:

    а) чи зупиняється довільна програма при вхідному значенні  0?

    б) чи  зупиняється  довільна  програма  при  будь-яких  вхідних даних?

    в)  чи  виконується  рівність   L(G)  =       для     довільної контекстно-залежної граматики  G?

    г) чи виконується рівність  L(G1)   L(G2) = , де G1 та G2 - довільні контекстно-вільні граматики ?

    д) чи виконується рівність  L(G) = T*,  G  =  (N, T, P, S)  - довільна контекстно-вільна граматика?

    е) чи виконується рівність L(G1) = L(G2), де  G1 та G2    - довільні контекстно-вільні граматики?

    є) чи є довільна контекстно-вільна граматика є однозначною?

Моделювання «реальних» комп’ютерів

Раніше розглянуті моделі комп’ютера (машина  Тюрінга  та  МНП) істотно відрізняються від реальних комп’ютерів нескінченою пам’яттю. Але логіку роботи  комп’ютера  вони  відображають  правильно. Так, у будь-якому комп’ютері, як і у  МНП,  є програмний лічильник; тільки він має обмежену  кількість  двійкових  розрядів  (нехай   m).  Тоді максимальна  кількість  значень  чисел,  що  можуть  зберігатись   у програмному лічильнику, дорівнює  2m. В цілому  пам’ять  реального комп’ютера також  обмежена  і  складається  з  деякої  кількості   k  регістрів з скінченою кількістю розрядів.

Оскільки пам’ять реальної машини обмежена, її можна  розглядати як  пристрій  зі  скінченою  множиною  станів.  Програма  при  цьому розглядається як сукупність вхідних дій, що призводять  до  переходу машини з одного стану в інший. Звичайно програма починає працювати, коли у програмному лічильнику встановлено  фіксоване  значення,  усі наступні значення  породжуються  автоматично,  доки  не  виконається команда припинення.

Часто  2m  може бути більше ніж   k,  і  тому   2m -  k   значень будуть неправильними адресами, що викликають помилку.  Отже  не  всі  2m значень,  що  можуть  міститись  у   програмному  лічильнику,  є правильними.

Почавши виконувати програму, машина  може  або  зупинитись  під дією  команди  зупинки,  чи   неправильного   значення   програмного лічильника,  або  продовжувати  роботу  нескінченно  довго.   Останнє можливо, в  силу  скінченності  пам’яті,  тільки,  якщо відбувається повторення деякого стану  (q, p). Проте  чекання  такої  події  може продовжуватись досить довго навіть для відносно невеликих значень  k  та  m. Звідси прямує висновок  про  те,  що  за  допомогою  тестових прикладів практично неможливо перевірити коректність програми (хоч і можна виявляти помилки).


 

А также другие работы, которые могут Вас заинтересовать

47925. ОСНОВИ ФІЗІОЛОГІЇ ТА ПЕДІАТРІЇ ДИТИНИ 1.32 MB
  Знати анатомо-фізіологічні особливості дітей різного вікового періоду. Профілактика порушення зору у дітей і підлітків. Виховувати у дітей гігієнічні навички по догляду за шкірою одягом взуттям. План лекції Анатомофізіологічні особливості системи травлення у дітей і підлітків.
47926. Маркетинг та його специфіка в банківській сфері 509.5 KB
  Маркетингова орієнтація передбачає фокусування зусиль і можливостей банку на виявленні реальних і потенційних запитів всіх субєктів економічних відносин і пошуку способів їх найкращого задоволення виходячи з фінансових кадрових організаційних технологічних законодавчих та інших обмежень. Банківський маркетинг традиційно розглядається з двох позицій: як філософія банківського бізнесу і як конкретний спосіб здійснення підприємницької політики банку. Банківський маркетинг це філософія стратегія й тактика банку що спрямовані на...
47927. Муніципальне право як галузь права України 787 KB
  Предметом муніципального права є місцеве самоврядування відносно самостійний вид суспільних відносин пов'язаний з організацією і здійсненням місцевої влади тобто публічної влади влади народу в межах відповідних адміністративнотериторіальних одиниць. Місцеве самоврядування як предмет муніципального права є багатогранним явищем. Зміст місцевого самоврядування полягає насамперед і головним чином у самостійному вирішенні територіальними спільнотами питань місцевого значення. За формою місцеве самоврядування це волевиявлення територіальних...
47928. Предмет і завдання хімії 1.83 MB
  Основні поняття хімії Атом – найменша частинка хімічного елемента що має його властивості. Молекула – найменша частинка речовини що має її хімічні властивості. Менделєєва: властивості хімічних елементів та їх сполук знаходяться у періодичній залежності від заряду ядра.
47929. Принципи й системи обліку 488 KB
  Основні загальноприйняті принципи бухгалтерського обліку.Склад і загальна характеристика міжнародних стандартів бухгалтерського обліку. Класифікація систем бухгалтерського обліку.
47930. ОСОБЛИВОСТІ ФІЗИЧНОГО ВИХОВАННЯ ШКОЛЯРІВ, ЯКІ МАЮТЬ ВІДХИЛЕННЯ У СТАНІ ЗДОРОВЯ 122 KB
  Петриши ПЛАН Стан здоров’я школярів у сучасних умовах Оцінка здоров’я школярів. Стан здоров’я школярів у сучасних умовах В Цільовій комплексній програмі €œФізичне виховання – здоров’я нації вказано що у сучасних умовах в Україні склалася критична ситуація із станом здоров’я населення і наводяться дані про те що майже 90 дітей учнів студентів мають відхилення у здоров’ї. За даними статистики збільшується кількість учнів першого класу які мають відхилення в стані здоров’я тобто на початку навчання у школі а в подальші шкільні...
47931. Основні поняття та визначення концепцій операційніх систем 11.08 MB
  Під ресурсами розуміють процесорний час дисковий простір пам'ять засоби доступу до зовнішніх пристроїв. У разі просторового розподілу ресурс доступний декільком споживачам одночасно при цьому кожен із них може користуватися частиною ресурсу так розподіляється пам'ять. У багатозадачних системах у пам'ять комп'ютера стали завантажувати кілька програм які виконувалися на процесорі навперемінно. Надання задачам справедливої частки ресурсів пам'яті процесора дискового простору тощо.
47932. Предмет і завдання геодезії, її звязок з іншими науками 3.12 MB
  Геодезія - це наука, яка розглядає методи та способи вимірювання земної поверхні, застосування яких дає можливість визначати форму і розміри землі, а також робити зйомку (вимірювання) окремих її частин для зображення на картах, планах використовуваних для створення різних інженерних споруд
47933. Правила та безпека дорожнього руху 2.03 MB
  ЛЕКЦІЇ І з предмету €œПравила та безпека дорожнього руху для студентів спеціальності 5. Ці Правила відповідно до Закону України Про дорожній рух встановлюють єдиний порядок дорожнього руху на всій території України. Інші нормативні акти що стосуються особливостей дорожнього руху перевезення спеціальних вантажів експлуатація транспортних засобів...