Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Порівняння складності арифметичних операцій в римській та десятковій системах числення
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2008
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Алгоритмізація та методи обчислення
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет „Львівська політехніка”
Кафедра ЕОМ
Звіт
з лабораторної роботи № 1
з дисципліни: “Алгоритмізація та методи обчислення”
на тему: "Порівняння складності арифметичних операцій в римській та десятковій системах числення".
Варіант № 20.
Мета роботи : Засвоєння основних визначень. Порівняння часової складності алгоритмів.
Мухамед ібн Муса з Хорезму, за арабським ім’ям – аль-Хорезмі (походженням з середньоазіатського міста Хорезм), видатний багдадський вчений, що працював у ІХ столітті н.е. У своїй книжці – трактаті “Про індійський рахунок” аль-Хорезмі описав десяткову систему числення і арифметичні операції “ множення і ділення, сумування, віднімання та інші”. Сьогодні збереглися лише переклади трактату. Перші з них відносяться до початку XII століття.
Наприкінці XVII ст. в роботах Лейбніца цей термін набув змістовності, яка не заперечує сучасному тлумаченню: “Алгоритм - це будь-який регулярний обчислювальний процес, що дозволяє за кінцеву кількість кроків розв’язувати задачі визначеного класу”. Зауважимо, що за довгу еволюцію слова “алгоритм“ було втрачено джерело його виникнення. І тільки у 1849 році сходознавець Ж. Рейно повернув нам ім’я аль-Хорезмі [2].
Арабською “відновлення” – аль-джебр. Звідси походить слово “алгебра”[3].
Здавна найбільшу увагу приділяли дослідженням алгоритму з метою мінімізації обсягу досліджень – часовій складності розв’язання задач. Але зміст складності алгоритму не обмежується однією характеристикою. В ряді випадків не менше значення має складність логіки побудови алгоритму, різноманітність його операцій, зв’язаність їх між собою. Ця характеристика алгоритму називається програмною складністю. В теорії алгоритмів, крім часової та програмної складності, досліджуються також інші характеристики складності, наприклад, ємкістна, але найчастіше розглядають дві з них - часову і програмну. Якщо у кінцевому результаті часова складність визначає час розв’язання задачі, то програмна складність характеризує ступінь інтелектуальних зусиль, що потрібні для синтезу алгоритму. Вона впливає на витрати часу проектування алгоритму.
аль-Хорезмі, мабуть, першим звернув увагу на складність римської системи числення у порівнянні з позиційною десятковою з точки зору простоти операцій, їх послідовного виконання та засвоєння. Слова – легкість, стислість, полегшення свідчать перш за все про те, що мова йде про програмну складність алгоритмів арифметичних операцій з використанням двох систем числення.
Алгоритми реалізації арифметичних операцій, описані аль-Хорезмі у словесній формі, були першими у позиційній десятковій системі числення. Цікаво спостерігати, як точно і послідовно описує він алгоритм сумування, користуючись арабською системою числення і кільцем (нулем).
Наприклад, для операції сумування двох чисел CMLIX + XCIV потрібні таблиці більшого об’єму, ніж 10*10 кожна. Один з варіантів рахунку полягає в представленні чисел, по-перше, розділеними на окремі цифри, по-друге, проведенням операцій віднімання і сумування окремих цифр з використанням таблиць, по-третє, об’єднанням цифр, що залишилися, в єдине число.
Як бачимо, для проведення розрахунків у римській системі необхідно виконувати більше типів операцій, ніж у десятковій арабській позиційній системі числення. Крім того, у римській системі потрібні додаткові логічні перетворення, що суттєво ускладнюють зв’язки між окремими операціями обчислювального процесу.
Часова складність операцій сумування і віднімання в десятковій системі визначається кількістю розрядів у взаємодіючих числах. У римській системі часова складність залежить від порядку розташування цифр у числах. У тих випадках, коли не потрібно утворювати ланцюги логічних операцій, часова складність не перевищує часову складність операцій з десятковими числами. У протилежному випадку, як у розглянутому прикладі, зростання невелике.
Таким чином, за логікою побудови і різноманітністю операцій – програмною складністю, арабська система суттєво простіша за римську, що й довів аль-Хорезмі. За часовою складністю вони майже однакові.
· Правила запису і читання чисел в римській системі числення:
Числа читаються зліва на право (від більшого до меншого): MXI = 1011;
Всі цифри складаються окрім тих, які стоять перед тими, що їх перевершують: XIX = 19;
Зліва від цифр, що більші їх самих можуть стояти тільки I, Х, С:
I може стояти зліва тільки від V і Х;
Х може стояти зліва тільки від L і С;
С може стояти зліва тільки від D і M;
· Підряд можуть йти тільки три однакові цифри. Підряд можуть йти I, Х, С, M;
V, L, D можуть зустрічатися тільки один раз;
I, Х, C зліва (від більшої цифри) можуть зустрічатися тільки один;
Завдання № 20 LVII + XLIX 57 + 49
LVII + XLIX = L + V + I + I - X + L - I + X
LVII + XLIX = L + L + V+ I = CVI;
Виконання однієї операції для римських чисел : ~0,00010486 сек
Виконання однієї операції для Десяткових чисел : ~ 0,00008495сек
Програмна складність для римських чисел ~587 дій
Програмна складність для десяткових чисел ~58 дій
Висновок : на даній лабораторній роботі я порівнював складність арифметичних операцій в римській та десятковій системах числення, та склав програму для виконання додавання чисел в обох системах сислення. Час виконання дій над числами майже однаковий , проте складність програми для римських чисел набагато більша від такої ж програми але вже для десяткових чисел.
28.01.2013 14:01-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора