14 поняття про мову розмітки гіпертексту

Вид материалаУрок
Тема 15 основи алгоритмізації і програмування
Тема 15 основи алгоритмізації і програмування
Тема 15 основи алгоритмізації і програмування
Приклад алгоритму
Властивості алгоритму
Подобный материал:
1   2   3   4   5

ТЕМА 15 ОСНОВИ АЛГОРИТМІЗАЦІЇ І ПРОГРАМУВАННЯ



УРОК 1 ІНФОРМАЦІЙНА МОДЕЛЬ


Основні етапи розв'язання задач з використанням комп'ютера

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

Процес розв'язання задач з використанням комп'ютера складається з декількох етапів:

етап 1. постановка задачі та її аналіз

Постановка задачі передбачає виявлення сутності задачі. На етапі постановки задачі вирішуються такі питання:

• окреслюються предмет задачі, умови, в яких він знаходиться, бажаний результат розв'язування задачі;

• уточнюється мета розв'язання задачі; визначається, які дані потрібні для її вирішення, а які є несуттєвими; встановлюється, які саме результати та в якому вигляді мають бути знайдені;

• з'ясовується, чи є обмеження на вхідні дані задачі; при яких умовах можна отримати результат, а при яких — ні; які результати вважатимуться правильними.

етап 2. побудова інформаційної моделі задачі, вибір методу її розв'язування

На цьому етапі розробляється інформаційна модель (спочатку звичайно у вербальній (усній) формі, далі — у знаковій формі), добирається метод розв'язування задачі.

З цією метою реалізуються такі дії:

• встановлюються параметри задачі, взаємозв'язки між ними, оцінюється залежність результатів рішення задачі від її параметрів, і на цій основі з урахуванням сутності задачі, мети її постановки створюється інформаційна модель задачі;

• задача формалізується (вводиться система умовних позначень, і задача подається у формалізованому вигляді);

• здійснюється перехід до знакової інформаційної моделі з використанням прийнятої системи позначень;

• аналізуються можливі методи розв'язування задачі та вибирається найбільш ефективний

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

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

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

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

етап 3. розробка комп'ютерної моделі

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

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

Розробка комп'ютерної моделі передбачає такі заходи:

• складання алгоритму розв'язування задачі на основі вибраного методу її розв'язування. В результаті цей метод втілюється у послідовність простих дій, які приводять до одержання потрібного результату;

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

• реалізація алгоритму засобами вибраного програмного середовища, тобто переведення алгоритму у таку форму, яка робить його придатним для виконання комп'ютером. Результатом цього процесу є програма;

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

За півстоліття активної експлуатації комп'ютерів нагромаджено значний досвід розробки програмного забезпечення, і одним із наслідків цієї роботи є створення фонду програмних засобів, орієнтованих на'застосування комп'ютера у певній предметній чи професійній області. Такі програмні засоби називають інструментальними, тому що вони надають користувачеві зручні інструменти для побудови комп'ютерних моделей відповідного типу. Наприклад, математичні середовища (Gran, DG, MathLab, Derive та інші) призначаються для реалізації математичних моделей; графічні середовища (Paint, CorelDraw, PhotoShop та інші) — для створення графічних моделей і т.д. Якщо ж задача вимагає розробки власної програми, то застосову-

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

етап 4. комп'ютерний експеримент

Метою комп'ютерного експерименту є одержання інформації, на основі якої можна приймати рішення, робити висновки про властивості об'єкта моделювання або прогнозувати його поведінку в тій чи іншій ситуації.

Цей етап складається з таких дій:

• розробка плану проведення експерименту;

• випробування комп'ютерної моделі; •, аналіз отриманих результатів.

Сутність випробування комп'ютерної моделі полягає у багаторазових запусках програми для опрацювання певних наборів вхідних даних. Такі набори розробляються в ході планування експерименту з метою виявлення певних залежностей чи отримання потрібних даних. Аналіз результатів експерименту може дати підставу для його завершення, якщо всі поставлені цілі досягнуто, або для продовження експерименту, корекції плану його проведення, якщо виявилася необхідність доповнення даних чи намітився новий напрям дослідження. Іноді за результатами експерименту виникає потреба в уточненні моделі або навіть у внесенні змін у постановку задачі, і тоді весь процес починається знову.


ТЕМА 15 ОСНОВИ АЛГОРИТМІЗАЦІЇ І ПРОГРАМУВАННЯ


УРОК 2 ПОНЯТТЯ ІНФОРМАЦІЙНОЇ МОДЕЛІ


Слово «модель» походить від латинського modulus, що означає «міра», «взірець», «норма». Модель — це матеріальний або уявлюва-ний аналог деякого об'єкта (предмета, явища або процесу), який зберігає суттєві риси об'єкта і здатний заміщувати його під час вивчення, дослідження або відтворення.

Процес створення моделі об'єкта називається моделюванням.

Об'єкт, що моделюється, називається прототипом, або оригіналом.

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

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

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

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

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

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

Моделі можна класифікувати за різними ознаками.

За областю застосування розрізняють:

навчальні моделі (засоби наочності, навчальні програми, тренажери);

дослідні моделі (зменшені чи збільшені копії об'єкта проектування:);

науково-технічні моделі (пристрої, що створюються для дослідження явищ і процесів, — наприклад, системи);

ігрові моделі (воєнні, економічні, спортивні, ділові ігри, які застосовуються для виявлення реакції об'єкта на ту чи іншу ситуацію);

імітаційні моделі (такі моделі застосовуються для вивчення та оцінювання можливих наслідків певних дій; наприклад, перед тим, як ввести у вжиток новий лікарський препа-

рат, здійснюють Імітаційний експеримент —

випробують препарат на мишах).

За галуззю знань, де застосовується модель, виділяють біологічні, фізичні, соціологічні та інші моделі.

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

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

За способом подання моделі поділяються на дві великі групи: матеріальні та інформаційні.

Матеріальні моделі можна назвати також предметними, натурними, фізичними. Вони завжди мають реальне втілення. Прикладами матеріальних моделей є дитяча іграшка, чучело птаха, макет ракети.

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

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

інтуїтивні моделі, які є уявленнями про об'єкт, отриманими в результаті роздумів, умовиводів (вірш, який складається у мозку поета; уявлення людини про навколишній світ тощо);

образні моделі, які виражають властивості оригінала засобами усної мови або образотворчими засобами (усна розповідь, фотографія, твір живопису, кінофільм тощо);

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

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

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

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

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

Надзвичайна значущість комп'ютерного моделювання полягає в тому, що воно дає можливість:

• досліджувати об'єкти чи явища, які неможливо, дорого або небезпечно відтворювати в реальних умовах;

• здійснювати пошук рішень, які потребують складних, численних або трудомістких розрахунків;

• уникати можливих шкідливих чи руйнівних наслідків проведення натурних випробувань;

• економити матеріальні ресурси;

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

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

ТЕМА 15 ОСНОВИ АЛГОРИТМІЗАЦІЇ І ПРОГРАМУВАННЯ


УРОК 2 АЛГОРИТМИ


Поняття алгоритму. Виконавець алгоритму

З алгоритмами ми зустрічаємося на кожному кроці. Будь-яка людина користується набором всіляких алгоритмів — правил, які вона засвоює в процесі виховання та навчання, фізичного тренування, набуття власного життєвого досвіду. Інструкції користування ліфтом, телефоном, різноманітними автоматами і побутовими приладами, правила переходу вулиці, надання першої медичної допомоги, приготування страв, виконання арифметичних дій або гімнастичних вправ, покроковий план розв'язування задачі або проведення фізичного чи хімічного досліду — все це можна вважати алгоритмами. Алгоритми відіграють велику роль у житті людини: вони зберігають її сили та час, тому що саме через алгоритми передається здобутий досвід ефективних способів діяльності. Один раз засвоєним правилом людина може користуватися все своє життя.

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

Назва «алгоритм» походить від імені видатного вченого Мухамеда аль-Хорезмі (Мухамеда з Хорезму), якому належить значний внесок у розвиток математики. 825 року він написав «Книгу про індійську арифметику», де було вперше систематично викладено арифметику, засновану на десятковій системі числення із застосуванням нуля, тобто ту арифметику, яка в наш час є звичайною та природною. Арифметика виникла в Індії і тому раніше називалася індійською. В перекладі на латинську «Книги про індійську арифметику» ім'я її автора було написано як «Алгоритм». «Так казав Алгоритм» — починали європейські вчені, посилаючись на викладені в книзі правила виконання арифметичних дій. Ці правила і дістали назву алгоритмів. Тільки у XX столітті, у зв'язку зі становленням та розвитком теорії алгоритмів, поняття алгоритму стало вживатися в більш широкому значенні.


Приклад алгоритму:

Алгоритм завершення роботи з комп'ютером, який працює під управлінням операційної системи Windows.

1. Натиснути на робочому столі Windows кнопку виходу в головне-меню «Пуск».

2. Вибрати в меню «Пуск» команду «Завершення роботи».

3. У діалоговому вікні «Завершення роботи з Windows» натискуванням радіокнопки вибрати пункт «Вимкнути комп'ютер».

4. Підтвердити свій вибір натискуванням кнопки «Так» на діалоговому вікні.

5. Дочекатись повідомлення на екрані «Тепер живлення комп'ютера можна вимкнути».

6. Натиснути кнопку «Power» на системному блоці комп'ютера.

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

Будь-який алгоритм складається з розрахунком на певного виконавця, який здатний зрозуміти та виконати кожну з команд алгоритму. Так, наприклад, наведений вище алгоритм завершення роботи з операційною системою Windows розраховано на виконавця, який знає, що таке кнопка, радіокнопка, меню, пункт меню, як здійснюється його вибір і таке інше. Кожний виконавець має свій перелік команд, які він розуміє і може виконати. Цей перелік називається системою команд виконавця.

Команди алгоритму мають формулюватися чітко, коротко, без зайвої інформації. Якщо виконавцем алгоритму є людина, то одну й ту саму команду можна сформулювати дещо по-різному. Так, обидві команди «Обчислити суму чисел 5 і 7» та «Знайти значення 5+7» людина сприйме та виконає однаково. На відміну від людини автоматичний пристрій, наприклад комп'ютер, має певний обмежений перелік точно визначених команд, і ніякі відхилення від правил їх запису та застосування не припускаються. Тому неточно сформульована команда може бути сприйнятою і, як наслідок, виконаною неправильно, або комп'ютер зовсім відмовиться виконувати команду і припинить свою роботу над алгоритмом.

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

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


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

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

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

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

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

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

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

дій. Саме це і дозволяє використовувати автоматизовані пристрої, зокрема комп'ютер, для розв'язування задач.

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

З урахуванням перелічених властивостей можна запропонувати уточнене визначення поняття алгоритму:

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