Додаткова література. 1. Вступ до спеціальності: конспект лекцій у двох частинах

1. Вступ до спеціальності: конспект лекцій у двох частинах. / укладач А.В. Булашенко - Суми: Вид-во СумДУ, 2010. – Ч.1 – 133с.

Бали___________________ Оцінка______________________

ТЕМА 4 «Алгоритмізація та формалізація інженерних задач»

СРС 4 «Схематичне зображення алгоритму»

Мета роботи: зрозуміти сутність та головну задачу алгоритмізації та формалізації інженерної задачі, визначити основні форми представлення алгоритму, поняття блок-схеми та призначення її функціональних блоків.

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

Методичні рекомендації до самостійної роботи студентів

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

Під алгоритмом розуміють опис послідовності дій, які потрібно виконати для досягнення поставленої мети або здобуття необхідного результату. Будь-який алгоритм складається з розрахунком на певного виконавця, якому належить виконувати приписані дії. Кожна дія алгоритму спричиняється окремою вказівкою. Вказівки алгоритму називаються командами. Отже, виконавець алгоритму має бути здатним зрозуміти та виконати кожну з команд алгоритму. Так, наприклад, алгоритм розв’язання квадратного рівняння розрахований на виконавця, який знає, що таке дискримінант, як обчислити квадратний корінь тощо. Сукупність команд, які виконавець може зрозуміти й виконати, називається системою команд виконавця. Якщо алгоритм орієнтовано на виконання людиною, то до формулювання команд жорсткі вимоги не висуваються. Достатньо, щоб людина точно зрозуміла, що саме від неї вимагається. Так, обидві команди: «знайди добуток чисел 5 і 7» і «помнож 5 на 7» людина зрозуміє і виконає однаково. Якщо ж виконавцем алгоритму є технічний пристрій, зокрема комп’ютер, то в такому разі слова «зрозуміти команду» означають розпізнати (або ідентифікувати) команду. Ідентифікацією (від лат. identicus — тотожний і ficatio — роблю) називається ототожнення об’єкта з одним із відомих системі. Комп’ютер має певний обмежений перелік точно визначених команд, які він може ідентифікувати й виконати. Ніякі відхилення від правил запису команд не припустимі. Комп’ютер у точності виконує надані йому команди й не коригує наших помилок. У разі неможливості ідентифікації або виконання команди він лише вказує на наявність помилки і припиняє роботу над алгоритмом. Для виконання алгоритму виконавцеві звичайно недостатньо самого алгоритму. Виконати алгоритм означає застосувати його до розв’язання конкретної задачі, тобто здійснити заплановані дії стосовно певної сукупності вхідних даних. Не будь-яка інструкція чи послідовність вказівок є алгоритмом.

Алгоритм може бути поданий у різних формах. У словесній формі алгоритм записується як послідовність занумерованих словесних команд. Команди виконуються в порядку зростання їх номерів. Якщо потрібно змінити цей порядок, застосовується спеціальна вказівка на перехід до виконання команди із заданим номером. Словесна форма алгоритму найчастіше використовується в людському спілкуванні, в інструкціях користувачам програмних засобів або побутових приладів тощо. Записом алгоритму можна вважати формулу, тому що з неї випливає порядок здійснення обчислень для отримання числового результату. Якщо виконується серія розрахунків за однаковими формулами, то для запису алгоритму застосовується таблична форма. За табличною формою в певних стовпцях таблиці розміщуються вхідні дані, а значення в наступних стовпцях — проміжні й вихідні — обчислюються за відповідними формулами. Таким чином, таблиця відбиває етапи виконання алгоритму. Ви використовували табличну форму подання алгоритму при роботі з електронними таблицями Excel.

Поширеною формою наочного подання алгоритму є блок-схема. Блок-схема складається з окремих геометричних фігур — блоків, які з’єднуються напрямленими лініями. Лінії показують послідовність переходу від одного блока до наступного. Для подання алгоритму застосовуються блоки двох видів: функціональні й альтернативні.

а) б)

Рис. 1 Основні елементи блок-схеми алгоритму (а) функціональний; б) альтернативний)

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

Алгоритмізація – етап розв’язання задачі, результатом якого є розробка алгоритму і її розв’язання.

