borisenko_o_a_diskretna_matematika

Дискретна математика

теорію їх побудови слід віднести до теорії кодування. Однак особливість систем числення, яка полягає в потребі виконання ними арифметичних і логічних операцій, спричиняє необхідність розглядати їх також і з позиції теорії чисел.

Тобто теорія позиційних систем числення межує з теорією чисел і теорією кодування. У цьому полягає її особливість і специфіка, хоча значною мірою вона все ж таки стосується теорії кодування. З огляду на це теорія позиційних чисел повинна розглядатися як самостійна наука, яка має свій математичний апарат і свої лише їй притаманні завдання, такі як кодування чисел, та їх теоретичний аналіз.

Сьогодні інколи вважається, що на основні питання, які стосуються побудови систем числення, знайдені відповіді, тому що на практиці існуючі системи числення добре себе зарекомендували, звідки випливає, що нині потреба розвивати їх теорію відсутня. Але такому підходу властиві свої недоліки, оскільки розвиток теорії систем числення має значний, не використаний достатньою мірою потенціал.

Про це свідчить і те, що час від часу виникають нові системи числення з новими властивостями й можливостями, які можна використовувати в різних галузях науки й практики. Серед таких систем числення є досить складні, до яких можна віднести системи залишкових класів, факторіальні, поліадичні, фібоначиєві і багато інших.

Так, вони не настільки економні й прості з точки зору кількості елементів в їх структурах, як, наприклад, десяткова, але мають свої позитивні специфічні властивості, які слід використовувати на практиці. Це можливість генерації різних комбінаторних об'єктів, таких, наприклад, як перестановки або сполучення із самими різними обмеженнями щодо них, їх перешкодостійкість і інші більш специфічні властивості, які виявляються під час їх практичного застосування. Крім того, у деяких випадках з допомогою таких систем числення можна збільшити швидкодію обчислювальних пристроїв і систем до величин, які недосяжні при використанні звичайних традиційних систем.

Ці системи не є конкурентами традиційних систем числення, як інколи це вважається, хоча б тому, що останні за своєю універсальністю й простотою виконання арифметичних і логічних операцій недосяжні для будь-яких інших систем числення з більш складною структурою. Однак такі системи числення є ефективним доповненням до звичайних універсальних систем, оскільки здатні

163

Борисенко О.А.

разом з останніми працювати над вирішенням одних і тих самих проблем, збільшуючи надійність чи швидкодію пристроїв і систем, які їх використовують. Тому не зовсім правильно протиставляти звичайні, прості, і більш нові, складні, системи числення. Будь-яка з них за певних умов зможе зарекомендувати себе з найкращого боку.

7. Історія виникнення систем числення

Історично першими виникли непозиційні системи числення. Вони ґрунтуються на кількісному підході до визначення числа, який для кодування тих чи інших кількостей застосовував особливі знаки - числа. Кожному такому знаку відповідав кількісний еквівалент. Наприклад, у так званій римській нумерації знаку X відповідала кількість елементів множини, яка дорівнювала 10.

У подальшому такими знаками - числами користувалися також і для одержання інших чисел. Так, якщо перед знаком X ставилась вертикальна риска, то отримували знак IX, який означав, що від десяти треба відняти одиницю і результуюча кількість буде дорівнювати 9. Знаки, подібні X, називаються вузловими. Вони широко використовувалися в первісних непозиційних системах числення. Слід ще раз зазначити, що серед цих знаків не було такого, який би відповідав нулю. Це свідчить про те, що нуль у той час ще не був сформований як число.

Кількість чисел, яку можна було одержати з допомогою непозиційного кодування, через його складність і відповідно велику кількість чисел, що потребували запам'ятовування, була обмежена кількома сотнями, і, крім того, щодо цих чисел досить важко було виконувати арифметичні й логічні операції. Тому в подальшому з розвитком науки виникла потреба в більш ефективних системах числення, які б мали прості правила кодування чисел, та легко виконували б щодо них арифметичні й логічні операції. Такі системи чисел були створені і отримали назву позиційних. Більш докладно ці системи числення будуть розглянуті нижче, тому що вони складають на сьогодні основу теорії систем числення взагалі.

Весь світ пройнятий кількістю.

А. И. Уайтхед

164

Дискретна математика

