Визначення алгоритму в інформатиці, властивості та приклади

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

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

Основні властивості

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

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

Вперше поняття алгоритму ввів математик Мухаммед ібн Мус ал-Хорезмі, який жив у 783-850 роках. У “Книзі про додавання і віднімання «вводиться визначення алгебри і описується, як формульно записувати натуральні числа і методи обчислень»стовпчиків”.

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

• Підійти до дороги.
• Подивитися на світлофор.
• Визначити колір світлофора.
• Якщо світло зелене і машини не їдуть — перейти дорогу.
• Якщо світло червоне і машину їдуть — повернуться до дії 2.

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

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

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

• Словесна – запис природною мовою.
• Псевдокод – умовна алгоритмічна мова, що включає в себе елементи мови програмування і Математичні символи.
• Графічна або блок-схема – зображення з фігур і стрілок.
• Програмна – текст певною мовою програмування.

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

Існує 3 види представлення алгоритму:

Найпростіший – лінійний алгоритм. Виконує послідовно дії без розгалужень і повторень.

Приклад “миття рук”:

1. Включити воду.
2. Намочити руки.
3. Взяти мило.
4. Намилити руки.
5. Змити водою мило.
6. Вимкнути воду.

Розгалужена алгоритмічна структура означає виконання певної дії. Розглядається 2 випадки: дія виконана і не виконана.

Приклад “покупка товарів в магазині”:

1. Дивимося на ціну товару.
2. Дістаємо гаманець.
3. Якщо грошей вистачає (умова) — беремо товар.
4. Якщо не вистачає – шукаємо інший.

Цикли виконують певні обчислення до тих пір, поки не відбудеться певна умова або для виконання n-числа дій. Все, що знаходиться всередині циклу, називається тілом.

Приклад “миття посуду”:

1. Взяти губку.
2. Взяти миючий.
3. Відкрити кран.
4. Вимити тарілку.
5. Витерти тарілку.
6. Переконатися, що немає брудних тарілок і закрити кран.
7. Якщо є брудні тарілки, повернутися до дії 4.

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

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

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

Як називається вид алгоритму

Поняття алгоритму належить не лише до фундаментальних наукових понять, а й до людських надбань. Будь-яку людську діяльність можна подати у вигляді алгоритмічного процесу. Автори огляду основних досягнень теорії алгоритмів [1] стверджують: “Алгоритмічні концепції відіграють у процесі навчання і виховання сучасної людини фундаментальну роль, порівнянну лише з роллю писемності”.

На одній із наукових конференцій (1984 р.) академік А. А. Самарський зобразив на слайді Інформатику красунею, яка мчить по неосяжному науковому океану на трьох китах. Імена тих китів: Модель, Алгоритм, Програма. Центральний кит – теорія алгоритмів, поєднавшись із математичною логікою, становлять теоретичний фундамент сучасних комп’ютерних наук.

Теорія алгоритмів подібна до математичної логіки. Із семантичними об’єктами, що несуть у собі зміст, математики, ще не звикли поводитися. Сенс терму або формули в математичній логіці “вказівний“: терм вказує на річ (тобто позначає), а формула – на факт. Сенс алгоритму “наказовий“: алгоритм повинен бути виконаний. Таким чином, теорія, що вивчає алгоритми, може трактуватися як свого роду лінгвістика наказових пропозицій. І, по-третє, теорія алгоритмів виникла на стику математики та інформатики. Тому вчені з обох боків “тягнули до себе ковдру“ при побудові теорії алгоритмів. Цю специфіку можна помітити, вивчаючи монографії та підручники з теорії алгоритмів. Залежно від того, ким вони написані – математиками чи знавцями інформатики, ми відчуваємо особливість змісту матеріалу, відображеного в них 5.

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

10.1. Поняття про алгоритм. Еволюція тлумачення та властивості

Поняття “ алгоритм “ – концептуальна основа різноманітних процесів у інформатиці. Саме наявність алгоритмів і забезпечує можливість автоматизації. Більше того, значною мірою теорія алгоритмів допомагає проникати математичним методам у всі сфери життя і науки, навіть біологію, лінгвістику, економіку аж до філософії природознавства [ 1-12].

Подальший розвиток математики затвердив ту думку, що вирішення будь-якої проблеми повинне бути алгоритмічним. Р. Декарт, Г. Ф. Лейбніц,

Саме в ті часи були поширені дві точки зору :

1. Усі проблеми є алгоритмічно розв’язними. Просто ще не існують знання для побудови алгоритму.

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

Перші фундаментальні праці з теорії алгоритмів були опубліковані незалежно в 1935-37 роках А. Тюрінгом, А. Черчем, С. Кліні, К. Гьоделем і Е. Постом.

Запропоноване А. Марковим поняття “нормального алгоритму“ є величезним внеском у світову науку, а А. Колмогорову належить пріоритет у визначенні загального поняття алгоритму та створення теорії складності конструктивних об’єктів.

У 1960-70-ті роки сформулювалися такі напрямки в теорії алгоритмів:

• Класична теорія алгоритмів (викладення завдання у термінах формальних мов, поняття задачі вирішення, введення класів складності, формулювання в 1965 році Едмондсом проблеми P=NP, відкриття класу NP-повних задач і його дослідження)[1].
• Теорія асимптотичного аналізу алгоритмів (поняття складності й трудомісткості алгоритму, критерії оцінки алгоритмів, методи одержання асимптотичних оцінок, зокрема для рекурсивних алгоритмів, асимптотичний аналіз трудомісткості або часу виконання), у розвиток якої зробили істотний внесок Кнут, Ахо, Хопкрофт, Ульман [2,4].
• Теорія практичного аналізу обчислювальних алгоритмів (одержання явних функцій трудомісткості, практичні критерії якості алгоритмів, методика вибору раціональних алгоритмів), основними роботами в цьому напрямку, мабуть, потрібно вважати фундаментальні праці [1,2].

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

Алгоритм – спосіб перетворення інформації за правилами, сформульованими певною мовою.

Будь-який алгоритм повинен мати такі основні властивості :

Визначеність (однозначність) – кожна команда алгоритму однозначно визначає дії виконавця і не припускає подвійного тлумачення.

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

Масовість – алгоритм може бути використаний для вирішення цілого класу однотипових завдань, для яких він створений.

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

Результативність (збіжність) – виконання алгоритму повинне закінчуватися результатом або інформацією про те, що не може бути отриманим результат.

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

10.2. Способи задання алгоритмів

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

Перший спосіб задання алгоритмів – це словесно-формульний (опис здійснюється у словесній формі з використанням математичних або інших формул). Він описує виконання дій алгоритму в певній послідовності за допомогою слів і пропозицій природної мови. Форма викладу довільна і встановлюється розробником. У математиці наявність формул дозволяє розв’язати задачу, навіть “не використовуючи слів“.

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

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

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

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

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

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

П’ятий спосіб, максимально наближений до комп’ютера, задання алгоритмів – це мови програмування. Справа в тому, що найчастіше у практиці виконавцем створеного людиною алгоритму є машина, і тому він повинен бути написаний мовою, зрозумілою для комп’ютера, тобто мовою програмування. Мова програмування – це знакова система, призначена для опису процесів вирішення завдань та їх реалізації на ЕОМ. Реалізація означає, що описи можуть бути введені в ЕОМ і однозначно нею зрозумілі. До мов програмування належать мови команд або машинні мови та мови високого рівня.

Блок-схеми алгоритму

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

Блок-схема – це спосіб представлення алгоритму в графічній формі, у вигляді геометричних фігур, сполучених між собою лініями (стрілками). Форма блока визначає тип дії, а текст всередині блоку дає детальне пояснення конкретної дії. Стрілки на лініях, що сполучають блоки схеми, вказують послідовність виконання команд, передбачених алгоритмом. Блок-схеми, за рахунок наочності спрощують створення ефективних алгоритмів, розуміння роботи вже створених, а як наслідок і їх оптимізацію. Існуючі стандарти на типи блоків дозволяють легко адаптувати алгоритми, створені у вигляді блок-схем до будь-яких існуючих на сьогоднішній день мов програмування.
Зображення блоків у алгоритмі, їх розміри, товщина ліній, кут нахилу ліній тощо, регламентуються Державним стандартом “Схеми алгоритмів, програм, даних і систем”, а саме : 19.701-90 (ISO 5807-85).
Блоки у блок-схемі з’єднуються лініями потоків. У кожен блок може входити не менше однієї лінії, з блоку ж (окрім логічного) може виходити лише одна лінія потоку . З логічного блоку завжди виходять дві лінії потоку: одна у випадку виконання умови, інша – при її невиконанні. Бажано, щоб лінії потоку не перетинались.
Алгоритм може бути детальним, або спрощеним (деякі зрозумілі блоки можуть не записуватись, інакше алгоритм збільшується в розмірі).
Основні види блок-схем :

