Основні типи алгоритмічних моделей

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

Перший тип трактує алгоритм як деякій детермінований пристрій, здатний виконувати в кожен момент лише строго фіксовану множину операцій. Основною теоретичною моделлю такого типу є машина Тьюринга, запропонована ним у 30-х роках минулого століття, яка зробила суттєвий вплив на розуміння логічної природи розроблюваних ЕОМ. Іншою теоретичною моделлю даного типу є машина довільного доступу – введена досить недавно (у 70-х роках) з метою моделювання реальних обчислювальних машин та отримання оцінок складності обчислень.

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

Третій тип алгоритмічних моделей – це перетворення слів у довільних алфавітах, в яких операціями є заміни фрагментів слів іншим словом. Основною теоретичною моделлю цього типу є нормальні алгоритми Маркова.

Теорія алгоритмів має істотний вплив на розвиток ЕОМ і практику програмування. В теорії алгоритмів передбачені основні концепції, які закладені в апаратуру і мови програмування ЕОМ. Згадувані вище основні алгоритмічні моделі математично еквівалентні. Але на практиці вони істотно розрізняються ефектами складності, що виникають при реалізації алгоритмів, і породили різні напрямки в програмуванні. Так, мікропрограмування будується на ідеях машин Тьюринга, структурне програмування запозичило свої конструкції з теорії рекурсивних функцій, мови символьної обробки інформації (РЕФАЛ, ПРОЛОГ) беруть початок від нормальних алгоритмів Маркова та систем Посту. На основі теорії алгоритмів в даний час отримані практичні рекомендації, що набувають все більшого поширення в області проектування і розробки програмних систем. Результати теорії алгоритмів набувають особливого значення для криптографії.

На практиці найбільш поширеним є такі форми подання алгоритмів:

– графічна (зображення з графічних символів);

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

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

Словесний спосіб не набув поширення з наступних причин:

– допускають неоднозначність тлумачення окремих записів.

Графічний спосіб подання алгоритмів є більш компактним і наочним порівняно зі словесним.

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

У табл. 1 наведені найбільш часто вживані блоки, конфігурація яких відповідає ГОСТ 19.701–90 "Единая система программной документации. Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения".

Побудова блок-схеми виконується з урахуванням наступних рекомендацій:

2. У будь-який блок-схемі є один елемент, відповідний початку, і один елемент, відповідний кінця.

3. Повинен бути хоча б один шлях з початку блок-схеми до будь-якого елементу.

4. Повинен бути хоча б один шлях від кожного елемента блок-схеми в кінець блок-схеми.

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

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

Базові структури алгоритму – це структури, за допомогою яких створюється алгоритм для розв’язання певної задачі. Існують три основні (базові) алгоритмічні структури, або три основні типи алгоритмів: лінійний, розгалужувальний та циклічний.

Лінійний алгоритм – це алгоритм, в якому дії виконуються тільки один раз і строго в тому порядку, в якому вони записані.

Елементарним прикладом лінійного алгоритму може бути визначення площі фігури.

Приклад. Скласти алгоритм розрахунку площі трапеції з основами a і b та висотою h.

Рішення. Відомо, що площа трапеції розраховується за формулою

. Тому можна записати наступний алгоритм її визначення:

Блок-схема цього лінійного алгоритму показана на рис. 2.

Розгалужувальний алгоритм – це алгоритм, в якому та чи інша дія виконується після аналізу умови. Процес аналізу умови і вибору однієї з гілок на блок-схемі показують за допомогою логічного блоку. Приклад розгалужується структури показаний на рис. 3. Процес аналізу умови і вибору однієї з гілок на блок-схемі показують за допомогою логічного блоку. Логічний блок має один вхід і два виходи (гілка "так" і гілка "ні"). У блок-схемах розгалужувальних алгоритмів завжди є логічний блок.

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

Зокрема, комп'ютерна реалізація алгоритму може бути здійснена:

• за допомогою табличного процесора (як правило, MS Excel);

• шляхом створення програм традиційними мовами програмування (Fortran, Pascal, Basic, Сі та ін.), а також на їх сучасних версіях (Delphi, Visual Basic for Application тощо);

• за допомогою спеціальних пакетів прикладних програм для вирішення математичних задач (Matlab, MathCAD, Maple і т. п.).

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

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

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: