Основные свойства алгоритмов

 

Алгоритм относится к фундаментальным понятиям информатики. На понятии алгоритма построены все основные принципы программирования — составления программ для вычислительных машин.

Алгоритм — это совокупность действий со строго определенными правилами выполнения. В информатике изучаются различного рода алгоритмы — диалоговые алгоритмы, алгоритмы обработки данных, вычислительные алгоритмы, алгоритмы управления роботами, станками и другими техническими устройствами.

Пример диалогового алгоритма:

 

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

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

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

Достоинство структурированной записи алгоритмов заключается в простоте их чтения и ввода с экрана ЭВМ. По форме они могут просто совпадать с записью программ, а разница между ними в том, что алгоритмы записываются на родном языке, понятном широкому кругу людей, а программы — на языке программирования, понятном компьютерам.

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

Приведем примеры описания алгоритма и программы в структурированной записи:

 

АлгоритмПрограмма

алг «приветствие» ' приветствие

нач сls

запрос(«Ваше uмя=»,NN) input «Ваше имя=»,NN$

вывод(«Добрый дeнь»,NN) print «Добрый дeнь»,NN$

кон end

 

Алгоритм, приведенный слева, записан на псевдокоде. Псевдокод — это язык записи структурированных алгоритмов в качестве документации к программам для ЭВМ. Особенность псевдокода заключается в том, что описания на нем выполняются на родном языке — русском, английском, украинском, казахском, немецком и т. п.

Программа, приведенная справа, записана на языке Бейсик — языке программирования персональных ЭВМ. Языками программирования называются формализованные языки, используемые для записи программ на ЭВМ. Одним из них является язык Бейсик.

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

С точки зрения информатики алгоритмы, записанные в такой обобщенной записи, позволяют выразить общую логику работы программ независимо от используемых языков программирования и типов ЭВМ. При этом алгоритмы, записанные в такой обобщенной форме, могут быть реализованы с помощью различных языков программирования для самых различных типов ЭВМ.

В качестве примера приведем реализацию этого же диалогового алгоритма на самой ранней версии языка Бейсик, использовавшегося на самых первых персональных компьютерах:

АлгоритмПрограмма

алг «приветствие» 10 ' приветствие

нач 20 сls

запрос(«Ваше uмя=»,NN) 30 input «Ваше имя=», NN$

вывод(«Добрый день»,NN) 40 print «Добрый день»,NN$

кон 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

расходы =? <r> расходы =? 700

прибыль = <р> прибыль = 300

 

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

Задача: расчет прибыли.

Треб: р — прибыль.

Дано: r — расходы;

d — доходы.

Где: d = r + р.

При: d > 0.

 

Для оценки правильности полученных результатов нужно сверить расходы и прибыль с доходами. В нашем случае это должно быть 700 + 300 = 1000, что выражает правильный конечный результат при указанных данных.

Для оценки правильности алгоритма и программы в целом необходимо рассмотреть конечные результаты их выполнения при произвольных значениях данных d и r. Вычисляемая величина р по алгоритму будет равна:

 

ОперацияРезультат

p:= d - r р = d - r

Подставляя в условие постановки задачи это значение, получаем:

d = r + p = r + (d— r) = d — верное тождество.

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

Вопросы

 

1. Что такое алгоритм?

2. Каковы основные виды алгоритмов?

3. Что такое однозначность алгоритмов?

4. Что такое результативность алгоритмов?

5. Что такое правильность алгоритмов?

6. Что такое массовость алгоритмов?

7. Что такое алгоритмические ошибки?

Задания

 

1. Составьте сценарий, алгоритм и программу:

а) поздравления с Новым годом;

б) поздравления с Днем рождения;

в) регистрации даты рождения;

г) регистрации фамилии и имени.

2. Составьте сценарий диалога, алгоритм и программу:

а) расчета сдачи за товар;

б) расчета остатка от прибыли;

в) пересчета рубль/доллар;

г) расчета остатка времени до 18.00.

3. Составьте сценарий, алгоритм и программу вычислений:

а) времени движения по длине пути и скорости;

б) длины пути по времени и скорости движения;

в) средней скорости по времени и длине пути.

4. Составьте картинки, алгоритмы и программу рисования:

а) российского флага; г) украинского флага;

б) шведского флага; д) французского флага;

в) японского флага; е) британского флага.

5. Составьте сценарий, алгоритмы и программу на Бейсике вывода изображений:

а) яхты; д) автомобиля;

б) трактора; е) усадьбы;

в) дерева; ж) цветка;

г) рыбы; з) птицы.