Алгоритмічне мислення

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

Що включає в себе алгоритмічне мислення?

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

Алгоритмічне мислення включає в себе не тільки створення алгоритму, але й інші пов’язані з цим кроки:

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

Алгоритмічне мислення на Знаємо інформатику

У рамах програми «Знаємо інформатику» ми ділимо цю тему на кілька підтем:

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

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

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

Наочний, спрощений приклад із життя:

• У Павла постійно закінчуються гроші, тому він почав записувати свої витрати.
• Спочатку він записує витрати в зошиті дуже конкретно, наприклад: книга «Хоббіт», 443 гривні; хліб і сир для вечері, 42 гривні. Але вчитися з такого запису важко.
• Павло вивчає витрати, знаходить типи витрат, які регулярно виникають, і використовує узагальнення: він розділяє витрати на відповідні категорії («їжа», «одяг», «навчання», …).
• Потім він переписує витрати в редакторі таблиці. Це дозволить йому легко підрахувати загальні витрати в окремих категоріях.
• Таким чином Павло виявляє, що витрачає занадто багато на одяг. З цією інформацію він надалі може планувати якісь дії для вирішення проблеми.

Перш ніж ми приступимо до пошуку більш складних шаблонів, корисно вміти розпізнавати абсолютно однакові шаблони. Це також не має бути зовсім легко. Іноді потрібно добре зосередитися на деталях. Іншим разом шаблони можуть бути ті самі, але, повернуті трохи по-іншому, вони вимагатимуть від нас просторової уяви, для того щоб їх знов виявити.

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

Приклади:

• пес, ліс, туз, рис – спільна кількість букв (3)
• дрізд, сова, горобець, дятел – спільна тема (птахи)
• тричі, речі, родичі, дорожчі – спільні літери (слова, що закінчуються на -чі)

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

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

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

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

Приклад із повсякденного життя: потрібно готуватися до походу в гори. Є багато речей, які необхідно організувати, і ми можемо відчувати себе приголомшеними та легко забути щось важливе. Може допомогти, якщо ми розділимо загальну проблему підготовка до походу в гори на підпроблеми: 1) спланувати маршрут і знайти сполучення, 2) придумати меню та купити їжу, 3) підготувати туристичне спорядження та перевірити його стан, 4) продумати і спакувати одяг . Ці підзадачі значною мірою не залежать одна від одної, тому ними можуть займатися різні люди. Навіть якщо їх вирішує одна і та сама людина, при вирішенні часткової підзадачі вона може зосередитися тільки на ній, що полегшує процес прийняття рішень.

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

Розкладати проблеми на частини – це складна навичка, яку людина набуває через тривалу практику. Для базового навчання пропонуємо приклади з малюнками. Складне на вигляд зображення часто можна створити з простих частин, які зібрані відповідним чином.

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

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

Підтеми алгоритмічного мислення

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

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

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

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

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

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

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

Ми можемо контролювати хід програми за допомогою циклів і умов. Цикли дозволяють виконувати команди неодноразово: або задану кількість повторень (повторюй N×), або доки діє якась умова (повторюй, поки). Умовні команди дозволяють виконувати частину програми, лише якщо застосовується певна умова.

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

У програмуванні змінна – це сховище, яке містить значення. Це значення може змінюватися під час розрахунку, тому змінну називають змінною.

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

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

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

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

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

• ціле число (123, −7) – над числами можна виконувати арифметичні операції (1 + 2) і порівнювати їх (1 < 2)
• десяткові числа (1,23, –0,05) – зазвичай використовується так звана «рухома кома», яка дозволяє зберігати навіть дуже великі чи маленькі числа, але з обмеженою точністю (наприклад, з 5 значущими цифрами можна зберігати як 123 450 000, так і 0,000 012 345, але не 123,456)
• логічне значення (істинності) (правда, неправда) – представляє інформацію про правдивість, з цими змінними можна виконувати логічні операції (x не застосовується, x або y, x і y). Цей тип часто називають булевими (“bool” або “boolean”) на честь Джорджа Буля, який описав правила обчислення з подібними значеннями
• текстовий рядок (“слово”, “більше слів”) – представляє текст будь-якої довжини. Щоб відрізнити цей текст від імен змінних, рядки зазвичай відокремлюють «лапками» або ‘апострофами’. Необхідно розрізняти рядок, що містить число, і число: “123” не є 123. Цей тип часто називають «string» від англійського слова, що означає «рядок»
• список (поле) ([1, 2, 3], [‘x’, ‘y’, ‘z’]) – дозволяє зберігати кілька пов’язаних значень в одній змінній. (Інші типи часто доступні для зберігання різних колекцій даних)

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

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

Дозволені імена

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

• Імена можуть містити лише літери, цифри та підкреслення. Якщо б змінна називалася a+b, її не можна було б відрізнити від операції додавання. Але назва не має починатися з числа. Якби змінна була названа 12, її було б неможливо відрізнити від значення 12.
• Імена не можуть містити пробіли. Якби змінна називалася ціна моркви, було б непросто визначити, чи це дві змінні (ціна та морква). Якщо нам потрібно більше слів, ми можемо використати, наприклад, підкреслення (ціна_моркви).
• Так звані зарезервовані слова, які вже мають визначене значення у мові програмування *(як-от, повторюй, або, правда), не можна використовувати як назву.

Конвенція

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

Описи

Описові назви полегшують читання програми та зменшують ризик помилок. Команда total_price ← price_carrot_1kg * kg_carrot зрозуміліша, ніж price ← c * m, а також зрозуміліше, що одиниці вимірювання правильні. Ми вибираємо імена, які чітко виражають призначення змінної, навіть якщо вони мають довшу назву. Імена з однієї літери (як-от, x) придатні лише в обмежених випадках (керуюча змінна циклу, координати точки, приклади короткого коду).

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

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

• Приклад із казки: збільшувальна чарівна паличка, якою ми постукуємо по овочам, і вони збільшуються вдвічі.
• Математичний приклад: функція квадратного кореня, у яку ми вводимо число, а вона повертає інше число (наприклад, якщо задамо 25, то отримаємо результат 5).
• Приклад програмування: функція polygon(n, length), якій ми надаємо два числа (кількість сторін і довжину сторони) як вхідні дані, і вона малює зображення багатокутника.

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

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

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

Приклад із повсякденного життя: Алік, Бен і Рекс — три конкретні домашні тварини. Ми можемо позначити їх абстрактним терміном «собака», тим самим нехтуючи деякими з їхніх характеристик (наприклад, віком, кольором шерсті чи породою), і ми зосереджуємося лише на тому, що вони мають спільного. Якби в нас удома ще був кіт Мурко, ми могли б для їх сукупного позначення використовувати, наприклад, категорію «ссавець».

Приклад із програмування: під час візуалізації зображень ми можемо створити функцію squareA(), яка малює синій квадрат розміром 100, і squareB(), яка намалює жовтий квадрат розміром 200. Але краще створити абстрактнішу функцію square(length, color), яка намалює квадрат будь-якого розміру тa кольору (за вказаними параметрами). Як варіант, ми можемо продовжити абстракцію далі та створити функцію, яка візуалізує будь-який багатокутник (із заданою кількістю вершин).

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

Простіше кажучи, функція — це заклинання, якому ми щось даємо (вхід), а воно видає нам щось інше (вихід).

• Приклад із казки: збільшувальна чарівна паличка, якою ви постукаєте по овочу, і він збільшиться вдвічі.
  • Математичний приклад: функція квадратного кореня, в яку ми вводимо число, а вона повертає інше число (наприклад, при введенні 25 отримуємо результат 5).
  • Приклад програмування: функція polygon(sides, length), у яку ми вводимо два числа (кількість сторін і довжину сторони), і вона малює зображення багатокутника.

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

Проєктування рекурсивних алгоритмів

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

Самопосилання

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

Фрактали

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

Ми рідко маємо можливість написати код без помилок з першого разу. Ризик помилок зменшується завдяки прагненню написати якісний код, але повністю уникнути помилок неможливо, тому необхідно їх активно шукати. Помилки в коді іноді називають англійським терміном bug. Процес перевірки правильності коду називається тестуванням, процес пошуку причини помилки та її усунення називається налагодженням (іноді також «debugging»).

Типи помилок

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

Процедура налагодження програми

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