Лекція 28 ДЕСЯТКОВА І СПОРІДНЕНІ і НЕЮ ПОЗИЦІЙНІ

СИСТЕМИ ЧИСЛЕННЯ

1. Позиційні числа

Для позиційних систем числення важливим є принцип позиційності, який полягає в змінах кількісного значення цифр залежно від їх позицій. Ці позиції визначаються розрядами числа. Кожна цифра числа має свій розряд, в якому вона знаходиться і який

відрізняється від інших розрядів своїм номером.

Принцип позиційності дозволяє легко з допомогою порівняно невеликої кількості цифр і позицій, які вони займають, зобразити будь-яке велике натуральне число. Це важлива властивість позиційних систем числення, яка широко використовується на практиці.

Кількість розрядів позиційного числа характеризує його довжину. У більшості випадків числа однієї і тієї ж самої системи числення мають однакову довжину. Тому вони легко розрізняються між собою Такі числа називають рівномірними. Однак ця довжина й відповідна їй кількість розрядів у загальному випадку для різних чисел однієї й тієї ж самої позиційної системи числення можуть бути різними. Такі числа з нерівномірною довжиною називаються нерівномірними. Це призводить до того, що виникає задача їх розпізнавання.

Ця задача розв'язується шляхом зображення чисел у вигляді префіксних кодів, тобто кодів, в яких кожне кодове слово не є початком іншого кодового слова цього коду. Так, кодові слова 000, 0010, 01100 створюють префіксний код, а слова коду 00, 001, 0101 не створюють його, оскільки слово 00 є початком слова цього коду - 001 і тому не може бути виділене як самостійне слово.

Для рівномірних чисел задача розпізнавання має значно простіший вигляд, оскільки її розв'язання відбувається шляхом підрахунку кількості цифр у числі. Якщо ця кількість буде дорівнювати довжині, яка для всіх чисел однакова, то воно вважається знайденим. Далі лише необхідно буде виокремити його з поміж інших чисел такої ж довжини. Так, рівномірні числа 00, 01, 10 і 11 легко розпізнаються, оскільки мають однакову довжину, яка складається з двох цифр. За наявності в числі в процесі його формування двох цифр воно вважається сформованим.

165

Борисенко О.А.

2. Структурні елементи позиційних систем числення

Будь-яка система числення, чи нумерація, у тому числі й позиційна, у загальному вигляді у своєму складі повинна мати скінченну множину невід'ємних чисел - діапазон, який вона кодує. До неї обов'язково в позиційних системах числення входить число 0 і далі числа натурального ряду, які починаються з 1. Крім того, в позиційну систему числення входить ще нумераційна, чи числова, функція, з допомогою якої ці числа нумеруються, а також алфавіт - скінченна множина цифр, з яких складаються кодові зображення чисел, і обмеження на значення цифр.

Для цифр алфавіту характерною ознакою є те, що вони починаються з нуля і далі йдуть як ряд натуральних чисел, тобто цифри алфавіту мають порядок 0, 1, ... . Серед цих цифр не може хоча б одна бути пропущеною. Так, для найбільш поширеної на сьогодні і досить простої позиційної системи числення - десяткової алфавіт має 10 цифр - 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, серед яких обов'язково буде нуль.

Число цих десяти цифр для десяткової системи числення, як і число цифр 2, 3, 4, 5, ... в алфавітах інших подібних їй двійкової, трійкової, четвіркової, п'ятеричної систем числення, має назву їх основи. Основа задає кількість цифр з урахуванням нуля, які має алфавіт тієї чи іншої системи числення. Тому максимальна цифра в алфавіті десяткової системи числення завжди буде на одиницю меншою від основи. Але це правило поширюється тільки на десяткову й подібні їй системи числення. У більш складних системах це може бути інакше.

Цікаво, що в нспозиційних системах числення нуль був відсутній. Щоб зрозуміти значення нуля й відповідної йому порожньої множини, треба було винайти позиційні системи числення, а для цього повинні були пройти тисячі років. Позиційні системи числення і лічба на їх основі неможливі без нуля. Тому нуль є однією з фундаментальних основ сучасної позиційної лічби.

3. Десяткова система числення

Вважається, що першими позиційними системами числення, які одержали поширення на практиці, були п'ятерична і десяткова. Пізніше з'явилися двійкова, восьмерична, дванадцятерична та інші системи числення. Кожна з цих систем числення має однакову довжину чисел.

У десятковій системі числення кожне натуральне число з допомогою нумераційної функції можна подати у вигляді суми

166

Дискретна математика

добутків цифр цього числа, починаючи з цифри нульового розряду, на степінь числа 10 з показниками степені 0, 1, ... . Цим показникам відповідають номери розрядів числа при їх підрахунку справа. Наприклад, число 123 десяткової системи числення можна подати у вигляді виразу, який зображає таку нумераційну функцію:

1-Ю2 +2-101 +3-10°.

При цьому обмеження на цифри для кожного розряду в цій функції для десяткової системи числення мають вигляд: 0 < / < 9, де /= 0,1, ..., 9. У системах числення з іншою основою обмеження на цифри, які використовуються в них, будуть іншими, але вони обов'язково існують. Наприклад, у найпростішій на сьогодні позиційній системі числення - двійковій, тобто в системі, основа якої дорівнює 2, цифри можуть приймати значення тільки 0 і 1. Тоді число 123 в двійковій системі буде мати вигляд - 1111011.

Діапазон десяткової системи числення дорівнює степеню числа 10, показник якого визначається кількістю розрядів десяткового числа. Діапазон чисел системи числення, якому належить десяткове число 123, очевидно, дорівнює 1000.

У позиційних системах числення кожний розряд має свою вагу. Ця вага для десяткової системи числення дорівнюватиме степеню 10 з показником степені, що дорівнює номеру розряду, вага якого визначається. Для вищенавсдсного прикладу ваги нульового, першого

й другого розрядів будуть дорівнювати величинам 10°, 10і, 102. Тобто в цьому десятковому числі вага нульового розряду дорівнює 1, а вага кожного наступного розряду збільшується в 10 разів і буде дорівнювати 10 і 100 відповідно для першого й другого розрядів.

Однак вага розряду в деяких системах числення втрачає свій первісний зміст, а натомість з'являється вага цифри цього розряду. Ця вага для кожної цифри розряду зображає її кількісне значення, яке може відрізнятися від значень інших цифр цього розряду. Однак для десяткової, двійкової й інших подібних систем числення вона дорівнює вазі розряду. Тому для цих систем числення можна говорити про вагу розряду, розуміючи при цьому вагу цифри, і навпаки, говорячи про вагу цифри, можна розуміти при цьому вагу розряду.

Крім ваги цифри розряду, будемо розглядати ще і її сумарну вагу в цьому розряді, яка мас вигляд суми ваг усіх менших від цієї

167

Борисенко О.А.

цифри можливих цифр цього розряду. їх кількість з урахуванням 0 буде такою, що відповідає цифрі числа цього розряду.

Сумарна вага цифри 0 завжди буде дорівнювати 0, оскільки додатні цифри, що менші за 0, відсутні. Цифра І показує, що в розряді, до якого вона належить, може бути лише одна менша від неї цифра - 0, вага якої в даному випадку й буде сумарною вагою цифри 1. Цифра 2 буде показувати, що меншими від неї є дві цифри - 0 і 1, ваги яких при підсумовуванні й створюють сумарну вагу цифри 2. Дія цього самого правила поширюється і на решту цифр числа.

Так, наприклад, для цифри 2 десяткового числа 123, яка належить до першого розряду, сумарна вага буде складатися із суми ваг двох менших цифр - 0 і 1. Вага кожної з них дорівнює 10, тобто сумарна вага цифри 2 числа 123 буде дорівнювати 20. Очевидно, що сумарна вага цифри 3 нульового розряду числа 123 буде складатися з ваг трьох менших цифр - 0, 1, 2, які в цьому розряді дорівнюють 1. Тому вона буде дорівнювати 1 + 1+1=3. Сумарна вага цифри 1 другого розряду відповідно до вищезазначеного, буде складатися з ваги попередньої цифри 0, яка дорівнює 100.

Також у такому десятковому числі, як 202, вага цифри 2 нульового розряду дорівнює 1, цифри 0 першого розряду - 10, цифри 2 другого розряду - 100, а сумарні ваги цих цифр дорівнюватимуть сумам кількісних значень менших цифр, які належать до цих розрядів. Так, у нульовому розряді цифра 2 має сумарну вагу, яка складається з двох кількісних значень менших цифр - 0 і 1. їх ваги, очевидно, дорівнюють 1, і тому сумарна вага цифри 2 буде дорівнювати 2. Відповідно в першому розряді цифра 0 має сумарну вагу, яка дорівнює 0, цифра 2 в другому розряді має сумарну вагу, яка складається з ваг цифр 0 і 1, тобто дорівнює 200.

