Алгоритми, їх властивості та подання
Програмування починається не із запам'ятовування команд мови, а з уміння точно описати послідовність дій. У цій лекції розглянемо шлях від даних і задачі до алгоритму, блок-схеми та першої консольної програми.
Цілі лекції
Після опрацювання матеріалу ви зможете:
- розрізняти дані та інформацію;
- пояснювати різницю між алгоритмом і програмою;
- називати й розпізнавати основні властивості алгоритму;
- подавати алгоритм словесно, псевдокодом, блок-схемою та програмним кодом;
- правильно використовувати стандартні фігури блок-схем;
- розпізнавати послідовність, розгалуження та цикл;
- описувати основні етапи створення програми;
- пояснювати на початковому рівні роль IDE, інтерпретатора та компілятора;
- читати й запускати просту консольну програму Python.
Передумови
Спеціальні знання з програмування не потрібні. Достатньо вміти виконувати послідовні інструкції, працювати з файлами та розуміти прості математичні вирази.
1. Дані та інформація
Дані - це зафіксовані значення, символи, сигнали або факти, які можна зберігати й опрацьовувати. Наприклад, датчик зафіксував значення:
532
Без контексту невідомо, що означає це число. Якщо додати опис «довжина хвилі лазера, нм», отримуємо інформацію: дані набули змісту й зменшили невизначеність.
Виміряна довжина хвилі лазера становить 532 нм.
Програми отримують дані, опрацьовують їх за визначеними правилами та формують результат, корисний людині або іншій системі. Помилкові вхідні дані чи неправильне правило можуть дати помилковий результат, навіть якщо комп'ютер бездоганно виконав усі команди.
2. Алгоритм і програма
Алгоритм - це точний і скінченний опис послідовності дій, виконання яких приводить від вхідних даних до результату для певного класу задач.
Наприклад, алгоритм обчислення енергії фотона за довжиною хвилі можна описати так:
- Отримати довжину хвилі.
- Перевести її в метри.
- Обчислити енергію за формулою.
- Вивести результат.
Алгоритм описує що і в якому порядку робити, але ще не обов'язково записаний мовою, яку виконає комп'ютер.
Програма - це реалізація алгоритму мовою програмування, придатна для виконання комп'ютером. Один алгоритм можна реалізувати різними мовами, зокрема Python, Scala або Go. Синтаксис буде різним, а послідовність розв'язання задачі може залишатися однаковою.
Алгоритми існують і поза програмуванням: інструкція налаштування оптичного приладу або порядок проведення вимірювання також задають дії. Проте побутова інструкція часто допускає здогадки, а комп'ютерна програма потребує особливої точності.
3. Властивості алгоритму
Якісний алгоритм має кілька основних властивостей.
| Властивість | Що означає | Простий приклад |
|---|---|---|
| Дискретність | Розв'язання поділено на окремі кроки | зчитати значення, обчислити, вивести |
| Визначеність (детермінованість) | Кожна команда однозначна; за однакових умов визначено той самий наступний крок | «помножити значення на 2», а не «трохи збільшити» |
| Масовість | Алгоритм придатний для класу однотипних вхідних даних, а не лише для одного випадку | обчислення для будь-якої допустимої довжини хвилі |
| Результативність | Після виконання отримуємо передбачений результат або коректне повідомлення про неможливість його отримати | числове значення або повідомлення про хибне введення |
| Скінченність | Виконання завершується після скінченної кількості кроків | цикл має умову завершення |
Властивості пов'язані, але не замінюють одна одну. Інструкція може бути скінченною, але неоднозначною. Програма може завершитися, але видати результат, який не відповідає поставленій задачі.
4. Способи подання алгоритмів
Той самий алгоритм можна описати кількома способами.
Словесний опис
Алгоритм записують звичайними реченнями. Такий опис легко обговорити, але складні дії можуть стати довгими або неоднозначними.
Отримати виміряну інтенсивність. Якщо вона перевищує допустиму межу,
вивести попередження; інакше повідомити, що значення в нормі.
Псевдокод
Псевдокод використовує короткі структуровані команди, схожі на програмний код, але не прив'язаний до точного синтаксису конкретної мови.
ВВЕСТИ intensity
ЯКЩО intensity > limit
ВИВЕСТИ "Перевищення"
ІНАКШЕ
ВИВЕСТИ "Норма"
КІНЕЦЬ ЯКЩО
Псевдокод зручний для продумування логіки до написання програми.
Блок-схема
Блок-схема показує кроки алгоритму стандартними фігурами та стрілками. Вона допомагає побачити порядок дій, вибір і повторення.
Мова програмування
Запис мовою програмування має точний синтаксис і може бути виконаний після опрацювання відповідним транслятором. Це найточніша форма для комп'ютера, але вона містить технічні деталі конкретної мови.
Жоден спосіб не є найкращим у всіх ситуаціях. Коротку ідею зручно пояснити словами, логіку вибору - псевдокодом або блок-схемою, а виконання комп'ютером потребує програми.
5. Стандартні елементи блок-схем
Форма блока передає його призначення. Не варто малювати всі дії однаковими прямокутниками.
| Елемент | Стандартна форма | Призначення | Приклад напису |
|---|---|---|---|
| Початок / кінець | овал або прямокутник із заокругленими краями | межі алгоритму | Початок, Кінець |
| Процес | прямокутник | обчислення або присвоєння | energy = h * c / wavelength |
| Введення / виведення | паралелограм | отримання чи показ даних | Ввести wavelength |
| Рішення | ромб | перевірка умови й вибір гілки | wavelength > 0? |
| Лінія потоку | стрілка | напрям виконання | від одного блока до наступного |
| З'єднувач | невелике коло | продовження схеми без довгої або перехресної лінії | однакові мітки A |
Основні правила побудови:
- схема має чіткі початок і завершення;
- стрілки показують напрям виконання;
- у ромбі записують умову, а виходи підписують
такіні; - блок містить одну зрозумілу дію або перевірку;
- лінії не повинні перетинатися без потреби;
- кожен можливий шлях має бути логічно завершеним.
Спрощена текстова модель розгалуження виглядає так:
(Початок)
|
/ Ввести wavelength /
|
< wavelength > 0? > -- ні --> / Повідомити про помилку / --> (Кінець)
|
так
|
[ Обчислити результат ]
|
/ Вивести результат /
|
(Кінець)
У справжній блок-схемі для цих позначень використовують відповідні геометричні фігури, а не текстові символи.
6. Три базові алгоритмічні структури
Більшість алгоритмів будується з трьох структур.
Послідовність
Команди виконуються одна за одною в записаному порядку.
ВВЕСТИ width
ВВЕСТИ height
area = width * height
ВИВЕСТИ area
Розгалуження
Залежно від істинності умови виконується одна з альтернатив.
ЯКЩО signal >= threshold
ВИВЕСТИ "Сигнал виявлено"
ІНАКШЕ
ВИВЕСТИ "Сигнал нижче порога"
КІНЕЦЬ ЯКЩО
Цикл
Одна або кілька дій повторюються, поки діє умова або для кожного елемента набору.
ДЛЯ КОЖНОГО measurement У measurements
ВИВЕСТИ measurement
КІНЕЦЬ ЦИКЛУ
Ця лекція дає лише огляд. Синтаксис умов і циклів та способи уникнення нескінченних повторень розглядатимемо окремо.
7. Від задачі до готової програми
Створення програми - це не лише введення коду. Типовий процес містить такі етапи:
- Постановка задачі. Визначити мету, вхідні дані, результат та обмеження.
- Аналіз. З'ясувати формули, правила, особливі випадки й критерії правильності.
- Проєктування алгоритму. Описати кроки словами, псевдокодом або блок-схемою.
- Кодування. Реалізувати алгоритм мовою програмування.
- Тестування і налагодження. Перевірити різні дані, знайти та виправити помилки.
- Документування. Пояснити призначення, використання та важливі рішення.
- Супровід. Виправляти виявлені проблеми й адаптувати програму до нових вимог.
На практиці розробник може повертатися до попередніх етапів. Наприклад, тест виявив, що нульове значення не було враховане під час аналізу, тому алгоритм потрібно уточнити.
8. IDE, інтерпретатор і компілятор
IDE (інтегроване середовище розробки) - програма, яка об'єднує редактор коду, запуск, підсвічування помилок, налагоджувач та інші інструменти. Приклади: PyCharm і Visual Studio Code з налаштованим розширенням Python. IDE допомагає працювати, але не замінює мову Python і не придумує алгоритм замість розробника.
Код високорівневої мови потрібно перетворити на дії, доступні комп'ютеру. На початковому рівні різницю можна сформулювати так:
- інтерпретатор опрацьовує програму під час її запуску;
- компілятор заздалегідь перетворює програму на іншу форму, придатну до виконання.
Python зазвичай називають інтерпретованою мовою, а Go - компільованою. Реальні реалізації можуть поєднувати кілька етапів, тому це корисна початкова модель, а не повний опис внутрішньої будови всіх мов. Для першого запуску Python важливо знати: встановлений інтерпретатор читає файл .py і виконує записані команди.
9. Перша консольна програма
Консольна програма взаємодіє з користувачем текстом у терміналі. Нижче один алгоритм реалізовано трьома мовами. У всіх варіантах програма послідовно виводить привітання та значення вимірювання.
print("Вітаємо в курсі програмування!")
wavelength_nm = 532
print("Довжина хвилі:", wavelength_nm, "нм")Python є основною мовою курсу. У ньому print(...) виводить текст або значення, а wavelength_nm = 532 зберігає число під зрозумілою назвою. Scala і Go потребують додаткового оформлення точки входу програми; зараз достатньо помітити, що алгоритм однаковий, а правила запису різні.
Файл Python можна зберегти як first_program.py і запустити в терміналі:
python first_program.py
Очікуваний результат:
Вітаємо в курсі програмування!
Довжина хвилі: 532 нм
Якщо програма не запускається, перевіряють, чи встановлено Python, чи відкрито правильну папку, чи правильно записано ім'я файла та чи немає синтаксичних помилок. Повідомлення про помилку - це джерело інформації для налагодження, а не ознака нездатності до програмування.
Підсумок
- Дані є зафіксованими значеннями, а інформація - даними, інтерпретованими в контексті.
- Алгоритм описує скінченну послідовність дій, а програма реалізує її мовою програмування.
- Основні властивості алгоритму: дискретність, визначеність, масовість, результативність і скінченність.
- Алгоритм можна подати словесно, псевдокодом, блок-схемою або програмним кодом.
- У стандартизованій блок-схемі форма блока показує його роль: початок/кінець, процес, введення/виведення або рішення.
- Послідовність, розгалуження та цикл є базовими структурами алгоритмів.
- Розробка охоплює постановку задачі, аналіз, проєктування, кодування, тестування, документування і супровід.
- IDE допомагає створювати й налагоджувати код; інтерпретатор і компілятор забезпечують його виконання різними способами.
- Python є основною мовою курсу, а перша консольна програма може складатися лише з кількох послідовних команд.