Как вы понимаете свойство алгоритма результативность
Алгоритм. Свойства алгоритма
Существует множество определений понятия «алгоритм»:
Из определений вытекают свойства алгоритма [5]:
Теперь покажем, что конкретный алгоритм обладает этими свойствами. В качестве примера, возьмем алгоритм, изображенный на рис. 1 в виде блок-схемы [6].
Рис 1 Блок-схема алгоритма проверки правильности расстановки скобок
Приведенный алгоритм проверяет правильность расстановки скобок, если скобки расставлены правильно – то каждой закрывающей скобке предшествует соответствующая открывающая, а каждой открывающей соответствует закрывающая.
Суть алгоритма заключается в подсчете глубины вложенности скобок друг в друга. Если в какой-то момент глубина получает значение меньше нуля – то скобки расставлены неправильно. Если просмотрены все символы строки, но счетчик не равен нулю – то в строке есть не закрытые скобки (расставлены неправильно). В противном случае скобки расставлены правильно.
Можно сказать, что алгоритм обладает свойством дискретности, так как весь алгоритм разбит на отдельные части (на блок-схеме это хорошо видно).
Доказать детерминированность алгоритма, достаточно сложно, например, когда алгоритм содержит части, которые выполняются параллельно, но не будем сейчас на этом останавливаться. Скажем, что в данном случае программа является детерминированной, т.к. не содержит фрагментов, зависящих от времени выполнения, т.е. сколько бы мы не тестировали алгоритм на одной и той же строке результат не изменится.
Чтобы показать результативность алгоритма, в данном случае достаточно заметить, что любой путь из начальной вершины в конечную содержит блок вывода результата. Перед блоком «конец» алгоритм содержит лишь 2 альтернативные ветви, каждая из которых выводит некоторый результат.
Алгоритм обладает свойством массовости, т.к. исходными данными для него может быть любая конечная последовательность символов. Алгоритм не обладал бы этим свойством, если бы работал лишь ограниченном наборе исходных данных, например на строках «()» и «())», но на остальных наборах не работал или работал не правильно.
Проверить свойство правильности алгоритма достаточно просто, для этого можно взять несколько примеров исходных данных, для которых результат очевиден и протестировать алгоритм на них, но доказать правильность алгоритма достаточно сложно. Доказательство правильности называется верификацией и явно выходит за рамки этой статьи.
В этой статье мы разобрались с тем, что такое алгоритм и какими основными свойствами он должен обладать. К теме алгоритмов я обязательно вернусь в будущих статьях.
Свойства алгоритма
Дата добавления: 2013-12-23 ; просмотров: 4425 ; Нарушение авторских прав
1. Результативность.Алгоритм имеет некоторое число входных величин – аргументов, задаваемых до начала работы. Цель выполнения алгоритма – получение результата (результатов), имеющего вполне определенное отношение к исходным данным. Можно сказать, что алгоритм указывает последовательность действий по преобразованию исходных данных в результаты.
2. Массовость. Для алгоритма можно брать различные наборы данных, т.е. использовать один и тот же алгоритм для решения целого класса однотипных задач. Вместе с тем существуют алгоритмы, которые применимы только к единственному набору исходных данных. Например, для алгоритма пользования автоматическим турникетом при входе в метро существует единственный вариант исходного данного – жетон. Поэтому понятие массовости требует уточнения. Можно считать, что каждого алгоритма существует свой класс объектов, допустимых в качестве исходных данных. Тогда свойство массовости означает, применимость алгоритма ко всем объектам этого класса. А количество объектов класса (конечное или бесконечное) – свойство самого класса исходных данных.
3. Понятность. Чтобы алгоритм можно было выполнить, он должен быть понятен исполнителю. Понятность алгоритма означает знание исполнителя алгоритма о том, что надо делать для его исполнения.
Таким образом, при формулировке алгоритма необходимо учитывать возможности и особенности исполнителя, на которого рассчитан алгоритм.
4. Дискретность. Алгоритм представлен в виде конечной последовательности шагов. Говорят, что алгоритм имеет дискретную структуру. Следовательно, его исполнение расчленяется на выполнение отдельных шагов (выполнение каждого последующего шага начинается только после выполнения предыдущего).
5. Конечность. Выполнение алгоритма заканчивается после выполнения конечного числа шагов. При выполнении алгоритма некоторые его шаги могут выполняться многократно.
В математике существуют вычислительные процедуры, имеющие алгоритмический характер, но не обладающие свойством конечности. Например, процедура вычисления числа π. Такая процедура описывает бесконечный процесс и никогда не завершится. Если же прервать ее искусственно, например, ввести условие завершения процесса вычислений вида: «Закончить вычисления после получения п десятичных знаков числа», то получится алгоритм вычисления п десятичных знаков числа π. На этом принципе основано получение многих вычислительных алгоритмов: строится бесконечный, сходящийся к искомому решению процесс. Он обрывается на некотором шаге, и полученное значение принимается за приближенное решение рассматриваемой задачи. При этом точность приближения зависит от числа шагов.
6. Определенность.Каждый шаг алгоритма должен быть четко и недвусмысленно определен и не должен допускать произвольной трактовки исполнителем. При исполнении алгоритма исполнитель должен действовать строго в соответствии с его правилами и у него не должно возникать потребности предпринимать какие-либо действия, отличные от предписанных алгоритмом. Иными словами, алгоритм рассчитан на чисто механическое исполнение. Это означает, что если один и тот же алгоритм поручить для исполнения разным исполнителям, то они придут к одному и тому же результату, лишь бы исполнители понимали алгоритм.
Таким образом, формулировка алгоритма должна быть так точна, чтобы полностью определять все действия исполнителя.
7. Эффективность.Алгоритм должен быть эффективен – значит, действия исполнителя на каждом шаге исполнения алгоритма должны быть достаточно простыми, чтобы их можно было выполнить точно и за конечное время. Кроме того, эффективность означает, что алгоритм может быть выполнен не просто за конечное, а за разумное конечное время(обычно важно, чтобы задача по разработанному алгоритму решалась как можно быстрее).Вот почему при разработке алгоритмов должны учитываться и возможности конкретных физических исполнителей алгоритма.
Приведенные выше комментарии поясняют интуитивное понятие алгоритма, но само по себе само это понятие не становится от этого более четким и строгим. Тем не менее, математики долгое время довольствовались этим понятием. Лишь с выявлением алгоритмически неразрешимых задач, т.е. задач, для которых невозможно построить алгоритм, появилась настоятельная потребность в построении формального определения алгоритма, соответствующего известному интуитивному понятию.
Интуитивное понятие алгоритма в силу своей расплывчатости не может быть объектом математического изучения, поэтому для доказательства существования или несуществования алгоритма решения задачи было необходимо формальное определение алгоритма.
Построение такого формального определения было начато с формализации объектов (операндов) алгоритма, т.к. в интуитивном понятии алгоритма его объекты могут иметь произвольную природу. Ими могут быть, например, числа, показания счетчиков, фиксирующих параметры некоторого процесса и т.п. Однако, полагая, что алгоритм имеет дело не с самими реальными объектами, а их образами, можно считать, что операнды алгоритма есть слова в произвольном алфавите. Тогда получается, что алгоритм преобразует слова в произвольном алфавите в слова того же алфавита. Дальнейшая формализация понятия алгоритма связана с формализацией действий над операндами и порядка этих действий. Одна из таких формализаций была предложена в 1936 г. английским математиком А. Тьюрингом, который формально описал конструкцию некоторой абстрактной машины (машины Тьюринга) как исполнителя алгоритма и высказал основной тезис о том, что всякий алгоритм может быть реализован соответствующей машиной Тьюринга. Примерно в это же время американским математиком Э. Постом была предложена другая формальная алгоритмическая схема – машина Поста, а в 1954 г. советским математиком А.А. Марковым была разработана теория класса алгоритмов, названных им нормальными алгоритмами, и высказан основной тезис о том, что всякий алгоритм нормализуем.
Эти алгоритмические схемы эквивалентны в том смысле, что алгоритмы, описываемые в одной из схем, могут быть также описаны и в другой. В последнее время эти теории объединяют под названием логические.
Логические теории вполне пригодны для решения теоретических вопросов о существовании или не существовании алгоритма. Но они никак не помогают в случаях, когда требуется получить хороший алгоритм, годный для практических применений. Дело в том, что с точки зрения логических теорий алгоритмы, предназначенные для практических применений (а именно такие алгоритмы в дальнейшем будут представлять интерес), являются алгоритмами в интуитивном смысле. Поэтому при решении проблем, возникающих в связи с созданием и анализом таких алгоритмов, нередко приходится руководствоваться лишь интуицией, а не строгой математической теорией.
Таким образом, практика поставила задачу создания содержательной теории, предметом которой были бы алгоритмы как таковые, и которая позволяла бы оценивать их качество, давала бы практически пригодные методы их построения, эквивалентного преобразования, доказательства правильности и т.п.
Содержательная (аналитическая) теория алгоритмов стала возможной лишь благодаря фундаментальным работам математиков в области логических теорий алгоритмов. Развитие такой теории связано с дальнейшим развитием и расширением формального понятия алгоритма, которое слишком сужено в рамках логических теорий. Формальный характер понятия позволит применять к нему математические методы исследования, а его широта должна обеспечить возможность охвата всех типов алгоритмов, с которыми приходится иметь дело на практике.
Презентация к уроку
Цель урока: Формирования у учащихся правильного понимания алгоритмов, их свойств, видов и практических навыков составления алгоритмов.
Задачи урока:
Дидактические: Обеспечить условия:
Воспитательные: Обеспечить условия:
Развивающие: Обеспечить условия:
Демонстрационный материал к уроку:
Ход урока
Понятие алгоритма
Появление алгоритмов связывают с зарождением математики.
Более 1000 лет назад (825 г.)ученый из города Хорезма Абдулла (или Абу Ждафар) Мухаммед бен Мусса аль-Хорезми создал книгу по математике, в тором описал способы выполнения арифметических действий над многозначными числами.
Алгоритм – описание последовательности действий, исполнение которых приводит к решению поставленной задачи за конечное число шагов.
Алгоритм — понятное и точное предписание исполнителю выполнить конечную последовательность команд, приводящих от исходных данных к искомому результату.
Свойства алгоритма
Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке.
Пример: Алгоритм «Зарядка»
При словесно-формульном способе алгоритм записывается в виде текста с формулами по пунктам, определяющим последовательность действий.
Пусть, например, необходимо найти значение следующего выражения:
Словесно-формульным способом алгоритм решения этой задачи может быть записан в следующем виде:
При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий.
Виды алгоритма
Линейный алгоритм – это такой, в котором все операции выполняются
последовательно одна за другой.
Пример: Алгоритм посадки дерева.
Разветвляющийся алгоритм – это алгоритм в котором выполняется либо одна, либо другая группа действий в зависимости от истинности или ложности условия.
Полная форма
Неполная форма
Пример: Если на улице дождь, то останемся дома, а если нет то идем гулять.
Циклический алгоритм – действия повторяются до тех пор, пока выполняется заданное условие.
Цикл с известным числом повторений
Цикл с известным числом повторений часто называют «циклом ДЛЯ»
Пример: Алгоритм «Упражнение для глаз»
Цикл с постусловием
Цикл с неизвестным числом повторений, в тором выход из цикла осуществляется при выполнении условия, принято называть «циклом с постусловием» или «циклом ПРИ»
Цикл с предусловием
Цикл с известным числом повторений, в котором цикл продолжается, пока выполняется условие, принято называть «циклом с предусловием» или «циклом ПОКА»
Свойства алгоритмов
Центральным понятием информатики является алгоритм. Алгоритм – это метод (способ) решения задачи, записанный по определенным правилам, обеспечивающим однозначность его понимания и механического исполнения при всех значениях исходных данных.
Описание метода следует выполнять в соответствии с определенными правилами:
– выделить величины, являющиеся исходными для задачи;
– разбить процесс решения задачи на этапы, известные исполнителю, которые он может выполнить однозначно без всяких пояснений;
– указать порядок выполнения этапов;
– указать признак окончания процесса решения задачи;
– указать результат решения задачи.
Составить такое описание обычно нелегко, но, следуя ему и механически выполняя все указанные в нем этапы в требуемом порядке, исполнитель может всегда правильно решить задачу.
Основные свойства алгоритма, вытекающие из его определения:
– дискретность алгоритма – свойство алгоритма, означающее, что процесс решения задачи, определяемый алгоритмом, разделен на отдельные элементарные действия (шаги). Алгоритм представляет последовательность указаний и команд, определяющих порядок выполнения шагов процесса;
– определенность алгоритма – свойство алгоритма, когда каждая его команда понятна исполнителю, не оставляя при этом места для ее неоднозначного толкования и неопределенного исполнения. Описание алгоритма должно быть таким, чтобы его мог выполнить пользователь;
– результативность алгоритма – свойство алгоритма, означающее, что решение задачи происходит за конечное число шагов и за конечное время. В алгоритме всегда должно быть указано условие его выполнения;
– массовость алгоритма – свойство алгоритма, означающее, что каждый алгоритм, разработанный для решения некоторой задачи, должен быть применим для решения задач этого типа при всех допустимых значениях исходных данных.
Процесс решения задачи с помощью ЭВМ не отличается от процесса решения этой же задачи человеком-исполнителем. Так же следует выбирать и изучать метод решения задачи, так же составлять алгоритм и решать задачу строго в соответствии с ним, только решать должна ЭВМ, а не человек. Программный принцип работы – способность действовать по алгоритму, реализованному в виде программы.
Возможность использования ЭВМ вместо человека объясняется соответствием свойств алгоритма и ЭВМ: алгоритм допускает механическое выполнение его для решения задачи, а ЭВМ может механически, не вникая, выполнять операции в заданном порядке. Отличие указанного процесса при использовании ЭВМ в том, что при составлении алгоритма происходит разбиение процесса решения задачи на операции, которые в состоянии выполнить ЭВМ.
Другое отличие в том, что составленный алгоритм решения задачи следует перевести на язык, понятный ЭВМ.
Алгоритм и его свойства.
1. Конечность(результативность) алгоритма означает, что за конечное число шагов должен быть получен результат;
2. Дискретность алгоритма означает, что алгоритм должен быть разбит на последовательность выполняемых шагов;
3. Понятность алгоритма означает, что алгоритм должен содержать только те команды, которые входят в набор команд, который может выполнить конкретный исполнитель;
4. Точность алгоритма означает, что каждая команда должна пониматься однозначно;
5. Массовость алгоритма означает, что однажды составленный алгоритм должен подходить для решения подобных задач с разными исходными данными.
6. Детерминированность (определенность). Алгоритм обладает свойством детерминированности, если для одних и тех же наборов исходных данных он будет выдавать один и тот же результат, т.е. результат однозначно определяется исходными данными.
Таким образом, Алгоритм — это понятное и точное предписание исполнителю, выполнить конечную последовательность шагов, приводящей от исходных данных к искомому результату.
Другие статьи в литературном дневнике:
Портал Стихи.ру предоставляет авторам возможность свободной публикации своих литературных произведений в сети Интернет на основании пользовательского договора. Все авторские права на произведения принадлежат авторам и охраняются законом. Перепечатка произведений возможна только с согласия его автора, к которому вы можете обратиться на его авторской странице. Ответственность за тексты произведений авторы несут самостоятельно на основании правил публикации и российского законодательства. Вы также можете посмотреть более подробную информацию о портале и связаться с администрацией.
Ежедневная аудитория портала Стихи.ру – порядка 200 тысяч посетителей, которые в общей сумме просматривают более двух миллионов страниц по данным счетчика посещаемости, который расположен справа от этого текста. В каждой графе указано по две цифры: количество просмотров и количество посетителей.
© Все права принадлежат авторам, 2000-2021 Портал работает под эгидой Российского союза писателей 18+