Лабораторна робота 1

Розробка алгоритмів

1 Завдання на лабораторну роботу

1.1 Реалізація алгоритму з розгалуженням

Реалізувати у вигляді діаграми діяльності алгоритм розв'язання квадратного рівняння. Алгоритм повинен включати всі можливі варіанти вихідних даних. Зокрема, слід перевіряти дискримінант, а також передбачити перевірку, чи рівняння є квадратним. Якщо рівняння виродилося в лінійне, слід передбачити знаходження кореня цього лінійного рівняння, або встановити наявність безлічі розв'язків (відсутності розв'язків).

1.2 Реалізація циклічного алгоритму

Реалізувати у вигляді діаграми діяльності алгоритм обчислення виразу:

У наведеній сумі спільний член можна записати як i/(x + 2i), але в ньому пропущено один елемент, коли i = k.

Забезпечити перевірку можливих помилок.

1.3 Індивідуальне завдання

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

Алгоритм повинен бути представлений з використанням UML-діаграми діяльності. Алгоритм повинен містити такі частини:

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

Конкретна функція визначається відповідно до номеру в списку студентів у групах (номер варіанту).

2 Методичні вказівки

2.1 Основні поняття інформатики

2.1.1 Системи числення

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

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

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

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

До недоліків двійкової системи можна віднести громіздкість запису чисел і недостатню наочність. У тих випадках, коли для роботи важливо саме двійкове подання числа, використовують системи числення з основою – ступенем двох. Раніше була поширена вісімкова система, в цей час найбільш часто використовують шістнадцяткову систему числення. Як шістнадцяткові цифри заведено використовувати десять десяткових цифр і букви A (10), B (11), C (12), D (13), E (14) і F (15).

У наведеній нижче таблиці подане десяткове, двійкове та шістнадцяткове представлення чисел від 1 до 32:

Десяткове	Двійкове	Шістнадцяткове	Десяткове	Двійкове	Шістнадцяткове
1	00000001	1	17	00010001	11
2	00000010	2	18	00010010	12
3	00000011	3	19	00010011	13
4	00000100	4	20	00010100	14
5	00000101	5	21	00010101	15
6	00000110	6	22	00010110	16
7	00000111	7	23	00010111	17
8	00001000	8	24	00011000	18
9	00001001	9	25	00011001	19
10	00001010	A	26	00011010	1A
11	00001011	B	27	00011011	1B
12	00001100	C	28	00011100	1C
13	00001101	D	29	00011101	1D
14	00001110	E	30	00011110	1E
15	00001111	F	31	00011111	1F
16	00010000	10	32	00100000	20

Формально зазвичай вказують основу як індекс числа. Наприклад,

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

Записавши останній результат і залишки від ділення, отримаємо

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

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

2.1.2 Програмне забезпечення

Термін "програма" використовують у двох значеннях:

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

Апаратне забезпечення – це фізичні, матеріальні частини комп'ютера чи іншої системи.

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

• системне ПЗ – програми, що забезпечують управління компонентами комп'ютерної системи; до системного ПЗ можна віднести:
  • операційні системи (operating systems);
  • системні утиліти (utilities);
  • СУБД (системи управління базами даних, database management systems)
  • драйвери пристроїв (device drivers);
• прикладне ПЗ – програми і пакети програм, призначені для розв'язання задач користувачів у конкретних предметних галузях; до прикладного програмного забезпечення відносять текстові процесори, графічні редактори, поліграфічні системи, програми для виконання наукових і технічних розрахунків, ігри тощо;
• інструментальні засоби – програмне забезпечення, призначене для створення іншого програмного забезпечення; до інструментальних засобів відносять компілятори та інші утиліти для збирання й зневадження, а також інтегровані середовища розробки (IDE, Integrated Development Environment) і CASE-системи (Computer-Aided Software Engineering).

Застосунок (додаток, застосування, application) – це синонім прикладної комп'ютерної програми. Однак під застосунком розуміють будь-яку програму, яка не є частиною операційної системи.

2.1.3 Операційні системи

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

У складі операційної системи виділяють три групи компонентів:

• ядро (планувальник, драйвери пристроїв, підтримка мережі, файлова система);
• системні бібліотеки;
• набір утиліт.

Приклади операційних систем – MS-DOS, OS/2, Mac OS, MS Windows різних версій, UNIX, Linux, Solaris, Google Android і багато інших.

2.1.4 Файлова система

Файлова система (file system) – це спосіб і правила організації та зберігання каталогів і файлів на зовнішньому пристрої. Іноді під файловою системою також розуміють сукупність файлів і каталогів на конкретному пристрої.

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

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

Файлову систему зазвичай розглядають як частину операційної системи. Кожна операційна система надає свій набір файлових систем. Наприклад, файлові системи FAT 16, FAT 32, NTFS пов'язані з Windows, Ext2, Ext3, Ext4 використовують в Linux.

2.1.5 Текстові та бінарні файли

Незалежно від файлової системи, всі файли можна поділити на текстові та бінарні (двійкові).

Текстовий файл (text file) – це комп'ютерний файл, в якому вся інформація представлена у вигляді символів визначеної кодової таблиці. Послідовність символів розділена на рядки. Для відокремлення рядків один від одного використовують роздільники – один або більше спеціальних символів. Приклади текстових файлів – прості документи, створені за допомогою блокнота (*.txt), сирцевий код (вихідні тексти) програм мовами високого рівня (*.pas, *.c, *.cpp, *.cs, *.java тощо), файли розмітки гіпертексту (*.htm, *.html), форматовані документи (*.rtf) тощо. Підготовка та редагування текстових файлів, незалежно від їх спеціального формату і призначення, може бути здійснена універсальними текстовими редакторами, наприклад, блокнотом.

Двійковий файл (бінарний файл, binary file) – це комп'ютерний файл, в якому числова інформація подана двійковими числами, відповідно до внутрішнього представлення в пам'яті комп'ютера (а не символами, як в текстових файлах). Кожен окремий формат двійкового файлу вимагає спеціального програмного забезпечення. Приклади двійкових файлів – файли, які містять команди для виконання процесором (executables) під усіма операційними системами, растрові зображення (*.tif, *.jpeg, *.png, *.gif тощо), архіви (*.zip, *.rar тощо), аудіофайли, відеофайли всіх форматів, файли з двійковим кодом (*.obj, *.class тощо), а також численні спеціальні формати пакетів прикладних програм.

2.2 Основні поняття програмування

2.2.1 Мови програмування

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

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

Мови високого рівня поділяють на основні групи:

• процедурні (FORTRAN, ALGOL-60, BASIC, ALGOL-68, PASCAL, C, Modula-2 тощо);
• об'єктно-орієнтовані (Simula-67, Smalltalk-80, C++, ADA, Object Pascal, OBERON, Java, C# тощо).

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

2.2.2 Інтерпретатори і компілятори. Етапи розробки програми

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

• Інтерпретатор (interpreter) транслює програму рядок за рядком і одразу ж виконує інструкції, зазначені в цих рядках; як приклади можна навести інтерпретатори BASIC, JavaScript; інтерпретатори забезпечують гнучкість і створюють ефект миттєвого виконання, але необхідність багаторазової трансляції раніше інтерпретованих рядків під час виконання істотно знижує ефективність програми;
• Компілятор (compiler) транслює весь код у набір команд, які може виконати процесор (віртуальна машина). Програми, написані мовами Pascal, C++, C# та багатьма іншими, завжди оброблюються компіляторами.

Типовими етапами розробки програми є такі:

• сирцевий програмний код (вихідний текст, source code) програми готується за допомогою текстового редактора;
• сирцевий код перетворюється в набір двійкових інструкцій (binary code); це може бути машинний код, як у C++, або проміжний двійковий код, як у Java;
• скомпільований код збирається з окремих частин (компонування, linking) і виконується.

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

2.2.3 Типи застосунків

Прикладні програми (застосунки, додатки, applications), які створюють у сучасних середовищах програмування, з точки зору взаємодії з користувачем можна розділити на дві основні групи:

• консольні застосунки (console applications);
• застосунки графічного інтерфейсу користувача (graphical user interface applications, GUI applications).

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

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

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

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

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

2.3 Алгоритми

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

Є декілька способів опису алгоритмів:

• вербальний спосіб;
• псевдокод (штучна алгоритмічна мова);
• графічний спосіб.

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

Уніфікована мова моделювання (Unіfіed Modeling Language, UML) – це графічна нотація для визначення, опису, проєктування та документування програмних систем, бізнес-систем і інших систем різної природи, в першу чергу пов'язаних з програмним забезпеченням. UML включає низку діаграм для моделювання і проєктування складних систем.

Діаграма діяльності (Activity diagram) – одна зі стандартних діаграм UML. Цей вид діаграм може бути використаний для зображення алгоритмів. У цьому випадку використовують такі елементи діаграми:

• початковий стан (initial state);
• діяльність (activity);
• перехід (transition);
• символ перевірки умови (decision);
• кінцевий стан (end state).

На кожній діаграмі діяльності може бути присутнім тільки один початковий стан:

Будь-яка діяльність (введення / виведення, обчислення та ін.) на діаграмі представляється овалом:

Діяльності зв'язуються одна з одною переходами у вигляді стрілок:

Символ перевірки умови (decision) зображують у вигляді ромба. Умови переходу записують у квадратних дужках:

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

З початкового стану виходить одна і тільки одна стрілка. Елемент "діяльність" вимагає, щоб у нього входила одна стрілка, а одна виходила. Не повинно бути діяльностей без вхідної, або без вихідної стрілки. Декілька стрілок може виходити тільки із символу перевірки умови.

2.4 Класифікація алгоритмів

Більшість задач алгоритмізації розв'язується за допомогою трьох найпростіших типів алгоритмів:

• лінійні алгоритми;
• алгоритми з розгалуженням;
• циклічні алгоритми.

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

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

Реалізація алгоритму обчислення зворотної величини вимагає перевірки можливості ділення (аргумент не може приймати значення 0). Це приклад алгоритму з розгалуженням:

Циклічний алгоритм передбачає виконання певних обчислень декілька разів. Сукупність таких дій, що циклічно повторюються, має назву тіла циклу. До початку виконання тіла циклу або після завершення дій у тілі циклу слід здійснювати перевірку необхідності повторного входу в цикл. Наведений нижче алгоритм описує дії, пов'язані з уведенням цілого n та знаходженням степенів числа 2 – від першого до n-го:

Під час створення алгоритмів за допомогою діаграм діяльності окремі повідомлення можна виводити будь-якими мовами (наприклад, "Print x", "Друкувати x" тощо), оскільки діаграма не пов'язана з певною мовою програмування та її програмна реалізація виконується вручну. Головне – діаграма повинна бути зрозумілою виконавцеві.

3 Приклади алгоритмів

3.1 Лінійне рівняння

Приклад алгоритму з розгалуженням (без циклів) – алгоритм розв'язання лінійного рівняння:

Якщо a не дорівнює нулю,

Якщо і a, і b є нулями, будь-яке значення можна розглядати як корінь рівняння. Якщо b ненульове значення, а a ні, рівняння неможливо розв'язати. Це слід зобразити на схемі алгоритму:

3.2 Обчислення суми

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

Алгоритм обчислення суми може виглядати так:

Як видно з алгоритму, спочатку ми присвоюємо 0 результату, а потім на кожному кроці додаємо наступний доданок.

3.3 Обчислення добутку

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

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

Наведена вище діаграма містить так звану анотацію – довільний текст з поясненням, який можна зв'язати з певним елементом.

3.4 Сума добутків

Іноді під час розв'язання задач виникає необхідність реалізації вкладених циклів. Наприклад, коли необхідно обійти всі комірки прямокутної таблиці або обчислити суму добутків, суму сум, добуток добутків тощо.

Припустимо, необхідно ввести значення n і обчислити y за формулою

Почати слід з аналізу задачі. Можна представити формулу в більш зручній формі:

Наприклад, для випадку n = 4 отримуємо:

Схема алгоритму може бути такою:

Важливо ініціалізувати внутрішній добуток початковим значенням (1) на кожному кроці зовнішнього циклу.

3.5 Добуток сум

Інший приклад реалізації алгоритму з вкладеними циклами – обчислення добутку сум. Необхідно ввести значення n, обчислити y за формулою

та вивести результат.

Як і в попередньому прикладі, представляємо формулу в більш зручній формі:

До початку обчислення необхідно переконатися, що число n, яке ввів користувач, більше або дорівнює 2, інакше формула втрачає сенс і слід виводити повідомлення про помилку. Схема алгоритму може бути такою:

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

3.6 Загальний алгоритм індивідуального завдання

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

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

4 Вправи для контролю

Вправи виконуються студентами, які бажають отримати відмінну оцінку.

Завдання 1

Розробити алгоритм програми, в якій здійснюється читання значення певної довжини в дюймах і обчислюється й виводиться значення цієї довжини в міліметрах (1 дюйм = 25,4 мм).

Завдання 2

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

Завдання 3

Розробити алгоритм програми, яка зчитує значення змінної n цілого типу й обчислює n!

5 Контрольні запитання

1. Що таке позиційна система числення?
2. Що таке основа системи числення?
3. Які є недоліки й переваги двійкової системи числення?
4. Для чого використовують шістнадцяткову систему числення?
5. Визначте поняття програмного забезпечення.
6. Як можна класифікувати програмне забезпечення?
7. Що таке інструментальні засоби?
8. Що таке застосунок (додаток)?
9. Які функції виконує операційна система?
10. Наведіть приклади операційних систем.
11. Що таке файлова система?
12. Чим текстові файли відрізняються від бінарних?
13. Наведіть приклади текстових і бінарних файлів.
14. Чим визначається "рівень" мови програмування?
15. Як визначити поняття "комп'ютерна програма"?
16. Які існують етапи розробки програми?
17. Що таке зневадження?
18. Що таке консольний застосунок і чим він відрізняється від інших видів застосунків?
19. У чому переваги і недоліки інтерпретаторів і компіляторів?
20. Що таке алгоритм?
21. Які є способи подання алгоритму?
22. Які є різні типи алгоритмів?
23. Що таке UML?
24. Що таке діаграма UML?
25. У чому різниця між блок-схемою і діаграмою діяльності?
26. У чому різниця між поданням умовних елементів в блок-схемі та діаграмі діяльності?
27. У чому різниця між поданням виведення та розрахунків у нотації діаграм діяльності?