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

   Введение

1. Основы алгоритмизации

1.1 Понятие алгоритма  и его свойства

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

2. Основы программирования

3. Понятие формализация

 

ВВЕДЕНИЕ

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

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

На лекции 5 мы рассмотрели понятие программного обеспечения и его классификацию.

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

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

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

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

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

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

1. ОСНОВЫ АЛГОРИТМИЗАЦИИ

1.1 Понятие  алгоритма и его свойства

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

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

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

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

Понятие алгоритма, раскрывающее его сущность на интуитивном  уровне, следующее:

Алгоритм - точно определенное правило действий, для которого задано указание, как и в какой последовательности это правило необходимо применять к исходным данным задачи, чтобы получить ее решение за конечное число шагов^** Название «алгоритм» произошло от латинской формы имени величайшего среднеазиатского математика Мухаммеда ибн Муса ал-Хорезми (Alhorithmi), жившего в 783-850 гг. В своей книге «Об индийском счете» он изложил правила записи натуральных чисел с помощью арабских цифр и правила действий над ними «столбиком». В XII веке эта книга была переведена на латынь и получила широкое распространение в Европе..

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

Формула для  нахождения корней квадратного уравнения

также является своеобразной формой записи алгоритма.

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

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

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

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

Основные свойства алгоритмов следующие:

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

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

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

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

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

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

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

· графическая - изображение алгоритма в виде схемы, состоящей из графических символов;

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

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

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

Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных в произвольном изложении на естественном языке.

Пример 1. Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел (алгоритм Эвклида).

Алгоритм можно  описать так:

1. Задать два  числа.

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

3. Определить  большее из чисел.

4. Заменить большее  из чисел разностью большего  и меньшего из чисел.

5. Повторить  алгоритм с шага 2.

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

Словесный способ не имеет широкого распространения, так как такие описания:

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

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

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

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

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

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

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

 

 

 

 

Таблица 1.1. Графические примитивы схем алгоритмов

Название примитива	Обозначение и  пример заполнения	Пояснение
Процесс		Вычислительное действие или последовательность действий
Решение		Выбор направления  выполнения алгоритма или программы  в зависимости от некоторых изменяемых условий
Модификация		Начало циклического процесса
Предопределенный  процесс		Вычисления  по подпрограмме, стандартной подпрограмме
Ввод-вывод		Преобразование  данных в форму, пригодную для  обработки (ввод) или отображения  полученных результатов (вывод)
Пуск-останов		Начало, конец  алгоритма, вход и выход в подпрограмму
Документ		Вывод результатов  на печать
Комментарий		Связь между  элементом схемы и пояснением
Узел		Указание связи  между прерванными линиями потока, связывающего символы
Ссылка на другую страницу		Обозначение связи  между различными частями схемы  алгоритма, размещенных на разных страницах
Линия потока		Обозначение последовательности связей между символами

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

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

2. Внутри примитива  дается краткое описание соответствующего  шага.

3. Любой шаг  или поток можно сопроводить  пояснением с помощью примитива  «Комментарий».

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

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

6. Расстояние  между параллельными линиями  потока должно быть не менее  3 мм, а между другими символами  - не менее 5 мм.

7. Линию потока  можно обрывать, используя на месте обрыва примитив «Узел» в пределах одной страницы или примитив «Ссылка на другую страницу», если надо указать переход на другую страницу.

8. Размеры примитивов  фиксированы. Если через b обозначить ширину элемента, а через а его высоту, то размер b = 1,5а, причем а должно принимать значения 10, 15, 20 мм. Допускается увеличивать размер а на величину, кратную 5.

Составление схем алгоритмов регламентируется двумя  ГОСТами:

· ГОСТ 19.002-80 соответствует международному стандарту ИСО 2636-73 и определяет правила составления схем алгоритмов;

· ГОСТ 19.003-80 соответствует международному стандарту ИСО 1028-73 и регламентирует использование графических примитивов.

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

Пример 2. Необходимо составить алгоритм вычисления суммы элементов вектора , т.е.

Для определения  суммы применим алгоритм ее накопления, используя рекуррентное соотношение

S_i := S_i-1 + a_i; S₀ = 0; i := 1, 2, ..., n,

где S_i -- текущее значение суммы;

S_i-1 -- предыдущее ее значение;

S₀ -- начальное значение суммы;

a_i -- значение текущего элемента вектора.

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

Схема алгоритма приведена  на рис. 1.1. Поясним ее.

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

2. Начальные данные вводятся  в память компьютера. Для обозначение  этой операции используется символ  «Ввода-вывода», внутри которого указываются, какие элементы вводятся.

3. Сумме присваивается  начальное значение, равное нулю (S:=0). Это означает пересылку 0 в область памяти, предназначенную для накопления суммы. Операция на схеме отображается символом «Процесс». Принятое обозначение суммы S расшифровывается символом «Комментарий».