Основные свойства алгоритмов
Алгоритм относится кфундаментальным понятиям информатики. На понятии алгоритма построено все основные принципы программирования - составления программ для вычислительных машин.
Алгоритм - это совокупность действий со строго определенными правилами выполнения. В информатике изучаются различного рода алгоритмы - диалоговые алгоритмы, алгоритмы обработки данных, вычислительные алгоритмы, алгоритмы управления роботами, станками и другими техническими устройствами.
Пример диалогового алгоритма:
Алгоритм Блок-схема
алг «приветствие» ¯
нач запрос («Ваше имя=», NN)
запрос («Ваше имя=», NN) ¯
вывод («Добрый день», NN) вывод («Добрый день», NN)
кон ¯
Дляописания алгоритмов используются блок-схемы, изображенные справа, или структурированная запись, приведенная слева. Блок-схемы наглядны. Однако блок-схемы трудно рисовать, в них сложно вносить изменения и исправления из-за сложности перерисовки рамок и стрелок. Однако блок-схемы до сих пор требуются отечественными стандартами на документирование программ.
Достоинство записи алгоритмов и программ в структурированной форме заключается впростоте их чтения и ввода с экрана ЭВМ, а также в простоте внесения изменений и исправлений с использованием даже самых простейших редакторов тестов. По этим причинам зарубежом блок-схемы уже давно не используются ни для документирования, ни для обучения, а все современные языки построены на принципах структурного программирования.
Приведем примеры описания алгоритма и программы в структурированной записи:
АлгоритмПрограмма
алг «приветствие» ' приветствие
нач сls
запрос («Ваше имя=», NN) input «Ваше имя=», NN$
вывод («Добрый день», NN) print «Добрый день», NN$
кон end
Алгоритм, приведенный слева, записан на псевдокоде.Псевдокод - это язык записи структурированных алгоритмов в качестве документации к программам для ЭВМ. Особенность псевдокода заключается в том, что описания на нем выполняются на родном языке — русском, английском, украинском, казахском, немецком и т. п.
Программа, приведенная справа, записана на языкеБейсик - языке программирования персональных ЭВМ. Языками программирования называются формализованные языки, используемые для записи программ на ЭВМ. Одним из них является язык Бейсик.
Достоинства псевдокода заключаются в том, что описания алгоритмов, записанные на родном языке, намного проще читать и понимать, чем запись программ на языке с иностранной лексикой. По этим причинам псевдокод используется как основное средство документирования программ во всех ведущих фирмах, занимающихся разработкой программ.
С точки зрения информатики алгоритмы, записанные в такой обобщенной записи, позволяют выразить общуюлогику работы программ, независимо от используемых языков программирования и типов ЭВМ. При этом алгоритмы, записанные в такой обобщенной форме, могут быть реализованы с помощью различных языков программирования для самых различных типов ЭВМ.
В качестве примера приведем реализацию этого же диалогового алгоритма на самой ранней версии языка Бейсик, использовавшегося на самых первых персональных компьютерах:
АлгоритмПрограмма
алг «приветствие» 10 ' приветствие
нач 20 сls
запрос («Ваше имя=», NN) 30 input «Ваше имя=», NN$
вывод («Добрый день», NN) 40 print «Добрый день», NNS
кон 50 end
Основные свойства алгоритмов и программ для вычислительных машин - однозначность, результативность, правильность и массовость. Этими свойствами алгоритмы отличаются от различного рода расплывчатых и неоднозначных предписаний, инструкций и кулинарных рецептов, которые могут толковаться и исполняться многими способами.
Однозначность алгоритмов - это однозначность правил их выполнения. Следствием этого свойства алгоритмов является однозначность результатов их выполнения в одинаковых начальных условиях. Это не всегда верно для кулинарных рецептов, когда разные исполнители в одних и тех же условиях могут придавать различный вкус и пикантность одним и тем же блюдам.
Результативность - это завершение выполнения алгоритмов определенными результатами. Результативность - наиболее важное свойство алгоритмов и программ, предназначенных для решения прикладных задач. Алгоритмы и программы, не дающие результатов или ведущие к сбоям и отказам, никому не нужны.
Массовость - это возможность применения алгоритмов в различных конкретных исходных условиях. Массовые алгоритмы особенно важны для решения прикладных задач, когда алгоритмы и программы должны обеспечить решение целого класса задач, различающихся исходными данными.
Правильность алгоритмов определяется правильностью результатов, получаемых с их помощью. По этой причине правильность алгоритмов и программ является относительным понятием. Оценка правильности может проводиться только при наличии требований к конечным результатам.
Алгоритм считаетсяправильным, если он дает правильные результаты для любых допустимых начальных условиях. Правильность алгоритмов гарантирует правильность результатов их выполнения.
Алгоритм содержитошибки, если его выполнение может привести к отказам, сбоям или неправильным результатам, либо вовсе не дает никаких результатов. Эти ошибки называются алгоритмическими. Алгоритмы и программы, содержащие такие ошибки, могут нанести вред или ущерб тем, кто захочет ими воспользоваться.
Для оценки правильности алгоритмов и программ необходимо уметь оценивать результаты выполнения составляющих их действий и конечные результаты их выполнения в целом.
Простейшие виды машинных операций - операции присваивания. С помощью присваивании в алгоритмах описываются вычисления в программах для ЭВМ. Рассмотрим примеры операций присваивания и описания результатов их выполнения.
Присваивания: Результаты:
а := 0 а = 0
b := а + 1 b ' = а + 1 = 1
b := b + 1 b " = b' + 1 = 2
Запись присваиваний читается:
а := 0 - «переменной а присвоить значение0»;
b := b + 1 - «переменной b присвоить значение b + 1».
Записи в колонке результатов читаются так:
а = 0 - «значение а равно 0»;
b' =b +1 - «значениеb' равно b + 1».
Здесьаиb - программные переменные - область машинной памяти, в которой хранятся их значения аи b. В отличии от обычных математических переменных программные переменные могут получать новые значения. В частности, присваиваниеb: = b + 1 записывает в программную переменную b новое значениеb', равное величине b + 1, где b - прежнее значение переменной b.
Для описания результатов выполнения алгоритмов и программ могут и должны использоватьсяспецификации. Спецификации - это точные, математически строгие описания. Примерами спецификаций могут служить сценарии диалоговых программ.
Сценарии диалоговых алгоритмов и программ - это совокупность текстов, картинок и сообщений, появляющихся на экранах ЭВМ. Рассмотрим в качестве примера сценарий алгоритма рисования домика на экране ЭВМ.
Сценарий«Домик»
 |
