Краткое содержание: Параграф § 5 / Информатика 11 класс

Определение и свойства алгоритма

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

Алгоритм обладает рядом фундаментальных свойств:

• Дискретность: Выполнение алгоритма разбивается на отдельные, законченные действия (шаги). Переход к следующему шагу возможен только после полного завершения предыдущего.
• Детерминированность (определенность): Каждая команда алгоритма точно определяет следующее действие исполнителя, исключая двусмысленность. Повторное применение алгоритма к одним и тем же исходным данным должно приводить к одинаковым промежуточным и конечным результатам.
• Понятность: Запись алгоритма должна быть настолько четкой и полной, чтобы исключить потребность в принятии самостоятельных решений исполнителем.
• Результативность: Алгоритм должен привести к конечному результату за конечное число шагов.
• Массовость: Алгоритм должен быть пригоден для решения целого класса задач, то есть он должен быть применим к различным исходным данным, в пределах установленного диапазона.

Способы описания и примеры алгоритмов

Для записи алгоритмов используются различные способы:

• Словесная запись на естественном языке.
• Запись на частично формализованном естественном языке с элементами языка программирования или общепринятыми математическими обозначениями.
• Запись в виде блок-схем – графическое представление логической структуры программы с использованием стандартных символов (таблица 2.1 на стр. 70, 71).
• Запись на языке программирования.

В качестве примеров рассматриваются:

• Алгоритм нахождения простых чисел, известный как «Решето Эратосфена».
• Блок-схема алгоритма игры «Угадай-ка», демонстрирующая метод половинного деления (рис. 2.3 на стр. 71).

Сложность алгоритмов

Сложность алгоритма – это количество элементарных шагов (действий) в вычислительном процессе. Эффективность алгоритма оценивается по количеству элементарных операций, требуемых для решения задачи, а также по объему памяти. Более эффективным считается алгоритм, имеющий наименьшую сложность.

• Алгоритмы с линейной сложностью имеют сложность \(O(n)\), где \(n\) – объем входных данных.
• Существуют также алгоритмы с квадратичной, кубической и другими видами сложности.

Рассматривается алгоритм быстрого возведения в степень натурального числа \(x\) в степень \(n\), который основан на двоичном представлении показателя \(n\). Например, для \(n=100\), его двоичное представление: \(100_{10} = 1100100_2\). Этот метод требует значительно меньше операций умножения, чем прямое перемножение \(x\) \(n\) раз.