Информатика, 11 класс.
Урок № 7.
Тема — Понятие алгоритма.
Свойства алгоритма. Способы записи алгоритма. Понятие сложности алгоритма
Перечень вопросов,
рассматриваемых в теме: алгоритм, свойства алгоритма:
дискретность, детерминированность, понятность, результативность, конечность,
массовость, исполнитель алгоритма, сложность алгоритма
Глоссарий по теме: алгоритм,
исполнитель алгоритма, дискретность, детерминированность, понятность,
конечность, массовость, сложность алгоритма.
Основная литература по теме
урока:
Л.
Л. Босова, А. Ю. Босова.
Информатика. Базовый уровень: учебник для 11 класса
—
М.: БИНОМ. Лаборатория знаний, 2017
Дополнительная литература по теме
урока:
К.
Ю. Поляков, Е. А. Еремин. Информатика углубленный уровень: учебник для 10
класса: часть 2 — М.: БИНОМ. Лаборатория знаний, 2013
И.
Г. Семакин, Т. Ю. Шеина, Л. В. Шестакова Информатика и ИКТ. Профильный уровень:
учебник для 10 класса — М.: БИНОМ. Лаборатория знаний, 2010
Теоретический материал для
самостоятельного изучения
На
протяжении всей жизни, в учебе, на работе или в быту человек сталкивается с
необходимостью решения огромного количества задач.
Для
решения любой задачи надо знать, что дано и что следует получить. Для получения
результатов необходимо знать способ решения задачи, т. е. располагать
алгоритмом.
Алгоритм
— это точная конечная система предписаний, определяющая содержание и порядок
действий исполнителя над некоторыми объектами для получения искомого результата.
Исполнитель
алгоритма — это субъект или устройство, способные правильно интерпретировать
описание алгоритма и выполнить содержащийся в нем перечень действий.
Исполнители
бывают неформальными и формальными.
В
информатике рассматривают только формальных исполнителей, которые не понимают и
не могут понять смысл даваемых команд. К этому типу относятся все технические
устройства, в том числе и компьютер.
Свойства алгоритма
Дискретность —
алгоритм состоит из отдельных команд, каждая из которых выполняется за конечное
число шагов.
Детерминированность (или определенность) — при каждом запуске
алгоритма с одними и теми же исходными данными должен быть получен один и тот
же результат.
Понятность —
алгоритм содержит только те команды, которые входят в систему команд
исполнителя, для которого он предназначен.
Конечность (или результативность) — для корректного набора
данных алгоритм должен завершиться через конечное время с вполне определенным
результатом. При этом результатом может быть и сообщение о том, что задача не
имеет решений.
Массовость —
алгоритм предназначен для решения не одной частной задачи, а для некоторого
класса задач.
Способы записи алгоритмов
Алгоритмы
можно записывать разными способами:
—
на естественном языке;
—
графически в виде блок-схем;
—
в виде программы на каком-либо языке программирования.
Если
задача имеет алгоритмическое решение вообще, то можно придумать множество
алгоритмов ее решения. Критерием выбора наилучшего алгоритма является сложность алгоритма — количество
элементарных действий, которые выполняет исполнитель при решении задачи,
пользуясь данным алгоритмом.
Сложность
алгоритма принято обозначать O(n) (читается «О большое от
эн»).
Сложность
алгоритма выражают в виде функции от объема входных данных.
Лучшим
считается алгоритм, имеющий наименьшую сложность.