4. Унітарна система числення Серед систем числення перехідне місце між позиційними і

непозиційними системами числення займає система числення з алфавітом цифр, який складається з однієї цифри - нуля. Це значить, що основа й діапазон чисел цієї системи дорівнює 1. Така система числення інколи називається унітарною. Наявність в її алфавіті лише нуля, тобто однієї цифри, призводить до того, що, наприклад, число з трьох розрядів унітарної системи числення, буде мати вигляд:

0 • І2 + 0 • 1' + 0 • 1° = 0.

168

Дискретна математика

Така система числення кодус лише одне початкове число натурального ряду - одиницю. При цьому вага 0 кожного розряду дорівнює 1, а його сумарна вага дорівнюватиме 0.

Здавалося б, що унітарна система числення не може мати прикладного значення через те, що кодує лише одне число - 1. Але це не так. Ця система використовувалась раніше і використовується сьогодні в сучасній цифровій техніці при побудові різних особливо надійних пристроїв автоматики й обчислювальної техніки, тому що вона може бути подана з допомогою так званого число-імпульсного коду. В цьому коді кожне число зображається з допомогою послідовності імпульсів, кількість яких дорівнює кількісному значенню цього числа.

Так, у вищенаведеному прикладі унітарна система числення зображує число 3. Тому воно в реальному пристрої кодується трьома імпульсами. Головний недолік використання такої системи числення - цс значне зниження швидкодії пристроїв, які її використовують. Але гам, де швидкодія не має особливого значення, унітарна система числення може бути досить ефективною завдяки високій надійності апаратури, яка її використовує.

5.Системи числення, споріднені з десятковою

Урозглянутих прикладах систем числення в кожному розряді їх чисел вага розряду визначалась степенем основи. Це найбільш простий і уживаний спосіб побудови систем числення. Але зустрічаються й більш складні системи числення, деякі з котрих будуть розглянуті нижче в цьому й інших розділах. Основою цих систем, як і раніше, є натуральні числа.

Наприклад, можна побудувати систему числення, яка грунтується на простих числах, таких як 1, 3, 5, 7, ... . Візьмемо в цій системі числення для нульового розряду одну основу - 1, для першого розряду дві основи - 1 і 3, для другого розряду три - 1, 3, 5 і т. д. З цього виходить, що алфавіт цифр для 0 розряду буде складатися з трьох цифр - 0, 1,2; першого розряду - з п'яти цифр - 0, 1, 2, 3, 4; другого із семи - 0, 1, 2, 3, 4, 5, 6.

Ваги розрядів при цьому отримаємо як добутки взятих у кожному розряді основ. Тоді вага нульового розряду буде дорівнювати 1, вага першого розряду - 3, вага другого розряду - 15.

Відповідно до наведеного число 220 буде мати такий вигляд:

2-5-3-1 + 2-3-1+ 0-1.

169

Борисенко О.А.

У десятковій системі числення цс число, очевидно, буде дорівнювати 36. Сумарна вага його цифри 0 у нульовому розряді буде дорівнювати 0, цифри 2 першого розряду - 6, цифри 2 другого розряду - 30. Тому кінцевий результат після підсумовування всіх сумарних ваг буде дорівнювати 36. Найбільше число в цій системі числення отримується шляхом підстановки в усі розряди числа максимальних цифр - 6, 4 і 2. У результаті отримаємо десяткове число 104. Відповідно, діапазон чисел, існуючих у цій системі числення, буде дорівнювати 105.

Отримана система числення хоча й близька до десяткової, але все ж таки має суттєві відмінності. Основ у неї не одна, а декілька. Також алфавіт цифр змінюється від розряду до розряду. Відповідно, і їх ваги змінюються не за степеневим законом, як це має місце в десятковій системі числення, а за більш складним. Ще більше відмінностей мають узагальнені позиційні системи числення, початкова теорія яких викладена в наступних розділах.

Природа - це те, що підлягає обчисленню.

