Що таке структурований алгоритм?

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

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

Алгоритм вважається правильним, Якщо він реалізує зазначену функцію $f : D \to Y$, де $D \subset X$ – безліч вхідних даних, $X$ – тип вхідних даних, $Y$ – тип вихідних даних.

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

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

1.2. Абстракція даних

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

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

Формальною мовою ми можемо описати і тип інформаційної структури (метадані), і конкретну інформацію в цій структурі (дані), що ми і робимо, коли пишемо програму деякою мовою програмування.

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

Як ми можемо працювати з об'єктами без конкретизації мови їхнього опису? Використовувати абстрактну мову алгебри. (“Алгоритм” і “алгебра” – слова однокореневі.) Наприклад, ми можемо визначити такі абстракції, як: “цілі числа”, “дійсні (речові) числа”, “комплексні числа”, “класи відрахувань по модулю $m$” , "Многочлени", "матриці", "множини", "функції". (Останні дві абстракції надто абстрактні поза певним контекстом.) Кожну абстракцію інтерпретуватимемо як тип інформаційної структури, а елемент відповідної алгебраїчної конструкції – це інформаційна структура.

Але суто алгебраїчних структур недостатньо охоплення всіх типів інформаційних структур. Серед інформаційних структур популярними є таблиці, словники, дерева, мережі. І хоча їх можна визначити через множини та функції, таке визначення в контексті зберігання даних у пам'яті ЕОМ не завжди буде доречним.

Наприклад, як визначити інформаційну структуру "послідовність елементів деякого типу \(T\)"? Можна як безліч пар

а можна як сукупність об'єктів типу \(T\), для яких вказано порядок їх проходження:

\[a_1, \; a_2, \; \dots, \; a_n \in T\]

Для типу інформаційної структури, вираженої як алгебраїчної конструкції чи зв'язки об'єктів, будемо застосовувати термін абстрактний тип даних [АхоХопУль, с. 23]. Будь-який абстрактний тип даних передбачає набір операцій над об'єктами цього.

Операція над об'єктом є або запитом, який обчислює певну функцію від об'єкта, або модифікацієюяка змінює сам об'єкт за певним правилом.

1) "числова множина"

Операції над об'єктами:

запити: пошук елемента; кількість елементів;

Модифікація: додати елемент, видалити елемент.

Бінарні операції типу: об'єднання (cup), перетин (cap), різниця (setminus).

2) "логічне висловлювання"

Бінарні операції типу: кон'юнкція \(\&\), диз'юнкція \(\vee\).

Унарні операції типу: заперечення (lnot).

Бінарні операції типу: \(+, \; -, \; \cdot, \; /\).

4) "послідовність типу \(T\)"

Операції над об'єктами:

запити: значення заданого елемента; довжина послідовності;

модифікації: додати елемент, видалити елемент, змінити заданий елемент.

Бінарні операції типу: конкатенація (times).

Студенти стоять у черзі на заселення, і ми можемо подумки зробити над ними якісь обчислювальні операції – наприклад, упорядкувати по зростанню, розбити безліч студентів на два підмножини за деяким критерієм. Але при сортуванні ми не людей переставлятимемо, а працюватимемо з інформацією про студентів.

Інформацію про них можна подати у вигляді інформаційної структури, яка буде об'єктом абстрактного типу даних (\). Наприклад:

\[(школа, напрямок) \in R_1\] \[(регіон, населений\ пункт) \in R_2\]

\(R_1, R_2\) - відносини між типами. На \(n\)-арних відносинах засновані реляційні бази даних [Дунаєв, с. 249].

\[(ШЕН,\, ПМІ) \in R_1, \quad (ІШ,\, ПМІ) \notin R_1\] \[(Приморський\ край,\, Владивосток) \in R_2, \quad (Якутія,\, Москва ) \notin R_2\]

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

Отже, алгоритм зручно формулювати абстрактних термінах, тобто не конкретизуючи спосіб представлення об'єктів АТД. Це дозволяє відокремити побудову та аналіз обчислювальної процедури від способу зберігання даних та форми запису алгоритму. З одного боку, це зручніше, ніж намагатися пам'ятати все і відразу. З іншого боку, якщо абстрагуватися від зайвих деталей, то сформульований таким чином перебіг обчислень не залежатиме від реалізації окремих операцій, що підвищує ефективність розробки. Нарешті, абстракція даних може бути виражена явно на деяких мовах програмування (приклад – об'єктно-орієнтоване та узагальнене програмування в C++).

1.3. Структури даних та реалізація алгоритмів

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

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

Приклади уявлень АТД:

1) АТД "ціле число", ЦД "32-бітове ціле число зі знаком"

Безліч уявних об'єктів: \(-2^..2^-1\) (потужність безлічі \(2^\)).

Відповідність [Андрєєва, розд. 2.1]:

Для чисел \(n \in 0 .. 2^-1\): \(b_ = 0\), \((b_1, \dots, b_)\) - уявлення числа \(n\) у 2-їчній системі обчислення.

Для чисел \(n \in -2^..-1\): \(b_ = 1\), \((b_1, \dots, b_)\) – подання числа \(2^-|n|\) у 2-їчній системі числення.

2) АТД "послідовність типу \(T\)", ЦД "масив елементів типу \(T\)"

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

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

3) АТД "послідовність типу \(T\)", ЦД "зв'язковий список елементів типу \(T\)"

Елементи послідовності можуть зберігатися в пам'яті будь-де, а не тільки один за одним.Кожен елемент послідовності зберігається в пам'яті разом з посиланням на наступний елемент послідовності.

4) АТД "програма на ЯП Сі"

Безліч уявлень: послідовності рядків, побудовані за певними правилами.

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

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

Будь-який алгоритм, сформульований для обчислювальної машини на певній мові, є операцією над даними. до всього АТД) та запис цих операцій на певному ЯП.

Підсумок

Інформаційна структура - Це певний опис об'єкта, з яким ми працюємо.

Абстрактний тип даних - Це формальний опис.

Структура даних - це вказівка, в якому вигляді зберігати ці дані та як організувати доступ до них.

Алгоритм зручно формулювати в абстрактних термінах, тобто не конкретизуючи спосіб уявлення об'єктів АТД.

Алгоритм

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

Опануйте професію «Data Scientist»

Зараз під цим словом розуміють будь-які послідовності дій, які можна чітко описати та розділити на прості кроки та які призводять до досягнення якоїсь мети. Наприклад, піти на кухню, налити воду та покласти в неї пакетик чаю – це алгоритм для виконання завдання «Заварити чай».

Пройдіть тест, щоб визначитися з професією в IT та отримати подарунки

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

Хто користується алгоритмами

Загалом — абсолютно всі живі та деякі неживі істоти, бо будь-яку послідовність дій, що веде до мети, можна вважати алгоритмом. Пошук їжі тваринам - алгоритм, рухи робота теж описуються алгоритмом.

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

Для чого потрібні алгоритми

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

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

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

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

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

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

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

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

Основні властивості алгоритмів

Дискретність. Алгоритм — не єдина неподільна структура, він складається з окремих дрібних кроків, або дій. Ці дії йдуть у порядку, одне починається після завершення іншого.

Результативність. Виконання алгоритму має призвести до будь-якого результату та не залишати невизначеності. Результат може навіть виявитися невдалим — наприклад, алгоритм може повідомити, що рішення немає, — але він має бути.

Детермінованість. На кожному кроці не повинно виникати різночитань та розбіжностей, інструкції мають бути чітко визначені.

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

Зрозумілість. Алгоритм повинен включати лише дії, відомі та зрозумілі виконавцю.

Кінцівка. Алгоритми кінцеві, вони мають завершуватись і видавати результат, у деяких визначеннях — за наперед відоме число кроків.

Якими бувають алгоритми

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

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

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

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

Рекурсивний. Рекурсія - це явище, коли якийсь алгоритм викликає сам себе, але з іншими вхідними даними. Це не цикл: ці інші, але «примірників» працюючих програм кілька, а не одна. Відомий приклад рекурсивного алгоритму – розрахунок чисел Фібоначчі.

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

Імовірнісні. Такі алгоритми згадуються рідше, але це досить цікавий тип: робота алгоритму залежить тільки від вхідних даних, а й від випадкових величин. До них, наприклад, належать відомі алгоритми Лас-Вегас та Монте-Карло.

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

Стати дата-саентистом і вирішувати амбітні завдання за допомогою нейромереж

Графічне зображення алгоритмів

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

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

Складність алгоритму

Поняття «складність» — один із ключових у вивченні алгоритмів. Воно означає не те, наскільки важко зрозуміти той чи інший метод, а ресурси, витрачені на обчислення. Якщо складність висока, алгоритм виконуватиметься повільніше і, можливо, витрачатиме більше апаратних ресурсів; такого бажано уникати.

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

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

• O(1) означає, що алгоритм виконується за фіксований константний час. Це найефективніші алгоритми.
• O(n) – це складність лінійних алгоритмів. n тут і далі означає розмір вхідних даних: чим більше nтим довше виконується алгоритм.
• O(n²) теж означає, що чим більше n, Тим вище складність. Але залежність тут не лінійна, а квадратична, тобто швидкість зростає набагато швидше. Це неефективні алгоритми, наприклад, із вкладеними циклами.
• O(log n) - ефективніший алгоритм. Швидкість виконання розраховується логарифмічно, тобто залежить від логарифму n.
• O(√n) — алгоритм, швидкість якого залежить від квадратного кореня з n. Він менш ефективний, ніж логарифмічний, але ефективніший за лінійний.

Існують також O(n³), O(nn) та інші малоефективні алгоритми з високими ступенями. Їхня складність зростає дуже швидко, і їх краще не використовувати.

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

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

Використання алгоритмів у IT

Ми наведемо кілька прикладів використання різних алгоритмів у галузях програмування. Насправді їх набагато більше – ми взяли лише частину, щоб допомогти вам зрозуміти практичну значущість алгоритмів.

