ФДБОУ ВО «Мордівський державний
Педагогічний інститут імені М.Є. Євсев'єва»
Фізико-математичний факультет
Кафедра інформатики та обчислювальної техніки
РЕФЕРАТ
«Принципи структурного програмування. Основні алгоритмічні структури та їх суперпозиції»
Виконала: студентка гр. МДМ-212
Багданова Яна
Саранськ 2016
Вступ
До початку 70-х років ХХ століття, коли розвиток мов програмування досяг досить високого рівня, а створювані програмні комплекси досягли досить великих розмірів (сотні тисяч – мільйони команд), стало очевидно, що програмні проекти стали надто складними для успішного проектування, кодування та налагодження у прийнятні терміни. Програмісти, що вирішують складні завдання, зіткнулися з проблемою зростання кількості та розміру програм настільки, що подальший процес розробки ставав практично некерованим, і ніхто з розробників не міг з впевненістю сказати, що створений програмний продукт завжди виконує те, що потрібно, і що він не виконує нічого такого, що не потрібне. Таким чином, виникла проблема докорінної зміни підходів до створення великих програмних комплексів.
Виходячи з цих проблем, провідними програмістами 70-х років (Дейкстра , Вірт , Дав , Xoap , Йордан , Костянтин , Майєрс та ін.) були розроблені суворі правила ведення проектів, які отримали назвуструктурної методології .
p align="justify"> Важливим етапом у становленні цього підходу стали міжнародні конференції з програмування, проведені в 1968-69 роках. На другому з нихЕдсгер Дейкстра вперше використав термін «структурне програмування і запропонував принципово новий спосіб створення програм. Він розглядав програму як сукупність ієрархічних абстрактних рівнів, які дозволяли:
чітко структурувати програму, що покращило її розуміння програмістами;
виконувати докази її коректності та тим самим підвищувати надійність функціонування програми;
скорочувати термін розробки програм.
Ще одним поштовхом до зміни способу програмістського мислення став опублікований листДейкстри редактору одного з наукових видавництв, яке було під назвою «Оператор GOTO слід вважати шкідливим ». Цей лист викликав гостру полеміку серед програмістів того часу, але в результаті перемогло все-таки структурне мислення, яке, крімДейкстри , активно підтримували професор Цюріхського технічного університетуВірт та професор Оксфордського університетуXoap . Одним із результатів полеміки був доказ того, що будь-яка програма може бути написана, використовуючи лише просту послідовність операторів, ітеративну конструкцію типуwhile ( Бувай ) та конструкцію виборуcase ( вибір ), а операторgoto ( перейти до ) не є необхідною керуючою конструкцією у структурному програмуванні. На жаль, суперечки про оператораgoto мали один негативний «побічний ефект» - досить часто програмування безgoto почало ототожнюватися з усім структурним програмуванням. Однак цілі структурного програмування набагато глобальніші та серйозніші.
1. ОСНОВИ ТЕХНОЛОГІЇ СТРУКТУРНОГО ПРОГРАМУВАННЯ
Структурне програмування - методологія розробки програмного забезпечення, В основі якої лежить уявлення програми у вигляді ієрархічної структури блоків. Запропоновано у 70-х роках XX ст. Е.Дейкстрой, розроблена та доповнена Н.Віртом (рис. 1).
Едсгер Вібе Дейкстра (1930 – 2002) - нідерландський учений, ідеї якого вплинули в розвитку комп'ютерної промисловості. Відомий як творець алгоритму пошуку найкоротшого шляху на графі, один із засновників структурного програмування. У 1972 р. став лауреатом премії Т'юрінга.
Ніклаус Вірт (1934) - швейцарський учений, фахівець у галузі інформатики, один із найвідоміших теоретиків у галузі розробки мов програмування, професор комп'ютерних наук, лауреат премії Тьюринга 1984 р. Провідний розробник мов програмування Паскаль, Модула-2, Оберон.
Мал. 1. Піонери структурного програмування – Е.Дейкстра та Н.Вірт.
Методологія структурного програмування виникла як наслідок зростання складності розв'язуваних на комп'ютерах завдань, і відповідного ускладнення програмного забезпечення: у роки XX в. обсяги та складність програм досягли такого рівня, що «інтуїтивна» (неструктурована) розробка програм, яка була нормою більш ранній час, перестала задовольняти потреби практики. Програми ставали надто складними, щоб їх можна було нормально супроводжувати, тому знадобилася якась систематизація процесу розробки та структури програм.
Найбільш сильну критику з боку розробників структурного підходу до програмування зазнав операторGOTO ( оператор безумовного переходу ). Неправильне та необдумане використання довільних переходів у тексті програми призводило до отримання заплутаних, погано структурованих програм (т.зв.спагетті-коду ), за текстом яких практично неможливо було зрозуміти порядок виконання та взаємозалежність фрагментів.
В основі структурного програмування лежать принципипослідовної декомпозиції завдання тацілеспрямованого їїструктурування на окремі складові. Методи структурного програмування є комплексом технічних і організаційних принципів системного проектування програмних продуктів.
Типовими методами структурного програмування є:
низхідне проектування (Проектування зверху вниз);
модульне (процедурне)програмування ;
структурне кодування .
Відповідно до методології структурного програмування:
1. Будь-яка програма є структурою, побудованою з трьох типівбазових конструкцій:
послідовне виконання - одноразове виконання операцій у тому порядку, у якому вони записані у тексті програми;
розгалуження - одноразове виконання однієї з двох або більше операцій, залежно від виконання певної заданої умови;
цикл - багаторазове виконання однієї й тієї ж операції доти, доки виконується деяке задане умова (умова продовження циклу).
У програмі базові конструкції можуть бути вкладені одна в одну довільним чином, але жодних інших засобів управління послідовністю виконання операцій не передбачається.
2. фрагменти програми, що повторюються (або не повторювані, але являють собою логічно цілісні обчислювальні блоки) можуть оформлятися у виглядіпідпрограм (Процедури або функції). У цьому випадку в тексті основної програми замість поміщеного в підпрограму фрагмента вставляється інструкція виклику підпрограми. При виконанні такої інструкції виконується викликана підпрограма, після чого виконання програми продовжується з інструкції, яка йде за командою виклику підпрограми.
3. Розробка програми ведеться покроково, шляхом «згори донизу».
Спочатку пишеться текст основної програми, в якому замість кожного зв'язкового логічного фрагмента тексту вставляється виклик підпрограми, яка виконуватиме цей фрагмент. Замість справжніх підпрограм, що працюють, в програму вставляються «заглушки », які нічого не роблять. Отримана програма перевіряється та налагоджується. Після того, як програміст переконається, що підпрограми викликаються у правильній послідовності (тобто. загальна структура програми правильна), підпрограми-заглушки послідовно замінюються на реально працюючі, причому розробка кожної підпрограми ведеться тим самим методом, що й основний програми. Розробка закінчується тоді, коли не залишиться жодної заглушки, яка не була б видалена. Така послідовність гарантує, що на кожному етапі розробки програміст одночасно має справу з доступною для огляду і зрозумілою йому безліччю фрагментів, і може бути впевнений, що загальна структура всіх вищих рівнів програми вірна. При супроводі та внесенні змін до програми з'ясовується, до яких саме процедур потрібно внести зміни, і вони вносяться, не торкаючись частини програми, безпосередньо не пов'язані з ними. Це дозволяє гарантувати, що при внесенні змін та виправленні помилок не вийде з ладу якась частина програми, яка перебуває в даний момент поза зоною уваги програміста.
Дотримання принципів структурного програмування зробило тексти програм, навіть досить великих, які нормально читаються. Серйозно полегшилося розуміння програм, з'явилася можливість розробки програм у нормальному промисловому режимі, коли програму може без особливих труднощів зрозуміти як її автор, а й інші програмісти. Це дозволило розробляти досить великі на той час програмні комплекси силами колективів розробників, і супроводжувати ці комплекси багато років, навіть у умовах неминучих змін у складі персоналу.
Методологію структурної розробки програмного забезпечення було визнано «найсильнішою формалізацією 70-х років». Після цього слово «структурний» стало модним у галузі, і його почали використовувати скрізь, де треба та де не треба. З'явилися роботи із «структурного проектування», «структурного тестування», «структурного дизайну» тощо.
До переваг структурного програмування можна віднести наступне:
1. Структурне програмування дозволяє значно скоротити кількість варіантів побудови програми за однією і тією ж специфікацією, що значно знижує складність програми та полегшує розуміння її іншими розробниками.
2. У структурованих програмах логічно пов'язані оператори знаходяться візуально ближче, а слабко пов'язані - далі, що дозволяє обходитися без блок-схем та інших графічних форм зображення алгоритмів (по суті сама програма є власною блок-схемою).
3. Сильно спрощується процес тестування та налагодження структурованих програм.
Розглянемо докладніше основні методи структурного програмування.
1.1. Цілі та принципи структурного програмування
Цілями структурного програмування є:
уникати використання мовних конструкцій із неочевидною семантикою;
прагнути до локалізації дії керуючих конструкцій та використання структур даних;
розробляти програму те щоб її можна було читати від початку остаточно без управляючих переходів в іншу сторінку.
Забезпечення дисципліни програмування у процесі створення програмних комплексів .
Поліпшення читабельності програми . Читабельність покращується, якщо дотримуватись наступних правил:
Підвищення ефективності програм . Цього можна досягти, якщо виконувати структурування програми, розбиваючи її на модулі так, щоб можна було легко знаходити та коригувати помилки, а також щоб текст будь-якого модуля з метою збільшення ефективності можна було переробити незалежно від інших.
Підвищення надійності програм . Цього можна досягти, якщо програма легко піддаватиметься наскрізному тестуванню і не створить проблем для організації процесу налагодження. Це забезпечується хорошим структуруванням програми при розбивці її на модулі та виконання правил написання читабельних програм.
Зменшення часу та вартості програмної розробки . Це відбувається в тому випадку, якщо кожен програміст команди розробників стає здатним писати та налагоджувати більше програмного коду, ніж раніше.
Основніпринципи структурного програмування зведені у табл. 1.
Таблиця 1. Принципи структурного програмування
Принцип
Пояснення
Абстракція
Абстракція дозволяє програмісту уявити необхідне вирішення проблеми без негайного обліку безлічі деталей. Програміст може розглядати програму за рівнями: верхній рівень показує велику абстракцію, полегшує погляд на проект, тоді як нижній рівень показує дрібні деталі реалізації.
Формальність
Використання розробки програми суворого методичного підходу, що є основою перетворення програмування з імпровізації в інженерну дисципліну. Цей принцип дає підстави докази правильності програм, оскільки дозволяє вивчати програми (алгоритми) як математичні об'єкти.
"Розділяй і володарюй"
Поділ програми на окремі фрагменти (модулі), які прості за керуванням і допускають незалежне налагодження та тестування.
Ієрархічне впорядкування
Структура розбиття на частини не менш важлива, ніж факт такого поділу. Цей принцип висуває вимогу ієрархічного структурування взаємозв'язків між модулями програмного комплексущо полегшує досягнення цілей структурного програмування.
1.2. Низхідне проектування
Специфікація завдання є відправною точкою у створенні програми. Потрібно зрозуміти, які дії повинні бути вчинені для вирішення завдання, описати їх природною мовою і на досить високому рівні абстракції.
Специфікація завдання є його первинним проектом. Від неї ми рухаємось до програми, поступово уточнюючи опис.
Поступове уточнення проекту називаєтьсяметодом проектування зверху донизу ( покрокової деталізації абонизхідного проектування ).
приклад 1. Як приклад розглянемо проект одягання дитини.
Рішення:
1. Первинна мета :
Одягнути.
2. Конкретизація мети першому кроці :
Одягнути нижню половину.
Одягнути верхню половину.
2.1. Нижню половину можна одягнути у два етапи:
Одягти штани.
Одягти шкарпетки та черевики.
2.2. Верхню половину можна також одягнути у два етапи:
Одягти сорочку.
Одягти куртку.
3. Остаточний проект виглядає так:
Одягти штани.
Одягти шкарпетки.
Одягти черевики.
Одягти сорочку.
Одягти куртку.
Метод низхідного проектування передбачає послідовне розкладання загальної функції обробки даних про прості функціональні елементи («згори-вниз»). В результаті будується ієрархічна схема –функціональна структура алгоритму ( ФСА ), що відображає склад та взаємопідпорядкованість окремих функцій (рис. 2).
Додаток 1
додаток n
Функція 1
Функція 2
Функція m
Підф-ція 11
Підф-ція 1 k
Підф-ція m 1
Підф-ція m 2
Підф-ція mp
Ціль 1
Підціль 11
Підціль 1s
Ціль2
Підціль2 1
Підціль2 q
Мал. 2. Функціональна структура програми
Послідовність дій щодо розробки ФСА додатка така:
визначаютьсяцілі автоматизації предметної області та їх ієрархія (ціль-підціль);
встановлюєтьсясклад додатків (Завдань обробки), що забезпечують реалізацію поставлених цілей;
уточнюєтьсяхарактер взаємозв'язку додатків та його основні характеристики (інформація на вирішення завдань, час і періодичність рішення, умови виконання та інших.);
визначаються необхідні вирішення завданьфункції обробки даних ;
виконуєтьсядекомпозиція функцій обробки до необхідної структурної складності, що реалізується передбачуваним інструментарієм.
Подібна структура програми відображає найважливіше –склад івзаємозв'язок функцій обробки інформації для реалізації програми, хоч і не розкриває логіку виконання кожної окремої функції, умови або періодичність їх викликів.
1.3. Модульне програмування
Модульне програмування є природним наслідком проектування зверху донизу і полягає в тому, що програма розбивається на частини.модулі , що розробляються окремо.
Модуль – це самостійна частина програми, що має певне призначення та забезпечує задані функціїобробки автономно від інших програмних модулів. Модуль складається із логічно взаємопов'язаної сукупності функціональних елементів.
У програмуванні під модулем розуміється окремапідпрограма , а підпрограми часто називаютьсяпроцедурами абопроцедурами-функціями . Тому модульне програмування ще називаєтьсяпроцедурним .
Під час створення програмних продуктів виділяютьсямодулі, що багаторазово використовуються , Проводиться їх типізація та уніфікація, за рахунок чого скорочуються терміни та трудовитрати на розробку програмного продукту в цілому.
Деякі програмні продукти використовують модулі готових бібліотек стандартних підпрограм, процедур, функцій, об'єктів, методів обробки даних.
Серед безлічі модулів розрізняють:
головний модуль - Керує запуском програмного продукту (існує в однині);
керуючий модуль - Забезпечує виклик інших модулів на обробку;
робочі модулі - Виконують функції обробки;
сервісні модулі та бібліотеки , утиліти - реалізують обслуговуючі функції.
У роботі програмного продукту активізуються потрібні програмні модулі. Керуючі модулі задають послідовність виклику виконання чергового модуля. Інформаційна зв'язок модулів забезпечується з допомогою використання загальної бази даних чи міжмодульної передачі через змінні обміну.
Кожен модуль може оформлятися як файл, що самостійно зберігається; Для функціонування програмного продукту потрібна наявність програмних модулів у складі.
Модуль повинен мати наступнівластивостями :
один вхід та один вихід – на вході програмний модуль отримує певний набір вихідних даних, виконує змістовну обробку та повертає один набір результатних даних, тобто. реалізується стандартний принципIPO ( Input-Process-Output – вхід-процес-вихід );
функціональна завершеність – модуль виконує перелік регламентованих операцій для реалізації кожної окремої функції у повному складі, достатніх для завершення розпочатої обробки;
логічна незалежність – результат роботи програмного модуля залежить тільки від вихідних даних, але не залежить від інших модулів;
слабкі інформаційні зв'язки з іншими програмними модулями – обмін інформацією між модулями має бути по можливості мінімізований;
доступний для перегляду за розміром і складністю програмний код .
Модулі містять:
визначення доступних для обробки даних;
операції обробки даних;
схеми взаємозв'язку коїться з іншими модулями.
Кожен модуль складається зспецифікації ітіла . Специфікації визначають правила використання модуля, атіло - Спосіб реалізації процесу обробки.
Однотипні функції реалізуються одними й тими самими модулями. Функція верхнього рівня забезпечується основним модулем; він управляє виконанням нижчестоящих функцій, яким відповідають підлеглі модулі.
При визначенні набору модулів, що реалізують функції конкретного алгоритму, необхідно враховувати таке:
кожен модуль викликається на виконання вищестоящим модулем і, закінчивши роботу, повертає управління модулю, що викликав його;
прийняття основних рішень в алгоритмі виноситься на максимально «високий» за ієрархією;
для використання однієї й тієї функції в різних місцях алгоритму створюється один модуль, який викликається на виконання в міру необхідності.
В результаті подальшої деталізації алгоритму створюєтьсяфункціонально-модульна схема ( ФМС ) алгоритму програми, що є основою програмування (рис. 2).
Склад та вид програмних модулів, їх призначення та характер використання у програмі значною мірою визначаються інструментальними засобами.
Другий рівень ієрархії програми
Перший рівень ієрархії програми
Головний модуль
(Програма-сервер)
Модуль керування 1
(Управління прогр. 1)
Модуль керування n
(Кер. прогр. n)
Модуль 1A
(Підпрогр. 1А)
Модуль 1В
(Підпрогр. 1В)
Модуль 1W
(Підпрогр. 1 W )
Модуль 0A
(Підпрогр. 0А)
Модуль 0B
(Підпрогр. 0B)
Модуль nA
(Підпрогр. nА)
Модуль nB
(Підпрогр. nB)
Модуль nW
(Підпрогр. nW)
Третій рівень ієрархії програми
Мал. 3. Функціонально-модульна структура алгоритму застосування
Більшість сучасних програм прикладного характеру, орієнтованих кінцевого користувача, працюють у діалоговому режимі взаємодії з користувачем в такий спосіб, що ведеться обмін повідомленнями, які впливають обробку даних. У діалоговому режимі під впливом користувача здійснюються запуск функцій обробки, зміна властивостей об'єктів, налаштовує параметри видачі інформації тощо. Діалоговий процес управляється згідно з створеним сценарієм, для якого визначаються:
точки (момент, умова) початку діалогу;
ініціатор діалогу – людина чи програмний продукт;
параметри та зміст діалогу – повідомлення, склад та структура меню, екранні форми тощо;
реакція програмного продукту завершення діалогу.
Для створення діалогових процесів та інтерфейсу кінцевого користувача найбільше підходятьоб'єктно-орієнтовані інструментальні засобирозробки програм .
1.4. Структурне кодування
Практика програмування показала необхідність науково обґрунтованої методології розробки та документування алгоритмів та програм. Ця методологія повинна стосуватися аналізу вихідної задачі, поділу її на досить самостійні частини та програмування цих частин наскільки можна незалежно друг від друга. Такою методологією єструктурне кодування ( програмування ).
Структурне кодування - це метод написання програм, що мають певну структуру та за рахунок цього зручних для розуміння, тестування, модифікації та використання.
Даний метод заснований на використанні невеликого набору простих керуючих структур (структурних операторів ), правильність роботи яких легко проаналізувати та встановити. При цьому одні оператори складаються з інших вкладених у них.
Властивість структурності операторів у тому, щокожен оператор має один вхід та один вихід . Програма, побудована із структурних операторів, називаєтьсяструктурованою .
Фундаментом структурного програмування єтеорема про структурування , сформульована італійськими математиками К.Бомом та Дж.Якопіні у 1966 р.
Теорема встановлює, що хоч би як складне завдання, схему алгоритм її розв'язання (і, відповідно, програму) можна у вигляді композиції трьох типів вкладених блоків:
слідування (begin-end – початок кінець ),
розгалуження (if - then - else – колись інакше ),
циклів з передумовою (while – Бувай ).
Іншими словами, ці елементарні структури маютьфункціональною повнотою , тобто. будь-який алгоритм може бути реалізований у вигляді композиції цих трьох структур.
На практиці дана теорема дозволяє уникнути використання операторів переходуgoto , що робить алгоритми та програми наочними та легко зрозумілими.
Види основних керуючих структур алгоритму наведено на рис. 4.
1. Структура типу «слідування » (Рис. 4, а) - утворюється послідовністю дій, S 1, S 2, …, Sn, наступних одне за одним:
виконатиS 1;
виконатиS 2;
виконатиSn .
У лінійному обчислювальному процесі всі операції виконуються послідовно у порядку їх запису. Типовим прикладом такого процесу є стандартна обчислювальна схема, що складається з трьох етапів:
введення вихідних даних;
обчислення за формулами;
виведення результату.
У мовіPascal така структура полягає в операторні дужкиBegin ... End :
Begin
S 1;
S 2;
...
Sn ;
End
Мал. 4. Базові алгоритмічні структури:
а) слідування (Begin – End ); б) розгалуження (If – Then – Else ); в) цикл із передумовою (While – Do )
2. Структура типу « розгалуження » (ЯКЩО – ТО – Інакше ) (рис. 4,б ) – забезпечує залежно від результату перевірки умовиР , що приймає одне з двох логічних значеньТак (True ) абоНі (False ), вибір одного з альтернативних шляхів роботи алгоритму:
якщо Р
то виконати S 1
інакше виконати S 2 .
Кожен із шляхів веде до загального виходу, тому робота алгоритму буде продовжуватися незалежно від того, який шлях буде обраний.
У мовіPascal
If P
Then S 1
Else S 2;
3. Структура типу «цикл із передумовою » (Рис. 4, в) – забезпечує багаторазове виконання дії Sв залежності від того, яке значення набуває логічна умова Р:
доти покиР
виконуватиS .
Виконання циклу припиняється, коли умова Рне виконується.
У мові Pascalтака структура має такий формат:
While P Do
S ;
До розширеного комплекту елементарних алгоритмічних структур додатково входять такі керуючі конструкції (рис. 5).
4. Структура типу « скорочене розгалуження » (ЯКЩО ТО ) (рис. 5,а ) – якщо результат перевірки умовиР приймає значенняТак (True ), то виконується діяS ; в іншому випадку ця дія пропускається та управління передається наступній структурі:
якщо Р
то виконати S 1 .
У мовіPascal така структура має такий формат:
If P
Then S ;
5 . Структура типу « вибір – інакше » (рис. 5,б ) є розширеним варіантом структури типуЯКЩО – ТО – Інакше . Тут перевірена умоваР може приймати не два логічні значення, а кілька порядкових значень, наприклад, 1, 2, …,n . ЯкщоР = i , то виконуватиметься діяSi . Якщо ж значенняР буде виходити з діапазону допустимих значень, то виконується діяS (у укороченому варіанті «вибір » ніякої дії не провадиться і управління передається до наступної структури. У мовіPascal така структура має такий формат:
Case P Of
1: S1;
2: S2;
…
n: Sn
Else S
End;
Мал. 5. Додаткові елементарні алгоритмічні структури:
а)
скорочене розгалуження
(If
–
Then
);
б)
вибір – інакше
(Case
–
Of
–
Else
);
в)
цикл із постумовою
(Repeat
–
Until
);
г)
цикл із параметром
(For
–
To
(
Downto
) –
Do
)
6. Структура типу « цикл із постумовою » (рис. 5,в ) – забезпечує багаторазове виконання діїS доти, доки не виконується умоваР .
У мовіPascal така структура має такий формат:
Repeat
S
Until P ;
7. Структура типу « цикл із параметром » (рис. 5,г ) – забезпечує заздалегідь визначене багаторазове виконання діїS . При цьому тут послідовно виконуються такі типові операції:
завдання початкового значення використовуваного параметра циклу (наприклад, якщо змінної циклу є i, то їй надається значення i 1, тобто. i:=i 1);
виконання дій S, передбачених у тілі циклу;
зміна параметра циклу, який забезпечує обчислення результату з новими початковими даними (наприклад, якщо параметр циклу iзмінюється з кроком i 3, i:=ii 3);
перевірка поточного значення параметра циклу із заданим кінцевим значенням ( i<=i 2);
перехід до повторення тіла циклу, якщо параметр циклу не перевищив кінцевого значення, інакше виконання наступних дій або виведення результату.
У мовіPascal така структура має такий формат:
For Змінна := i 1 To (Downto) i 3 Do
S ;
Розглядаючи схему програми, можна назвати у ній частини (фрагменти), досить прості і зрозумілі структурою. Подання цих фрагментів укрупненими блоками істотно полегшує сприйняття алгоритму (а надалі програми) загалом.
Структурні оператори зазвичай використовуються вже на ранніх стадіях низхідного проектування програми.
Таким чином,структурне програмування засноване намодульної структури програмного продукту татипових (базових ) керуючих структурах алгоритмів обробки даних різних програмних модулів
ВИСНОВКИ
Структурне програмування - методологія розробки програмного забезпечення, основу якої уявлення програми як ієрархічної структури блоків. Запропоновано у 70-х роках XX ст. Е.Дейкбуд, розроблена та доповнена Н.Віртом. Типовими методами структурного програмування є: низхідне проектування (проектування зверху донизу); модульне (процедурне) програмування; структурне кодування
Цілями структурного програмування є: забезпечення дисципліни програмування, підвищення ефективності та надійності програм, зменшення часу та вартості програмної розробки. Основні засади структурного програмування: абстракція, формальність, «розділяй та володарюй», ієрархічне впорядкування.
Метод низхідного проектування передбачає послідовне розкладання загальної функції обробки даних про прості функціональні елементи («згори-вниз»). Засоби досягнення цілей на попередньому рівні перетворюються на цілі на нижньому.
Структурне кодування - це спосіб написання програм, мають певну структуру. Він ґрунтується на використанні невеликого набору структурних операторів, правильність яких легко проаналізувати та встановити. При цьому одні оператори складаються з інших вкладених у них.
Фундаментом структурного програмування є теорема про структурування, сформульована італійськими математиками К.Бомом та Дж.Якопіні в 1966 р. Теорема встановлює, що хоч би якою складною була задача, схему алгоритм її вирішення (і, відповідно, програму) завжди можна представити у вигляді композиції трьох типів вкладених блоків: прямування (begin-end – початок-кінець), розгалуження (if-then-else – колись інакше), циклів з передумовою (while – поки).
* Е.Дейкстра дав таке визначення: « Структурне програмування - це дисципліна, яку програміст нав'язує сам собі».
Структурне програмування - одне з найбільших досягнень у технології програмування. Хоча найзагальніше і досить невиразне уявлення про структурне програмування є майже у всіх, загальноприйнятого чіткого його визначення немає. Структурне програмування ставить за мету писати програми мінімальної складності, змусити програміста мислити ясно, полегшити сприйняття програми.
Текст програми має бути таким, щоб його можна було читати «зверху – вниз». Необмежене використання операторів безумовного переходу (GO TO ) порушує цю умову, тому структурне програмування часто називають програмуванням без GO TO.
Можна навести приклади програм, які не містять GO TO , і акуратно розташовані драбинкою відповідно до рівня вкладеності операторів, але абсолютно незрозумілі і бувають інші програми, що містять GO TO і все ж таки зрозумілі. Отже наявність чи відсутність GO TO - поганий показник якості програми (ілюстрації в Д. Кнут). І все ж таки: найбільш важко контрольованим і потенційно нестійким є оператор безумовного переходу - GO TO.
Структура тіла модулів і базові конструкції програмування, що використовуються, повинні бути потенційно стійкими до апаратурних збоїв, спотворень вихідних даних і до помилок у програмах.
Будь-яку програму можна синтезувати на основі елементарних базових конструкцій трьох типів:
1. Проста послідовність. 2. Умови (альтернативи).
3. Повторення (цикли, ітерації). Можливі один із двох або обидва види:
Робити «поки що» Робити «поки що»
4. Можна додати четверту конструкцію – вибір (перемикач).
Блоки визначаються рекурсивно: прямокутники зображують вкладені будівельні блоки, які використовуються замість прямокутника.
Перелічені елементарні конструкції, наприклад, у мові Паскаль реалізовані так:
Умовний оператор IF лог. вир. THEN оператор 1 ELSE оператор2;
IF лог. вираз THEN оператор;
Повторення (цикли, ітерації)
а) Робити «поки що» WHILE умова продовження DO оператор;
б) Робити «поки що» REPEAT оператор UNTIL умова завершення;
в) Цикл з перебором FOR К: = В1 ТО В2 DO оператор;
FOR K:=B2 DOWNTO B1 DO оператор;
Вибір (перемикач) CASE умова OF
N1, ... Nk: оператор 1;
Ni ... Nm : оператор п;
END;
У мові FoxBASE ці конструкції реалізовані у вигляді:
Умовний оператор IF лог. вираз
оператори1
[ ELSE
оператори2]
ENDIF
Цикл DO WHILE вираз
оператори
ENDDO
Вибір (перемикач) DO CASE
CASE лог. вираз 1
оператори
CASE лог. вираз2
Оператори
CASE лог. Вираз п
Оператори
ENDCASE
Кожна структура характеризується єдиною точкою передачі управління структуру (єдиний вхід) і єдиною точкою виходу зі структури.
Ці конструкції мають систематизуюче та дисциплінуюче значення. Простота вихідних конструкцій структурного програмування запобігає появі складних інформаційних зв'язків та заляканих передач управління.
При підвищенні структурованості модулів знижується складність програм, зростає їхня наочність, що сприяє скороченню числа помилок. Проте за підвищення якості програм доводиться розплачуватись додатковою пам'яттю та часом їх реалізації на ЕОМ.
Структурність програми залежить від мови програмування, що використовується. Сучасні програмні засоби розробки програм є найкращими мовами структурного програмування. З поширених мов програмування найбільш підходящими вважаються Паскаль, Basic, FoxBASE. Структурне програмування, наприклад, мовою Асемблер майже неможливе. Сам факт використання мови асемблера вказує на те, що програма написана в основному в термінах машинної мови.
Структурне програмування орієнтоване спілкування з людьми, а чи не з машиною, сприяє написанню програм, що становлять просте і ясне рішення завдання.
Важливо, щоб програміст, тільки приступаючи до програмування логіки, мислив у термінах основних базових структурних конструкцій.
Позиція щодо оператора GO TO має бути такою: уникати використання GO TO усюди, де це можливо, але не ціною ясності програм. Часто виявляється доцільним використовувати GO TO для виходу з циклу або модуля, для переходу в конструкції ON (наприклад, в мові Basic ) або щоб уникнути занадто великої глибини вкладеності розвилок, тим більше що перехід здійснюється на наступні (розташовані нижче) оператори програми та структурна програма продовжує залишатися легко читається зверху донизу. Найгіршим застосуванням оператора GO TO вважається передача управління оператором, розташованим вище (раніше) у тексті програми.
Крім того, щоб полегшити читання програми, її текст необхідно розбити фізично на частини, додаючи порожні рядки між розділами, підрозділами. Текст програми повинен бути написаний з правильними зрушеннями, тому розриви в послідовності виконання легко простежуються. Одноцільові пропозиції кожного модуля повинні поміщатися на одній сторінці друкуючого пристрою.
Перші програми складалися з кількох десятків – сотень машинних команд. Програмні комплекси та інформаційні системи включали від декількох десятків тисяч до мільйонів операторів мовами високого рівня. У міру збільшення обсягу програмних засобів на перше місце за впливом на швидкість їх розробки вийшов процес налагодження,тобто. виявлення та виправлення допущених помилок. Практика показала, що написати більш-менш велику програму без помилок практично неможливо. Більше того, навіть під час експлуатації готових програм виявляються пропущені при налагодженні помилки. Помилки поділяються на кілька категорій.
Найпростіша – синтаксичні помилки. Вони пов'язані з неправильним написанням конструкцій мови і виявляються відразу, коли компілятор намагається перекласти програму на машинну мову
Якщо виправлені всі синтаксичні помилки та помилки компонування, програма починає виконуватися (стадія Run).Однак ця стадія може бути перервана неприпустимою операцією (наприклад, розподілом на нуль), і в цьому випадку говорять про помилки часу виконання (RunTime Errors).Або програма дорахувала остаточно, але отримані результати виявляються неправильними. Викликати це можуть помилки алгоритму, або помилки організації міжмодульних зв'язків, помилки перетворення типів даних, або прості описки (наприклад, пропущений нуль під час запису 100 і програма використовувала в обчисленнях 10).
Помилки часу виконання виявляються рішенням серії тестових прикладів (прогін програми),результат яких відомий заздалегідь. Як правило, час, витрачений на пошук подібних помилок, суттєво перевищує час написання самої програми та виправлення синтаксичних помилок. Розвиток концепції програмування був із проблемою зниження шлюбу під час написання програми.Розробляються теоретичні основи структурного програмування, теорія доказу правильності програми, доказове програмування.
Концепція структурного програмування передбачає такий науково обґрунтований підхід до побудови програми та до можливостей мови програмування, при якому буде суттєво знижено обсяг можливих помилок. Істотний розвиток концепції досягнуто у мові структурного програмування Pascal. Суть структурного програмування у тому, що дані є, передусім, абстракції реальних об'єктів і формулюються переважно як абстрактні структури, які можуть мати конкретної реалізації у мові програмування. У процесі конструювання програми подання даних поступово уточнюється за уточненням алгоритму.
Мова структурного програмування має надавати можливість конструювання власних типів даних. На нижчому рівні стоять зумовлені у мові фундаментальні структури (наприклад: скалярні типи, запис, масив та безліч). З фундаментальних структур, як із молекул, будують ускладнені структури. Змінні фундаментальної структури можуть змінювати тільки значення, зберігаючи тип або безліч допустимих значень і розмір, який він займає. Ускладнені структури характеризуються зміною як значення, а й самої форми уявлення, складом входять до них фундаментальних структур. Динамічне управління пам'яттю реалізується лише на рівні покажчиків, і динамічні дані об'єднуються в деревоподібну структуру (дерева).
З іншого боку, пред'являються певні вимоги до типізації даних, рахунок чого тип будь-якого висловлювання чи змінної можна визначити без необхідності проведення обчислень, тобто. на стадії трансляції При цьому можна уникнути великої кількості важко помилок часу виконання за рахунок виявлення їх на стадії трансляції програми.
Концепція структурного програмування передбачає як використання спеціальних мов і застосування певного стилю програмування. Насамперед це - філософія програмування, яка зачіпає і такий аспект, як методика навчання програмістів.
Зазначається, що програмування є великою і різноманітною діяльністю, що часто вимагає складної розумової роботи. Невірно вважати, що програмування можна звести до використання готових рецептів, що базуються на систематичному описі найпростіших блоків. В учнів необхідно розвивати здатність творчо мислити, і тут надзвичайно важлива роль вчителя, який показує, як він робить те й те. Творчість не підвладна канонам, методикам та технологіям. Як метод навчання приймається ретельний вибір та розгляд характерних прикладів. Необхідно розглядати складні та довгі програми, які часто й зустрічаються на практиці і найкраще підходять для виявлення тієї невловимої, але важливої властивості, яка називається стилемпрограмування. Розбір довгих програм служить вправою у мистецтві їх читання, що менш важливо, ніж вміння писати програми.Контрольні питання та завдання
5.1. Назвіть та коротко охарактеризуйте частини команди програми.
5.2. Основою для програми функціонування УОДІ є ____; дайте його визначення.
5.3. Що розуміється під програмуванням у кодах?
5.4. Що Ви знаєте про мову асемблер?
5.5. Які мови програмування називають машинно-незалежними?
5.6. Як здійснюється «переклад» програми, написаної алгоритмічною мовою в об'єктний код, зрозумілий комп'ютеру?
5.7. Що розуміється під модульним програмуванням та окремим модулем?
5.8. Що Ви знаєте про структурне програмування?
Структурне програмування– методологія програмування, спрямовану створення логічно простих і зрозумілих програм. Структурне програмування ґрунтується на припущенні, що логічність та зрозумілість програми полегшує розробку, доказ правильності та подальший супровід програми, а також забезпечує її надійність.
Характерними принципами структурного програмування є:
· низхідне програмування –метод розробки програм, у якому програмування ведеться шляхом «згори-вниз», від загального до деталей;
· модульне програмування, При якому відносно незалежні підзавдання програмуються у вигляді окремих програмних модулів;
· Використання при програмуванні трьох структур управління (слідування, вибір, повторення). Структура проходження передбачає природну послідовність виконання операторів. Структура вибір задається схемою «якщо – інакше» (умовний оператор if). Структурі повторення зіставлено оператора циклу;
· Відмова від безумовних передач управління та обмежене використання глобальних змінних.
В основі структурного програмування лежить теорема, яка була суворо доведена теорією програмування. Суть її в тому, що алгоритм для вирішення будь-якого логічного завдання можна скласти тільки зі структур , розгалуження, цикл». Їх називають базовими алгоритмічними структурами. По суті, ми і раніше в усіх прикладах програм дотримувалися принципів структурного програмування.
Проходження – це лінійна послідовність дій (рис. 2.6):
Мал. 2.6. Слідування
Кожен блок може містити як просту команду, так і складну структуру, але обов'язково повинен мати один вхід і один вихід.
Розгалуження – алгоритмічна альтернатива. Управління передається одному з двох блоків залежно від істинності чи хибності умови. Потім відбувається вихід загальне продовження (рис. 2.7):
Мал. 2.7. Розгалуження
Цикл – повторення певної групи дій за умовою. Розрізняються два типи циклу. Перший – цикл із передумовою (рис. 2.8):
Мал. 2.8. Цикл із передумовою
Поки умова істинна, виконується серія, що утворює тіло циклу.
Другий тип циклічної структури – цикл із постумовою (рис. 2.9):
Мал. 2.9. Цикл із постумовою
Тут тіло циклу передує умові циклу. Тіло циклу повторює своє виконання, якщо умова хибна. Повторення закінчується, коли умова стане істинною.
Теоретично необхідним та достатнім є лише перший тип циклу – цикл із передумовою. Будь-який циклічний алгоритм можна збудувати з його допомогою. Це загальний варіант циклу, ніж цикл-до. Справді, тіло циклу до хоча б один раз обов'язково виконається, оскільки перевірка умови відбувається після завершення його виконання. А для циклу-поки можливий такий варіант, коли тіло циклу не виконається жодного разу. Тому в будь-якій мові програмування можна було б обмежитися лише циклом-поки. Однак у ряді випадків застосування циклу до виявляється більш зручним, і тому він використовується.
Іноді у літературі структурне програмування називають програмуванням без goto. Справді, за такого підходу немає місця безумовному переходу. Невиправдане використання у програмах оператора goto позбавляє її структурності, отже, всіх пов'язаних із цим позитивних властивостей: прозорості та надійності алгоритму. Хоча в усіх процедурних мовах програмування цей оператор є, проте, дотримуючись структурного підходу, його вживання слід уникати.
Складний алгоритм складається із з'єднаних між собою базових структур. Поєднуватися ці структури можуть двома способами: послідовнимі вкладеним.Ця ситуація аналогічна тому, що ми спостерігаємо в електротехніці, де будь-яка як завгодно складна електрична ланцюг може бути розкладена на послідовно і паралельно з'єднані ділянки.
Вкладені алгоритмічні структури є аналогом паралельно з'єднаних провідників. Тут більше підходить аналогія з матрьошками, поміщеними одна в одну. Якщо блок, що становить тіло циклу, сам є циклічною структурою, то, отже, мають місце вкладені цикли. У свою чергу, внутрішній цикл може мати в собі ще один цикл і т.д. У зв'язку з цим запроваджується уявлення про глибину вкладеності циклів. Так само і розгалуження можуть бути вкладеними один в одного.
Структурний підхід вимагає дотримання стандарту зображення блок-схем алгоритмів. Рисувати їх треба так, як це робилося у всіх наведених прикладах. Кожна базова структура повинна мати один вхід та один вихід. Нестандартно зображена блок-схема погано читається, втрачається наочність алгоритму.
Мови програмування Паскаль і Сі називають мовами структурного програмування. Вони є всі необхідні керуючі конструкції для структурної побудови програми. Наочність такої побудови надає структуризація зовнішнього вигляду тексту програми. Основний прийом, що використовується для цього – зрушення рядків, які повинні підкорятися наступним правилам:
Конструкції одного рівня вкладеності записуються на одному вертикальному рівні (починаються з однієї позиції у рядку);
Вкладена конструкція записується зміщеною рядком на кілька позицій вправо щодо зовнішньої для неї конструкції.
Структурна методика алгоритмізації – це не тільки форма опису алгоритму, але це ще й спосіб мислення програміста . Створюючи алгоритм, потрібно прагнути складати його із стандартних структур. Якщо використовувати будівельну аналогію, можна сказати, що структурна методика побудови алгоритму подібна до збирання будівлі зі стандартних секцій на відміну від складання по цеглині.
Ще одним найважливішим технологічним прийомом структурного програмування є декомпозиція розв'язуваної задачі на підзавдання – простіші з погляду програмування частини вихідної задачі. Алгоритми вирішення таких підзавдань називаються допоміжними алгоритмами. У зв'язку з цим можливі два шляхи у побудові алгоритму:
«згори донизу»: спочатку будується основний алгоритм, потім допоміжні алгоритми;
«знизу нагору»: спочатку складаються допоміжні алгоритми, потім основний.
Перший підхід ще називають методом послідовної деталізації, другий – складальним методом.
Складальний метод передбачає накопичення та використання бібліотек допоміжних алгоритмів, реалізованих у мовах програмування у вигляді підпрограм, процедур, функцій. При послідовної деталізації спочатку будується основний алгоритм, та був у нього вносяться звернення до допоміжним алгоритмам першого рівня. Після цього складаються допоміжні алгоритми першого рівня, в яких можуть бути звернення до допоміжних алгоритмів другого рівня, і т.д. Допоміжні алгоритми нижнього рівня складаються лише з простих команд.
Метод послідовної деталізації застосовується у будь-якому конструюванні складних об'єктів. Це природна логічна послідовність мислення конструктора: поступове заглиблення у деталі. У нашому випадку йдеться також про конструювання, але не технічних пристроїв, а алгоритмів. Досить складний алгоритм в інший спосіб побудувати практично неможливо.
У методі послідовної деталізації спочатку аналізується вихідне завдання. У ній виділяються підзавдання. Будується ієрархія таких підзавдань. Потім складаються алгоритми (або програми), починаючи з основного алгоритму (основної програми), далі – допоміжні алгоритми (підпрограми) з послідовним поглибленням рівня, доки отримаємо алгоритми, які з простих команд.
Перший крок до деталізації. Спочатку намітимо всі необхідні підпрограми, вказавши лише заголовки (специфікації). На місці тіла підпрограм запишемо коментарі, що пояснюють (такий вид підпрограми називається «заглушкою»). Напишемо основну частину програми. А потім повернемось до детального програмування процедур та функцій. На першому етапі програмування замість тіла підпрограми опишемо її призначення у формі коментаря.
Застосування структурного програмування дозволяє збільшити швидкість написання програм та полегшити налагодження написаної програми. Структурне програмування можливе і мовами програмування assembler, де не передбачено структурних операторів, подібних до структурних операторів мов програмування C, PASCAL, PL/M.
Програмування для універсальних комп'ютерів починалося з програмування в машинних кодах, потім з'явилися і почали свій розвиток мови високого рівня, потім Дейкбуд розвинулися принципи структурного програмування, на зміну структурному програмуванню прийшло об'єктне програмування і в даний час активно розвивається візуальне програмування.
Програмування для мікроконтролерів багато в чому повторює той самий шлях. Перехід від етапу до етапу залежить від доступних внутрішніх ресурсів мікроконтролерів. Ще кілька років тому використання мов високого рівня було неможливим через невеликий обсяг внутрішньої пам'яті програм. (У дешевих моделях мікроконтролерів ця ситуація зберігається досі.) В даний час з появою мікроконтролерів та з обсягом внутрішньої пам'яті в кілька десятків кілобайт з'являється можливість об'єктного проектування.
В даний час існує два способи написання програм: знизу вгору та зверху вниз. При написанні програми знизу вгору розпочати налагодження програми неможливо, не написавши повністю всю програму. При написанні програми зверху вниз, що є обов'язковим при структурному програмуванні, будь-якому етапі написання програми може бути оттранслирована і виконано, у своїй можна відстежити все алгоритмічні дії програми, написані на той час. Процес написання програми не відрізняється від процесу створення алгоритму. Більше того, ці етапи створення програми можна поєднати. Алгоритмічна дія, що виконується, відображається в назві підпрограми. Наприклад:
Основна ідея структурного програмування полягають у тому, що існує лише чотири структурні оператори. Використовуючи ці структурні оператори можна побудувати як завгодно складну програму.
Перший структурний оператор називається лінійний ланцюжок операторів. Будь-яке завдання може бути розбите на кілька підзавдань. Виконання підзавдань може бути доручено підпрограмі, в назві якої можна (і потрібно) відобразити підзавдання, яке має вирішувати ця підпрограма. На момент написання алгоритму (і програми) верхнього рівня нас не цікавить, як вирішуватиметься це завдання, тому замість справжньої підпрограми поставимо