Головна Головна -> Інше українською -> Інформатика, комп'ютери, програмування -> Поняття алгоритму

Поняття алгоритму

Назва:
Поняття алгоритму
Тип:
Інше
Мова:
Українська
Розмiр:
5,86 KB
Завантажень:
351
Оцінка:
 
поточна оцінка 5.0


Скачати цю роботу безкоштовно
Пролистати роботу: 1  2  3  4 
Поняття алгоритму
 
 
 
 
 
Поняття алгоритму   
Інтуїтивно алгоритм визначається як "послідовність чітких недвозначних інструкцій, які зрозумілі виконавцеві і які призводять до певного результату за скінченний час". Точне визначення алгоритму дати неможливо, але можна сформулювати ряд інтуїтивних вимог до алгоритмів. Вважається, що послідовність інструкцій є алгоритмом, якщо вона задовольняє таким вимогам:
дискретність: алгоритм являє собою послідовність кроків, на кожному з яких виконується та чи інша інструкція; кожна наступна інструкція виконується після того, як завершиться виконання попередньої;
елементарність кроків: кожна інструкція є елементарною для виконавця і не вимагає від нього ніякої винахідливості;
локальність кроків: процес виконання інструкції не вимагає повернення до попередніх інструкцій або звертання до наступних;
детермінованість: після завершення чергового кроку завжди відомо, що робити на наступному кроці;
результативність: повинно бути визначено, що слід вважати результатом роботи алгоритму;
скінченність: результат повинен досягатися за скінченну кількість кроків;
масовість: алгоритм повинен бути призначений для вирішення не однієї конкретної задачі, а цілого класу однотипних задач.   
Будемо називати деяку функцію y = f(x1,…,xn) ефективно обчислюваною, або просто обчислюваною, якщо існує будь-яка механічна процедура, яка дозволяє знайти значення y, якщо відомі значення x1,…,xn. Якщо функція визначена не для всіх значень x1,…,xn, вона називається частково обчислюваною.
   Отже, будь-який алгоритм, і, відповідно, будь-яку програму ми розглядаємо як реалізацію деякого інформаційного перетворення, тобто як реалізацію частково обчислюваної функції, аргументами якої є вхідні дані алгоритму, а значенням - результат роботи алгоритму.
   Слова "алгоритм" і "механічна процедура" ми розглядаємо як синоніми. Ми кажемо, що будь-яка механічна процедура реалізує певний алгоритм, і навпаки - якщо послідовність інструкцій є алгоритмом, то повинен існувати якийсь механізм, здатний виконати цю послідовність інструкцій.    
Основними мірами обчислювальною складності алгоритмів є:
часова складність, яка характеризує час, необхідний для виконання алгоритму на даній машині; цей час, як правило, визначається кількістю операцій, які потрібно виконати для реалізації алгоритму;
ємнісна складність, яка характеризує пам'ять, необхідну для виконання алгоритму.Часова та ємнісна складність тісно пов'язані між собою. Обидві є функціями від розміру вхідних даних. Надалі обмежимося тільки аналізом часової складності.   
Складність алгоритму описується функцією f(n), де n - розмір вхідних даних. Важливе теоретичне і практичне значення має класифікація алгоритмів, яка бере до увагу швидкість зростання цієї функції.
   Визначення.
Кажуть, що f(n) = O (g(n)), якщо існує така константа с > 0, що для будь-якого n виконується нерівність: |f(n)| Ј с |g(n)|.Оскільки і розмір вхідних даних, і кількість операцій є величинами невід'ємними (а фактично - додатніми), модулі можна опустити.   
Виділяють такі основні класи алгоритмів:
логарифмічні: f(n) = O (log2n);
лінійні: f(n) = O (n);
поліноміальні: f(n) = O (nm); тут m - натуральне число, більше від одиниці; при m = 1 алгоритм є лінійним;
експоненційні: f(n) = O (an); a - натуральне число, більше від одиниці.   
Для однієї й тієї ж задачі можуть існувати алгоритми різної складності. Часто буває і так, що більш повільний алгоритм працює завжди, а більш швидкий - лише за певних умов.    
Приклад.
Часто зустрічається задача пошуку в масиві, яка неформально формулюється таким чином: в заданій послідовності чисел знайти елемент з певним значенням.
   В загальному випадку застосовується алгоритм послідовного пошуку, який полягає в послідовному перегляді всіх елементів і порівнянні їх з потрібним значенням.

Завантажити цю роботу безкоштовно
Пролистати роботу: 1  2  3  4 



Інше на тему: Поняття алгоритму

BR.com.ua © 1999-2017 | Реклама на сайті | Умови використання | Зворотній зв'язок