Алгоритм: поняття, властивості, структура та види

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

• Історія появи алгоритмів
• Взаємодія алгоритму з людиною і машиною
• Що таке алгоритм?
• Основні властивості алгоритму
• Циклічний алгоритм
• Лінійні типи алгоритмів
• Алгоритм розгалуження
• Допоміжний алгоритм
• Терміни, що зустрічаються в алгоритмах
• Структура алгоритму
• Графічний варіант побудови алгоритму
• Геометричні фігури, що відповідають за різні дії в алгоритмі
• Поняття алгоритму інформатики
• Вивід

У цій статті ми розберемо основні поняття алгоритму.

Історія появи алгоритмів

Алгоритм – поняття, що з’явилися в XII столітті. Саме слово «» алгоритм «» походить від латинської інтерпретації імені відомого математика середнього сходу Мухаммеда аль Хорезмі, який написав книгу «» Про індійський рахунок «». У цій книзі описано, як правильно записувати натуральні числа, використовуючи арабські цифри, і наведено опис алгоритму дій стовпчиком над такими числами.

У XII столітті книга «Про індійський рахунок» була перекладена латинською мовою, тоді і з’явилося це визначення.

Взаємодія алгоритму з людиною і машиною

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

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

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

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

Що таке алгоритм?

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

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

Взагалі, алгоритм має безліч визначень, кілька вчених характеризують його по-різному.

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

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

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

Основні властивості алгоритму

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

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

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

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

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

Існують різні типи алгоритмів, але є три основних.

Циклічний алгоритм

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

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

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

Найпростіший вид циклу – це фіксований.

Існує два види циклічних алгоритмів:

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

Лінійні типи алгоритмів

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

Алгоритм розгалуження

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

Приклад. Питання: “” Йде дощ? ” Варіанти відповідей: «Так» або «Ні». Якщо «так» «- відкрийте парасольку, якщо» ні «» – покладіть парасолю в сумку.

Допоміжний алгоритм

Допоміжний алгоритм можна використовувати в інших алгоритмах, вказавши лише його назву.

Терміни, що зустрічаються в алгоритмах

Умова знаходиться між словами «» якщо «» і «» тоді «».

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

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

Алгоритмічний процес – вирішення завдання за алгоритмом із застосуванням певних даних.

Структура алгоритму

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

Який із способів буде використаний, залежить від декількох факторів: від складності завдання, від того, наскільки потрібно деталізувати процес вирішення завдання тощо.

Графічний варіант побудови алгоритму

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

Графічні схеми зображуються не як попало. Для того щоб їх могла зрозуміти будь-яка людина застосовуються найчастіше блок-схеми і структурограми Нассі-Шнейдермана.

Також блок-схеми зображуються відповідно до GOST-19701-90 і GOST-19.003-80.
Графічні фігури, що застосовуються в алгоритмі, поділяються на:

• Основні. Основні зображення застосовуються для визначення дій, потрібних для обробки даних під час вирішення завдання.
• Допоміжні. Допоміжні зображення потрібні для позначення окремих, не найважливіших, елементів вирішення завдання.

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

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

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

Як правильно побудувати алгоритм?

Структура алгоритму, як було сказано вище, повинна будуватися за ГОСТ, інакше вона не буде зрозуміла і доступна оточуючим.

Загальна методика запису включає в себе такі пункти:

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

Кожен алгоритм має чітко позначати початок і кінець.

У алгоритмів повинні бути чітко і ясно описані всі дані, як вхідні, так і вихідні.

При складанні алгоритму слід зазначити дії, які дозволять робити потрібні для вирішення завдання дії над обраними даними. Зразковий вид алгоритму:

Правильна побудова схеми істотно полегшить обчислення алгоритмів.

Геометричні фігури, що відповідають за різні дії в алгоритмі

Горизонтально розташований овал – початок і кінець (знак завершення).

Горизонтально розташований прямокутник – обчислення або інші дії (знак процесу).

Горизонтально розташований паралелограм – введення або виведення (знак даних).

Горизонтально розташований ромб – перевірка умови (знак рішення).

Витягнутий, горизонтально розташований шестикутник – модифікація (знак підготовки).

Моделі алгоритмів представлені нижче на малюнку.

Формульно-словесний варіант побудови алгоритму.

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

Поняття алгоритму інформатики

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

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

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

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

Вивід

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

Що таке комп’ютерні алгоритми та як вони працюють?

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

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

Що таке алгоритм?

Слово «алгоритм» має етимологію, подібну до «алгебри», за винятком того, що це стосується самого арабського математика, аль-Хварізмі (просто цікавий шматок). Алгоритм для непрограмістів серед нас – це набір інструкцій, які беруть вхід A і забезпечують вихід B, який певним чином змінює задіяні дані. Алгоритми мають широке застосування. У математиці вони можуть допомогти обчислити функції з точок у наборі даних, серед набагато більш досконалих речей. Окрім їх використання в самому програмуванні, вони відіграють головну роль у таких справах, як стиснення файлів та шифрування даних.

Основний набір інструкцій

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

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

Графіки

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

Цей графік ми можемо виразити як зв’язок між усіма його точками. Для того, щоб відтворити це зображення, ми можемо дати набір інструкцій комусь іншому.

Ми можемо представити це як ряд точок, і інформація буде відповідати стандартній формі графіку = <(x1, y1), (x2, y2), …, (xn, yn)>.

Досить легко побудувати графік кожної точки, одну за одною, і зв’язати їх із попередньою точкою. Однак уявіть собі графік з тисячою точками або декількома відрізками, які рухаються в будь-який бік. Цей список містив би багато даних, правда? І тоді необхідність зв’язувати кожного, по одному, може бути болем.

Ще одне, що ми можемо зробити, це вказати початкову точку, нахил лінії між нею та наступною точкою, та вказати, де очікувати наступну точку, використовуючи стандартну форму графіку = <(starting point>, [m1, x1, h1],…, [mn, xn, hn]>. Тут змінна «m» представляє нахил лінії, «x» – напрямок, в якому потрібно рахувати (будь то x чи y), а «h» – вам вказати, скільки потрібно врахувати у вказаному напрямку. Ви також можете пам’ятати будувати точку після кожного руху.

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

Що робити, якщо окремі точки насправді не мають значення, а має значення лише сам графік? Ми можемо консолідувати ці три останні розділи так:

Це трохи скорочує речі від того, де вони були раніше.

Спробуймо зробити це по-іншому.

y = 0, 0≤x≤3
x = 0, 0≤y≤3
y = x, 3≤x≤5
y = 2,5x-7,5, 5≤x≤7
y = -3x + 29, 7≤x≤8
y = -3x + 29, 8≤x≤9
y = -3x + 29,9≤x≤10

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

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

Ще один важливий момент, на який слід звернути увагу, полягає в тому, що кожен метод покладається на ключ. Кожен набір інструкцій марний, якщо ви не знаєте, що з ними робити. Якщо ви не знаєте, що ви повинні побудувати кожну точку та з’єднати крапки, перший набір точок нічого не означає. Якщо ви не знаєте, що означає кожна змінна у другому методі, ви не будете знати, як їх застосовувати, подібно до ключа до шифру. Цей ключ також є невід’ємною частиною використання алгоритмів, і часто цей ключ можна знайти в спільноті або за допомогою “стандарту”.

Стиснення файлів

Завантажуючи файл .zip, ви витягуєте вміст, щоб можна було використовувати все, що знаходиться всередині нього. На сьогоднішній день більшість операційних систем можуть занурюватися у .zip-файли, як звичайні папки, роблячи все у фоновому режимі. На моїй машині Windows 95 більше десяти років тому мені довелося витягувати все вручну, перш ніж я міг побачити щось більше, ніж імена файлів всередині. Це тому, що те, що зберігалося на диску як .zip-файл, не було придатним для використання. Подумайте про висувний диван. Коли ви хочете використовувати його як ліжко, вам доведеться зняти подушки і розкласти, що займає більше місця. Коли він вам не потрібен або ви хочете його транспортувати, ви можете скласти його назад.

Алгоритми стиснення налаштовані та оптимізовані спеціально для типів файлів, на які вони призначені. Наприклад, аудіоформати використовують різні способи зберігання даних, які при декодуванні аудіокодеком дають звуковий файл, схожий на вихідну форму сигналу. Щоб отримати додаткову інформацію про ці відмінності, перегляньте нашу попередню статтю, Які відмінності між усіма цими аудіоформатами? Аудіоформати без втрат та файли .zip мають одне спільне: вони обидва видають вихідні дані в точному вигляді після процесу декомпресії. Втрачені аудіокодеки використовують інші засоби, щоб заощадити місце на диску, наприклад, обрізання частот, які не чутні людськими вухами, і згладжування форми сигналу в розділах, щоб позбутися деяких деталей. Зрештою, хоча ми, можливо, не зможемо почути різницю між MP3 і CD-композицією, у першій, безумовно, дефіцит інформації.

Шифрування даних

Алгоритми також використовуються при захисті даних або ліній зв’язку. Замість того, щоб зберігати дані так, щоб вони зайняли менше місця на диску, вони зберігаються таким чином, що не виявляються іншими програмами. Якщо хтось викраде ваш жорсткий диск і почне його сканувати, він може забрати дані, навіть коли ви видаляєте файли, оскільки самі дані все ще є, хоча місце пересилання на нього вже немає. Коли дані шифруються, все, що зберігається, не схоже на те, що воно є. Зазвичай це виглядає випадковим, ніби фрагментація накопичилася з часом. Ви також можете зберігати дані та зробити їх такими, що відображаються як файл іншого типу. Файли зображень та музичні файли добре підходять для цього, оскільки, наприклад, вони можуть бути досить великими, не викликаючи підозр. Все це робиться за допомогою математичних алгоритмів, які беруть якийсь вхід і перетворюють його в інший, дуже конкретний тип виводу. Щоб отримати докладнішу інформацію про те, як працює шифрування, перегляньте статтю HTG пояснює: Що таке шифрування та як воно працює?

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