Поняття алгоритму властивості, способи опису
Назва роботи: Поняття алгоритму: властивості, способи опису
Предметна область: Інформатика, кібернетика та програмування
Опис: Мова програмування призначений для реалізації програм на ЕОМ. Для розробки програм використовуються системи програмування. Система програмування засіб автоматизації програмування включає мову програмування транслятор цієї мови документацію а також кошти підготовки та виконання програм. Основними образотворчими засобами алгоритмів є такі способи їх запису: словесний; формульно-словесний; блоксхемний; псевдокод; структурні діаграми; мови програмування.
Розмір файлу: 242.5 KB
Роботу скачали: 19 чол.
екция: Поняття алгоритму: властивості, способи опису Сторінка 6 з 6
[2] Алгоритмизация обчислювальних процесів
[2.1] Основні визначення і поняття
[2.2] Засоби зображення алгоритмів
[2.3] Базові канонічні структури алгоритмів
[2.4] Контрольні питання.
Тема: Поняття алгоритму: властивості, способи опису.
Мета. формування поняття «алгоритм», дати опис властивостями алгоритму, визначити способи опису.
Основні визначення і поняття
Алгоритмізація - це процес побудови алгоритму розв'язання задачі, результатом якого є виділення етапів процесу обра? Лення даних, формальна запис змісту цих етапів і визначенні? Ня порядку їх виконання.
Алгоритм - це точне розпорядження, що визначає обчислювальні? Вальний процес, що веде від варійованих початкових даних до іско? Мому результату.
- детермінованість - точність вказівок, що виключає їх довільне тлумачення;
- дискретність - можливість розчленування обчислювального про? процесу на окремі елементарні операції, можливість виконання яких не викликає сумнівів;
- результативність - припинення процесу через кілька етапів з видачею шуканих результатів або повідомлення про неможливість? ності продовження обчислювального процесу;
- масовість - придатність алгоритму для вирішення всіх завдань за? даного класу.
Алгоритмічна мова - набір символів і правил освіти і тлумачення конструкцій з цих символів для запису алгоритмів.
Мова програмування - призначений для реалізації програм на ЕОМ.
Програма - це алгоритм, записаний у формі, яка сприймається машиною. Програма містить поряд з описом даних команди, в якій послідовності, над якими даними і які операції долж? На виконувати машина, а також в якій формі слід отримати резуль? Тат. Це забезпечують різні оператори.
Дані - це факти і ідеї, представлені в формалізованому вигляді, що дозволяє передавати або обробляти ці факти і ідеї з по? Міццю деякого процесу.
Оператор - сукупність символів, що вказують операцію і значення, або місцезнаходження її елементів.
Змінна - це об'єкт, який в ході виконання програми може змінювати своє значення.
1) змінна називається невизначеною до тих пір, поки вона не отримає значення:
б) занесенням константи;
в) занесенням значення інший, раніше певної змінної;
- в кожен момент часу змінна може або мати визна? поділене значення, або бути невизначеною;
- наступне значення знищує (пере) попереднє зна? ня. Вибір (читання) змінної і її використання не змінюють зна? Ня змінної.
Для розробки про? Грам використовуються системи програмування.
Система програмування - засіб автоматизації програм? Мування, що включає мову програмування, транслятор цього язи? Ка, документацію, а також кошти підготовки та виконання програм.
Транслятор - це програма, яка перекладає з однієї мови на іншу.
Інтерпретатор - це програма, яка одночасно виконує пере? Водиться команди.
Компілятор - це програма, яка переводить конструкції ал? Горітміческого мови в машинні коди.
Засоби зображення алгоритмів
Алгоритм - це точне розпорядження, що визначає обчислювальні? Вальний процес, що веде від змінюваних початкових даних до вирішення поставленого завдання.
Основними образотворчими засобами алгоритмів є такі способи їх запису:
- словесний;
- формульно-словесний;
- блок-схемний;
- псевдокод;
- структурні діаграми;
- мови програмування.
Розглянемо приклад блок-схеми тієї ж завдання, для якої приве? Ден словесний алгоритм.
Розглянемо приклад словесної записи алгоритму. Нехай заданий масив чисел. Потрібно перевірити, чи всі числа належать заданому
інтервалу. Інтервал задається межами А і В.
п.1 Беремо перше число. На п.2.
п.2 Порівнюємо: вибране число належить інтервалу;
якщо так, то на п.3. якщо ні # 150; на п.6.
п.4 Вибираємо наступний елемент. На п.2.
п.5 Друк повідомлення: всі елементи належать інтервалу. На п.7.
п.6 Друк повідомлення: не всі елементи належать інтервалу. На п.7.
При цьому способі відсутня наочність обчислювального процесу, тому що немає достатньої формалізації.
Формульно-словесний # 150; завдання інструкцій з використанням математичних символів і виразів в поєднанні зі словесними поясненнями.
Наприклад, потрібно написати алгоритм обчислення площі трикутника за трьома сторонами.
п.1 # 150; обчислити напівпериметр трикутника
п.2 # 150; обчислити
п.3 # 150; вивести S. як шуканий результат і припинити обчислення.
При використанні цього способу може бути досягнута будь-який ступінь деталізації, більш наочно, але не строго формально.
Блок-схемний # 150; це графічне зображення логічної структури алгоритму, в якому кожен етап процесу переробки даних представляється у вигляді геометричних фігур (блоків), що мають певну конфігурацію в залежності від характеру виконуваних операцій.
Таке уявлення алгоритму досить зручно і наочно показує послідовність виконання операторів програми.
Використовуючи дані позначення можна скласти блок-схеми основних операторів програмування на алгоритмічній мові Паскаль.
Відповідно до використовуваними в програмі операторами розрізняють наступні типи алгоритмів. лінійний. розгалужених, циклічний, комбінований.
Наведемо приклад блок-схеми комбінованого алгоритму для розрахунку суми позитивних S1 і негативних S2 чисел з N випадкових чисел від -100 до 100.
Відповідні алгоритму оператори мають вигляд:
Writeln ( 'Введіть кількість випадкових чисел');
x: = Random (201) -100;
if x <0 Then S2:=S2+x else S1:=S1+x;
Малюнок 1 Блок-схема алгоритму
Псевдокод - дозволяє формально зображати логіку програми, не піклуючись при цьому про синтаксичних особливостях конкретного мови програмування. Зазвичай являє собою суміш операторів мови програмування і природної мови. Є засобом представлення логіки програми, яке можна застосовувати замість блок-схеми.
Запис алгоритму у вигляді псевдокоду:
Вибираємо перший елемент (i = 1) IF A> X t або х.> B THEN
друк повідомлення і перехід на кінець ELSE
перехід до наступного елементу (i = i + 1)
IF масив не скінчилася (i <= n ) THEN переход на проверку интервала
друк повідомлення, що всі елементи входять в інтервал
Структурні діаграми - можуть використовуватися в якості структурних блок-схем, для показу міжмодульних зв'язків, для відображення структур даних, програм і систем обробки даних. Існують різні структурні діаграми: діаграми Насс-Шнейдермана, діаграми Варньє, Джексона, МЕСІД і ін.
Основні елементи МЕСІД
Розглянемо приклад використання діаграм МЕСІД.
Задано одновимірний масив з позитивних і негативних чисел. Потрібно визначити частка від ділення суми позитивних елементів на суму негативних елементів цього масиву. Праворуч від діаграми наводяться відповідні оператори мови Паскаль.
Щоб комп'ютер виконав рішення будь-якої задачі, йому необхідно отримати від людини інструкції, як її вирішувати. Набір таких інструкцій для комп'ютера, спрямований на вирішення конкретного завдання, називається комп'ютерною програмою.
Сучасні комп'ютери не настільки досконалі, щоб розуміти програми, записані на будь-якому уживаній людиною мовою # 151; російською, англійською, японською. Команди, призначені для ЕОМ, необхідно записувати в зрозумілій їй формі. З цією метою застосовуються мови програмування - штучні мови, алфавіт, словниковий запас і структура яких зручні людині і зрозумілі комп'ютера.
У найзагальнішому сенсі мовою програмування називається фіксована система позначень і правил для опису алгоритмів і структур даних. Всі мови програмування поділяються на мови низького, високого та надвисокого рівня.
Мова програмування низького рівня - це засіб запису інструкцій комп'ютера простими командами на апаратному рівні. Така мова відображає структуру даного класу ЕОМ і тому іноді називається машинно-орієнтованою мовою. Користуючись системою команд, зрозумілою комп'ютера, можна описати алгоритм будь-якої складності. Запис програми на цій мові являє собою послідовність нулів і одиниць.
Більш численну групу складають мови програмування високого рівня. кошти яких допускають опис завдання в наочному, легко воспри? Німа вигляді. Відмінною особливістю цих мов є їх орієнтація не на систему команд тієї чи іншої ЕОМ, а на систему операторів, характерних для запису певного класу алгоритмів. До мов програмування цього типу відносяться: Бейсік, Фортран, Алгол, Паскаль, Сі. Програма на мовах висок? Кого рівня записується системою позначень, близькій людині (наприклад, фіксованим набором слів англійської мови, що мають строго певне призначення). Програму на мові високого рівня простіше зрозуміти і значно легше налагодити.
До мов програмування надвисокого рівня можна віднести Алгол, при розробці якого зроблена спроба формалізувати опис мови, привед? Шая до появи абстрактної і конкретної програм. Абстрактна програма створюється програмістом, конкретна - виводиться з першого. Передбачається, що при такому підході принципово неможливо породити зрадливу синтакси? Тично (а в ідеалі і семантично) конкретну програму. Мова APL відносять до мов надвисокого рівня за рахунок введення надпотужних операцій і операто? Рів. Запис програм такою мовою виходить компактною.
Всі перераховані вище мови - обчислювальні. Молодші - декларативні (непроцедурного) мови, відмінна риса яких - завдання зв'язків і відносин між об'єктами і величинами і відсутність визначення послідовно? Ності виконання дій (Пролог). Такі мови зіграли важливу роль в програмуванні, так як вони дали поштовх до розробки спеціалізованих мов штучного інтелекту і мов представлення знань.
Базові канонічні структури алгоритмів
Доведено, що будь-яку програму можна написати, використовуючи комбінації трьох керуючих структур.
- слідування або послідовності операторів;
- розвилки або умовного оператора;
- повторення або оператора циклу.
Дії А і В можуть бути:
- викликом з поверненням деякої процедури;
- інший керуючої структурою.
IF P then A else B;
Перевірка P представляється предикатом, тобто функцією, яка задає логічне вираз або умову, значенням якого може бути істина або брехня. Ця структура може бути неповною, коли відсутня дія, що виконується при помилковому значенні логічного виразу. Тоді структура буде наступна:
Дія А буде повторюватися до тих пір, поки значення предиката буде залишатися істинним. Тому в дії А повинно змінюватися значення змінних, від яких залежить Р. В іншому випадку відбудеться зациклення. Обчислення предиката проводиться до початку виконання дії А і може статися так, що дія А не виконуватиметься жодного разу.
Repeat A until P;
Повторення типу Repeat until завжди виконується хоча б 1 раз. Дія А перестає виконуватися, як тільки предикат стає справжнім.
4) вибір # 150; перемикач case (узагальнення розвилки), структура, яка полегшує програмування без шкоди для ясності програми. Структура вибір корисна в тому випадку, коли потрібно вибрати одну з декількох альтернатив.
Залежно від значення Р виконується одна з дій А, В, ... Z. Після чого відбувається перехід до виконання наступного керуючої структури.
Контрольні питання.
- Дайте визначення алгоритму. Опишіть властивості алгоритму.
- Перерахуйте способи записів алгоритмів.
- Чим відрізняється компілятор від інтерпретатора?
- Що таке підпрограма?
- Перерахуйте способи відображення алгоритмів.
- Особливості словесного способу зображення алгоритмів.
- Особливості формульно-словесного способу зображення алгоритмів.
- Особливості зображення алгоритмів за допомогою операторних схем (псевдокоду).
- Особливості зображення алгоритмів за допомогою структурних діаграм.
- Особливості блок-схемного способу зображення алгоритмів.
- Основні символи, які використовуються при складанні блок-схем.
- Дайте поняття регулярної програми.
- Особливості використання базових конструкцій «проходження» і «повторення».
- Особливості використання базових конструкцій «розвилка» і «вибір».