Тема: розв‘язування задач на визначення довжини двійкового коду даних різних типів.

Мета: навчитись розв'язувати задачі на визначення довжини двійкового коду.

Обладнання: ПК зі встановленою ОС і набір файлів для проведення замірів.

Структура уроку

1. Організаційний момент
2. Актуалізація опорних знань
3. Вивчення нового матеріалу
4. Інструктаж з ТБ
5. Закріплення вивченого матеріалу
6. Підбиття підсумків
7. Домашнє завдання

Хід уроку

1. Організаційний момент
Вітання з класом. Перевірка присутності і готовності учнів до уроку.

2. Актуалізація опорних знань

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

У передаванні (поширенні) інформації беруть участь дві сторони:

• джерело — людина або пристрій, що передає інформацію;
• приймач — людина або пристрій, який її отримує.

Розмовляючи, ми передаємо один одному інформацію. У ході технічного прогресу люди придумали багато пристроїв для передачі інформації: телевізор, радіо, телеграф, телефон, ЕОМ.

Кодування повідомлень — це перетворення повідомлень без зміни його змісту на інший вигляд за допомогою певних правил.

Код — це набір правил перетворення для кодування.

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

Для подання та опрацювання інформації в комп’ютері використовують двійкові коди, що містять лише два символи — 0 і 1.

Біт — найменша одиниця двійкового коду (0 або 1).

Байт — це послідовність з 8 бітів.

Загальна кількість різних комбінацій двійкових значень у байті дорівнює 2⁸=256.

Поряд з бітами і байтами використовують і такі одиниці вимірювання інформаційного об’єму повідомлення:

• 1 Кбайт (один кілобайт) = 2¹⁰ байт = 1024 байт;
• 1 Мбайт (один мегабайт) = 2²⁰ байт = 1024 Кбайт;
• 1 Гбайт (один гігабайт) = 2³⁰ байт = 1024 Мбайт.

Для кодування різних символів та для їх зберігання в запам’ятовуючих пристроях комп’ютера найчастіше використовують американський стандартний код для обміну інформацією АSCII — певну стандартну таблицю кодування знаків.

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

3. Вивчення нового матеріалу

Інформаційним об’ємом повідомлення називають кількість бітів у цьому повідомленні.

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

Кодова відстань Хеммінга між двома двійковими кодами (однакової довжини) — це кількість відмінних бітів у цих кодах.

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

Наприклад, коди 01101 і 11001 відрізняються у 2 бітах (першому й третьому), тому кодова відстань між ними дорівнює 2 — кількості відмінних від 0 бітів такого коду:
10100 = 01101 xor 11001.

З властивостей дії додавання та залежності остачі суми лише від суми остач випливає:

• побітна сума однакових кодів дорівнює 0;

• подвійне побітне додавання одного й того самого коду є тотожним перетворенням, тобто нічого не змінює.

Тому щоб знайти усі (двійкові) коди, віддалені від даного на певну відстань k, потрібно знайти побітні суми його з усіма кодами, віддаленими від нульового (суцільні нулі) на відстань k, тобто з усіма кодами, що містять k одиниць у своєму записі, а решта — нулі. Для кодів довжини n кількість потрібних кодів дорівнює кількості варіантів вибору k бітів з n для заповнення одиницями:

Тут k = 1 · 2 · 3 · … · (k – 1) · k. Наприклад, при k = 3, n = 5 така кількість дорівнює 5!/(3!∙2!) = 120/(6∙2) = 10. Запишемо першому рядку таблиці всі ці 10 кодів, у другому рядку — один і той самий код, наприклад 01001, у третьому рядку — побітну суму двох елементів у клітинках згори. Тоді третій рядок таблиці міститиме усі ті коди, які розташовані від коду 01001 на відстані 3.

З метою завадити спотворенню коду (наприклад, при передаванні повідомлень) коди роблять надмірними, додаючи допоміжну інформацію для виявлення можливого спотворення початкового повідомлення. Наприклад, парність суми вмісту певної кількості бітів.

Надмірність двійкового коду довжини n, яким можна закодувати 2ⁿ символів, при кодуванні лише 2^k символів обчислюють за такою формулою:

Наприклад, при відведенні по одному байту (8 бітів) на кожний з 64 символів (64 = 2⁶) надмірність такого двійкового коду дорівнює:

4. Інструктаж з ТБ
5. Закріплення вивченого матеріалу

Виконання всіх наступних завдань оформити у зошиті, який потрібно здати вчителю після виконання роботи.

Завдання 1. Визначити кодову відстань між двійковими кодами А і В (вказує вчитель) і записати всі коди такої самої довжини, розташовані від коду А на (кодовій) відстані 2.

Завдання 2. Абетка деякої мови налічує 64 символи. На кодування кожної літери відведено 1 байт. Визначити надмірність такого коду.

Завдання 3. Визначити розміри текстових файлів (формат txt) при кодування ANSII та UTF-8, що містять цифри 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 у вказаному порядку і далі з повторенням. Назви файлів: 1, 2, 4, 8, 16, 32, 64 вказують на кількість змістовних символів-цифр і спосіб кодування. Даними дослідження заповнити такі таблиці.

Зробити висновки з проведеного дослідження.

Завдання 4. Визначити розміри графічних файлів формату bmp, png, jpg. Кожний файл містить лише чорний квадрат розміру j × j при j = 1, 2, 4, 8, 16, 32, 64 (назва файлу). Даними дослідження заповнити такі таблиці.

Зробити висновки з проведеного дослідження.

Завдання 5. Визначити, скільки місця потрібно, щоб зберегти текст деякої книжки обсягом 300 сторінок за умови, що сторінка книжки має у середньому 40 рядків тексту по 66 символів.

6. Підбиття підсумків уроку
Виставлення оцінок.

7. Домашнє завдання
Повторити вивчений матеріал. Доробити незавершені завдання.

Текст упорядкував Єршов Олег Володимирович, вчитель інформатики гімназії № 283 Деснянського району міста Києва, під час виконання випускної роботи на курсах підвищення кваліфікації з 17.04.2014 по 04.04.2014.