Розробка ПЗ та сайтів. Алгоритми використовуються для парсингу, тобто «розбору» структур даних, таких як JSON. Парсинг - одне з базових завдань, наприклад у Інтернеті. Також алгоритми потрібні при малюванні динамічних структур, виведенні оповіщень, налаштуванні поведінки програми та багато іншого.

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

Окреме значення алгоритми мають у Big Data та аналіз даних: там вони дозволяють обробити величезну кількість інформації, у тому числі сирої, і не витратити на це занадто багато ресурсів.

Пошукові задачі. Алгоритми пошуку – окрема складна галузь. Їх виділяють в окрему групу, де зараз десятки різних алгоритмів. Пошук важливий у науці про даних, у методах штучного інтелекту, в аналітиці та багато іншого. Найочевидніший приклад — пошукові системи на кшталт Google чи Яндекса. До речі, подробиці про алгоритми пошуковики зазвичай тримають у секреті.

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

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

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

Отримайте у подарунок кар'єрну консультацію, міні-курс та доступ до чат-боту, щоб почати змінювати життя прямо зараз!

Алгоритми: структуровані програми

Початковою метою теорії алгоритмів є класифікація всіх завдань на алгоритмічно розв'язні та нерозв'язні, тобто. ті, котрим існують вирішальні їх алгоритми , і ті, котрим таких алгоритмів немає. Неформально під алгоритмом можна розуміти виражений деякою мовою набір правил (припис, рецепт, спосіб), що дозволяє застосувати до вихідних (вхідних) даних x з деякої множини допустимих даних X послідовність дискретних дій (операцій, команд), що призводить до певного результату - вихідним даним з деякої множини Y . І тут кажуть, що алгоритм обчислює функцію типу X -> Y . Це несуворе визначення цілком підходить у тих випадках, коли для деякої функції нам пред'являється "об'єкт", званий алгоритмом її обчислення (наприклад, алгоритм Евкліда для обчислення найбільшого загального дільника двох цілих чисел), і можна легко перевірити, чи дозволяє він дійсно обчислити необхідну функцію . Однак воно зовсім не годиться для доказу того, що для заданої функції немає алгоритму.

Починаючи з тридцятих років ХХ століття, було здійснено низку досліджень для формалізації поняття алгоритму. Перерахуємо деякі із запропонованих різними авторами у різний час формальних моделей: машини Тьюринга-Поста, частково-рекурсивні функції (Гедель, Кліні), -числення (Черч, Кліні), ітеративні автомати Неймана, нормальні алгоритми Маркова, лічильникові автомати Мінського, автомати на графах Колмогорова-Барздиня та інших. Закладені у яких ідеї значною мірою вплинули потім архітектуру і мови програмування реальних комп'ютерів (наприклад, з урахуванням -числения побудований широко застосовуваний у завданнях штучного інтелекту мову ЛИСП , та якщо з нормальних алгоритмів Маркова стався добре підходящий для текстової обробки мова РЕФАЛ). Кожна з численних мов програмування також задає певну формальну модель алгоритмів. Ми спочатку розглянемо одну з найпростіших таких мов – прості структуровані програми. А потім порівняємо їх з двома іншими моделями алгоритмів: описами частково рекурсивних функцій та машинами Тьюринга.

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

Нагадаємо, що з N позначається безліч натуральних чисел, тобто. N = . Для часткової n – місцевої арифметичної функції f: N n -> N через позначимо область її визначення. Щоб вказати, що f не визначено на певному наборі чисел a₁. a_n писатимемо , а якщо f на цьому наборі визначено, то писатимемо . Отже, .

Структуровані програми

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

Визначимо спочатку синтаксис структурованих програм. Зафіксуємо для цього деяку лічильну кількість імен змінних Var, які будуть використовуватися в програмах. Як завжди, вважатимемо, що воно включає імена x, x₁,x₂. , y, y₁. z,z₁. . і т.п. У наступних визначеннях x, y, z - це довільні змінні Var .

Визначення 7.1. Оператор присвоєння. Привласнення - це вираз одного з наступних трьох видів:

Визначення 7.2. Умови. Умова - це вираз одного з двох видів:

Структуровані програми визначаються індуктивно.

Визначення 7.3. Структуровані програми.

• Кожне присвоєння - це структурована програма.
• Якщо і структуровані програми, то і це структурована програма.
• Якщо і - структуровані програми, а - це умова, то

Конструкція у п. (б) називається послідовним застосуванням або композицією програм і , конструкція п. (в) називається умовним оператором ; конструкція у п.(г) - це оператор циклу, - умова циклу, а - тіло циклу.

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

Визначення 7.4. Стан - це відображення з безлічі змінних Var до множини N . Для позначимо значення змінної x в стані Через S позначимо безліч всіх станів.

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

Визначення 7.5. Операційна семантика програми - це відображення (власне кажучи, часткове) типу S -> S, яке програма індукує на безлічі всіх станів. Через позначимо стан-результат застосування програми до стану. Воно визначається індукцією щодо побудови програми.

• , де за , і .
• , де за , і .
• , де при , і
• Нехай. Тоді при цьому, якщо або і , то і .
• Нехай якщо x = y тоінакшекінець. Тоді

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