алгоритмічні моделі

Алгоритмічні моделі засновані на понятті алгоритму. Історично перші точні визначення алгоритму, що виникли в 30-х роках, були пов'язані з поняттям обчислюваності. З тих пір було запропоновано безліч, як з'ясувалося, еквівалентнихопределеній алгоритму.

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

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

ЗАВДАННЯ. Описати процедуру, що реалізує перетворення з називного відмінка в родовий для іменників наступних типів: БУДИНОК, МАМА, ВИЛКА, КІНО, НІЧ, ТОКАР, КІЛЬ.

Рішення 1 зазначено на рис. 6.1 у вигляді блок-схеми відповідного алгоритму.

Мал. 6.1. Рішення 1. Алгоритм

З точки зору програмування на алгоритмічних мовах гідності подібного уявлення очевидні - ця блок-схема без труднощів перекладається в текст програми, наприклад, на мові Асемблер або С ++. Однак саме складання подібної блок-схеми при появі іменників нових типів стає, очевидно, все більше і більше стомлюючим заняттям. Для ілюстрації цього припустимо, що дана

ДОДАТКОВА ЗАВДАННЯ. Розширити алгоритм, представлений на рис. 6.1. на слова ВАСЯ, ЧАС, АКЦІЯ, ЗАВДАННЯ.

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

продукційні моделі

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

Таблиця 6.1. рішення 2

Для слова РОЗА буде виявлено відповідність з ситуацією "-А". В результаті виконання дії "-и" буде отримано вихідний слово ТРОЯНДИ.

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

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

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

Для продовження скачування необхідно зібрати картинку: