Файл: Алгоритмизация как обязательный этап разработки программы ( Алгоритмизация ).pdf
Добавлен: 01.04.2023
Просмотров: 54
Скачиваний: 2
Введение
Быстрое развитие информатики как науки и проникновение её во все области человеческой деятельности, сделало термин "алгоритм" часто употребляемым на бытовом уровне и понятием которое используют специалисты различных областей. Кроме того, переход к информационному обществу делает алгоритмы важнейшим фактором цивилизации.
Первым известным человечеству алгоритмом, который решал поставленную задачу, принято считать предложенный Евклидом в 3 веке до нашей эры алгоритм нахождения наибольшего общего делителя двух чисел. Из этого следует, что теория алгоритмов образовалась вовсе не в связи с развитием информатики и вычислительной техники, а появилась в недрах математической логики для решения её собственных задач. Однако, теоретические области, связанные с вычислительной техникой, несомненно, сыграли свою роль на появление теории алгоритмов в том виде, в котором она сейчас существует. Теория алгоритмов повлияла и на теоретическое программирование, а именно, существенную роль в теоретическом программировании играют модели вычислительных автоматов. Операторы, используемые для составления структурированных программ (повторение, линейное выполнение, разветвление), а также трактовка программ как объектов вычисления, пришли в программирование именно из теории алгоритмов. Обратное влияние выразилось, например, в том, что возникла потребность в создании и развитии теории вычислительной сложности алгоритмов. Поэтому можно сказать, что теория алгоритмов используется и в других областях знаний, а не только в информатике.
Цель данной курсовой работы детально разобрать понятие алгоритма, его свойства, а также научиться составлять алгоритмы различной структуры, уметь применять их для решения различных задач и для написания программ.
В качестве источников были использованы современные учебные пособия рекомендуемые для студентов высших учебных заведений России и стран СНГ, лекции преподавателей ВУЗов и информация из документов ГОСТ.
1. Алгоритмизация
Во многих сферах деятельности, в частности в области обработки информации, человеку приходится решать задачи с использованием компьютера. Решение любой задачи предполагает использование алгоритма, который определяет порядок выполнения действий для получения желаемого результата. На основе алгоритма составляется программа, т.е. запись алгоритма решения задачи каком-то формальном языке, пригодном для выполнения на компьютере. Следовательно, различные программы для ЭВМ являются конкретным воплощением разнообразных алгоритмов.
Алгоритмизацией же называют процесс составления алгоритмических предписаний. Роль алгоритмизации в жизни современного общества определяется не только техническими аспектами ее использования. Алгоритмический подход невозможно отделить от повседневной жизни людей, от их обычной работы. В подавляющем большинстве случаев результат деятельности человека зависит от того, насколько четко он понимает алгоритмическую сущность своих действий: что и когда делать в определенный момент времени, в какой последовательности, каким именно должен быть итог его действий. Это, в некоторой степени, зависит от умения человека составлять и использовать алгоритмы.
2. ПОНЯТИЕ АЛГОРИТМА. СВОЙСТВА И ВИДЫ АЛГОРИТМОВ
Главным, и одним из наиболее сложных этапов решения задачи с использованием ЭВМ, является разработка алгоритма. Алгоритм — конечное предписание исполнителю, описанное на некотором языке, которое определяет вычислительный процесс, направленный на решение поставленной задачи за определенное время[[1]].
Понятие «Алгоритм» происходит от латинского слова algorithmi — от имени узбекского ученого Мухаммеда аль-Хорезми[[2]]. В своей книге, примерно в 825 году, он дал описание десятичной позиционной системы счисления, придуманной в Индии. Позже, в XII веке, книга попала в Европу под названием «Индийское искусство счета, сочинение Аль-Хорезми» (Algoritmi de numero Indorum). На протяжении нескольких следующих столетий множество других трудов, посвященных счёту с помощью цифр, содержали в своём названии слова algoritmi и algorismi.
Из Алгебры и теории чисел у нас появились, упоминаемый во введении, Алгоритм Евклида, а также алгоритмы Гаусса, Штурма и прочие. В дальнейшем, алгоритмом стали называть точное предписание, определяющее последовательность элементарных операций, обеспечивающие получение определяемого из исходных данных результата. Но, несмотря на множество различных вариантов, такое определение алгоритма не является исчерпывающим[[3]], наиболее удачными являются определения алгоритма данные российскими ученными А.А. Марковым и А.Н. Колмогоровым.
Алгоритм может быть предназначен для исполнения человеком, а также автоматическим устройством. По сути, написание даже самого элементарного алгоритма - процесс творческий. Поэтому он доступен только живым существам, и долгое время считалось, что только человеку. Совсем по-другому дела обстоят с реализацией уже имеющегося алгоритма. Её можно поручить объекту, который не обязан вникать в суть задачи, а возможно, даже не способен её понять. Такой объект принято называть формальным исполнителем. Отличным примером формального исполнителя может служить кофе-машина или микроволновая печь, которая в точности исполняет предписанные ей действия, даже если вы забыли положить продукты внутрь. Формальными исполнителями, в первую очередь, являются именно разнообразные автоматизированные устройства, компьютеры, но и человек может выступать в такой роли.
Любой алгоритм создается с расчетом на вполне определенного исполнителя, при этом допустимыми называют действия, которые может совершать такой исполнитель. Система команд исполнителя образуется из совокупности допустимых действий. Алгоритм должен содержать только те действия, которые допустимы для данного исполнителя.
Чтобы отличать алгоритмы от других инструкций, обычно формулируют ряд их требований (свойств)[[4]]:
- Определенность (детерминированность) – алгоритм должен быть точным и понятным исполнителю, не допускающий двусмысленной трактовки. Исполнитель, выполняя инструкции, должен чётко понимать, что нужно сделать на данном шаге, и какой шаг должен быть следующим. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных инструкций или сведений о выполняемой задаче.
- Массовость – алгоритм пригоден для решения всех задач одного типа при различающихся исходных данных. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.
- Дискретность – означает раздельность определяемого алгоритмом вычислительного процесса на отдельные этапы, возможность выполнения которых исполнителем не вызывает сомнений. Каждое действие, предусмотренное алгоритмом, выполняется только после того, как закончилось выполнение предыдущего[[5]].
- Результативность – целью выполнения алгоритма является получение конкретного результата, имеющего определенное отношение к исходным данным. Алгоритм должен останавливаться после определенного числа шагов, зависящего от данных, с указанием того, что считать результатом. Если же решение не может быть найдено, то должно быть указано, что в этом случае считать за результат.
Основными критериями качества алгоритма являются:
- Связность – определяется количеством промежуточных результатов, которые должны одновременно храниться в памяти. Следовательно, чем меньше связность алгоритма, тем он лучше.
- Объём алгоритма – количество простейших операций, которые необходимо выполнить для решения задачи.
- Логическая сложность алгоритма – количество ветвлений и циклов. Определяет разнообразие путей процесса вычисления и повторяющихся многократно операций соответственно.
- Длительность выполнения алгоритма – зависит от количества и сложности шагов алгоритма. Что в свою очередь, конечно же, зависит от быстродействия исполнителя, но если принять за константу время выполнения некоторой операции, то чем быстрее выполняется алгоритм, тем он лучше[[6]].
- Эффективность – алгоритм должен состоять из минимального количества шагов и требовать минимальных затрат ресурсов. При этом решение должно удовлетворять критерии точности.
Существуют и другие критерии качества алгоритма, такие как: разветвленность, цикличность и прочие.
В алгоритме отражаются логика и способ формирования результатов решения задачи с указанием используемых формул, логических условий, соотношений для контроля достоверности получаемых результатов. В алгоритме должны быть предусмотрены все ситуации, которые могут возникнуть в процессе решения поставленной задачи, в т.ч. должна присутствовать обязательная проверка исходных данных.
Алгоритм решения комплекса задач и его программная реализация на формальном языке тесно взаимосвязаны. Специфика применяемых методов проектирования алгоритмов и используемых при этом инструментальных средств разработки программ может повлиять на форму представления и содержание алгоритма обработки данных. Применительно к вычислительной машине, алгоритм – точное предписание, т.е. набор инструкций и правил, при помощи которого, используя некоторые исходные данные, можно решить какую-то задачу определенного типа.
Алгоритмы, в зависимости от цели, начальных условий задачи, путей её решения и определения действий исполнителя, подразделяются на три основных вида[[7]]:
- Линейный алгоритм – набор инструкций, выполняемых последовательно одна за другой.
- Разветвляющийся алгоритм – содержащий одно или более условий, в результате обработки которого ЭВМ выполняет одно из двух указанных действий.
- Циклический алгоритм – выполняющий многократное повторение одного и того же действия, либо одних и тех же операций, над новыми исходными данными. К циклическим алгоритмам сводится большинство методов вычислений, перебора вариантов. Циклом программы, в таком случае, называют последовательность команд (тело цикла), которое выполняется неоднократно (для новых исходных данных) до выполнения некоторого условия.
Но также существуют и другие виды алгоритмов:
- Механический алгоритм (детерминированный), к примеру, алгоритм работы механизма и т.п.
- Эвристический алгоритм (от греческого слова «эврика») – алгоритм, в котором достижение конечного результата программы действий однозначно не предопределено, так же как не обозначена вся последовательность действий, не выявлены все действия исполнителя. К примеру, к эвристическим алгоритмам можно отнести различные предписания и инструкции. В этих алгоритмах используются универсальные логические процедуры и способы принятия решений.
- Вероятностный алгоритм (гибкий или стохастический) – дает программу решения задачи несколькими путями или способами, приводящими к вероятному достижению результата.
- Вспомогательный (подчиненный) алгоритм – ранее разработанный и целиком используемый при алгоритмизации конкретной задачи. В некоторых случаях, при наличии однотипных последовательностей, указаний или команд для различных данных, с целью сокращения записи, также можно создать вспомогательный алгоритм[[8]].
3. СПОСОБЫ ОПИСАНИЯ АЛГОРИТМОВ
Алгоритм можно описать такими способами: словесной записью, псевдокодом и блок-схемой.
Словесная запись алгоритма основана на естественном языке, и содержит набор фраз, не допускающий неоднозначного понимания, повторений и ненужных слов[[9]]. К примеру, любой бытовой прибор (стиральная машина, печь, утюг и т.п.) имеет инструкцию пользователя, другими словами, словесное описание алгоритма, в соответствии с которым этот прибор должен эксплуатироваться.
Не существует единых правил составления словесного описания. Запись словесного алгоритма осуществляется в произвольной форме на естественном языке, к примеру, на русском или английском языке. Такой способ не имеет широкого распространения, так как строго не формализуем (под «формальным» понимается то, что описание абсолютно полное и учитывает все возможные ситуации, которые могут возникнуть в ходе решения); может допускать многозначность толкования некоторых действий; страдает многословностью.
Псевдокод — основан на естественном, частично формализованном языке предписаний, задаваемых с помощью ограниченного набора типовых синтаксических конструкций[[10]]. Набор таких конструкций состоит из смеси алгоритмического языка и фраз языка, понятных исполнителю. Псевдокод облегчает разработку программ, поскольку псевдокод обладает всеми преимуществами структурированной записи, алгоритм, написанный на псевдокоде достаточно легко преобразовать в программный код. Как правило, не существует стандартов для записи псевдокода, поэтому возможны различные варианты псевдокода, отличающиеся набором используемых слов и синтаксических конструкций.
Блок-схема – способ выполнения задачи, представленный графически с помощью набора определенных геометрических фигур, связанных линиями[[11]]. Благодаря наглядности, такой способ описания алгоритма считается наиболее распространенным, и обладает рядом преимуществ. Визуализация повышает «читаемость» алгоритма и точно отображает порядок выполнения отдельных инструкций. Такой способ записи позволяет быстро и наглядно оценить весь алгоритм в целом, оценить всю картину, не вдаваясь в подробности его реализации. В блок-схеме, каждому типу действия, соответствует определенная геометрическая фигура, связанная линиями, которые определяют очередность выполнения.