Методы построения и анализа алгоритмов Малышкин Виктор Эммануилович Кафедра Параллельных Вычислительных Технологий Новосибирский государственный технический. - презентация

1 Методы построения и анализа алгоритмов Малышкин Виктор Эммануилович Кафедра Параллельных Вычислительных Технологий Новосибирский государственный технический университет E_mail: Телефон: Новосибирск

2 Алгоритмы: Анализ и Построение2 Общая характеристика курса 1. 1.Рассматривается неформальное понятие алгоритма и его представления 2. 2.Тема курса очень обширна, доступно много учебных материалов. В 8 лекций материал невозможно уложить так, чтобы изучить проблемы и научиться пользоваться знанием. Потому для большей широты покрытия материала обсуждаются идеи, а остальное - самостоятельная работа студента Обсуждаются свойства алгоритмов, разработка алгоритмов 4. 4.Вводится понятие сложности алгоритма 5. 5.Рассматриваются и анализируются алгоритмы из различных предметных областей 6. 6.Лекции и семинары/лабораторные рассматривают детально приложения.

3 Алгоритмы: Анализ и Построение3 Ахо, Альфред, В., Хопкрофт, Джон, Ульман, Джеффри, Д. Структуры данных и алгоритмы. : Пер. с англ. : Уч. пос. М. : Издательский дом "Вильяме", с. Кормен Т., Лейзерсон Ч., Риверс Р., Штайн К. Алгоритмы. Построение и анализ – М.: «Вильямс», 2012 В.Э.Малышкин, В.Д.Корнеев. Параллельное программирование мультикомпьютеров. – В серии «Учебники НГТУ», Новосибирск, изд-во НГТУ, 2011, 296 стр. (есть в библиотеке Рекомендуемые учебники

4 Алгоритмы: Анализ и Построение4 ДОПОЛНИТЕЛЬНЫЕ М.Гэри, Д.Джонсон. Вычислительные машины и труднорешаемые задачи // М. Мир, 1982, 416 стр. Седжвик Роберт. Фундаментальные алгоритмы на C++. Анализ/Структуры данных/ Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - К.: Издательство «ДиаСофт», с.Седжвик Роберт. Фундаментальные алгоритмы на C++. Анализ/Структуры данных/ Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - К.: Издательство «ДиаСофт», с.

5 Алгоритмы: Анализ и Построение5 Лекции 1 и 2 Лекции 1 и 2 АЛГОРИТМ И ЕГО СВОЙСТВА Основная задача лекций – обсудить неформально понятие алгоритма, его полезные свойства, его представления для тех или иных целей 1. 1.Дается и обсуждается формальное определение алгоритма 2. 2.Рассматривается связь алгоритма и программы: Задача модель_задачи F A P 3.Обсуждаются проблемы конструирования программы, реализующей алгоритм

6 Алгоритмы: Анализ и Построение6 Краткая классификация алгоритмовЗАДАЧИСВОЙСТВА Численные Системные Комбинаторные Оптимизационные Прикладные (машиностроение, космос, наука, экономика, …) Теоретические Технологические И прочие и прочие Параллельные Высокоточные Интенсивные вычисления Интенсивные данные Быстрые Динамические Настраивающиеся Самоорганизация Минимальное потребление ресурсов Надежность И прочие и прочие

7 Алгоритмы: Анализ и Построение7 ПОНЯТИЕ ВЫЧИСЛИМОЙ ФУНКЦИИ Формализация Клини понятия вычислимой функции и алгоритма нам понадобится для формирования правильной исходной точки зрения при анализе, конструировании и размышлениях об алгоритмах и программах.Формализация Клини понятия вычислимой функции и алгоритма нам понадобится для формирования правильной исходной точки зрения при анализе, конструировании и размышлениях об алгоритмах и программах. Понятие вычислимой функции - ключевое понятие из тех, которыми должен владеть программист и вообще всякий, работающий в области вычислений. Задача лекции - дать начальные понятия теории алгоритмов в ее приложении к программированиюПонятие вычислимой функции - ключевое понятие из тех, которыми должен владеть программист и вообще всякий, работающий в области вычислений. Задача лекции - дать начальные понятия теории алгоритмов в ее приложении к программированию

8 Алгоритмы: Анализ и Построение8 Говоря о программе, всегда будем иметь ввиду всевозможные способы ее исполнения, включая частный случай - последовательное исполнение. Термин последовательная программа используется, чтобы подчеркнуть единственно допустимый способ исполнения программы.Говоря о программе, всегда будем иметь ввиду всевозможные способы ее исполнения, включая частный случай - последовательное исполнение. Термин последовательная программа используется, чтобы подчеркнуть единственно допустимый способ исполнения программы. Каждый легко может определить, является ли некоторый предъявленный процесс алгоритмом или нет. Например, вычисление корней квадратного полинома по формуле Виета есть алгоритм. Однако без формализации понятия алгоритма невозможно показать, что не существует алгоритмического решения некоторой проблемыКаждый легко может определить, является ли некоторый предъявленный процесс алгоритмом или нет. Например, вычисление корней квадратного полинома по формуле Виета есть алгоритм. Однако без формализации понятия алгоритма невозможно показать, что не существует алгоритмического решения некоторой проблемы

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

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

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

12 Алгоритмы: Анализ и Построение12 Каждый алгоритм A вычисляет функцию F A при некоторых заданных значениях входных величин. Функции, вычисляемые алгоритмом, называются алгоритмически вычислимыми функциями. Понятие вычислимой функции, так же как и понятие алгоритма, тоже здесь интуитивно. Каждый алгоритм A вычисляет функцию F A при некоторых заданных значениях входных величин. Функции, вычисляемые алгоритмом, называются алгоритмически вычислимыми функциями. Понятие вычислимой функции, так же как и понятие алгоритма, тоже здесь интуитивно. Существует много разных формализаций понятия алгоритм, удовлетворяющих неформальным требованиям. Однако класс алгоритмически вычислимых функций, определенный во всех таких формализациях оказался одним и тем же при самых разнообразных попытках расширить понятие алгоритма.Существует много разных формализаций понятия алгоритм, удовлетворяющих неформальным требованиям. Однако класс алгоритмически вычислимых функций, определенный во всех таких формализациях оказался одним и тем же при самых разнообразных попытках расширить понятие алгоритма.

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

14 Алгоритмы: Анализ и Построение14 АКСИОМЫ (простейшие вычислимые функции) На первом шаге выбирается счетный базис простейших рекурсивных функций, вычислимых по определению. Это следующие функции: 1. Функция следования s(x)=x+1 2. Нулевая функция o(x)=0 3. Функции выбора I m n (x 1,x 2,...,x n )=x m, 1 mn Функции устроены крайне просто. Ни у кого, видимо, нет сомнений в интуитивной вычислимости этих функций, в возможности построить некоторое механическое устройство, вычисляющее эти функции. Аксиоматическое построение теории вычислимых функций и алгоритмов

15 Алгоритмы: Анализ и Построение15 ОПЕРАТОРЫ 1.СУПЕРПОЗИЦИЯ ВЫЧИСЛИМЫХ ФУНКЦИЙ Пусть заданы n частичных функций m переменных f i m :D 1 D 2... D m D o, i=1, 2,..., n, и пусть определена функция f n :D 0 D 0... D 0 D. Определим функцию m переменных g m, определенную на множестве D 1 D 2... D m со значениями в D, g m (x 1,x 2,...,x m )=f n (f 1 m (x 1,x 2,...,x m ),...,f n m (x 1,x 2,...,x m )). Функция g m конструируется суперпозицией (подстановкой) из функций f n, f 1 m,..., f n m. Оператор суперпозиции будем обозначать S n+1. Понятно, что функция g m (x 1,x 2,...,x m ) и есть та функция, которую определяет функциональный терм f n (f 1 m (x 1,x 2,...,x m ),...,f n m (x 1,x 2,...,x m )) при соответствующей интерпретации.

16 Алгоритмы: Анализ и Построение16 Программисты легко могут представить себе наличие процедур, вычисляющих простейшие вычислимые функции. Оператор суперпозиции определяет, с позиций программирования, простое сцепление процедур, при котором одни процедуры вырабатывают значения своих выходных переменных, а другие их использует в качестве входных величин. Понятен и механический характер определения оператора суперпозиции, его очевидная вычислимость, а именно: если известно, как вычислить значения функций f, f 1,..., f n, то понятен и алгоритм вычисления функцииПрограммисты легко могут представить себе наличие процедур, вычисляющих простейшие вычислимые функции. Оператор суперпозиции определяет, с позиций программирования, простое сцепление процедур, при котором одни процедуры вырабатывают значения своих выходных переменных, а другие их использует в качестве входных величин. Понятен и механический характер определения оператора суперпозиции, его очевидная вычислимость, а именно: если известно, как вычислить значения функций f, f 1,..., f n, то понятен и алгоритм вычисления функции g m (x 1,x 2,...,x m )=f n (f 1 (x 1,x 2,...,x m ),...,f n (x 1,x 2,...,x m )). g m (x 1,x 2,...,x m )=f n (f 1 (x 1,x 2,...,x m ),...,f n (x 1,x 2,...,x m )).

17 Алгоритмы: Анализ и Построение17 Каждый программист легко узнает в нижеследующей программе реализацию оператора суперпозиции. Пусть процедуры f, f 1,..., f n вычисляют одноименные функции. Тогда программа P вычисляет функцию g. P:y 1 := f 1 ( x 1,x 2,...,x m );... y n := f n (x 1,x 2,...,x m )) y n := f n (x 1,x 2,...,x m )) y := f(y 1,y 2,..., y n );

