Понятие алгоритма. Свойства алгоритма. Способы записи алгоритма. Понятие сложности алгоритма
план-конспект занятия

Тема — Понятие алгоритма. Свойства алгоритма. Способы записи алгоритма. Понятие сложности алгоритма

Теоретический материал для самостоятельного изучения

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

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

Алгоритм — это точная конечная система предписаний, определяющая содержание и порядок действий исполнителя над некоторыми объектами для получения искомого результата.

Исполнитель алгоритма — это субъект или устройство, способные правильно интерпретировать описание алгоритма и выполнить содержащийся в нем перечень действий.

Исполнители бывают неформальными и формальными.

В информатике рассматривают только формальных исполнителей, которые не понимают и не могут понять смысл даваемых команд. К этому типу относятся все технические устройства, в том числе и компьютер.

Свойства алгоритма

1. Дискретность — алгоритм состоит из отдельных команд, каждая из которых выполняется за конечное число шагов.
2. Детерминированность (или определенность) — при каждом запуске алгоритма с одними и теми же исходными данными должен быть получен один и тот же результат.
3. Понятность — алгоритм содержит только те команды, которые входят в систему команд исполнителя, для которого он предназначен.
4. Конечность (или результативность) — для корректного набора данных алгоритм должен завершиться через конечное время с вполне определенным результатом. При этом результатом может быть и сообщение о том, что задача не имеет решений.
5. Массовость — алгоритм предназначен для решения не одной частной задачи, а для некоторого класса задач.

 Алгоритмы можно записывать разными способами:

— на естественном языке;

— графически в виде блок-схем;

— в виде программы на каком-либо языке программирования.

Если задача имеет алгоритмическое решение вообще, то можно придумать множество алгоритмов ее решения. Критерием выбора наилучшего алгоритма является сложность алгоритма — количество элементарных действий, которые выполняет исполнитель при решении задачи, пользуясь данным алгоритмом.

Линейный алгоритм

Пример 1. Составить алгоритм запуска программы Paint в ОС Windows 7.

1. Войти в меню «Пуск».
2. Войти в пункт «Все программы».
3. Войти в пункт «Стандартные».
4. Выбрать программу «Paint».

Данный алгоритм в виде блок-схемы имеет следующий вид:

Пример 2 Вычисление длины гипотенузы с по формуле

1. Начало алгоритма.
2. Ввод значений длин катетов a и b.
3. Вычисление длины гипотенузы с по формуле
4. Вывод значения длины гипотенузы.
5. Конец алгоритма

Разветвленный алгоритм

Пример 1. Составьте алгоритм для перехода дороги на светофоре.

1. Подойти к светофору.
2. Посмотреть на его свет.
3. Если горит зелёный, то перейти дорогу.
4. Если горит красный, то подождать, пока загорится зелёный, и уже тогда перейти дорогу.

Самостоятельная работа «Алгоритмы»

1. Составьте блок-схему для действий Ивана по поиску смерти Кощея Бессмертного. «Смерть моя – на конце иглы, которая в яйце, яйцо – в утке, утка – в зайце, заяц в сундуке сидит, сундук на крепкий замок закрыт и закопан под самым большим дубом на острове Буяне, посреди моря-океяна …»
2. Составить блок-схему для помощи деду в вытаскивании репки. Вспомним сюжет сказки: дед тянет-потянет – вытянуть не может. Затем на помощь к деду по очереди подходят новые персонажи – и так до тех пор, пока не приходит мышка.
3. Придумать задачу для следующих блок-схем

4. Алгоритм представлен блок-схемой.  Выясните, какую задачу решает этот алгоритм. Найдите значение переменной Y при: 1) х = –10;     2) х = 2;    3) х = 10.

5. Найти значения   при  1) х=2, у=2     2) х=-1, у=0    3) х=-0,5, у=1    4) х=10, у=-3

Тема — Понятие алгоритма. Свойства алгоритма. Способы записи алгоритма. Понятие сложности алгоритма

Перечень вопросов, рассматриваемых в теме: алгоритм, свойства алгоритма: дискретность, детерминированность, понятность, результативность, конечность, массовость, исполнитель алгоритма, сложность алгоритма

Глоссарий по теме: алгоритм, исполнитель алгоритма, дискретность, детерминированность, понятность, конечность, массовость, сложность алгоритма.

Основная литература по теме урока:

Л. Л. Босова, А. Ю. Босова. Информатика. Базовый уровень: учебник для 11 класса

— М.: БИНОМ. Лаборатория знаний, 2017

Дополнительная литература по теме урока:

К. Ю. Поляков, Е. А. Еремин. Информатика углубленный уровень: учебник для 10 класса: часть 2 — М.: БИНОМ. Лаборатория знаний, 2013

