В інтернеті дуже часто зустрічається слово “алгоритм”, і для багатьох воно є загадкою. Розберемося на зрозумілих і простих прикладах з поняттям алгоритму, а також з його видами і застосуванням.
Алгоритм – це
Алгоритми оточують нас всюди. За їхніми принципами існує тваринний світ, люди, працюють комп’ютери і механізми. Деякі з них очевидні, інші ж приховані від очей (але це не означає, що їх немає).
Алгоритм в інформатиці – це послідовність дій, яка спрямована на досягнення остаточного розв’язання проблеми найбільш оптимальними і ефективними способами.
Існує версія, що термін алгоритм походить від імені стародавнього вченого Аль-Хорезмі, який написав трактат «Книга про додавання і віднімання».
Пізніше один з перекладачів на латинську мову неправильно перевів ім’я вченого і виніс його в назву книги — «Алгоритмії про рахунок Індійському». Так цей термін проник в європейські мови й закріпився в них.
Існують складні і легкі алгоритми. Для вирішення одних не потрібно зусиль, а для інших не вистачить і всієї потужності комп’ютерів.
Будь-які дії, що передбачають певну послідовність в житті тварин і людей, можна назвати алгоритмом (пошук їжі для тварини, похід в магазин за хлібом).
Алгоритм це..
Звичайно, тварина, яка шукає корм, не підозрює, що використовує алгоритми, але діє за певними правилами (інстинктами), щоб добути їжу:
- тварина шукає місце, де є корм (використовуючи нюх і інші органи чуття);
- потім здійснює дії, щоб дістатися до ласощі;
- при вдалому результаті з’їдає знайдене.
В інформатиці та програмуванні алгоритми використовуються для написання програм. Чим якісніше алгоритми, використовувані в програмі, тим краще вона працює.
Коли ви починаєте вивчати будь-яку мову програмування, то перше, що вам пояснюють — це принципи побудови алгоритму для майбутньої програми. Це такі блок-схеми, які наочно покажуть хід обробки даних і логіку обчислень. Без них спочатку буде дуже важко писати програми.
Види та типи алгоритмів
Лінійний алгоритм – це послідовне виконання інструкцій в суворій черговості їх розташування (приклад, «зробити бутерброд з сиром»).
Послідовність дій:
- взяти шматок хліба;
- відрізати шматок сиру;
- покласти його на хліб.
Розгалуження – послідовність дій відповідно до визначених умов (якщо одна умова, то виконується дія 1, якщо інший умова, то виконується дія 2);
Приклад: якщо йде сильний дощ, тоді візьми парасольку, а інакше брати парасольку не потрібно.
У більшості випадків слово “інакше” опускається, бо з контексту першої частини фрази вже зрозуміла подальша логіка.
Приклад: якщо хочете повідомити щось важливе, зателефонуйте (в такому випадку, очевидно, що якщо повідомлення неважливе, то дзвонити не потрібно).
Циклічні алгоритми – це послідовність дій, яку необхідно повторювати кілька разів для досягнення позитивного результату («перевірка груш на гнилі й не гнилі»).
Приклад: в одному ящику лежать груші, необхідно відібрати гнилі та хороші. Для цього здійснюємо наступні дії:
- взяти з ящика грушу;
- подивитися, гнила вона чи ні;
- якщо гнила, то викинути;
- якщо ні, покласти в інший ящик;
- повторити операцію до перебору всіх груш в ящику.
Іноді трапляються ситуації, коли цикл починає нескінченно повторюватися. Це називається зацикленням або нескінченний цикл.
Це відбувається в тому випадку, коли умова не може бути виконана, тоді цикл замикається в нескінченне повторення. Варто відзначити, що таких ситуацій слід уникати.
У мовах програмування існують різні види алгоритмів для вирішення певних завдань.
До основних видів, які повинен знати кожен початківець програміст, можна віднести ті, які використовують методи сортування і пошуку.
Все, що нас оточує побудовано саме на цих алгоритмах, вони вважаються простими для розуміння.
Де застосовують алгоритми
У математичних науках та інформатиці це пошук ефективного вирішення поставленого завдання з використанням інструментів і засобів.
Наприклад, навіть при вирішенні простої задачки (2*6) використовуються певні методи та інструменти для отримання правильного результату. Найцікавіше полягає в тому, що її можна вирішити декількома способами: використавши листок і ручку, порахувавши на комп’ютері або виконавши множення в розумі. Найбільш ефективний спосіб вирішення цього завдання і буде кращим алгоритмом в даному випадку.
Але такі прості приклади не дуже цікаві для любителів інформатики. Є набагато більш захоплюючі проблеми, хвилюючі уми багатьох програмістів, і над їх вирішенням б’ються вчені всього світу.
Завдання продавця (комівояжера)
Існують більш цікаві приклади для розуміння складності функціонування алгоритмів. Наприклад, задача комівояжера.
Дано: одному продавцеві необхідно відвідати чотири міста: наприклад, Київ, Берлін, Лондон, і Сан-Франциско. Продати там товар, а потім повернутися назад.
Рішення завдання виглядає простим. Спочатку з Києва поїхати в Берлін, потім відвідати Лондон, а потім відправитися в Сан-Франциско і повернутися в Київ.
Насправді це складний для комп’ютера алгоритм. У цих 4-х варіантах приховано 24 різних комбінацій подорожі для вирішення завдання. Комп’ютер вираховує відстань від одного міста до іншого, потім порівнює варіанти та видає рішення.
Але якщо збільшити кількість міст (наприклад, до 100), то комп’ютер не зможе вирішити це завдання, так як варіантів будуть мільйони, а на рішення знадобиться кілька століть.
Але найцікавішим є те, що, зрозумівши принцип вирішення подібного завдання, його можна поширити на всі подібні, що розширить знання в області інформатики та інших наук.
Машина Тюрінга – це основа для розуміння алгоритмів
Це абстрактна машина, яку придумав Алан Тюрінг, відомий британський вчений. Геніальність цього автомата полягає в наступному. Є якась стрічка, що складається з безлічі окремих (нескінченних) осередків, в яких містяться дані або біти (0 і 1). Є зчитувальний пристрій, що має доступ до стрічки.
У процесі руху пристрій забезпечений певними інструкціями, отримує доступ до осередків, зчитує інформацію і крокує далі. Але машина може змінювати свої дії, записати іншу інформацію або пересуватися то в одну, то в іншу сторону (на основі стека внутрішніх інструкцій).
В результаті досліджень таких машин Тюрінгом висунута гіпотеза про те, що алгоритм при знаходженні значень деякої функції, яка задана в області алфавіту, тільки тоді існує, коли дана функція обчислюється на машині Тюрінга.
Це аксіома, постулат, які неможливо довести математичним методом, так як алгоритм — це не точне математичне поняття.
Висновок
Вивчення алгоритмів – це важлива частина в розумінні роботи комп’ютерів. Це дозволяє дізнатися, як комп’ютер функціонує, як приймає, обробляє дані й видає необхідний результат.
Розуміння принципів роботи допоможе краще оволодіти комп’ютерними мовами, так як, володіючи принципами побудови і створення ефективних алгоритмів, можна вивчити будь-яку мову програмування (як алфавіт в іноземних мовах).
Вивчаєте, освоюйте, застосовуйте алгоритми. Сподіваємося, що наша стаття допомогла вам у цьому!
