Основи програмування

1.    Двійкова система числення

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

Наприклад, нижче наведено число означає сто двадцять три.

1 2 3

3 знаходиться в колонці одиниць, 2 – десятків, 1 – сотень.

Тобто 123 – це 100×1 + 10×2 + 1×3 = 100 + 20 + 3 = 123.

У двійковій системі лише дві цифри, існує два значення для кожного місця:

4 2 1

0 0 0

Така сума все ще дорівнюватиме 0.

Тепер, якщо замінити бінарне значення на, скажімо, 0 1 1, то десяткове значення дорівнюватиме 3.

4 2 1

0 1 1

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

Для відображення літер потрібно вирішити, які числа їм відповідають. Багато років тому було колективно створено стандартну систему їх представлення, яку назвали ASCII. Наприклад, літера «А» відповідає 65, а «В» — 66 і так далі.

Байт – це 8 біт, його використовують як одиницю для упорядкування бітів. Наприклад, цифра 72 вписується в один байт.

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

2. Подання даних

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

На стандартній англійській клавіатурі не видно літери з діакритичними знаками та багато інших символів:

 

Аби розв’язати цю проблему, комп'ютери можуть відображати літери за іншими стандартами на додачу до ASCII.

Обидві літери з діакритичними знаками, як і смайлики, можуть бути представлені кількома байтами зі стандартною назвою Unicode (одна з версій якого називається UTF-8).

Коли ми отримуємо смайлик, наш комп'ютер просто отримує десяткове число, наприклад 128514 (11111011000000010 в бінарній системі) яке він потім перетворює на зображення смайлика.

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

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

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

Відео – це багато картинок, які програються одна за одною в певній кількості за секунду.

Відео можна розглядати як приклад абстракції картинок, картинки – абстракція пікселів, а ті, в свою чергу, абстракція бітів.

3. Алгоритми

Розглянемо тепер приклад вхідної та вихідної інформації. Спочатку "чорна скринька" вміщуватиме алгоритми – покрокові інструкції розв’язання задач.

Наприклад, потрібно знайти в телефонній книзі Майка Сміта.

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

Також можна гортати по дві сторінки одразу, але так можна пропустити пострібну сторінку.

Однак найефективнішим способом було б відкрити телефонну книгу посередині, вирішити, чи ім’я Майка буде в лівій або в правій половині книги (тому що книга в алфавітному порядку), і негайно відкинути половину задачі. Можна це повторити, ділячи задачу щоразу навпіл.

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

Перший розв’язок, а саме одна сторінка за раз – червона крива: час на розв’язок зростає лінійно відповідно до збільшення кількості сторінок.

Другий розв’язок, тобто дві сторінки за раз – жовта крива: нахил менший, але все ще лінійно.

Остаточний розв’язок – зелена крива, вона логарифмічна, оскільки час на розв’язання задачі зростає все повільніше зі збільшенням задачі. Інакше кажучи, якщо телефонна книга збільшиться з 1000 до 2000 сторінок, знадобиться ще один крок, аби знайти Майка. Якщо розмір знову збільшиться вдвічі з 2000 до 4000 сторінок, всеодно потрібно буде на один крок быльше.

 

4. Псевдокод

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

 0 взяти телефонну книгу

 1 відкрити її посередині

 2 подивитися на імена

 3 якщо "Сміт" є серед імен

 4     подзвонити Майку

 5 інакше якщо "Сміт" знаходиться раніше в книзі

 6     відкрити посередині лівої половини книги

 7     повернутися на крок 2

 8 інакше якщо "Сміт" знаходиться далі в книзі

 9     відкрити посередині правої половини книги

10     повернутися на крок 2

11 інакше

12     закінчити

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

 0 взяти телефонну книгу

 1 відкрити її посередині

 2 подивитися на імена

 3 якщо "Сміт" є серед імен

 4     подзвонити Майку

 5 інакше якщо "Сміт" знаходиться раніше в книзі

 6     відкрити посередині лівої половини книги

 7     повернутися на крок 2

 8 інакше якщо "Сміт" знаходиться далі в книзі

 9     відкрити посередині правої половини книги

10     повернутися на крок 2

11 інакше

12     закінчити

Також тут є питання, на які існує кілька відповідей, як перехрестя на дорозі. Їх називають умовами:

 0 взяти телефонну книгу

 1 відкрити її посередині

 2 подивитися на імена

 3 якщо "Сміт" є серед імен

 4     подзвонити Майку

 5 інакше якщо "Сміт" знаходиться раніше в книзі

 6     відкрити посередині лівої половини книги

 7     перейти на крок 2

 8 інакше якщо "Сміт" знаходиться далі в книзі

 9     відкрити посередині правої половини книги

10     повернутися на крок 2

11 інакше

12     закінчити

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

 0 взяти телефонну книгу

 1 відкрити її посередині

 2 подивитися на імена

 3 якщо "Сміт" є серед імен

 4     подзвонити Майку

 5 інакше якщо "Сміт" знаходиться раніше в книзі

 6     відкрити посередині лівої половини книги

 7     повернутися на крок 2

 8 інакше якщо "Сміт" знаходиться далі в книзі

 9     відкрити посередині правої половини книги

10     повернутися на крок 2

11 інакше

12     закінчити

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

 0 взяти телефонну книгу

 1 відкрити її посередині

 2 подивитися на імена

 3 якщо "Сміт" є серед імен

 4     подзвонити Майку

 5 інакше якщо "Сміт" знаходиться раніше в книзі

 6     відкрити посередині лівої половини книги

 7     повернутися на крок 2

 8 інакше якщо "Сміт" знаходиться далі в книзі

 9     відкрити посередині правої половини книги

10     повернутися на крок 2

11 інакше

12     закінчити