Алгоритми та програми

1. Виконавці алгоритмів та їхні системи команд.

2. Способи опису алгоритму. Програма.Середовище опису й виконання алгоритмів.

3. Лінійні алгоритми.

4. Алгоритми з розгалуженнями.

5. Алгоритми з повтореннями

Виконавці алгоритмів та їхні системи команд. 

Способи опису алгоритму

Поняття алгоритма, системи команд виконавця

Залежно від цілей, початкових умов задачі, шляхів її вирі­шення алгоритми поділяються на:

Механічні — задають певні дії, позначаючи їх у єдиній послі­довності, забезпечуючи тим самим однозначний результат.

Імовірнісні — дають програму вирішення задачі кількома шля­хами, що приводить до ймовірнісного досягнення результату.

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

Ви вже не раз зустрічалися з алгоритмами в інших шкільних предметах. Наприклад, у хімії отримання тієї чи іншої сполуки можна описати за допомогою алгоритму. Але найбільше прикладів алгоритмів у математиці — науці, у якій власне й зародилося це по­няття. По суті, математика вивчає різні алгоритми і створює нові. До алгоритмів зі шкільного курсу математики належать правила виконання арифметичних дій, правила знаходження розв’язків рівнянь тощо. У вигляді алгоритмів можна сформулювати правила побудови різних геометричних фігур (згадайте задачу на побудо­ву), а також рекомендації щодо розв’язування типових задач.

До слова «алгоритм» близькі за значенням слова: спосіб, ре­цепт. Однак алгоритми в інформатиці — це не тільки рецепти роз­в’язування задач. Алгоритми розробляють, насамперед, із метою автоматизації дій виконавця.

Составление алгоритма начинается с разбивки описываемого процесса на последовательность отдельных шагов. Свойство разбивания алгоритма па отдельные шаги называют дискретностью алгоритма. Каждый шаг алгоритма формулируется в виде инструкций (команд), то есть определенных предписаний исполнителю.

Виконавець і властивості алгоритму

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

Алгоритми складаються з орієнтацією на певного виконавця ал­горитму: дресированої тварини, людини, автоматичного пристрою, комп’ютера. До складу алгоритму мають належати команди, які ви­конавець розуміє та може виконати.

Алгоритми складаються з урахуванням можливостей вико­навця.

Виконавець алгоритму — об’єкт (людина, комп’ютер), що здатний правильно зрозуміти й точно виконати всі дії алго­ритму.

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

Механічний (машинний) алгоритм — алгоритм, для якого виконавцем є ЕОМ. Такий алгоритм повинен відповідати низці вимог.

Перейдіть за посиланням та виконайте завдання:

Властивості алгоритмів. Способи подання алгоритмів.

Незважаючи на різноманіття алгоритмів, в них можна знайти багато спільного. І ці спільни риси називаються властивостями алгоритмів.

Властивості алгоритмів:

• Дискретність.

• Визначеність (однозначність).

• Формальність.

• Результативність.

• Масовість.

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

За скінченну кількість кроків алгоритм має приводити до здобуття потрібного результату або до досягнення потрібної мети. Цю властивість алгоритму називають скінченністю або результативністю.

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

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

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

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

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

Перейдіть за посиланням та пограйте в гру: http://www.umapalata.com/uschool/expo/vashygymaga/13309.html?LANG=RU

СПОСОБИ ТА ФОРМИ ОПИСУ АЛГОРИТМІВ

1. Словесні

2. Словесно-формульні

3. Графічні (схеми)

4. Скінченний набір кодів

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

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

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

Схема складається з елементів двох типів:

1-й тип — графічні фігури, кожна з яких відображає один з етапів процесу рішення задачі та містить у собі текст відповідної команди;

2-й тип — лінії зі стрілками, які вказують послідовність (порядок) виконання етапів. У цілому такий спосіб запису алго­ритмів можна розглядати як своєрідну алгоритмічну мову — сис­тему позначень і правил для однотипного запису алгоритмів та їх виконання.

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

У процесі розробки алгоритмів використовується три основні структури: слідування, розгалуження, повторення.

Команда — записаний в алгоритмі наказ виконавцеві вико­пати менпу закінчену дію.

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

План складання алгоритму

1. Уважно прочитати умову задачі.

2. Визначити:

а) що дано (аргументи);

б) що потрібно знайти (результати);

в) у якому вигляді (тип аргументів і результатів).

3. Записати заголовок алгоритму.

4. Визначити шляхи вирішення задачі та виявити необхідні проміжні величини.

5. Записати алгоритм алгоритмічною мовою. 

6. Перевірити правильність складання алгоритму при конк­ретних значеннях аргументів

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

Виконайте завдання

Програма. Середовище опису й виконання алгоритмів

Середовище виконання алгоритму – програма Scratch

Як завантажити середовище Скретч?
Вікно програми Скретч має складові, подібні до вікон програм, які ми вже вивчали: рядок заголовка, меню, кнопки управління вікном  тощо
У цьому середовищі виконавцем алгоритму є Рудий кіт. Для нього існує своя система команд. З кожною командою пов’язана певна подія, яка відтворюється на сцені.

Завантажити Скретч можна за посиланням: http://scratch.mit.edu/download

Виконавців алгоритму в середовищі Скретч ще називають спрайтами. У перекладі з англійської мовиsprite — світля­чок або ельф.
Програма, що виконується в середовищі Скретч, складається з команд, які можна обрати в контейнері.  Вони реалізують команди із системи команд виконавця алгоритмів у середовищі, які
об’єднані в групи:

•  руху,

• зміни вигляду,

•  малювання,

•  відтворення звуку тощо.

  Головне програмне вікно середовища поділено на декілька частин, згрупованих у три стовпчики.

  • лівий стовпчик містить палітру блоків.

  • центральний стовпчик містить піктограму активного спрайту з координатами його розташування на сцені та 3 закладки:Скрипти, Образи, Звуки;

  • правий стовпчик містить Сцену і Cписок спрайтів.

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

  Як усталено використовують спеціального виконавця вказівок — Рудого кота . Він може рухатися, говорити, змінювати зовнішній вигляд, взаємодіяти з іншими виконавцями на сцені. Інших виконавців можна долучати:

  • з бібліотеки Scratch;

  • з мережі (локальної чи глобальної);

  • як об’єкти, створені в інших графічних програмах (наприклад, GIMP)

  • як об’єкти, створені у графічому редакторі, вбудованому у Scratch.

Скрипт (script, сценарій, метод) — послідовність вказівок, що визначає, які дії і в якому порядку потрібно виконати певному об’єкту (спрайту).

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

Стек (stack) — набір послідовно сполучених різнокольорових графічних блоків у межах однієї події.

Блок — це мінімальний фрагмент програми у Scratch: змінна, оператор, функція або структура, що керує. Блоки згруповано у 8 категорій (див. далі ілюстрації).

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

Образи (вигляд спрайту) — сукупність зображень одного й того ж об’єкту (спрайту), кожне з яких дещо відрізняється від попередніх.

Звуки — приєднані звукові ефекти й музика.

Сцена — область, в якій діє об’єкт (спрайт) при виконанні програми.

Зображення вигляду виконавця, фон сцени і програму мож­на зберегти у файлі. Файл, створений у середовищі Скретч, називають проектом.

Відкривають існуючий проект за таким алгоритмом:

• У меню Файл обрати вказівку Відкрити.

• У вікні Відкрити проект вибрати потрібну папку, напри­клад, папку Навчальні проекти.

• Натиснути кнопку Гаразд.

• Вибрати файл проекту. Знову натиснути кнопку Гаразд.

Які особливості режимів роботи в середовищі Скретч?
Під кнопками управління вікном середовища розміщено кноп­ки перемикання його режимів роботи.
У режимі перегляду ми бачимо тільки сцену виконання алго­ритму, що займає весь екран. Вийти з нього можна, натиснувши кнопку повернення у верхньому правому кутку екрана Щоб виконавець алгоритму розпочав виконувати команди на сцені, натискають на зелений прапорець. КнопкаЗупинити все припиняє виконання алгоритму.
У режимах У зменшений розмір та У певний розмір відобра­жаються всі складові вікна програмного середовища, як пока­зано на попередньому слайді.
У першому режимі сцена зменшена.
У цих режимах алгоритм можна виконувати покомандно, групою або цілком.
Наприклад, якщо в наборі команд, що міститься у вкладці Скрипти, обрати одну команду та двічі клацнути на ній мишею, то на сцені відтворюватиметься подія, що відповідає цій команді.
Натискання на кнопку Зупинити всеприпиняє виконання алгоритму.

Ще раз розібратися та повторити вам допоможе відеоурок:

Установи відповідності між зображеннями і їхніми назвами у середовищі Scratch:

Кросворд

Дайте відповідь на наступні запитання:

Лінійні алгоритми

Види алгоритмів. Поняття лінійного алгоритму

Команди в алгоритмах записують одна за одною в певному порядку, а от виконуються вони не завжди в такій послідовності. Залежно від порядку виконання команд алгоритми поділяють на три типи:

• лінійні алгоритми (слідування);

• алгоритми з розгалуженням;

• алгоритми з повторенням.

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

Вигляд лінійного алгоритму:

Лінійний алгоритм переходу вулиці:

Виконайте завдання:

Поняття алгоритму з розгалуженням

Вигляд алгоритму з розгалуженням:

Поняття алгоритму з повторенням

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

Команди Scratch для побудови зірки із восьми променів:

Команда Scratch	Положення спрайта	Пояснення дій спрайта
		Початкове положення спрайта
		Повертає на кут 45° проти годинникової стрілки
		Переміщується на 3° кроків

		Повертає на кут 90° за годинниковою стрілкою
		Переміщується на 30 кроків
		Повертає на кут 45° проти годинникової стрілки
		Переміщується на 30 кроків
		Повертає на кут 90° за годинниковою стрілкою
		Переміщується на 30 кроків

Визначити види алгоритмів: