5. Технология проектирования алгоритмов «сверху вниз». Принципы документирования (самодокументирования) программного кода (с помощью соответствующих комментариев к тексту программы). Примеры.

Существуют различные методы разработки алгоритмов (и программ), но наиболее важным является метод пошаговой детализации (или метод разработки « сверху - вниз »). При этом методе первоначально продумывается и фиксируется множество данных и результатов алгоритма без детальной проработки отдельных частей. Задачу разбивают на автономные части, каждая из которых существенно проще. Может оказаться необходимым повторять процесс детализации многократно, но это определяется только сложностью решаемых задач. Конечным уровнем детализации алгоритма можно считать такой, при котором в алгоритме нет действий более крупных, чем: обращение к готовому алгоритму; вычисление арифметического выражения и присваивание значения переменной; сравнение арифметических выражений (или переменных); ввод (вывод) данных и т.п.

• Принципы документирования

Перед комментарием ставится знак «%». Комментарии следует писать в начале функции, а так же, в случае надобности, среди кода для пояснения того, что делает код.

• Пример:

function a=findmin(x)

%Исходно: массив чисел

%Результат: минимум среди элементов с четными индексами

a=x(2);

l=length(x)

for i=2:2:l

if a>x(i)

a=x(i);

end

end

6. Метод рекуррентных соотношений для проектирования алгоритмов. Примеры.

• Метод рекуррентных соотношений для проектирования алгоритмов

Рассмотрим числовую последовательность a1 a2 … ak. Говорят, что последовательность задана рекуррентным соотношением, если задана функция f(x) такая, что для любого k a(k)=f(a(k+1)), и задано значение некоторого члена этой последовательности(например, а1).

Альтернативный способ задания последовательности - это задать выражение общего вида k-го члена последовательности.

• Пример:

Последовательность четных чисел

2 4 6 8 10 …

a1 a2 a3 a4 a5 …

a(k)=2*k

или

a(k+1)=a(k)+2

a1=2

7. Прямая и косвенная рекурсия. Использование рекурсии для записи алгоритмов. Примеры.

• Рекурсия

Рекурсия – это такой способ организации вычислительного процесса, при котором программа в ходе выполнения составляющих её операторов обращается сама к себе.

Прямая рекурсия - непосредственный вызов алгоритма (функции, процедуры) F из текста самого алгоритма F.

Под косвенной рекурсией понимают явление, когда рекурсивные функции вызывают друг друга (например, функция А вызывает B, а функция B вызывает A).

• Пример рекурсии

function res=factor(n) %исходно:-x число которое надо возвести в факториал %результат res-ответ res=n if n>1 res=res*factor(n-1) end

8. Причина возможной катастрофической неэффективности рекурсивных алгоритмов (можно на примере вычисления последовательности Фибоначчи)

ПОСЛЕДОВАТЕЛЬНОСТЬ ФИБОНАЧЧИ - математическая ПОСЛЕДОВАТЕЛЬНОСТЬ, каждый член которой является суммой двух предыдущих. Неэффективность заключается в том что, при зацикливании, или выполнении большого объема задач выделяется большой объём памяти, если происходит зацикливание, то выделяемый объем стремится к бесконечности

9. Инвариант цикла. Использование инварианта цикла для доказательства правильности алгоритмов и для их вывода (на примере вычисления суммы элементов конечной числовой последовательности, максимального значения конечной числовой последовательности, алгоритма Евклида для вычисления НОД).

Инвариант цикла - выражение, значение которого не меняется при каждом прохождении цикла. Инвариант цикла - это свойство ситуации или объекта, с которыми имеет дело алгоритм, такое, которое не меняется при исполнении тела цикла. Инвариант цикла — это условие, которое должно выполняться до и после каждого выполнения цикла, являющегося частью алгоритма.(на мой взгляд самое верное) пример алгоритма Евклида для вычисления НОД условие до начала цикла a>0 и b>0, a~=b условие после цикла

1) a=b

Или

2) a~=b

это и есть инвариант цикла на примере алгоритма Эвклида.

нод=наибольшее общее кратное

10. Проектирование однопроходных алгоритмов (на примерах подсчёта числа элементов массива, имеющих максимальное значение, вычисления средне-квадратического отклонения заданной числовой последовательности)

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

• Понятие временной сложности алгоритма, асимптотические оценки временной сложности сверху, использование символики О-большое

• 1/16

http://habrahabr.ru/blogs/algorithm/78728/

• Алгоритм быстрого возведения в степень

function res=e11_2(t,k) %возведение числа t в степень k

res=1;

while k>0

if mod(k,2)==1

res=res*t

end

t = t*t;

k = fix(k/2); %целая часть от деления

end

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

• Понятие временной сложности алгоритма, асимптотические оценки временной сложности сверху, использование символики О-большое

http://habrahabr.ru/blogs/algorithm/78728/

• 1/15.jpg