Алгоритмизация как обязательный этап разработки программы

Содержание:

Введение

Ежедневно большинство пользователей встречается с большим количеством профессиональных задач. Чтобы решить данные задачи можно было быстро, и эффективно существуют определенные инструкции и правила при помощи, которых можно разделить данные задачи на подзадачи.

Любой ид деятельности человека – это последовательность процессов принятия решений, выполнение действий и анализа результатов. Алгоритм действий – это главный элемент, без которого невозможна успешная работа не только пользователя компьютера, но менеджера фирмы, депутата парламента и т.д.

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

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

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

1. Основные понятия и свойства алгоритмов

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

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

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

1. Каждый алгоритм имеет дело с данными - входными, промежуточными, выходными. Для того, чтобы уточнить понятие данных, фиксируется конечный алфавит выходных символов (цифры, буквы и т.п.) и указываются правила построения алгоритмических объектов. Типичным используемым средством является индуктивное построение.

2. Алгоритм для размещения данных требует память. Память обычно считается однородной и дискретной, то есть она состоящей из одинаковых ячеек, причем каждая ячейка может содержать один символ данных, что позволяет согласовать единицы измерения объема данных и памяти. В итоге процесс разработки алгоритма должен быть направлен на получение четкой структуры алгоритмических конструкций.

3. Алгоритм состоит из отдельных элементарных шагов, причем множество различных шагов, из которых составлен алгоритм, конечны. Типичный пример множества элементарных шагов - система команд процессора.

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

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

6. Алгоритм предполагает наличие механизма реализации, который по описанию алгоритма порождает процесс вычисления на основе входных данных.

Предполагается, что описание алгоритма и механизм его реализации конечные.

Можно заметить аналогию с вычислительными машинами. Требование 1 соответствует цифровой природе ПК, требование 2 - память ПК, требование 3 – программе машины, требование 4 - ее логической природе, требования 5, 6 – вычислительному устройству и его возможностям.

Понятие алгоритма принадлежит к основным понятиям современной вычислительной математики и информатики.

Алгоритм - описанная на некотором языке точная конечная система правил, которая определяет содержание и порядок действий над некоторыми объектами, строгое выполнение которых дает решение поставленной задачи.

Или (более кратко):

Алгоритм - это строго определенная последовательность действий, необходимых для решения данной задачи.

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

1) ввести исходные данные;

2) превратить начальные данные в результаты;

3) получить результаты.

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

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

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

Определяются исходные данные задачи.

1. Процесс решения задачи разбивается на этапы, понятные и однозначные для исполнителя.

2. Указывается порядок, в котором выполняются этапы, а также признак завершения процесса.

3. Определяется, что является результатом решения задачи.

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

Любой алгоритм должен иметь следующие основные свойства:

- детерминированность (определенность) - через полную однозначность правил, установленных в алгоритме, применение алгоритма к одинаковым входным данным должно приводить к одинаковому результату;

- дискретность - процесс, определяется алгоритмом, можно разделить на отдельные элементарные этапы (шаги), каждый из которых называется шагом алгоритмического процесса или алгоритма;

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

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

Сущность алгоритмизации состоит в следующих действиях, которые отражают ее свойства:

- Выделение законченных частей вычислительного процесса;

- Формальной записи каждого из них;

- Назначение детерминированного порядка выполнения выделенных частей;

- Проверки правильности выбранного алгоритма по реализации заданного метода вычислений.

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

1.1 Способы описания алгоритмов

Сейчас распространилась и бурно развивается наука, которая считается частью дискретной математики - теория алгоритмов. Она изучает общие свойства алгоритмов, сравнивает время их выполнения, вводит числовые оценки их сложности. Эту теорию заложили Е.Борель (1912) и Г. Вейль (1921). В вычислительной технике чаще всего используется теория алгоритмов в интерпретации А. Тьюринга и Е. Поста (1936), их конструкции во многом предвосхитили идеи, положенные в основу современных цифровых вычислительных машин (машина Тьюринга).

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

• словесное описание;
• формульно-словесное описание;
• псевдокод;
• графический способ (блок-схема);
• программа (способ описания с помощью языков программирования).

Словесное описание подразумевает конкретный алгоритм - спецификацию о выполнении действий в определенной последовательности при помощи слов и предложений естественного языка. Форма изложения произвольная и устанавливается разработчиком.

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

Возвращаясь к истории трансформации понятия «алгоритм», следует отметить, что до 1950 г. под этим словом чаще всего понимали изложенный в «Элементах» Евклида алгоритм Евклида - процесс нахождения наибольшего общего делителя (НОД) двух целых положительных чисел. Именно поэтому будет полезно привести в качестве примера описание этого алгоритма.

1. Даны два целых положительных числа. Если они равны, то первое из них является наибольшим общим делителем, если же нет, то перейдем к пункту 2.

2. Сравним два числа и выберем наибольшее из них.

3. Большее из двух цифр заменим разницей большего и меньшего.

4. Перейдем к пункту 1.

Этот способ описания не имеет широкого применения, т. к. строго не формализован (под «формальным» понимается то, что описание абсолютно полное и учитывает все возможные ситуации, которые могут возникнуть в ходе решения), допускает неоднозначность толкования при описании некоторых действий, страдает многословием.

