Файл: АЛГОРИТМИЗАЦИЯ КАК ОБЯЗАТЕЛЬНЫЙ ЭТАП РАЗРАБОТКИ ПРОГРАММЫ (Понятие алгоритма. История возникновения).pdf
Добавлен: 27.06.2023
Просмотров: 48
Скачиваний: 3
Введение.
При создании ответственных технологических объектов одной из важнейших составляющих процесса их проектирования является комплексная автоматизация технических средств. Различная природа физических процессов, протекающих в объектах, сложный характер взаимодействия между ними и управляющими системами обуславливает трудности алгоритмизации и программирования задач управления. Вопросы унификации аппаратного обеспечения в настоящее время решаются достаточно успешно на основе микропроцессорных и микроконтроллерных комплектов, программируемых логических контроллеров и промышленных компьютеров. Однако при формировании общих подходов к созданию алгоритмического и программного обеспечения возникают трудности, связанные с необходимостью достижения их наглядности, структурированности, наблюдаемости и управляемости. Эти трудности усугубляются тем, что при создании различных систем управления обычно используются и различные технологии алгоритмизации и программирования.
Спектр таких технологий широк: от технологий на основе алгоритмических языков высокого уровня для промышленных компьютеров до технологий на основе специализированных языков для программируемых логических контроллеров (например, функциональных и лестничных схем). Очевидно, что алгоритмизация и программирование систем управления техническими средствами, должны основываться на единой методологии, позволяющей строить, читать, проверять, верифицировать алгоритмы и программы. До настоящего времени алгоритмы логического (основанные на истинности и ложности) управления задаются Проектантом (Технологом) в словесной форме, и поэтому они могут быть противоречивыми и неполными. Это вносит дополнительные трудности в процесс алгоритмизации и программирования управляющих устройств, так как каждый участник разработки понимает в силу неоднозначности и словесного описания алгоритмы логического управления по-своему. По этой причине даже самый "точный" словесный алгоритм может удовлетворять каждого из участников разработки в отдельности, но, в конечном счете, являться некорректным.
Ситуация усугубляется при создании систем управления, ядро которых представляет собой систему взаимосвязанных управляющих устройств. При этом, с одной стороны, совокупность таких устройств (вследствие большой размерности) становится плохо обозримой, наблюдаемой и управляемой, а с другой – плохо понимаемой Заказчиком и Проектантом (Технологом). Это во многом определяется тем, что обычно автоматизация каждого комплекса технических средств выполняется самостоятельным коллективом Разработчиков и Программистов, которые используют специфическую технологию алгоритмизации и программирования. В настоящее время в практике проектирования систем управления, наиболее часто употребляемыми языками спецификаций алгоритмов логического управления являются язык функциональных схем и язык блок-схем алгоритмов, называемых обычно схемами алгоритмов. Указанные языки удобны, как правило, только для одних участников разработки, но крайне неудобны для других участников. Так, например, наиболее часто при согласовании алгоритмов управления судовыми техническими средствами применяется язык функциональных схем, который достаточно хорошо понятен только Разработчику, так как такой язык для последовательностных алгоритмов, реализуемых схемами с обратными связями, описывает их структуру (статику), но не отражает в явном виде их поведение (динамику).
Тема алгоритмизации на сегодняшний день стала особо актуальной, поскольку с течением времени программным продуктам ставятся всё более сложные задачи, выполнение которых теперь невозможно без чётко определённого алгоритма.
В данной курсовой работе я постараюсь осветить такие понятия, как алгоритм, исполнитель алгоритма, алгоритмизация, рассказать о свойствах и видах алгоритмов, о правилах построения алгоритмов, о методах их представления и классификации, о роли алгоритмизации в программировании.
Раздел 1. Понятие алгоритма. История возникновения.
Принято считать, что слово алгоритм произошло от имени одного из значимых персидских ученых Аль-Хорезми, жившего в 799-850 гг. на территории современного Узбекистана и Туркмении. Сочинение, написанное им в первой половине IX века и повествовавшее о придуманной в Индии позиционной десятичной системе счисления, положило начало начертанию цифр, которые ныне так привычны нашему глазу. Именно индийские цифры стали прародителями арабских, которые мы используем по сей день. Сочинение Аль-Хорезми так и называлось – «Книга об индийском счете» (лат. Algoritmi de numero Indorum). Латинское название сочинение получило в XII веке, когда проникло в Европу. Арабское название книги звучало как Китаб аль-джебр валь-мукабала. От названия этой книги пошло современное название науки алгебры. Так же Аль-Хорезми подарил нам еще одну книгу, о существовании которой узнали в середине XIX века, благодаря найденному в библиотеке Кембриджского университета латинскому переводу этой книги. Первые строки этой книги гласят: «Сказал Алгоритми. Воздадим должную хвалу Богу, нашему вождю и защитнику». Благодаря переводу Аль-Хоризми стал Алгоритми.
Так что же есть алгоритм? Алгоритмом называется определённый порядок действий, который приводит к конечному результату за определённое количество шагов. В повседневной жизни мы очень часто используем алгоритмы. Покупая мебель, мы открываем инструкцию по сборке, что в своем роде тоже является алгоритмом. Просматривая кулинарные книги, мы тоже сталкиваемся с алгоритмами, только в виде рецептов.
В XX веке, с появлением первых вычислительных машин, термин алгоритм стал употребляться более активно. Этому в неменьшей степени поспособствовал английский математик и криптограф Алан Тьюринг, доказавший возможность создания машины, которая способна исполнять алгоритм. Впоследствии была создана машина Тьюринга, которая позволила взломать немецкий шифратор Энигма. С этих пор стал употребляться термин – исполнитель алгоритма. Этот термин не имеет четкого определения, ведь совершать действие над алгоритмом может кто угодно, начиная от программы и заканчивая человеком.
В информатике универсальным исполнителем алгоритмов является компьютер.
Исполнитель алгоритма - некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнить действия, предписываемые алгоритмом.
Исполнителя характеризуют: среда; система команд; элементарные действия; отказы.
Среда (или обстановка) - "место обитания" исполнителя. Объекты, над которыми исполнитель может совершать действия. Для алгоритмов, встречающихся в математике, средой того или иного исполнителя могут быть числа разной природы - натуральные, действительные и т.п., буквы, буквенные выражения, уравнения, тождества и т. п.
Система команд - совокупность допустимых действий. Каждый исполнитель может выполнять команды только из некоторого строго заданного списка - системы команд исполнителя. Для каждой команды должны быть заданы условия применимости, описаны результаты выполнения команды.
Элементарное действие - те действия, которые может совершать исполнитель.
Отказы исполнителя возникают, если команда вызывается при недопустимом для нее состоянии среды.
Раздел 2. Виды и свойства алгоритмов.
Все алгоритмы должны быть составлены так, чтобы исполнитель мог однозначно следовать командам для получения определённого результата. Это накладывает на алгоритмы базовые требования, которые называются свойствами алгоритма. Существуют следующие свойства алгоритма:
- Дискретность - свойство алгоритма, требующее пошагового выполнения задачи. Каждое действие выполняется только после завершения предыдущего.
- Определенность. Каждый шаг должен быть однозначным. В алгоритме не должно присутствовать двоякого трактования. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.
- Результативность. Алгоритм, в конечном итоге, должен приводить к решению задачи за определённое число шагов.
- Массовость. Алгоритм решения задачи разрабатывается в общем виде, то есть, он должен быть применим для некоторого класса задач, различающихся только исходными данными.
Представим себе следующую ситуацию:
У нас есть корзина, в которой лежат 15 яблок и 10 апельсинов. Нам необходимо взять острый нож, почистить все фрукты и разложить их в разные миски.
Выше я представил алгоритм чистки фруктов, в котором можно наглядно увидеть все обязательные свойства алгоритма. Например, дискретность. В алгоритме описан строгий порядок действий, нарушив который мы не получим конечного результата. Попробуйте убрать нож, а затем почистить фрукты. У вас ничего не получится. Теперь определенность. В нашем алгоритме присутствует точное определение ножа. Он должен быть острым. Если бы в нашем алгоритме не было этого условия, мы могли бы взять любой нож, в том числе и тупой, что в дальнейшем усложнило бы задачу чистки, если не сделала бы её невозможной. Далее результативность. Тут всё просто, фрукты почищены, разложены по мискам, результат получен. И наконец, массовость. Данный алгоритм мы можем применить не только для чистки яблок и апельсинов но и например для картофеля.
Алгоритм – искусственная конструкция, которую мы сооружаем для достижения определенных целей. Каждый алгоритм составляется с применением определённый правил которые можно охарактеризовать как требования к алгоритму.
Правило 1. Для построения алгоритма необходимы объекты, с которыми он будет работать. Если эти объекты представлены в виде кода, они называются данными. Алгоритм берет некий объем данных, называемый входными данными, производит над ними работу и в конечном итоге представляет нам выходные данные.
Правило 2. Для работы алгоритма необходима память. В неё размещаются входные данные, промежуточные данные которые появляются во время работы над входными данными. Согласно теории алгоритмов память бесконечна, т.е. мы можем предоставить алгоритму неограниченное количество памяти.
Правило 3. – дискретность. Требование пошагового выполнения задачи.
Правило 4. – сходимость (результативность). Алгоритм должен завершать работу после определенного числа шагов.
Алгоритм применительно к ЭВМ – набор действий и правил их выполнения, с помощью которого можно решить определенную задачу имея некоторые входные данные. В зависимости от поставленной цели, условий задачи и возможных способах её решения алгоритмы подразделяются на следующие виды:
Детерминированные. Такого рода алгоритмы описывают строгий процесс выполнения задачи, без какого либо нарушения последовательности действий. Если выполняются поставленные условия, будет достигнут требуемый результат.
Стохастические. Стохастические алгоритмы позволяют решать задачу разными способами, с возможным достижением результата.
Эвристические. Эвристические алгоритмы это алгоритмы, в которых не определен конечный результат, по той причине, что отсутствует четкая последовательность действий исполнителя. К такому роду алгоритмов можно отнести инструкции.
Линейные. Алгоритмы, шаги в которых выполняются последовательно, друг за другом.
Разветвляющиеся. В структуре такого алгоритма присутствует условие, которое подразумевает несколько дальнейших вариантов решения задачи.
Циклические. Такие алгоритмы имеют внутри себя цикл, по завершению которого будет выполнен следующий шаг или достигнут результат. Каждый цикл имеет условие, принимающее истинное или ложное значение.
Вспомогательные. Вспомогательные алгоритмы, или как их еще называют – процедуры помогают в решении конкретной задачи, будучи изначально составленными для похожей.
Вернемся к ситуации с фруктами. Попробуем записать её разными видами алгоритмов. В детерминированном виде задача записана изначально. Шаг за шагом, последовательно мы приближаемся к результату в виде почищенных фруктов. Стохастический алгоритм я также же описывал. Вспомним про нож. Взяв в руки острый нож, мы однозначно почистим фрукты. Если возьмем тупой, то можем и не достигнуть результата. В виде эвристического алгоритма представим инструкцию по чистке яблок. Линейный алгоритм в нашем примере имеет некоторое сходство с детерминированным алгоритмом. В линейном алгоритме также задача решается последовательно, шаг за шагом, но однократно, т.е. мы взяли одно яблоко, взяли нож, почистили яблоко, положили в миску. В нашем примере в корзине лежит некоторое количество фруктов. Закончив чистить один плод, мы берём следующий, и начинаем сначала. Это пример циклического алгоритма. Пока сохраняется условие цикла (в корзине есть фрукты), алгоритм будет повторяться. Как только последний плод будет очищен, результат будет достигнут.
Давайте немного изменим вводные данные. Представим, что помимо чистки фруктов нам надо убедиться в их годности к употреблению. Здесь в игру вступает разветвляющийся алгоритм. Перед тем, как почистить яблоко нам необходимо визуально оценить его состояние, и если оно удовлетворяет нашим критериям, чистим его и складываем в миску. Если нет, то выбрасываем.
Когда то мы своими глазами увидели, как можно чистить овощи ножом. В дальнейшем мы переняли этот опыт себе. Мы использовали вспомогательный алгоритм, который ныне алгоритмизирует нам чистку фруктов, хотя ранее это был алгоритм чистки овощей.