Тема 15. Основні властивості і параметри алгоритмів . Основні поняття про алгоритмічну мову.

Основні терміни теми : дискретність, детермінованість, точність, зрозумілість.

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

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

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

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

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

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

Відзначена властивість називається властивістю визначеності, або детермінованості.

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

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

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

Проілюструємо властивості алгоритму на прикладі алгоритму Евкліда.

Масовість алгоритму Евкліда полягає в тім, що його можна застосувати до будь-якої пари натуральних чисел. Результативність його полягає в тому, що він визначає процес, що приводить для будь-якої пари натуральних чисел до одержання їхнього найбільшого дільника. Зрозумілість алгоритму полягає в тім, що виконавець уміє виконувати дії, обумовлені командами алгоритму. Детермінованість алгоритму випливає з того, що кожна команда виконується виконавцем однозначно. Точність алгоритму забезпечується тим, що, по-перше, виконавцю відомо, з чого починати виконання алгоритму (з команди номер 1), і, по-друге, кожна команда постачена вказівкою, яку команду виконувати наступною.

2. Приклади правил, які не є алгоритмами.

Очевидно, не кожне правило, що приводить до рішення задачі, є алгоритмом. Розберемо з цих позицій кілька таких правил.

Приклад 2.1. Проведення перпендикуляра до прямій MN у заданій крапці A.

I. Відкласти в обидва боки від крапки A на прямій MN циркулем відрізки рівної довжини з кінцями B і C,

II. Збільшити розчин циркуля до радіуса, у півтора-два разу більшого довжини відрізків AB у AC.

III. Провести зазначеним розчином циркуля послідовно з центрами B і C дуги окружностей так, щоб вони охопили крапку A і утворили дві крапки перетинання один з одним D і E.

IV. Узяти лінійку і прикласти її до крапок D і E і з’єднати їх відрізком. При правильній побудові відрізок пройде через крапку А и буде шуканим перпендикуляром

Рис. 2.1. Проведення перпендикуляра до прямої в заданій крапці

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

Насамперед, воно не має властивість детермінованості. Так, у пункті І потрібно від виконавця зробити вибір відрізка довільної довжини (для побудови крапок B і C треба провести окружність довільного радіуса r з центром у крапці A). У пункті ІІ потрібно зробити вибір відрізка в півтора-два разу більшого довжини відрізків AB і AC. У пункті 3 треба провести дуги, що також однозначно не визначаються їх описом. Людина-виконавець, що застосовує дане правило, до тим самим вихідним даних (прямій MN і крапці A) повторно, одержить незбіжні проміжні результати. Це суперечить вимозі детермінованості алгоритму.

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

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

У команді ІІ потрібно привласнити імена крапкам перетинання прямій MN і окружності . Тут можна домовитися позначати крапки, наприклад, так, щоб вектори і були однонаправлені.

У команді ІІІ потрібно позначити крапки перетинання окружностей і . Домовимося, наприклад, позначати через D ту з двох крапок перетинання, що знаходиться лівіше, якщо дивитися з центра B у напрямку центра C.

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

З обліком сказаного шуканий алгоритм може виглядати в такий спосіб.

Приклад 2.2. Алгоритм проведення перпендикуляра до прямій MN у заданій крапці A ( ).

1. Провести окружність радіуса 1 з центром у крапці A.

2. Позначити крапки перетинання окружності з прямій MN через B і C так, щоб .

3. Послідовно провести окружності і радіуса 2 з центром відповідно в крапках B і C.

4. Позначити крапки перетинання окружностей і через D і E так, щоб обхід багатокутника BDCE (послідовно від B через D і C до E) відбувався по годинній стрілці.

5. Провести пряму DE. Пряма DE – шуканий перпендикуляр.

Рис.2.2. Проведення перпендикуляра до прямої в заданій крапці

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

3. Уточнення поняття алгоритму

