Міністерство освіти і науки України Національний університет „Львівська політехніка” Звіт лабораторної роботи № 1 з курсу алгоритми та методи оптимізації на тему:"Порівняння складності арифметичних операцій в римській та десятковій системах числення". 2008 Мета роботи : Засвоєння основних визначень. Порівняння часової складності алгоритмів. Теоретична частина: Те, що зараз ми розуміємо під словом алгоритм, використовувалося в глибокій давнині, наприклад, теорема про залишки в Китаї (Китайська теорема), арифметичні операції в Індії. Але праці Евкліда і аль-Хорезмі для теорії складності алгоритмів мають особливе значення. Мухамед ібн Муса з Хорезму, за арабським ім’ям – аль-Хорезмі (походженням з середньоазіатського міста Хорезм), видатний багдадський вчений, що працював у ІХ столітті н.е. У своїй книжці – трактаті “Про індійський рахунок” аль-Хорезмі описав десяткову систему числення і арифметичні операції “ множення і ділення, сумування, віднімання та інші”. Сьогодні збереглися лише переклади трактату. Перші з них відносяться до початку XII століття. Далі ми наводимо цитати з “Книги про індійський рахунок”, переклад якого був виконаний Ю.Копелевич з середньовічного латинського тексту, що зберігається у Кембриджському університеті [1]. Кожний розділ трактату, а іноді навіть абзац, починався словами “Сказав Альгорізмі…”. Це словосполучення використовували у своїх лекціях і професори середньовічних університетів. Поступово ім’я аль-Хорезмі набуло звучання “алгоризм”, “алгоритм” і навіть перетворилися у назву нової арифметики. Пізніше термін “алгоритм” почав означати регулярний арифметичний процес (Хр. Рудольф, 1525р.). І тільки наприкінці XVII ст. в роботах Лейбніца цей термін набув змістовності, яка не заперечує сучасному тлумаченню: “Алгоритм - це будь-який регулярний обчислювальний процес, що дозволяє за кінцеву кількість кроків розв’язувати задачі визначеного класу”. Зауважимо, що за довгу еволюцію слова “алгоритм“ було втрачено джерело його виникнення. І тільки у 1849 році сходознавець Ж. Рейно повернув нам ім’я аль-Хорезмі [2]. Зауважимо, що й слово “алгебра” бере свій початок з математичного трактату аль-Хорезмі “Книга відновлення і протиставлення”. Мухамеду ібн Мусі ще не були відомі від’ємні числа, тому в процесі обчислень він користувався операцією перенесення від’ємника з одної частини рівняння в іншу, де той стає доданком. Цю операцію Мухамеда ібн Муса називав “відновленням”. Слову “протиставлення” відповідає зміст збирання невідомих на одну сторону рівняння. Арабською “відновлення” – аль-джебр. Звідси походить слово “алгебра”[3]. Слова “алгоритм” і “алгебра” на перших кроках розвитку математики було щільно пов’язані між собою і за змістом і за походженням. Вони виникли з одного джерела і разом пройшли багатовіковий шлях еволюції, зайняли провідні місця у сучасній науковій термінології. Здавна найбільшу увагу приділяли дослідженням алгоритму з метою мінімізації обсягу досліджень – часовій складності розв’язання задач. Але зміст складності алгоритму не обмежується однією характеристикою. В ряді випадків не менше значення має складність логіки побудови алгоритму, різноманітність його операцій, зв’язаність їх між собою. Ця характеристика алгоритму називається програмною складністю. В теорії алгоритмів, крім часової та програмної складності, досліджуються також інші характеристики складності, наприклад, ємкістна, але найчастіше розглядають дві з них - часову і програмну. Якщо у кінцевому результаті часова складність визначає час розв’язання задачі, то програмна складність характеризує ступінь інтелектуальних зусиль, що потрібні для синтезу алгоритму. Вона впливає на витрати часу проектування алгоритму. Вперше значення зменшення програмної складності продемонстрував аль-Хорезмі у своєму трактаті “Про індійський рахунок”. У часи аль-Хорезмі для розрахунків користувалась непозиційною римською системою числення. Її вузловими числами є ...