Головна

Інтуїтивного поняття алгоритму, ОПЕРАЦІЇ

  1.  A. Поняття дії в класичній механіці
  2.  Event-менеджмент - поняття, основні методи.
  3.  I. Поняття конфлікту
  4.  I. Територіальна і соціальна диференціація мови. Поняття загальнонародного і національної мови. Літературна мова.
  5.  II. ПОЛІТИКА: ПОНЯТТЯ І ГРОМАДСЬКИЙ СЕНС
  6.  II. Поняття і види динаміки мови. Екстра-та інтралінгвістичні (внутрішні) умови розвитку мови.
  7.  II. Поняття про граматичному ладі мови як об'єкт і предмет вивчення граматики.

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

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

Про п р е д е л е н і е. алгоритм - Це припис, провідне від вихідних даних до шуканого результату і володіє властивостями: 1) визначеності (общепонятном і точності); 2) масовості; 3) результативності.

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

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

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

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

Операції.

Про п р е д е л е н і е. операціями називаються: 1) натуральні операції (див. нижче); 2) линеаризация і делінеарізація (див. Нижче); 3) двомісна операція з'єднання слів (конкатенація); 4) будь-яке оголошене операцією відображення, здійснюване алгоритмом.

Визначимо натуральні операції. Попередньо визначимо одну приватну символьну конструкцію, яка нам при цьому буде потрібно.

Введемо в розгляд зв'язок першого рангу і першого жанру, неоднакову з молодою зв'язком проходження, і назвемо її виділяє зв'язком.

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

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

Натуральні операції діляться на натуральні дії і натуральні умови. У свою чергу, натуральні дії діляться на чотири групи. До групи I входять перетворення слів в слова; в групу II - перетворення слів в квазіслова; в групу III - перетворення квазіслов в квазіслова; нарешті, в групу IV - перетворення квазіслов в слова. V групу натуральних операцій утворюють умови, виконання яких не змінює операнда, але ставить йому у відповідність логічне значення (істина, якщо умова виконана, або брехня, якщо не виконано). Перш ніж приступити до роз'яснення операцій лінеаризації і делінеарізаціі, розглянемо проблему отримання всіляких нумераций довільної сукупності предметів, якщо відома якась їх нумерація.

Таблиця 3.1.

Перелік натуральних операцій

 номер групи  Назва операції  опис
I  a - генерація  Перетворення порожнього слова в однобуквені слово складається з букви a
 анігіляція  Перетворення однобуквені слова в порожнє слово
 II  Знаходження початку слова  Перетворення непорожньої слова в квазіслова шляхом виділення його початку
 III  просування вперед  Перенесення в квазіслова виділяє зв'язку на одну букву правіше
 просування назад  Перенесення в квазіслова виділяє зв'язку на одну букву лівіше
 Подовження вперед (без продовження)  Перетворення квазіслова з виділеним кінцем шляхом приєднання літери, однаковою з виділеної
 відкидання кінця  Перетворення квазіслова в нове шляхом відкидання літер, наступних за виділеною, яка при цьому стає виділеної
 IV  відключення  Квазіслова перетворюється в непорожнє слово шляхом відкидання виділяє зв'язку
V  Натуральні умови: Умова непустоту  Перевіряється предикат «розглядається слово непусто»
 Умова початку  Перевіряється предикат «в розглянутому квазіслова виділена перша буква»
 Умова кінця  Перевіряється предикат «в розглянутому квазіслова виділена остання буква»
 Умова тотожності букв  Перевіряється предикат «в розглянутому квазіслова виділена буква, однакова з a»

Отже, припустимо, що деяка кінцева сукупність предметів перенумерована числами

1,2, ..., n, n> 1.

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

1) Складемо рядок s з одного елемента 1; перейдемо до п.2.

2) Параметру j дамо (тимчасово) значення 1; перейдемо до п.3.

3) Якщо j = n, то перейдемо до п.4, інакше - до п.6.

4) Припишемо в кінці кожної з наявних послідовностей s число j + 1. Нами отримані нові послідовності, обмінюючи в кожній з них елемент j + 1 стільки раз, скільки можливо, з попереднім елементом, з кожною новою послідовності отримаємо ще j нових послідовностей. Кожну з нових послідовностей будемо називати ім'ям s (старих послідовностей вже немає). Перейдемо до п. 5.

5) Збільшимо значення j на 1 і перейдемо до п. 3.

6) Утворити пари з отриманих послідовностей, в кожній з яких 1-v членом є послідовність 1,2, ..., n. Всього таких пар буде v = n! -1. Вважаємо, що в кожній парі елементи (числа), однаково розташовані в її членах, взаємно-однозначно відповідають один одному. Таким чином, отримано v цілочисельних функцій, кожна з яких дозволяє перетворити вихідну нумерацію в деяку нову. Перейдемо до п. 7.