18 Алгоритмы: Анализ и Построение18 2.Оператор примитивной рекурсии Оператор примитивной рекурсии позволяет определить циклические вычисления специального вида. Пусть заданы: - n-местная вычислимая функция g и - (n+2)-местная вычислимая функция h. Тогда (n+1)-местная функция f строится примитивной рекурсией из функций g и h, если для всех натуральных значений x 1, x 2,...,x n, y имеем: f(x 1, x 2,...,x n,0 )=g(x 1, x 2,...,x n ) f(x 1, x 2,...,x n,y+1)=h(x 1, x 2,...,x n,y, f(x 1, x 2,...,x n,y))

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

20 Алгоритмы: Анализ и Построение20 Пусть необходимо вычислить значение функции f при y=k. Тогда из определения (1) схемы примитивной рекурсии имеем последовательность функциональных термов t 0, t 1,…, t k, вычисляющих значение функции f(x 1, x 2,...,x n, k): t 0 : f 0 =f(x 1,x 2,...,x n,0)=g(x 1,x 2,...,x n ) t 1 : f 1 =f(x 1,x 2,...,x n,1)=h(x 1,x 2,...,x n,0,g(x 1,x 2,...,x n )) t 2 : f 2 =f(x 1,x 2,...,x n,2)= h(x 1,x 2,...,x n,1, f(x 1,x 2,...,x n,1)) t k : f k =f(x 1,x 2,...,x n, k)=h(x 1,x 2,...,x n,k-1,f(x 1,x 2,...,x n,k-1)) Здесь представлен способ вычисления f, следовательно, функция f определена однозначно. Если одна из функций f(x 1,x 2,...,x n,m), m

