Лекция 1. Алгоритмы.

2 План 1. Содержательное понятие алгоритма Содержательное понятие алгоритма 2. Императивный подход Императивный подход 3. Исполнитель (алгоритмов) и его система команд Исполнитель (алгоритмов) и его система команд 4. Основные свойства алгоритмов Основные свойства алгоритмов 5. Формы представления алгоритмов Формы представления алгоритмов 6. Абстракция данных Абстракция данных 7. Структуры данных Структуры данных 8. Базовые управляющие структуры Базовые управляющие структуры 9. Парадигма процедурного программирования Парадигма процедурного программирования

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

4 Термин «алгоритм» - Аль Хорезми (825 г.). Алгоритмами они называли правила арифметических действий над многоразрядным и числами.

5 XVII век В.Лейбниц идея формализации математики – т.е. построения универсального метода решения математических задач в виде системы правил манипулирования символами, с помощью которых эти задачи формулируются. В.Лейбниц ввел в употребление современную символику дифференциального и интегрального исчисления, в большой степени решившую задачу вычислений производных и интегралов при помощи формальных правил манипулирования символами.

6 Понятие алгоритма «Алгоритм это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.» (А. Колмогоров) «Алгоритм это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату.» (А. Марков) «Алгоритм строго детерминированная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд.» (Н. Угринович)

7 Понятие алгоритма Формальное понятие алгоритма было сформулировано как одно из понятий математической логики в 30-х годах XX века. в работах Э. Поста, А. Тьюринга, С. Клини, А. Черча и др. логиков. Несколько позже А.А. Марков ввел еще один формализм описания алгоритмов – т.н. нормальные алгорифмы Маркова. Пост, Эмиль Леон Алан Тьюринг Стивен Коул Клини (Клейни) Алонзо Чёрч А.А. Марков

8 Императивный подход Императивный подход состоит в уточнении способа описания алгоритма как последовательности шагов, на каждом из которых выполняется одна из т.н. инструкций (команд, операторов).

9 Алгоритм Алгоритм - это конечный набор инструкций по преобразованию информации (команд, операторов), выполнение которых приводит к результату. Каждая инструкция алгоритма содержит точное описание некоторого элементарного действия по преобразованию информации, а также (в явном или неявном виде) указание на инструкцию, которую необходимо выполнить следующей. С1С1 С2С2 С k-1 CkCk Вход Выход

10 Пример 1. Алгоритм сложения дробей Вход: A/B, C/D; 1. Вычислить Y = B*D; {Перейти к следующей команде} 2. Вычислить X1 = A*D; {Перейти к следующей команде} 3. Вычислить X2 = B*C; {Перейти к следующей команде} 4. Вычислить X = X1+X2; {Перейти к следующей команде} 5. Вычислить Z = НОД(X,Y); {Перейти к следующей команде} 6. Вычислить Е = X div Z; {Перейти к следующей команде} 7. Вычислить F = Y div Z; {Закончить работу}. Выход: E/F

11

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

13 Исполнителя хаpактеpизуют: сpеда; элементаpные действия; cистема команд; отказы.

14 Исполнитель операций целочисленной арифметики сложение, вычитание, умножение, вычисление неполного частного (div) и остатка (mod), вычисление НОД и НОК запоминание результатов и умение переходить к следующей команде. X = НОД((A + B) div 100, (A * B - 7) mod 10)

15 Алгоритм деления отрезка пополам с помощью циркуля и линейки Вход: Отрезок AB; Построить окружность O1 с центром A и радиусом AB; Построить окружность O2 с центром B и радиусом AB; Найти точки С и D пересечения окружностей O1 и O2; Построить отрезок CD; Найти точку Е пересечения AB и CD. Выход: Точка Е - середина отрезка AB. В примере 2 Исполнитель обладает системой команд, с помощью которых можно решать геометрические задачи на построения с помощью циркуля и линейки.

16 Алгоритм решения приведенного квадратного уравнения x 2 + px + q = 0; Вход: Коэффициенты p и q уравнения x 2 + px + q = 0; Вычислить D = p 2 - 4q; Если D < 0 то (ответить Решений нет; Перейти к 1); Если D = 0 то (вычислить x = -p/2; Перейти к 1); Вычислить x1 = (-p+ (D))/2; Вычислить x2 = (-p- (D))/2); 1:Закончить работу. Выход Решений нет или корень x или корни x1, x2.

17 Алгоритм решения приведенного квадратного уравнения (объяснение) выбирающие, условные команды или ветвления. Если то ( ) Команды перехода Перейти к