7) Послідовно застосовуючи отримані функції до вихідної нумерації, отримуємо з неї (і крім неї) ще v нових нумераций. Процес закінчено.

Суттєвою рисою описаного процесу є та обставина, що крім опису його і вихідної нумерації для отримання всіх можливих нумераций ніяких додаткових даних не потрібно. Отримані нами функції ми будуємо тоді, коли вони можуть знадобитися. Мати їх в запасі не потрібно. Це важливо тому, що такий запас, придатний на будь-який випадок, був би нескінченний, а процедура отримання всіх можливих нумераций не була б ефективною. При n = 1 задана нумерація є єдино можлива.

лінеаризацією називається операція, за допомогою якої довільна конструкція класу (А, в, е) перетворюється в слово певного спеціального виду в спеціальному розширенні алфавіту А. Перш за все опишемо потрібне нам розширення алфавіту А.

Візьмемо довільний алфавіт літер З, що не перетинається ні з А, ні з В, і має число букв, рівне певного нами максимальному рангу зв'язків, перерахованих в В. Нарешті, візьмемо алфавіт D, що не перетинається ні з А, ні з В, ні з С, число букв якого дорівнює 3. Для визначеності літерами в D вважатимемо символи "(", ")" і "1", які будемо називати дужками і одиницею (цифрою 1). Як розширення алфавіту А візьмемо А '= ВEАE СED. Слова, утворені з одиниць, ми будемо при виконанні нумераций застосовувати як записи цілих чисел в одиничної системі числення.

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

Нижче, при описі процесу лінеаризації, ми будемо довільно нумерувати ті або інші елементи конструкції, а потім враховувати всі можливі результати довільній нумерації. Для цього будемо репродукувати оброблювану конструкцію n! -1 Раз (де n - найбільший з довільних номерів) і виробляти перетворення довільних номерів (представлених як такі рядки 1 ... 1) способом, описаним вище. Після кожного такого кроку число оброблюваних конструкцій буде збільшуватися. Подальші дії будуть застосовуватися до кожної з n! отриманих конструкцій в припущенні, що кожна з них має те ж ім'я, що і вихідна.

Лінеаризація складається з наступних етапів.

Етап I. Перетворювані конструкцію До укладають в оболонку.

Етап II. Знаходять в До для кожної літери bi (I = 1,2, ...) алфавіту В 'всі зв'язки, що відповідають цій букві. Проводять їх довільну нумерацію і позначають словами 1,11, і т. Д. Якщо довільна нумерація привела до найбільшого номером, який ?2, то визначають всі можливі нумерації, збільшуючи число примірників оброблюваної конструкції і перетворюючи вищеописаним способом номера. Вважають, що кожна з отриманих конструкцій має ім'я К. Далі, переходячи від зв'язку до зв'язку в кожній К, в порядку, який задають приписані зв'язків номера, впорядковують гілки кожної зв'язку аналогічно тому, як це робилося для зв'язків, з тією лише різницею, що замість алфавіту В використовують алфавіт С, вважаючи, що гілкам i-ого жанру відповідає i-ая буква цього алфавіту. Число конструкцій знову зростає (після кожної довільної нумерації), а ім'я До закріплюється за кожною з отриманих конструкцій (це дозволяє, кажучи про К, мати на увазі кожну з них).

Після закінчення цього етапу всі зв'язки і гілки зв'язків в деякому числі конструкцій, кожна з яких називається К, позначені буквами та номерами.

описом кожної гілки будь-якого зв'язку називають слово, на початку якого стоїть буква в В, потім кілька букв "1", потім - буква в С і, нарешті, знову кілька одиниць, Вважають, що зв'язку розпалися на окремі гілки.

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

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

Етап IV. З усіх попередніх результатів вибирають один, який лексикографічно не старші інших. Це і є результат лінеаризації.

Незважаючи на ряд актів сваволі, які були зроблені при лінеаризації, її результат однозначний, звичайно, при заданих алфавітах В, С і D.

Делінеарізаціей називається процес відновлення конструкції по слову, який має відповідну структуру, коротко кажучи, - є її описом.

Для конструкції класу (А, в, е) називаються однаковими, Якщо вони при однаковому А 'дають один і той же результат лінеаризації.

 




 Аналогові обчислювальні машини. |  Якість програмних систем. |  Поняття потоку даних. |  СПЕЦИФІКАЦІЇ У ВИГЛЯДІ ГРАФІЧНИХ СХЕМ. |  INNER JOIN |

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