Тема” Алгоритми. Властивості алгоритмів. Форми подання алгоритму. Виконавець алгоритму.”
Мета уроку. Ознайомити учнів з поняттям алгоритму, властивостями алгоритмів, виконавцем алгоритму, способами опису алгоритмів, схемами алгоритмів.
Хід уроку.
I . Повідомлення теми та мотивація навчання.
Повідомити тему та ознайомити учнів з метою уроку.
II. Актуалізація опорних знань та перевірка домашнього завдання.
- Математична модель.
- Етапи розв’язування будь-якої за складністю чи обсягом задачі за допомогою ЕОМ:
· розробка математичної моделі (математична постановка задачі);
1) Визначають дані, які потрібні для побудови математичної моделі (аргументи).
2) Визначають, що необхідно знайти (результат) і які обмеження накладаються на результат.
3) Встановлюють зв’язки між аргументами і результатами у вигляді формул, рівнянь, нерівностей та їх систем, тобто будують власне математичну модель.
· вибір методу розв’язування задачі;
· побудова алгоритму розв’язування задачі;
· складання програми (запис алгоритму засобами мови програмування);
· налагодження та тестування програми (введення програми в комп’ютер та перевірка її правильності на ряді тестових прикладів);
· виконання програми для заданих вхідних даних;
· аналіз отриманих результатів.
- Інформаційна модель.
III. Подача нового матеріалу.
Поняття алгоритму. Властивості алгоритмів. Виконавець алгоритмів.
Термін «алгоритм» утворився в результаті перекладу на європейські мови імені арабського математика ІХ століття Аль-Хорезмі, який описав правила (алгоритми) виконання основних арифметичних операцій у десятковій системі числення. В теперішній час поняття алгоритму використовується не тільки в математиці. Його використовують в багатьох сферах людської діяльності, наприклад, говорять про механізми (алгоритми) управління виробничим процесом, алгоритми гри в шахи, використання побутових приладів, алгоритми пошуку шляху в лабіринті, алгоритм управління ракетою та інше.
Алгоритм – це зрозуміла і чітка вказівка виконавцеві здійснювати послідовність дій, направлених на досягнення конкретної мети, або розв’язання задачі певного типу.
У своїй практичній діяльності люди постійно мають справу із алгоритмами (послідовностями вказівок, інструкціями, правилами тощо). Для прикладу можна назвати приготування кулінарної страви згідно з рецептом, користування міжміським телефоном-автоматом, пошук слова у словнику, розв’язування квадратного рівняння.
Властивості алгоритмів:
1. Дискретність. Алгоритм можна розбити на окремі вказівки (правила), кожна з яких передбачає виконання певної дії ( арифметичної чи логічної). Кожна дія повинна бути виконана виконавцем, перш ніж перейти до наступної команди.
2. Скінченність. Виконання кожного алгоритму повинно завершуватись за скінчене число кроків. При виконанні алгоритму деякі кроки можуть повторюватись. В математиці існують такі процедури, які мають алгоритмічний характер, але не мають цієї властивості. Так обчислення числа p нескінченний процес, але якщо ввести умову: “Закінчити обчислення після отримання n десяткових знаків після коми числа p, то процес закінчиться.
3. Результативність. Виконання алгоритму завжди повинно приводити до певного результату (можливо, негативного). Воно не може закінчуватись невизначеною ситуацією або ж не закінчуватись взагалі. Алгоритм вказує послідовність дій по переробці даних в результати. Якщо задача немає розв’язку, то цей випадок також повинен бути врахований в алгоритмі.
4. Формальність.. Виконавець відповідно до алгоритму повинен одержати результат, не вникаючи в його суть. Результат не повинен залежати від яких-небудь факторів, що не є частиною алгоритму. Команди повинні бути зрозумілі виконавцеві і входити в систему команд виконавця. Людина може не розуміти суті алгоритму та призначення окремих дій , але виконуючи їх прийти до правильного результату. І навпаки людині здається, що вона розуміє команди алгоритму, але по своєму, зовсім протилежне до замислу алгоритму. Ця властивість має особливе значення для автоматизації виконання алгоритмів. Очевидно, що комп’ютери не можуть розуміти суть завдань і окремих вказівок алгоритмів.
5. Визначеність. Будь-який алгоритм повинен бути описаний так, щоб при його розшифровуванні у виконавця не виникло двозначних вказівок Тобто різні виконавці згідно з алгоритмом повинні діяти однаково та прийти до одного й того ж результату. Будь-який алгоритм повинен бути записаний за допомогою зрозумілих виконавцю команд, які можна виконати для зазначених вхідних даних і не допускати подвійного тлумачення. Наприклад, підставити у вираз 2х1+3х2 замість змінної число 2. команда не зрозуміла виконавцеві.
6. Масовість За допомогою складеного алгоритму повинен розв’язуватись цілий клас однотипних задач.
7. Зрозумілість. В алгоритмі повинні бути лише операції, які знайомі виконавцеві. При цьому виконавцем алгоритму може бути людина, комп’ютер, робот тощо.
8. Правильність. Алгоритм правильний, якщо його виконання забезпечує досягнення мети.
Вчинки людей підпорядковані досягненню конкретної мети. Часто люди не замислюються над тим, що їхні дії є прикладами виконання алгоритмів. Обдумуючи плани на день, ми фактично складаємо алгоритми розв’язування побутових задач чи задач, пов’язаних з професійною діяльністю. Отже, люди є виконавцями алгоритмів.
Для полегшення фізичної та інтелектуальної праці люди створили різні технічні пристрої, машини, автомати, роботи, комп’ютери. Прикладами механічних виконавців алгоритмів можуть бути: телефонний автомат, автомати, що продають воду чи морозиво, роботи-маніпулятори. Робот замінює людину біля конвеєра: малює кузов автомобіля чи закручує гайки Комп’ютер використовується для опрацювання великих обсягів інформації. Виконуючи команди користувача чи деякої програми, він допомагає розв’язати не лише складні інженерні задачі, але й може визначити діагноз і порекомендувати ліки хворому, подати довідку з енциклопедичного словника, виправити граматичні помилки в тексті чи перекласти текст, відтворити музику чи відеозображення, переслати повідомлення тощо.
Дія – це частина роботи, спрямованої на отримання корисного результату.
Алгоритм складається з елементарних вказівок, закінчених дій, кожна така вказівка називається командою.
Кожний виконавець алгоритму може виконати певну кількість команд, які називаються допустимими командами виконавця, або системою команд виконавця. Для людини кількість команд, які вона може виконати, практично необмежена. Тому на дії людей розумні обмеження накладаються законами, мораллю й сумлінням. Кількість команд для механічних виконавців є значно меншою. Наприклад, робот не виконує таких команд, як їсти чи пити, а комп’ютер не переміщується у просторі. Команди, які не може виконати виконавець, називаються недопустимими.
Алгоритми можна описувати за допомогою слів, спеціальних мов, використовуючи математичні формули, таблиці, графіки, блок-схеми та інші засоби.
Способи подання алгоритмів.
Схеми алгоритмів.
Використовують наступні способи подання (опису) алгоритмів:
1. Символьний. Символьне представлення поділяється на записи:
а) природною мовою. Типовими прикладами алгоритмів , поданих природною мовою, є інструкції користування побутовими приладами, міським телефоном, торговими апаратами тощо.
б) штучною мовою. Серед штучних мов виділяють
1) мови програмування. У вигляді програм, написаних певною мовою програмування.
2) математичні формули, ще в середні віки започаткували подання алгоритмів штучною мовою. Опис здійснюється у словесній формі з використанням математичних чи інших формул.
2. Графічний. Графічне подання алгоритмів, в свою чергу, поділяється на представлення алгоритму у вигляді
а) бпок-схем.
б) структурних схем, (структурограм (діаграм) Нессі- Шнейдермана);
У бпок-схемах окремі дії зображаються геометричними символами -фігурами, що мають стандартне призначення та вигляд. Найбільш використовувані блоки подано в таблиці.
Блоки у блок-схемі з’єднані лініями потоків. У кожен блок може входити не менше однієї лінії, з блоку ж може виходити лише одна лінія пoтoкy. З логічного блоку завжди виходять дві лінії потоку: одна у випадку виконання умови, інша – при її невиконанні.
При використанні діаграм Нессі-Шнейдермана алгоритми подаються у вигляді прямокутників, які примикають один до одного (команди, які в них вказуються, виконуються послідовно) або входять у середину інших (вкладені конструкції). Для прикладу опишемо алгоритм Ейлера знаходження найбільшого спільного дільника.
IV. Розв’язування вправ.
Приклад 1. Скласти алгоритм обчислення і роздрукування значення виразу у = (Ах+В)(Сх+D).
1. Задати значення А, В, С, D, х.
2. Обчислити у = (Ах+В)(Сх+ D).
3. Надрукувати у
4. Процес обчислення завершити.
Приклад 2. Скласти алгоритм знаходження найбільшого з трьох чисел а, Ь, с і результат присвоїти змінній у.
1. Задати значення а, Ь, с.
2. Якщо а>=b, то d:=a, інакше d.=b.
3. Якщо d>=c, то y:=d, інакше у:=c.
4. Надрукувати значення у.
5. Процес обчислення завершити.
Приклад 3. Скласти алгоритм знаходження коренів квадратного рівняння ах2 + Ьх + с = 0.
1. Задати значення а, Ь, с
2. Обчислити D= b2 -4ас.
3. Якщо D<O, то перейти на крок 7, інакше – на крок 4.
4. Обчислити х1=(-Ь+ OD )/(2а), х2=(-Ь –OD )/(2а).
5. Надрукувати значення х1, х2.
6. Перейти на крок 8.
7. Надрукувати повідомлення про те, що рівняння коренів немає.
8. Процес розв’язування завершити.
Приклад 4. Скласти алгоритм обчислення суми цілих чисел від 1 до 100
1. Присвоїти початкові значення S.=0; х:=1.
2. Поки х<=I00, виконувати команди S:=S+ х; х:=х+1.
3. Надрукувати значення S.
4. Процес обчислення завершити.
V. Домашнє завдання.
Тема” Алгоритми. Властивості алгоритмів. Форми подання алгоритму. Виконавець алгоритму.”