§ 27. Визначення та властивості алгоритму
Основні теми параграфа:
♦ походження поняття «алгоритм»;
♦ виконавець алгоритму;
♦ алгоритмічний мову;
♦ властивості алгоритму;
♦ визначення алгоритму;
♦ формальне виконання алгоритму;
♦ що таке програма.
Поняття алгоритму так само фундаментально для інформатики. як і поняття інформації. Тому в ньому дуже важливо як слід розібратися.
Походження поняття «алгоритм»
Саме слово «алгоритм» походить від імені видатного математика середньовічного Сходу Мухаммеда аль-Хорезмі (787-850). Їм були запропоновані прийоми виконання арифметичних обчислень з багатозначними числами (вам вони добре знайомі зі шкільної математики). Пізніше в Європі ці прийоми назвали алгоритмами, від Algorithmi - латинського написання імені аль-Хорезмі. У наш час поняття алгоритму розуміється ширше, не обмежується тільки арифметичними обчисленнями.
З попереднього параграфа ви дізналися, що алгоритм - це послідовність команд управління будь-яким об'єктом. Ми назвали його об'єктом управління або виконавцем алгоритму. Їм може бути як технічний пристрій, так і жива істота.
Розглянемо виконавця-людини. Для нього можна сформулювати безліч алгоритмів, наприклад алгоритми арифметичних обчислень. З таким же успіхом можна назвати алгоритмами безліч різних інструкцій, розпорядчих послідовність дій людини для виконання будь-якої роботи. Наприклад, кулінарний рецепт - це алгоритм роботи кухаря з метою приготування страви; інструкція по збірці машинки з деталей дитячого конструктора - алгоритм для дитини; інструкція по використанню кухонного комбайна - алгоритм для домогосподарки.
Ви, напевно, ніколи не замислювалися над тим, яка кількість алгоритмів вам відомо. Життєвий досвід людини зростає зі збільшенням числа освоєних їм алгоритмів. Наприклад, щоб дитина навчилася купувати в магазині хліб, йому потрібно спочатку розповісти (а краще показати), як це робиться. Освоївши «алгоритм покупки хліба», він надалі буде успішно виконувати цю роботу.
Пошук виграшною тактики, а отже, і алгоритму нескладної гри - цікава і корисна задача. Розглянемо одну з таких ігор, яка називається грою БАШЕЄВ.
Грають двоє. Перед ними 21 предмет, припустимо, камені (також може бути 11, 16, 26 і т. Д.). Гравці беруть каміння по черзі. За один хід можна взяти 1, 2, 3, 4 каменю. Програє той, хто забирає останній камінь.
Є виграшна тактика для гравця, що бере камені другим. Вона полягає в тому, щоб брати таку кількість каменів, яке доповнює число каменів, узятих суперником на попередньому ході, до п'яти. Цей алгоритм можна описати у вигляді послідовності команд:
алг Гра Баше
нач
1. Надати хід супернику.
2. Взяти стільки каменів, щоб в сумі з попереднім ходом суперника вийшло 5.
3. Якщо залишився один камінь, то оголосити про свій виграш, інакше повернутися до виконання команди 1.
кін
Гравець, строго наступний цим алгоритмом, буде завжди вигравати, навіть якщо він не розуміє, чому так відбувається.
У наведеному прикладі використовується символіка навчального алгоритмічні мови (АЯ).
З прикладу видно, що під час запису алгоритму на АЯ на початку пишеться заголовок, що починається зі службового слова алг (скорочена слово «алгоритм»). Потім вказується назва алгоритму, яке укладач алгоритму придумує сам. Наступна частина називається тілом алгоритму. Вона починається зі службового слова поч (початок) і закінчується словом кін (кінець). Тіло алгоритму являє собою послідовність команд для виконавця.
Тут і надалі службові слова в алгоритмах на алгоритмічній мові будуть записуватися жирним шрифтом. У мовах програмування (як і в АЯ) службовими називаються слова, які завжди вживаються в одному і тому ж сенсі.
Процес рішення задачі повинен бути розбитий на послідовність окремо виконуваних кроків.
Це властивість алгоритму називається дискретністю.
Всякий алгоритм складається в розрахунку на конкретного виконавця з урахуванням його можливостей. Для того щоб алгоритм був виконаємо, не можна включати в нього команди, які виконавець не в змозі виконати. Не можна кухареві доручати роботу токаря, яка б докладна інструкція йому ні давалася. У кожного виконавця є свій перелік команд, які він може виконати. Такий перелік називається системою команд виконавця алгоритмів (СКІ).
Алгоритм, складений для конкретного виконавця, повинен включати тільки ті команди, які входять в систему команд виконавця.
Це властивість алгоритму називається зрозумілістю.
Кожна команда алгоритму повинна визначати однозначне дію виконавця.
Це властивість алгоритму називається точністю.
Алгоритм не повинен бути розрахований на прийняття будь-яких самостійних рішень виконавцем, не передбачених укладачем алгоритму.
Ще одна важлива вимога, що пред'являється до алгоритму - це властивість кінцівки (іноді кажуть - результативності) алгоритму. Це означає що:
Виконання алгоритму має завершитися за кінцеве число кроків.
Для успішного виконання будь-якої роботи мало мати її алгоритм. Завжди потрібні ще якісь вихідні дані, з якими буде працювати виконавець (продукти для приготування страви, деталі для збору технічного пристрою і т. П.). Виконавцю, вирішального математичну задачу, потрібно вихідна числова інформація. Завдання завжди формулюється так: дана вихідна інформація, потрібно отримати якийсь результат. В математиці ви звикли в такому вигляді записувати умови задач. наприклад:
Дано: катети прямокутного
трикутника а = 3 см; b = 4 см.
Знайти: гіпотенузу з
Алгоритм рішення цієї задачі можна представити в такому вигляді:
алг Гіпотенуза
нач
1, Звести а в квадрат.
2. Звести b в квадрат.
3. Скласти результати дій 1 і 2.
4. Обчислити квадратний корінь результату дії 3 і прийняти його за значення с.
кін.
Кожну з цих команд може виконати будь-яка людина, що знає основи математики, отже, вони входять в його систему команд.
Тільки маючи повний набір даних, можна точно вирішити задачу.
У завданнях управління фізичними об'єктами (автомобіль, літак, верстат і т. П.) Вихідними даними є інформація про стан об'єкта управління, про обстановку, його навколишнього.
Узагальнюючи все сказане, сформулюємо визначення алгоритму.
Алгоритм - зрозуміле і точне розпорядження виконавцю виконати кінцеву послідовність команд, що приводить від вихідних даних до шуканого результату.
Формальне виконання алгоритму
Якщо алгоритм має перерахованими вище властивостями, то робота по ньому буде проводитися виконавцем
формально (тобто без всяких елементів творчості з його боку). На цьому заснована робота програмно керованих виконавців-автоматів, наприклад промислових роботів. Робот-маніпулятор може виконувати роботу токаря, якщо він вміє виконувати всі операції токаря (включати верстат, закріплювати різець, переміщати різець, заміряти виріб). Від виконавця не потрібно розуміння сутності алгоритму, він повинен лише точно виконувати команди, не порушуючи їх послідовності.
Що таке програма
А що таке програма? Чи відрізняється чомусь програма від алгоритму?
Програма - це алгоритм, записаний на мові виконавця.
Інакше можна сказати так; алгоритм і програма не відрізняються за змістом, але можуть відрізнятися за формою.
Коротко про головне
Слово «алгоритм» походить від імені Мухаммеда аль-Хорезмі, першим запропонував прийоми виконання арифметичних операцій з багатозначними числами.
Виконавець алгоритму - це той об'єкт, для управління якими складено алгоритм.
Процес рішення задачі повинен бути розбитий на послідовність окремих кроків (властивість дискретності алгоритму).
Система команд виконавця (СКІ) - це вся сукупність команд, які виконавець вміє виконувати (розуміє). Алгоритм можна будувати тільки з команд, що входять в СКІ виконавця (властивість зрозумілості).
Кожна команда алгоритму управління визначає однозначне дію виконавця (властивість точності).
Виконання алгоритму повинно приводити до результату за кінцеве число кроків (властивість кінцівки).
Для успішного виконання роботи, виконання завдання необхідно повідомити (передати) виконавцю повний набір вихідних даних.
Виконання алгоритму виконавцем проводиться формально.
Програма від алгоритму може відрізнятися за формою, але не за змістом. Програма - це алгоритм, представлений на мові виконавця.
Запитання і завдання
1. Що таке алгоритм? Звідки сталася це слово?
2. Що таке виконавець алгоритму?
3. Що таке система команд виконавця?
4. У чому полягають основні властивості алгоритму?
5. Назвіть виконавців наступних видів роботи: прибирання сміття на подвір'ї; перевезення пасажирів; видача заробітної плати; прийом іспитів; складання іспитів; навчання дітей в школі. Спробуйте сформулювати СКІ для кожного з цих виконавців.
6. Визначте повний набір даних для вирішення наступних завдань обробки інформації:
• обчислення вартості покупок в магазині;
• обчислення суми здачі від даних вами продавцеві грошей;
• визначення часу показу по телевізору цікавить вас фільму;
• обчислення площі трикутника;
• визначення часу падіння цегли з даху будинку;
• визначення місячної плати за витрату електроенергії;
• переклад українського тексту на італійську мову;
• переклад італійського тексту на українську мову.
7. Спробуйте сформулювати алгоритми обробки інформації для завдань з п. 6, якщо виконавцем є ви самі. Які команди при цьому ви повинні вміти виконувати?
І. Семакін, Л. заставного, С. Русаков, Л. Шестакова, Інформатика, 9 клас
Відіслано Новомосковсктелямі з інтернет-сайтів
Якщо у вас є виправлення або пропозиції до даного уроку, напишіть нам.
Якщо ви хочете побачити інші коригування та побажання до уроків, дивіться тут - Освітній форум.