 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Поняття алгоритму
Алгоритмізація обчислювальних процесів
В реальному житті ми постійно зустрічаємося з алгоритмами. Інструкція по користуванню телефоном-автоматом, містить порядок дій необхідних для успішного телефонного дзвінка. Правила використання побутової техніки в лаконічній формі повідомляють нас, що треба робити в тій або іншій ситуації, визначаючи тим самим алгоритм нашої поведінки.
Слово «алгоритм» походить від algorithm - латинського написання імені аль-Хорезмі, під яким в середньовічній Європі знали математика Мухаммеда бен Мусу, що жив у 783-850 рр. У своїй книзі «Про індійський рахунок» він сформулював правила запису натуральних чисел за допомогою арабських цифр і правила дій над ними стовпчиком. Надалі алгоритмом стали називати точне розпорядження, що визначає послідовність дій, щоб забезпечити отримання необхідного результату з початкових даних.
Алгоритм — це кінцева послідовність однозначних розпоряджень, виконання яких дозволяє за допомогою кінцевого числа кроків отримати рішення задачі, що однозначно визначається початковими даними.
Прикладом алгоритму є класична історія про козу, капусту і вовка, яких необхідно переправити на інший берег річки за допомогою одного човна і перевізника.
Початковий стан завдання: все на лівому березі. Обмеження, що накладаються: не допустити, щоб хто-небудь кого-небудь з'їв під час перевезення.
Необхідно розробити алгоритм для проведення цієї операції.
Позначимо човен стрілкою, вовка, козу, капусту буквами – В, КЗ, КП.
1. Першою веземо козу. Інші варіанти неможливі, оскільки приводять до порушення умов.
2. Човен повертається назад, забирає капусту і везе на інший берег.
Лівий берег Правий берег
В,КЗ,КП
В,КП КЗ
В КЗ,КП
В,КЗ КП
КЗ В,КП
КЗ В,КЗ,КП
3. Капусту з козою залишати не можна, забираємо козу назад.
4. Залишаємо козу, забираємо вовка і веземо його до капусти.
5. Повертаємося за козою і перевозимо її на інший берег.
6. Завдання вирішене.
Алгоритм може бути призначений для виконання його людиною або автоматичним пристроєм. Створення алгоритму, нехай навіть найпростішого, - процес творчий. Він доступний виключно живим істотам, а довгий час вважалося, що тільки людині. Інша справа - реалізація вже наявного алгоритму. Її можна доручити суб'єкту або об'єкту, який не зобов'язаний вникати в суть справи, а можливо, і не здатний його зрозуміти. Такий суб'єкт або об'єкт прийнято називати формальним виконавцем. Прикладом формального виконавця може служити пральна машина-автомат, яка неухильно виконує програму прання, навіть якщо ви забули покласти в неї порошок. Людина теж може виступати в ролі формального виконавця, але в першу чергу формальними виконавцями є різні автоматичні пристрої, і комп'ютер зокрема.
Алгоритм є основою для розробки тих інструкцій, якими керується комп'ютер при роботі, але безпосередньо використовувати алгоритм він не зможе, оскільки алгоритм пишеться на природній людській мові, комп'ютеру не зрозумілій. Для того, щоб комп'ютер виконав алгоритм його перекладають мовою зрозумілою машині і такий алгоритм, записаний на машинній мові називається програмою.
Кожен алгоритм створюється з розрахунку на цілком конкретного виконавця. Ті дії, які може здійснювати виконавець, називаються його допустимими діями. Сукупність допустимих дій утворює систему команд виконавця. Алгоритм повинен містити тільки ті дії, які допустимі для даного виконавця.
Об'єкти, над якими виконавець може здійснювати дії, утворюють так зване середовище виконавця. Його можна представити у вигляді ряду: явище, процес, задача è модель è алгоритм è програма è комп'ютер è результат
2. Властивості алгоритмів
Дане вище визначення алгоритму не можна вважати строгим - не цілком ясно, що таке «точне розпорядження» або «послідовність дій, що забезпечує отримання необхідного результату». Тому зазвичай формулюють декілька загальних властивостей алгоритмів, що дозволяють відрізняти алгоритми від інших інструкцій.
Такими властивостями є:
• Дискретність - алгоритм повинен представляти процес рішення задачі як послідовне виконання простих (або раніше визначених) кроків. Кожна дія, передбачена алгоритмом, виконується тільки після того, як закінчилося виконання попередньої.
• Визначеність -кожне правило алгоритму повинне бути чітким, однозначним і не залишати місця для роздумів. Завдяки цій властивості виконання алгоритму носить механічний характер і не вимагає ніяких додаткових вказівок або відомостей про вирішуване завдання.
• Результативність - алгоритм повинен приводити до рішення задачі за кінцеву кількість кроків.
• Масовість - придатність алгоритму для вирішення певного класу завдань. Алгоритм рішення задачі розробляється в загальному вигляді для деякого класу завдань, що розрізняються тільки початковими даними. При цьому початкові дані можуть вибиратися з деякої області, яка називається областю застосовності алгоритму.
Поиск по сайту: