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

Введение

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

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

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

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

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

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.

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

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

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

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

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

---