И. Г. Семакин, Т. Ю. Шеина, Л. В. Шестакова Информатика и ИКТ. Профильный уровень: учебник для 10 класса — М.: БИНОМ. Лаборатория знаний, 2010

Теоретический материал для самостоятельного изучения

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

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

Алгоритм — это точная конечная система предписаний, определяющая содержание и порядок действий исполнителя над некоторыми объектами для получения искомого результата.

Исполнитель алгоритма — это субъект или устройство, способные правильно интерпретировать описание алгоритма и выполнить содержащийся в нем перечень действий.

Исполнители бывают неформальными и формальными. СЛ 3

В информатике рассматривают только формальных исполнителей, которые не понимают и не могут понять смысл даваемых команд. К этому типу относятся все технические устройства, в том числе и компьютер.

Рассмотрим примеры

СЛ 4-7

СЛ 8 Свойства алгоритма

1. Дискретность — алгоритм состоит из отдельных команд, каждая из которых выполняется за конечное число шагов.
2. Детерминированность (или определенность) — при каждом запуске алгоритма с одними и теми же исходными данными должен быть получен один и тот же результат.
3. Понятность — алгоритм содержит только те команды, которые входят в систему команд исполнителя, для которого он предназначен.
4. Конечность (или результативность) — для корректного набора данных алгоритм должен завершиться через конечное время с вполне определенным результатом. При этом результатом может быть и сообщение о том, что задача не имеет решений.
5. Массовость — алгоритм предназначен для решения не одной частной задачи, а для некоторого класса задач.

СЛ 9 Давайте обсудим

 Алгоритмы можно записывать разными способами:

— на естественном языке;

 СЛ 10— графически в виде блок-схем;

— в виде программы на каком-либо языке программирования.

СЛ 11 Если задача имеет алгоритмическое решение вообще, то можно придумать множество алгоритмов ее решения. Критерием выбора наилучшего алгоритма является сложность алгоритма — количество элементарных действий, которые выполняет исполнитель при решении задачи, пользуясь данным алгоритмом.

Задания

Самостоятельная работа «Алгоритмы»

6. Составьте блок-схему для действий Ивана по поиску смерти Кощея Бессмертного. «Смерть моя – на конце иглы, которая в яйце, яйцо – в утке, утка – в зайце, заяц в сундуке сидит, сундук на крепкий замок закрыт и закопан под самым большим дубом на острове Буяне, посреди моря-океяна …»
7. Составить блок-схему для помощи деду в вытаскивании репки. Вспомним сюжет сказки: дед тянет-потянет – вытянуть не может. Затем на помощь к деду по очереди подходят новые персонажи – и так до тех пор, пока не приходит мышка.
8. Придумать задачу для следующих блок-схем

Пример

Дан фрагмент блок-схемы алгоритма. Найдите значения переменных a и c после его выполнения, заполнив трассировочную таблицу.

9. Алгоритм представлен блок- схемой.  Выясните, какую задачу решает этот алгоритм. Найдите значение переменной Y при:

 1) х = –10;     2) х = 2;    3) х = 10.

10. Найти значения   при  

1) х=2, у=2     2) х=-1, у=0    3) х=-0,5, у=1    4) х=10, у=-3

11. У исполнителя Калькулятор две команды, которым присвоены номера:

1.  прибавь 2                 2.  умножь на 3

Выполняя первую из них, Калькулятор прибавляет к числу на экране 2, а выполняя вторую, утраивает его.

1. Запишите все возможные программы для этого исполнителя, состоящие ровно из трех команд.
2.  Запишите порядок команд в программе получения из 0 числа 28, содержащей не более 6 команд, указывая лишь номера команд.

12. У исполнителя Калькулятор две команды, которым присвоены номера:

1.  прибавь 2                 2.  умножь на 3

Выполняя первую из них, Калькулятор прибавляет к числу на экране 2, а выполняя вторую, утраивает его. Запишите порядок команд в программе получения из 2  числа 42, содержащей ровно 4 команды

13. Петя и Вера играют. Петя пишет «слово» – произвольный набор букв русского алфавита. Вера заменяет в этом «слове» каждую букву на другую букву так, чтобы выполнялись следующие правила:

1) гласная буква меняется на согласную, согласная – на гласную;

2) в получившемся «слове буквы следуют в алфавитном порядке.

Пример. Петя написал: ЖЕНЯ. Вера может написать ЕНОТ или АБУЧ, но не может написать МАМА или ИВАН. Алфавит (для справки):

АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ.

Петя написал: КОТ. Укажите, из следующих «слов» может написать Вера. Почему она какое может написать другие из следующих «слов». Дайте краткое обоснование.

1) ЭЛЬ                 2) ЕНОТ              3) АНЯ                 4) ЭЛЯ

9. Определите значение целочисленных переменных  после выполнения фрагмента программы: