ЛЕКЦІЯ № 1 (алгоритми та методи обчислень)

ЛЕКЦІЯ № 1 (алгоритми та методи обчислень)

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

– опис послідовності дій для розв’язання задачі або досягнення поставленої мети;

– правила виконання основних операцій обробки даних;

– опис обчислень за математичними формулами.

Термін "алгоритм" походить від "algorithmi" – латинської форми написання імені великого математика аль-Хорезмі, який сформулював правила виконання арифметичних дій. Тому спочатку під алгоритмом розуміли тільки правила виконання чотирьох арифметичних дій над багатоцифровими числами в десятковій системі числення. Зараз він є одним із фундаментальних понять інформатики.

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

Прикладом алгоритму може служити алгоритм "Переправа". На лівому березі річки знаходяться дві молодих людини зі своїми дівчатами (рис.1). Всім потрібно перебратися на правий берег, але в човні тільки два місця. Кожна дівчина не хоче залишатися на березі без свого молодого чоловіка, якщо на цьому ж березі знаходиться інша молода людина. Як всім переплисти на інший берег?

Рішення: Позначимо дівчат і молодих людей Д1, Д2, М1, М2, переїзд на правий берег →, переїзд на лівий берег ←. Можна записати алгоритм:

У 30-х роках минулого століття зародилася і бурхливо розвивається наука, яка називається теорією алгоритмів.

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

На основі формалізації поняття алгоритму можливі наступні дії:

– порівняння алгоритмів за їх ефективністю;

Початковою точкою відліку сучасної теорії алгоритмів вважають роботу німецького математика Курта Геделя (1931 рік – теорема про неповноту символічних логік). Перші фундаментальні роботи з теорії алгоритмів були опубліковані незалежно в 1936 році роки Аланом Тьюрингом, Алоізом Черчем і Емілем Постом. Запропоновані ними машина Тьюринга, машина Посту і лямбдачислення Черча були еквівалентними формалізмами алгоритму. Важливим розвитком цих робіт стало формулювання і доказ алгоритмічно нерозв'язних проблем. У 50-ті роки минулого століття істотний внесок у теорію алгоритмів внесли роботи Колмогорова і Маркова.

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

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

1. Кожен алгоритм має справу з даними – вхідними, проміжними, вихідними. Для того, щоб уточнити поняття даних, фіксується алфавіт вихідних символів (цифри, букви і т.п.) і вказуються правила побудови алгоритмічних об'єктів. Типовим використовуваним засобом є індуктивна побудова. Наприклад, визначення ідентифікатора в Паскалі, Сі: ідентифікатор – це або буква, або ідентифікатор, до якого приписана праворуч або буква, або цифра. Інший випадок алгоритмічних об'єктів – формули.

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

3. Алгоритм складається з окремих елементарних кроків, причому множина різних кроків, з яких складений алгоритм, скінченні. Типовий приклад множини елементарних кроків – система команд процесора.

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

5. Алгоритм повинен бути результативним, тобто зупинятися після скінченного числа кроків (залежного від вхідних даних) з видачею результату. Дана властивість іноді називають збіжністю алгоритму.

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

Вимога 1 відповідає цифровій природі ПК, вимога 2 – пам'ять ПК, вимога 3 – програмі машини, вимога 4 – її логічній природі, вимоги 5, 6 – обчислювальному пристрою та його можливостям.

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

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

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

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

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

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

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

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

Скінченність – кожна окрема дія, як і весь алгоритм повинні мати можливість реального виконання. Тому алгоритм має межу, тобто скінченність.

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

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

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

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

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

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

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

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

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

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

У табл. 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 закінчуючи одержанням некоректних результатів.

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

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

Складання. Є два наближення

до двох величин х і у, а також відповідні абсолютні похибки е_х і е_у. Тоді в результаті складання маємо

Похибка суми, яку позначимо через е_х _{+ у}, буде дорівнювати

Оскільки помилки зазвичай набагато менше самих величин, то добутком помилок можна знехтувати. Будемо мати:

Множник, що стоїть в дужках, при

можна розкласти в ряд

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

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

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

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

з відповідними похибками

. Ці похибки можуть бути будь-якого походження. Величини

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

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

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

ЛЕКЦІЯ № 1 (алгоритми та методи обчислень)

– опис послідовності дій для розв’язання задачі або досягнення поставленої мети;

– правила виконання основних операцій обробки даних;

– опис обчислень за математичними формулами.

У 30-х роках минулого століття зародилася і бурхливо розвивається наука, яка називається теорією алгоритмів.

На основі формалізації поняття алгоритму можливі наступні дії:

– порівняння алгоритмів за їх ефективністю;

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

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот...

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

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