Зміст
ВведенняГлава 1. Представлення даних у цифрових автоматах (ЦА)
1.1 Представлення чисел у позиційних системах числення (ПСС)
1.2 Форми представлення даних в ЦА
1.3 Виконання арифметичних операцій з цілими числами, представленими в машинних кодах
1.4 Виконання логічних операцій з цілими числами, представленими в машинних кодах
Глава 2. Методи контролю роботи ЦА
2.1. Коригуюча здатність кодів
2.2 Метод парності / непарності. Коди Хемінг
2.3 Контроль за модулем
Глава 3. Побудова алгоритму реалізації чисельного методу «швидкої сортування»
3.1 Математичне опис методу
3.2 Таблиця використовуваних змінних
Список використаних джерел
Додаток 1. Блок-схема алгоритму
Введення
У своїй роботі я ставлю такі завдання:
- Навчитися представляти дані у ЦА;
- Вивчити методи контролю роботи ЦА і навчитися будувати код Хеммінга;
- Вивчити реалізацію алгоритму чисельного методу «швидкого сортування» і побудувати його блок-схему.
Глава 1. Представлення даних у цифрових автоматах (ЦА)
1.3 Представлення чисел у позиційних системах числення (ПСС)
Система числення - це сукупність символів і правил їх запису, необхідних для запису чисел.
У позиційній системі числення вага символу залежить від позиції в якій розташований символ. Наприклад, число 222 - перший символ цього числа має вагу 200, другий - 20, третій - 2.
Основною характеристикою ПСС є підстава. Підстава ПСС - це кількість символів даної системи числення, які використовуються при складанні чисел. Залежно від підстави ПСС існує чотири основні системи числення: двійкова, вісімкова, десятеричная і шістнадцяткова. Всі ці системи числення використовуються в ЦА і кожна має свої основні функції. Наприклад, числа, записані в двійковій системі числення, використовуються в ЦА для операцій вироблених процесором: запис, зчитування, складання і т.д.; числа в шістнадцятковій системі числення - для адресації комірок пам'яті.
Переклад чисел з однієї ПСС в іншу
При перекладі чисел з десяткової системи числення в систему з основою P зазвичай використовують наступний алгоритм:
1) якщо переводиться ціла частина числа, то вона ділиться на P, після чого запам'ятовується залишок від ділення. Отримане приватне знову ділиться на P, залишок запам'ятовується. Процедура триває до тих пір, поки приватне не стане рівним нулю. Залишки від ділення на P виписуються в порядку, зворотному їх отримання;
2) якщо переводиться дробова частина числа, то вона множиться на P, після чого ціла частина запам'ятовується і відкидається. Знову отримана дробова частина множиться на P і т.д. Процедура триває до тих пір, поки дробова частина не стане рівною нулю. Цілі частини виписуються після двійковій комою в порядку їх отримання. Результатом може бути або кінцева, або періодична двійкова дріб. Тому, коли дріб є періодичною, доводиться обривати множення на будь-якому кроці і задовольнятися наближеною записом вихідного числа в системі з основою P.
Переклад числа з системи числення з основою P1 в систему числення з основою P2, можна виконати за таким же алгоритмом, але все обчислення потрібно проводити в системі числення з основою P1. Другий спосіб перевести число можна в два етапи: перевівши це число в десяткову систему числення, а потім з десяткової до системи числення з основою P2.
Щоб перевести число з системи числення з основою P
в десяткову систему числення, потрібно знайти суму творів вмісту розряду на вагу цього розряду в системі числення з основою P. Де розряд - номер позиції в числі, нумеруються справа наліво, починаючи з нуля; вага розряду - число, рівне основи системи числення певною мірою номери розряду.
Щоб перевести число з двійкової системи числення
у вісімкову (шістнадцяткову) систему числення, потрібно розбити число на трійки (четвірки) цифр, у разі необхідності слід доповнити цілу і дробову частини числа нулями (цілу ліворуч, дробову праворуч). Потім замінити отримані групи цифр відповідними їм вісімковими (шестнадцатерічнимі) цифрами. Наприклад, число 11010010.10 2 треба перевести у вісімкову систему числення. Розіб'ємо число на трійки цифр: 011 010 010. 100, замінимо трійки цифр на відповідними їм вісімковими цифрами. Отримаємо 11010010.10 2 = 322.4 8
Щоб перевести число з вісімковій (шістнадцятковій) системи числення в двійкову систему числення, потрібно замінити кожну цифру числа відповідними їм трійками (четвірками) двійкових цифр.
Завдання. Здійснити переклад числа (А + В), представленого в 10-ій системі з однієї системи числення в інші, за схемою малюнка.
|
|
|
|
|
|
|
|
|
|
|
|
Рішення.
А + В = 307 +6.6 = 313.6 10
313.6 10 = () 2
Спочатку переводимо цілу частину числа, ділимо на підставу 2:
313 / 2 = 156 залишок - 1;
156 / 2 = 78 залишок - 0;
78 / 2 = 39 залишок - 0;
39 / 2 = 19 залишок - 1;
19 / 2 = 8 залишок - 1;
9 / 2 = 4 залишок - 1;
4 / 2 = 4 залишок - 0;
2 / 2 = 1 залишок - 0;
Далі ділити не можна, тому збираємо всі залишки, починаючи з кінця і враховуємо кінцевий результат від ділення тобто 2 / 2 = 1. Отримаємо 313 10 = 100111001 2
Тепер переводимо дробову частину числа, множимо на підставу 2:
| * | 6 | * | 2 | * | 4 | * | 8 | ||||
| 2 | 2 | 2 | 2 | ||||||||
| 1 | 2 | 0 | 4 | 0 | 8 | 1 | 6 |
Отримаємо 0.6 10 = 0.1001 2, значить,
313 10 »100111001.1001 2
100111001.1001 2 = () 8
Розіб'ємо число на трійки цифр: 100 111 001. 100 100, замінимо трійки цифр на відповідними їм вісімковими цифрами тобто 100 2 = 4 8; 111 2 = 7 8; 001 2 = 1 8. Отримаємо 100111001.1001 2 = 471.44 8
100111001.1001 2 = () 10
| 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | . | 1 | 0 | 0 | 1 | Число |
| 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | -1 | -2 | -3 | -4 | Розряди числа |
= 0.0652 + 0.5 + 1 + 8 + 16 + 32 + 256 = 313.5652 10 »313.6 1910
100111001.1001 2 = () 16
Розіб'ємо число на четвірки цифр: 0001 0011 1001. 1001, замінимо четвірки цифр на відповідними їм шестнадцатерічнимі цифрами тобто 0001 2 = 1 16; 0011 2 = 3 16; 1001 2 = 9 16. Отримаємо 100111001.1001 2 = 139.9 16
313.6 10 = () 8
Спочатку переводимо цілу частину числа, ділимо на підставу 8:
313 / 8 = 39 залишок - 1;
39 / 8 = 4 залишок - 7.
Отримаємо 313 10 = 471 8
Тепер переводимо дробову частину числа, множимо на підставу 8:
| * | 6 | * | 8 | * | 4 | * | 2 | ||||
| 8 | 8 | 8 | 8 | ||||||||
| 4 | 8 | 6 | 4 | 3 | 2 | 1 | 6 |
313 10 »471.4631 8
471.4631 8 = () 2
Кожен символ числа 471.4631 8 запишемо у двійковій системі числення: 4 8 = 100 2, 7 8 = 111 2, 1 8 = 001 2, 6 8 = 110 2, 3 8 = 011 2.
Отримаємо 471.4631 8 = 100111001.100110011001 2
471.4631 8 = () 10
| 4 | 7 | 1 | . | 4 | 6 | 3 | 1 | Число |
| 2 | 1 | 0 | -1 | -2 | -3 | -4 | Розряди числа |
= 0.0002 + 0.0058 + 0.0937 + 0.5 + 1 + 56 + 256 = 313.5997 10 »313.6 10
471.4631 8 = () 16
Переклад числа з вісімковій системи числення в шістнадцяткову проведемо у два етапи: спочатку переведемо число в десяткову систему числення, потім з десятеричной в шістнадцяткову. Переклад числа 471.4631 8 у десяткову систему числення вже здійснено вище: 471.4631 8 = 313.6 10. Далі переведемо 313.6 10 в шістнадцяткову систему числення:
313.6 10 = () 16
Спочатку переводимо цілу частину числа, ділимо на підставу 16:
313/16 = 19 залишок - 9;
19/16 = 1 залишок - 3.
Отримаємо 313 10 = 139 16
Тепер переводимо дробову частину числа, множимо на підставу 16:
| * | 6 | * | 6 | ||
| 16 | 16 | ||||
| 9 | 6 | 9 | 6 |
313 10 »139.99 16
139.99 16 = () 2
Кожен символ числа 139.99 1916 запишемо у двійковій системі числення: 1 16 = 0001 2, 3 16 = 0011 2, 9 16 = 1 001 2.
Отримаємо 139.99 16 = 100111001.10011001 2
139.99 16 = () 8
Переклад числа з шістнадцятковій системи числення у вісімкову будемо виконувати в один етап, роблячи все обчислення в шістнадцятковій системі числення.
Спочатку переводимо цілу частину числа, ділимо на підставу 8:
| 139 | 8 | ||
| 100 | 27 | ||
| - | 39 | ||
| 38 | |||
| 1 | |||
| 27 | 8 |
| 20 | 4 |
| 7 |
Тепер переводимо дробову частину числа, множимо на підставу 8:
| * | 99 | * | С8 | * | 40 | |||
| 8 | 8 | 8 | ||||||
| 4 | С8 | 6 | 40 | 2 | 00 |
139.99 16 »471.4620 8
139.99 16 = () 10
1 | 3 | 9 | . | 9 | 9 | Число |
| 2 | 1 | 0 | -1 | -2 | Розряди числа |
Виконання арифметичних операцій над числами, представленими в ПСС
Операції над числами в двійковій, вісімковій, шістнадцятковій системі числення виконуються за такими ж правилами, що й арифметичні операції над числами в десятеричній системі числення.
Завдання
А) Скласти числа (А) 16 і (B) 16
(А) 10 = 307 10 = 133 16 (В) 10 = 6.6 10 = 6.99 16
| + | 133.00 |
| 6.99 | |
| 139.99 |
(А) 10 = 307 10 = 463 8 (В) 10 = 6.6 10 = 6.46 8
| - | 463.00 |
| 6.46 | |
| 454.31 |
(С) 10 = 91 10 = 1011011 2 (У) 10 = 6.6 10 = 110.1001 2
| * | 1011011 | |
| 110.1001 | ||
| 1011011 | ||
| + 1011011000 | ||
| 101101100000 | ||
| 1011011000000 | ||
| 1001010101.0011 | ||
(С) 10 = 91 10 = 1011011 2 (В) 10 = 6.6 10 = 110.1 2
| 1011011 | 110.1 | Þ |
| 10110110 | 1101 | ||
| 01101 | 1110.0 | ||
| 010011 | |||
| 001101 | |||
| 0001101 | |||
| 0001101 | |||
| 0000000 | |||
Кодування та форми подання чисел в ЦА
Представлення чисел у машинних кодах для виконання арифметичних операцій
Прямий код - це двійковий код числа, записаний у розрядній сітці, в старшому розряді якого вказується знак числа.
Для позитивних чисел прямий код числа збігається з зворотним і додатковому кодом тобто [A] пр = [A] обр = [A] доп.
В іншому випадку, коли число негативне:
- Зворотний код виходить з прямого, шляхом інверсії всіх розрядів, за винятком знакового;
- Додатковий код виходить шляхом додавання одиниці до зворотного коду тобто [A] доп = 1 + [A] обр.
Модифікований зворотний (додатковий) код - аналог зворотного (додаткового) коду, з тією лише різницею, що на знак виділяються два старших розряду.
Завдання. Числа А,-А, З і-З представити в прямому, зворотньому, додатковій, модифікованому зворотному і модифікованому додатковому кодах.
А = 307 10 = 100 110 011 2 З = 91 10 = 1011011 2
[A] пр = [A] об = [A] доп = 0 | 000000100110011
[A] мод. Про = 00 | 00000100110011
[A] мод. Доп = 00 | 00000100110011
[-A] пр = 1 | 000000100110011
[-A] об = 1 | 111111011001100
[-A] мод. Про = 11 | 11111011001100
[-A] доп = 1 | 111111011001100 +1 = 1 | 111111011001101
[-A] мод. Доп = 11 | 11111011001100 +1 = 11 | 11111011001101
[C] пр = [C] об = [C] доп = 0 | 000000001011011
[C] мод.об = 00 | 00000001011011
[C] мод.доп = 00 | 00000001011011
[-C] пр = 1 | 000000001011011
[-C] об = 1 | 111111110100100
[-C] мод.об = 11 | 11111110100100
[-C] доп = 1 | 111111110100100 +1 = 1 | 111111110100101
[-C] мод.доп = 11 | 11111110100100 +1 = 11 | 11111110100101
Представлення чисел у форматі з фіксованою комою
Для чисел, представлених у форматі з фіксованою комою, попередньо визначається місце комою між розрядами, тому число може бути визначене тільки в певному діапазоні. Якщо розглядати два числа, які мають місце положення різні, то числа вирівнюються по молодшого розряду. Для цього всі числа заносяться в ЦА попередньо множаться на маштабної коефіцієнт.
Наприклад:
111.101 * 2 4 = 1111010 - цілий вид;
111.101 * 2 -3 = 0.111101 - дробовий вигляд,
де 2 4 і 2 -3 - маштабної коефіцієнт.
Завдання. Числа A,-A, B і-B представити у форматі з фіксованою точкою (в 16-ти розрядах). При цьому числа A і B призвести до цілого виду, а-A і B-до дробовому з 4-ма знаками після коми.
А = 307 10 = 100 110 011 2
A = 0000000100110011 - цілий вид;
A = 100110011 * 2 -4 = 000000010011.0011 - дробовий вигляд.
В = 6.6 10 = 110.1 2
B = 110.1 * 2 1 = 0000000000001101 - цілий вид;
B = 110.1 * 2 -3 = 000000000000.1101 - дробовий вигляд.
Представлення чисел у форматі з плаваючою комою
Будь-яке число N у системі числення з основою q можна записати у вигляді N = M * q p, де M називається мантиссой числа, а p - порядком. Такий спосіб запису чисел називається виставою з плаваючою крапкою.
Мантиса повинна бути правильною дробом, перша цифра дробової частини якої відмінна від нуля: M з діапазону [0.1; 1).
Таке, найбільш вигідне для комп'ютера, уявлення дійсних чисел називається нормалізованим.
Мантиссу і порядок q-ічного числа прийнято записувати в системі з основою q, а сама підстава - у десятковій системі.
При зберіганні числа з плаваючою точкою відводяться розряди для мантиси, порядку, знака числа і знака порядку:
| ... | ... |
Знак числа |
|
|
|
Наприклад: 753.15 = 0.75315 * 10 3.
Завдання. Числа A,-A, B і-B представити у форматі з плаваючою точкою.
А = 307 = 0.307 * 10 3
В = 6.6 = 0.66 * 10 1
Кодування та способу викладення символьної інформації
У більшості перших комп'ютерів використовувався семібітний код КОІ-7 (код обміну інформацією, семизначний). У такому коді можна було закодувати 2 7 = 128 символів. Але з розвитком техніки це стало досить незручно.
Новий код був вже восьмібітним і грунтувався на американському стандартному коді обміну інформацією ASCII (American Standard Code for Information Interchange). У восьмібітним коді можна закодувати вже 2 8 = 256 символів. Цього цілком вистачає щоб без жодних проблем використовувати в тексті великі і маленькі літери російського і латинського алфавітів, розділові знаки, цифри, спеціальні символи.
З недавнього часу був запропонований новий стандарт символьного кодування UNICODE. Шістнадцять розрядів дозволяють забезпечити унікальні коди для 2 16 = 65536 різних символів - цього поля достатньо для розміщення в одній таблиці символів більшості мов планети.
Завдання. Використовуючи таблицю Windows 12.51, закодувати свої: прізвище та ім'я (записані російською та англійською мовами). Вписати їх у розрядну сітку.
| Буква | Десятірічний код | Двійковий код | Буква | Десятірічний код | Двійковий код | |
| Ш | 216 | 11011000 | S | 83 | 1010011 | |
| а | 224 | 11100000 | h | 104 | 1101000 | |
| б | 225 | 11100001 | a | 97 | 1100001 | |
| а | 224 | 11100000 | b | 98 | 1100010 | |
| р | 240 | 11110000 | a | 97 | 1100001 | |
| про | 238 | 11101110 | r | 114 | 1110010 | |
| в | 226 | 11100010 | o | 111 | 1101111 | |
| v | 118 | 1110110 | ||||
| П | 207 | 11001111 | ||||
| а | 224 | 11100000 | P | 80 | 1010000 | |
| в | 226 | 11100010 | a | 97 | 1100001 | |
| е | 229 | 11100101 | v | 118 | 1110110 | |
| л | 235 | 11101011 | e | 101 | 1100101 | |
| l | 108 | 1101100 |
Арифметичні операції з цілими числами, представленими в машинних кодах, виконуються тільки операцією додавання. Тобто операція різниці, замінюється операцією додавання, операція твори також замінюється операцією додавання.
Наприклад, обчислити: А + B, A - B,-A - B. Нехай А = 160 10, B = 45 10.
[A] доп = 0 | 000000010100000
[-A] доп = 1 | 111111101100000
[B] доп = 0 | 000000000101101
[-B] доп = 1 | 111111111010011
| А + B | A - B | -A - B | |||||
| + | 0 | 000000010100000 | + | 0 | 000000010100000 | + | 1 | 111111101100000 | ||
| 0 | 000000000101101 | 1 | 111111111010011 | 1 | 111111111010011 | |||||
| 0 | 000000011001101 | 0 | 000000001110011 | 1 | 111111100110011 |
A = 307 10 = 100 110 011 2 З = 91 10 = 1011011 2
[A] доп = 0 | 000000100110011
[-A] доп = 1 | 111111011001101
[C] доп = 0 | 000000001011011
[-C] доп = 1 | 111111110100101
| А + C | -A + C | |||
| + | 0 | 000000100110011 | + | 1 | 111111011001101 | |
| 0 | 000000001011011 | 0 | 000000001011011 | |||
| 0 | 000000110001110 | 1 | 111111100101000 | |||
| А + (- C) | -A + (- C) | |||
| + | 0 | 000000100110011 | + | 1 | 111111011001101 | |
| 1 | 111111110100101 | 1 | 111111110100101 | |||
| 0 | 000000011011000 | 1 | 111111001110010 |
Кількість логічних операцій може бути обчислена за формулою
| Для виконання логічних операцій, використовують таблиці істинності: Логічне додавання a Ú b | Логічне множення a & b | Логічне заперечення | Додавання за модулем 2 a Å b | ||||||||||
| a \ b | 1 | 0 | a \ b | 1 | 0 | a | a \ b | 1 | 0 | ||||
| 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | |||
| 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | |||
а) зробити логічне додавання чисел А і С:
| Ú | 0 | 000000100110011 |
| 0 | 000000001011011 | |
| 0 | 000000101111011 |
| & | 0 | 000000100110011 |
| 0 | 000000001011011 | |
| 0 | 000000000010011 |
| Å | 0 | 000000100110011 |
| 0 | 000000001011011 | |
| 0 | 000000101101000 |
| A | -A | ||
| 0 | 000000100110011 | 1 | 111111011001101 | Число | |
| 0 | 000001001100110 | 1 | 111110110011010 | Результат зсуву вліво |
| C | -C | ||
| 0 | 000000001011011 | 1 | 111111110100101 | Число | |
| 0 | 000000000101101 | 0 | 111111111010010 | Результат зсуву вправо |
| A | -A | ||
| 0 | 000000100110011 | 1 | 111111011001101 | Число | |
| 0 | 000010011001100 | 1 | 111101100110100 | Результат зсуву вліво на 2 біти |
| C | -C | ||
| 0 | 000000001011011 | 1 | 111111110100101 | Число | |
| 0 | 000000000010110 | 0 | 011111111101001 | Результат зсуву вправо на 2 біти |
| A | -A | ||
| 0 | 000000100110011 | 1 | 111111011001101 | Число | |
| 0 | 000001001100110 | 1 | 111110110011010 | Результат зсуву вліво |
| C | -C | ||
| 0 | 000000001011011 | 1 | 111111110100101 | Число | |
| 0 | 000000000101101 | 1 | 011111111010010 | Результат зсуву вправо |
Глава 2. Методи контролю роботи ЦА
2.1 Коригувальна здатність кодів
При роботі ЦА можуть відбутися ті або інші збої, що призводять до спотворення інформації. Тому при проектуванні ЦА повинні передбачатися кошти, що дозволяють контролювати, виявляти і виправляти виникаючі помилки. Вирішення всіх завдань контролю стає можливим тільки при наявності певної надмірності інформації, яка супроводжує основну інформацію. Інакше кажучи, при представленні числа в будь-якому коді, необхідно предусмотретьв цьому коді додаткові (контрольні) розряди.
Систематичний код - це код, який містить в собі інформаційні та контрольні розряди. До контрольних розряди записується деяка інформація про вихідний числі, тому систематичний код має надмірністю.
При цьому абсолютна надмірність буде виражатися кількістю контрольних розрядів - k, а відносна надмірність -
Поняття корегуючої здатності коду пов'язують з можливістю виявлення та виправлення помилки. Кількісно коригуюча здатність коду визначається імовірністю виявлення або виправлення помилки. Коригуюча здатність коду пов'язана поняттям кодового відстані.
Кодова відстань (Хемінгово відстань) d для кодових комбінацій A і B визначається як вага такої третьої комбінації, яка виходить складанням початкових комбінацій за модулем 2. Вага кодової комбінації V - це кількість одиниць містяться в кодової комбінації.
Наприклад, A = 100111001 і B = 011011100. Звідси ваги кодових комбінацій будуть рівні: V (A) = 5, V (B) = 5. Кодова комбінація C = A + B = 111100101, вага цієї кодової комбінації дорівнює V (C) = 6. Таким чином кодова відстань для A і B - d (A, B) = V (C) = 6.
У будь-якій позиційній системі числення мінімальне кодова відстань дорівнює 1. У теорії кодування показано, що систематичний код має здатність виявлення помилки лише тоді, коли код відстані для нього більше або дорівнює 2t. Отже,
2.2 Метод парності / непарності. Коди Хемінг
Якщо в математичному коді виділений один контрольний розряд, то до кожного бінарного числа додається один надлишковий розряд. До цього розряду записується 1 або 0 з такою умовою, щоб сума цифр за модулем 2 була дорівнює 0 для випадку парності або 1 для випадку непарності. Поява помилки в кодуванні обнружівается з порушення парності / непарності. При такому кодуванні допускається, що може виникнути тільки одна помилка.
Приклад реалізації методу парності:
Число | Контрольний розряд | Перевірка |
| 10101011 | 1 | 0 |
| 11001010 | 0 | 0 |
| 10010001 | 1 | 0 |
| 11001011 | 0 | 1 - помилка |
Збільшення надмірності призводить до того, що з'являється можливість не тільки виявити помилку, але і виправити її.
Наприклад: число 1000111011010101110010101 представимо за згаданою вище схемою, отримаємо:
| 1 | 0 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 1 | 0 | |
| 0 | 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 | 1 |
Код Хеммінга - біочний систематичний код, тобто складається з інформаційних та коригувальних символів, рассположенних за строго визначеною системою, що мають однакову довжину і завжди займають строго визначені місця в кодових комбінаціях.
При передачі коду може бути спотворений або не спотворений будь-який символ. Якщо довжина коду - n символів, то
Співвідношення n,
Таблиця 2.2.a
| n | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| 0 | 0 | 1 | 1 | 2 | 3 | 4 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 11 | |
| 1 | 2 | 2 | 3 | 3 | 3 | 3 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 4 | 5 |
Далі необхідно визначити на якій позиції повинні знаходитися контрольні коефіцієнти. Позиція контрольних коефіцієнтів - k в коді обчислюється за формулою -
Таблиця 2.2.c
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | Розряди коду Хеммінга |
| k1 | k2 | И4 | k3 | И3 | И2 | І1 | Призначення розрядів |
| 1 | 0 | 1 | 1 | Значення розряду |
Значення контрольних коефіцієнтів за правилом: якщо сума одиниць на перевірочних позиціях парна, то значення контрольного коефіцієнта дорівнює 0, у противному випадку - 1.
Таблиця 2.2.d
| Позиція контрольного коефіцієнта | Перевірочні позиції |
| 1 | 1, 3, 5, 7, 9, 11, 13 ... |
| 2 | 2, 3, 6, 7, 10, 11, 14 ... |
| 4 | 4, 5, 6, 7, 12, 13, 14 ... |
| 8 | 8, 9, 10, 11, 12, 13, 14 ... |
k 1 = 1 + 0 + 1 = 0;
k 2 = 1 + 1 + 1 = 1;
k 3 = 0 + 1 +1 = 0.
Отримаємо код Хеммінга 0110011 для передачі числа 11 10.
Тепер розглянемо приклад коригування отриманого кодованого в коді Хеммінга числа, в якому є збій. Отримали число 0110001. Для виправлення помилки необхідно визначити позицію, в якій стався збій. Для цього визначаємо значення контрольних коефіцієнтів, використовуючи таблицю 2.2.d:
k 1 = 0 + 1 + 0 + 1 = 0 - немає помилки;
k 2 = 1 + 1 + 0 + 1 = 1 - помилка;
k 3 = 0 + 0 +0 +1 = 1 - помилка.
Номер помилкового розряду співпадає з сумою позицій контрольних коефіцієнтів, що вказали на наявність помилки тобто 2 + 4 = 6. Для виправлення помилки досить інвертувати значення 6-го розряду.
Завдання. Побудувати код Хеммінга для числа А.
A = 307 10 = 100 110 011 2
Використовуючи таблицю 2.2.a отримуємо:
k 1 = 1 + 0 + 1 + 1 + 0 + 1 = 0;
k 2 = 1 + 0 + 1 + 0 + 0 = 0;
k 3 = 0 + 0 +1 + 1 + 1 = 1;
k 4 = 1 + 0 + 0 + 1 + 1 = 1.
Отримаємо код Хеммінга 0011001110011.
При передачі, отримали код з помилкою 0011001110111. Перевіряємо:
k 1 = 0 + 1 + 0 + 1 + 1 + 1 + 1 = 1; - помилка;
k 2 = 0 + 1 + 0 + 1 + 0 + 1 = 1; - помилка;
k 3 = 1 + 0 + 0 +1 + 1 + 1 = 0; - немає помилки;
k 4 = 1 + 1 + 0 + 1 + 1 + 1 = 1 - помилка.
Помилка знаходиться в розряді 1 + 2 + 8 = 11, інвертуємо 11-й розряд і отримуємо вихідний код Хеммінга.
2.3 Контроль за модулем
Контроль виконання арифметичних і логічних операцій можна здійснювати за допомогою контрольних кодів, що представляють собою залишки від ділення чисел на деякий модуль. Такий контроль називають контролем за модулем. Для двійкових чисел цей модуль зазвичай равер або більше 3. Розрізняють числової і цифровий контроль по модулю.
При числовому методі код заданого числа визначається як найменший позитивний залишок від ділення числа на обраний модуль. Наприклад, визначити контрольний код числа 160 по модулю 6. Для цього ділимо 160 на 6, отримуємо залишок - 4.
При цифровому методі контролю, контрольний код числа утворюється діленням суми цифр числа на обраний модуль. Наприклад, визначити контрольний код числа 160 по модулю 6. Сума цифр числа 160 дорівнює 7, ділимо її на 6. Отримаємо залишок 1, значить це, контроль числа 160 по модулю 6, при цифровому методі контролю.
Числовий метод контролю
Арифметичні операції можна уявити у вигляді послідовності наступних елементарних операцій: передача слова, зсув, взяття зворотного коду, складання.
Операцію зсуву можна представити як передачу слова з i-го розряду в (i + x) розряд. Тому, контроль зсуву можна здійснити за методом парності / непарності.
Контроль виконання арифметичних операцій: додавання, віднімання, множення можна здійснити методом контролю за модулем. Для цього застосовують формули:
K A = A mod P K B = B mod P
K A + B = (A + B) mod P = (K A + K B) mod P
K A * B = (A * B) mod P = (K A * K B) mod P
Наприклад, знайдемо контрольний код чисел A, B і контрольний код арифметичних операцій над ними, отримаємо:
Перевірка виконаних операцій:
K A + B = (8 + 3) mod 9 = 2 - немає помилки;
K A - B = (8 - 3) mod 9 = 5
K A * B = (8 * 3) mod 9 = 6 - немає помилки.
Завдання. Визначити контрольні коди чисел A і C за модулем P, а також контрольні коди суми A + C і різниці A - C.
До А = 307 mod 9 = 1;
K C = 91 mod 9 = 1;
K A + C = (307 +91) mod 9 = 398 mod 9 = 2; перевірка:
K A + C = (1 + 1) mod 9 = 2 mod 9 = 2 - немає помилки.
K A - C = (307-91) mod 9 = 216 mod 9 = 0; перевірка:
K A - C = (1 - 1) mod 9 = 0 mod 9 = 0 - немає помилки.
Цифровий метод контролю
Контроль виконання арифметичних операцій: додавання, віднімання, множення виконується за темже формулами, тільки при цифровому методі контролю, контрольний код числа утворюється діленням суми цифр числа на обраний модуль.
Завдання. Визначити контрольні коди чисел A і C за модулем P, а також контрольні коди суми A + C і різниці A - C.
До А = (3 +0 +7) mod 9 = 1;
K C = (9 +1) mod 9 = 1;
K A + C = (3 +0 +7 +9 +1) mod 9 = 20 mod 9 = 2; перевірка:
K A + C = (1 + 1) mod 9 = 2 mod 9 = 2 - немає помилки.
K A - C = (3 +0 +7-9-1) mod 9 = 0 mod 9 = 0; перевірка:
K A - C = (1 - 1) mod 9 = 0 mod 9 = 0 - немає помилки.
Глава 3. Побудова алгоритму реалізації чисельного методу «швидкої сортування»
3.1 Математичне опис методу
Алгоритм сортування К. Хоорі називають сортуванням з поділом або «швидкої сортуванням». В основу алгоритму покладено метод послідовного дроблення масиву на частини.
Алгоритм «швидкого сортування» можна проаналізувати на прикладі. Нехай дано масив M [i] = (9, 11, 12, 3, 19, 1, 5, 17, 10, 18, 3, 19, 17, 9, 12, 20, 20, 19, 2, 5). Після першого виклику процедури QuickS у вихідному масиві буде визначено його середина (10-й елемент) і змінної X присвоєно значення m [10], тобто 18. Після цього масив ділиться на дві частини. Далі виконується обмін елементами за наступним правилом:
При перегляді лівій частині масиву зліва направо виполниется пошук такого елемента масиву, що M [i]> X, потім при перегляді правій частині справа наліво відшукується такий елемент, що M [i] <X. Виконується обмін місцями даних елементів, поки всі елементи ліворуч від середини, що задовольняють умові M [i]> X, не будуть обмінені з елементами, рассположеннимі праворуч від середини і задовольняють умові M [i] <X. У результаті цього отримаємо масив з двох частин такого вигляду:
9, 11, 12, 3, 19, 1, 5, 17, 10, 18, 3, 19, 17, 9, 12, 20, 20, 19, 2, 5 Число ітерацій = 1
19, 20, 12, 3, 19, 1, 5, 17, 10, 18, 3, 19, 17, 9, 12, 20, 11, 9, 2, 5 Число ітерацій = 2
19, 20, 20, 3, 19, 1, 5, 17, 10, 18, 3, 19, 17, 9, 12, 12, 11, 9, 2, 5 Число ітерацій = 3
19, 20, 20, 19, 19, 1, 5, 17, 10, 18, 3, 3, 17, 9, 12, 12, 11, 9, 2, 5 Число ітерацій = 4
19, 20, 20, 19, 19, 18, 5, 17, 10, 1, 3, 3, 17, 9, 12, 12, 11, 9, 2, 5 Число ітерацій = 5
Далі ліва частина в свою чергу дробиться на дві частини, і викликається процедура для сортування лівої частини (з 1-го по 6-й елемент)
20, 20, 19, 19, 19, 18, 5, 17, 10, 1, 3, 3, 17, 9, 12, 12, 11, 9, 2, 5 Число ітерацій = 6
20, 20, 19, 19, 19, 18, 5, 17, 10, 1, 3, 3, 17, 9, 12, 12, 11, 9, 2, 5 Число ітерацій = 7
Після того як ліва частина масиву відсортована, знову рекурсивно викликається процедура, в якій визначається середина даної частини масиву, і виконується обмін елементів. Масив стає таким:
20, 20, 19, 19, 19, 18, 5, 17, 10, 1, 3, 3, 17, 9, 12, 12, 11, 9, 2, 5 Число ітерацій = 8
20, 20, 19, 19, 19, 18, 5, 17, 10, 1, 3, 3, 17, 9, 12, 12, 11, 9, 2, 5 Число ітерацій = 9
Далі знову рекурсивно викликається процедура для сортування, поки в кожній з частин залишиться по одному елементу.
Потім рекурсивно викликається процедура для аналогічної сортування правій частині (з 7-го по 13-й елемент). Результат послідовних етапів сортування масиву відображається так:
20, 20, 19, 19, 19, 18, 5, 17, 10, 1, 3, 3, 17, 9, 12, 12, 11, 9, 2, 5 Число ітерацій = 10
20, 20, 19, 19, 19, 18, 17, 17, 10, 1, 3, 3, 5, 9, 12, 12, 11, 9, 2, 5 Число ітерацій = 11
20, 20, 19, 19, 19, 18, 17, 17, 10, 1, 3, 3, 5, 9, 12, 12, 11, 9, 2, 5 Число ітерацій = 12
20, 20, 19, 19, 19, 18, 17, 17, 10, 9, 3, 3, 5, 9, 12, 12, 11, 1, 2, 5 Число ітерацій = 13
20, 20, 19, 19, 19, 18, 17, 17, 10, 9, 11, 3, 5, 9, 12, 12, 3, 1, 2, 5 Число ітерацій = 14
20, 20, 19, 19, 19, 18, 17, 17, 10, 9, 11, 12, 5, 9, 12, 3, 3, 1, 2, 5 Число ітерацій = 15
20, 20, 19, 19, 19, 18, 17, 17, 10, 9, 11, 12, 12, 9, 5, 3, 3, 1, 2, 5 Число ітерацій = 16
20, 20, 19, 19, 19, 18, 17, 17, 10, 9, 11, 12, 12, 9, 5, 3, 3, 1, 2, 5 Число ітерацій = 17
20, 20, 19, 19, 19, 18, 17, 17, 12, 9, 11, 12, 10, 9, 5, 3, 3, 1, 2, 5 Число ітерацій = 18
20, 20, 19, 19, 19, 18, 17, 17, 12, 12, 11, 9, 10, 9, 5, 3, 3, 1, 2, 5 Число ітерацій = 19
20, 20, 19, 19, 19, 18, 17, 17, 12, 12, 11, 9, 10, 9, 5, 3, 3, 1, 2, 5 Число ітерацій = 20
20, 20, 19, 19, 19, 18, 17, 17, 12, 12, 11, 9, 10, 9, 5, 3, 3, 1, 2, 5 Число ітерацій = 21
20, 20, 19, 19, 19, 18, 17, 17, 12, 12, 11, 10, 9, 9, 5, 3, 3, 1, 2, 5 Число ітерацій = 22
20, 20, 19, 19, 19, 18, 17, 17, 12, 12, 11, 10, 9, 9, 5, 5, 3, 1, 2, 3 Число ітерацій = 23
20, 20, 19, 19, 19, 18, 17, 17, 12, 12, 11, 10, 9, 9, 5, 5, 3, 1, 2, 3 Число ітерацій = 24
20, 20, 19, 19, 19, 18, 17, 17, 12, 12, 11, 10, 9, 9, 5, 5, 3, 1, 2, 3 Число ітерацій = 25
20, 20, 19, 19, 19, 18, 17, 17, 12, 12, 11, 10, 9, 9, 5, 5, 3, 3, 2, 1 Число ітерацій = 26
Як видно з прикладу, даний масив буде відсортований за 26 ітерацій методом «швидкої сортування». Той же масив відсортований лінійним методом, буде відсортований за 190 ітерацій, бульбашковим методом за 170 ітерацій. Як видно з наведених прикладів, алгоритм «швидкого сортування» дає кращі результати.
3.2 Таблиця використовуваних змінних
Примітка: так як процедура сортування масиву - рекурсія, то змінні i, j, X - повинні бути локальними.
Висновок
У процесі виконання курсової роботи, я дізнався як представляються дані в ЦА, навчився переводити числа з однієї системи числення в іншу, навчився представляти числа у машинному коді і виконувати над ними арифметичні та логічні операції. При вивченні методу контролю роботи ЦА, я навчився будувати код Хеммінга, а також виявляти помилки в даних, закодованих кодом Хеммінга. При вивченні реалізації алгоритму чисельного методу «швидкої сортування», я побачив перевагу даного методу у відмінності від інших методів сортування.
Таким чином, при виконанні курсової роботи, я отримав нові знання та навички для своєї професійної діяльності.
Список використаних джерел
1. Пономарьов В.С., Красніков В.В. Методичні вказівки з курсу «Організація і функціонування ЕОМ і систем». Ч.1. Арифметичні основи ЕОМ. ДДТУ, 1996.
2. Інтернет-ресурс «Системи числення: двійкова, вісімковий, шестнадцатірічное»
http://www.pascalstudy.narod.ru/tems/pas_5.html
3. Коштоев В.В., Кіпіані К.К. Навчальний посібник «Основи прикладної теорії цифрових автоматів» Тбілісі, 1998.
4. Інтернет-ресурс «Теоретичні основи інформатики. Коди Хеммінга »
http://de.uspu.ru/Informatics/Metodes/DPP/F/08/1/glavs/5/564.htm
5. Інтернет-ресурс «Контроль за модулем арифметичних операцій у десятковій і двійкової СС»
http://distance-onu.by.ru/metod/11.htm
6. Інтернет-ресурс «Глава 3. Вирази та Операції. Побітові операції зсуву »
http://pyramidin.narod.ru/jscript/coreguide15/expr.html
7. Turbo Pascal для школярів: Учеб. посібник .- 3-е доп.ізд .- М.: Фінанси і статистика, 2002.-528 с.
Додаток 1. Блок-схема алгоритму
A = 307 10 = 100 110 011 2
Використовуючи таблицю 2.2.a отримуємо:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | Розряди коду Хеммінга |
| k1 | k2 | И9 | k3 | І8 | И7 | І6 | k4 | И5 | И4 | И3 | И2 | І1 | Призначення розрядів |
| 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | Значення розряду |
k 2 = 1 + 0 + 1 + 0 + 0 = 0;
k 3 = 0 + 0 +1 + 1 + 1 = 1;
k 4 = 1 + 0 + 0 + 1 + 1 = 1.
Отримаємо код Хеммінга 0011001110011.
При передачі, отримали код з помилкою 0011001110111. Перевіряємо:
k 1 = 0 + 1 + 0 + 1 + 1 + 1 + 1 = 1; - помилка;
k 2 = 0 + 1 + 0 + 1 + 0 + 1 = 1; - помилка;
k 3 = 1 + 0 + 0 +1 + 1 + 1 = 0; - немає помилки;
k 4 = 1 + 1 + 0 + 1 + 1 + 1 = 1 - помилка.
Помилка знаходиться в розряді 1 + 2 + 8 = 11, інвертуємо 11-й розряд і отримуємо вихідний код Хеммінга.
2.3 Контроль за модулем
Контроль виконання арифметичних і логічних операцій можна здійснювати за допомогою контрольних кодів, що представляють собою залишки від ділення чисел на деякий модуль. Такий контроль називають контролем за модулем. Для двійкових чисел цей модуль зазвичай равер або більше 3. Розрізняють числової і цифровий контроль по модулю.
При числовому методі код заданого числа визначається як найменший позитивний залишок від ділення числа на обраний модуль. Наприклад, визначити контрольний код числа 160 по модулю 6. Для цього ділимо 160 на 6, отримуємо залишок - 4.
При цифровому методі контролю, контрольний код числа утворюється діленням суми цифр числа на обраний модуль. Наприклад, визначити контрольний код числа 160 по модулю 6. Сума цифр числа 160 дорівнює 7, ділимо її на 6. Отримаємо залишок 1, значить це, контроль числа 160 по модулю 6, при цифровому методі контролю.
Числовий метод контролю
Арифметичні операції можна уявити у вигляді послідовності наступних елементарних операцій: передача слова, зсув, взяття зворотного коду, складання.
Операцію зсуву можна представити як передачу слова з i-го розряду в (i + x) розряд. Тому, контроль зсуву можна здійснити за методом парності / непарності.
Контроль виконання арифметичних операцій: додавання, віднімання, множення можна здійснити методом контролю за модулем. Для цього застосовують формули:
K A = A mod P K B = B mod P
K A + B = (A + B) mod P = (K A + K B) mod P
K A * B = (A * B) mod P = (K A * K B) mod P
Наприклад, знайдемо контрольний код чисел A, B і контрольний код арифметичних операцій над ними, отримаємо:
| A | B | A + B | A - B | A * B | Арифметичні операції над числами |
| 89 | 57 | 146 | 33 | 5073 | Значення чисел |
| 8 | 3 | 2 | 6 | 6 | Контроль за модулем 9 |
|
K A - B = (8 - 3) mod 9 = 5
K A * B = (8 * 3) mod 9 = 6 - немає помилки.
Завдання. Визначити контрольні коди чисел A і C за модулем P, а також контрольні коди суми A + C і різниці A - C.
До А = 307 mod 9 = 1;
K C = 91 mod 9 = 1;
K A + C = (307 +91) mod 9 = 398 mod 9 = 2; перевірка:
K A + C = (1 + 1) mod 9 = 2 mod 9 = 2 - немає помилки.
K A - C = (307-91) mod 9 = 216 mod 9 = 0; перевірка:
K A - C = (1 - 1) mod 9 = 0 mod 9 = 0 - немає помилки.
Цифровий метод контролю
Контроль виконання арифметичних операцій: додавання, віднімання, множення виконується за темже формулами, тільки при цифровому методі контролю, контрольний код числа утворюється діленням суми цифр числа на обраний модуль.
Завдання. Визначити контрольні коди чисел A і C за модулем P, а також контрольні коди суми A + C і різниці A - C.
До А = (3 +0 +7) mod 9 = 1;
K C = (9 +1) mod 9 = 1;
K A + C = (3 +0 +7 +9 +1) mod 9 = 20 mod 9 = 2; перевірка:
K A + C = (1 + 1) mod 9 = 2 mod 9 = 2 - немає помилки.
K A - C = (3 +0 +7-9-1) mod 9 = 0 mod 9 = 0; перевірка:
K A - C = (1 - 1) mod 9 = 0 mod 9 = 0 - немає помилки.
Глава 3. Побудова алгоритму реалізації чисельного методу «швидкої сортування»
3.1 Математичне опис методу
Алгоритм сортування К. Хоорі називають сортуванням з поділом або «швидкої сортуванням». В основу алгоритму покладено метод послідовного дроблення масиву на частини.
Алгоритм «швидкого сортування» можна проаналізувати на прикладі. Нехай дано масив M [i] = (9, 11, 12, 3, 19, 1, 5, 17, 10, 18, 3, 19, 17, 9, 12, 20, 20, 19, 2, 5). Після першого виклику процедури QuickS у вихідному масиві буде визначено його середина (10-й елемент) і змінної X присвоєно значення m [10], тобто 18. Після цього масив ділиться на дві частини. Далі виконується обмін елементами за наступним правилом:
При перегляді лівій частині масиву зліва направо виполниется пошук такого елемента масиву, що M [i]> X, потім при перегляді правій частині справа наліво відшукується такий елемент, що M [i] <X. Виконується обмін місцями даних елементів, поки всі елементи ліворуч від середини, що задовольняють умові M [i]> X, не будуть обмінені з елементами, рассположеннимі праворуч від середини і задовольняють умові M [i] <X. У результаті цього отримаємо масив з двох частин такого вигляду:
9, 11, 12, 3, 19, 1, 5, 17, 10, 18, 3, 19, 17, 9, 12, 20, 20, 19, 2, 5 Число ітерацій = 1
19, 20, 12, 3, 19, 1, 5, 17, 10, 18, 3, 19, 17, 9, 12, 20, 11, 9, 2, 5 Число ітерацій = 2
19, 20, 20, 3, 19, 1, 5, 17, 10, 18, 3, 19, 17, 9, 12, 12, 11, 9, 2, 5 Число ітерацій = 3
19, 20, 20, 19, 19, 1, 5, 17, 10, 18, 3, 3, 17, 9, 12, 12, 11, 9, 2, 5 Число ітерацій = 4
19, 20, 20, 19, 19, 18, 5, 17, 10, 1, 3, 3, 17, 9, 12, 12, 11, 9, 2, 5 Число ітерацій = 5
Далі ліва частина в свою чергу дробиться на дві частини, і викликається процедура для сортування лівої частини (з 1-го по 6-й елемент)
20, 20, 19, 19, 19, 18, 5, 17, 10, 1, 3, 3, 17, 9, 12, 12, 11, 9, 2, 5 Число ітерацій = 6
20, 20, 19, 19, 19, 18, 5, 17, 10, 1, 3, 3, 17, 9, 12, 12, 11, 9, 2, 5 Число ітерацій = 7
Після того як ліва частина масиву відсортована, знову рекурсивно викликається процедура, в якій визначається середина даної частини масиву, і виконується обмін елементів. Масив стає таким:
20, 20, 19, 19, 19, 18, 5, 17, 10, 1, 3, 3, 17, 9, 12, 12, 11, 9, 2, 5 Число ітерацій = 8
20, 20, 19, 19, 19, 18, 5, 17, 10, 1, 3, 3, 17, 9, 12, 12, 11, 9, 2, 5 Число ітерацій = 9
Далі знову рекурсивно викликається процедура для сортування, поки в кожній з частин залишиться по одному елементу.
Потім рекурсивно викликається процедура для аналогічної сортування правій частині (з 7-го по 13-й елемент). Результат послідовних етапів сортування масиву відображається так:
20, 20, 19, 19, 19, 18, 5, 17, 10, 1, 3, 3, 17, 9, 12, 12, 11, 9, 2, 5 Число ітерацій = 10
20, 20, 19, 19, 19, 18, 17, 17, 10, 1, 3, 3, 5, 9, 12, 12, 11, 9, 2, 5 Число ітерацій = 11
20, 20, 19, 19, 19, 18, 17, 17, 10, 1, 3, 3, 5, 9, 12, 12, 11, 9, 2, 5 Число ітерацій = 12
20, 20, 19, 19, 19, 18, 17, 17, 10, 9, 3, 3, 5, 9, 12, 12, 11, 1, 2, 5 Число ітерацій = 13
20, 20, 19, 19, 19, 18, 17, 17, 10, 9, 11, 3, 5, 9, 12, 12, 3, 1, 2, 5 Число ітерацій = 14
20, 20, 19, 19, 19, 18, 17, 17, 10, 9, 11, 12, 5, 9, 12, 3, 3, 1, 2, 5 Число ітерацій = 15
20, 20, 19, 19, 19, 18, 17, 17, 10, 9, 11, 12, 12, 9, 5, 3, 3, 1, 2, 5 Число ітерацій = 16
20, 20, 19, 19, 19, 18, 17, 17, 10, 9, 11, 12, 12, 9, 5, 3, 3, 1, 2, 5 Число ітерацій = 17
20, 20, 19, 19, 19, 18, 17, 17, 12, 9, 11, 12, 10, 9, 5, 3, 3, 1, 2, 5 Число ітерацій = 18
20, 20, 19, 19, 19, 18, 17, 17, 12, 12, 11, 9, 10, 9, 5, 3, 3, 1, 2, 5 Число ітерацій = 19
20, 20, 19, 19, 19, 18, 17, 17, 12, 12, 11, 9, 10, 9, 5, 3, 3, 1, 2, 5 Число ітерацій = 20
20, 20, 19, 19, 19, 18, 17, 17, 12, 12, 11, 9, 10, 9, 5, 3, 3, 1, 2, 5 Число ітерацій = 21
20, 20, 19, 19, 19, 18, 17, 17, 12, 12, 11, 10, 9, 9, 5, 3, 3, 1, 2, 5 Число ітерацій = 22
20, 20, 19, 19, 19, 18, 17, 17, 12, 12, 11, 10, 9, 9, 5, 5, 3, 1, 2, 3 Число ітерацій = 23
20, 20, 19, 19, 19, 18, 17, 17, 12, 12, 11, 10, 9, 9, 5, 5, 3, 1, 2, 3 Число ітерацій = 24
20, 20, 19, 19, 19, 18, 17, 17, 12, 12, 11, 10, 9, 9, 5, 5, 3, 1, 2, 3 Число ітерацій = 25
20, 20, 19, 19, 19, 18, 17, 17, 12, 12, 11, 10, 9, 9, 5, 5, 3, 3, 2, 1 Число ітерацій = 26
Як видно з прикладу, даний масив буде відсортований за 26 ітерацій методом «швидкої сортування». Той же масив відсортований лінійним методом, буде відсортований за 190 ітерацій, бульбашковим методом за 170 ітерацій. Як видно з наведених прикладів, алгоритм «швидкого сортування» дає кращі результати.
3.2 Таблиця використовуваних змінних
| Ім'я змінної | Тип змінної | Опис змінної |
| M [i] | Цілий / Речовий | Сортований масив чисел |
| i j | Цілий | Використовуються в циклі при зверненні до елементу масиву |
| X | Цілий / Речовий | Значення елемента в середині масиву |
| First Last | Цілий | Межі сортованого масиву |
| tmp | Цілий / Речовий | Тимчасове зберігання значення елемента масиву при обміні |
Висновок
У процесі виконання курсової роботи, я дізнався як представляються дані в ЦА, навчився переводити числа з однієї системи числення в іншу, навчився представляти числа у машинному коді і виконувати над ними арифметичні та логічні операції. При вивченні методу контролю роботи ЦА, я навчився будувати код Хеммінга, а також виявляти помилки в даних, закодованих кодом Хеммінга. При вивченні реалізації алгоритму чисельного методу «швидкої сортування», я побачив перевагу даного методу у відмінності від інших методів сортування.
Таким чином, при виконанні курсової роботи, я отримав нові знання та навички для своєї професійної діяльності.
Список використаних джерел
1. Пономарьов В.С., Красніков В.В. Методичні вказівки з курсу «Організація і функціонування ЕОМ і систем». Ч.1. Арифметичні основи ЕОМ. ДДТУ, 1996.
2. Інтернет-ресурс «Системи числення: двійкова, вісімковий, шестнадцатірічное»
http://www.pascalstudy.narod.ru/tems/pas_5.html
3. Коштоев В.В., Кіпіані К.К. Навчальний посібник «Основи прикладної теорії цифрових автоматів» Тбілісі, 1998.
4. Інтернет-ресурс «Теоретичні основи інформатики. Коди Хеммінга »
http://de.uspu.ru/Informatics/Metodes/DPP/F/08/1/glavs/5/564.htm
5. Інтернет-ресурс «Контроль за модулем арифметичних операцій у десятковій і двійкової СС»
http://distance-onu.by.ru/metod/11.htm
6. Інтернет-ресурс «Глава 3. Вирази та Операції. Побітові операції зсуву »
http://pyramidin.narod.ru/jscript/coreguide15/expr.html
7. Turbo Pascal для школярів: Учеб. посібник .- 3-е доп.ізд .- М.: Фінанси і статистика, 2002.-528 с.
Додаток 1. Блок-схема алгоритму