загрузка...
загрузка...
На головну

Глава 3. Алгоритми. Алгоритмізація

  1. Алгоритмізація та
  2. Алгоритмізація і програмування
  3. Алгоритмізація.
  4. Бібліографічний список по всім главам
  5. У Цивільному кодексі України (глава 35) виділяється два види договору найму. У теорії їх називають комерційний і соціальний.
  6. В Глава 1. Емоційне реагування
  7. В Глава 12. Характеристика різних почуттів

3.1 Абстрактні автомати і поняття алгоритму

Класичні приклади абстрактних автоматів - машина Тьюринга або алгоритмічна система Посту (Пост на відміну від Тьюринга не користувався терміном машина). Щоб підкреслити єдність підходів обох авторів будемо вживати термін «машина». Машина Поста складається з нескінченної стрічки, розділеної на окремі секції (осередки), в які можна або заносити мітку, або зчитувати мітку за допомогою записує чи зчитує головки (рис. 3.1). Стрічка (або головка) може пересуватися в ліву чи праву сторони на один крок в залежності від команди. Стрічка завжди зупиняється так, щоб навпроти головки перебувала секція (осередок). Команди абстрактного автомата зазвичай включають в себе одну з таких дій (на прикладі машини Посту); рух головки вправо, рух головки вліво, запис мітки, стирання мітки, передача управління, зупинка (стоп).

Кожна команда має свій номер i. Стрілка вказує напрямок руху. Друге число j, що стоїть в кінці команди, називається відсиланням.

Мал. 3.1.

У команди передачі управління можуть бути дві відсилання. Тому програма абстрактного автомата повинна володіти двома властивостями:

  • на першому місці в списку завжди стоїть команда з номером 1, на другому місці - з номером 2 і т. д .;
  • відсилання кожної з команд завжди знаходиться в списку команд програми.

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

Для «роботи» абстрактного автомата необхідно задати програму і початковий стан, т. Е, положення головки і стан осередків стрічки. Після цього автомат приступає до виконання команди номер 1. Всі секції (осередки) стрічки нумеруються в певному порядку. Порядок нумерації осередків може збігатися з порядком, в якому розташовані натуральні цілі числа.

Кожна команда виконується за один крок, після чого починається виконання команди, номер якої зазначений в відсилання. Якщо ця команда має дві відсилання, то команда з номером верхньої відсилання виконується, якщо під головкою знаходиться порожня клітинка. Якщо ж під головкою знаходиться осередок з міткою, то виконується команда з номером нижньої відсилання. Виконання команди передачі управління не змінює стану автомата (жодна з міток не знищується і не ставиться, і стрічка залишається нерухомою). При запуску автомата може виникнути одна з наступних ситуацій:

автомат дійшов до виконання нездійсненним команди (запис мітки в зайняту комірку, стирання мітки в порожній клітинці); виконання програми припиняється, автомат зупиняється (назвемо це стан поломкою автомата), відбувається безрезультатна зупинка;

автомат дійшов до команди стоп, програма вважається виконаним, відбувається результатная зупинка;

автомат не доходить ні до результатной, ні до безрезультатною зупинки, відбувається нескінченна робота (автомат «завис»).

На таких елементарних автоматах, як машина Посту або машина Тьюринга, можна проводити різні дії над числами. Для цього необхідно представляти числа у абстрактному автоматі.

Назвемо послідовність секцій (осередків), що містять мітку, масивом, а число секцій в ньому - довжиною масиву. Домовимося число n представляти на стрічці масивом довжини n + 1. Тоді цей масив будемо називати автоматним зображенням числа. Наприклад, числа 6, 3 і 2 представлені відповідно на рис. 3.2. автоматними зображеннями.

Мал. 3.2. автоматні зображення чисел

Уявімо собі, що на машині Посту треба додати 1 до будь-якого числа.

Для цього потрібно написати програму для машини Поста, що володіє наступною властивістю: для будь-якого числа n, записаного на стрічці, програма повинна дати результатную зупинку із записом числа n + 1 в довільному місці стрічки.

Програма повинна виглядати наступним чином:

В якості початкового стану може бути вибрано будь-який стан, при якому головка знаходиться на одній із зазначених осередків стрічки (т. Е. Над набором числа). Якщо ж головка буде знаходитися в довільному місці стрічки, то програма ускладниться. За допомогою абстрактного автомата можна реалізувати і інші перетворення числової інформації.

Можна скласти програми для складання, множення, ділення чисел. Чи є обмеження на обчислення, вироблені на машині Посту? Відповідь на це питання було сформульовано самим Е. Постом в наступному вигляді: «Завдання па складання програми, що приводить від вихідного даного до результуючому числа, тоді і тільки тоді має рішення, коли є який-небудь загальний спосіб, що дозволяє за довільним і одному даному виписати результуюче число ».

Формулювання постулату Посту підводить до поняття алгоритму.

Англійський математик А. М. Тьюринг в роботі «Про обчислюваних числах з додатком

до проблеми дозволу »і американський математик Е, X, Пост в роботі« ФІНІТНОГО комбінаторні процеси »майже одночасно в 1936 р дали уточнення поняття« алгоритм »на прикладі гіпотетичної машини з нескінченною стрічкою. Машина Тьюринга відрізняється від

машини Посту тим, що осередки заповнюються не просто міткою, а символами із заданого безлічі, у машини Тьюринга є логічний пристрій.

Історично термін «алгоритм» походить від прізвища узбецького математика IX століття Мухаммада ібн Муса ал - Хорезмі, який вперше сформулював правила чотирьох арифметичних дій. Спочатку саме ці правила називалися алгоритмами, але потім термін отримав подальший розвиток в першу чергу в математиці.

Існує багато визначень терміну «алгоритм». Наприклад, за визначенням акад. Л, Н. Колмогорова, алгоритм або алгорифм - це будь-яка система обчислень, які виконуються за строго визначеними правилами, яка після будь-якого числа кроків свідомо призводить до вирішення поставленого завдання.

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

3.2 Форми запису алгоритмів.

Словесна форма запису алгоритму.

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

Наприклад, алгоритм знаходження найбільшого спільного дільника (алгоритм Евкліда) двох натуральних чисел можна записати в такий спосіб:

1) задати два числа;

2) якщо числа рівні, то взяти будь-який з них в якості відповіді і зупинитися, інакше продовжити виконання алгоритму;

3) визначити більше з чисел;

4) замінити більше з чисел різницею більшого і меншого з чисел;

5) повторити алгоритм з кроку 2.

За вказівками цього алгоритму можна знайти найбільший спільний дільник для будь-якої пари цілих чисел.

Словесний спосіб немає поширення, бо такі описания не строго формалізуються, допускають неоднозначність тлумачення окремих приписів.




Властивості інформації. | Формула Хартлі | Формула Шеннона. | Джерело - кодує пристрій - кодер каналу - канал зв'язку - декодер каналу - декодер - приймач. | Принципи фон Неймана | ЕОМ - програмно-керований цифровий автомат. | Коротка історія розвитку ЕОМ | перше покоління | друге покоління | третє покоління |

загрузка...
© um.co.ua - учбові матеріали та реферати