Решение - следующие алгоритм и программа, результатом работы которых должен быть приведенный выше рисунок:
АлгоритмПрограмма
алг «Домик» ' Домик
нач screen 2,0
линия (130,40)-( 100,100), красная line (150,40)-(100,100),8
линия (130,40)-(200,100), красная line (150,40)-(200,100),8
рамка(100,100)-(200,200), белая line (100,100)-(200,200),15,b
рамка(130,120)-(170,160), синяя line (130,120)-(170,160),3,b
кон end
Однако результатом выполнения приведенных алгоритма и программы будет следующий рисунок:
Экран ЭВМ
 |
Причиной того, что на этом рисунке крыша «поехала» влево, являются алгоритмические ошибки - неправильный расчет координат крыши в алгоритме, из-за чего составленная программа дает не тот рисунок, который указан в сценарии.
Примером прикладного алгоритма и программы может служить следующий алгоритм расчета прибыли:
Алгоритм Программа
алг «расчет прибыли» ' расчет прибыли
нач сls
запрос («доходы =», d) input «доходы =», d
запрос («расходы =», r) input «расходы =», r
р: = d - r р = d - r
вывод («прибыль =», р) print «прибыль =», р
кон end
Сценарий диалогаПротокол диалога
доходы =?<d> доходы =? 1000
расходы =? <г> расходы =? 700
прибыль = <р> прибыль = 300
Для проверки правильности алгоритма и программы необходима постановка задачи. Приведем строгую постановку решаемой задачи.
Задача: расчет прибыли.
Треб.: р - прибыль.
Дано: r - расходы;
d - доходы.
Где: d = r + р.
При:d > 0.
Для оценки правильности полученных результатов нужно сверить расходы и прибыль с доходами. В нашем случае это должно быть 700 + 300 = 1000, что выражает правильный конечный результат при указанных данных.
Для оценки правильности алгоритма и программы необходимо рассмотреть конечные результаты их выполнения при произвольных значениях данных d и г. Вычисляемая величина р по алгоритму будет равна
ОперацияРезультат
р := d - r р = d – r
Подставляя в условие постановки задачи это значение, получаем:
d = r + p = r + (d - r) = d - верное тождество.
Таким образом, при любых значениях исходных данных результаты выполнения приведенного алгоритма будут правильными.