|
Основні типи алгоритмічних моделейРозглянемо основні типи алгоритмічних моделей, що розрізняються трактуваннями поняття алгоритм. Перший тип трактує алгоритм як деякій детермінований пристрій, здатний виконувати в кожен момент лише строго фіксовану множину операцій. Основною теоретичною моделлю такого типу є машина Тьюринга, запропонована ним у 30-х роках минулого століття, яка зробила суттєвий вплив на розуміння логічної природи розроблюваних ЕОМ. Іншою теоретичною моделлю даного типу є машина довільного доступу – введена досить недавно (у 70-х роках) з метою моделювання реальних обчислювальних машин та отримання оцінок складності обчислень. Другий тип пов'язує поняття алгоритму з традиційним уявленням – процедурами обчислення значень числових функцій. Основною теоретичною моделлю цього типу є рекурсивні функції – історично перша формалізація поняття алгоритму. Третій тип алгоритмічних моделей – це перетворення слів у довільних алфавітах, в яких операціями є заміни фрагментів слів іншим словом. Основною теоретичною моделлю цього типу є нормальні алгоритми Маркова. Теорія алгоритмів має істотний вплив на розвиток ЕОМ і практику програмування. В теорії алгоритмів передбачені основні концепції, які закладені в апаратуру і мови програмування ЕОМ. Згадувані вище основні алгоритмічні моделі математично еквівалентні. Але на практиці вони істотно розрізняються ефектами складності, що виникають при реалізації алгоритмів, і породили різні напрямки в програмуванні. Так, мікропрограмування будується на ідеях машин Тьюринга, структурне програмування запозичило свої конструкції з теорії рекурсивних функцій, мови символьної обробки інформації (РЕФАЛ, ПРОЛОГ) беруть початок від нормальних алгоритмів Маркова та систем Посту. На основі теорії алгоритмів в даний час отримані практичні рекомендації, що набувають все більшого поширення в області проектування і розробки програмних систем. Результати теорії алгоритмів набувають особливого значення для криптографії. Форми подання алгоритмів На практиці найбільш поширеним є такі форми подання алгоритмів: – словесна (записи природною мовою); – графічна (зображення з графічних символів); – псевдокод (напівформалізований опис алгоритмів умовною алгоритмічною мовою, який включає в себе як елементи мови програмування, так і фрази природної мови, загальноприйняті математичні позначення та ін.); – програмна (тексти мовою програмування). Словесний спосіб запису алгоритмів – це опис послідовних етапів обробки даних. Алгоритм задається у довільному викладі природною мовою. Словесний спосіб не набув поширення з наступних причин: – такі описи строго не формалізуються; – страждають багатослівністю записів; – допускають неоднозначність тлумачення окремих записів. Графічний спосіб подання алгоритмів є більш компактним і наочним порівняно зі словесним. При графічному поданні алгоритм зображується у вигляді послідовності пов'язаних між собою функціональних блоків, кожен з яких відповідає виконанню однієї або кількох дій. Таке графічне подання називається схемою алгоритму або блок-схемою. У блок-схемі кожному типу дій (введення вихідних даних, обчислення значень виразів, перевірка умов, керування повторенням дій, закінчення обробки і т. п.) відповідає геометрична фігура, яка має певний вигляд блочного символу. Блокові символи з'єднуються лініями переходів, які визначають черговість виконання дій. Блоки необхідно розміщувати зверху вниз або зліва направо в порядку їх виконання. У табл. 1 наведені найбільш часто вживані блоки, конфігурація яких відповідає ГОСТ 19.701–90 "Единая система программной документации. Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения". Таблиця 1
Побудова блок-схеми виконується з урахуванням наступних рекомендацій: 1. Блок-схема будується зверху вниз. 2. У будь-який блок-схемі є один елемент, відповідний початку, і один елемент, відповідний кінця. 3. Повинен бути хоча б один шлях з початку блок-схеми до будь-якого елементу. 4. Повинен бути хоча б один шлях від кожного елемента блок-схеми в кінець блок-схеми. Псевдокод є системою позначень і правил, призначених для однакового запису алгоритмів. Він займає проміжне місце між природною і формальною мовами. З одного боку, він близький до звичайної природної мови, тому алгоритми можуть на ньому записуватися і читатися як звичайний текст. З іншого боку, в псевдокоді використовуються деякі формальні конструкції і математична символіка, що наближає запис алгоритму до загальноприйнятого математичного запису. У псевдокоді не прийняті строгі синтаксичні правила для запису команд, властиві формальним мовам, що полегшує запис алгоритму на стадії його проектування і дає можливість використовувати більш широкий набір команд, розрахований на абстрактного виконавця. Однак у псевдокоді зазвичай є деякі конструкції, властиві формальним мовам, що полегшує перехід від запису на псевдокоді до запису алгоритму формальною мовою. Зокрема, в псевдокоді, так само, як і в формальних мовах, є службові слова, зміст яких визначено раз і назавжди. Єдиного або формального визначення псевдокоду не існує, тому можливі різні псевдокоди, що відрізняються набором службових слів і основних (базових) конструкцій. Базові структури алгоритму Базові структури алгоритму – це структури, за допомогою яких створюється алгоритм для розв’язання певної задачі. Існують три основні (базові) алгоритмічні структури, або три основні типи алгоритмів: лінійний, розгалужувальний та циклічний. Лінійний алгоритм – це алгоритм, в якому дії виконуються тільки один раз і строго в тому порядку, в якому вони записані. Елементарним прикладом лінійного алгоритму може бути визначення площі фігури. Приклад. Скласти алгоритм розрахунку площі трапеції з основами a і b та висотою h. Рішення. Відомо, що площа трапеції розраховується за формулою . Тому можна записати наступний алгоритм її визначення: 1. Задати числові значення a, b, h. 2. Розрахувати вираз . 3. Записати відповідь S. Блок-схема цього лінійного алгоритму показана на рис. 2. Розгалужувальний алгоритм – це алгоритм, в якому та чи інша дія виконується після аналізу умови. Процес аналізу умови і вибору однієї з гілок на блок-схемі показують за допомогою логічного блоку. Приклад розгалужується структури показаний на рис. 3. Процес аналізу умови і вибору однієї з гілок на блок-схемі показують за допомогою логічного блоку. Логічний блок має один вхід і два виходи (гілка "так" і гілка "ні"). У блок-схемах розгалужувальних алгоритмів завжди є логічний блок. Циклічний алгоритм (цикл) – це алгоритм, в якому група операторів виконується кілька разів поспіль. Блок-схема циклу обов'язково містить логічний блок, її структура показана на рис 4. Виконується циклічний алгоритм так: спочатку перевіряється умова, якщо умова вірна (істина), то виконується тіло циклу (дії або група операторів) і, далі, змінюються значення параметра циклу і знову перевіряється умова і т. д. На якомусь етапі умова не виконається (хибність) і тоді відбувається вихід з циклу і продовжується виконання програми. 1.6. Комп’ютерна реалізація алгоритму Для комп'ютерної реалізації алгоритму важлива наявність певного програмного забезпечення, яке може бути як досить універсальним, так і спеціалізованим, призначеним лише для певного виду розрахункових робіт. Зокрема, комп'ютерна реалізація алгоритму може бути здійснена: • за допомогою табличного процесора (як правило, MS Excel); • шляхом створення програм традиційними мовами програмування (Fortran, Pascal, Basic, Сі та ін.), а також на їх сучасних версіях (Delphi, Visual Basic for Application тощо); • за допомогою спеціальних пакетів прикладних програм для вирішення математичних задач (Matlab, MathCAD, Maple і т. п.). Але треба чітко розуміти, що комп'ютер є хорошим інструментом для створення і дослідження алгоритмів розрахунків, але він їх не придумує. Абстрактний аналіз навколишнього світу з метою відтворення його в алгоритмі виконує людина. На етапі програмної реалізації математичної моделі незалежно від вибору мови програмування важливим є вибір придатного числового методу для розв’язання рівнянь, що описують об’єкт, який досліджується. Некоректний вибір числового методу може стати джерелом багатьох проблем, починаючи від неефективності розрахунків i закінчуючи одержанням некоректних результатів. Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)... Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем... Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот... Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|