1.Поняття алгоритму і його властивості
2.Способи опису алгоритмів
3.Основні структурні алгоритмічні конструкції
4. Список літератури
Будь алгоритм існує не сам по собі, а призначений для певного виконавця (людини, робота, комп'ютера, мови програмування і т.д.). Властивістю, що характеризує будь-якого виконавця, є те, що він вміє виконувати деякі команди. Сукупність команд, які даний виконавець вміє виконувати, називається системою команд виконавця. Алгоритм описується в командах виконавця, який буде його реалізовувати. Об'єкти, над якими виконавець може вчиняти дії, утворюють так звану середу виконавця. Вихідні дані і результати будь-якого алгоритму завжди належать середовищі того виконавця, для якого призначений алгоритм.
Значення слова «алгоритм» дуже схоже зі значеннями слів «рецепт», «метод», «процес». Однак, на відміну від рецепта або процесу, алгоритм характеризується наступними властивостями: дискретністю, масовістю, визначеністю, результативністю, формальністю.
Дискретність (розривність - протилежно безперервності) - це властивість алгоритму, що характеризує його структуру: кожен алгоритм складається з окремих закінчених дій, кажуть: «Ділиться на кроки».
Масовість - придатність алгоритму до всіх завдань даного типу, при будь-яких вихідних даних. Наприклад, алгоритм вирішення квадратного рівняння в області дійсних чисел повинен містити всі можливі результати рішення, тобто розглянувши значення дискримінанту, алгоритм знаходить або два різних кореня рівняння, або два рівних, або робить висновок про те, що дійсних коренів немає.
Визначеність (детермінованість, точність) - властивість алгоритму, яке вказує на те, що кожен крок алгоритму має бути строго визначений і не допускати різних тлумачень; також строго повинен бути визначений порядок виконання окремих кроків. Пам'ятаєте казку про Івана-царевича? «Йшов Іван-царевич по дорозі, дійшов до розвилки. Бачить великий камінь, на ньому напис: «Прямо підеш - голову втратиш, направо підеш - дружину знайдеш, наліво підеш - розбагатієш». Варто Іван і думає, що далі робити ». Таких інструкцій алгоритм містити не може.
Результативність - властивість, що складається в тому, що будь-який алгоритм повинен завершуватися за кінцеве (може бути дуже велике) число кроків. Питання про розгляд нескінченних алгоритмів залишається за рамками теорії алгоритмів.
Формальність - це властивість вказує на те, що будь-який виконавець, здатний сприймати і виконувати інструкції алгоритму, діє формально, тобто відволікається від змісту поставленого завдання і лише строго виконує інструкції. Міркувати «що, як і чому?» Повинен розробник алгоритму, а виконавець формально (не думаючи) по черзі виконує запропоновані команди і отримує необхідний результат.
Розглянемо наступні способи опису алгоритму: словесний опис, псевдокод, блок-схема, програма.
Словесноеопісаніе представляє структуру алгоритму природною мовою. Наприклад, будь-який прилад побутової техніки (праска, електропила, дриль і т.п.) має інструкцію по експлуатації, тобто словесне опису алгоритму, відповідно до якого даний прилад повинен використовуватися.
Ніяких правил складання словесного опису не існує. Запис алгоритму здійснюється в довільній формі на природному, наприклад, російською мовою. Цей спосіб опису не має широкого поширення, так як строго не формалізуємо (під «формальним» розуміється то, що опис абсолютно повне і враховує всі можливі ситуації, які можуть виникнути в ході вирішення); допускає неоднозначність тлумачення при описі деяких дій; страждає багатослівність.
Псевдокод - опис структури алгоритму на природному, частково формалізованому мовою, що дозволяє виявити основні етапи рішення задачі, перед точної його записом на мові програмування. У псевдокоді використовуються деякі формальні конструкції і загальноприйнята математична символіка.
Строгих синтаксичних правил для запису псевдокоду не існує. Це полегшує запис алгоритму при проектуванні і дозволяє описати алгоритм, використовуючи будь-який набір команд. Однак в псевдокоді зазвичай використовуються деякі конструкції, властиві формальним мовам, що полегшує перехід від псевдокоду до запису алгоритму на мові програмування. Єдиного або формального визначення псевдокоду не існує, тому можливі різні псевдокоду, що відрізняються набором використовуваних слів і конструкцій.
Блок-схема - опис структури алгоритму за допомогою геометричних фігур з лініями-зв'язками, які показують порядок виконання окремих інструкцій. Цей спосіб має ряд переваг. Завдяки наочності, він забезпечує «читаність» алгоритму і явно відображає порядок виконання окремих команд. У блок-схемі кожної формальної конструкції відповідає певна геометрична фігура пли пов'язана лініями сукупність фігур.
Розглянемо деякі основні конструкції, які використовуються для побудови блок-схем алгоритмів програм, регламентовані ГОСТ 19.701-90.
Блок, що характеризує початок / кінець алгоритму (для підпрограм - виклик / повернення)
Блок - процес, призначений для опису окремих дій
Блок - Зумовлений процес, призначений для звернення до допоміжним алгоритмам (підпрограм)
Блок - введення / виведення з невизначеного носія або опису вихідних даних
Блок - рішення (перевірка умови або умовний блок)
Блок - кордони циклу, що описує циклічні процеси типу: «цикл з передумовою», «цикл з умовою поста»
Опису алгоритму в словесній формі, на псевдокоді або у вигляді блок-схеми допускають деякий свавілля при зображенні команд. Разом з тим вона настільки достатня, що дозволяє людині зрозуміти суть справи і виконати алгоритм. На практиці виконавцями алгоритмів виступають комп'ютери. Тому алгоритм, призначений для виконання на комп'ютері, повинен бути записаний на «зрозумілою» для неї мовою, такий формалізований мову називають мовою програмування.
Програма - опис структури алгоритму на мові алгоритмічного програмування.
Елементарні кроки алгоритму можна об'єднати в наступні алгоритмічні конструкції: лінійні (послідовні), розгалужуються, циклічні з передумовою і циклічні з умовою поста. Будь алгоритм можна скласти, використовуючи ці чотири алгоритмічні конструкції.
Лінейнойназивают алгоритмічну конструкцію, реалізовану у вигляді послідовності дій (кроків), в якій кожна дія (крок) алгоритму виконується рівно один раз, причому після кожного i-го дії (кроку) виконується (i + 1) -е дію (крок), якщо i-е дію - не кінець алгоритму.
Розгалужується (іліветвящейся) називається алгоритмічна конструкція, що забезпечує вибір між двома альтернативами в залежності від значення вхідних даних. При кожному конкретному наборі вхідних даних розгалужується алгоритм зводиться до лінійного. Розрізняють неповне (якщо - то) і повне (якщо - то - інакше) розгалуження. Повний розгалуження дозволяє організувати дві гілки в алгоритмі (то чи інакше), кожна з яких веде до спільної точки їх злиття, так що виконання алгоритму триває незалежно від того, який шлях був обраний (рис. 1). Неповне розгалуження передбачає наявність деяких дій алгоритму тільки на одній гілці (то), друга гілка відсутня, тобто для одного з результатів перевірки ніяких дій виконувати не треба, управління відразу переходить до точки злиття.
Мал. 1. Повне розгалуження
Циклічної (або циклом) називають алгоритмічну конструкцію, в якій якась, що йде підряд група дій (кроків) алгоритму можемо виконуватися кілька разів, в залежності від вхідних даних або умови завдання. Група повторюваних дій на кожному кроці циклу називається тілом циклу. Будь-яка циклічна конструкція містить в собі елементи ветвящейся алгоритмічної конструкції.
Цикл з передумовою
У даній циклічної структурі спочатку перевіряється значення умовного виразу (умова) перед виконанням чергового кроку циклу. Якщо значення умовного виразу істинно, виконується тіло циклу. Після чого управління знову передається перевірці умови і т.д. Ці дії повторюються до тих пір, поки умовний вираз не прийме значення БРЕХНЯ. При першому ж недотриманні умови цикл завершується. Кількість кроків циклу заздалегідь не визначено і залежить від вхідних даних задачі. Особливістю циклу з передумовою є те, що якщо спочатку умовне вираз помилково, то тіло циклу не виконається жодного разу.
Мал. 2. Блок-схема циклу з передумовою: два варіанти зображення за допомогою умовного блоку а) і за допомогою блоку кордону циклу б)
Цикл з умовою поста
Як і в циклі з передумовою, в циклічній конструкції з умовою поста заздалегідь не визначено число повторень тіла циклу, воно залежить від вхідних даних задачі. На відміну від циклу з передумовою, тіло циклу з умовою поста завжди буде виконано хоча б один раз, після чого перевіряється умова. У цій конструкції тіло циклу буде виконуватися до тих пір, поки значення умовного виразу помилково (умова "закінчення" циклу). Як тільки воно стає справжнім, виконання команди припиняється. Можливо побудова циклу і з умовою "продовження" циклу, тобто тіло циклу буде виконуватися до тих пір, поки значення умови істинно. Блок-схема даної конструкції представлена на рис. 3 двома способами: за допомогою умовного блоку а й за допомогою блоку управління б.
Мал. 3. Блок-схема циклу з умовою поста
Розглянемо три типи циклічних алгоритмів: цикл з параметром (який називають арифметичним циклом), цикл з передумовою і цикл з умовою поста (їх називають ітераційним).
Існує різновид циклу з передумовою, яка називається арифметичний цикл. В арифметичному циклі число його кроків (повторень) однозначно визначається правилом зміни параметра, яке задається за допомогою початкового (N) і кінцевого (К) значень параметра і кроком (h) його зміни. Тобто на першому кроці циклу значення параметра дорівнює N, на другому - N + h, на третьому - N + 2h і т.д. На останньому кроці циклу значення параметра не більш К, але таке, що подальше його зміна призведе до значення, більшого; ніж К.
Наприклад, вивести 10 разів слово «Привіт!». Його блок-схема використовує спеціальний блок початку арифметичного циклу із зазначенням, що змінна i в ньому буде змінюватися від 1 до 10 з кроком 1.
