Тема 1. Основні поняття інформатики.

Інформація та повідомлення.

Інформатика – наука, яка вивчає структуру і загальні властивості інформації, а також питання, пов’язані із збиранням, обробкою, збереженням, пошуком, передаванням і використанням інформації. Зокрема, до предмету інформатики відносять питання пов’язані з проектуванням, створенням та функціонуванням комп’ютерних систем та їх застосуванням. В англомовних країнах замість терміну "Інформатика" (Informatique) використовують термін "Computer Science".

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

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

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

,

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

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

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

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

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

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

Повідомлення у двійковій формі можна характеризувати довжиною – кількістю двійкових цифр, що його складають. Одиницею довжини двійкового повідомлення є біт, що відповідає повідомленню, яке складається з однієї двійкової цифри. Наприклад, довжина повідомлення 10011 становить 5 біт. Слово bit (біт) є скороченням англійського binary digital, що перекладається, як "двійкова цифра". Для характеристики довжини повідомлення використовують і більші одиниці:

1 байт = 8 біт,

1 Кілобайт (1 Кбт) = 1024 байти,

1 Мегабайт (1 Мбт) = 1024 Кілобайт,

1 Гігабайт (1 Гбт) = 1024 Мегабайт,

1 Терабайт (1 Тбт) = 1024 Гігабайт.

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

Кодування текстової інформації.

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

Таблиця, яка встановлює відповідність між символами і їх двійковими кодами називається кодовою таблицею. Код кожного символу має довжину 8 біт (1 байт). Всього символів в кодовій таблиці є 2⁸ = 256. Існує багато різних варіантів кодових таблиць, але їх основу складає ASCII – Американський стандартний код обміну інформацією. ASCII задає коди перших 128 символів кодової таблиці, куди входять великі і малі літери англійського алфавіту, знаки пунктуації, цифри, математичні символи та управляючі символи.

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

Для Європи більше підходить кодова таблиця 850, яка мітить літери більшості європейських алфавітів, а також північно- і південноамериканських алфавітів. В другій половині таблиці для цього були викинуті літери грецького алфавіту та деякі символи псевдографіки (бо число символів кодової таблиці фіксоване і дорівнює 256).

Ні таблиця 437, ні таблиця 850 не містять літер українського, російського та білоруського алфавітів – кирилиці. Для цих країн розроблена кодова таблиця 866. В жертву принесені деякі символи псевдографіки, а також специфічні літери європейських алфавітів.

Другу половину кодової таблиці називають розширенням ASCII. Коди символів кодової таблиці записуються в більшості випадків не в двійковій формі, а за допомогою шістнадцяткового алфавіту (іншими словами, за допомогою системи числення за основою 16).

В цьому алфавіті використовуються цифри 0, 1, ... , 9, A, B, C, D, E, F. Це дозволяє записати таблицю більш компактно. Код кожного символу записується в цьому випадку як дві шістнадцяткові цифри. Перехід від 16-го коду до 2-го легко здійснити, замінивши кожну з двох шістнадцяткових цифр чотирма двійковими у відповідності з табл.1:

 

Тут 2-й рядок – шістнадцяткові цифри, 1-й рядок відповідні їм числа в десятковій системі числення, 3-й рядок – запис шістнадцяткових цифр у двійковій системі числення.

Приклад. Шістнадцятковий код А3 відповідає двійковому коду 10100011.

Нижче (табл. 2) подана кодова таблиця 866.

Таблиця 2.

Шістнадцятковий код символу складається з номера стовпця і номера рядка, де знаходиться символ. Так, літера Ї має шістнадцятковий код F4, а двійковий - 11110100.

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

Пропуск між літерами також є знаком ASCII з шістнадцятковим кодом 20.

Десяткові цифри 0, 1, ... , 9 мають коди від 30 до 39 відповідно. Застосовуючи ASCII число 26 (в десятковій системі числення) можна подати як 00110010 00110110. Перші 8 цифр – це двійковий код цифри 2, а наступні 8 – двійковий код цифри 6.

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

Кожний символ в повідомленні, закодованому за допомогою ASCII, займає 1 байт. В останній час, із зростанням потужності комп’ютерів, використовується 16-бітне кодування Unicode (Юнікод). Кожен символ при кодуванні за допомогою Unicode зображається 16-а двійковими цифрами. Загальна кількість символів дорівнює 2¹⁶ = 65536. Цього достатньо, щоби закодувати практично всі символи більшості народів світу, елементи китайських, японських та корейських ієрогліфів, що дозволяють будувати будь-які ієрогліфи, та величезну кількість спеціальних символів.

Кодування числової інформації.

Кодувати числа за допомогою коду ASCII можна, але такий спосіб кодування є неекономним. Число, яке має цифр, буде кодуватись послідовністю з 8 двійкових цифр. Так число 1000000 буде представлено в пам’яті комп’ютера як послідовність з 56 двійок і одиниць. Більш економним, порівняно з кодуванням за допомогою ASCII, є запис числа в двійковій системі числення. 1000000 в двійковій системі числення зобразиться як

11110100001001000000

де всього 20 двійкових цифр. Про перевід десяткових чисел в двійкові (і навпаки) при допомозі стандартної програми Калькулятор див. Тему 8.

З іншого боку, виконання математичних дій в комп’ютері здійснюється над числами, записаними в двійковій системі числення, а не закодованими за допомогою ASCII. Комп’ютер так само автоматично здійснює перевід чисел в двійкову систему числення. А звідки комп’ютер знає, який спосіб переводу чисел використовувати? Це визначає програма, яка в даний момент управляє його роботою.

Кодування графічної інформації.

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

Для кодування чорно-білого зображення нам достатньо ставити у відповідність кожному елементу одну двійкову цифру, наприклад, 1 - для білого прямокутника, 0 – для чорного. Для кодування 4‑колірного зображення потрібна вже послідовність з двох цифр, наприклад, 00 – чорний колір, 01 – синій колір, 10 – зелений, 11 – червоний. Повноцінна кольорова гамма одержується при кодуванні кожного елемента 24 бітами. Розмір елемента зображення повинний бути малим настільки, щоби він мав один колір (а не був, наприклад, частиною червоний, а частиною зелений).

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

Приклад. Використовуючи описане вище 2-бітне кодування, малюнок з орнаментом можна подати у вигляді послідовності 100101010101101011111011111001001010101010101.

Тут 10 – код першого елемента (зелений колір), 01 – код другого елемента (синій колір) і т.д.

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

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

Алгоритми.

Електронна обчислювальна машина (ЕОМ), або комп’ютер, є пристрій, призначення якого – автоматична обробка інформації. В дійсності, комп’ютер обробляє не інформацію, а повідомлення. Але оскільки повідомлення є носіями інформації, то обробка повідомлень призводить до обробки інформації.

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

 

Мал 1. Зв’язок між даними, виконавцем та алгоритмом.

Виконавець може виконувати лише операції з деякої скінченної множини. Ця множина називається системою операцій виконавця.

Алгоритм має наступні властивості:

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

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

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

- Формальність. – Будь-який виконавець, здатний сприймати і виконувати вказівки алгоритму (навіть не розуміючи їх змісту), діючи за алгоритмом може виконати поставлене завдання.

- Масовість. – Алгоритм повинний бути застосовний до широкого класу вхідних даних.

Алгоритм можна подавати у різних формах:

- словесній;

- словесно-формульній;

- графічній;

- за допомогою спеціальної алгоритмічної мови;

При складанні алгоритму розв’язку деякої задачі S, її розбивають на менші підзадачі. Можливі лише три типи зв’язків між підзадачами:

1. Слідування. Підзадачі розв’язуються одна за другою в порядку їх слідування (Мал.2).

 

Мал 2. Слідування.

2. Розгалуження. Для розв’язку задачі S небхідно спочатку розв’язати підзадачу визначення істиності твердження U (умови). Якщо твердження U є істинним, то тоді ров’язується підзадача S1, якщо ні – то підзадача S2 (Мал.3). Іноді, в останньому випадку ніяку підзадачу розв’язувати непотрібно. Тоді таке розгалуження називається неповним. (Мал.4).

 

Мал 3. Розгалуження.

 

Мал 4. Неповне розгалуження.

3. Поторення (цикл). Цикли бувають двох типів: цикли ПОКИ і цикли ДО.

Цикл ПОКИ. Для розв’язку задачі S необхідно встановити істинність твердження U (умови). При негативній відповіді задача S розв’язана, а при позитивній – потрібно розв’язати підзадачу S1 і знову повернутись до перевірки істинності твердження U. Отже, поки твердження U є істинним, розв’язується підзадача S1 і знову перевіряється умова U. (Мал.5)

Цикл ДО. При цьому способі спочатку розв’язується підзадача S1, а потім перевіряється умова U. Якщо ця умова виконується (тобто її значення є істиною), то задача S є розв’язаною; якщо ні, то знову розв’язується підзадача S1. Ці дії повторюються до настання істинності твердження U.(Мал.6).

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

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

 

Мал. 5. Цикл ПОКИ.

 

Мал. 6. Цикл ДО.