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

Введение

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

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

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

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

Значительный вклад в развитие теории алгоритмов внесли советские ученые А. А. Марков, А. И. Мальцев, В. М. Глушков, А. Н. Колмогоров, А. П. Ершов, Ю. Л. Ершов, А. А. Ляпунов, П. С. Новиков, С. В. Яблонский и многие другие.

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

Поставленная цель обусловила следующие задачи:

- рассмотреть понятие алгоритмов;

- изучить формы представления алгоритмов;

- описать известные алгоритмы.

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

Теоретические основы изучения алгоритмов.

Понятие алгоритмов.

Алгоритм является фундаментальным понятием информатики.

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

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

Алгоритмы - это любая корректно определенная вычислительная процедура, на вход (input) которой подается некоторая величина или набор величин, и результатом выполнения которой является выходная (output) величина или набор значений [6, с.56].

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

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

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

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

Для создания алгоритма (программы) необходимо знать:

- полный набор исходных данных задачи (начальное состояние объекта);

- цель создания алгоритма (конечное состояние объекта);

- систему команд исполнителя (то есть набор команд, которые исполнитель понимает и может выполнить).

Полученный алгоритм (программа) должен обладать следующим набором свойств:

- дискретность (алгоритм разбит на отдельные шаги - команды);

- однозначность (каждая команда определяет единственно возможное действие исполнителя);

- понятность (все команды алгоритма входят в систему команд исполнителя);

- результативность (исполнитель должен решить задачу за конечное число шагов).

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

Некоторые алгоритмы, к примеру, для вычисления последовательности Фибоначчи, являются интуитивно понятными и относятся к врожденным навыкам логического мышления и решения задач [12, с.45].

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

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

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

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

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

В теории алгоритмов установлен важный факт: в универсальной алгоритмической модели всегда существует универсальный алгоритм, т. е. алгоритм, который способен моделировать работу любого другого алгоритма, описанного в этой модели. Универсальный алгоритм устроен следующим образом. Имеется метод кодирования S для любого алгоритма А в данной модели [20, с.113].

Если на вход универсального алгоритма U подать код S(A) алгоритма A и исходные данные х, то результат работы U будет равен результату работы А над х: U(S(A),x) = А(х). По существу, метод кодирования алгоритмов - это язык программирования, а код S(A) - это программа алгоритма А в языке S.

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

Значение слова «алгоритм» очень схоже со значениями слов «рецепт», «метод», «процесс». Однако, в отличие от рецепта или процесса, алгоритм характеризуется следующими свойствами:

- дискретностью;

- массовостью;

- определенностью;

- результативностью;

- формальностью.

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

Массовость - применимость алгоритма ко всем задачам рассматриваемого типа, при любых исходных данных.

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

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

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

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

Формы представления алгоритмов.

На практике наиболее распространены следующие формы представления алгоритмов:

Словесная – запись на естественном языке;

- в псевдокодах – полуформализованное описание алгоритма на условном алгоритмическом языке, включающее в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и т.д.;

- табличная;

- графическая – с помощью графических символов;

- программная – запись на искусственном языке (языке программирования).

Словесный способ не имеет широкого применения по следующим причинам:

- описания не строго формализуемы;

- страдают многословностью записей;

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

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

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

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

Блочные символы соединяются линиями переходов, определяющими очередность выполнения действий. В таблице 1 приведены наиболее часто употребляемые символы.

Таблица 1

Графические символы алгоритмов