Головна › Навігатори › Виконання алгоритму конкретного виконавця рішення. Інформатика та інформаційні технології. Способи опису алгоритмів

Виконання алгоритму конкретного виконавця рішення. Інформатика та інформаційні технології. Способи опису алгоритмів

Ключові слова:

алгоритм
властивості алгоритму
- дискретність
- зрозумілість
- визначеність
- результативність
- масовість
виконавець

характеристики виконавця
- коло розв'язуваних завдань
- середа
- режим роботи
- система команд
формальне виконання алгоритму

3.1.1. Поняття алгоритму

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

Приклад 1. Завдання «Знайти середнє арифметичне двох чисел» вирішується у три кроки:

задумати два числа;
скласти два задумані числа;
отриману суму поділити на 2.

Приклад 2. Завдання «Внести гроші на рахунок телефону» поділяється на такі кроки:

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

Приклад 3. Етапи розв'язання задачі «Намалювати веселого їжачка» представлені графічно:

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

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

У загальному вигляді схему роботи алгоритму можна подати так (рис. 3.1):

Мал. 3.1.
Загальна схема роботи алгоритму

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

Анімації "Робота з алгоритмом", "Найбільший спільний дільник", "Найменше загальне кратне" (http://school-collection.edu.ru/) допоможуть вам згадати деякі алгоритми, вивчені на уроках російської мови та математики.

Приклад 4. Деякий алгоритм призводить до того, що з одного ланцюжка символів виходить новий ланцюжок таким чином:

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

Ланцюжок, що вийшов таким чином, є результатом роботи алгоритму.

Так, якщо вихідним був ланцюжок А#В, то результатом роботи алгоритму буде ланцюжок #А1В2, а якщо вихідним ланцюжком був АБВ@, то результатом роботи алгоритму буде ланцюжок БА@В2.

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

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

Розрізняють формальних та неформальних виконавців. Формальний виконавець ту саму команду завжди виконує однаково. Неформальний виконавець може виконувати команду по-різному.

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

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

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

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

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

Розглянемо приклади виконавців.

Приклад 5. Виконавець Черепашка переміщається на екрані комп'ютера, залишаючи слід у вигляді лінії. Система команд Черепашки складається з двох команд:

Направо m (де m – ціле число) – викликає зміну напрямку руху Черепашки на m градусів за годинниковою стрілкою.

Запис Повтори k [<Команда1> <Команда2> ... <Командаn>] означає, що послідовність команд у дужках повториться k разів.

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

Повтори 12 [Направо 4 5 Вперед 20 Направо 45]

Приклад 6. Система команд виконавця Обчислювач складається із двох команд, яким присвоєно номери:

Перша їх зменшує число на 1, друга збільшує число 3 разу. При записі алгоритмів для стислості вказуються лише номери команд. Наприклад, алгоритм 21212 означає наступну послідовність команд:

За допомогою цього алгоритму число 1 буде перетворено на 15: ((1-3-1)-3-1)-3 = 15.

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

Під час виконання кожної такої команди Робот переміщається до сусідньої клітини у вказаному напрямку. Якщо ж у цьому напрямку між клітинами стоїть стіна, то робот руйнується. Що станеться з Роботом, якщо він виконає послідовність команд 32323 (тут цифри позначають номери команд), почавши рух із клітини А? Яку послідовність команд слід виконати Роботу, щоб переміститися з клітини А до клітини В, не зруйнувавшись від зустрічі зі стінами?

При розробці алгоритму:

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

Можна сміливо сказати, що алгоритм - модель діяльності виконавця алгоритмів.

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

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

Властивість дискретності означає, що шлях розв'язання задачі поділено окремі кроки (дії). Кожній дії відповідає розпорядження (команда). Тільки виконавши одну команду, виконавець може розпочати виконання наступної команди.

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

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

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

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

Приклад 8. Розглянемо один із методів знаходження всіх простих чисел, що не перевищують n. Цей метод називається «решета Ератосфена», що на ім'я запропонував його давньогрецького вченого Ератосфена.

Для знаходження всіх простих чисел, не більших за задане число n, слідуючи методу Ератосфена, потрібно виконати наступні кроки:

виписати поспіль усі цілі числа від 2 до n (2, 3, 4, ..., n);
укласти в рамку 2 - перше просте число;
викреслити зі списку всі числа, що діляться на останнє знайдене число;
знайти перше невідзначене число (відзначені числа - закреслені числа або числа, ув'язнені в рамку) і укласти його в рамку - це буде просте число;
повторювати кроки 3 і 4 доти, доки залишиться невідзначених чисел.

Більш наочне уявлення про спосіб знаходження звичайних чисел ви можете отримати за допомогою анімації «Решето Ератосфена» (http://school-collection.edu.ru/).

Розглянута послідовність дій є алгоритмом, оскільки вона задовольняє властивостям:

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

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

3.1.4. Можливість автоматизації діяльності людини

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

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

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

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

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

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

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

Найголовніше

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

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

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

Запитання та завдання

Що називають алгоритмом?
Підберіть синоніми до слова "припис".
Наведіть приклади алгоритмів, які ви вивчаєте в школі.
Хто може бути виконавцем алгоритму?
Наведіть приклад формального виконавця. Наведіть приклад, коли людина виступає у ролі формального виконавця.
Які команди мають бути у робота, який виконує функції: а) касира в магазині; б) двірника; в) охоронця?
Від чого залежить коло завдань виконавця «комп'ютер»?
Розгляньте як виконавець текстовий процесор, що є на вашому комп'ютері. Охарактеризуйте коло розв'язуваних цим виконавцем завдань та її середовище.
Що таке команда, система команд виконавця?
Перелічіть основні властивості алгоритму.
До чого може призвести відсутність будь-якої властивості алгоритму? Наведіть приклади.
У чому важливість можливості формального виконання алгоритму?
Послідовність чисел будується за наступним алгоритмом: перші два числа послідовності приймаються рівними 1; кожне наступне число послідовності приймається рівним сумі двох попередніх чисел. Запишіть 10 перших членів цієї послідовності.
Деякий алгоритм отримує з одного ланцюжка символів новий ланцюжок в такий спосіб. Спочатку записується вихідний ланцюжок символів, після нього записується вихідний ланцюжок символів у зворотному порядку, потім записується буква, що йде в російському алфавіті за тією буквою, яка у вихідному ланцюжку стояла на останньому місці. Якщо у вихідному ланцюжку на останньому місці стоїть буква Я, то як наступна буква записується буква А. Ланцюжок, що вийшов, є результатом роботи алгоритму. Наприклад, якщо вихідний ланцюжок символів був ДІМ, то результатом роботи алгоритму буде ланцюжок ДОММОДН. Дано ланцюжок символів КОМ. Скільки букв О буде в ланцюжку символів, який вийде, якщо застосувати алгоритм до цього ланцюжка, а потім ще раз застосувати алгоритм до результату його роботи?
Знайдіть в Інтернеті анімацію кроків алгоритму Ератосфена. За допомогою алгоритму Ератосфена знайдіть усі прості числа, що не перевищують 50.
Що буде результатом виконання Черепашкою (див. приклад 5) алгоритму?
Запишіть алгоритм для виконавця Обчислювач (приклад 6), що містить не більше 5 команд:
Система команд виконавця Конструктор складається з двох команд, яким надано номери:
По першій з них до числа приписується праворуч 2, по другій число ділиться на 2. Як буде перетворено число 8, якщо виконавець виконає алгоритм 22212? Складіть алгоритм у системі команд цього виконавця, яким число 1 буде перетворено на число 16 (в алгоритмі має бути трохи більше 5 команд).
У якій клітині повинен бути виконавець Робот (приклад 7), щоб після виконання алгоритму 3241 до неї і повернутися?

