О В Копаєв - Модельна сутність алгоритму - страница 1

Страницы:
1  2 

О. В. Копаєв

Черкаський національний університет імені Богдана Хмельницького

Модельна сутність алгоритму

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

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

Таким чином, в контексті з'ясування сутності алгоритмічного стилю мислення та алгоритмічної діяльності постає питання про розгляд поняття алгоритму саме як предмета алгоритмічної діяльності.

Ознайомившись із інтерпретаціями поняття алгоритму у різних авторів з метою виявлення його предметної специфіки, можна помітити, що, як правило, в цих тлумаченнях алгоритм протиставляється алгоритмічному процесу. Наприклад, алгоритм розуміють як «точний припис, що визначає обчислювальний процес, який веде від вихідних даних, що можуть варіюватися, до очікуваного результату» [1, с.3] або «текст, який у визначених обставинах може привести до однозначного розвитку подій - процесу виконання алгоритму» [2, с.5], або «правило, що указує дії, в результаті ланцюжка яких від вихідних даних ми приходимо до шуканого результату. Такий ланцюжок дій називається алгоритмічним процесом, а кожна дія - його кроком»[1] [3, с.10] і т.п. Виходячи з цих тлумачень, логічно припустити, що між алгоритмом та алгоритмічним процесом існують певні відношення. Ми припустили, що ці відношення мають модельний характер.

У попередніх працях нами вже висловлювалася думка про те, що алгоритм можна розглядати як модель, а саме, - знакову модель алгоритмічного процесу [4, 5]. Проте зауважимо, що у тих публікаціях можливість такого розгляду детально не обґрунтовувалася. Думки щодо модельного характеру алгоритму трапляються й у інших дослідників методики навчання інформатики. Наприклад, у О. С Лєсневського: «Алгоритм, точніше його запис, є не що інше, як формальна модель дискретного процесу» [6, с.42]. О. А. Кузнецов стверджує, що «алгоритм - це інформаційна модель діяльності» [7, с.4]. У новій програмі середньої освіти з інформатики та інформаційних технологій Російської Федерації в основному змісті, який пропонується для засвоєння учнями, зазначено: «Алгоритм як модель діяльності» [8, с.23]. На жаль, у цих авторів, так само, як і в згаданій програмі думка про алгоритм як модель лише висловлюється, але не обґрунтовується і не розкривається.

Н. Г. Салміна, аналізуючи тлумачення поняття моделі різними авторами, приходить до висновку, що всі вони виділяють дві характеристики моделі: 1) модель - заміщувач об'єкта вивчення, 2) модель й виучуваний об'єкт перебувають у визначених відношеннях відповідності (і в цьому розумінні модель відображує об'єкт) [9, с.91]. Алгоритм і алгоритмічний процес - це різні об'єкти, причому вони мають різну природу. Разом з тим, вивчаючи алгоритм, можна зробити й певні висновки про алгоритмічний процес, який він задає. Адже алгоритм повністю детермінує алгоритмічний процес, а отже, й повністю його описує. Саме ці міркування дозволяють припустити, що алгоритм можна вважати моделлю алгоритмічного процесу.

Аналізуючи літературу, присвячену питанням моделювання як загальному методу пізнання та питанням навчання моделюванню, ми ознайомилися із працями Ю. А. Гастева , Б. В. Бірюкова та Є. С. Геллера, у яких, зокрема, зроблено висновок, що «... при всьому різноманітті змістів, в яких застосовується в літературі поняття моделі, ці змісти можуть бути охоплені в єдиному підході, в основу якого покладено поняття ізоморфізму і гомоморфізму. А саме, об'єкт (система елементів) А є моделлю об'єкта В тоді і лише тоді, коли існує такий гомоморфний образ А' об'єкта А і такий гомоморфний образ В' об'єкта В, що А' і В' між собою ізоморфні» [10, с.3б].

Тому метою цієї статті є обґрунтування із залученням апарату теорії множин принципової можливості означення алгоритму як моделі алгоритмічного процесу.

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

Будемо вважати, що алгоритмічний процес - це процес, який є: 1) дискретним; 2) однозначно детермінованим; 3) потенційно скінченним та 4) перетворює певні конструктивні об'єкти. Він складається із елементарних дискретних актів або ж операцій. Кожна така операція вибирається з множини операцій певного алгоритмічного виконавця та актуалізується в конкретній обстановці протікання алгоритмічного процесу. Позначимо цю множину О:

О = {оі,     о„}, п єК

Зауважимо, що ця множина є непорожньою, скінченною та задається перерахуванням усіх її елементів. У ході алгоритмічного процесу будь-яка з цих операцій може застосовуватися кілька разів, атому їхні «копії» формально не розрізняються між собою. Розрізнення цих «копій» можна провести, пов'язавши з ними час початку їх виконання в межах алгоритмічного процесу, тобто утворивши пари виду <Оі, tj>, де Оі є О - операція з множини операцій алгоритмічного виконавця (1 < / < п), t,є (0, Т] -момент часу її застосування (виконання) в цьому процесі, а Т - загальний час протікання всього процесу.

Оскільки усі пари такого роду є однорідними, але чітко розрізняються, а однією з характеристик алгоритмічного процесу є потенційна скінченність, то останній можна вважати скінченною множиною таких пар. Однорідність зазначених пар визначається належністю першої складової ol до множини операцій одного й того ж алгоритмічного виконавця, а їх розрізнення визначається відмінністю другої складової ti. При цьому, ti+1 = ti + At, де At - різниця часу виконання «сусідніх» операцій. Для спрощення будемо вважати, що At - величина стала і дорівнює певній одиниці часу. Тоді, tj+1 = tj + 1.

Алгоритмічний процес можна подати v вигляді roacba (схема 1).

Рі Р2 РЗ Р4 рх-1 Рх О--*-0-*-0—-----*-0-*-0

Схема 1. Подання алгоритмічного процесу у вигляді графа

Таким чином,

Рі =<0іЛ >, «і єО, l = \,n, t, =ґг_! +1, z=l,x;

Р = \,Р2,-,Рх), ХЄИ.

Пару виду <oh tj> (або рг) назвемо операцією алгоритмічного процесу. Задамо на множиніР бінарне відношення R  = {(pj,pj)\j<і, і, j = 1,х} Це відношення є:

1) транзитивне: із того, що pj RPpj і pj RPpkслідує, що pj RPpk ;

2) рефлексивне: для будь-якого pj із P з того, що pj RPpj слідує, щоpj RPpi,

3) антисиметричне: із того, що pi RP pj+1  і pj+1 RP pj слідує, що pj = pi+1.

Отже, на множині операцій алгоритмічного процесу P визначене відношення порядку. Позначимо його RP. Крім цього, на цій же множині визначимо унарну операцію слідування[2]

fp -Pi Рі,Рі+\ єр

Оскільки на множині P визначені відношення порядку та операція слідування, то трійка < P, RP, fP > є алгебраїчною системою[3]. Позначимо її SP.

Якщо всі наведені вище викладки повторити для алгоритму (для спрощення вважаючи його лінійним), і першим елементом пари обрати деякий оператор оргт (1 < т < п) з множини операторів алгоритмічного виконавця (яку позначимо OPR.), а у ролі другого елемента - порядковий номер щ ( njeN), цього оператора в алгоритмі, то отримаємо:

aj =<oprm,rij >, oprm eOPR , m = \,n, ny J_1 +1; j = l,y;

А = {аъа2,...,ау), yeN.

Пару виду <oprm, n> (або ж aj) назвемо алгоритмічним оператором.

На множині А теж визначене відношення порядку, яке позначимо Ra, та унарна операція

Тому трійка < A, RA, fA > теж є алгебраїчною системою, яку позначимо SA. Алгоритм (лінійний) можна подати v вигляді rnarha:

«і         яз       аз       &4               ау ау О-*-0------

Сиема 2. Подання лінійного алгоритму у вигляді графа

Як уже зазначалося, перебіг алгоритмічного процесу повністю детермінується відповідним алгоритмом. У випадку лінійного алгоритму кожному елементу (алгоритмічному оператору aj) алгоритму A відповідає елемент (операція pi) алгоритмічного процесу P, причому i = j, x = y :

ai p1; a2    pi, . ^  ay py, і навпаки, кожному елементу алгоритмічного процесу P відповідає елемент алгоритму A:

pi ai, p - a2,_ _ py ay. Кожному елементу множини A поставлений у відповідність єдиний елемент множини P та, навпаки, - кожному елементу множини P поставлений у відповідність єдиний елемент множини A. Отже, має місце взаємооднозначне відображення зазначених множин (схема 3):

PI P2

О-*-o-

+ t

I I

о-*o-

Схема 3. Взаємооднозначне відображення множини алгоритмічних операцій та множини операцій алгоритмічного процесу

P = {pi,p-,     py} <-> A = {ai, a-, ay}.

Тому відношення порядку RP, задане на множині елементів P, зберігається й для множини A. Також зберігається й операція слідування:

Якщо fp : pt -+pi+l; Pi,pi+i є і5, то fA :а, ->a;+1, о„йі+1єі.

Таким чином, множини Л і Р є ізоморфними[4]. Тому можна зробити висновок: алгоритм та алгоритмічний процес є ізоморфними між собою.

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

Скористаємося такими означеннями: «гомоморфізмом називають таку відповідність між двома системами об'єктів із визначеними для цих об'єктів відношеннями, при якій: 1) кожному об'єкту першої системи поставлений у відповідність лише один об'єкт другої системи, і кожному відношенню першої системи поставлене у відповідність лише одне відношення другої системи; 2) якщо для деяких об'єктів a, b, є,... першої системи виконується певне відношення S першої системи, то для об'єктів a', b', c\... другої системи, що відповідають об'єктам a, b, c, виконується відношення S' другої системи, яке відповідає відношенню S. Друга система об'єктів і відношень називається при цьому гомоморфним образом першої» [12, с.182]. При цьому ізоморфізм є частковим випадком гомоморфізму: «в тому частковому випадку, коли, по-перше, встановлена між двома системами, що розглядаються, відповідність взаємооднозначна і, по-друге, відношення S' виконується у другій системі між об'єктами a', b', c'. тоді й тільки тоді, коли відповідне відношення S виконується між відповідними об'єктами a, b, c,.   першої системи, гомоморфізм називають ізоморфізмом» [12, с.182].

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

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

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

и'

С™ =-, n,m<EN, т< п .

т\(п-т)\

Фрагмент комп'ютерної програми, описаний мовою Pascal, що реалізує цей алгоритм, може мати такий вигляд:

C  := Fact(N)/(Fact(M)*Fact(N - M));

Функція знаходження факторіалу Fact(x) може розглядатися як окрема елементарна дія (оператор)

в межах алгоритму знаходження значення функції        . Але для практичного застосування є

обов'язковою реалізація знаходження факторіалу шляхом застосування лише елементарних операторів алгоритмічного виконавця (в цьому випадку - операторів мови Pascal). Наприклад,

function Fact(const N: Byte): Integer; var

I: Byte;

Result: Integer; begin

Result  := 1;

for I   := 2 to N do

Result  := Result * I; Fact  := Result; end;

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

Страницы:
1  2 


Похожие статьи

О В Копаєв - Модельна сутність алгоритму