Міністерство освіти І науки України
національний університет “Львівська політехніка”
Кафедра ЕОМ
Аналіз складності алгоритмів
Методичні вказівки
До лабораторної роботи № 2
з дисципліни
" AЛГОРИТМИ ТА МЕТОДИ ОБЧИСЛЕНЬ"
для студентів напряму
6.050102 “Комп’ютерна інженерія”
Затверджено
на засідання кафедри
“Електронні обчислювальні машини”.
Протокол № __ від ________ 2010 р.
р.
Львів – 2010
Методичні вказівки до комплексу лабораторних робіт з дисципліни "AЛГОРИТМИ ТА МЕТОДИ ОБЧИСЛЕНЬ" для підготовки студентів напряму 6.050102 “Комп’ютерна інженерія” / Укл. Т.А.Лисак – Львів: Видавництво НУ “Львівська політехніка”, 2010 – 18 с.
Укладач: Лисак Т.А., ст. викладач каф.ЕОМ
Відповідальний
за випуск: Мельник А.О., д-р техн. наук, проф.
Рецензенти: Мороз І.В., ст. викладач каф.ЕОМ
Юрчак І.Ю., доцент кафедри САПР, к.т.н.
1. Мета роботи
Оволодіти методикою аналізу складності основних алгоритмічних конструкцій. Навчитись обчислювати функцію трудомісткості. Ознайомитись з класифікацією алгоритмів на основі функції трудомісткості. Опанувати методику аналізу розроблених алгоритмів на предмет їх складності.
2. Теоретичні відомості
2.1. Поняття алгоритму
В старому трактуванні алгоритм - це точний набір інструкцій, що описують послідовність дій деякого виконавця для досягнення результату, рішення деякого завдання за кінцевий час. У зв'язку з розвитком паралельності в роботі комп'ютерів слово «послідовність» стали заміняти більше загальним словом «порядок». Це пов'язане з тим, що якісь дії алгоритму повинні бути виконані тільки один за одним, але якісь можуть бути й незалежними.
Поняття алгоритму необов'язково відноситься до комп'ютерних програм, так, наприклад, чітко описаний рецепт готування блюда також є алгоритмом, у такому випадку виконавцем є людина. Однак найчастіше як виконавець виступає комп'ютер.
Єдиного «правдивого» визначення поняття «алгоритм» немає.
«Алгоритм - це всяка система обчислень, що виконуються по строго визначеним правилам, які після певного числа кроків свідомо приводять до рішення поставленого завдання.» (А. Колмогоров)
«Алгоритм - це точне розпорядження, яке визначає обчислювальний процес, що йде від варійованих вихідних даних до шуканого результату.» (А. Марков)
«Алгоритм - строго детермінована послідовність дій, що описує процес перетворення об'єкта з початкового стану в кінцеве, записана за допомогою зрозумілих виконавцеві команд.» (М. Угринович)
«Алгоритм - це послідовність дій, спрямованих на одержання певного результату за кінцеве число кроків.» (ROXANstudio)
«Алгоритм є формалізована послідовність дій (подій). Алгоритм може бути записаний словами і зображений схематично. Практично будь-яка невипадкова повторювана дія піддається опису через алгоритм.» ([grey_olli])
«Алгоритм - однозначно, доступно і коротко описана послідовність процедур для відтворення процесу з обумовленим завданням алгоритму результатом при заданих початкових умовах. Універсальність (або спеціалізація) алгоритму визначається застосовністю і надійністю даного алгоритму для рішення нестандартних завдань.»