Тема 7: Алгоритмы и элементы программирования.

 

Тема 7: Алгоритмы и элементы программирования.

 

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

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

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

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

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

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

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

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

Дискретность — алгоритм состоит из отдельных команд, каждая из которых выполняется за конечное число шагов.

Детерминированность (или определенность) — при каждом запуске алгоритма с одними и теми же исходными данными должен быть получен один и тот же результат.

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

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

Массовость — алгоритм предназначен для решения не одной частной задачи, а для некоторого класса задач.

Способы записи алгоритмов

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

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

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

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

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

Сложность алгоритма принято обозначать O(n) (читается «О большое от эн»).

Сложность алгоритма выражают в виде функции от объема входных данных.

Лучшим считается алгоритм, имеющий наименьшую сложность.

 

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

Самой простой структурой является «следование».

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

Алгоритм, основанный на конструкции «следование» называется линейным алгоритмом. Примером такого алгоритма может служить алгоритм вычисления дискриминанта квадратного уравнения, блок-схема которого приведена на рисунке 1.

Рис. 1

Следующей конструкцией является «ветвление». Она встречается, если действия алгоритма зависят от некоторого условия.

Алгоритм реализован через алгоритмическую конструкцию «ветвление», если от входных данных зависит, какие команды будут выполняться. Условие, которое выражает эту зависимость, фактически является вопросом, на который можно ответить либо «да», либо «нет».

Существуют полная и неполная формы ветвления.

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

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

Алгоритм, основанный на конструкции «ветвление» называется разветвляющимся алгоритмом. Примером такого алгоритма может служить алгоритм нахождения корней квадратного уравнения, блок-схема которого приведена на рисунке 2.

Рис. 2

И, наконец, последняя алгоритмическая конструкция — «повторение».

Алгоритм реализован с использованием алгоритмической конструкции «повторение», если некая группа подряд идущих шагов алгоритма (она называется телом цикла) может выполняться многократно в зависимости от входных данных.

Алгоритм, содержащий конструкцию «повторение» называется циклическим алгоритмом.

Существует несколько разновидностей циклических алгоритмов.

Первый — цикл с заданным условием продолжения работы (цикл с предусловием или цикл-пока).

Второй — цикл с заданным условием окончания работы (цикл с постусловием или цикл-до).

И третий — цикл с заданным числом повторений (цикл с параметром).

Доказано, что при решении задач можно ограничиться только одним циклом — циклом с предусловием. Но в ряде случаев цикл с постусловием или цикл с параметром делают решение задачи легче.

Примером решения одной и той же задачи с помощью различных циклов может служить задача возведения некоторого числа a в натуральную степень n.

 

 

 

 

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

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

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