Кодування та моделювання

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

• Дорожні знаки — це зображення, де кодується така інформація, як «в’їзд заборонено» або «поступіться дорогою».
  • Двійкова система кодує числа у вигляді послідовності нулів і одиниць.
  • Ми можемо кодувати кольори на зображенні за допомогою тріо чисел, що характеризують пропорцію червоного, зеленого та синього компонентів.
  • Азбука Морзе кодує букви за допомогою крапок і тире.

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

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

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

Цей розділ ілюструє основні принципи кодування на простих прикладах:

• Кодування інформації за допомогою зображення –⁠ дорожні знаки, туристичні знаки, іконки, символи для прогнозу погоди
• Символи Emoji та Unicode – кодування тексту, символів і маленьких значків
• Кодування інформації за допомогою тексту та іншим способом – погляд на текст (та інші способи запису інформації) як на спосіб кодування інформації

У наступних темах більш детально обговорюються технічні принципи кодування:

• Кодування тексту та шифрування
• Кодування зображення та звуку
• Кодування чисел

Нам потрібно якось записувати (кодувати) інформацію про світ. Типовий спосіб такого коду — письмовий. Наприклад, якщо ми маємо піти до стоматолога у вівторок о 9:00 ранку, ми кодуємо цю інформацію в щоденник словом «стоматолог». Але це не єдиний можливий шлях. Замість того, щоб писати слово, ми могли б намалювати в щоденнику похід до стоматолога.

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

До типових прикладів кодування інформації за допомогою зображень належать:

• дорожні знаки
• маркери на туристичних мапах
• символи, що позначають прогноз погоди
• позначення видів спорту на Олімпійських іграх
• іконки в комп’ютерних програмах

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

Способи кодування за допомогою тексту

Існує багато різних способів кодування інформації в текст. Можливо, замість простого пароля стоматолог ми могли б написати Не забувайте, що вам завтра потрібно піти до стоматолога на огляд. Часто достатньо записати лише важливу інформацію, решту зазвичай можна зрозуміти за контекстом чи на основі наших знань про світ. Як наслідок, код (запис) часто набагато лаконічніший, ніж інформація, яку він позначає.

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

Інші способи кодування

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

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

Базове кодування тексту використовувалося ще до появи комп’ютерів. Наприклад, азбука Морзе використовувалася для передачі повідомлень по телеграфу, а шрифт Брайля кодує текст, який читається на дотик. Для текстового кодування в комп’ютерах використовуються методи на основі двійкових чисел (нулів і одиниць).

Кодування не шифрує повідомлення. Якщо ми напишемо повідомлення PES азбукою Морзе (.–.|.|…), то будь-хто, хто знає цей код, зможе легко прочитати повідомлення. Щоб зберегти повідомлення в секреті, використовується шифрування. Люди люблять тримати речі в таємниці, тому шифрування використовується майже так само довго, як письмо. Уже в давнину широко використовувався, наприклад, добре відомий шифр Цезаря. Шифрування багато разів відігравало важливу роль в історії. Так, однією з ключових подій Другої світової війни став злам німецької шифрувальної машини Enigma.

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

Ви можете практикувати тему шифрування кількома способами:

• Базові шифри – основні принципи шифрування (транспонування, підстановка), проілюстровані простими прикладами.
• Шифри з ідеєю – ці шифри не використовуються для практичних цілей, але вони добре послужать для тренування мислення та перевірки основних криптоаналітичних навичок.
• Шифрування: основні поняття та принципи – більш просунута тема, у якій детальніше розглядаються методи використання шифрування та основні концепції.

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

• Азбука Морзе присвоює кожній літері код, що складається з крапок і тире. Раніше він використовувався в основному для передачі інформації за допомогою телеграфу.
• У Міжнародному Кодексі Сигналів кожна літера має свій прапор. Текст закодовано у вигляді серії прапорів.
• У прапорцевій сигналізації відповідна людина кодує літери, використовуючи різні положення рук, тримаючи кольорові прапорці. Як і алфавіт військово-морського прапора, він використовується, наприклад, серед моряків для зв’язку на великі відстані.
• Шрифт Брайля кодує літери за допомогою нерівностей у сітці 2×3. Цей шрифт призначено для людей із вадами зору для читання на дотик.
• Комп’ютери зберігають літери за допомогою числових кодів. Окрема тема стосується кодування тексту в комп’ютерах.

У комп’ютері вся інформація зберігається у вигляді нулів і одиниць. Щоб зберігати текстову інформацію, нам потрібне кодування, яке перетворює текст на нулі та одиниці. У 60-х роках ХХ століття для цього була створена таблиця ASCII, яка присвоювала символам числа від 0 до 255, а потім ці числа записували у двійковій системі в один байт.

Однак ASCII дозволяло кодувати лише літери англійського алфавіту та деякі інші базові символи. Тому пізніше був розроблений стандарт Unicode, який дозволяє писати не лише основні літери, а й літери інших світових алфавітів та багато інших символів (як-от, символ сніговика: ☃). Ви можете дізнатися, які інші символи є в Unicode тут. У той час як Unicode призначає цифри символам, різні кодування (наприклад, UTF-8) визначають, як конвертувати ці числа в одиниці та нулі для збереження на комп’ютері.

Напр., Unicode кодує сніговика як число 2603 у шістнадцятковій системі. UTF-8 кодує це число у три байти зі значеннями 11 100 010, 10 011 000 і 10 000 011.

Транспозиційні шифри

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

• написання задом наперед (ДИНОЗАВР → РВАЗОНИД)
• написання через одну літеру (ДИНОЗАВР → ДЗИАНВОР)
• заміна сусідніх літер (ДИНОЗАВР → ИДОНАЗРВ)

Існують також більш складні шифри транспонування, які дозволяють шифрувати за допомогою пароля.

Шифри підстановки

З іншого боку, шифри підстановки зберігають порядок літер, але змінюють їхню форму. Базовий шифр заміни — це зсув у алфавіті (також званий шифром Цезаря), коли літери замінюються іншими літерами, наприклад, при зсуві на одну ми шифруємо ЛЬВІВ → МЮГЇГ (Л змінюється на М, Ь змінюється на Ю і так далі). Більш складним прикладом шифру підстановки є шифр Віженера.

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

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

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

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

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

Звук кодується як послідовність амплітуд (відхилень) звукового сигналу.

У растровій графіці зображення зберігаються у вигляді сітки пікселів. Пікселі – це точки, які мають задане положення на зображенні та колір. Ми кодуємо кольори у пікселях певним заздалегідь визначеним способом, наприклад, часто використовується модель RGB. Чим дрібніша сітка (чим більше пікселів містить зображення), тим якіснішим і детальнішим буде зображення. Оскільки пікселі не можна далі розділити, у міру збільшення растрового зображення пікселі також будуть збільшені, а якість буде втрачено. На малюнку ми бачимо, як можна зберегти зображення кола на невеликій кількості пікселів.

Глибина кольору – це кількість кольорів, яку може мати один піксель. Чим більша глибина кольору, тим більше кольорів ми маємо, і зображення може бути вищої якості. На малюнку показано різницю, коли доступні 2 кольори, 4 кольори та 256 кольорів.

Розмір растрового зображення визначається кількістю пікселів. Зображення 1024 × 1024 містить 1024 \cdot 1024 (приблизно один мільйон) пікселів і має розмір 1 Mpx (мегапіксель). Роздільна здатність – це значення, яке вказує, наскільки детальним є зображення. Воно надається в одиницях DPI (dots per inch, тобто точок на дюйм).

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

Векторні зображення часто зберігаються у форматі SVG. Текстове представлення простої форми у форматі SVG може виглядати так:

<circle cx="60" cy="60" r="55" fill="green" />

Спочатку ми визначаємо тип об’єкта: circle означає коло англійською мовою. Нижче наведено різні параметри, які точно визначають, як має виглядати це коло. Параметри cx і cy визначають положення центра кола в координатах (60, 60) на зображенні. Параметр r визначає радіус кола, а колір заливки вказано як зелений у параметрі fill. Таким чином, відтворене зображення буде виглядати так:

У форматі SVG можна закодувати багато інших типів об’єктів, наприклад rect (прямокутник), polygon (багатокутник) або line (лінія). Для кожного типу об’єкта ми задаємо різні параметри: наприклад, визначаємо розмір прямокутника за його висотою та шириною. Однак, якщо ми збираємося створювати власні векторні зображення, не обов’язково писати все текстом – є комп’ютерні програми, які дозволять нам працювати лише з об’єктами і писатимуть текстовий код за нас.

Існує 2 основних типи кодування зображень: векторна та растрова графіка. Растрові зображення складаються з пікселів (кольорових крапок), векторні зображення складаються з геометричних об’єктів. Формати, що використовують растрову графіку: BMP, JPG, PNG і GIF. Найбільш використовуваним векторним форматом є SVG, векторна графіка також використовується у форматі PDF.

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

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

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

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

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

Модель RGB (Red-Green-Blue) використовується для цифрових дисплеїв, де кольори відображаються як комбінація трьох основних кольорів – червоного, зеленого та синього. Кожен із цих кольорів має числове значення в діапазоні від 0 до ⁠255. Коди RGB зазвичай записуються з використанням шістнадцяткових чисел. Оскільки це кодування дуже часто використовується у графічних програмах, корисно мати принаймні базове уявлення про те, які кольори відповідають різним кодам RGB.

Модель CMYK (Cyan-Magenta-Yellow-Key) використовується для друку, коли кольори створюються шляхом змішування трьох основних кольорів – блакитного, пурпурового та жовтого з чорним.

Модель HSL (Hue-Saturation-Lightness) дозволяє відображати кольори за трьома параметрами – відтінком, насиченістю та яскравістю. Відтінок змінюється від 0 до ⁠360 градусів, насиченість визначає інтенсивність кольору, а яскравість визначає світлість або темність кольору. Ця модель дозволяє легко регулювати колір, наприклад, змінювати яскравість або насиченість.

Колірна модель RGB — це спосіб представлення кольорів за допомогою трьох компонентів: червоного (red, R), зеленого (green, G), синього (blue, B). Це адитивний спосіб змішування кольорів – окремі компоненти кольору складаються і створюють світло більшої інтенсивності (світліший колір).

При використанні моделі RGB ми записуємо колір у вигляді трійки чисел. Для запису значення окремих компонентів використовується багато різних позначень. Так, помаранчевий колір можна записати так:

• RGB(255, 160, 64) = десятковий запис восьмирозрядного числа
• #FFA040 = шістнадцятковий запис
• RGB(100%, 63%, 25%) = колірні компоненти у відсотках
• RGB(1, 0.63, 0.25) = колірні компоненти у вигляді чисел від 0 до 1

Часто використовуваним позначенням є десятковий запис восьмирозрядного числа, тобто чисел від 0 до 255.

Основні принципи

Звук — це механічні коливання навколишнього середовища (зазвичай повітря) із частотою приблизно 20–20 000 Гц. Вищі частоти сприймаються вухом як вищі тони.

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

Кодування звукової хвилі

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

Цифрові пристрої не можуть обробляти звукову інформацію протягом нескінченної кількості моментів. При перетворенні аналогового сигналу в цифровий здійснюється так звана дискретизація – сигнал перетворюється в непостійний (дискретний), який змінює обмежену кількість значень протягом певного часу (на малюнку позначено синіми крапками). Це пов’язано з частотою дискретизації. Наприклад, при частоті дискретизації 48 кГц 48 000 значень семплів чергуються протягом секунди.

Навіть миттєве відхилення сигналу не може мати необмеженої кількості значень, тому виконується так зване квантування, яке пов’язане з роздільною здатністю семплу. Наприклад, роздільна здатність (семплу) 4 біти означає, що миттєве відхилення вибірки може приймати 2⁴ = 16 станів (див. рисунок).

Для стиснення з втратами значення бітрейт (вказує швидкість передачі) є важливим. Чим вищий бітрейт, тим більше даних описується за секунду аудіозапису (наприклад, 320 кбіт/с є найвищим бітрейтом для файлів mp3).

Тонове кодування

На додаток до повного запису звукових хвиль (описано вище), звук можна представити як послідовність тонів. Це використовується під час створення музики або у зв’язку з інтерфейсом MIDI. Усередині послідовності тони можуть мати, наприклад, різну висоту, довжину, гучність тощо. Цим тонам потім «призначається» певний звук, або у формі семплу, або згенерований синтезатором. Звук, представлений у вигляді послідовності тонів (у форматі MID), раніше використовувався, наприклад, як музичний супровід комп’ютерних ігор. Наразі використовується більше для роботи зі звуком, отримані треки згодом експортуються у вигляді звичайного цифрового запису сигналу.

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

Як ми можемо закодувати 358 інакше? Наприклад, намалювавши триста п’ятдесят вісім рисок поруч. Або ми могли б погодитися, що дракон позначатиме сто, свиня – п’ятдесят, а заєць – два. Тоді ми могли б представити 358 зображенням трьох драконів, свині та чотирьох зайців.

Комп’ютери, однак, не користуються драконами і поросятками для кодування. Навіть десяткова система не підходить для комп’ютерів, тому що в комп’ютерів немає десяти пальців. З іншого боку, комп’ютери можуть добре розрізняти два стани (активний і неактивний). Тому для кодування чисел у комп’ютері в основному застосовується двійкова система, в якій використовуються тільки дві цифри: 0 і 1.

Основний принцип [двійкової системи] (https://www.znaiemoinformatyku.org/dviikovi-chysla-osnovy) не є специфічним для комп’ютерів. Це математичний принцип «позиційної системи», який працює в цілому. Ви можете використовувати його, наприклад, для лічби на пальцях, що дозволяє рахувати від 0 до 31 на пальцях однієї руки. Також підрахунок у двійковій системі (додавання, віднімання, множення) — це загальний принцип, який працює так само, як підрахунок у нашій звичній десятковій системі.

Для кодування від’ємних і десяткових чисел необхідно вдатися до деталей, дещо специфічних для комп’ютерів (скільки біт пам’яті виділяємо для номерів, як саме будемо їх використовувати).

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

Принцип двійкової системи

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

Маркування систем

Щоб розрізнити, чи йде мова про число у двійковій чи десятковій системі, ми додаємо нижні індекси до чисел, що позначають систему. Наприклад, число 5 у десятковій системі буде записано як 5_{10}, двійкове число зі значенням 5 буде записано як 101_2. Тоді ми можемо чітко визначити, що, наприклад, під нотацією 11_{10} ми маємо на увазі десяткове число 11, тоді як нотація 11_2 буде інтерпретуватися як двійкове число 11 і, отже, як десяткове число 3.

Інтуїтивна підказка

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

Тоді ми можемо рахувати на пальцях однієї руки не тільки до п’яти, але й до тридцяти одного. Кожне число можна виразити (однозначно) як суму степенів двійки. Якщо позначити положення пальців нулями й одиницями, то отримаємо запис у двійковій системі.

Приклади

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

Додавання двійкових чисел

Ми можемо складати двійкові числа подібним чином, як ми звикли складати числа в десятковій системі. Єдина різниця виникає, якщо ми додаємо дві одиниці. Оскільки 1_2 + 1_2 = 10_2, у цьому випадку ми пишемо 0 і переносимо 1 до вищого порядку.

Віднімання двійкових чисел

Аналогічним чином працює віднімання двійкових чисел. Перенос відбувається тільки при підрахунку різниці 0_2 – 1. У цьому випадку ми «позичаємо» одиницю з вищого порядку, ніби ми рахуємо 10_2 – 1_2. Потім пишемо 1 і в наступному рядку додатково віднімаємо те, що позичили.

Множення двійкових чисел

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

Якщо в нас є двійкове число для помноження на ступінь двійки, ми можемо значно полегшити нашу роботу. Все, що вам потрібно зробити, це додати в кінець числа стільки нулів, скільки у степені двійки ми множимо. Наприклад, при множенні на два додаємо 1 нуль (2 = 2^1), при множенні на вісім додаємо 3 нулі (8 = 2^3). Поділити ціле число на двійку також легко, просто видаліть із дільника стільки останніх цифр, скільки буде двійка, на яку ми ділимо.

Шістнадцяткові числа — числа, записані в шістнадцятковій (гексадецимальній) системі. Ця система використовує 16 символів (0-9 і A-F, де A-F означає числа від десяти до п’ятнадцяти).

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

Шістнадцяткові числа часто використовуються для відображення кольорів, наприклад, у моделі RGB. Кожен компонент кольору (червоний, зелений, синій) представлений вісьмома бітами, що відповідає двом шістнадцятковим цифрам. Так, червоний колір із повною інтенсивністю буде записаний як #FF0000, де FF означає максимальне значення червоного компонента.

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

Фотографія зберігається на комп’ютері у вигляді послідовності нулів і одиниць. Скільки потрібно нулів і одиниць? Це вказує нам розмір даних, який ми вимірюємо у байтах і їх кратних (мегабайтах, гігабайтах). Корисно розуміти розмір даних, наприклад, щоб чітко знати, скільки фотографій поміщається на карті пам’яті.

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

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

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

Біт є основною та найменшою одиницею інформації. Він може мати два різних значення: 0 або 1. Біти згруповані у байти, один байт складається з 8 бітів. Комп’ютери працюють з цілими байтами, тому байт є найменшою одиницею, яку він може обробляти. Саме через це розмір комп’ютерної пам’яті та файлів, що зберігаються в ній, наведено у байтах. Біт позначається як b, байт як B.

Усі дані зберігаються та обробляються в комп’ютерах у вигляді серії байтів. Оскільки файли на комп’ютерах часто складаються з багатьох мільйонів байтів, ми використовуємо кілька одиниць, щоб легше позначати розмір даних. Для легшого перетворення між одиницями ми використовуємо співвідношення 1 kB = 1000 B, але іноді ми також можемо зустріти співвідношення 1 kB = 1024 B = 2^{10} B. Те саме стосується інших кратних одиниць, тобто іноді ми можемо побачити 1 MB = 1024 kB, 1 GB = 1024 MB тощо.

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

Стиснення без втрат зберігає всю інформацію, що міститься у файлі, тому ми не втрачаємо жодних даних і можемо будь-коли повернутися до вихідної версії файлу. Недоліком цього типу стиснення є те, що він не може зменшити розмір настільки ж ефективно, як і стиснення із втратами. Він дуже часто використовується для текстів і для стиснення файлів незалежно від їх формату. Стиснення без втрат використовують, наприклад, архіви ZIP і RAR, які можуть стискати кілька різних файлів або папок одночасно. Іншими форматами зі стисненням без втрат є PNG, GIF (зображення) і FLAC (відео).

Одним із простих алгоритмів стиснення без втрат є RLE (кодування серії). Кодує ряд послідовних ідентичних символів у пару (кількість значень, значення). Наприклад, рядок aaaaaa кодується як 6a, рядок ccccddce як 3c2d1c1e.

Стиснення з втратами ефективніше зменшує розміри файлів. Однак під час стиснення ми можемо назавжди втратити частину інформації, яка була в оригінальному файлі. Тому стиснутий файл може містити дещо спотворені деталі або бути нижчої якості, ніж оригінал. Він широко використовується для зображень, відео та аудіо. Формати, які використовують стиснення з втратами, це, наприклад, JPG (зображення), MP3 (аудіо), MP4 і OGG (відео).

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

Тут ми маємо справу з останнім згаданим значенням. У цьому випадку граф означає вершини («точки») і ребра («зв’язки»). Такі графіки використовуються для моделювання зв’язків між об’єктами, наприклад:

• Транспортна мережа: вершини – міста, ребра – дороги між ними.
• Соціальна мережа: вершини — люди, ребра — підписки.
• Вебсторінки: вершини — окремі сторінки, ребра — зв’язки між ними.

Основні теми вивчення графів зосереджені на використанні їх на інтуїтивному рівні (ці теми також підходять на рівні початкової школи):

• Графи та абстракції – використання графа як моделі реальності, розуміння значення графів.
• Графи суміжності – один конкретний випадок використання графів, на якому принцип абстракції можна добре відпрацювати в суто графічній формі.
• Найкоротші шляхи – інтуїтивно зрозумілі приклади пошуку найкоротших шляхів між вершинами, що є одним із типових застосувань графів.
• Ізоморфні графи – тема зі складною назвою, але відносно інтуїтивно зрозумілими призначеннями зображень; ми шукаємо графи, які мають «однакові зв’язки».

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

Графи є ізоморфними, якщо вони мають однакову кількість вершин і однакові зв’язки. Тут ми не аналізуватимемо точне математичне визначення (його можна знайти, наприклад, тут), а лише інтуїтивну ідею. Уявімо собі вершини графа як дерев’яні кілочки, а ребра – як гумки між ними. Ми можемо переміщати кілочки та гумки, і це все один і той самий графік, тому що зв’язок між змінними зберігається. Ізоморфізм графів належить саме до цього типу «однаковості». Чи ми можемо рухатися за допомогою одного графіка стільки, щоб з нього отримати інший?

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

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

До основних понять графів належать:

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

Далі ми покажемо деякі розширення звичайних графів, тобто типи графів, властивості яких певним чином змінені.

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

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

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

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

Підграф — це частина (тобто деякі вибрані вершини та ребра) графа, яка сама також утворює граф. Отже, кожне ребро у підграфі мусить мати вершину на обох кінцях, яка також належить підграфу. Жовті вершини та ребра на малюнку утворюють підграф.

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

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

Люди, речі та інші об’єкти у світі часто взаємопов’язані різними способами: вони впливають один на одного, пов’язані один з одним або чимось схожі. Іншими словами, вони мають відносини один з одним. Кілька взаємопов’язаних об’єктів утворюють систему. Щоб краще зрозуміти більш складну систему, часто варто зобразити або намалювати дану систему – модель.

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

Об’єкти (речі, люди, групи тощо) можуть мати відносини з іншими об’єктами. Відносини виражають, як різні об’єкти пов’язані один з одним. Якщо ми кажемо про Андрія, що в нього є сестра Ганна, ми говоримо, що між Андрієм та Ганною є зв’язок – вони брат і сестра. Можна також сказати, що Андрій ходить до 2-ї початкової школи в Умані. Це зв’язок між Андрієм та школою, яку він відвідує. Об’єкти також можуть мати різні властивості, тобто додаткову інформацію, яка якимось чином їх описує. До властивостей Андрія належать зелені очі та темно-каштанове волосся. Властивість школи – те, що вона розташована за адресою Шкільна, 135.

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

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

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

Тут ми пропонуємо практику за основними принципами:

• Моделі та реальність: приклади моделей і міркування про те, яку частину реальності вони моделюють.
• Використання моделей і симуляцій: для чого ми насправді використовуємо моделі та симуляції, яка мета конкретних моделей, як мета моделювання впливає на вибір моделі.
• Інтерпретація симуляцій: інтерактивна робота з конкретними симуляціями та інтерпретація того, що в них відбувається.

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

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

Інші приклади моделей:

• глобус як модель Землі,
• моделі погоди, які використовуються для прогнозування погоди,
• іграшкові автомобілі або поїзди як моделі справжніх автомобілів і поїздів,
• 3D-модель персонажа в комп’ютерній програмі,
• зображення ланцюга живлення як моделі взаємовідносин тварин у природі.

Модель фіксує правила та принципи. Якщо ми «рухатимемо» модель, ми отримаємо симуляцію. Ми можемо зробити, наприклад, симуляцію автомобільної аварії за допомогою симуляції моделі автомобіля на комп’ютері або використовуючи фізичний краш-тест. Також можна зробити симуляцію погоди, щоб передбачити майбутнє. Не всі моделі, однак, варто перетворювати на симуляцію. Скажімо, симуляція такої моделі як мапа не має особливого сенсу.

Ми можемо створити моделі та симуляції для багатьох різних цілей:

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

Ми часто використовуємо моделювання, щоб досліджувати питання “Що якщо?”. Що якщо б обмеження швидкості на дорозі було нижчим? А якби карантин був жорсткішим? Що якщо б ми поєднали комп’ютерну мережу іншим способом?

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

Моделі мають регульовані параметри, які впливають на поведінку моделювання. Кожного разу, коли ми працюємо з моделюванням, корисно перевірити вплив параметрів на хід моделювання. Вправи практикують роботу з параметрами, розуміння опису моделі та інтерпретацію результатів моделювання.