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. Звідси прямує висновок  про  те,  що  за  допомогою  тестових прикладів практично неможливо перевірити коректність програми (хоч і можна виявляти помилки).


 

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

75405. Типы склонения существительных 15.83 KB
  Изменение слова по падежам называется склонением. Склонение – 1) класс слов, объединенных общностью словоизменения, 2) отвлеченный образец, по которому изменяются слова этого класса. В современном русском языке существует три таких класса (три склонения) – первое, второе и третье
75406. Степени сравнения прилагательных. Проблема их включения в состав форм прилагательных. Вопрос о существовании простой превосходной степени 14.71 KB
  Степени сравнения прилагательных. Вопрос о существовании простой превосходной степени. Категория степени сравнения у прилагательных это словоизменительная морфологическая категория образуемая двумя рядами противопоставленных друг другу форм с морфологическими значениями положительной и сравнительной степени. В формах положительной степени заключено морфологическое значение представляющее названный прилагательным признак вне сравнения по степени его проявления.
75407. Прилагательное как часть речи. Разряды прилагательных по значению и их влияние на изменение слов. Противопоставление кратких и полных форм и его функции 389.5 KB
  Ряд отличительных черт: имеют два ряда форм полные атрибутивные и краткиепредикативные образуют формы сравнит. У них всегда производная основа они склоняются но не образуют степеней сравнения и краткой формы у них отсутствуют все признаки свойственные качественным прилагательным. Полные склоняемые формы называются атрибутивными краткие несклоняемые предикативными. Соотносительные полные и краткие формы имеют только качественные прилаг.
75409. Вводные слова и основания для их выделения в особую часть речи 29 KB
  Вводные слова и основания для их выделения в особую часть речи. Как особая часть речи нередко рассматриваются вводные или модальные слова. Это неизменяемые слова производные от слов иных частей речи при помощи которых выражается субъективное отношение говорящего к высказыванию или его части с точки зрения достоверности недостоверности т. Как правило эти слова выступают в синтаксической функции вводного слова: вопервых итак разумеется вернее дескать всего подобных слов около трёхсот.
75410. Проблема местоимений как особой части речи. Особенности местоименной семантики и функции местоименных слов. Основания для их разведения по разным частям речи 12.67 KB
  Термин местоимение в грамматической науке употребляется также применительно к более широкому кругу слов, чем местоимения-существительные: местоимениями называются слова – существительные, прилагательные, числительные
75411. Проблема слов «категории состояния». Их признаки и основания для выделения в особую часть речи. Понятие «предикатив» и его соотношение с «категорией состояния» 13.23 KB
  Проблема слов категории состояния. Понятие предикатив и его соотношение с категорией состояния. Категория состояния это класс слов которые обозначают независимый признак состояние душевное физическое или эмоциональное состояние человека окружающей среды и природы и не имеют форм словоизменения склонения и спряжения но могут с помощью глаголасвязки выражать значение времени. При характеристике категории состояния как части речи основная трудность связана с необходимостью отграничивать эти слова от омонимичных им форм...
75412. Наречие как часть речи. Проблема компаратива 17.62 KB
  Главным формальным признаком наречия как части речи является отсутствие словоизменения. Исключение составляют наречия образующие формы сравнительной степени. По своему общему значению непроцессуального признака наречия близки прилагательным. Этим значением определяются синтаксические функции наречий: вопервых они определяют глагол имя или другое наречие соединяясь с ним связью примыкания; вовторых наречия свободно употребляются в функции сказуемого; втретьих наречия определяют предложение в целом.
75413. Глагол как часть речи. Принципиальное отличие глагола от имени. Особенности глагольной основы. Классы глаголов 46 KB
  Глагольные спрягаемые формы чаще всего в предложении выполняют предикативную функцию. По образованию глагольные формы распадаются на две группы в зависимости от образующей основы которая может выступать в двух вариантах: как основа неопределенной формы и как основа настоящего времени. Основа неопределенной формы определяется путем устранения аффиксов ть ти: собирать.