18 Основные свойства алгоритмов Элементарность. Каждая команда из набора команд Исполнителя содержит указание выполнить некоторое элементарное (не детализируемое более подробно) действие, однозначно понимаемое и точно выполняемое Исполнителем. Дискpетность (прерывность, раздельность) алгоpитм должен пpедставлять пpоцесс pешения задачи как последовательное выполнение пpостых (или pанее опpеделенных) шагов (этапов). Определенность. Исполнение алгоритма строго определено. Это означает, что на каждом шаге Исполнитель не только точно выполняет команду, но и однозначно определяет следующую исполняемую команду. Поэтому повторное выполнение алгоритма для одних и тех же исходных данных в точности повторяет первое его выполнение.

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

20 Элементарность. Каждая команда из набора команд Исполнителя содержит указание выполнить некоторое элементарное (не детализируемое более подробно) действие, однозначно понимаемое и точно выполняемое Исполнителем. Пример Алгоритм Евклида вычисления наибольшего общего делителя целых положительных чисел A и B: НОД(A, B). Вход A, B; Вычислить U = A; Вычислить V = B; Пока U V выполнять Если U < V то Вычислить V = V - U иначе Вычислить U = U - V; Вычислить D = U. Выход: D - наибольший общий делитель A и B.

21 Формы представления алгоритмов: словесная (запись на естественном языке); графическая (изображения из графических символов); псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.); программная (тексты на языках программирования).

22 Абстракция данных Примеры Исполнителей, рассмотренные выше, используют абстрактные представления о предметных областях, над которыми определяются алгоритмы. Понятие Исполнителя является одной из основных абстракций, используемых для описания алгоритмов. Именно система команд Исполнителя и есть уточнение набора средств, с помощью которых строятся алгоритмы.

23 Абстракция данных Разработчик конкретного прикладного алгоритма (программист) либо проектирует его в терминах ранее определенного набора команд Исполнителя, либо предварительно описывает (проектирует) систему команд Исполнителя, создавая тем самым понятийный аппарат и инструментарий предметной области Исполнителя, а затем использует его в описании прикладного алгоритма.

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

25 Структура данных состоит из трех основных компонент: Набор предметно-ориентированных операций для обработки специфических типов абстрактных объектов описываемой предметной области. Структура памяти, в которой хранятся данные, описывающие абстрактные объекты. Интерпретация (реализация) каждой из операций в терминах структуры памяти. Первая компонента определения – набор операций над абстрактными объектами – называется абстрактным типом данных (АТД). АТД определяет, что делает структура данных - какие операции она поддерживает, не раскрывая, как они выполняются. Вторая и третья компоненты вместе образуют реализацию структуры данных.

26 Пример. АТД Планиметрия. Примитивные типы объектов: точка, прямая, окружность. Примитивные операции: –Line: (точка, точка) прямая l = Line(A, B) определяет прямую l, проходящую через точки A, B –Circle: (точка, точка) окружность o = Circle(A, B) определяет окружность о с центром в т. А, проходящую через т. В. –CircleRad: (точка, точка, точка) окружность o = CircleRad(A, B, C) определяет окружность о с центром в т. А, построенную раствором циркуля c ножками, установленными в B, C. –IntersectLines(прямая, прямая) точка A = Intersect(l, m) определяет точку пересечения прямых l и m –IntersectCircles(окружность, окружность) (точка, точка) (A, B) = IntersectCircles(o, p) определяет пару точек A, B пересечения окружностей o и p. –IntersectLineCircle(прямая, окружность) (точка, точка) (A, B) = IntersectLineCircle(l, o) определяет пару точек A, B пересечения прямой l и окружности o.

27 Пример. АТД Планиметрия. Из примитивных типов объектов АТД Планиметрия можно теперь строить т.н. составные типы. Например тип треугольник можно определить как тройку точек (вершин) Треугольник = (точка, точка, точка) Из примитивных (основных) операций АТД можно определять производные операции. Например, операция ParralelLine: (точка, прямая) прямая, результатом которой является прямая, проходящая через данную точку и параллельная данной прямой. Использование АТД приводит к применению модульного подхода к алгоритмизации (программированию), т.е. практике разбиения алгоритма на отдельные модули (библиотеки) с хорошо отработанным интерфейсом.

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