21 Алгоритмы: Анализ и Построение21

22 Алгоритмы: Анализ и Построение22 Это множество функциональных термов и определяет алгоритм вычисления функции f. Опытные программисты легко узнают на рисунке «раскрутку» вызовов рекурсивной процедуры. Множество термов (представление алгоритмов в виде множества термов) позволяет легко построить программу P, реализующую применение оператора примитивной рекурсии к функциям g и h и вычисляющую функцию f.Это множество функциональных термов и определяет алгоритм вычисления функции f. Опытные программисты легко узнают на рисунке «раскрутку» вызовов рекурсивной процедуры. Множество термов (представление алгоритмов в виде множества термов) позволяет легко построить программу P, реализующую применение оператора примитивной рекурсии к функциям g и h и вычисляющую функцию f. P: s:=k; P: s:=k; f[0]:=g(x 1,x 2,...,x n );f[0]:=g(x 1,x 2,...,x n ); for i=1 to s dofor i=1 to s do f[i]=h(x 1,x 2,...,x n, i-1, f[i-1]);f[i]=h(x 1,x 2,...,x n, i-1, f[i-1]); f :=f[s];f :=f[s];

23 Алгоритмы: Анализ и Построение23 Программисты записывают, обычно, P более экономно, но не функционально.Программисты записывают, обычно, P более экономно, но не функционально. P1 : s:=k; P1 : s:=k; f:=g(x 1,x 2,...,x n );f:=g(x 1,x 2,...,x n ); for i=1 to s dofor i=1 to s do f=h(x 1,x 2,...,x n,i-1,f);f=h(x 1,x 2,...,x n,i-1,f); Функция f называется примитивно рекурсивной относительно множества простейших функций, если она строится из простейших вычислимых функций конечным числом применения операторов суперпозиции и примитивной рекурсии.Функция f называется примитивно рекурсивной относительно множества простейших функций, если она строится из простейших вычислимых функций конечным числом применения операторов суперпозиции и примитивной рекурсии.

