Поняття алгоритму
Давайте пригадаємо поняття алгоритму, знайоме вам із курсу інформатики 2–4 класів.
Алгоритм — це скінченна послідовність указівок на виконання дій, спрямованих на розв’язування задачі.
 |
Рис. 1 |
Слово «алгоритм» походить від імені арабського математика Аль-Хорезмі (800–847 рр.). Абу Абдулла Абу Джафар Мухаммад ібн Муса аль-Хорезмі (рис.1) сформулював правила чотирьох арифметичних дій над багатозначними числами. Латиною ім’я автора європейці писали як «Algorithmi», і спочатку алгоритмами називали саме ці чотири правила виконання арифметичних дій.
З часом алгоритмами почали називати способи розв’язування найрізноманітніших задач.
У повсякденному житті людина стикається з алгоритмами, що визначають послідовність дій різної природи. Із курсу математики вам відомі алгоритми виконання арифметичних операцій над багатоцифровими числами, алгоритми знаходження коренів лінійних рівнянь та інше.
1) Рецепти приготування страв, порядок підготовки автоматичного пристрою до використання та інші послідовності розпоряджень, виконання яких дає змогу досягти поставленої мети, є алгоритмами.
Для багатьох ігор існують алгоритми виграшу, якщо результат гри залежить не від випадкового збігу обставин, а від кмітливості гравця й попередніх розрахунків.
2) Гра Баше. Є 11 предметів. За один хід гравець може взяти 1, 2, 3 предмети. Програє той, кому дістанеться останній предмет. Алгоритм виграшу для першого гравця:
1-й хід: узяти два предмети.
2-й хід і далі: брати стільки предметів, щоб кількість предметів, узятих разом із суперником за черговий хід, у сумі складала 4.
Уміння складати алгоритми є дуже важливим для людини будь-якої професії.
Властивості алгоритмів
Алгоритм складається з окремих кроків, які потрібно виконати в певному порядку. Якщо порушити порядок виконання кроків або пропустити якийсь крок, то алгоритм не буде виконаний до кінця або призведе до неправильного результату.
3) Розглянемо алгоритм відкривання дверей.
- Дістань ключ.
- Встав ключ у замкову шпарину.
- Двічі поверни ключ за годинниковою стрілкою.
- Вийми ключ.
Чи відкриємо ми двері, якщо поміняти місцями вказівки 2 і 3?
Алгоритм має певні властивості. Щоб алгоритм виконав своє призначення, його
необхідно будувати за певними правилами (рис. 2).
 |
Рис. 2 |
Дискретність означає, що алгоритм повинен складатися з окремих кроків, кожний з яких має завершуватися.
Визначеність означає однозначність тлумачення правил виконання кроків і порядку їх виконання. Алгоритм не повинен містити команди, які можуть сприйматися виконавцем неоднозначно.
Виконуваність означає, що алгоритм, призначений для певного виконавця, може містити лише ті команди, які виконавець здатний виконати. Так, алгоритм для виконавця Першокласник не може містити команду «Побудуй бісектрису даного кута», хоча така команда може бути в алгоритмі, призначеному для виконавця Восьмикласник.
Скінченність — обов’язкова виконуваність алгоритму. Алгоритм має складатися зі скінченної кількості кроків, кожен з яких потребує для свого виконання скінченного проміжку часу.
4) Наведена послідовність команд є нескінченною.
- Візьміть число 2.
- Помножте задане число на 10.
- Додайте до результату 5.
- Якщо одержано додатне число, то перейдіть до команди 3, якщо ні, то припиніть виконання алгоритму.
Результативність означає, що після виконання послідовності вказівок алгоритму має бути отримано конкретний результат.
Наприклад, послідовність вказівок «налий води; увімкни плитку; вимкни плитку» не є результативною, якщо потрібно було нагріти воду.
Формальність означає, що будь-який виконавець, здатний сприймати й виконувати вказівки алгоритму (навіть не розуміючи його змісту), може виконати завдання за заданим алгоритмом. Як відомо, автоматизовані пристрої правильно розв’язують багато задач за заданими їм алгоритмами, хоча змісту задач вони, безумовно, розуміти не можуть.
Немає коментарів:
Дописати коментар