Порівняння складності арифметичних операцій в римській та десятковій системах числення. Звіт до лабораторної роботи з Алгоритмізація та методи обчислення. Робота № 518959

Порівняння складності арифметичних операцій в римській та десятковій системах числення

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

ВУЗ:

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

Інститут:

Не вказано

Факультет:

КН

Кафедра:

Кафедра ЕОМ

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

Рік:

2013

Тип роботи:

Звіт до лабораторної роботи

Предмет:

Алгоритмізація та методи обчислення

Завантажити

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

Міністерство освіти і науки України Національний університет „Львівська політехніка” Кафедра ЕОМ Звіт з лабораторної роботи № 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 дій Висновок : на даній лабораторній роботі я порівнював складність арифметичних операцій в римській та десятковій системах числення, та склав програму для виконання додавання чисел в обох системах сислення. Час виконання дій над числами майже однаковий , проте складність програми для римських чисел набагато більша від такої ж програми але вже для десяткових чисел.

Звіт до лабораторної роботи Алгоритмізація та методи обчислення

infoman

28.01.2013 14:16

Коментарі

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

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

поділитись