Формульно-словесный способ записи шагов содержит в себе формальные символы и выражения (формулы) в сочетании со словесными пояснениями. То есть алгоритм записывается в виде текста с формулами по пунктам, определяющими последовательность действий. Этот способ описания наглядный, не громоздкий, но не является строго формальным.

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

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

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

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

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

• наглядность отображения типовых конструкций алгоритма;
• концентрация внимания на структуре алгоритма;
• применение принципа разбиения при коллективном решении сложной задачи;
• преобразование алгоритма методом укрупнения (сведения к единому блоку) или детализации (разбиения на ряд блоков);
• быстрая проверка разработанного алгоритма.

Существует два вида графических схем: блок – схемы и структурные схемы.

Блок-схема состоит из блоков нескольких видов: овальных блоков «начало» и «конец», блоков «ввода» и «вывода» данных в виде параллелограмма и т.д.

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

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

Для наглядности операции различного вида изображаются в схеме различными геометрическими фигурами (таблица).

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

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

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

1.2 Основные алгоритмические структуры как базовые элементы алгоритмизации

Алгоритмы можно представлять как некоторые структуры, состоящие из отдельных базовых (т.е. основных) элементов. Эти элементарные шаги объединяются в алгоритмические конструкции. В зависимости от особенностей своего построения алгоритмы можно разделить на следующие группы:

1) линейные (последовательные);

2) разветвленные;

3) циклические;

4) рекурсивные.

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

Линейным называется алгоритм, в котором все этапы решения задачи выполняются ровно один раз и строго последовательно. Т. е. линейный (последовательный) алгоритм выполняется в естественном порядке его написания и не содержит разветвлений или повторений.

Примерами линейных алгоритмов являются: алгоритм отпирания дверей - получить ключ, вставить ключ в замочную скважину, открыть замок; алгоритм заваривания чая - получить чайник, насыпать в него чай, залить кипятком, настоять 5-10 мин.

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

На практике редко удается представить схему алгоритма решения задачи в виде линейной структуры. Задача может содержать условие, в зависимости от которого вычислительный процесс идет с той или иной ветви, т. е. появляется разветвление алгоритма.

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

Часто при решении задач приходится проверять одно условие для нескольких значений или повторять некоторые действия несколько раз.

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

Циклической называется структура, в которой какая-то подряд идущая группа действий (шагов), может выполняться несколько раз, в зависимости от входных данных или условия задачи.

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

Группа повторяющихся действий на каждом шаге цикла называется телом цикла.

Циклический алгоритм включает:

1. Подготовку цикла - действия, связанные с задачей исходных данных, используемых в цикле;

2. Тело цикла - повторяющиеся действия для вычисления искомых величин, а также подготовка значений, необходимых для повторного выполнения действий в теле цикла;

3. Условия продолжения цикла - действия, которые определяют необходимость дальнейшего выполнения тела цикла.

Рекурсивным называется алгоритм, который в процессе выполнения на каком-то шаге прямо или косвенно обращается сам к себе. Как правило, в основе такого алгоритма лежит рекурсивное определение какого-то понятия.

Пример рекурсивного определения - определение факториала числа n: n! = 1 * 2 * 3 * 4 * ... * n.

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

1. Комбинированные алгоритмы. На практике часто встречаются задачи, алгоритм решения которых распадается на части, фрагменты и каждый фрагмент представляет собой алгоритм одного из трех описанных типов. Алгоритм, содержащий несколько структур одновременно, называется комбинированным.

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

1. Вложенные циклы. Частным случаем комбинированных алгоритмов являются алгоритмы, в которых необходимо использовать несколько циклов, которые меняются одновременно. Например, внутри одного цикла могут находиться один или несколько других циклов. Такие комбинации называются вложенными циклами. Охватываемый цикл называется внешним, а вложенные в него циклы - внутренними (вложенными), при этом область действия внутреннего цикла должна полностью находиться в области внешнего цикла, то есть циклы не должны пересекаться.

Заключение

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

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

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

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

Список использованной литературы

1. Дузельбаев С.Т., Омарбекова А.С., Шарипбаев А.А., Юсубекова С.О «Основы алгоритмизации и программирования»:- Астана 2008.
2. Аглицкий Д.С., Любченко С.Р. Работа на персональном компьютере для всех. М.: Филинъ, 2010.
3. Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения. Единая система программной документации. [Текст]: ГОСТ 19.701-90 (ИСО 5807-85). Введен 01.01.92
4. Схемы алгоритмов и программ. Обозначения условные графические. Единая система программной документации. [Текст]: ГОСТ 19003-80. Взамен ГОСТ 19428-74. Введен 01.01.92
5. Мовшович С. М., Кравченко О. А. Алгоритмизация и программирование. – 2008.
6. Долинский М. С. Алгоритмизация и программирование на TURBO PASCAL. – Питер, 2005.
7. Есмагамбетова М. М., Есмагамбетов Т. У. Алгоритмизация и программирование //Вестник научных конференций. – ООО Консалтинговая компания Юком, 2016. – №. 12-2. – С. 35-37.
8. Трофимов В. В. и др. Информатика. В 2 тт. 3-е изд., пер. и доп.: учебник для академического бакалавриата. – 2016.
9. Попов С. Н. Алгоритмизация и основы программирования. – 2017.
10. Самовендюк Н. В. Алгоритмизация и программирование. – 2015.