Алгоритм, властивості, параметри та характеристики складності алгоритму. Лабораторна робота з Алгоритми та методи обчислень. Робота № 517890

Перехід до торгівельного партнера Binance

Алгоритм, властивості, параметри та характеристики складності алгоритму

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Не вказано

Інформація про роботу

Рік:

2012

Тип роботи:

Лабораторна робота

Предмет:

Алгоритми та методи обчислень

Група:

КІ

Завантажити

Частина тексту файла (без зображень, графіків і формул):

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” Лабораторна робота №1 на тему: " Алгоритм, властивості, параметри та характеристики складності алгоритму". з дисципліни " Алгоритми та методи обчислень " Мета роботи: засвоїти основні поняття та визначення теорії алгоритмів, проаналізувати вплив параметрів алгоритму на характеристики складності алгоритму Теоретичні відомості : Алгоритм – це будь-який регулярний обчислювальний процес, що дозволяє за кінцеву кількість кроків розв’язувати задачі визначеного класу. Алгоритм – це процес послідовної побудови величин, які проходять в дискретному часі таким чином, що в пчатковий момент часу задається початкова скінчена система величин, а кожний наступний момент системи величин отримується за певним законом. Властивості алгоритму : дискретність масовість детермінованість елементарність спрямованість 3. Параметри : Система початкових даних Система проміжних результатів Система кінцевих результатів Правило початку Правило безпосереднього перероблення Правило закінчення Правило вводу Правило виводу Практична частина : 1. Знаходження НСД двох чисел методом перебору, починаючи з 1: 12 : 1 = 12 18 : 1 = 18 12 : 2 = 6 18 : 2 = 3 12 : 3 = 4 18 : 3 = 6 12 : 4 = 3 18 : 4 = 2 Часова складність: 8 2. Знаходження НСД двох чисел методом перебору, починаючи з меншого числа: 18 : 12 = 7 (4) 12 : 12 = 1 18 : 11 = 8 (4) 12 : 11 = 1 (1) 18 : 10 = 10 12 : 10 = 1 (2) 18 : 9 = 12 12 : 9 = 1 (3) 18 : 8 = 15 12 : 8 = 2 18 : 7 = 7 (4) 12 : 7 = 1 18 : 6 = 8 (4) 12 : 6 = 1 (1) 18 : 5 = 10 12 : 5 = 1 (2) 18 : 4 = 12 12 : 4 = 1 (3) 18 : 3 = 15 12 : 3 = 2 Часова складність: 5 3. Знаходження НСД двох чисел алгоритмом Евкліда: 60 : 8 = 7 (4) 8 : 4 = 2 Часова складність: 2 Висновок: дослідивши 3 методи знаходження НСД чисел в діапазоні від 1 до 100, я вияснив що середня часова складність цих алгоритмів така: для методу перебору, починаючи з 1 ≈ 36,2927; для методу перебору, починаючи з меншого числа ≈ 31,2367; для алгоритму Евкліда ≈ 2,4731. Результати дослідження середнього значення часової складності наведені згідно роботи програми обчислення НСД з перебором 10000 комбінацій чисел в діапазоні від 1 до 100.

Лабораторна робота Алгоритми та методи обчислень

rew1rew

19.11.2012 14:11-

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись