Лабораторна робота № 1
"Порівняння складності арифметичних операцій в римській та десятковій системах числення".
Мета роботи : Засвоєння основних визначень. Порівняння часової складності алгоритмів.
Зміст роботи:
I. Теоретична частина.
Основні поняття та визначення
Тлумачення понятя алгоритм.
Властивості алгоритму.
Характеристики алгоритму.
II. Практична частина
Виконати арифметичну операцію в римській та десятковій системах числення.
Практичне заняття
Скласти блок-схеми алгоритмів для заданого варіанту .Номер варіанту відповідає порядковому номеру студента в журналі.
Порівняти часову і програмну складність алгоритмів.
Лабораторна робота
Скласти програму, яка на прикладі виконання додавання/віднімання двох чисел в римській та десятковій системах числення демонструє властивості алгоритму (дискретність, детермінованість, елементарність кроку та масовість).
Програма повинна мати зручний графічний інтерфейс.
III. Висновки.
______________________________________________________________________________
Зауваження до виконання роботи.
= Алгоритм операції в римській системі числення не повинен використовувати в явній формі операцій в позиційній системі числення (наприклад перетворення представлення числа з римської в позиційну систему).




Те, що зараз ми розуміємо під словом алгоритм, використовувалося в глибокій давнині, наприклад, теорема про залишки в Китаї (Китайська теорема), арифметичні операції в Індії. Але праці Евкліда і аль-Хорезмі для теорії складності алгоритмів мають особливе значення.
Мухамед ібн Муса з Хорезму, за арабським ім’ям – аль-Хорезмі (походженням з середньоазіатського міста Хорезм), видатний багдадський вчений, що працював у ІХ столітті н.е. У своїй книжці – трактаті “Про індійський рахунок” аль-Хорезмі описав десяткову систему числення і арифметичні операції “ множення і ділення, сумування, віднімання та інші”. Сьогодні збереглися лише переклади трактату. Перші з них відносяться до початку XII століття.
Далі ми наводимо цитати з “Книги про індійський рахунок”, переклад якого був виконаний Ю.Копелевич з середньовічного латинського тексту, що зберігається у Кембриджському університеті [1].
Кожний розділ трактату, а іноді навіть абзац, починався словами “Сказав Альгорізмі…”. Це словосполучення використовували у своїх лекціях і професори середньовічних університетів. Поступово ім’я аль-Хорезмі набуло звучання “алгоризм”, “алгоритм” і навіть перетворилися у назву нової арифметики. Пізніше термін “алгоритм” почав означати регулярний арифметичний процес (Хр. Рудольф, 1525р.). І тільки наприкінці XVII ст. в роботах Лейбніца цей термін набув змістовності, яка не заперечує сучасному тлумаченню: “Алгоритм - це будь-який регулярний обчислювальний процес, що дозволяє за кінцеву кількість кроків розв’язувати задачі визначеного класу”. Зауважимо, що за довгу еволюцію слова “алгоритм“ було втрачено джерело його виникнення. І тільки у 1849 році сходознавець Ж. Рейно повернув нам ім’я аль-Хорезмі [2].
Зауважимо, що й слово “алгебра” бере свій початок з математичного трактату аль-Хорезмі
“Книга відновлення і протиставлення”. Мухамеду ібн Мусі ще не були відомі від’ємні числа,
тому в процесі обчислень він користувався операцією перенесення від’ємника з одної частини
рівняння в іншу, де той стає доданком. Цю операцію Мухамеда ібн Муса називав “відновленням”.
Слову “протиставлення” відповідає зміст збирання невідомих на одну сторону рівняння.
Арабською “відновлення” – аль-джебр. Звідси походить слово “алгебра”[3]. Слова “алгоритм” і
“алгебра” на перших кроках розвитку математики було щільно пов’язані між собою і за
змістом і за походженням. Вони виникли з одного джерела і разом пройшли багатовіковий шлях
еволюції, зайняли провідні місця у сучасній науковій термінології.
Здавна найбільшу увагу приділяли дослідженням алгоритму з метою мінімізації обсягу досліджень – часовій складності розв’язання задач. Але зміст складності алгоритму не обмежується однією характеристикою. В ряді випадків не менше значення має складність логіки побудови алгоритму, різноманітність його операцій, зв’язаність їх між собою. Ця характеристика алгоритму називається програмною складністю. В теорії алгоритмів, крім часової та програмної складності, досліджуються також інші характеристики складності, наприклад, ємкістна, але найчастіше розглядають дві з них - часову і програмну. Якщо у кінцевому результаті часова складність визначає час розв’язання задачі, то програмна складність характеризує ступінь інтелектуальних зусиль, що потрібні для синтезу алгоритму. Вона впливає на витрати часу проектування алгоритму.
Вперше значення зменшення програмної складності продемонстрував аль-Хорезмі у своєму
трактаті “Про індійський рахунок”. У часи аль-Хорезмі для розрахунків користувалась непозиційною римською системою числення. Її вузловими числами є І, V, X, L, C, D, M, всі решта
чисел утворюються сумуванням і відніманням вузлових. аль-Хорезмі, мабуть, першим звернув увагу на складність римської системи числення у порівнянні з позиційною десятковою з точки зору простоти операцій, їх послідовного виконання та засвоєння. Він писав: “…ми вирішили розтлумачити про індійський рахунок за допомогою .ІХ. літер, якими вони виражали будь-яке своє число для легкості і стислості, полегшуючи справу тому, хто вивчає арифметику, тобто число найбільше і найменше, і все, що є в ньому від множення і ділення, сумування, віднімання та інше.”[1]. Виокремленні слова – легкість, стислість, полегшення свідчать перш за все про те, що мова йде про програмну складність алгоритмів арифметичних операцій з використанням двох систем числення. Мабуть, ці слова аль-Хорезмі про складність алгоритмів при їх порівнянні були першими в історії арифметики.
Алгоритми реалізації арифметичних операцій, описані аль-Хорезмі у словесній формі, були першими у позиційній десятковій системі числення. Цікаво спостерігати, як точно і послідовно описує він алгоритм сумування, користуючись арабською системою числення і кільцем (нулем). Наведемо повністю цей алгоритм [1].
“Сказав Алгорізмі: Якщо ти хочеш додати число до числа або відняти число від числа, постав обидва числа в два ряди, тобто одне над другим, і нехай буде розряд одиниць під розрядом одиниць і розряд десятків під розрядом десятків. Якщо захочеш скласти обидва числа, тобто додати одне до другого, то додай кожний розряд до розряду того ж роду, який над ним, тобто одиниці до одиниць, десятки до десятків. Якщо в якому-небудь із розрядів, тобто в розряді одиниць або десятків, або якому-небудь іншому набереться десять, став замість них одиницю і висувай її в верхній ряд, тобто, якщо ти маєш в першому розряді, який є розряд одиниць, десять, зроби з них одиницю і підніми її в розряд десятків, і там вона буде означати десять. Якщо від числа залишилось що-небудь, що нижче десяти, аби якщо саме число нижче десяти, залиши його в тому ж розряді. А якщо нічого не залишиться, постав кружок, щоби розряд не був пустим; але нехай буде в ньому кружок, який займе його, аби не сталося так, що якщо він буде пустим, розряди зменшаться і другий буде прийнятий за перший, і ти обманешся в своєму числі. Те ж саме ти зробиш у всіх розрядах. Подібним же чином, якщо збереться у другому розряді .Х., зробиш з них одиницю і піднімеш її в третій розряд, і там вона буде означати сто, а що лишається нижче .Х., залишиться тут. Якщо ж нічого в інших не залишається , ставиш тут кружок, як вище. Так ти зробиш в інших розрядах, якщо буде більше”.
Можна бачити, що в цьому опису є всі параметри алгоритму. Це один з перших відомих у світі вербальних арифметичних алгоритмів.
Розглянемо логіку побудови арифметичних процедур з використанням римської та арабської
систем числення з метою порівняння їх за програмною складністю. Розглянемо приклад операції сумування. Будемо користуватися алгоритмом на основі табличного методу. У арабській системі з порозрядними операціями розмір таблиці 10*10. Визначення суми чергових розрядів двох чисел, наприклад, 2 і 3 за таблицею дорівнює 5, або 7 і 9 дорівнює 16. Ці таблиці ми пам’ятаємо з дитинства.
Інша ситуація є з римською системою числення. Крім таблиці (I,II,…Х)*(I,II,…Х), що є еквівалентом таблиці 10*10 у арабській позиційній системі, додатково потрібно ще чотири таблиці з вузловими числами римської системи L,C,D,M та доповнення табличного методу логічними процедурами. Наприклад, для операції сумування двох чисел CMLIX + XCIV потрібні таблиці більшого об’єму, ніж 10*10 кожна. Один з варіантів рахунку полягає в представленні чисел, по-перше, розділеними на окремі цифри, по-друге, проведенням операцій віднімання і сумування окремих цифр з використанням таблиць, по-третє, об’єднанням цифр, що залишилися, в єдине число.
CMLIX + XCIV = (-C) + M +L +(-I) + X + (-X) + C +(-I) + V;
Оскільки –C + С = 0; –X + X = 0; – I – I = – II, V – II = III,
то (1) перепишеться у вигляді: CMLIX + CIV = M + L + III = MLIII;
Як бачимо, для проведення розрахунків у римській системі необхідно виконувати більше типів операцій, ніж у десятковій арабській позиційній системі числення. Крім того, у римській системі потрібні додаткові логічні перетворення, що суттєво ускладнюють зв’язки між окремими операціями обчислювального процесу.
Часова складність операцій сумування і віднімання в десятковій системі визначається кількістю розрядів у взаємодіючих числах. У римській системі часова складність залежить від порядку розташування цифр у числах. У тих випадках, коли не потрібно утворювати ланцюги логічних операцій, часова складність не перевищує часову складність операцій з десятковими числами. У протилежному випадку, як у розглянутому прикладі, зростання невелике.
Таким чином, за логікою побудови і різноманітністю операцій – програмною складністю, арабська система суттєво простіша за римську, що й довів аль-Хорезмі. За часовою складністю вони майже однакові.
Величезне революційне значення мало використання десяткової систем числення у Європі у всіх сферах життя – побуті, навчанні, торгівлі, суднобудуванні, техніці, географії, астрономії та багато інших. І те, що цей процес співпав з епохою Відродження, не є випадковим.
Введення десяткової системи числення, можливо, відіграло вирішальну роль прискорювача у поступових процесах Ренесансу. Значна роль в цьому належить видатному арабському вченому
аль-Хорезмі.
Мухаммад ибн Муса ал-Хорезми. Математические трактаты.- Ташкент, 1983.
2.Юшкевич А.П. История математики в средние века. – М1961.
Контрольні запитання
Дати тлумачення понятю алгоритм.
Пояснити властивості алгоритму.
Визначити характеристики складності алгоритму
Пояснити спосіб мінімізації часової складності вибором системи числення.
Праці Аль-Хорезмі, їх роль в теорії алгоритмів.

Варіанти завдань для практичного заняття.
Завдання № 1 LXVII – XIX 67 - 29
Завдання № 2 LXVI – XXXII 66 - 32
Завдання № 3 LXVII – XXV 67 - 25
Завдання № 4 LVII – XXIII 56 - 23
Завдання № 5 LXII – VI 62 - 6
Завдання № 6 LVII – XIV 57 - 14
Завдання № 7 CXIV – XI 114 - 11
Завдання № 8 CLXII + LX 162 + 60
Завдання № 9 MCX – XV 1110 - 15
Завдання № 10 DLV – X 555 - 10
Завдання № 11 DXV – III 515 - 3
Завдання № 12 CXVIII – IV 118 - 4
Завдання № 13 CXVIII + V 118 + 5
Завдання № 14 MCM – CX 1900 - 110
Завдання № 15 MCM + LXIV 1900 + 64
Завдання № 16 CIII – XIX 103 - 29
Завдання № 17 MIII + CV 1003 - 105
Завдання № 18 MXVII – LXVI 1017 - 66
Завдання № 19 MXXXVII + VII 1037 + 7
Завдання № 20 LVII + XLIX 57 + 49
Завдання № 21 DXVII – CXIV 517 - 114
Завдання № 22 DXVII + CXXIV 517 + 124
Завдання № 23 DLXVI – CXXVIII 566 -128
Завдання № 24 DLXVI + XVIII 566 + 18
Завдання № 25 DIII – IX 503 - 9
Завдання № 26 DIII + XVIII 503 + 18
Завдання № 27 MDIII – LV 1503 – 55
Завдання № 28 MDIII + DVIII 1503 + 508
Завдання № 29 MMII – IV 2002 - 4
Завдання № 30 MMII - MIV 2002 - 1004

Додаток.
Позначення цифр в римській системі числення:
I = 1
V = 5
Х = 10
L = 50
С = 100
D = 500
M = 1000
· Правила запису і читання чисел в римській системі числення:
Числа читаються зліва на право (від більшого до меншого): MXI = 1011;
Всі цифри складаються окрім тих, які стоять перед тими, що їх перевершують: XIX = 19;
Зліва від цифр, що більші їх самих можуть стояти тільки I, Х, С:
I може стояти зліва тільки від V і Х;
Х може стояти зліва тільки від L і С;
С може стояти зліва тільки від D і M;
· Підряд можуть йти тільки три однакові цифри. Підряд можуть йти I, Х, С, M;
V, L, D можуть зустрічатися тільки один раз;
I, Х, C зліва (від більшої цифри) можуть зустрічатися тільки один;
Цифра, яка стоїть справа не може стояти зліва.