Категории:
ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника
Свойства алгоритмов. Формы представления алгоритмов.
Алгоритм –точный набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное время. В старой трактовке вместо слова «порядок» использовалось слово «последовательность».
Свойства алгоритма:
- Дискретность - алгоритм должен представлять процесс решения задачи как последовательное выполнение некоторых простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, то есть преобразование исходных данных в результат осуществляется во времени дискретно.
- Детерминированность (определённость). В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных.
- Понятность - алгоритм для исполнителя должен включать только те команды, которые ему (исполнителю) доступны, которые входят в его систему команд.
- Завершаемость (конечность) - при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. С другой стороны, вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0.
- Массовость (универсальность). Алгоритм должен быть применим к разным наборам исходных данных.
- Результативность - завершение алгоритма определёнными результатами.
Алгоритм содержит ошибки, если приводит к получению неправильных результатов либо не даёт результатов вовсе.
Алгоритм не содержит ошибок, если он даёт правильные результаты для любых допустимых исходных данных.
Способы представления алгоритмов:
1.Алгоритм представленный на естественном языке. Алгоритм-инструкция. Такая форма представления понятно описывает действия, которые нужно выполнить.
2.Блок-схемы (графическое), когда действия или группы действий записываются в специальных фигурах (овал, параллелограмм и тд). Такая форма хороша для визуального восприятия последовательности действий.
3.Табличная – часто используется на уроках физики. И она хороша в случаях когда необходимо проверить результат.
4. Формульный
Дана строка; слова разделены пробелами. Подсчитать, сколько в ней букв 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) на отрезке [x0;x1] получаем интеграл:
(26)
Формула (26) даёт один из простейших способов вычисления определённого интеграла и называется формулой трапеций. Действительно, при n=1 подынтегральная функция заменяется интерполяционным многочленом Лагранжа первой степени (т.е. линейной функцией), а это означает геометрически, что площадь криволинейной фигуры подменяется площадью трапеции.
Распространяя формулу (26) на все отрезки разбиения, получим общую формулу трапеций для отрезка [a;b]
(27)
Если аналитическое выражение подынтегральной функции может быть поставлен вопрос об оценке погрешности численного интегрирования по формуле (27) (погрешность метода). В этом случае имеется в виду, что
где Rn(f) - остаточный член квадратурной формулы (27). Формулу остаточного члена получим вначале для отрезка [x0;x1]. Имеем:
откуда следует, что естественно рассматривать 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?[x0; x0+h] и ζi зависит от h. Далее
откуда с учётом (30) и обобщённой теоремы о среднем имеем:
(31)
где ζ?[x0; x0+h].
Таким образом, погрешность метода при интегрировании функции f на отрезке [x0;x1] по формуле (27) имеет величину:
(32)
Из формулы (32) видно, что при f’’(ζ)>0 формула (27) даёт значение интеграла с избытком, а при f’’(ζ)<0 - с недостатком.
При распространении оценки (32) на весь отрезок интегрирования [a;b] (т.е. на все n частичных отрезков) получается формула:
Учитывая, что h*n=b-a, найден следующий окончательный вид формулы для оценки погрешности метода интегрирования по формуле трапеций:
где
Последнее изменение этой страницы: 2016-08-11
lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...