24 Алгоритмы: Анализ и Построение24 ПРИМЕР.ПРИМЕР. Рассмотрим примитивно рекурсивную схемуРассмотрим примитивно рекурсивную схему x+0=xx+0=x x+(y+1)=(x+y)+1=s(x+y)x+(y+1)=(x+y)+1=s(x+y) Следовательно, функция (x+y) строится применением оператора примитивной рекурсии R к примитивно рекурсивным функциям g(x)=х и h(x,y,z)=z+1. Следовательно, функция x+y примитивно рекурсивна.Следовательно, функция (x+y) строится применением оператора примитивной рекурсии R к примитивно рекурсивным функциям g(x)=х и h(x,y,z)=z+1. Следовательно, функция x+y примитивно рекурсивна.

25 Алгоритмы: Анализ и Построение25 Следует различать понятия алгоритмически вычислимой функции и алгоритма, а именно: пусть существует некоторая нерешенная математическая проблема x. Определим функцию h(x)= Ясно, что функция h(x)-константа (либо 0, либо 1) и, следовательно, примитивно рекурсивна. Однако алгоритм (примитивно рекурсивная схема) ее вычисления неизвестен, поскольку функции h(x)=0 и h(x)=1 вычисляются разными алгоритмами, а сделать правильный выбор невозможно (нет решения проблемы).

26 Алгоритмы: Анализ и Построение26 3.Оператор минимизации Пусть f - некоторая n-местная вычислимая функция, n 1, алгоритм вычисления f известен. Вычисление значения функции f для некоторого значения аргумента невозможно лишь тогда, когда алгоритм не может завершиться.Пусть f - некоторая n-местная вычислимая функция, n 1, алгоритм вычисления f известен. Вычисление значения функции f для некоторого значения аргумента невозможно лишь тогда, когда алгоритм не может завершиться. Зафиксируем некоторые значения первых n-1 переменных x 1, x 2,...,x n-1. Рассмотрим уравнениеЗафиксируем некоторые значения первых n-1 переменных x 1, x 2,...,x n-1. Рассмотрим уравнение f(x 1, x 2,...,x n-1,y)=x n (3)f(x 1, x 2,...,x n-1,y)=x n (3) Для его решения начнем вычислять последовательно значения функции f(x 1, x 2,...,x n-1,y) для y=0, 1, 2,.... Наименьшее число k такое, что f(x 1, x 2,...,x n-1,k)=x n есть решение этого уравнения. Это решение обозначается y (f(x 1, x 2,...,x n-1,y)=x n ). Решения может и не оказаться, например если:Для его решения начнем вычислять последовательно значения функции f(x 1, x 2,...,x n-1,y) для y=0, 1, 2,.... Наименьшее число k такое, что f(x 1, x 2,...,x n-1,k)=x n есть решение этого уравнения. Это решение обозначается y (f(x 1, x 2,...,x n-1,y)=x n ). Решения может и не оказаться, например если: - значения f(x 1, x 2,...,x n-1,k), k=0, 1, 2,,,, определены и отличны от x n, а значение f(x 1, x 2,...,x n-1,k+1) не определено,- значения f(x 1, x 2,...,x n-1,k), k=0, 1, 2,,,, определены и отличны от x n, а значение f(x 1, x 2,...,x n-1,k+1) не определено, - значения f(x 1, x 2,...,x n-1,k), k=0, 1, 2,..., все определены и отличны от x n.- значения f(x 1, x 2,...,x n-1,k), k=0, 1, 2,..., все определены и отличны от x n.

27 Алгоритмы: Анализ и Построение27 В таких случаях значение y (f(x 1, x 2,...,x n-1,y)=x n ) считается неопределенным. Величина y (f(x 1, x 2,...,x n-1, y)=x n ) зависит от значений переменных x 1, x 2,...,x n-1,x n и потому она может рассматриваться как значение функции от аргументов x 1, x 2,..., x n-1, x n. Эта функция обозначается f, называется оператором минимизации. В таких случаях значение y (f(x 1, x 2,...,x n-1,y)=x n ) считается неопределенным. Величина y (f(x 1, x 2,...,x n-1, y)=x n ) зависит от значений переменных x 1, x 2,...,x n-1,x n и потому она может рассматриваться как значение функции от аргументов x 1, x 2,..., x n-1, x n. Эта функция обозначается f, называется оператором минимизации. Оператор минимизации очевидно частично вычислим, а значит и функция f частично вычислима. Функция f называется частично рекурсивной относительно простейших функций, если она строится конечным числом применений операторов суперпозиции, примитивной рекурсии и минимизации.Оператор минимизации очевидно частично вычислим, а значит и функция f частично вычислима. Функция f называется частично рекурсивной относительно простейших функций, если она строится конечным числом применений операторов суперпозиции, примитивной рекурсии и минимизации.

28 Алгоритмы: Анализ и Построение28 Как и для оператора примитивной рекурсии для оператора минимизации можно построить представление в виде счетного множества функциональных термов. Введем предикат P(y i ):f(x 1, x 2,...,x n-1,y i )=x n. Тогда оператор минимизации представляется счетным множеством функциональных термов.

29 Алгоритмы: Анализ и Построение29 Предикат P(y i ) выделяет функциональный терм, который вырабатывает значение функции y (f(x 1, x 2,...,x n-1,y)=x n ). Предикат P(y i ) выделяет функциональный терм, который вырабатывает значение функции y (f(x 1, x 2,...,x n-1,y)=x n ). Из всех этих термов лишь один может выработать значение функции f, а именно тот, который выработает значение z k =x n для минимального k. Таким образом и здесь, как и в случае оператора примитивной рекурсии, операторный терм f представляется счетным множеством функциональных термов. Одно из существенных отличий состоит в том, что конечное множество функциональных термов, представляющих оператор примитивной рекурсии, фиксируется для конкретных значений до начала вычислений. В случае оператора минимизации терм, вычисляющий значение функции, определяется динамически в ходе вычисления.Из всех этих термов лишь один может выработать значение функции f, а именно тот, который выработает значение z k =x n для минимального k. Таким образом и здесь, как и в случае оператора примитивной рекурсии, операторный терм f представляется счетным множеством функциональных термов. Одно из существенных отличий состоит в том, что конечное множество функциональных термов, представляющих оператор примитивной рекурсии, фиксируется для конкретных значений до начала вычислений. В случае оператора минимизации терм, вычисляющий значение функции, определяется динамически в ходе вычисления.

30 Алгоритмы: Анализ и Построение30 Для конструирования программы, вычисляющей частично- рекурсивную функцию, оператора типа for уже недостаточно, нужен оператор типа while. Именно поэтому, любой процедурный язык программирования содержит операторы типа while. Следующая программа реализует оператор минимизации:Для конструирования программы, вычисляющей частично- рекурсивную функцию, оператора типа for уже недостаточно, нужен оператор типа while. Именно поэтому, любой процедурный язык программирования содержит операторы типа while. Следующая программа реализует оператор минимизации: P : z:=f(x 1, x 2,...,x n-1,0); P : z:=f(x 1, x 2,...,x n-1,0); i:=0;i:=0; while z x n do while z x n do { i:=i+1; i:=i+1; z:=f(x 1, x 2,...,x n-1,i); z:=f(x 1, x 2,...,x n-1,i); };}; f:=i; f:=i; Понятно, что эта программа не всегда останавливается и, следовательно, вычисляемая ею функция может оказаться не всюду определенной.Понятно, что эта программа не всегда останавливается и, следовательно, вычисляемая ею функция может оказаться не всюду определенной.

31 Алгоритмы: Анализ и Построение31 Было показано, что каждая частично рекурсивная функция представляется потенциально бесконечным множеством функциональных термов.Было показано, что каждая частично рекурсивная функция представляется потенциально бесконечным множеством функциональных термов. И наоборот, каждой программе может быть сопоставлено множество функциональных термов, определяющее тот алгоритм, что реализован программой. Например, программа покомпонентного сложения двух векторовИ наоборот, каждой программе может быть сопоставлено множество функциональных термов, определяющее тот алгоритм, что реализован программой. Например, программа покомпонентного сложения двух векторов n:=.... ;n:=.... ; for i = 1 to n dofor i = 1 to n do z[i]:=x[i]+y[i] ;z[i]:=x[i]+y[i] ; реализует алгоритм, представленный множеством термовреализует алгоритм, представленный множеством термов

32 Алгоритмы: Анализ и Построение32

33 Алгоритмы: Анализ и Построение33 Рассмотрим другой пример. n:=.... ; for i = 1 to n do if P(x[i])>0 then z[i]:=x[i]+y[i] else z[i]:=x[i]+y[i] ; Реализуемый программой алгоритм может быть представлен множеством функциональных термов:

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

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

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

37 Алгоритмы: Анализ и Построение37 Представление алгоритма A есть набор S=(X,F,C,M), где X={x,y,...,z} - конечное множество переменных, F={a,b,...,c} - конечное множество операций. C - управление, т. е. множество ограничений на порядок выполнения операций. Каждое ограничение определяет порядок исполнения пары операций вида (a

38 Алгоритмы: Анализ и Построение38 M - функция, задающая отображение множеств переменных и операций в физические устройства вычислительной системы (здесь обычно мультикомпьютер), т. е. M задает распределение ресурсов компьютера. Часть ограничений управления C, определенных информационной зависимостью между операциями, называется потоковым управлением, остальные ограничения C задают прямое управление, связанное обычно с распределением ресурсов. Чтобы перейти от алгоритма к программе в общем случае необходимо построить управление С и распределение ресурсов М

39 Алгоритмы: Анализ и Построение39 Реализацией алгоритма A, представленного в форме S, называется выполнение операций в некотором произвольном допустимом порядке, который не противоречит управлению C. Предполагается, что при любой реализации вычисляется функция F A, т.е. C всегда содержит потоковое управление, которое и гарантирует вычисление F A Множество всех реализаций алгоритма A, представленного в форме S, обозначим P(A,S). Если P(A,S) есть одноэлементное множество, то S - последовательное представление. S - параллельное представление алгоритма A, если множество P(A,S) содержит, более одной реализации

40 Алгоритмы: Анализ и Построение40 Пример 1.Пусть F=f(x 1,x 2 ), x 1 =g(y 1,...,y k ), x 2 =h(z 1,...,z m ) - операции, out(h)={x 2 }, out(g)=x 1, out(f)={f 0 }. Тогда алгоритм А вычисления функции F= f(g 1 (y 1,..., y k ), h=(z 1,...,z m ) представлен в параллельной форме S 1, f, g и h – операции Управление C в представлении S 1 - это отношение частичного порядка {(g

41 Алгоритмы: Анализ и Построение41 Допустим всякий порядок выполнения операций, при котором вычисление аргументов операции предшествует выполнению операции, управление C - потоковое, сохраняющее необходимые информационные зависимости между операциями. Уменьшить потоковое управление (например, разрешить операции f выполняться раньше операции g) нельзя, так как при этом будет вычисляться, вообще говоря, не функция F, а какая-то другая. В этом смысле потоковое управление есть минимальное управление, гарантирующее вычислений функции F. Множество реализаций алгоритма А, представленного в форме S1, состоит из трёх элементов

42 Алгоритмы: Анализ и Построение42 Если для хранения значений переменных используются ячейки памяти и заданы представления S 1 =(X,F,C 1,R 1 ) и S 2 =(X,F,C 2,R 2 ) алгоритма вычисления функции f=f(g(y 1,...,y k ),h(z 1,...,z m )). В S 2 потребуем, чтобы значения переменных алгоритма x 1 и z 1 хранились в одной и той же ячейке памяти. Тогда P(A,S 1 ) P(A,S 2 ), так как в силу сделанного распределения памяти для вычисления f прямое управление в С 2 должно теперь содержать требование, чтобы операция h выполнялась раньше g, то есть управление C 2 в представлении S 2 - это множество {(g

43 Алгоритмы: Анализ и Построение43 Пример 2. Алгоритм A задан в форме программы P, записанной на некотором последовательном языке программирования. Операторы языка, вычисляющие значения переменных, есть операции. Прямое управление задается последовательностью операторов в программе либо специальными операторами управления типа go to. Порядок выполнения операций полностью фиксирован. Распределение памяти задаётся идентификаторами переменных программы, которые фактически есть имена ячеек памяти, имена переменных алгоритма в программе не сохраняются. Предполагается, что для выполнения алгоритма может быть использован только один процессор.

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

45 Алгоритмы: Анализ и Построение45 Пример 4. Задание алгоритма формулами Исходный алгоритм умножения квадратных матриц сформулирован в терминах элементов матрицИсходный алгоритм умножения квадратных матриц сформулирован в терминах элементов матриц

46 Алгоритмы: Анализ и Построение46 a i,1 b 1,j a i,k b k,jb a i,K b K,j С i,j … … Исходный алгоритм 46ФП_iCAM

47 Алгоритмы: Анализ и Построение47 Диаграмма: алгоритм и программа 47ФП_iCAM

48 Алгоритмы: Анализ и Построение48 Ввод записей файла и их обработка

49 Алгоритмы: Анализ и Построение49 Если отображение M сопоставляет массиву y участок памяти, в котором может быть размещена лишь одна запись, и доступен только один процессор, тогда прямым управлением C должен быть задан следующий жестко определенный порядок выполнения операций: read(f,1), a 1, read(f,2), a 2,... (обычно в программе задается с использованием оператора цикла).Если отображение M сопоставляет массиву y участок памяти, в котором может быть размещена лишь одна запись, и доступен только один процессор, тогда прямым управлением C должен быть задан следующий жестко определенный порядок выполнения операций: read(f,1), a 1, read(f,2), a 2,... (обычно в программе задается с использованием оператора цикла). При таком порядке исполнения считанная запись файла будет потреблена операцией a, память освобождена, и следующая запись может быть считана в тот же участок памяти, что и предшествующая запись. Алгоритм A file будет правильно реализован, т.е. будет вычислена функция F Afile.При таком порядке исполнения считанная запись файла будет потреблена операцией a, память освобождена, и следующая запись может быть считана в тот же участок памяти, что и предшествующая запись. Алгоритм A file будет правильно реализован, т.е. будет вычислена функция F Afile.

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

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