– лінійні (нерозгалужені);
– розгалужені;
– циклічні;
– з підпрограмами;
– змішані.

Таблиця 1 – Опис основних символів схем алгоритмів

Блок, що зображує початок чи кінець алгоритму; всере- дині блока слід написати «початок» або «кінець».

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

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

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

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

Блок виклику підпрограми (функції, модуля), тобто допоміжних алгоритмів, які визначені автономно. Всередині блока записується, наприклад, ім’я функції, яка викликається, та список фактичних параметрів.

Символ, що використовується для зв’язку елемента схеми з коментарем.

Символ-з’єднувач застосовується для обриву лінії схеми та продовження її у другому місці.

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

– + – і меньше або дорівнює N;

– – – i завбільшки ніж N.

Інлді на схемах алгоритмів ‘+’ і ‘-‘ змінюють відповідно на ‘так’ або ‘ні'(рис. 1в).
Алгоритми циклічної структури (рис.1в). Цикл – це команда виконавцеві (компілятору) багаторазово повторити послідовність певних команд. При багатократному проходженні деяких ділянок алгоритму в процесі виконання алгоритм називається циклічним. Кількість проходжень циклу повинна бути повністю визначена алгоритмом розв’язання задачі, інакше виникає “зациклювання”, при якому процес розв’язання задачі не може завершитися. На рис.1в наведена схема алгоритмів обчислення добутка цілих значень в диапазоні більше ніж 2M-N+1 та завменьшки 2M. Алгоритми розв’язання задач циклічної структури можуть бути такими, що при однократному проході циклу деякі ділянки алгоритму виконуються неодноразово, тобто всередині циклу існують інші цикли. Алгоритми такої структури називаються алгоритмами з вкладеними циклами.

Рисунок 1 – Приклади простих алгоритмів

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

Елемент даних, що має фіксоване значення, яке під час розв’язання задачі не змінюється, називають константою. Поряд з константами широко використовуються змінні, тобто величини, що мають ідентифікатор і значення, яке може змінюватись залежно від використаних дій. У випадку, коли змінна х приймає значення, наприклад, в інтервалі від 0 до 1, тобто хє [0; 1], і змінюється з постійним кроком hx = 0,l. Її значення можна представити послідовністю із 11 чисел:

0; О,1; 0,2; 0,3; О,4; 0,5; 0,6; 0,7; 0,8; 0,9; 1.

Ця послідовність може зберігатися в пам’яті комп’ютера двома засобами:

– всі значення змінної х зберігаються по черзі в одній комірці пам’яті і обчислюються самим комп’ютером за заданим законом змінення кроку hx згідно з межами (х є [0; 1]);

– у пам’яті виділяється стільки комірок, скільки значень приймає змінна, тобто існує масив з 11 послідовних комірок, де для переходу від одного значення до іншого необхідно змінювати номер комірки.Таким чином, залежно від способу зберігання розрізняють прості змінні та змінні з індексами (масиви).

Масив – структура даних, що визначена ім`ям (ідентифікатором) і являє собою однорідну, фіксовану за розміром і упорядковану за номерами (індексами) сукупність елементів, У загальному випадку елементами масиву можуть бути будь-які однотипні дані. Найчастіше використовуються одновимірні масиви (вектори) та двовимірні масиви (матриці), наприклад: х4 (і = 0. n-1), n = 11 або y (i = 0. n-l, j = 0. m-l), п = 4, m = 6. Такі масиви розрізняють за кількістю індексів, яку потрібно вказувати для звернення до їх елементів.

Приклад 1. Обчислити площу трикутника(s), якщо відомі довжина кожної сторони(a, b, c) .

Рисунок 2 – Схема алгоритму прикладу 1

Приклвд 2. Обчислити функцію із заданими значеннями параметрів a, b, c і змінної x.

де значення a, b, c, x задається.

Рисунок 3 – Схема алгоритму прикладу 2

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

Рисунок 4 – Схема алгоритму прикладу 3

Алгоритм розв’язання складається з таких етапів:

– спочатку відбувається послідовне введення в пам’ять аргументів функції – елементів одновимірного масиву Хі (і = = 0. п-1), п = 7, тобто блок введення передбачає для цього використання циклу за індексною змінною і;

– для організації доступу до потрібного елемента масиву та виконання необхідних обчислень використовується новий цикл за параметром і;

– в середині циклу відбувається виведення поточних значень у та Хі;

– після завершення циклу за параметром і, тобто коли всі аргументи Хі вичерпано алгоритм закінчується.