ID: 10077

Название работы: Общее понятие исполнителя и алгоритма. Смысл понятия правильный алгоритм. Примеры

Категория: Конспект

Предметная область: Информатика, кибернетика и программирование

Описание: Общее понятие исполнителя и алгоритма. Смысл понятия правильный алгоритм. Примеры. Алгоритм Алгоритм последовательность определенных действий или шагов для решения поставленной задачи. Программа запись алгоритма на языке исполнителя Свва алгорит...

Язык: Русский

Дата добавления: 2013-03-21

Размер файла: 116.5 KB

Работу скачали: 25 чел.

1.  Общее понятие исполнителя и алгоритма. Смысл понятия «правильный алгоритм». Примеры.

•  Алгоритм

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

•  Исполнитель

Исполнитель – объект, который выполняет алгоритм.

•  Правильный алгоритм

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

•  Пример

%Нахождение разности
a = input ('введите уменьшаемое')
b = inbut ('введите вычитаемое')
res = a - b %разность

1.  Программы (m-функции) и подпрограммы (вспомогательные m-функции). Функции с параметрами, входные и выходные параметры, механизм присваивания значений параметрам функции (формальные и фактические параметры), локальные и глобальные переменные, рабочие области памяти (модель памяти) в языке МАТЛАБ

•  М-функции

М-функции являются M-файлами, которые допускают наличие входных и выходных аргументов. Они работают с переменными в пределах собственной рабочей области, отличной от рабочей области системы MATLAB.

Пример

Функция average - это достаточно простой M-файл, который вычисляет среднее значение элементов вектора:

function y = average (x)

% AVERAGE Среднее значение элементов вектора.

% AVERAGE(X), где X - вектор. Вычисляет среднее значение элементов вектора.

% Если входной аргумент не является вектором, генерируется ошибка.

[m,n] = size(x);

if (~((m == 1) | (n == 1)) | (m == 1 & n == 1)) 

error('Входной массив должен быть вектором’)

end 

y =sum(x)/length(x); % Собственно вычисление

•  Подпрограммы (вспомогательные m-функции)

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

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

•  Функции с параметрами

Функции с параметрами — функции, позволяющие производить определенные операции с переменными значениями.

Входные параметры — параметры с которыми работает программа  

Выходные — параметры которые выводятся на экран после выполнения программы
Пример: zad16(x,y,dey); x,y,dey - фактические входные параметры

Фактический параметр — аргумент, используемый как значение (число, символ и т. д.); Формальный параметр — аргумент, используемый как ячейка памяти (название переменной, указатель на переменную), выступающее в качестве идентификатора этого значения, принимаемого функцией.

•  Локальные переменные

Локальные переменные действуют только внутри m-функции, глобальные действуют во всей программе. Локальные переменные не требуют объявления. Прежде чем переменной присвоить значение, необходимо убедиться, что всем переменным в правой части значения присвоены. Любая операция присваивания создает переменную, если это необходимо, или изменяет значение существующей переменной. Обычно каждая М-функция, задаваемая в виде M-файла, имеет собственные локальные переменные, которые отличны от переменных других функций и переменных рабочей области. Однако, если несколько функций и рабочая область объявляют некоторую переменную глобальной, то все они используют единственную копию этой переменной. Любое присваивание этой переменной распространяется на все функции, где она объявлена глобальной.

•  Рабочие области функции

Каждой M-функции выделяется дополнительная область памяти, не пересекающаяся с рабочей областью системы MATLAB. Такая область называется рабочей областью функции.

При работе с системой MATLAB можно получить доступ только к переменным, размещенным в рабочей области системы или в рабочей области функции. Если переменная объявлена глобальной, то ее можно рассматривать как бы принадлежащей нескольким рабочим областям.

1.       Конструкции ветвления организация циклов в языке МАТЛАБ. Средства обработки (конструкция try – catch- end) и генерации (встроенная функция error) исключительных ситуаций в языке МАТЛАБ, вызванных наступлением фатальных ошибок (т.е. исключающих возможность нормального продолжения вычислительного процесса) при выполнении программы. Примеры

•  Конструкции ветвления организация циклов в языке МАТЛАБ

В программном пакете MATLAB возможно использование двух видов цикла: цикл for и цикл while.

for используется для организации вычислений с заданным количеством повторений. Цикл while используется, когда необходимо выполнять инструкции тела файла до тех пор, пока не выполнится заданное условие. Также существует оператор break, прекращающий работу последнего по вложению цикла.

•  Конструкция try-catch-end

Эта конструкция позволяет выполнить сомнительную операцию, а если операция приводит к фатальной ошибке, то вся программа не сломается, а пойдет дальше. После try запускаются некоторые инструкции. Если их невозможно выполнить, что берется программа действий из catch, а затем выполнение передается за оператор end. Очень похоже по принципу на if-else-end.

•  Error

Позволяет дать ошибке имя, указать переменные, использование которых привело к ошибке. Похоже на функцию sprintf.

function test

disp('Мы вошли в цикл')

try

a = fopen('test.txt', 'r'); %открываем некоторый файл

r = fread(a); %пытаемся прочесть некоторый файл

catch

disp ('Файла нет')

end

disp ('Мы вышли из цикла')

end

function errtest1(x, y)

if nargin ~= 2 %кол-во аргументов не 2

error('myApp:argChk', 'Wrong number of input arguments') % название ошибки, суть ошибки

end

1.  Значения, переменные, массивы (одномерные, двумерные, …), выражения встроенных классов  языка МАТЛАБ: double, logical, char, cell, struct. Оператор присваивания, явное и неявное присваивание, создание и удаление из памяти переменных различных классов. Примеры.

•  Значения, переменные, массивы

Значение - это константа, число или параметр присваиваемый переменной

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

Массив-совокупность чисел записанных в виде таблицы

•  Одномерные, двумерные, многомерные массивы.

Отличие состоит в способе нумерации: одномерные-1 индекс

пример:

x(1)=2; x(2)=4; x(3)=0; x(4)=-2;

получится вектор-строка:

2 4 0 -2

Двумерные- 2 индекса

y(1,1)=-2; y(1,2)=9; y(1,3)=-15; y(2,1)=1; y(2,2)=0; y(2,3)=2;

получится массив:

-2 9 -15
1 0 2

•  Выражения:

1.  Значение(константа)-это есть выражение
2.  Переменная-это есть выражение(значение с именем)
3.  m-функция, возвращающая значения с n входными фактическими параметрами- это есть выражение(n>=0)
4.  Функции, возвращающие значения, фактические параметры которой выражения- это тоже выражения

Класс выражения определяется классом значения-результата
double-используется для представления чисел с плавающей точкой
char-для представления символов
logical-для представления логических значений
cell-массивы ячеек
struct-массивы структур

•  Создание и удаление переменных

Переменная создается путем присваивания

<имя переменной>=<значение>-частный случай

<имя переменной>=<выражение>-общий случай

Пример

x=2.3-класс double

h='b'-класс char

удаляются переменные так:

clear('x','h')

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

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

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

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

•  Пример:

function a=findmin(x)

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

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

a=x(2);

l=length(x)

for i=2:2:l

   if a<x(i)

       a=x(i);

   end

end

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

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

Рассмотрим числовую последовательность 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

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

•  Рекурсия

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

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

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

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

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

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

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

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

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

1) a=b

Или

2) a~=b

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

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

Вычисление суммы:

function s=zad9(x)

x=[1,2,3,4];

%инвар:s-сумма первых i элем. x

s=0;

i=0;

n=numel(x);

 

while i<n

   i=i+1;

   s=s+x(i);

end

%утв. i==n & инвариант

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

Подсчёта числа элементов массива, имеющих максимальное  значение:

function s=v10_1(x)

x=[1,2,3,4,5,8,5,8]

maxm=x(end/2);

n=numel(x);

s=0;

for i=1:n

   if x(i)>maxm

       maxm=x(i);

       s=0;

   end

   

   if x(i)==maxm

       s=s+1;

   end

end

Вычисления средне-квадратического отклонения заданной числовой последовательности:

function otk=zad10_2(x)

x=[1,2,3,4,5,6,7]

n=numel(x);

sr=0;

sk=0;

s=0;

for i=1:n

   sr=sr+x(i)/n; %среднее

   sk=sk+(x(i))^2; %сумма квадратов чисел

   s=s+x(i);  %сумма чисел

end

otk=sqrt((sk-2*sr*s+n*sr^2)/n);

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

•  Понятие временной сложност:

Оценка числа операций, требуемых для выполнения алгоритма.

f(n) = O(1) константа
f(n) = O(log(n)) логарифмический рост
f(n) = O(n) линейный рост
f(n) = O(n*log(n)) квазилинейный рост
f(n) = O(n^m) полиномиальный рост
f(n) = O(2^n) экспоненциальный рост

Запись вида f(n) = O(g(n)) означает, что ф-ия f(n) возрастает медленнее чем ф-ия g(n) при с = с1 и n = N, где c1 и N могут быть сколь угодно большими числами, т.е. При c = c1 и n >= N, c*g(n) >=f(n).

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

Принцип - если степень N четна то можно возвести число в квадрат и в оставшуюся целую степень (N/2), иначе умножаем результат на возводимое число и уменьшаемстепень на 1.

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

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

Пузырьковая сортировка, является сортировкой квадратичной сложности, т.к. содержит 2 цикла, то есть n^2

function x=bubble(x)

n=length(x);

for j=1:1:n-1

   % сравниваем каждый элемент со следующим и меняем местами

       for i=1:1:n-1

           if x(i)>x(i+1);

               temp=x(i);

               x(i)=x(i+1);

               x(i+1)=temp;

           end

       end

end

Сортировка слиянием:

function p=sort_sl(m,n)

m=[1,2,3,4,5]

n=[1,2,3,4,5]

n1=numel(m);

n2=numel(n);

j=1;

L=1;

for i=1:(n1+n2)

   if j>n1

       p(i)=n(L);

       L=L+1;

   else

       if L>n2

           p(i)=m(j);

           j=j+1;

       else

           if m(j)<=n(L)

               p(i)=m(j);

               j=j+1;

           else

               p(i)=n(L);

               L=L+1;

           end

       end

   end

end

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

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

В качестве примера может послужить второй типовик

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

function n=num_abcd(str)

str='abcdabcdasdasdkosakdabcd';

n=0;

s=0;

while ~isempty(str)

   if s==0

       if str(1)=='a'

           s=1;

       end

   elseif s==1

       if str(1)=='b'

           s=2;

       else

           s=0;

       end

   elseif s==2

       if str(1)=='c'

           s=3;

       else

           s=0;

       end

   elseif s==3

           if str(1)=='d'

               n=n+1;                

           end

     s=0;      

   end  

   str(1)=[];

end

       

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

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

Убывание степеней:

function p=zad15(x)

x=-1;            %точка х

a=[1,1,2,1];     %коэффициенты полинома

q=a(1);

p=0;             %производная

for i=2:length(a)

   p=p.*x+q;    %вычисление производной в точке х

   q=q.*x+a(i); %вычисление значения ф-ии в точке х

end

Возрастание степеней:

function y=zad15_2(x)

x=-2;             %точка х

a=[1,2,1,1];      %коэффициенты полинома

y=0;              

p=1;              %степень x

for k=1:length(a)

   y=y+a(k).*p;   %вычисление значения ф-ии в точке х

   p=p.*x;    

end

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

function s=zad16(x,y,dey)

%степень: n,n-1,...,2,1,0

x=[1,2,1];

y=[1,3];

dey=2;                         %1-сложение, все остальное умножение

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

   a=length(x);               %a-длина х, но в данной задаче как длина самого длинного вектора

   while length(x)~=length(y)

       y=[0,y];

   end

else

   a=length(y);

   while length(y)~=length(x) %если наоборот, то дополняем нулями x

       x=[0,x];

   end 

end

 

%получили 2 одинаковых вектора готовых к сложению или умножению

 

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

   for i=1:a

       m(i)=x(i)+y(i);

   end

else   %умножаем

   m(1:(length(x)+length(y)-1))=0; %делаем нулевой массив m

   for i=1:a

       for j=1:a

           m(i+j-1)=m(i+j-1)+x(i)*y(j);

       end

   end

end

%убираем нули в начале массива m.

i=1;

if m(1)==0  %если первый элемент массива m нулевой, тогда

   while m(i)==0

       s=m(i+1:end);

       i=i+1;

   end

else

   s=m;

end

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

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

function d=det_1(x)

%det-библиотечная функция для вычисления определителя

%исх  x-возвр. Матрица double

%рез d=определитель Х

x=[12,2,3;4,5,6;7,8,9];

n=length(x);

 

for i=1:n-1

      x(i:end,i:end)=pol_nuli(x(i:end,i:end));

end

%x имеет ступентачатый вид

d=1;

for i=1:n

     d=d*x(i,i);

end

 

 

function x=pol_nuli(x)

%исх: X-квадратная матрица double

% рез: выполняем превый шаг привидения к ступенчатому виду : x(1,1)~=0;x(2,2)~=0

imax=1;%индекс ведущей строки

n=length(x);

for i=2:n

      if abs(x(i,1))>abs(x(imax,1))

           imax=i;

       end

end

t=x(1,:);

x(1,:)=x(imax,:);

x(imax,:)=t;

%x(1,1)-ведущий элемент в 1-ом столбце

 for i=2:n

k=-x(i,1)/x(1,1);

x(i,:)=x(i,:)+k*x(1,:);

 end

•  Рекурсивно

function d=det_2(x)

x=[12,2,3;4,5,6;7,8,9]

if length(x)==1

   d=x

else

   d=0;

   sign=1;

end

 

for i=1:length(x)

   d=d+sign*det(x(2:end,[1:i-1,i+1:end]))*x(1,i);

   sign=-sign;

end

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

Обычные числа и переменные в MATLAB рассматриваются как матрицы размера 1x1, что дает единообразные формы и методы проведения операций над обычными числами и массивами. Данная операция обычно называется векторизацией. Векторизация обеспечивает и упрощение записи операций, производимых одновременно над всеми элементами вектрров и матриц, и существенное повышение скорости их выполнения.

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

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

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

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

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

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

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

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

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

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

Формирование

»V=[1 2 3] 

V= 
1   2   3 
задает вектор V, имеющий три элемента со значениями 1, 2 и 3. 

» М=[1 2 3: 4 5 6; 7 8 9]; 
задает квадратную матрицу, которую можно вывести: 
M = 
1     2     3 

4     5     6 

7     8     9 
Возможен ввод элементов матриц и векторов в виде арифметических выражений, содержащих любые доступные системе функции, например: 
» V= [2+2/(3+4) exp(5) sqrt(l0)]: 

V =  2.2857     148.4132     3.1623 

Удаление столбцов и строк матриц
Для формирования матриц и выполнения ряда матричных операций возникает необходимость удаления отдельных столбцов и строк матрицы. Для этого используются пустые квадратные скобки [ ]. Проделаем это с матрицей М: 
» М=[1 2 3; 4 5 6; 7 8 9] 
Удалим второй столбец используя оператор : (двоеточие):  » М(:.2)=[ ] 
1    3

4    6

7    9

А теперь, используя оператор : (двоеточие), удалим вторую строку:  » М(2.:)=[ ] 
1    3

7    9

1.  Алгоритмы вычисления коря нелинейного уравнения с одной неизвестной (делением отрезка пополам)

•  Делением отрезка пополам

function z=zad17(a,b,eps)

%инвар: f(a)f(b)<0, корень ровно 1 на [a,b]

%a=0;

%b=2;

%eps=0.000001;

 

ya=f(a);

yb=f(b);

 

while b-a>2*eps

   z=(a+b)/2;

   yz=f(z);

   if ya*yz<0

       b=z;

       yb=yz;

   else

       a=z;

       ya=yz;

   end

end

 

function y=f(x)

%y=cos(x)-x;

То, что было на консультации: Дан массив, отсортировать первый столбец по убыванию, вместе с этим отсортировать и строки, содержащие первый элемент

function y=prim_mat(x)

x=[1,2,3;0,2,4;7,9,12];

c=x(:,1);

n=length(c);

p=1:n;

%пузырьковая сортировка по убыванию

for i=1:n-1

   for j=1:n-i

       if c(j)<c(j+1)

           t=c(j);

           c(j)=c(j+1);

           c(j+1)=t;

           

           t=p(j);

           p(j)=p(j+1);

           p(j+1)=t;

       end

   end

end

 

y=x(p,:);

 

%другой вариант:

%i=1;

%while i<=n

%    y(i,:)=x(p(i),:);

%    i=i+1;

%end