2. Свойства алгоритмов. Формы представления алгоритмов.

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

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

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

- Детерминированность (определённость). В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных.

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

- Завершаемость (конечность) - при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. С другой стороны, вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0.

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

- Результативность - завершение алгоритма определёнными результатами.

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

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

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

1.Алгоритм представленный на естественном языке. Алгоритм-инструкция. Такая форма представления понятно описывает действия, которые нужно выполнить.

2.Блок-схемы (графическое), когда действия или группы действий записываются в специальных фигурах (овал, параллелограмм и тд). Такая форма хороша для визуального восприятия последовательности действий.

3.Табличная – часто используется на уроках физики. И она хороша в случаях когда необходимо проверить результат.

4. Формульный

3. Дана строка; слова разделены пробелами. Подсчитать, сколько в ней букв r, k, t.

program lab35;

var s:string;

n,i:integer;

begin

writeln('Vvedite stroku');

readln(s);

n:=0;

for i:=1 to length(s) do

if (s[i]='r') or (s[i]='k') or (s[i]='t') then

n:=n+1;

writeln('V stroke naydeni bukvi r, k, t : ', n, ' raz');

end.

Билет №21

1.Метод трапеций для численного нахождения определенного интеграла: вывод формулы, оценка погрешности, геометрический смысл.

Метод трапеций.

При n=1 из формулы

(24) имеем (i=0;1):

Тогда по формуле (25) на отрезке [x₀;x₁] получаем интеграл:

(26)

Формула (26) даёт один из простейших способов вычисления определённого интеграла и называется формулой трапеций. Действительно, при n=1 подынтегральная функция заменяется интерполяционным многочленом Лагранжа первой степени (т.е. линейной функцией), а это означает геометрически, что площадь криволинейной фигуры подменяется площадью трапеции.

Распространяя формулу (26) на все отрезки разбиения, получим общую формулу трапеций для отрезка [a;b]

(27)

Если аналитическое выражение подынтегральной функции может быть поставлен вопрос об оценке погрешности численного интегрирования по формуле (27) (погрешность метода). В этом случае имеется в виду, что

где R_n(f) - остаточный член квадратурной формулы (27). Формулу остаточного члена получим вначале для отрезка [x₀;x₁]. Имеем:

откуда следует, что естественно рассматривать R как функцию шага h:R=R(h). Заметим, что R(0)=0.

Продифференцируем R(h) по h:

Заметим, что R'(0)=0. Далее:

(28)

Определим R, последовательно интегрируя R"(h) на отрезке [0;h]:

откуда с учётом (28) имеем:

(29)

Применяя к (29) обобщённую теорему о среднем, получаем:

(30)

где ζ_i€[x₀; x₀+h] и ζ_i зависит от h. Далее

откуда с учётом (30) и обобщённой теоремы о среднем имеем:

(31)

где ζ€[x₀; x₀+h].

Таким образом, погрешность метода при интегрировании функции f на отрезке [x₀;x₁] по формуле (27) имеет величину:

(32)

Из формулы (32) видно, что при f’’(ζ)>0 формула (27) даёт значение интеграла с избытком, а при f’’(ζ)<0 - с недостатком.

При распространении оценки (32) на весь отрезок интегрирования [a;b] (т.е. на все n частичных отрезков) получается формула:

Учитывая, что h*n=b-a, найден следующий окончательный вид формулы для оценки погрешности метода интегрирования по формуле трапеций:

где