13. Использование метода рекуррентных соотношений для суммирования степенных рядов. Примеры.

Числовым рядом называют сумму из бесконечного числа слагаемых вида a1+a2+a3…, где a1+a2+a3…-некоторая числовая последовательность, элементы которой называют элементами числового ряда n-ой частичной суммой числового ряда называют сумму первых n членов этого ряда Sn=a1+a2+…+an Говорят, что числовой ряд сходится, если существует lim Sn, принадлежащий R ( n стремиться к +бесконечности). Этот предел называют суммой ряда Степенной ряд-ряд, в который, переменная входит в некоторой натуральной степени В качестве примера может послужить второй типовик

14. Использование (построение) графической диаграммы (графа) конечного автомата для записи алгоритма поиска всех местоположений заданной подстроки символов (например, ‘abcd’) в заданной строке символов

• 1/44.jpg

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

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

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

• Вычисление значений многочлена, заданного массивом коэффициентов по схеме Горнера

Занято

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

function result=e16(x,y,act)

%степень: 0,1,2,3,4,5, и т.д.

%x=[1,8,3,1]

%y=[4,11,3]

%act=1 %если = 1 - сложение, иначе - умножение

if length(x)>length(y) %если x и y разной длины, то дополняем нулями короткий, чтобы стали одинаковой длины

aa=length(x)

y(length(y)+1:aa)=0

else

aa=length(y)

x(length(x)+1:aa)=0

end

if act==1 %складываем

result(1:aa)=x(:)+y(:)

else %умножаем

result(1:aa*2)=0

for i=1:aa

for j=1:aa

result(i+j-1)=result(i+j-1)+x(i)*y(j)

end

end

end

%в result коэффициенты при степени x идут от 0 и возрастают.

%например, для result = 4 43 103 61 20 3 0 0

%многочлен получится 4 + 43x + 103x^2 + 61x^3 + 20 x^4 + 3x^5 Вычисление определителя квадратной матрицы методом приведения её к треугольному виду с помощью элементарных преобразований и рекурсивно, с использованием разложения по строке или столбцу

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

• Методом приведения к треугольному виду

function result=e17_1d(x) %x - это матрица, определитель которой надо посчитать

%считает определитель методом Гаусса: приводит матрицу к верхней треугольной путём сведения всех элементов

%столбца к 0 за счёт элемента x(i,i), где i - номер строки=номер столбца (за счёт каждого элемента на главной диагонали)

%x=[9, -1, 1; 20, 1, 2; 31, 2, 4] %уже введённые матрицы, чтобы было удобнее проверять работу

%x=[11,2,3,4;4,5,6,8;7,8,9,28;7,8,9,11]

%x=[0, -1, 1; 20, 1, 2; 31, 2, 4] %в этой матрице есть 0

sx=size(x) %размер матрицы. sx(1) - кол-во столбцов, sx(2) - кол-во строк

result=1 %так надо (c), чтобы не вылетало с ошибкой на строке 18

znak=1 %знак (множитель) определителя. Если 1, то +, если -1, то -. Знак меняется при каждой перестановке.

%Таким образом, если число перестановок чётно, то znak=1 (т.е.+). Если нет, то домножаем определитель на -1 (znak=-1)

for i=1:sx(1)

[x,znak]=checkforzero(x,i,znak)

for j=i:sx(2) %проходим по каждой строке

if i~=j %не трогаем текущую строку

k=x(j,i)/x(i,i) %коэффициент, на который домножаем, чтобы получить 0 (x(i,i) - элемент на главной диагонали, за счёт которго приводим к 0, x(j,i) - элемент на том же столбце и на текущей строке (j)

x(j,:)= x(j,:)- x(i,:)*k %вычитаем из строки j строку i, домноженную на k

end

end

result=result*x(i,i) %считаем определитель (произведение элементов главной диагонали треугольной матрицы)

end

result=result*znak %корректировка знака

function [result,znak]=checkforzero(x,i,znak) %x - матрица, i - номер элемента, за счёт которого будет делать 0 в остальных, znak - текущий множитель

if x(i,i)==0 %если элемент =0, то надо поменять местами строку, содержащую его, с любой, ниже его, не содержащей 0 в этом же столбце

aa=find(x) %ищем ненулевые элементы

for ee=1:length(aa) %ищем ближайший ненулевой элемент в текущем слолбце, расположенный под x(i,i)

if aa(ee)>i

i1=aa(1)

end

end

bf=x(1,:) %меняем строки местами

x(1,:)=x(i1,:)

x(i1,:)=bf

if znak==1 %меняем множитель

znak=-1

else

znak=1

end

end

result=x

• Рекурсивно

function result=exam_17_2_r(x) %x - это матрица, определитель которой надо посчитать

%x=[9, -1, 1; 20, 1, 2; 31, 2, 4] %уже введённые матрицы, чтобы было удобнее проверять работу

%x=[11,2,3,4;4,5,6,8;7,8,9,28;7,8,9,11]

result=do_it(x) %запускаем функцию

function result=do_it(x) %функция, которую запускаем

%считает определитель по 1й строке

op=0 %так надо (c)

sx=size(x) %размер матрицы. sx(1) - кол-во столбцов, sx(2) - кол-во строк

if sx(1)>2

for i=1:sx(1)

if i==1 %если первый элемент в строке

op=op+x(1,i)*do_it(x(2:sx(1), 2:sx(2)))

else %если другие элементы

t(1:i-1)=1:(i-1) %индексы столбцов, из которых формируется очередной определитель

t((i):sx(2)-1)=(i+1):sx(2) %этими 2 строками в t заполняются номера строк от 1 до sx(2), за исключением i

if mod(i,2)==0 %считаем определитель получившейся матрицы

op=op-x(1,i)*do_it(x(2:sx(1), t)) %если номер столбца чётный - домножаем коэфициент на -1

else

op=op+x(1,i)*do_it(x(2:sx(1), t)) %если нет, то не домножаем

end

end

result=op

end

else

result=op+(x(1,1)*x(2,2)-x(1,2)*x(2,1)) %считаем определитель, если получили матрицу 2x2

end

18. Векторизация арифметических и логических выражений в языке МАТЛАБ, возможности программировать на языке МАТЛАБ вычисления, без явного использования циклов. Использование векторных индексов массивов для выделения требуемой части массива. Понятие о динамических массивах, копирование, формирование и удаление отдельных элементов и более крупных частей массива. Примеры.

• Векторизация арифметических и логических выражений, возможность программировать без циклов:

Пусть x и y - массивы одинаковых размеров.

x.*y - перемножить все элементы x на соответствующие элементы y

x.^y - аналогично возвести в степень

x./y - аналогично деление

• Использование векторных индексов для выделения требуемой части массива:

y=x(2:5) - присвоить массиву y массив элементов x со 2го элемента до 5го.

y=x(2:end) - то же самое, только не до 5го элемента, а до конца

• Динамический массив

Динамическим называется массив, размер которого может меняться во время исполнения программы. Для изменения размера динамического массива язык программирования, поддерживающий такие массивы, должен предоставлять встроенную функцию или оператор. Динамические массивы дают возможность более гибкой работы с данными, так как позволяют не прогнозировать хранимые объёмы данных, а регулировать размер массива в соответствии с реально необходимыми объёмами. Обычные, не динамические массивы называют ещё статическими.

• Остальное - в начале части 1 лекции