| § 2.1. Алгоритми та виконавці

Урок 14
§ 2.1. Алгоритми та виконавці

Ключові слова:

Алгоритм
властивості алгоритму (дискретність; зрозумілість; певність; результативність; масовість)
виконавець
характеристики виконавця (коло розв'язуваних завдань; середовище; режим роботи; система команд)
формальне виконання алгоритму

2.1.1. Поняття алгоритму

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

приклад 1.Завдання «Знайти середнє арифметичне двох чисел» вирішується у три кроки:

1) замислити два числа;
2) скласти два задумані числа;
3) отриману суму поділити на 2.

приклад 2.Завдання «Внести гроші на рахунок телефону» поділяється на такі кроки:

1) підійти до терміналу оплати платежів;
2) вибрати оператора зв'язку;
3) запровадити номер телефону;
4) перевірити правильність введеного номера;
5) вставити грошову купюру в купюроприймач;
6) дочекатися повідомлення про зарахування грошей на рахунок;
7) одержати чек.

приклад 3.Етапи розв'язання задачі «Намалювати веселого їжачка» представлені графічно:

У загальному вигляді схему роботи алгоритму можна подати так (рис. 2.1).

Мал. 2.1. Загальна схема роботи алгоритму

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

Анімації «Робота з алгоритмом» (193576), «Найбільший спільний дільник» (170363), «Найменше загальне кратне» (170390) допоможуть вам згадати деякі алгоритми, вивчені на уроках російської та математики (http://sc.edu.ru /).

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

1. Обчислюється довжина (у символах) вихідного ланцюжка символів.
2. Якщо довжина вихідного ланцюжка непарна, то до вихідного ланцюжка праворуч приписується цифра 1, інакше ланцюжок не змінюється.
3. Символи попарно змінюються місцями (перший – з другим, третій – з четвертим, п'ятий – з шостим тощо).
4. Праворуч до отриманого ланцюжка приписується цифра 2.

Ланцюжок, що вийшов таким чином, є результатом роботи алгоритму.

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

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

Виконавець - це певний об'єкт (людина, тварина, технічний пристрій), здатний виконувати певний набір команд.

Розрізняють формальних та неформальних виконавців. Формальний виконавець ту саму команду завжди виконує однаково. Неформальний виконавець може виконувати команду по-різному.

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

Розглянемо приклади виконавців.

Приклад 5.Виконавець Черепашка переміщається на екрані комп'ютера, залишаючи слід у вигляді лінії.

Система команд Черепашки складається з наступних команд:

1. Вперед n (де n - ціле число) - викликає пересування Черепашки на п кроків у напрямку руху - у тому напрямі, куди розгорнуті її голова та корпус;
2. Направо m (де m - ціле число) - викликає зміну напрямку руху Черепашки на градусів за годинниковою стрілкою.
Запис Повтори k [<Команда1> <Команда2> ... <Командаn>] означає, що послідовність команд у дужках повториться k разів.

Подумайте, яка постать з'явиться на екрані після виконання Черепашкою наступного алгоритму.
Повтори 12 [Направо 45 Вперед 20 Направо 45]

Приклад 6.Система команд виконавця Обчислювач складається із двох команд, яким присвоєно номери:

1 - відніміть 1
2 - помнож на 3

Помнож на 3
віднімай 1
помнож на 3
віднімай 1
помнож на 3

За допомогою цього алгоритму число 1 буде перетворено на 15:

((1 3 - 1) 3 - 1) 3 = 15.

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

1 - вгору
2 - вниз
3 - праворуч
4 - вліво

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

Що станеться з Роботом, якщо він виконає послідовність команд 32323 (тут цифри позначають номери команд), почавши рух із клітини А? Яку послідовність команд слід виконати Роботу, щоб переміститися з клітини А до клітини В, не зруйнувавшись від зустрічі зі стінами?

При розробці алгоритму:

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

Можна сміливо сказати, що алгоритм - модель діяльності виконавця алгоритмів.

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

Властивість дискретностіозначає, що шлях розв'язання задачі поділено на окремі кроки (дії). Кожній дії відповідає розпорядження (команда). Тільки виконавши одну команду, виконавець може розпочати виконання наступної команди.

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

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

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

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

Приклад 8.Розглянемо один із методів знаходження всіх простих чисел, що не перевищують деяке натуральне число n. Цей метод називається «решета Ератосфена» на ім'я давньогрецького вченого Ератосфена, що запропонував його (III ст. до н. е.).

1) виписати поспіль усі натуральні числа від 2 до n (2, 3, 4, ..., n);
2) укласти в рамку 2 – перше просте число;
3) викреслити зі списку всі числа, що діляться останнє знайдене просте число;
4) знайти перше невідзначене число (відзначені числа - закреслені числа чи числа, ув'язнені у рамку) і укласти їх у рамку - це буде чергове просте число;
5) повторювати кроки 3 і 4 доти, доки залишиться невідзначених чисел.

Наочніше уявлення про метод знаходження простих чисел ви зможете отримати за допомогою розміщеної в Єдиній колекції цифрових освітніх ресурсів анімації «Решето Ератосфена» (180279).

Розглянута послідовність дій є алгоритмом, оскільки вона задовольняє властивостям:

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

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

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

2.1.4. Можливість автоматизації діяльності людини

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

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

1. Якщо число предметів у купці кратно 3, то поступитися ходом противнику, інакше почати гру, взявши 1 або 2 предмети так, щоб залишилася кількість предметів, кратна 3.
2. Своїм черговим ходом щоразу доповнювати кількість предметів, взятих суперником, до 3 (кількість предметів, що залишилися, має бути кратно 3).

1) процес вирішення задачі представляється у вигляді послідовності найпростіших операцій;
2) створюється машина (автоматичний пристрій), здатна виконувати ці операції у послідовності, заданої в алгоритмі;
3) людина звільняється від рутинної діяльності, виконання алгоритму доручається автоматичному устрою.

НАЙГОЛОВНІШЕ

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

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

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

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

Запитання та завдання

1. Ознайомтеся з матеріалами презентації до параграфа, що міститься в електронному додаткудо підручника. Чи доповнює презентація інформацію, що міститься у тексті параграфа? Якими слайдами Ви могли б доповнити презентацію?