29 Команды управления. Синтаксис Алгоритмы должны быть определены точно и недвусмысленно, форма их записи (нотации) должна быть определена с математической точностью. Синтаксические правила Совокупность синтаксических правил описания алгоритмов определяет формально–языковую среду – алгоритмический язык. Совокупность синтаксических правил, определяющих описание алгоритма, можно разбить на две группы: правила описания данных; правила описания операторов. Семантика Совокупность правил, определяющих выполнение алгоритма, можно также разбить на две группы: правила интерпретации данных; правила интерпретации операторов.

30 Алгоритм Евклида вычисления НОД двух натуральных чисел: Алгоритм Evclid; Начало Вход(a,b); u := a; v := b; Пока u v выполнить начало w := u - v; Если w > 0 то u := w иначе v := -w; конец; Выход(u) конец.

31 Приближенное (с заданной точностью Eps) решение уравнения f(x) = 0 методом деления отрезка пополам: Алгоритм EquationSol; Начало Вход(a, b, Eps); u := a; v := b; Пока u - v >= Eps выполнить начало w := (u + v)/2; Если f(u)*f(w) > 0 то u := w иначе v := w; конец; Выход(u) Конец.

32 Структура алгоритма: Начало ; Пока выполнить начало ; Если то иначе ; конец; Конец.

33 Структура алгоритма на языке блок схем: Ввод Инициализация Оператор Условие Оператор Условие

34 К основным структурам управления относятся: последовательное выполнение ветвление повторение фрагмент 1 фрагмент 2 Оператор 1 Оператор 2 условие True Условие Оператор True

35 Базовая структура "следование". Образуется последовательностью действий, следующих одно за другим: Школьный алгоритмический язык Язык блок-схем действие 1 действие действие n 2 n

36 Базовая структура "ветвление" Обеспечивает в зависимости от результата проверки условия (да или нет) выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран. Структура ветвление существует в четырех основных вариантах: еслито; еслитоиначе; выбор; выбориначе.

37

38

39 Примеры структуры ветвление

40 Примеры структуры ветвление

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

42 Примеры структуры цикл

43 Описание алгоритмов в терминах структур данных и структур управления называют структурным программированием. Особую роль в структурном программировании играют процедуры и функции - основные семантические единицы проектируемого алгоритма, содержащие описания отдельных подзадач, имеющих самостоятельное значение. Процедуры содержат описания интерпретаций (реализаций) АТД. Структурный подход называют также процедурным программированием. Программирование управления – описание управления алгоритма - осуществляется комбинированием основных управляющих структур.

44 Структура управление любого алгоритма может быть реализована в виде комбинации основных управляющих структур. Оператор перехода Перейти_к_ оператор Goto не включен ни в список основных, ни дополнительных управляющих операторов. Поэтому структурное программирование иногда называют программированием без Goto. Оператор Условие Основной результат

45 Ключевым аспектом семантического определения операторов управления является понятие условия. Как правило, в алгоритмических системах условия определяются в терминах АТД - т.н. логического типа. Логический тип имеет два значения – F и T, также функционально полный набор логических операций (and, or, xor, not, …) со стандартными интерпретациями алгебры высказываний (т.н. таблицы истинности логических связок). Семантика операторов управления

46 Каждый предметно-ориентированный АТД имеет, как правило, несколько операций логического типа. Например, АТД «натуральные числа» должен содержать операции логического типа (, >=, =, ). Семантика оператора Если U то P иначе Q U = T Если U то P иначе Q =df= P U = F Если U то P иначе Q =df= Q Семантика операторов управления

47 Важную роль в семантическом описании управляющих операторов играет понятие неопределенности. Неопределенность возникает как следствие того, что некоторые операции АТД вообще говоря, частично определены. Так, операция A/B не определена при B = 0. Еще один источник неопределенности – бесконечно повторяющиеся циклы. Оператор Пока T выполнять P не определен, причем эта неопределенность не может быть раскрыта Не существует конструктивного способа (алгоритма), который по описанию цикла распознавал бы, завершится ли этот цикл, или нет. Семантика операторов управления

48 Полные семантические описания управляющих операторов обязаны содержать правила учета неопределенностей. Для обозначения неопределенности введем специальный символ. Тогда семантика оператора Если U то P иначе Q дополняется равенством U = Если U то P иначе Q =df= Семантика операторов управления

49 Основная идея, методология (парадигма) обсуждаемого подхода к определению алгоритма может быть выражена «формулой» Н.Вирта: АТД + Структуры управления = Алгоритмы Алгоритмы + структуры данных = программы Парадигма процедурного программирования

50 Спасибо за внимание!