Міністерство освіти і науки України Національний університет „Львівська політехніка” Кафедра ЕОМ ЛАБОРАТОРНА РОБОТА №1 з дисципліни: “Алгоритми” Львів 2008 Тема: Порівняння складності арифметичних операцій в римській та десятковій системах числення Мета роботи : Засвоєння основних визначень. Порівняння часової складності алгоритмів. I. Теоретична частина. Алгоритм – точний припис, який задає обчислювальний процес, що починається з довільних початкових даних і спрямований на отримання результату, який повністю визначається цим початковим даним. Властивості алгоритму: Дискретність – алгоритм проводиться за послідовністю кроків. Детермінованість – результат обчислення на кожному кроці точно відповідає вхідним умовам, даним і функції перетворення на цьому кроці Елементарність – простота і локальність кроків алгоритму. Масовість – один і той же алгоритм дозволяє розв’язувати множину задач які відрізняються набором вхідних даних. Параметри алгоритму: Правило початку. Правило виводу даних. Система вхідних даних. Правило безпосереднього перероблення. Система проміжних результатів. Правило виводу результатів. Система результатів. Правило закінчення. II. Практична частина Виконати арифметичну операцію в римській та десятковій системах числення. Завдання №4 LVII – IX 56 – 9 Блок-схема адгоритму для десаткової системи числення (56 – 9) Так Ні Так Ні Часова складність L = 10 Програмна складність Р =7 Блок-схема адгоритму для римської системи числення(LVII – IX). Часова складність L =8 Програмна складність Р =5 Отже для даного прикладу часова і програмна складність менша в алгоритмі віднімання римської системи числення. III. Висновки. На лабораторній роботі засвоїв основні визначення, порівняв часову та програмну складність алгоритмів.