2. Що називають алгоритмом?

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

4. Наведіть приклади алгоритмів, які ви вивчаєте в школі.

5. Хто може бути виконавцем алгоритму?

6. Наведіть приклад формального виконавця. Наведіть приклад, коли людина виступає у ролі формального виконавця.

7. Від чого залежить коло завдань виконавця «комп'ютер»?

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

9. Що таке команда, система команд виконавця?

10. Які команди мають бути у робота, який виконує функції:

а) касира у магазині;
б) двірника;
в) охоронця?

11. Перерахуйте основні властивості алгоритму.

12. До чого може призвести відсутність будь-якої властивості алгоритму? Наведіть приклади.

13. У чому важливість можливості формального виконання алгоритму?

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

15. Деякий алгоритм отримує з одного ланцюжка символів новий ланцюжок в такий спосіб. Спочатку записується вихідний ланцюжок символів, після нього записується вихідний ланцюжок символів у зворотному порядку, потім записується буква, що йде в російському алфавіті за тією буквою, яка у вихідному ланцюжку стояла на останньому місці. Якщо у вихідному ланцюжку на останньому місці стоїть буква «Я», то як наступна буква записується буква «А». Ланцюжок, що вийшов, є результатом роботи алгоритму. Наприклад, якщо вихідний ланцюжок символів був «ДІМ», то результатом роботи алгоритму буде ланцюжок «ДОММОДН». Дано ланцюжок символів «КОМ». Скільки літер «О» буде в ланцюжку символів, який вийде, якщо застосувати алгоритм до цього ланцюжка, а потім знову застосувати алгоритм до результату його роботи?

16. Знайдіть у мережі Інтернет анімацію кроків алгоритму Ератосфена. За допомогою алгоритму Ератосфена знайдіть усі прості числа, що не перевищують 50.

17. Що буде результатом виконання Черепашкою (див. приклад 5) алгоритму?

18. Запишіть алгоритм для виконавця Обчислювач (див. приклад 6), що містить не більше 5 команд:

а) одержання з числа 3 числа 16;
б) отримання у складі 1 числа 25.

19. Система команд виконавця Конструктор складається з двох команд, яким надано номери:

1 - приписати 2
2 - розділити на 2

По першій з них до числа приписується праворуч 2, по другій число ділиться на 2. Як буде перетворено число 8, якщо виконавець виконає алгоритм 22212? Складіть алгоритм у системі команд цього виконавця, яким число 1 буде перетворено на число 16 (в алгоритмі має бути трохи більше 5 команд).

20. У якій клітині повинен бути виконавець Робот (приклад 7), щоб після виконання алгоритму 3241 до неї і повернутися?

Вільне програмне забезпечення:

