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

Вопросы

1. Когда результаты правильные?

2. Когда результаты неправильные?

3. Когда способ решения правильный?

4. Что такое постановка задачи?

4. Что такое метод решения?

5. Когда метод решения правильный?

6. Когда метод решения неправильный?

Задания

1. Приведите постановку задачи и общий метод решения квадратного уравнения.

2. Приведите калькуляцию для решения квадратных уравнений на компьютере.

3. Докажите правильность общего метода решения квадратного уравнения.

4. Приведите калькуляцию для решения системы уравнений с двумя неизвестными:

а ∙ х + b ∙ у = е

с ∙ х + d ∙ y = f

с помощью следующего общего метода:

х = D_x / D y = D_y / D

D_x = e ∙ d – b ∙ f D_y = a ∙ f – b ∙ e

D = a ∙ d – b ∙ c

5. Приведите обоснование правильности схем вычислений следующих функций:

а) суммирование чисел СУММ (x₁, x₂, ..., x_n) = х₁ + х₂ + ... + x_n

s₀ = 0

{s_k = s_k-1 + x_k , (k = 2, 3, …, n)

СУММ (x₁, x₂, ..., x_n) = s_n

б) максимальное значениеМАКС (x₁, x₂, ..., x_n) = mах (x₁, x₂, ..., x_n)

mх₁ = х,

{mx_k = mах(mx_k-1, х_k), (k = 2, 3, ..., n)

МАКС (x₁, x₂, ..., x_n) = mх_n

в) минимальное значениеМИН(x₁, x₂, ..., x_n) = min(x₁, x₂, ..., x_n)

mn₁ = х₁

{mn_k = min(mn_k-1, х_k) , (k = 2, 3, ..., n)

МАКС(x₁, x₂, ..., x_n) = mn_n

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

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

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

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

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

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

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

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

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

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

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

нач с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