69109

Теорія і методи структурного програмування

Лекция

Информатика, кибернетика и программирование

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

Украинкский

2014-09-30

143 KB

9 чел.

Лекція 18.Тема: Теорія і методи структурного програмування

План:

1. Теорія і методи структурного програмування

2. Низхідне проектування програм

3. Модульне програмування

4. Методи структурування програм

1. Теорія і методи структурного програмування

Методологія структурного програмування - це сукупність методів проектування та написання програм за жорсткими правилами, дотримання яких підвищує продуктивність праці програмістів, поліпшує читабельністъ і полегшує процес тестування програм [11]. Витоки цієї методології сягають 60-х років XX століття, коли швидкими темпами почала зростати складність програм, а отже, постала потреба у методах подолання такої складності. Методологія структурного програмування грунтується на трьох методах: низхідного проектування, модульного програмування і структурування програм.

2. Низхідне проектування програм

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

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

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

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

Специфікація інтерфейсів – це формалізований опис входів, виходів 1 функцій, що мають бути реалізовані програмним модулем. Коли інтерфейс модуля специфіковано, можна спробувати в явному вигляді записати його код. Якщо це зробити неможливо, модуль поділяють на певну кількість невеликих підмодулів. Коли модуль не можна ані закодувати, ані декомпонувати, його вважаютъ модулем-заглушкою, інтерфейс якого відомий, а реалізація - ні.

Одним із прийомів формалізованого підходу до низхідного проектування є метод ієрархічних діаграм, що позначається абревіатурою НІРО (від англ. Hierarchical Input Processing Output - діаграма входу, обробки, виходу). Згідно з цим методом структура всієї програми подається у вигляді дерева, в якому підпрограми зображуються вузлами, а їхні виклики - ребрами.

3. Модульне програмування

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

  •  спростити процес тестування і налагодження програми;
  •  розробити програму зусиллями більше ніж одного програміста;
  •  локалізувати дію змін і доповнень до програми в межах одного модуля;
  •  скоротити термін і вартість розробки програми.

Програму можна вважати модульною, якщо її логічна і фізична структура відповідає таким умовам:

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

Незалежність модулів є визначальним принципом модульного програмування. Це означає, що програма має бути поділена на модулі таким чином, щоб зв'язки між модулями були слабкими, а зв'язки всередині модулів — сильними. Точніше, модулі можуть вважатися незалежними, якщо вони задовольняють таким вимогам:

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

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

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

4. Методи структурування програм

Методи низхідного проектування та модульного програмування регламентують процес побудови архітектури програм на макрорівні. Методи структурування, навпаки, працюють на мікрорівні, регламентуючи процес створення програмного коду. В основу методів структурування програм покладено теорему про структурування, що її у 1965 році довели Бом і Джакопіні. Згідно з цією теоремою будь-яку програму можна побудувати з використанням лише трьох керуючих структур: послідовності, вибору і повторення.

Метою структурування є перетворення неструктурованої програми на еквівалентну їй структуровану, тобто таку, що складається з обмеженого набору керуючих алгоритмічних структур. Методи структурування грунтуються на поняттях функціонального вузла, а також на поняттях простої, елементарної і складеної програми [14].

Функціональним вузлом називається частина алгоритму, що має один вхід та один вихід. Прикладом функціонального вузла є окремий оператор - присвоєення, виклик процедури тощо.

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

Елементарна програма — це проста програма, що не містить підпрограм, які складаються більше ніж з одного вузла. Зазначимо, що існує лише обмежена кількість елементарних програм, з яких основними є три програми, які зображені на рис. 6.1.

Якщо функціональний вузол елементарної програми замінити елементарною програмою, утвориться складена програма. Якщо вузол складеної програми замінити елементарною програмою, знов утвориться складена програма. В такий спосіб із будь-якої множини елементарних програм утворюється певний клас складених програм. Так, множина {послідовність, ifthenelse} формує клас програм без циклів, а множина {ifthenelse, whiledo} приводить до утворення класу програм, які містять цикли. Отже, будь-яка підмножина множини елементарних програм є базисною множиною для певного класу складених програм. Складена програма, побудована з певної множини елементарних програм, називається структурованою.

 а

            б         в

Рис. 6.1. Основні елементарні програми: послідовність (а), вибір (б), цикл із передумовою (в)

Позначимо літерою S клас складених програм, базисна множина якого містить такі елементарні програми, як послідовність (рис. 6.1, а), вибір (ifthenelse, рис. 6.1, б) і цикл із передумовою (whiledo, рис. 6.1, в). Теорема про структурування стверджує, що будь-яку просту програму шляхом покрокового перетворення можна замінити функціонально еквівалентною структурованою програмою, що належить означеному вище класу S. Згадане покрокове перетворення здійснюється за переліченими нижче правилами.

  1.  Правило простоти: створення програми слід починати із простої програми;
  2.  Правило пакетування: кожну дію можна замінити двома послідовними діями;
  3.  Правило вкладання - кожну дію можна замінити будь-якою структурою керування;
  4.  Правила 2 і 3 можна застосовувати у будь-якій послідовності необмежену кількість  разів.

Принцип застосування правил пакетування та вкладання до простої програми продемонстровано на рис. 6.2.

Для перетворення неструктурованих програм у структуровані використовуються такі методи: дублювання кодів, введення змінної стану і метод булевих ознак [11].

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

 Правило   Правило

 пакетування   вкладання

Рис. 6.2. Застосування правил пакетування та вкладання до простої програми

Приклад 6.1. 

Розглянемо неструктуровану програму, блок-схема якої зображена на рис. 6.3. Блоки позначені ідентифікаторами модулів.

Рис. 6.3. Блок-схема неструктурованої пограми

Із блок-схеми видно, що модуль М5 не може розпочати своєї роботи доти, доки не стануть відомими результати роботи модулів М2 і М3. Як правило, в модулі М5 міститься фрагмент коду, що активізується під час виклику цього модуля з модуля М2, а також інший фрагмент коду, що активізується під час виклику модуля М5 з модуля М3.

Перетворимо зображену на рис. 6.3 неструктуровану програму, застосовуючи правила пакетування та вкладання. Зобразимо початкову програму як просту, що складається з елементарних програм типу вибору (ifthenelse). Користуючись правилом вкладання, розширимо блоки МХ і МУ, замінивши їх елементарними програмами типу ifthenelse. У результаті заміни модуль М5 продублюється (рис. 6.4.).

        

Рис. 6.4. Процес перетворення неструктурованої програми у структуровану

Метод введення змінної стану [11] застосовується до неструктурованих програм, що містять цикли. Процес перетворення неструктурованої програми у структуровану складається з таких кроків:

  •  у програму вводиться змінна стану, що її значення дорівнює номеру блока, на який буде передане керування після виконання поточних дій;
  •  функціоналыні блоки неструктурованої програми замінюються функціональними блоками, що виконують такі самі дії та надають змінній стану значення, що ідентифікує номер блока, на який передається управління.

Приклад 6.2.

Розглянемо блок-схему неструктурованої програми, що містить цикли (рис 6.5.). Кожному блоку приписано довільний номер.

У програму вводиться нова змінна і. Цій змінній присвоюється номер блока, на який потрібно передати керування. Зокрема, якщо істинна умова А, то цій змінній присвоюється номер блока В, тобто 2, якщо істинна умова С, змінній і присвоюється 1 - номер блок А.

Логічні блоки неструктурованої блок-схеми замінюються елементарними програмами типу ifthenelse, що послідовно перевіряють значення змінної стану. Гілки «Так» програм типу ifthenelse мають містити оператори присвоєння нових значень змінній стану і оператори перевірки певних умов початкової програми.

Блок-схему неструктурованої програми зображено на рис. 6.5, а блок-схему відповідної структурованої програми - на рис. 6.6.

                1

          Так

    2      3  

            Так

              5

    4

  Так

             

           0

Рис 6.5. Блок-схема неструктурованої програми, що містить цикли

Метод булевої ознаки використовується для перетворення неструктурованих програм, що містять цикли. В програму вводиться додаткова змінна, яка набуває значення true чи false. Доки змінна ознаки зберігає це значення, виконання циклу триває. Значення змінної ознаки всередині циклу модифікується лише за певних умов.

    Так

            

    

            Так

     Так

    Так

    

      Так

    Так

      Так

    Так

    Так

Рис. 6.6. Блок-схема структурованої циклічної структури

Приклад 6.3.

Розглянемо блок-схему неструктурованого циклу, що має одну точку входу та дві  точки виходу (рис. 6.7). У програму вводиться змінна flag, що ініціалізується нулем (false). Якщо істинною є умова P або Q, змінна flag набуває значення 1 (true), що приводить до виходу з циклу. В такий спосіб неструктурованнй цикл із двома виходами перетворюється на структурований цикл з одним виходом (рис. 6.8.).

        Так

Так

     Так

 Так

     Так

Рис. 6.7. Блок-схема неструктурованого     Рис. 6.8. Блок-схема структурованого

  циклу                циклу

Контрольні питання

1. Теорія і методи структурного програмування

2. Низхідне проектування програм

3. Модульне програмування

4. Методи структурування програм


 

А также другие работы, которые могут Вас заинтересовать

16164. Ответственность за должностные преступления в зарубежных странах. Учебное пособие 346.5 KB
  ОТВЕТСТВЕННОСТЬ ЗА ДОЛЖНОСТНЫЕ ПРЕСТУПЛЕНИЯ в зарубежных странах Москва Юридическая литература 1994 67 080 Работа подготовлена коллективом сотрудников Института законодательства и сравнительного правоведения при Правительстве Российской Федерации: п...
16165. Задержание лица, подозреваемого в совершении преступления. Учебное пособие 134.5 KB
  В пособии в форме тематической лекции, прочитанной в УрЮИ МВД России, рассматриваются понятие, цели, условия, основания, мотивы и процессуальный порядок производства задержания лица, подозреваемого в совершении преступления, а также основания освобождения лица от подозрения. Проводится разграничение фактического, административного, уголовно-процессуального задержания и заключения под стражу
16166. Криминалистика, тактика, организация и методика расследования преступлений. Учебное пособие 884.5 KB
  Учебник предназначен для слушателей факультета заочного обучения. В нем рассмотрены темы курса криминалистики по тактике, организации и методике расследования преступлений в соответствии с рабочей программой по криминалистике для Волгоградского юридического института России
16167. Расследование хищений чужого имущества. Учебное пособие 676 KB
  В учебном пособии рассмотрены общие положения методики расследования хищений чужого имущества, а также частные методики расследования хищений автотранспорта, предметов, имеющих особую ценность, серийных квартирных краж, хищений, совершаемых группами несовершеннолетних
16168. Уголовное право России. Учебное пособие 2.65 MB
  Г.М. Миньковский A.A. Магомедов В.П. Ревин УГОЛОВНОЕ ПРАВО РОССИИ Под общей редакцией заслуженного деятеля науки РФ доктора юридических наук профессора РЕВИНА В.П. УЧЕБНИК Общая и Особенная части. Рекомендуется к изданию редакционноиздательским советом Академии у
16170. Практика назначения наказания. Учебное пособие 500 KB
  С.А. Разумов ПРАКТИКА НАЗНАЧЕНИЯ НАКАЗАНИЯ Учебнопрактическое пособие Москва Институт международного права и экономики имени А.С. Грибоедова 2001 Разумов С.А. Р17 Практика назначения наказания: Учебнопра...
16171. Основы экологического права. Учебное пособие 1.38 MB
  МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ КРАСНОЯРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Т.Г. Пучинина Основы экологического права Учебное пособие Красноярск 1999 Издательский центр Красноярского государственного университета 660041 г. Красноярск пр. Свобод...
16172. Коммерческое право. Учебное пособие 1.36 MB
  Коммерческое право Предисловие Уважаемый читатель Вы открыли одну из замечательных книг изданных в серии Классический университетский учебник посвященной 250летию Московского университета. Серия включает свыше 150 учебников и учебных пособий рекомендов