Презентація на тему:
Алгоритми

Алгоритми

Основні поняття алгоритмізації Поняття алгоритму Слово “алгоритм” походить від Algorithmi (латин.) – імені великого математика аль-Хорезмі, який сформулював правила використання арифметич-них дій над багатоцифровими числами. Алгоритм – це точні розпорядження (вказівки, команди) виконавцеві відносно здійснення послідовності дій, які спрямовані на розв’язання певної задачі. Виконавець алгоритму - це істота (людина, свійська тварина) або неістота (робот, автомат, комп’ютерна система), яка може виконувати всі вказівки заданого алгоритму.

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

Властивості алгоритму Це вимоги, які повинен задовольняти алгоритм. Дискретність. Алгоритм складається із сукупності відокремлених одна від одної команд, кожна з яких виконується за кінцевий час. Тільки закінчивши виконання однієї команди, виконавець переходить до виконання іншої. Однозначність. Кожна команда алгоритму однозначно визначає дії виконавця і не допускає їх подвійного тлумачення. Однозначним є й порядок виконання операцій. Формальність. Будь-який виконавець, що володіє заданою системою команд виконавця, може, не знаючи суті завдання, виконати алгоритм й отримати такий самий результат.

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

Подання алгоритмів Алгоритми подаються за допомогою природних або штучних мов,схем, рисунків, знаків тощо. Способи подання алгоритмів Словесний – подання алгоритмів,які призначені на виконання людиною (наприклад, кулінарних рецептів, правил переходу вулиці тощо), природною мовою в усній або письмовій формі. Формульно-словесний – подання алгоритму у навчальній та науковій діяльності за допомогою мови математичних формул, хімічних процесів тощо зі словесними поясненнями природною мовою.

Графічний – подання алгоритмів у вигляді графічних схем (блок-схем або структурних схем) для спрощення розробки та аналізу алгоритмів, полегшення переходу від запису алгоритмів до написання програм. Програмний – подання алгоритмів мовою програмування для їх подальшого опрацювання на комп’ютері . Інші способи – специфічні способи подання алгоритмів, такі, як запис музики за допомогою нот тощо.

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

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

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

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

Серія 2 Серія 1

Логічні вирази та логічні операції Висловлювання – це деяке мовне ствердження, яке має зміст і відносно якого можна сказати, що воно істинне або хибне. Тобто кожному висловлюванню можна приписати істиннісне (логічне) значення “істинність” (“1” , “true”) або “хибність” (“0”, “false”). Використовуючи частку “ні” (“не”), сполучники “і” (“та”), “або” та інші, можна будувати нові висловлювання. Побудова нового висловлювання з наданих висловлювань називається логічною операцією.

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

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

Серія 1 Повне галуження реалізується таким чином: у разі виконання умови (логічного виразу), виконується серія команд 1, інакше (у разі невиконання умови) – серія команд 2. ЛВ Серія 2 так ні

Повне галуження можна записати за допомогою інструкції: Якщо ЛВ То Серія 1 Інакше Серія 2 Неповне галуження – це галуження , у якому дії визначені тільки у разі виконання (або невиконання) заданої умови. Неповне галуження реалізується таким чином: якщо умова виконується, виконується задана серія команд, інакше (якщо умова не виконується) – не виконується жодна команда. Неповне галуження можна записати за допомогою інструкції: Якщо ЛВ То Серія

Серія 1 Послідовні галуження – це алгоритми, у яких структури галуження слідують одна за одною, тобто лінійно. Вкладені галуження – це алгоритми галуження, у яких серія команд для виконання містить іншу структуру галуження. ЛВ так ні

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

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

ні так ЛВ Серія

Цикл з післяумовою (цикл-“до”) – це цикл, у якому тіло циклу виконується доти, доки умова, що задана після тіла циклу, не виконається. Цикл з післяумовою реалізується таким чином. Спочатку виконується тіло циклу, а потім перевіряється умова. Якщо умова виконується, то цикл завершується. Якщо умова не виконується, то знову виконується тіло циклу, і т.д. Цикл з післяумовою можна записати за допомогою мовної інструкції: Виконуй команди До ЛВ

ЛВ Серія ні так

Цикл з параметром(цикл з покроковою зміною аргументу) – це цикл, у якому тіло циклу виконується відому кількість разів, що реалізовано через покрокову зміну параметра. Цикл з параметром реалізується таким чином. Параметру циклу надається початкове значення, і з ним виконується тіло циклу. Параметр змінюється на заданий крок, і знову виконується тіло циклу, і так, доки параметр не дістане кінцевого значення. Цикл з параметром можна записати за допомогою мовної інструкції: Для ПЦ Від ПЗ До КЗ Кроком К Виконуй команди

Серія ПЦ:=ПЗ, КЗ, К

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