Материал: Пособие с Алгоритмами

ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ

Федеральное государственное образовательное бюджетное учреждение

высшего профессионального образования

Московский ордена трудового Красного Знамени технический университет связи и информатики

Т.И.Семенова, И.О.Юсков,И.Б.Юскова

Алгоритмизация вычислительных задач

Электронное учебное пособие

для направления

11.03.02 – Инфокоммуникационные технологии и системы связи

Москва 2017

УДК32.973.26018.2

Семенова Т.И., Юсков И.О., Юскова И.Б. Алгоритмизация вычислительных задач, Электронное учебное пособие/ МТУСИ. – М., 2017. – 64с.

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

Ил. 55, табл. 1, список лит. 4 назв.

Издание утверждено советом факультета

Протокол № от

Рецензенты: доцент, к.т.н. Шакин В.Н.

© Московский технический университет

связи и информатики, 2017

Оглавление

Введение 4

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

1.1. Алгоритм, его свойства 5

1.2. Базовые алгоритмические структуры 7

2. Алгоритмы численных методов 12

2.1. Алгоритмы методов решения нелинейных уравнений 12

2.1.1. Метод половинного деления 12

2.1.2. Метод итераций 13

2.1.3. Метод Ньютона 14

2.1.4. Метод хорд 15

2.2. Алгоритмы методов интерполяции функции 17

2.2.1. Метод Лагранжа 17

2.2.2. Первая интерполяционная формула Ньютона 19

2.2.3. Вторая интерполяционная формула Ньютона 21

2.3. Алгоритм аппроксимации функции методом наименьших квадратов 24

29

2.4. Алгоритмы методов численного интегрирования 30

2.4.1. Метод средних прямоугольников 30

2.4.2. Метод трапеций 32

2.4.3. Метод Симпсона 33

2.5. Алгоритмы методов решения обыкновенных дифференциальных уравнений 34

2.6. Алгоритмы методов одномерной оптимизации 36

2.6.1. Метод дихотомии 36

2.6.2. Метод золотого сечения 37

2.6.3. Метод средней точки 38

2.7. Алгоритмы методов многомерной оптимизации 39

3. Создание схем алгоритмов с использованием графического редактора MS Visio 44

3.1. Назначение MS Visio 44

3.2. Создание документа, открытие и сохранение файлов 44

3.3. Создание простых схем 49

3.4.Настройка внешнего вида блоков схемы алгоритма 53

3.5. Работа с текстом 59

Список литературы 64

Введение

Решение задач с использованием компьютера включает в себя несколько этапов:

1. Постановка задачи.

2. Анализ и исследование задачи.

3. Разработка алгоритма.

4. Программирование.

5. Тестирование и отладка.

6. Анализ результатов решения задачи.

7. Сопровождение программы.

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

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

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

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

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

   1. Алгоритм, его свойства

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

К основным свойствам алгоритмов можно отнести:

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

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

3. Однозначность - правила и порядок выполнения действий алгоритма имеют единственное толкование.

4. Конечность - действия и алгоритм в целом обязательно завершаются.

5. Результативность - по завершении выполнения алгоритма обязательно получается конечный результат.

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

• вычислительные алгоритмы, работающие со сравнительно простыми видами данных, такими как числа и матрицы, хотя сам процесс вычисления может быть долгим и сложным;

• информационные алгоритмы, представляющие собой набор процедур, работающих с большими объемами информации (алгоритмы баз данных);

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

Для записи алгоритмов используют самые разнообразные средства. Выбор средства определяется типом исполняемого алгоритма.

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

• вербальный (словесный)- последовательность действий, описанная на естественном языке;

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

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

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

Для графического описания алгоритмов используются стандартные графические блоки, начертание и размеры которых регламентируются соответствующим ГОСТом[1]. В табл.1.1-1 приведен перечень основных обозначений, принятых в схемах алгоритмов.

Таблица 1.1-1

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

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

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

2. Базовые алгоритмические структуры

Базовыми алгоритмическими структурами принято называть подмножество алгоритмических структур, которые позволяют составить алгоритм решения сколь угодно сложной задачи[2]. Эти структуры могут быть использованы в качестве составляющих разработчиком программы в зависимости от специфики решаемой задачи. К базовым алгоритмическим структурам относятся:

• последовательные структуры;

• разветв­ляющиеся структуры;

• циклические структуры регулярного типа;

• циклические структуры итеративного типа.

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

Рис. 1.2-1. Последовательная алгоритмическая структура

Разветвляющимися называются такие алгоритмические струк­туры, в которых порядок выполнения функциональных блоков определяется значе­ниями логических выражений. Если логическое выражение принимает значение «Истина», то выполняется часть алгоритма, расположенная по ветви «Да», если принимает значение «Ложь», то – часть алгоритма по ветви «Нет».Разветвляющиеся структуры могут быть достаточно сложными, но среди них можно выявить три основных типа разветвлений: стандартное, усеченное и вложенное.

Стандартное разветвлениесодержит функциональные блоки как в ветви «Да», так и в ветви «Нет» (рис.1.2-2).

Рис.1.2-2. Стандартное разветвление

Усеченное разветвление содержит функциональные блоки только в ветви «Да» или только в ветви «Нет» (рис.1.2-3).

Рис. 1.2-3. Типы усеченных разветвлений

Вложенное разветвление содержит одно или несколько дополнительных разветвлений (рис.1.2-4). 

Рис. 1.2-4. Вложенное разветвление

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

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

-регулярные циклические структуры– это циклические структуры с заранее известным числом повторений;

- итеративной циклической структурой– это циклические структуры с заранее неизвестным числом повторений цикла.

Общий вид алгоритма регулярной циклической структуры приведен нарис.1.2-5.

Рис.1.2-5. Регулярная циклическая структура

Здесь в блоке организации цикла используется специальная пере­менная, которая предназначена для определения условия останова цикла (i). Эта переменная называется параметром цикла. Блоки, следующие за заголовком цикла, составляют тело цикла. Тело цикла выполняется для всех значений параметра цикла i, начинаю­щегося со значения m1и изменяющегося с шагом m3 до значения m2.

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

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

При организации цикла с предусловием (рис.1.2-6) условие выхода из цикла (или выполнения) предшествуют блокам тела цикла, и они выполняются только, если условие L принимает значение «Истина». Выход из цикла происходит при первом невыполнении этого условия. Таким образом, возможен случай, когда тело цикла не будет выполнено ни разу.

Рис. 1.2-6. Итеративная циклическая структура с предусловием

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

Рис.1.2-7. Итеративная циклическая структура с постусловием

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

(а) (б)

Рис. 1.2-8. Ввод двумерного массива в укрупненном (а) и

детализированном (б) алгоритмах

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