uzluga.ru
добавить свой файл
1



Общая характеристика курса

  • Рассматривается неформальное понятие алгоритма и его представления

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

  • Обсуждаются свойства алгоритмов, разработка алгоритмов

  • Вводится понятие сложности алгоритма

  • Рассматриваются и анализируются алгоритмы из различных предметных областей

  • Лекции и семинары/лабораторные рассматривают детально приложения.



Рекомендуемые учебники





Лекции 1 и 2 АЛГОРИТМ И ЕГО СВОЙСТВА

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

  • Дается и обсуждается формальное определение алгоритма

  • Рассматривается связь алгоритма и программы:

  • Задача  модель_задачи  F  A  P

  • 3.Обсуждаются проблемы конструирования программы, реализующей алгоритм



Краткая классификация алгоритмов



ПОНЯТИЕ ВЫЧИСЛИМОЙ ФУНКЦИИ

  • Формализация Клини понятия вычислимой функции и алгоритма нам понадобится для формирования правильной исходной точки зрения при анализе, конструировании и размышлениях об алгоритмах и программах.

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



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

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

  • Каждый легко может определить, является ли некоторый предъявленный процесс алгоритмом или нет. Например, вычисление корней квадратного полинома по формуле Виета есть алгоритм. Однако без формализации понятия алгоритма невозможно показать, что не существует алгоритмического решения некоторой проблемы



Неформальные свойства алгоритмов

  • а).Алгоритм - это процесс последовательного построения величин, идущий в дискретном времени таким образом, что в начальный момент задается исходная конечная система величин, а в каждый следующий момент новая конечная система величин получается по определенному закону (программе) из системы величин, имеющихся в предыдущий момент времени (дискретность алгоритма).



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

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

  • в).Закон получения последующей системы величин из предшествующей должен быть простым и локальным (элементарность шагов алгоритма).



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

  • г).Если способ получения последующей величины из какой-нибудь заданной величины не дает результата, то должно быть указано, что надо считать результатом алгоритма (направленность алгоритма).

  • д).Начальная система величин может выбираться из некоторого потенциально бесконечного множества (массовость алгоритма).



Каждый алгоритм A вычисляет функцию FA при некоторых заданных значениях входных величин. Функции, вычисляемые алгоритмом, называются алгоритмически вычислимыми функциями. Понятие вычислимой функции, так же как и понятие алгоритма, тоже здесь интуитивно.

  • Каждый алгоритм A вычисляет функцию FA при некоторых заданных значениях входных величин. Функции, вычисляемые алгоритмом, называются алгоритмически вычислимыми функциями. Понятие вычислимой функции, так же как и понятие алгоритма, тоже здесь интуитивно.

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







ОПЕРАТОРЫ

      • ОПЕРАТОРЫ
      • 1.СУПЕРПОЗИЦИЯ ВЫЧИСЛИМЫХ ФУНКЦИЙ
      • Пусть заданы n частичных функций m переменных fim:D1D2...DmDo, i=1, 2,..., n, и пусть определена функция fn:D0D0...D0D. Определим функцию m переменных gm, определенную на множестве D1D2...Dm со значениями в D, gm(x1,x2,...,xm)=fn(f1m(x1,x2,...,xm),...,fnm(x1,x2,...,xm)). Функция gm конструируется суперпозицией (подстановкой) из функций f n, f1m, ... , fnm. Оператор суперпозиции будем обозначать Sn+1.
      • Понятно, что функция gm(x1,x2,...,xm) и есть та функция, которую определяет функциональный терм fn(f1m(x1,x2,...,xm),...,fnm(x1,x2,...,xm)) при соответствующей интерпретации.


Программисты легко могут представить себе наличие процедур, вычисляющих простейшие вычислимые функции. Оператор суперпозиции определяет, с позиций программирования, простое “сцепление” процедур, при котором одни процедуры вырабатывают значения своих выходных переменных, а другие их использует в качестве входных величин. Понятен и “механический” характер определения оператора суперпозиции, его очевидная вычислимость, а именно: если известно, как вычислить значения функций f, f1, ... , fn, то понятен и алгоритм вычисления функции

  • Программисты легко могут представить себе наличие процедур, вычисляющих простейшие вычислимые функции. Оператор суперпозиции определяет, с позиций программирования, простое “сцепление” процедур, при котором одни процедуры вырабатывают значения своих выходных переменных, а другие их использует в качестве входных величин. Понятен и “механический” характер определения оператора суперпозиции, его очевидная вычислимость, а именно: если известно, как вычислить значения функций f, f1, ... , fn, то понятен и алгоритм вычисления функции

  • gm(x1,x2,...,xm)=f n (f1(x1,x2,...,xm), ...,f n(x1,x2,...,xm)).



Каждый программист легко узнает в нижеследующей программе “реализацию” оператора суперпозиции.

  • Каждый программист легко узнает в нижеследующей программе “реализацию” оператора суперпозиции.

  • Пусть процедуры f, f1, ... , fn вычисляют одноименные функции. Тогда программа P вычисляет функцию g.

  • P: y1 := f1( x1,x2,...,xm );

  • . . .

  • yn := fn(x1,x2,...,xm))

  • y := f(y1,y2,..., yn );



2.Оператор примитивной рекурсии

  • Оператор примитивной рекурсии позволяет определить циклические вычисления специального вида.

  • Пусть заданы:

  • - n-местная вычислимая функция g и

  • - (n+2)-местная вычислимая функция h.

  • Тогда (n+1)-местная функция f строится примитивной рекурсией из функций g и h, если для всех натуральных значений x1, x2, ... ,xn, y имеем:

  • f(x1, x2, ... ,xn,0 )=g(x1, x2, ... ,xn )

  • f(x1, x2, ... ,xn,y+1)=h(x1, x2, ... ,xn ,y, f(x1, x2, ... ,xn,y))



Соотношения называются схемой примитивной рекурсии. Они определяют оператор примитивной рекурсии R. Эта схема, собственно, и есть алгоритм вычисления функции f. Оператор R определен на множестве частичных вычислимых функций, f=R(g,h).

  • Соотношения называются схемой примитивной рекурсии. Они определяют оператор примитивной рекурсии R. Эта схема, собственно, и есть алгоритм вычисления функции f. Оператор R определен на множестве частичных вычислимых функций, f=R(g,h).

  • Понятно, что функция f существует и единственна. Это следует из того, что определение функции, построенной примитивной рекурсией, фактически содержит схему (алгоритм) ее вычисления. Распишем детально эту схему, используя термальные представления.



Пусть необходимо вычислить значение функции f при y=k. Тогда из определения (1) схемы примитивной рекурсии имеем последовательность функциональных термов t0, t1,…, tk, вычисляющих значение функции f(x1, x2, ... ,xn, k):

  • Пусть необходимо вычислить значение функции f при y=k. Тогда из определения (1) схемы примитивной рекурсии имеем последовательность функциональных термов t0, t1,…, tk, вычисляющих значение функции f(x1, x2, ... ,xn, k):

  • t0: f0=f(x1,x2,...,xn,0)=g(x1,x2,...,xn)

  • t1: f1=f(x1,x2,...,xn,1)=h(x1,x2,...,xn,0,g(x1,x2,...,xn))

  • t2: f2=f(x1,x2,...,xn,2)= h(x1,x2,...,xn,1, f(x1,x2,...,xn,1))

  • ..............................................................................

  • tk: fk=f(x1,x2,...,xn, k)=h(x1,x2,...,xn,k-1,f(x1,x2,...,xn,k-1))

  • Здесь представлен способ вычисления f, следовательно, функция f определена однозначно. Если одна из функций f(x1,x2,...,xn,m), mне определена, то и значение f(x1,x2,...,xn,y) для всех ym тоже не определено. Эту последовательность k+1 функциональных термов t0, t1, ... tk удобно для наглядности изобразить графически.





Это множество функциональных термов и определяет алгоритм вычисления функции f. Опытные программисты легко узнают на рисунке «раскрутку» вызовов рекурсивной процедуры. Множество термов (представление алгоритмов в виде множества термов) позволяет легко построить программу P, реализующую применение оператора примитивной рекурсии к функциям g и h и вычисляющую функцию f.

  • Это множество функциональных термов и определяет алгоритм вычисления функции f. Опытные программисты легко узнают на рисунке «раскрутку» вызовов рекурсивной процедуры. Множество термов (представление алгоритмов в виде множества термов) позволяет легко построить программу P, реализующую применение оператора примитивной рекурсии к функциям g и h и вычисляющую функцию f.

  • P: s:=k;

  • f[0]:=g(x1,x2,...,xn);

  • for i=1 to s do

  • f[i]=h(x1,x2,...,xn, i-1, f[i-1]);

  • f :=f[s];



Программисты записывают, обычно, P более экономно, но не “функционально”.

  • Программисты записывают, обычно, P более экономно, но не “функционально”.

  • P1 : s:=k;

  • f:=g(x1,x2,...,xn);

  • for i=1 to s do

  • f=h(x1,x2,...,xn,i-1,f);

  • Функция f называется примитивно рекурсивной относительно множества простейших функций, если она строится из простейших вычислимых функций конечным числом применения операторов суперпозиции и примитивной рекурсии.







3.Оператор минимизации

      • 3.Оператор минимизации
  • Пусть f - некоторая n-местная вычислимая функция, n1, алгоритм вычисления f известен. Вычисление значения функции f для некоторого значения аргумента невозможно лишь тогда, когда алгоритм не может завершиться.

  • Зафиксируем некоторые значения первых n-1 переменных x1, x2, ... ,xn-1. Рассмотрим уравнение

  • f(x1, x2, ... ,xn-1,y)=xn (3)

  • Для его решения начнем вычислять последовательно значения функции f(x1, x2, ... ,xn-1,y) для y=0, 1, 2, ... . Наименьшее число k такое, что f(x1, x2, ... ,xn-1,k)=xn есть решение этого уравнения. Это решение обозначается y(f(x1, x2, ... ,xn-1,y)=xn). Решения может и не оказаться, например если:

  • - значения f(x1, x2, ... ,xn-1,k), k=0, 1, 2, ,,, определены и отличны от xn, а значение f(x1, x2, ... ,xn-1,k+1) не определено,

  • - значения f(x1, x2, ... ,xn-1,k), k=0, 1, 2, ... , все определены и отличны от xn.



В таких случаях значение y(f(x1, x2, ... ,xn-1,y)=xn) считается неопределенным. Величина y(f(x1, x2, ... ,xn-1, y)=xn) зависит от значений переменных x1, x2, ... ,xn-1,xn и потому она может рассматриваться как значение функции от аргументов x1, x2, ... , xn-1, xn . Эта функция обозначается f, называется оператором минимизации.

  • В таких случаях значение y(f(x1, x2, ... ,xn-1,y)=xn) считается неопределенным. Величина y(f(x1, x2, ... ,xn-1, y)=xn) зависит от значений переменных x1, x2, ... ,xn-1,xn и потому она может рассматриваться как значение функции от аргументов x1, x2, ... , xn-1, xn . Эта функция обозначается f, называется оператором минимизации.

  • Оператор минимизации очевидно частично вычислим, а значит и функция f частично вычислима. Функция f называется частично рекурсивной относительно простейших функций, если она строится конечным числом применений операторов суперпозиции, примитивной рекурсии и минимизации.



Как и для оператора примитивной рекурсии для оператора минимизации можно построить представление в виде счетного множества функциональных термов. Введем предикат P(yi):f(x1, x2, ... ,xn-1,yi)=xn. Тогда оператор минимизации представляется счетным множеством функциональных термов .



  • Предикат P(yi) выделяет функциональный терм, который вырабатывает значение функции y(f(x1, x2, ... ,xn-1,y)=xn).

  • Из всех этих термов лишь один может выработать значение функции f, а именно тот, который выработает значение zk=xn для минимального k. Таким образом и здесь, как и в случае оператора примитивной рекурсии, операторный терм f представляется счетным множеством функциональных термов. Одно из существенных отличий состоит в том, что конечное множество функциональных термов, представляющих оператор примитивной рекурсии, фиксируется для конкретных значений до начала вычислений. В случае оператора минимизации терм, вычисляющий значение функции, определяется динамически в ходе вычисления.



Для конструирования программы, вычисляющей частично-рекурсивную функцию, оператора типа for уже недостаточно, нужен оператор типа while. Именно поэтому, любой процедурный язык программирования содержит операторы типа while. Следующая программа реализует оператор минимизации:

  • Для конструирования программы, вычисляющей частично-рекурсивную функцию, оператора типа for уже недостаточно, нужен оператор типа while. Именно поэтому, любой процедурный язык программирования содержит операторы типа while. Следующая программа реализует оператор минимизации:

  • P : z:=f(x1, x2, ... ,xn-1,0);

  • i:=0;

  • while z xn do

  • {

  • i:=i+1;

  • z:=f(x1, x2, ... ,xn-1,i);

  • };

  • f:=i;

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



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

  • Было показано, что каждая частично рекурсивная функция представляется потенциально бесконечным множеством функциональных термов.

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

  • n:=.... ;

  • for i = 1 to n do

  • z[i]:=x[i]+y[i] ;

  • реализует алгоритм, представленный множеством термов







Это множество функциональных термов строится фиксацией значения предиката P. Если фиксировать P=true, то программа реализует множество функциональных термов с использованием только операции “+”. А если зафиксировать P=false, то программа реализует множество функциональных термов с операцией “-“ . Объединение этих множеств и даст множество, показанное на рисунке.

  • Это множество функциональных термов строится фиксацией значения предиката P. Если фиксировать P=true, то программа реализует множество функциональных термов с использованием только операции “+”. А если зафиксировать P=false, то программа реализует множество функциональных термов с операцией “-“ . Объединение этих множеств и даст множество, показанное на рисунке.





Каждый преобразователь a (будем впредь называть его операцией) вычисляет функцию f, значение которой есть результат выполнения преобразования (выполнение операции) a. Для вычисления функции f используется модуль mod a

















Пример 3 и разработка программы

  • Представление S=(X,F,C,M) алгоритма A в форме блок-схемы и одного из его возможных представлений в форме программы P. Здесь X={x,y,z,x1,z1}, F={a,b,c}. C - потоковое управление (показано стрелками)



Пример 4. Задание алгоритма формулами

  • Исходный алгоритм умножения квадратных матриц сформулирован в терминах элементов матриц



Исходный алгоритм

  • Исходный алгоритм



Диаграмма: алгоритм и программа

  • Диаграмма: алгоритм и программа





Если отображение M сопоставляет массиву y участок памяти, в котором может быть размещена лишь одна запись, и доступен только один процессор, тогда прямым управлением C должен быть задан следующий жестко определенный порядок выполнения операций: read(f,1), a1, read(f,2), a2, ... (обычно в программе задается с использованием оператора цикла).

  • Если отображение M сопоставляет массиву y участок памяти, в котором может быть размещена лишь одна запись, и доступен только один процессор, тогда прямым управлением C должен быть задан следующий жестко определенный порядок выполнения операций: read(f,1), a1, read(f,2), a2, ... (обычно в программе задается с использованием оператора цикла).

  • При таком порядке исполнения считанная запись файла будет потреблена операцией a, память освобождена, и следующая запись может быть считана в тот же участок памяти, что и предшествующая запись. Алгоритм Afile будет правильно реализован, т.е. будет вычислена функция FAfile.



Если при тех же условиях на размещение массива y для исполнения алгоритма доступны два процессора, тогда, кроме последовательного, может быть ещё организовано конвейерное исполнение алгоритма (другая его реализация), при котором обработка i-ой записи файла делается одновременно со считыванием (i+1)-ой записи файла

  • Если при тех же условиях на размещение массива y для исполнения алгоритма доступны два процессора, тогда, кроме последовательного, может быть ещё организовано конвейерное исполнение алгоритма (другая его реализация), при котором обработка i-ой записи файла делается одновременно со считыванием (i+1)-ой записи файла



Если разрешается разместить в памяти две записи, тогда может быть использован режим ввода с двумя буферами и две операции - ai и ai+1 - смогут выполняться одновременно, когда есть доступные процессоры и т.д.