Понятие, свойства и способы описания алгоритмов Прокопьева Т.В. 2009 год. - презентация

1 Понятие, свойства и способы описания алгоритмов Прокопьева Т.В год

2 Свойства алгоритма При разработке алгоритмов следует учитывать ряд требований, совокупность которых формирует его свойства. Из основных свойств алгоритма выделим: определенность, определенность, определенность дискретность, дискретность,дискретность конечность, конечность,конечность результативность, результативность, результативность рациональность, рациональность, рациональность массовость. массовость.массовость

3 определенность Указания, составляющие алгоритм, должны быть четкими и однозначными, не допускать произвольного или двоякого толкования. Это свойство называют определенностью. Оно является гарантией того, что алгоритм может быть выполнен объектами, не обладающими интеллектуальными способностями, в частности ПЭВМ. При составлении алгоритма нельзя рассчитывать на профессионального исполнителя, который может проанализировать и как-то исправить ход решения задачи в случае необходимости. Указания, составляющие алгоритм, должны быть четкими и однозначными, не допускать произвольного или двоякого толкования. Это свойство называют определенностью. Оно является гарантией того, что алгоритм может быть выполнен объектами, не обладающими интеллектуальными способностями, в частности ПЭВМ. При составлении алгоритма нельзя рассчитывать на профессионального исполнителя, который может проанализировать и как-то исправить ход решения задачи в случае необходимости.

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

5 Конечность, результативность Вычислительный процесс после выполнения заданной алгоритмом конечной последовательности действий должен заканчиваться выдачей результатов или сообщением о невозможности решить задачу. Эти взаимосвязанные свойства алгоритма называются конечностью и результативностью. Вычислительный процесс после выполнения заданной алгоритмом конечной последовательности действий должен заканчиваться выдачей результатов или сообщением о невозможности решить задачу. Эти взаимосвязанные свойства алгоритма называются конечностью и результативностью. ПРИМЕР

6 Для иллюстрации этих свойств алгоритма рассмотрим вычисление значения функции sin(х) методом разложения ее в ряд по степеням аргумента по известной формуле: Очевидно, что при расчете по подобной формуле окончательного ответа мы не получим, поскольку в условии задачи ничего не говорится о количестве членов ряда, которые необходимо учитывать при вычислениях. Без подобных указаний вычислительный процесс может продолжаться сколь угодно долго, то есть «бесконечно». Чтобы этого не произошло, следует ввести некоторые ограничения, обеспечивающие свойство конечности алгоритма, в частности задать некоторое допустимое число шагов выполнения алгоритма. Например, суммирование продолжать до тех пор, пока значение очередного, учитываемого в сумме члена ряда не станет меньше некоторого E, равного В этом случае за некоторое конечное число шагов будет получен результат и алгоритм вычисления функции приобретет свойство результативности. Очевидно, что при расчете по подобной формуле окончательного ответа мы не получим, поскольку в условии задачи ничего не говорится о количестве членов ряда, которые необходимо учитывать при вычислениях. Без подобных указаний вычислительный процесс может продолжаться сколь угодно долго, то есть «бесконечно». Чтобы этого не произошло, следует ввести некоторые ограничения, обеспечивающие свойство конечности алгоритма, в частности задать некоторое допустимое число шагов выполнения алгоритма. Например, суммирование продолжать до тех пор, пока значение очередного, учитываемого в сумме члена ряда не станет меньше некоторого E, равного В этом случае за некоторое конечное число шагов будет получен результат и алгоритм вычисления функции приобретет свойство результативности.

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

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

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

10 Словесный способ записи алгоритмов представляет собой описание последовательности действий по обработке данных на естественном языке человеческого общения. Очевидные преимущества: доступность и простота использования. Недостатки: алгоритмы плохо формализуемы, громоздки и ненаглядны. Словесный способ записи алгоритмов представляет собой описание последовательности действий по обработке данных на естественном языке человеческого общения. Очевидные преимущества: доступность и простота использования. Недостатки: алгоритмы плохо формализуемы, громоздки и ненаглядны. Структурно-стилизованный способ записи основан на применении естественного языка в формализованном представлении предписаний, конструкции которого близки к конструкциям структурных языков программирования. Примером такого способа является предложенный академиком А. П. Ершовым алгоритмический язык в русской нотации (АЯРН), известный многим из школьной дисциплины «Информатика». Структурно-стилизованный способ записи основан на применении естественного языка в формализованном представлении предписаний, конструкции которого близки к конструкциям структурных языков программирования. Примером такого способа является предложенный академиком А. П. Ершовым алгоритмический язык в русской нотации (АЯРН), известный многим из школьной дисциплины «Информатика». В этом языке введен ограниченный набор типовых синтаксических конструкций (псевдокодов), представленных в понятном для разработчика и пользователя виде и позволяющих запись алгоритма осуществить в формализованной и более выразительной форме. Например, в языке АЯРН начало алгоритма кодируется как нач, конец кон, признаком заголовка является ключевое слово алг и т. д.

