Область наук:
  • Математика
  • Рік видавництва діє до: 2012
    Журнал
    Освітні технології (м.Москва)
    Наукова стаття на тему 'АЛГОРИТМИ І АЛГОРИТМІЧНІ СТРУКТУРИ'

    Текст наукової роботи на тему «АЛГОРИТМИ І АЛГОРИТМІЧНІ СТРУКТУРИ»

    ?"ЛУ

    Г.В. Суходольський

    АЛГОРИТМИ І АЛГОРИТМІЧНІ СТРУКТУРИ1

    Алгоритм - це правило або програма дій для вирішення будь-якої задачі. У класичній математиці алгоритми називалися алгорифм, але це застаріло. Алгоритм як математичний об'єкт може бути заданий в будь-який з п'яти форм: словесної, символічної, графічної, табличній і аналітичної. Математичні функції, позначені символами, записані у вигляді рівнянь, все є алгоритмами. Наприклад, коли ми пишемо за цим символом тригонометричної функції ховається правило її обчислення: взяти відношення катета, протилежного куту, до катета, йому прилеглому. А рівняння прямої у = ах + Ь в неявному вигляді описує, як отримати значення однієї з функціонально пов'язаних змінних, множачи на константу значення іншої змінної (аргументу) і підсумовуючи з ще однією константою. Цей предпісательной сенс рівняння став би більш явним, якби його записувати так: ха + Комерсант = у.

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

    В однозначному алгоритмі дії слідують один за одним як причини і наслідки до отримання результату, заради которо-

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

    Багатозначні алгоритми більш складні: вони складаються з безлічі однозначних під-алгоритмів, або реалізацій, які "включаються" при певних умовах. Багатозначні алгоритми придатні для вирішення завдань певного класу при ширшому колі умов, ніж однозначні алгоритми. Зазвичай однозначні подалго-ритми представляють собою варіанти, в сукупності призводять до вирішення завдання. Тому можна уявити багатозначний алгоритм у вигляді безлічі однозначних варіантів і називати його «варіативним» алгоритмом. Ось характерний приклад.

    Зі шкільної лави і за довідниками всім відомо, що (а + + Ь) 2 = а2 + 2аЬ + Ь2. Але якщо врахувати, що (а + М = (а + ред) (а + ред) і всілякі перестановки порядку дій, то виявиться: за цієї звичної формулою ховаються 38 варіантів обчислень. Наприклад: (Ь + а) 2 = 62а + Ь2 + а2. І я, напевно, не всі варіанти перерахував.

    1 Суходольський Г.В. Математичні методи в психології. 3-е изд., Испр. Харків: Вид-во «Гуманітарний

    центр », 2008.

    ТЕХНОЛОГІЯ І ПРАКТИКА НАВЧАННЯ ............

    Взагалі кажучи, слід зрозуміти, що будь-яка «людська» завдання варіативна, тобто має багато способів вирішення. На жаль, вони зазвичай не відомі і не використовуються, як в прикладі з (а + Ь) 2. Навіть для нескладних завдань одна людина досить складно знайти кілька можливих варіантів вирішення. А більш-менш повне безліч варіантів існує як чорний ящик, який можна «просветлить» лише великому числу працюючих над ним ісследователей2.

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

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

    2 Наприклад, в кінці 60-х рр. Арон Флейшман разом

    зі мною досліджував варіативність завдання із завдань-

    ника для 4-го класу. Нам вдалося незалежно один від одного знайти по 4-6 способів вирішення. І тільки коли ці пошуки у вигляді експерименту «спробуй виріши ще

    будь-яким іншим способом »(на гнучкість мислення-

    ня) ​​були проведені в фізико-математичних класах, серед студентів, інженерів - людина 300, тоді було знайдено 12 способів вирішення (від 4 дій до

    7 дій).

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

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

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

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

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

    "ЛУ

    Мал. 1. Графи алгоритмів: а - ЛСА (логічна схема варіативного алгоритму): А, Б, В, Г, Д - позначення дій; б - дві однозначні реалізації варіативного алгоритму: 1 - без повторень, 2 - з одноразовим повторенням; в - граф стохастичного варіативного алгоритму, отриманий узагальненням зважених імовірностями Р1 і Р2 реалізацій

    Але може трапитися, що спочатку намічене місце, куди переставлено об'єкт, чимось неадекватно і об'єкт потрібно знову перенести на інше місце. У такому випадку дія «поставити» поєднується з оцінним дією «чи то місце»; в результаті з'являються дві можливі оцінки - «так», «місце то», або «ні», «місце не те». ось,

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

    Тоді замість реалізації з двома переносами (рис. 1, б, 2) з'явиться реалізація з трьома, чотирма і т.д. переносами. Але я для прикладу обмежуся двома реалізаціями.

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

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

    Так ось як «простого» можна прийняти алгоритм, число дій в якому відповідає міллеровськие числу 7 ± 2. При більшій кількості дій доводиться розчленовувати задачу на підзадачі, які вирішуються простими алгоритмами, і синтезувати з них складні алгоритми, які доцільно, по суті справи, називати «алгоритмічними структурами».

    ТЕХНОЛОГІЯ І ПРАКТИКА НАВЧАННЯ

    ......Ц ~ хз............

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

    Ця ситуація добре знайома всім навчалися у ВНЗ. Викладач задає питання, а студент на них відповідає - правильно чи неправильно. І залежно від кількості правильних і неправильних відповідей, викладач оцінює знання студента дихотомически - «залік» або «незалік».

    Досвідчений викладач не стане перетворювати залік в іспит. Він буде задавати «ключові» питання по курсу і обмежить їх кількість - мінімально двома, максимально трьома питаннями. Тому що дві правильні відповіді достатні, щоб поставити залік, так само як два неправильних відповіді достатні, щоб заліку чи не поставити. Невизначеність виникає, якщо студент на два питання дає один правильний і один неправильний відповідь. У цьому випадку необхідний третє питання, за результатами відповіді на який ставиться «залік» або «незалік».

    Таким чином, є всього шість варіантів дій і рішень. Вони у вигляді

    2 Суходольський Г.В. Структурно-алгоритмічний аналіз і синтез діяльності. Л., 1976; Суходольський Г.В. Математико-психологічні моделі діяльності. СПб., 1994; Суходольський Г.В. Введення в математико-психологічну теорію діяльності. СПб., 1998..

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

    Мал. 2. каскадний граф алгоритмічної структури заліку, проведеного викладачем:

    В - питання викладача; ОП, ВОНИ - відповідь правильний чи неправильний, що дається студентом; 3, НЗ - оцінки «залік» або «незалік», які ставить викладач

    Неважко бачити, що утворюють алгоритмічну структуру в даному випадку

    є діади «питання-відповідь», які можна розглядати в якості елементарних алгоритмів. Їх з'єднання в ланцюжки, кероване характером відповідей студента і оцінками викладача, і утворює дану алгоритмічну структуру. На рис. 2 вона показана як варіативна нестохастична. Але це не так.

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

    Випишемо це мульти в загальному вигляді:

    (?! ВОП, .ВОП, 3; Р2 ВОП, ВОНП, ВОП, 3; Р3 • ВОНП, ВОП, ВОП, 3;

    ^ <107 ^

    Р4 • ВОНП, ВОНП, НЗ;

    Р5 • ВОП, ВОНП, ВОНП, НЗ;

    Р1 • ВОНП, ВОП, ВОНП, НЗ).

    Звичайно, сума цих шести ймовірностей дорівнює одиниці. Сума трьох перших: Р (3) = Р1 + Р2 + Р3 визначає загальну успішність групи (курсу). Сума трьох останніх: Р (НЗ) = Р4 + Р5 + Р6 змушує задуматися над дефектами навчання або навчання. Сума Р2 + Р3 характеризує частку студентів, погано освоїли 1/3 навчального матеріалу, а сума Р5 + Р6 - частку студентів, які не засвоїли 2/3 необхідних знань. Таким чином, кількісно аналізуючи підсумки реалізації даної алгоритмічної структури, можна отримати корисну інформацію.

    Редакція дякує Видавництво «Гуманітарний центр» (м.Харків, Україна) за надані матеріали (Н. Томашек, Г. Суходольський).


    Завантажити оригінал статті:

    Завантажити