Точне математичне визначення поняття “алгоритм” було вироблено лише в тридцятих роках XX століття. Чому ж до цього часу математики задовольнялися інтуїтивним поняттям алгоритму? Це зв’язано з тим, що звичайно поняття алгоритму зустрічалося в зв’язку з конкретним рішенням задачі. Про алгоритм говорили лише тоді, коли пропонувався спосіб рішення якого-небудь класу задач. На початку XX століття в математиці нагромадилася велика кількість задач, що не піддавалися рішенню, незважаючи на те, що над ними думали першокласні вчені. Виникла підозра, що для деяких з цих задач узагалі не існує алгоритму, що дозволяє їх розв’язати. Твердження про нерозв’язність того або іншого класу задач можна було вивести, тільки маючи точне визначення алгоритму, треба було знати, неіснування чого потрібно довести.

Спроби дати строге математичне визначення алгоритму, що погодиться з інтуїтивним представленням про алгоритм, привели до вироблення відразу декількох визначень (Черч, Посада, Тьюринг, Марков і ін.). Згодом з’ясувалося, що всі ці визначення рівносильні між собою і, отже, визначають те саме поняття. Як основу для уточнення поняття алгоритму ми вибираємо так називані машини з необмеженими регістрами, або, коротше, МНР. Виклад на базі МНР привабливо через близькість цих машин до реальних ЕОМ.

Кожний алгоритм має справу з даними – вхідними, проміжними і вихідними. Оскільки ми збираємося уточнювати поняття алгоритму, потрібно уточнити і поняття даних. Як дані для МНР ми обмежуємося безліччю Z0 ненегативних цілих чисел. Таке обмеження не є істотним, оскільки інші види об’єктів і операції над ними можуть бути закодовані натуральними числами і представлені як операції над натуральними числами.

Нижче ми перелічимо всі команди зі списку розпоряджень МНР (для уточнення властивості “зрозумілість”), однозначно визначимо дію кожної команди (для уточнення властивості “визначеність”) і опишемо механізм реалізації алгоритму (для уточнення властивості “точність”).

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

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

У список розпоряджень МНР входить чотири команди: команда обнуління Z(n); команда додатка одиниці S(n); команда переадресації T(m, n) і команда умовного переходу J(m, n, q). Команди обнуління, додатка одиниці і переадресації називаються арифметичними.

команди Дія, вироблена МНР

J(m, n, q) Якщо , то перейти до

обчислення команди алгоритму

Рис. 3.2. Список розпоряджень МНР

Алгоритмом називається кінцева непорожня послідовність команд зі списку розпоряджень МНР, що починається з команди з номером 1.

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

Припустимо, що деякий алгоритм P складається з послідовності команд I1, I2, . Is. МНР починає обчислення з команди I1, потім виконуються команди I2, I3 і т.д. доти, поки не зустрінеться команда виду J(m, n, q). У цьому випадку МНР переходить до виконання команди, запропонованої J(m, n, q) і поточним змістом регістрів Rm і Rn

МНР виконує алгоритм P: I1, I2, . Is доти, поки це можливо. Обчислення зупиняється тоді і тільки тоді, коли немає наступної команди, тобто коли МНР тільки що виконала команду Ik і наступна команда в обчисленні є Iv, де v > s. Це може відбутися одним зі способів:

I) якщо Ik = Is (виконана остання команда в P) і Ik – арифметична команда;

2) якщо Ik = J(m, n, q), Rm = Rn і q > s.

3) якщо Ik = J(m, n, q), Rm Rn і q = s.

У цьому випадку будемо говорити , що обчислення зупинилося після виконання команди Ik, і заключна конфігурації є послідовність r1, r2, r3, . умісти регістрів на цьому кроці .

Результатом застосування алгоритму до деякої початкової конфігурації будемо вважати число r1 з регістра R1 заключної конфігурації.

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

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

Урок інформатики на тему: “Поняття алгоритму. Властивості алгоритмів. Форми подання алгоритмів. Виконавець алгоритму».

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

При проведенні уроку з інформатики для групи кухарів з теми «Поняття алгоритму. Властивості алгоритмів. Форми подання алгоритмів. Виконавець алгоритму» для кращого засвоєння навчального матеріалу та зацікавленості учнями матеріалу я використовувала багато прикладів з технології приготування їжі.

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

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

Наталя Григорівна Чернюх, викладач інформаційних технологій, інформатики, математики

Урок інформатики на тему: “Поняття алгоритму. Властивості алгоритмів. Форми подання алгоритмів. Виконавець алгоритму».

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

При проведенні уроку з інформатики для групи кухарів з теми «Поняття алгоритму. Властивості алгоритмів. Форми подання алгоритмів. Виконавець алгоритму» для кращого засвоєння навчального матеріалу та зацікавленості учнями матеріалу я використовувала багато прикладів з технології приготування їжі.

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

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

Тема : Поняття алгоритму. Властивості алгоритмів. Форми подання алгоритмів. Виконавець алгоритму.

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

розвивальна : розвивати логічне мислення, розумову активність учнів, цілеспрямованість, пам’ять;

виховна : уважність, вміння самостійно приймати рішення.

Тип уроку : засвоєння нових знань, формування вмінь.

Вид уроку : лекція з елементами презентації.

Методи навчання : пояснювально-ілюстративний.

Форми організації : фронтально-групова

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

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

Структура уроку

II . Актуалізація теми уроку……………………………………………………. 3 хв.

III . Мотивація навчальної діяльності……………………………………………3хв.

IV . Засвоєння нових знань………………………………………………………15хв.

1. Алгоритм. Історична довідка.
2. Виконавець алгоритму. Основні характеристики.
3. Властивості алгоритму.
4. Форми подання алгоритму.
5. Основні елементи блок – схем алгоритму.

V . Формування вмінь та навичок…………………………………………………8хв.

Колективне виконання практичного завдання.

VI . Узагальнення та осмислення набутих знань………………………….…….8хв.

Самостійно скласти блок-схему приготування соусів.

VII . Підбиття підсумків уроку……………………………………………………..3хв.

I . Організаційний етап

Оголошення теми та мети уроку, його ролі в темі, курсі інформатики в цілому та в професійній орієнтації.

II . Актуалізація теми уроку

1. Чому потрібно записувати алгоритми?

2. Що таке мови і для чого вони існують?

3.Чи потрібні якісь загальні правила під час запи сування алгоритмів? Чому?

III . Мотивація навчальної діяльності.

Кожен із вас зустрічався з таким поняттям, як алго ритм, у повсякденному житті, хоча навіть не здога дувався про це. Ось декілька прикладів.

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

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

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

Тепер ми можемо сформулювати, що ж таке алго ритм.

IV . Засвоєння нових знань

1. Алгоритм. Історична довідка.

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

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

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

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

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

Виконавець алгоритму – це істота (людина, свійська тварина) або неістота (робот, автомат , комп’ютерна система), яка може виконувати всі вказівки заданого алгоритму.

Основні характеристики виконавця алгоритму:

1. Середовище виконання – умови, в яких може діяти виконавець.
2. Елементарні дії – найпростіші дії, які може виконати виконавець.
3. Система команд виконавця – сукупність допустимих команд виконавця.

Допустимі команди – команди, які зрозумілі виконавцю і можуть бути ним виконані. Недопустимі команди – команди, які не можуть бути виконані виконавцем.

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

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

Усі ми з вами любимо смачні справи, наприклад домашню локшину, чебуреки, а також тістечка з листкового або пісочного тіста. Готуючи ці страви, доводиться докласти чимало зусиль, щоб тісто було тонким. Вдома ми використовуємо звичайну качалку, але в умовах виробництва іі використовувати недоцільно. Щоб розкачати пласт тіста, на підприємствах харчування використовують машину для розкачування тіста МРТ-60М. Виконавцем даного процесу можете бути кухар або тісторозкачувальна машина, яка призначена для розкачування крутого дріжджового, листкового і пісочного тіста.

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

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

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

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

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

Наприклад, вам потрібно приготувати яйця. «Мішечок», рідкі та круті. Ви маєте одну сировина, один спосіб теплової обробки, але різний результат в залежності від часу варіння. Яйця «мішечок» готуються – 4-5 хв; рідкі – 2 -3хв.; круті – 7-8 хв.

Зрозумілий алгоритм все ж таки не повинен містити вказівки, зміст яких може сприйматися неоднознач не. Наприклад, вказівки «почисти картоплю», «по соли за смаком», «взяти 2-3 ложки цукру», «трохи підігрій молоко», «прибери в квартирі» є неоднознач ними, тому що в різних випадках можуть призвести до різних результатів. Не випадкову для приготування страви за рецептом вказується конкретна маса продуктів, що використовуються.

Наприклад: рецепт сирників: 250 г сиру домашнього; 1 велике яйце; 2 ст. л. цукру; 1 ч. л. ванільного цукру; 2 ст. л. з гіркою борошна.

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

Дискретність алгоритму означає, що його виконання зводиться до виконання окремих дій (кроків) у певній послідовності.

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

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

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

Наприклад випікання смаколиків виробів кондитерським цехом.

Однак поряд з масовими алгоритмами складаються і застосовуються немасові алгоритми. Наприклад, алгоритм приготування конкретного салату (наприклад, грецького) на конкретну кількість осіб.

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

Картопляне пюре протирання в гарячому стані, щоб воно було пишне та однорідне. Або випікання коржів торта «Наполеон» в духовці при температурі 220 о С.

Скінченність алгоритму означає, що його виконання виконавець закінчить після скінченної (можливо, досить великої) кількості кроків і за скінчений час при будь-яких допустимих значеннях початкових даних. Продовжимо наш приклад: випікання коржів торта «Наполеон» при температурі 220 о С за 7-8 хв.

4. Форми подання алгоритму

Перший спосіб — словесний (кулінарні рецепти, правила).

Подання алгоритмів виконавцю за допомогою сло ­ весного опису.

Приклад №1. Любий кулінарний рецепт.

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

Приклад №1. Приготування бутерброду з маслом та сиром.

Приклад №2. Правила роботи учнів в комп’ютерному класі.

Приклад №3. А лгоритмів, що записані у вигляді умовних позначок на купленому товарі, щодо його користу вання (заварювання чаю, приготування різних страв, використовуючи інструкцію на упаковці товару, прання білизни тощо).

Приклад №4. У математиці наявність формул дозволяє розв’язати задачу навіть «не використовуючи слів».

Третій спосіб — графічний ( запис за допомогою блок-схеми).

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

Основні елементи блок – схем алгоритму.

Четвертий спосіб — навчальні алгоритмічні мови (псевдокоди).

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

П’ятий спосіб максимально наближений до комп’ ютера — це мови програмування.

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

Інші способи – специфічні способи подання алгоритмів, такі, як запис музики за допомогою нот.

Існують чотири базові структури алгоритмів: лінійні; розгалужені; циклічні;

V . Формування вмінь та навичок.

1. Виконання практичного завдання. На прикладі приготування вареників (1,стр.115) з групою закріплює набуті знання та пояснює як правильно складати алгоритм, використовуючи базові структури алгоритмів.

Приклад №1. Приготування вареників

1.Зачитуємо рецепт з підручника.

Питання. Який спосіб описання даного алгоритму? (С ловесний )

2.Розглядаємо таблицю технологічного приготування вареників.

Питання. Який спосіб описання даного алгоритму? (Словесно-формульний )

3.Запишемо даний алгоритм в вигляді блок-схеми. (Додаток 1)

Питання. Який спосіб описання даного алгоритму? (Графічний)

VI . Узагальнення та осмислення набутих знань.

На уроках теоретичного навчання ви вивчаєте тему «Приготування соусів».

З лабораторного практикуму з предмету «Технологія приготування їжі» самостійно скласти алгоритм приготування соусу в вигляді блок-схеми. (1, стр 65) з наступним оцінюванням:

1.Заправка для салатів – 2 бали.

4.Соус білий основний -5 балів.

VII . Підбиття підсумків уроку

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

Контрольні питання до теми:

1.Щотаке алгоритм? Наведіть приклади алгоритмів з вашої професії.

2. Перелічіть основні властивості алгоритмів.

3. Перелічіть способи подання алгоритмів.

4. Що таке блок-схема алгоритму?

5. Які блоки використовуються при складанні блок-схем?

VIII . Домашнє завдання

Опрацювати конспект уроку.