Схематичне зображення алгоритму – це графічне подання всіх його кроків за допомогою відповідних геометричних об’єктів.

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

Формалізована схема процесу/задачі має включати в себе:

1. характеристики процесу/ задачі;

2. систему параметрів, що впливають на сам процес, задачу;

3. визначення залежностей між характеристиками і параметрами процесу/задачі з урахуванням усіх потрібних факторів;

4. систематизовану і уточнену сукупність цих вхідних даних, відомих параметрів процесу/задачі та початкових умов.

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

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

Основні:

1. Вставте слова, пропущені у наведеному нижче визначенні алгоритму (5 балів – 0,25 балу):

«Алгоритм — це … і … припис про здійснення скінченної послідовності визначених дій з метою розв’язання задачі певного типу або досягнення поставленої мети».

а) чіткий;

б) точний;

в) зрозумілий для виконавця;

г) короткий;

д) простий;

е) доступний.

2. Дайте відповіді на тестові завдання (30 балів – 1,5 бали)

1. Властивостями алгоритму є:

а) зрозумілість;

б) повнота;

в) лаконічність;

г) масовість;

д) дискретність;

е) детермінованість;

є) формальність;

ж) скінченність;

з) правильність.

2. Зрозумілість алгоритму означає, що:

а) кожна його команда є зрозумілою для всіх;

б) кожна команда алгоритму є зрозумілою для його виконавця;

в) кожна його команда є простою для виконання;

г) виконавець розуміє й може виконати кожну команду алгоритму;

д) кожна команда алгоритму може бути виконаною.

3. Детермінованість алгоритму означає, що:

а) алгоритм дає виконавцю все, що йому потрібно для розв’язання завдання;

б) алгоритм обмежує дії виконавця;

в) алгоритм однозначно визначає всі дії виконавця;

г) алгоритм гарантує розв’язання задачі за скінченну кількість кроків.

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

а) сукупності окремих простих дій;

б) визначеної послідовності окремих простих дій;

в) певної множини зрозумілих дій;

г) скінченної множини дій, які виконавець може виконати.

5. Масовість алгоритму означає, що його можна застосовувати:

а) для розв’язання будь-яких задач;

б) для розв’язання будь-яких задач певного класу;

в) для розв’язання задач певного класу з будь-якими вхідними даними;

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

3. Здійснити розв’язок за наведеним алгоритмом (35 балів – 2,25 балів)

Індійський математик Д. Капрекар довів, що будь-яке чотиризначне число, у якого не всі цифри однакові, в результаті перетворень за певним алгоритмом приводить до одного й того самого числа, яке отримало назву сталої Капрекара.

Алгоритм має такий вигляд:

1) переставити цифри числа N за спаданням;

2) переставити цифри числа N за зростанням;

3) відняти від першого числа друге;

4) якщо отримана різниця R не дорівнює числу N, то повторити з нею дії 1)—3).

Через не більш як 7 повторень алгоритм приводить до числа, яке далі переходить само в себе. Це і є стала Капрекара. Знайдіть її.

Додаткові:

Побудуйте етапи розвитку цивілізацій (20 балів – 1 бал)

Джон Конвей запропонував алгоритм «Життя», за яким можна спостерігати поетапний розвиток «цивілізації» на клітинному просторі.

Спочатку у деяких клітинках простору зародилося життя. Кожний наступний етап розвитку «цивілізації» цілком визначається ситуацією, яка була на попередньому етапі, за такими правилами:

- клітинка виживає, якщо у неї два або три сусіди;

- клітинка гине, якщо у неї менше двох сусідів (від самотності) або більше трьох (від тісноти);

- життя зароджується в пустій клітинці, якщо вона має трьох сусідів.

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

Побудуйте етапи розвитку таких «цивілізацій»:

Рекомендована література

1. Гаєвський О. Ю. Інформатика: 7-11 кл. Навч. Посіб. – К.: Видавництво А.С.К., 2004. – 512 с.: іл.

2. Зарецька І. Т., Колодяжний Б. Г., Гуржій А. М., Соколов О. Ю. Інформатика: Навч. посібн. для 10-11 кл. –К.: Навчальна книга, 2002. – 496 с.: іл..