система Кумир - Комплект навчальних світів (завантажити архів програми з сайту) або відвідати сторінку Кумир ((http://www.niisi.ru/kumir/)

Будь ласка, припиніть роботу AdBlock на цьому сайті.

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

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

Рис.1 Скріншот ігрового поля на code.org

Сподіваюся, у вас все вийшло. Тепер на цьому прикладі опишемо кілька основних понять:

виконавець;
система команд виконавця;
алгоритм.

В іграшці ми керуємо червоною пташкою. Завдання кожного етапу: дістатися пташкою до свині. Пташка вміє виконувати певні команди, наприклад: перемістити вперед, повернути ліворуч, повернути праворуч та ін.

Людина, машина або пристрій, які можуть виконувати деякі команди, називається виконавцем . У цій іграшці, очевидно, виконавець – пташка. Набір команд, які розуміє та вміє виконувати виконавець, називають системою команд виконавця.

Послідовність команд, яку має виконати виконавець на вирішення завдання, називається алгоритмом .

Необхідно загострити увагу на кількох моментах.

Виконавець може виконувати лише ті команди, які входять до системи команд.

Це означає, наприклад, що не можна написати виконавцю-пташці: «Іди до свині!». Точніше записати можна, але нічого не станеться, т.к. виконавець таких команд не знає.

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

Виконавець виконує те, що наказує йому алгоритм.

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

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

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

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

Отже, підсумуємо:

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

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

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

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

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

Приклади: порядок дня, порядок приготування страви, інструкція тощо)

Виконавець алгоритму- Це той, хто виконує алгоритм (людина, тварина, машина, комп'ютер).

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

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

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

1.Результативність (кінцевість)- Можливість отримання з вихідних даних результату за кінцеве число кроків. (Наприклад, при виконанні алгоритму додавання 2 чисел повинні отримати суму).

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

3.Детермінованість(визначеність, точність) – кожна команда має однозначно визначати дію виконавця.

4.Зрозумілість– команда має бути записана зрозумілою комп'ютеру мовою.

5.Дискретність- Розбиття алгоритму на окремі команди.

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

1) природною мовою – запис як окремих команд зрозумілою людині мові.

2) Графічний – мовою блок-схем, з допомогою геометричних фігур (овал, прямокутник, паралелограм, ромб).

3) алгоритмічною мовою – мова запису алгоритмів, на навчання програмуванню. Команди записуються російською мовою.

4) Мовою програмування - програма. Мови програмування: Basic, Pascal, Сі, Visual Basic.

Б7.Основні алгоритмічні структури: прямування, розгалуження, цикл; зображення на блок-схемах. Розбиття завдань на підзавдання. Допоміжні алгоритми.

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

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

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

Так виглядає лінійний алгоритм мовою блок схем:

приклад: алгоритм включення комп'ютера:

Увімкнути живлення комп'ютера (натиснути кнопку на мережевому фільтрі).
Увімкнути монітор, принтер.
Натиснути кнопку Power на системному блоці.
Дочекатися завантаження операційної системита появи Робочого столу.
Приступити до роботи.

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

В алгоритмічну структуру « розгалуження» входить умова, Залежно від істинності умови виконується та чи інша послідовність команд (серій).

Умова – це висловлювання, яке може бути істинним чи хибним. В умові два числа, два рядки, два змінні або рядкові вирази порівнюються між собою з використанням операцій порівняння (>,<, =, >=, <=).

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

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

Циклічні алгоритмічні структури бувають двох типів:

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

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

Алгоритм та його властивості.

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

Виконавець алгоритму- це об'єкт чи суб'єкт, керувати яким складено алгоритм.

Система команд виконавця (СКІ) – це вся сукупність команд, які виконавець вміє виконувати.

Властивості алгоритму: зрозумілість, точність, кінцівка.

Зрозумілість:алгоритм складається лише з команд, що входять до СКІ виконавця.

Точність:кожна команда алгоритму керування визначає однозначну дію виконавця.

Кінцівка (або результативність):Виконання алгоритму має призводити до результату за кінцеве число кроків.

Середовище виконавця: обстановка, у якій функціонує виконавець.

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

Повний набір даних:необхідний та достатній набір даних для вирішення поставленої задачі (отримання шуканого результату).

Способи запису алгоритмів.

Найбільшу поширеність набули способи: графічний, словеснийі у вигляді програм для ЕОМ.

Графічний спосібпередбачає використання певних графічних символів – блоків.

Найменування блоку	Позначення блоку	Зміст
Процес		Обробка інформації
Прийняття рішення		Логічний блок перевірки істинності чи хибності деякої умови
Передача даних		Введення чи виведення інформації
Пуск, зупинка		Початок або кінець програми
Модифікація		Організація циклічного процесу - заголовок циклу

Сукупність блоків утворює так звану блок-схему алгоритму.

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

При записі алгоритмів у вигляді програмдля ЕОМ використовуються мови програмування - системи кодування розпоряджень та правила їх використання. Для запису алгоритмів як програм характерна високий рівень формалізації.

Алгоритми роботи із величинами. Основні алгоритмічні структури.

Величина – це окремий інформаційний об'єкт, який має ім'я, значення та тип.

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

Величини бувають постійними та змінними.

Постійна величина (константа)не змінює свого значення під час виконання алгоритму. Константа може позначатись власним значенням (числа 10, 3.5) або символічним ім'ям (число).

Змінна величинаможе змінювати значення під час виконання алгоритму. Змінна завжди позначається символічним ім'ям (X, A, R5 тощо).

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

Вираз- Запис, що визначає послідовність дій над величинами. Вираз може містити константи, змінні, знаки операцій, функції. Приклад:

А+В; 2*X-Y; K + L - sin(Х)

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

ім'я змінної>:=вираз>

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

приклад.Нехай змінна А мала значення 6. Яке значення набуде змінна А після виконання команди: А: = 2 * А - 1?
Рішення.Обчислення виразу 2*А - 1 при А=6 дасть число 11. Значить нове значення змінної А дорівнюватиме 11.

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

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

Приклад: введенняА – введення значення змінної А з клавіатури комп'ютера.

Команда виведення: команда, за якою значення величини відображається на пристрої виведення комп'ютера (наприклад, монітор).

Приклад: висновок X – значення змінної X виводиться екран.

Команда розгалуження- Поділяє алгоритм на два шляхи залежно від деякої умови; потім виконання алгоритму виходить загальне продовження. Розгалуження буває повне і неповне. Опис розгалуження в блок-схемах та Алгоритмічною мовою:

Тут під серією розуміється одна чи кілька послідовних команд; кв – кінець розгалуження.

Команда циклузабезпечує повторне виконання послідовності команд (тіла циклу) за певною умовою.

Цикл із передумовою- цикл, виконання якого повторюється, поки істинна умова циклу:

Цикл із параметром- повторне виконання тіла циклу, поки цілий параметр пробігає безліч всіх значень від початкового (In) до кінцевого (Ik):

приклад.Дано два прості дроби. Скласти алгоритм отримання дробу, що є результатом їхнього поділу.
Рішення.В формі алгебри вирішення завдання виглядає наступним чином:
а/в: з/d = а*d/b*c = m/n
Вихідними даними є чотири цілі величини: а, b, c, d. Результат - два цілих числа m та n.

алгрозподіл дробів
ціла, b, с, d, m, n
поч введенняа, b, с, d
m:=a*d
n:=b*c
висновок "Чисник=", m
висновок "Знаменник=", n
які

Слід звернути увагу, що для виведення тексту (будь-якої символьної послідовності) його слід записати в лапках у команді висновок.

Єфімова О., Морозов Ст, Угрінович Н. Курс комп'ютерної технології з основами інформатики. Навчальний посібникдля старших класів - М: ТОВ "Видавництво АСТ"; АВF, 2000 р.
Задачник-практикум з інформатики. У 2-х томах / Под ред. І.Семакіна, Є.Хеннера. - М: Лабораторія Базових Знань, 2001 р.
Угрінович Н. Інформатика та інформаційні технології. 10-11 клас-М: Лабораторія Базових Знань, АТ "Московські підручники", 2001 р.

Завдання та тести на тему "Алгоритми та виконавці"

Управління виконавцем Чортежник - Алгоритми 6 клас
Уроків: 4 Задань: 9 Тестів: 1
2 Задань: 9 Тестів: 1

Шановний учень!

Знання Теми "Алгоритми та виконавці" необхідне насамперед для подальшого вивчення програмування. Як базу для вивчення програмування вибрано мову програмування QBasic. Ми відмовилися від ідеї включити до нашого курсу Visual Basic або будь-яку іншу мову об'єктно-орієнтованого програмування, оскільки такий підхід поки не отримав широкого застосування в більшості середніх шкіл РФ. Крім того, в основі об'єктно-орієнтованого програмування лежать принципи класичного програмування Dos.

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

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

Популярне в рубриці: