Правила запису команд

Команда присвоєння:

<Ім'я величини> := <Вираз>

Команди вибору:

Якщо <Умова> то <Команда>

Якщо <Умова> то <Команда> інакше <Команда>

Команда повторення:

Поки <Умова> виконувати <Команда>

Складена команда:

(<послідовність команд через крапку з комою>)

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

Команда переходу:

Перейти <Натуральне число>

 

3. Поняття алгоритму. Алгоритми та їх виконавці. Складання і виконання алгоритмів. Поняття лінійного алгоритму. Блок-схема лінійного алгоритму.

Одним з базових понять інформатики є поняття алгоритму. Алгоритм вказує, які операції, пов'язані з обробкою даних, і в якій послідовності треба виконати, щоб отримати розв'язок задачі. Алгоритм розрахований на певного виконавця, з погляду котрого вказівки мають бути елементарними, тобто такими, що можуть бути виконані безпосередньо, без подальшого тлумачення. Слово «алгоритм» походить від назви латинського перекладу трактату арабського математика IX століття Аль-Хорезмі («Трактат Аль-Хорезмі про арифметичне мистецтво індусів»).

Алгор́итм (латинізов. Algorithmi, від імені перського математика IX ст. аль-Хорезмі) — послідовність, система, набір систематизованих правил виконання обчислювального процесу, що обов'язково приводить до розв'язання певного класу задач після скінченного числа операцій.

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

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

Є декілька способів опису алгоритму: словесний опис послідовності дій, алгоритмічна мова, аналітичний опис у вигляді набору формул, графічний — у вигляді блок-схеми тощо. Формалізована система правил текстуального опису алгоритмів є одним із різновидів мов програмування. А мови, призначені для запису алгоритмічних структур, називаються мовами структурного програмування.

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

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

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

Узагальнюючи сказане, можна сказати, що кінець кінцем кожну задачу можна вважати окремою командою виконавцю, якщо його навчено виконувати поставлене завдання. Якщо ж виконавець не знає, як розв'язувати запропоновану задачу, виникає потреба розкласти її на такі підзадачі, що являються "посильними" для виконання, тобто входять до системи команд виконавця. Продовжуючи цей процес, остаточно отримують алгоритм, що складається з простих команд, зрозумілих виконавцю, або остаточно переконуються, що дана задача непосильна для вибраного виконавця, тому що в його системі команд не існує необхідних для цього команд. Наприклад, як би ми не деталізували алгоритм побудови багатоповерхової будівлі для дитини, задача кінець кінцем є для неї непосильною.

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

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

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

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

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

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

Таким чином, можна вважати допоміжний алгоритм своєрідним "чорним ящиком", на вхід якого подаються деякі вхідні дані, а на виході ми отримуємо очікуваний результат. Головне чітко домовитись про правила оформлення вхідних даних та вигляд результату. Невиконання домовленостей може привести до збою у виконанні допоміжного алгоритму або до отримання неочікуваного результату.

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

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

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

· лінійні;

· розгалужені;

· циклічні;

· змішані.

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

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

 

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

· проснутися;

· зробити ранковий туалет;

· одягнутися;

· поснідати;

· зібрати речі;

· одягнути верхній одяг;

· вийти до училища.

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