Шпенглер

170

Дискретна математика

Лекцій 29 ПОЗИЦІЙНЕ КОДУВАННЯ ЧИСЕЛ

1. Розбиття множин

Позиційні системи числення, які розглядались у попередньому розділі, мають широке застосування на практиці, але вони відображають лише частину можливих їх структур. Щоб в узагальненому вигляді уявити всі ці структури, потрібно зрозуміти ідею, на якій ґрунтується їх побудова.

одиниці на непорожні підмножини. Ця ж сама ідея є підґрунтям будьякого іншого кодування інформації. Слід зазначити, що кодування чисел має свою специфіку, і тому можна говорити про відповідну цьому кодуванню теорію позиційних систем числення.

Розбиття на підмножини, які мають в них місце, відбуваються певними кроками, які в подальшому в системах числення розглядаються як відповідні цим крокам розряди чисел, а кількості елементів в підмножинах - як ваги їх цифр. У загальному випадку на кожному кроці розбивається більше, ніж одна отримана на попередньому кроці розбиття підмножина. Тільки на першому кроці розбивається лише одна вихідна множина З розбиття цієї множини й починаються подальші розбиття отриманих на цьому кроці підмножин на нові підмножини до того часу, поки кожній одержаній під час розбиття підмножині не буде належати один елемент. Таке розбиття вихідної множини чи якоїсь з отриманих при цьому підмножин будемо називати повним.

Так, вихідна множина, до якої належить 100 елементів, при побудові десяткових чисел має повне розбиття, коли на першому кроці розбивається на 10 підмножин з 10 елементами в кожній, а на другому кожна з отриманих підмножин розбивається ще на 10 підмножин, тепер уже з одним елементом і на цьому розбиття підмножин закінчуються. Тобто дане розбиття буде повним і кожне з отриманих на їх основі число буде складатися з двох розрядів, у кожному з яких є дві цифри від 00 до 99.

Але в загальному випадку ніщо не забороняє ці ж самі 100 елементів розбивати на підмножини з різною кількістю елементів, і тоді при повному їх розбитті можна отримувати більш складні системи числення, ніж десяткова. Через свою складність подібні системи менш поширені на практиці, але все ж таки вони мають

171

Борисенко О.А.

ігоштивні якості, які можуть з успіхом бути використані в сучасній обчислювальній техніці. Тому їх слід розглядати не тільки із теоретичних міркувань, а й з практичних теж.

2. Правило Суми

Щоб довести важливі властивості позиційного кодування чисел, необхідно сформулювати правило розбиття множин на нідмножини, яке назвемо правилом Суми.

Якщо деяку скінченну множину елементів розбити на декілька підмножин, що не перетинаються між собою, то сума їх елементів дорівнюватиме числу елементів, які були в цій множині до її розбиття.

Це правило через його очевидність не визиває сумніву і в неявному вигляді, як аксіома, широко використовується на практиці. Але для цього навчального курсу був сенс сформулювати його таким чином, щоб потім свідомо використовувати його для вивчення способів побудови позиційних чисел. У більш загальному вигляді воно застосовується разом з правилом Добутку в комбінаториці, а також має пряму причетність до правила Діріхле.

Правило Суми відносно розбиття скінченних множин на підмножини є загальним. Воно поширюється в тому числі й на порожні множини, але більш важливим є випадок, коли при розбитгі скінченної множини на підмножини порожні множини будуть відсутні. Далі завжди, коли йтиме мова про розбиття множин на підмножини, будемо вважати, що й множини і їх підмножини не є порожніми.

З наведеного правила випливає, якщо скінченна множина ^ розкладається на декілька підмножин, то кожній з них повинно належати число елементів менше, ніж їх було в цій множині до її розбиття. Інакше сума елементів у цих підмножинах буде перевищувати число елементів у вихідній множині, що призведе до порушення цього правила.

Якщо ж продовжити розбиття отриманих підмножин на число, більше ніж одна підмножина, далі, то кількість елементів, які належать цій підмножині, буде відповідно до наведеного вище правила Суми зменшуватися і через певне число кроків виявляться лише одноелементні підмножини.

На цьому процедура розбиття вихідної множини на підмножини може або закінчитися, або, у разі необхідності, продовжитися, але вже у вигляді розбиття кожної з отриманих одноелементних підмножин на

172