оритмів і вивченню алгоритмічних моделей, до самостійного вивчення алгоритмів з метою їх порівняння по робочих характеристик (числу дій, витраті пам'яті), а також їх оптимізації. Виникло важливий напрям у теорії алгоритмів - складність алгоритмів і обчислень. Почала складатися так звана метрична теорія алгоритмів, основним змістом якої є класифікація завдань за класами складності. Самі алгоритми стали об'єктом точного дослідження як і ті об'єкти, для роботи з якими вони призначені.
1. АЛГОРИТМИ
.1 Поняття алгоритму
Слово Алгоритм походить від algorithmi - латинського написання імені аль - Хорезмі, під яким у середньовічній Європі знали видатного математика з Хорезму (місто в сучасному Узбекистані) Мухаммеда бен Мусу, який жив у 783- 850 рр.
У своїй книзі Про індійський рахунку він сформулював правила запису натуральних чисел за допомогою арабських цифр і правила дій над ними стовпчиком. Надалі алгоритмом стали називати точний припис, що визначає послідовність дій, що забезпечує отримання необхідного результату з вихідних даних.
Алгоритм може бути призначений для виконання його людиною або автоматичним пристроєм. Створення алгоритму, нехай навіть самого простого, - процес творчий. Він доступний виключно живим істотам, а довгий час вважалося, що тільки людині. Інша справа - реалізація вже наявного алгоритму. Її можна доручити суб'єкту чи об'єкту, який не зобов'язаний вникати в суть справи, а можливо, і не здатний його зрозуміти. Такий суб'єкт або об'єкт прийнято називати формальним виконавцем. Прикладом формального виконавця може служити пральна машина-автомат, яка неухильно виконує запропоновані їй дії, навіть якщо ви забули покласти в неї порошок.
Людина теж може виступати в ролі формального виконавця, але в першу чергу формальними виконавцями є різні автоматичні пристрої, і комп'ютер в тому числі. Кожен алгоритм створюється з розрахунку на цілком конкретного виконавця. Ті дії, які може вчиняти виконавець, називаються його допустимими діями. Сукупність допустимих дій утворює систему команд виконавця. Алгоритм повинен містити тільки ті дії, які допустимі для даного виконавця.
Об'єкти, над якими виконавець може вчиняти дії, утворюють так звану середу виконавця. Для алгоритмів, зустрічаються в математиці, середовищем того чи іншого виконавця можуть бути числа різної природи - натуральні, дійсні і т.п., літери, літерні вирази, рівняння, тотожності і т.п.
Дане вище визначення алгоритму не можна вважати суворим - не цілком ясно, що таке точне розпорядження або послідовність дій, що забезпечує отримання необхідного результату raquo ;. Тому зазвичай формулюють кілька загальних властивостей алгоритмів, що дозволяють відрізняти алгоритми від інших інструкцій.
Такими властивостями є:
Дискретність (переривчастість, роздільність) - алгоритм повинен представляти процес вирішення завдання як послідовне виконання простих (або раніше визначених) кроків. Кожна дія, передбачене алгоритмом, виконується тільки після того, як закінчилося виконання попереднього.
Визначеність - кожне правило алгоритму має бути чітким, однозначним і не залишати місця для сваволі. Завдяки цій властивості виконання алгоритму носить механічний характер і не вимагає ніяких додаткових вказівок або відомостей про розв'язуваної задачі.
Результативність (кінцівка) - алгоритм повинен призводити до вирішення завдання за кінцеве число кроків.
Масовість - алгоритм вирішення задачі розробляється в загальному вигляді, тобто, він повинен бути застосовний для деякого класу задач, що розрізняються тільки вихідними даними. При цьому вихідні дані можуть вибиратися з деякої області, яка називається областю застосовності алгоритму.
1.2 Властивості алгоритмів
На підставі цих властивостей іноді дається визначення алгоритму, наприклад:
Алгоритм - це послідовність математичних, логічних або разом узятих операцій, які відрізняються детерминированностью, масовістю, спрямованістю і призводить до вирішення всіх задач даного класу за кінцеве число кроків. Таке трактування поняття алгоритм є неповною і неточною. По-перше, невірно пов'язувати алгоритм з рішенням якої-небудь задачі. Алгоритм взагалі може не вирішувати ніякої завдання. По-друге, поняття масовість відноситься не до алгоритмів як до таких, а до математичних методів в цілому. Рішення поставлених практикою задач математичними методами засноване на абстрагуванні - ми виділяємо ряд істотних ознак, характерних для деякого кола явищ, і будуємо на підставі цих ознак математичну модель, відкидаючи несуттєві ознаки кожного ...