11 О графическом способе Наиболее распространенным способом представления алгоритма является графический. В графическом представлении алгоритмы изображаются в виде блок-схемы, дополненной элементами словесной или математической записи. Схема алгоритма включает геометрические фигуры (блочные символы), соединенные между собой стрелками (линиями), указывающими порядок выполнения операций. Блочные символы стандартизированы и различаются по типу выполняемых действий ( ГОСТ и ,. международные стандарты ИСО или ИСО ). Наиболее распространенным способом представления алгоритма является графический. В графическом представлении алгоритмы изображаются в виде блок-схемы, дополненной элементами словесной или математической записи. Схема алгоритма включает геометрические фигуры (блочные символы), соединенные между собой стрелками (линиями), указывающими порядок выполнения операций. Блочные символы стандартизированы и различаются по типу выполняемых действий ( ГОСТ и ,. международные стандарты ИСО или ИСО ).

12 Графический способ блок-схема В схеме начало и завершение алгоритма, а также вход и выход из вспомогательных алгоритмов, отмечаются соответственно блочными символами «начало» и «конец» (рис. 1.1 а и 1.16, блоки 1 и 2). Эти блоки, в отличие от большинства других, имеют один вход или один выход, отмечающие как бы начало и конец пути обработки информации. Каждая схема обязательно должна начинаться и заканчиваться этими символами. В схеме начало и завершение алгоритма, а также вход и выход из вспомогательных алгоритмов, отмечаются соответственно блочными символами «начало» и «конец» (рис. 1.1 а и 1.16, блоки 1 и 2). Эти блоки, в отличие от большинства других, имеют один вход или один выход, отмечающие как бы начало и конец пути обработки информации. Каждая схема обязательно должна начинаться и заканчиваться этими символами.

13 Графический способ блок-схема Изображенные на рис. 1.1 в и 1.1 г блочные символы в виде параллелограмма (блоки 3 и 4) используют для обозначения операций ввода-вывода данных. Изображенные на рис. 1.1 в и 1.1 г блочные символы в виде параллелограмма (блоки 3 и 4) используют для обозначения операций ввода-вывода данных.

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

15 Графический способ блок-схема Логический блочный символ «решение» (рис. 1.1 ж-и, блоки 6, 7, 8 соответственно) используют для обозначения выбора направления выполнения алгоритма в зависимости от некоторого условия (условий). В блоке указывают условие, вопрос или решение, определяющие дальнейшее направление выполнения алгоритма. Условия могут быть простыми (рис. 1./1 ж, блок 6) и составными (рис. 1.1 и, блок 8). В них должны быть учтены абсолютно всевозможные варианты следования процесса при решении задачи. Из блока проверки условия может выходить два или три информационных потока, что отличает его от других блочных символов, имеющих не более одного выхода. Выходящие из блока линии должны снабжаться пояснениями о направлениях исполнения ' алгоритма при выполнении или невыполнении приведенного условия (например, «да», «нет», «<0», «=0», «>0», «+», «-» или др.).

16 Блочный символ модификации (рис. 1.1 к и 1.1 л, блоки 9 и 10) символизирует начало циклических вычислений (заголовок цикла), для управления которыми он используется. Внутри блока указывается переменная цикла и параметры, характеризующие закон ее изменения, например, I = Анач, Акон, ΔА, где I _ переменная цикла, Анач и Акон - начальное и конечное значения переменной цикла, ΔА - шаг ее изменения (переменная цикла изменяется от Анач до Акон с шагом Δ А). Если шаг равен 1, то Δ А можно не указывать. Кроме входящей линии блок модификации имеет одну выходящую (на рис. 1.1 л обозначенную «Вых»), а также линии, отмечающие передачу вычислительного процесса на обработку для циклических вычислений «Цикл» и возврат в начало для изменения переменной цикла «Изм. пер.».

17 Графический способ блок-схема Для уменьшения количества пересечений и длины линий, символизирующих пути следования информационных потоков, допускается их разрывать, вставляя в места разрыва соединители. Если линия разрывается между блоками, размещенными на одной странице, то в качестве соединителя используют соответствующие символы (рис. 1.1 и и 1.1 о). В блочный символ вписывают номера блоков, в которые вычислительный процесс передается или из которых он поступил. Так, соединитель на рис. 1.1 н указывает, что вычислительный процесс передается на вход блока 15, а соединитель на рис. 1.1 о, что вычислительный процесс поступил из выхода блока 10.

18 Графический способ блок-схема Если же линии соединяют блоки, расположенные на разных страницах, то используется символ межстраничного соединителя, в который вписывают не только номера блоков, но и номера страниц. В изображенном на рис. 1.1 п в межстраничном соединителе указано, что вычислительный процесс передается на вход блока 23, расположенного на странице 10. На входе блока 23 будет стоять приведенный на рис. 1.1 р межстраничный соединитель (информация передана с выхода блока 12, расположенного на странице 6). Если же линии соединяют блоки, расположенные на разных страницах, то используется символ межстраничного соединителя, в который вписывают не только номера блоков, но и номера страниц. В изображенном на рис. 1.1 п в межстраничном соединителе указано, что вычислительный процесс передается на вход блока 23, расположенного на странице 10. На входе блока 23 будет стоять приведенный на рис. 1.1 р межстраничный соединитель (информация передана с выхода блока 12, расположенного на странице 6).

19 Графический способ блок-схема Для пояснений особенностей функционирования отдельных блоков или групп блоков, принятых допущений и назначений от­дельных элементов, обозначений переменных и др. в схемы алгоритмов могут включаться комментарии (рис. 1.1 с). Для пояснений особенностей функционирования отдельных блоков или групп блоков, принятых допущений и назначений от­дельных элементов, обозначений переменных и др. в схемы алгоритмов могут включаться комментарии (рис. 1.1 с).

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

21 Графический способ блок-схема В схеме блоки, за исключением соединителей, могут нумероваться для простоты дальнейшего описания их работы, организации комментариев и использования соединителей. Номера проставляют в верхней части графического символа в разрыве его начертания, как это сделано на рис В схеме блоки, за исключением соединителей, могут нумероваться для простоты дальнейшего описания их работы, организации комментариев и использования соединителей. Номера проставляют в верхней части графического символа в разрыве его начертания, как это сделано на рис. 1.1.

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

23 Разработка алгоритма Алгоритмы целесообразно разрабатывать поэтапно (по шагам). Сложные задачи следует разбивать на достаточно простые, легко воспринимаемые части. Логика алгоритма должна опираться на минимальное число достаточно простых управляющих базовых структур. При разработке схем алгоритмов необходимо соблюдать некоторые требования: Алгоритмы целесообразно разрабатывать поэтапно (по шагам). Сложные задачи следует разбивать на достаточно простые, легко воспринимаемые части. Логика алгоритма должна опираться на минимальное число достаточно простых управляющих базовых структур. При разработке схем алгоритмов необходимо соблюдать некоторые требования: В схеме алгоритма все линии от блока «начало» до блока «конец» не должны иметь разрывов, не помеченных соединителями. Все линии, указывающие последовательность выполнения действий, должны быть замкнутыми. В схеме алгоритма все линии от блока «начало» до блока «конец» не должны иметь разрывов, не помеченных соединителями. Все линии, указывающие последовательность выполнения действий, должны быть замкнутыми. В схеме должны четко прослеживаться потоки информации. В схеме должны четко прослеживаться потоки информации. Блоки следует размещать таким образом, чтобы избегать пе­ ресечения линий. При передаче управления в схеме «снизу- вверх» или «справа-налево» линии обязательно помечают стрелками. Блоки следует размещать таким образом, чтобы избегать пе­ ресечения линий. При передаче управления в схеме «снизу- вверх» или «справа-налево» линии обязательно помечают стрелками. Не допускается передача управления в никуда. «Источник» передачи управления и «получатель» должны быть четко обозначены. Не допускается передача управления в никуда. «Источник» передачи управления и «получатель» должны быть четко обозначены.

24 Домашнее задание Подготовить 10 вопросов для взаимопроверки. Подготовить 10 вопросов для взаимопроверки. Знать ряд для вычисления значения синуса. Знать ряд для вычисления значения синуса. Знать алгоритм Евклида. Знать алгоритм Евклида. *Найти другие варианты записи алгоритма Евклида. *Найти другие варианты записи алгоритма Евклида.