VIIII . Рефлексія

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

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

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

Що таке складність алгоритму?Інтуїтивно можна виділити такі основні складові складності алгоритму:1. Логічна складність — кількість людино-місяців, витрачених на створення алгоритму.2. Статична складність — довжина опису алгоритмів (кількість операторів).3. Часова складність — час виконання алгоритму.4. Ємнісна складність — кількість умовних одиниць пам’яті, необхідних для роботи алгоритму.

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

Оцінка складностіСкладність алгоритмів зазвичай оцінюють за часом виконання або по використовуваній пам’яті. В обох випадках складність залежить від розмірів вхідних даних: масив з 100 елементів буде оброблений швидше, ніж аналогічний з 1000. При цьому мова йде не про точний час обчислень, який залежить від процесора, типу даних, мови програмування тощо. Оцінюється складність при прагненні розміру вхідних даних до нескінченності.

Складність алгоритму. Часова складність алгори́тму — характеристика продуктивності алгоритму, що визначається кількістю елементарних операцій, які потрібно виконати для реалізації алгоритму. При цьому вважають, що кожна елементарна операція виконується за однаковий час. Часову складність оцінюють для найгіршого випадку і визначають як максимальний час, необхідний для обробки алгоритмом будь-якої множини з n елементів. Часова складність алгоритму зазвичай визначається виразом O (f (n)) (або так званої О—нотації). Вираз O(f(n)) означає, що час виконання алгоритму зростає з тією ж швидкістю, що і функція f (n).

Поширені складності алгоритмів• Якщо час роботи алгоритму не залежить від обсягу вхідних даних, то його часову складність позначають як O(1); приклад — визначення значення третього елемента масиву, для чого не потрібно ні запам’ятовувати елементи, ні проходити по ним декілька разів. Завжди потрібно просто дочекатися в потоці вхідних даних третій елемент і це буде результатом, на обчислення якого для будь—якої кількості даних потрібний один і той же час.• Лінійна складність O (n): подвоєння розміру задачі подвоїть і необхідний час; приклади — алгоритм пошуку найбільшого елемента в невідсортованому масиві, для чого потрібно переглянути всі n елементів масиву; алгоритм додавання/віднімання чисел з n цифр.

Поширені складності алгоритму• Квадратична складність O ( n2 ): час роботи алгоритму зростає пропорційно квадрату кількості оброблюваних елементів, подвоєння розміру задачі вчетверо збільшує необхідний час; приклад — алгоритм сортування бульбашкою, що виконує два вкладені цикли перебору масиву.• Кубічна складність O ( n3 ): подвоєння розміру задачі збільшує необхідний час у вісім разів. Припустимо, певним алгоритмом потрібно виконати 4n3+7n умовних операцій, щоб обробити n елементів вхідних даних. При збільшенні n на час роботи буде значно більше впливати зведення n в куб, ніж множення його на 4 або ж додавання 7n.

Приклад: Нехай дана послідовність з нулів та одиниць і нам потрібно з’ясувати, чи є там хоч одна одиниця. Яку складність матиме алгоритм розв’язання цієї задачі?Розв’язання. Нехай n – кількість символів в послідовності. Алгоритм буде послідовно перевіряти, чи немає одиниці в поточному місці заданої послідовності, а потім рухатися далі, поки вхід не скінчиться. Оскільки одиниця дійсно може бути тільки одна, для отримання точної відповіді на це питання в гіршому випадку доведеться перевірити всі n символів входу. Таким чином, алгоритм має складність O (n), іншими словами, він лінійний.

Приклад: Розглянемо код, який для масиву A[n, n] знаходить максимальний елемент у кожному рядку. for i:=1 to N do begin max:=A[i,1]; for j:=1 to N do if A[i,j]>max then max:=A[i,j] writeln(max); end;У цьому алгоритмі змінна і змінюється від 1 до n. При кожній зміні і, змінна j теж змінюється від 1 до n. Під час кожної з n ітерацій зовнішнього циклу, внутрішній цикл теж виконується n раз. Загальна кількість ітерацій внутрішнього циклу дорівнює n* n. Це визначає складність алгоритму O( n2 ).