Алгоритмізація

Алгоритмізація

Основні етапи розв’язання прикладних задач із використанням комп’ютера

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

Поняття інформаційної моделі

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

Поняття алгоритму

Визначення алгоритму

Слово «алгоритм» походить від «algorith­mi» — латинської форми написання імені великого математика аль-Хорезмі, який сформулював правила виконання арифметичних дій. Тому спочатку під алгоритмом розуміли тільки правила виконання чотирьох арифметичних дій над багатоцифровими числами в десятковій системі числення. Зараз він є одним із фундаментальних понять інформатики.
Алгоритм — це послідовність дій, спрямованих на розв’язання поставленої задачі.

Виконавець алгоритму

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

Властивості алгоритму

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

Базові структури алгоритму

Базові структури алгоритму — це структури, за допомогою яких створюється алгоритм для розв’язання певної задачі. Існують три основні (базові) алгоритмічні структури, або три основні типи алгоритмів: лінійний, розгалужений та циклічний.
Лінійний алгоритм (послідовне виконання, структура слідування) — це алгоритм, який забезпечує отримання результату шляхом одноразового виконання послідовності дій, незалежно від вхідних даних і проміжних результатів. Дії в таких алгоритмах виконуються послідовно, одна за однією, тобто лінійно.
Розгалужений алгоритм (умова, структура вибору) — у класичному варіанті ця структура розглядається як вибір дій у разі виконання або невиконання заданої умови. Галуження бувають повними і неповними.
Повне галуження — це галуження, в якому певні дії визначені й у разі виконання, і в разі невиконання умови. Неповне галуження — це розгалуження, в якому дії визначені тільки у разі виконання (або у разі невиконання) умови.
Циклічний алгоритм (цикл, структура повторення) — це алгоритм, у якому передбачено повторення деякої серії команд. За допомогою цієї структури описуються однотипні дії, що повторюються декілька разів. Такі алгоритми забезпечують виконання довгої послідовності дій, записаних порівняно короткою послідовністю команд. Саме використання циклів дозволяє у повній мірі реалізувати швидкодію комп’ютерів.
Основна особливість базових алгоритмічних структур — це їх повнота, тобто цих структур достатньо для створення найскладнішого алгоритму.

Способи запису алгоритму

Процес алгоритмізації — це визначення елементарних дій та порядку їх виконання для розв’язання поставленого завдання. Існують різні способи запису алгоритмів (словесний, формульно-словесний, метод блок-схем, програмний та ін.), які застосовуються для представлення алгоритму у вигляді, що однозначно розуміється і розробником, і виконавцем алгоритму.
Для опису алгоритмів людина часто користується природною мовою, але для запису багатьох алгоритмів природна мова виявилась незручною, тому виникла необхідність у створенні штучних мов, наприклад мови математичних формул, хімічних процесів тощо. Існує спеціальна навчальна алгоритмічна мова, яка була створена для запису алгоритмів на папері; вона використовує слова природної мови, але має більш жорстку структуру. Найбільше поширення для запису логічної структури алгоритмів отримали графічні (структурні) схеми, які спрощують складання та аналіз алгоритму, полегшують перехід від запису алгоритму до написання програми.
Графічна схема (блок-схема) алгоритму — це графічне зображення алгоритму у вигляді спеціальних блоків з необхідними словесними поясненнями. Кожний етап алгоритму представляється у вигляді геометричної фігури (блоку), що має певну форму в залежності від характеру операції. Блоки на схемі з’єднуються стрілками (лініями зв’язку), які визначають послідовність виконання операцій та утворюють логічну структуру алгоритму.
Основні блоки графічної скеми:
• блок пуск-зупинка, що ви­­значає початок та кінець алгоритму (для блоку пуск (початок) — визначений тільки один вихід, для блоку зупинка (кінець) — тільки вхід);
• блок введення-виведення, що визначає введення інформації в програму або виведення на пристрій;
• блок процес, що визначає зміну значення, форми уявлення або розташування даних;
• блок перевірки умови, що визначає подальші кроки виконання алгоритму в залежності від виконання умови.
Важливою особливістю базових структур алгоритмів є те, що вони мають один вхід і один вихід, що дозволяє при відносній незалежності конструювати окремі блоки алгоритмів, а потім окремо розроблені структури з’єднувати між собою (вихід однієї базової структури сполучається із входом іншої). Весь алгоритм представляє лінійну послідовність базових структур.

Поняття величини

Базовим поняттям математичних і природних наук є поняття величини, що характеризує стани деякого об’єкта або явища.
Значення та позначення величин. При­пус­тимо, ми отримали деяке повідомлення N разом з відповідною йому інформацією I. Інформацію I на­зивають значенням величини, а повідомлення N — позначенням величини. Кажуть, «позна­ченню N відповідає значення I».
Наприклад, «X = 5» означає, що величина, позначена як Х, має значення 5.
З точки зору алгоритмізації як величини та їх сукупності виступають дані, що обробляються цим алгоритмом.
Аргументи та результати. Для роботи багатьох алгоритмів необхідно задавати початкові значення, які передаються в алгоритм за допомогою аргументів — величин, значення яких необхідно задати для виконання алгоритму. Результат — це величина, значення якої буде отримано внаслідок виконання алгоритму.
Також для опису алгоритму використовуються проміжні величини — величини, які додатково вводяться автором алгоритму під час його розробки.
Змінні та сталі величини. Сталою величиною (константою) називається ве­ли­чина, значення якої не змінюється в процесі виконання алгоритму.
Змінною називається величина, значення якої може мінятися в процесі виконання алгоритму. У кожний момент часу змінна величина має деяке значення, яке називається поточним значенням.
Саме над величинами виконуються певні операції. Якщо в процесі виконання алгоритму якась величина не набула значення, кажуть, що дана величина не визначена.
При написанні алгоритму величинам даються відповідні імена (ідентифікатори), що використовуються для звернення до значення деякої величини. Алгоритм роботи над величинами записується з використанням імен цих величин, але на кожному кроці виконання алгоритму дії проводяться з поточними значеннями величин.
У процесі виконання алгоритму значення величини може мінятися: їй присвоюється нове значення, а старе при цьому втрачається.

Технології програмування

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

Структурний підхід до проектування алгоритмів

Поняття про структурний підхід. Для розробки алгоритму складних задач використовується принцип структурного проектування алгоритмів.
Структурний підхід до створення алгоритмів — це метод розробки алгоритму, який забезпечує легкість читання алгоритму, простоту перевірки правильності виконання алгоритму, зручність у його модифікації. Цей метод передбачає:
• конструювання алгоритму з використанням трьох базових алгоритмічних структур;
• використання методу покрокової деталізації, тобто подрібнення задачі на більш прості задачі, потім подрібнення цих задач на ще більш прості складові й т. д. (розробка алгоритму «зверху вниз»);
• аналіз алгоритму, тобто контроль правильності кожної структури алгоритму і взаємозв’язків структур.
Перевагою структурного підходу є його модульність. Модуль — це послідовність логічно пов’язаних команд, яка оформлена у вигляді окремого алгоритму. Ці допоміжні алгоритми можна конструювати й аналізувати окремо та незалежно, використовуючи їх потім в основ­ному алгоритмі або інших допоміжних алгоритмах.
Структурний підхід привів до ідеї розподілу роботи серед розробників алгоритмів. Структурний підхід застосовується при використанні процедурних мов програмування.
Метод покрокової деталізації. Для створення алгоритму складної задачі застосовується метод покрокової деталізації («проектування зверху вниз»). При цьому методі складна задача розбивається на декілька простих. Ці задачі, у свою чергу, можуть розбиватися на серію ще простіших і т. д. Процес покрокової деталізації вважається закінченим, коли задачі чергового рівня стають досить простими для незалежного розв’язання. Потім результати проектування простих задач компонуються в загальний алгоритм.
Допоміжні алгоритми. При структуруванні алгоритму виникає необхідність у розв’язанні додаткових завдань. Назвемо алгоритм для виконання основної задачі основним алгоритмом. Тоді алгоритм для розв’язання допоміжної задачі, виділеної в окрему структуру, назвемо допоміжним алгоритмом. Цей алгоритм призначений для досягнення допоміжної мети на шляху розв’язання основної задачі. Один і той самий допоміжний алгоритм може бути використаний і в основному, і в іншому допоміжному алгоритмі.
Кожний допоміжний алгоритм має своє унікальне ім’я, за яким його можна розпізнати серед інших допоміжних алгоритмів і на це ім’я викликати його з іншого алгоритму за допомогою команди виклику допоміжного алгоритму.
Виконання допоміжного алгоритму з по­трібними початковими даними та/або передавання результатів в основний алгоритм здійснюється за допомогою параметрів алгоритму.
Параметри, які необхідно вказати перед початком роботи допоміжного алгоритму, називаються аргументами алгоритму. Ці параметри дають можливість змінити вхідні дані перед початком роботи допоміжного алгоритму.
Параметри, значення яких визначаються внаслідок роботи алгоритму, називаються результатами алгоритму. Допоміжний алгоритм може зовсім не мати параметрів або мати якийсь один тип параметрів. Параметри, які використовуються для опису вхідних і вихідних даних алгоритму, називаються формальними. Формальні параметри складають список формальних параметрів.
При конкретному виконанні допоміжного алгоритму формальні параметри замінюються на фактичні, тобто при виклику допоміжного алгоритму потрібно вказати фактичні параметри алгоритму.
Результатом виконання деякого допоміжного алгоритму може бути одна або декілька результуючих величин, які містяться в списку параметрів, або деяка дія (наприклад виведення звуку) без результуючої величини. Такі допоміжні алгоритми називаються алгоритмами-процедурами.
Алгоритми-функції — це допоміжні алгоритми, які виконують деякі дії, результатом виконання яких є один-єдиний результат, що присвоюється безпосередньо імені функції. Ім’я функції використовується в командах як ім’я звичайної змінної або константи.
Алгоритми-процедури і алгоритми-функції забезпечують можливість практичної реалізації методу структурного програмування.
Виклик допоміжного алгоритму має різний вигляд у разі виклику алгоритму-функції чи алгоритму-процедури:
• виклик допоміжного алгоритму-процедури здійснюється за допомогою спеціальної команди;
• виклик алгоритму-функції здійснюється безпосередньою вказівкою імені функції з фактичними аргументами в деякому виразі.
Виконання цих команд відбувається так:
• формальні аргументи допоміжного алгоритму замінюються фактичними значеннями, указаними в команді виклику алгоритму в списку фактичних параметрів; якщо в списку фактичних аргументів присутні вирази — вони спочатку обчислюються;
• виконуються всі команди допоміжного алгоритму з використанням фактичних аргументів;
• отримані результати присвоюються фактичним іменам результатів (іменам фактичних змінних, які використовуються як фактичні результати в алгоритмах-процедурах або імені самого алгоритму-функції).
Після виконання допоміжного алгоритму виконується команда основного алгоритму, записана після команди виклику допоміжного алгоритму.
Слово «алгоритм» походить від «algorith­mi» — латинської форми написання імені великого математика аль-Хорезмі, який сформулював правила виконання арифметичних дій. Тому спочатку під алгоритмом розуміли тільки правила виконання чотирьох арифметичних дій над багатоцифровими числами в десятковій системі числення. Зараз він є одним із фундаментальних понять інформатики.

Copyright © 2009-2017. All Rights Reserved.