Поняття алгоритму та алгоритмічної мови. Основи теорії програмування.
Поняття алгоритму та алгоритмічної мови. Основи теорії програмування. Виконавець: Остапенко Галина Іванівна
План лекції Поняття алгоритму та алгоритмічної мови. Основні властивості алгоритмів. Способи запису алгоритму. Алгоритмічна мова або мова програмування. Коротка історія та класифікація мов програмування. Основні елементи алгоритмічної мови.
Поняття алгоритму Слово алгоритм походить від algorithmi — латинської форми написання імені великого математика ІХ ст. Аль-Хорезмі, який сформулював правила виконання чотирьох арифметичних дій над багатозначними числами. Алгоритм — це вказівка виконавцеві здійснити послідовність дій, спрямованих на досягнення певної мети або розв'язування поставленої задачі.
Поняття алгоритму Алгоритм — чітко задана послідовність кроків, які мають бути виконані для розв'язання завдання Приклад алгоритму. Задача. Вказати послідовність дій, які необхідно виконати для обчислення виразу (ах+b)х+с при заданих значеннях а, b, с, х. Алгоритм можна описати таким чином: 1. Помножити a на х 2. До отриманого результату додати b. 3. Отриманий результат помножити на х 4. До отриманого результату додати с.
Існує багато визначень поняття «алгоритм». Алгоритм — це зрозумілий, точний та повний опис послідовності простих дій для розв'язування конкретної задачі. Алгоритм знаходження найбільшого спільного дільника (НСД) двох натуральних чисел вперше описав Евклід: 1. Порівняй числа а і b. 2. Якщо а =b , то а найбільший спільний дільник. 3. Якщо а >b , то замінити а на a – b. 4. Якщо а
Властивості алгоритмів: 1. Скінченність. Виконання кожного алгоритму повинно завершуватись за скінчене число «кроків». 2. Результативність. Виконання алгоритму завжди повинно приводити до певного результату (можливо і негативного). Воно не може закінчуватися невизначеною ситуацією або ж не закінчуватись взагалі. 3. Формальність. Виконавець відповідно до алгоритму повинен одержати результат, не вникаючи в його суть. Ця властивість має особливе значення для автоматизації виконання алгоритмів. Очевидно, що комп'ютери не можуть розуміти суті завдань і окремих вказівок алгоритмів. 4. Визначеність. Будь-який алгоритм повинен бути описаний так, щоб при його розшифруванні у виконавця не виникало двозначних вказівок. Тобто різні виконавці згідно з алгоритмом повинні діяти однаково та прийти до одного й того ж результату. 5. Масовість. За допомогою складеного алгоритму повинен розв'язуватись цілий клас задач. 6. Зрозумілість. В алгоритмі повинні бути лише операції, знайомі виконавцеві.
Форми подання алгоритмів: 1. словесні; 2. словесно-формульні; 3. графічні; 4. скінчений набір кодів. При складанні алгоритмів можна поєднувати різні форми подання алгоритмів. За типом розрізняють лінійні, розгалужені, циклічні й змішані алгоритми. Лінійний алгоритм — це найпростіший тип алгоритму, що містить одну серію простих команд, які виконуються послідовно. Розгалужений алгоритм — це такий алгоритм, що, крім простих команд, містить умову, залежно від якої виконуються або не виконуються команди, що входять до складеної команди. Циклічний алгоритм — це алгоритм, що містить команди, які забезпечують багаторазове повторення виконання команди або групи команд. На практиці ми найчастіше маємо справу зі змішаними алгоритмами, у яких використовують різні типи команд.
Види алгоритмів Будь-який алгоритм подається у вигляді лінійної послідовності базових алгоритмічних структур. Лінійний алгоритм — алгоритм, в якому використовується тільки структура "слідування". Алгоритмом з розгалуженням — алгоритм, в основі якого лежить структура "розгалуження". Циклічний алгоритм — алгоритм, в основі якого лежить структура "повторення" .
Виконавці алгоритмів Алгоритми складають для певного виконавця. Виконавцем може бути людина або машина. Алгоритми створені для людей — це інструкції, приписи. Алгоритми, створені для машин, називають програмами. Під машиною ми розуміємо технічний пристрій — автомат, комп’ютер, робот. Отже, виконавцями алгоритмів є людина або машина.
2 Алгоритм може бути зорієнтований на виконання його людиною або автоматичним пристроєм. Алгоритми, призначені для виконання комп'ютерами, називають комп'ютерними програмами, або просто програмами. Комп'ютерна програма — це план майбутніх робіт, складений із розрахунку на його виконання комп'ютером. Для того, щоб комп'ютер зміг виконати програму, вона повинна бути записана у спеціальній формі, доступній комп'ютеру і записана відповідно до спеціального набору правил.
Алгоритмічна мова Набір правил запису комп'ютерної програми називається «алгоритмічною мовою». Перша мова програмування створена Адою Августою Лавлейс.
Навчальна алгоритмічна мова Спілкування між споживачами інформації здійснюється за допомогою деякої мови. Мова — це сукупність засобів для фіксації повідомлень і передавання їх від джерела інформації до споживача. Алгоритмічні мови — мови, призначені для фіксації алгоритмів у вигляді деяких повідомлень і передавання таких повідомлень споживачеві інформації (виконавцеві алгоритму). Алфавіт алгоритмічної мови — сукупність символів, які дозволяються використовувати при описанні алгоритмів на тій чи Іншій алгоритмічній мові. Синтаксис алгоритмічної мови — сукупність правил опису алгоритмів на алгоритмічній мові. Вказівка (команда) — окреме повідомлення про деяку операцію, яку повинна виконати машина.
Алфавіт навчальної алгоритмічної мови Алфавіт навчальної алгоритмічної мови включає в себе великі малі букви українського і латинського алфавітів, цифри десяткової системи числення, спеціальні символи, символи математичних операцій. Для більш зрозумілого і виразного запису алгоритмів алфавіт алгоритмічної мови доповнено службовими словами. Сукупність знаків і правил, за допомогою яких описуються алгоритми, утворюють алгоритмічну мову.
Правила описання алгоритмів навчальною алгоритмічною мовою Запис алгоритму повинен бути оформленим за такими правилами. У першому рядку записується слово алгоритм або його скорочення до трьох літер — алг. Далі за цим словом записується назва алгоритму. У другому рядку записується слово початок або його скорочення — поч. Далі з невеликим відступом у 2—З проміжки записуються дії, що складають власне алгоритм. Останнім рядком опису алгоритму має бути слово кінець або його скорочення — кін у цій самій позиції, що й слово початок. Алгоритм, описаний навчальною алгоритмічною мовою, має вигляд: Заголовок алгоритму початок серія кінець де серія — послідовність неіменованих вказівок, що виконуються в такому порядку, в якому вони записані.
Заголовок алгоритму Заголовок алгоритму — початкова частина запису алгоритму до службового слова початок, яка містить в собі ім'я алгоритму, перелік його аргументів і результатів з зазначенням їх величин. Заголовок алгоритму має вигляд: алг ім'я_алгоритму (список параметрів із вказанням їх типів) арг список аргументів рез список результатів де алг, арг, рез — службові слова. Виділені слова називаються службовими і використовуються при записі довільного алгоритму. Тіло алгоритму — частина алгоритму, яка знаходиться між словами початок і кінець.
Словесна й таблична форми подання алгоритму Алгоритм може бути поданий у різних формах. У словесній формі алгоритм записується як послідовність занумерованих словесних команд. Команди виконуються в порядку зростання їх номерів. Якщо потрібно змінити цей порядок, застосовується спеціальна вказівка на перехід до виконання команди із заданим номером. Словесна форма алгоритму найчастіше використовується в людському спілкуванні, в інструкціях користувачам програмних засобів або побутових приладів тощо.
Запис алгоритму Записом алгоритму можна вважати формулу, тому що з неї випливає порядок здійснення обчислень для отримання числового результату. Якщо виконується серія розрахунків за однаковими формулами, то для запису алгоритму застосовується таблична форма. За табличною формою в певних стовпцях таблиці розміщуються вхідні дані, а значення в наступних стовпцях — проміжні й вихідні — обчислюються за відповідними формулами. Таким чином, таблиця відбиває етапи виконання алгоритму. Ми використовували табличну форму подання алгоритму при роботі з електронними таблицями Excel.
Блок схема Поширеною формою наочного подання алгоритму є блок-схема. Блок-схема складається з окремих геометричних фігур — блоків, які з’єднуються напрямленими лініями. Лінії показують послідовність переходу від одного блока до наступного. Для подання алгоритму застосовуються блоки двох видів: функціональні й альтернативні
Блок-схеми Функціональні блоки позначаються прямокутниками. Одна напрямлена лінія входить у прямокутник і одна виходить із нього. Всередині прямокутника розміщується команда, яка має бути виконаною. Альтернативні блоки позначаються ромбами. Слово «альтернативний» (від лат. alternare — чергуватися) означає «такий, що припускає одну з двох можливостей, які виключають одна одну». Усередині ромба розміщується умова. Умовою називають будь-яке висловлювання, яке може мати тільки одне з двох значень — «істина» або «хибність». Наприклад, у ролі умов можуть бути висловлювання: «колір прапорця помаранчевий», «z — двозначне число», «зріст хлопця не нижче 170 см», «x = 7», «a >= b» тощо.
В альтернативний блок входить одна напрямлена лінія, а виходять з нього дві — з надписами «так» і «ні». Умова, записана всередині ромба, піддається перевірці. За результатом перевірки — «істина» («так») або «хибність» («ні») — здійснюється вибір відповідної напрямленої лінії, тобто вибір одного з двох можливих варіантів продовження виконання алгоритму. Крім функціональних та альтернативних блоків, у блок- схемах застосовуються також допоміжні блоки для позначення початку або кінця алгоритму) і введення або виведення Даних.
Поняття про мови програмування Мова — це система знаків (символів, жестів, міміки, положень перемикача і т. д.) для представлення, обміну інформацією. Це загальне визначення включає в себе і природні, і штучні (формальні) мови. До штучних мов належать мови, створені людьми для розв’язання специфічних задач. Це мова математичних формул, нотна грамота, мови програмування тощо. Алгоритмічна мова — це мова, призначена для представлення алгоритму у вигляді послідовності вказівок для виконання їх виконавцем алгоритму. Алгоритмічна мова, як і кожна інша, має свій словник. Основу цього словника складають слова, що використовуються для запису команд, які входять у систему команд виконавця.
Мови програмування Мови програмування — це алгоритмічні мови, призначені для опису алгоритмів, що орієнтовані для виконання на комп’ютері, або система позначень для точного опису алгоритму, який треба виконати за допомогою комп’ютера. Мова програмування, як і будь-яка інша мова, являє собою набір символів (алфавіт), систему правил складання базових конструкцій мови (синтаксис) та правила тлумачення мовних конструкцій (семантика). Ця система позначень і правил призначена для одноманітного і точного запису алгоритму. Алфавіт, синтаксис і семантика — три основні складові мов програмування. Програма — це алгоритм, записаний мовою програмування.
Трансляція, трансляція, компіляція Трансляція (від англ. translation — переклад) — програма, яка перетворює команди мови програмування на машинну мову. Існує два способи трансляції: інтерпретація та компіляція. Інтерпретація Інтерпретація (від англ. interpretation) — спосіб трансляції, при якому кожна інструкція програми перекладається в машинні коди та виконується, і тільки після виконання одного фрагмента програми процесор переходить до обробки іншого фрагмента. Це гнучка система перекладу, яка реалізовується нескладно. Вона використовується в тих випадках, коли потрібна простота трансляції (Basic), або там, де інший спосіб перекладу дуже складний або навіть неможливий (Lisp). Компіляція (від англ. compile — збирати) — спосіб трансляції, при якому здійснюється переклад усього тексту програми, збір перед її виконанням та запис у пам’ять комп’ютера. При перегляді програми компілятор виділяє місце в пам’яті для кожної змінної.
Класифікація мов програмування Мови програмування високого і низького рівнів. Програми для перших ЕОМ складалися машинною мовою, вельми далекою від понять, якими оперує людина. Алфавіт машинної мови складається тільки з двох символів {0, 1}. Для складання програм на такій мові була потрібна досить висока кваліфікація. Програмісти, зацікавлені в полегшенні своєї праці, і виробники ЕОМ зацікавлені в розширенні ринку, стали шукати вихід. Першим кроком на шляху створення мов, що містять поняття, близькі поняттям людини, стали мови, що перекладають символічні імена в машинні коди (асемблер). До мов програмування низького рівня належать мови асемблера — машинно-залежні мови, що описують дії в термінах команд процесора. Для кожного типу процесора існує своя мова асемблера, тому для перенесення програми на асемблері на іншу апаратну платформу її потрібно майже повністю переписати.
Законспектуйте відповіді на запитання Які існують способи запису алгоритмів? Хто і коли ввів вперше поняття алгоритму? В чому виявляються основні властивості алгоритмів? Перерахуйте основні алгоритмічні структури та опишіть їх. Які основні принципи розробки алгоритмів? Чим пояснюється різноманітність форм запису алгоритму? Охарактеризуйте словесно-покроковий спосіб запису алгоритму. Що таке результат виконання алгоритму? Що являє собою графічна форма запису алгоритму? Які види циклів Ви знаєте? Для чого використовують структуру «цикл»?
про публікацію авторської розробки
Додати розробку