ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ
Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования
Московский ордена трудового Красного Знамени технический университет связи и информатики
Т.И.Семенова, И.О.Юсков,И.Б.Юскова
Алгоритмизация вычислительных задач
Электронное учебное пособие
для направления
11.03.02– Инфокоммуникационные технологии
исистемы связи
Москва 2017
УДК32.973.26018.2
Семенова Т.И., Юсков И.О., Юскова И.Б. Алгоритмизация вычислительных задач, Электронное учебное пособие/ МТУСИ. – М., 2017. –
64с.
Электронное учебное пособие содержит алгоритмы наиболее часто используемых в инженерной практике и в современных математических пакетах прикладных программ численных методов и методов оптимизации, а также краткое описание приложения MSVisio, позволяющего автоматизировать процесс создания алгоритмов.
Ил. 55, табл. 1, список лит. 4 назв.
Издание утверждено советом факультета Протокол № от
Рецензенты: доцент, к.т.н. Шакин В.Н.
© Московский технический университет связи и информатики, 2017
2
|
Оглавление |
|
ВВЕДЕНИЕ................................................................................................. |
5 |
|
1. |
ОСНОВЫ АЛГОРИТМИЗАЦИИ .............................................................. |
6 |
|
1.1. АЛГОРИТМ, ЕГО СВОЙСТВА .................................................................. |
6 |
|
1.2. БАЗОВЫЕ АЛГОРИТМИЧЕСКИЕ СТРУКТУРЫ............................................... |
8 |
2. |
АЛГОРИТМЫ ЧИСЛЕННЫХ МЕТОДОВ ............................................... |
13 |
|
2.1. АЛГОРИТМЫ МЕТОДОВ РЕШЕНИЯ НЕЛИНЕЙНЫХ УРАВНЕНИЙ ................... |
13 |
|
2.1.1. Метод половинного деления ................................................................ |
13 |
|
2.1.2. Метод итераций ................................................................................... |
14 |
|
2.1.3. Метод Ньютона .................................................................................... |
15 |
|
2.1.4. Метод хорд............................................................................................. |
16 |
|
2.2. АЛГОРИТМЫ МЕТОДОВ ИНТЕРПОЛЯЦИИ ФУНКЦИИ ................................ |
18 |
|
2.2.1. Метод Лагранжа ................................................................................... |
18 |
|
2.2.2. Первая интерполяционная формула Ньютона.................................. |
20 |
|
2.2.3. Вторая интерполяционная формула Ньютона................................. |
22 |
|
2.3. АЛГОРИТМ АППРОКСИМАЦИИ ФУНКЦИИ МЕТОДОМ НАИМЕНЬШИХ |
|
КВАДРАТОВ….. ....................................................................................................24
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 |
|
3. СОЗДАНИЕ СХЕМ АЛГОРИТМОВ С ИСПОЛЬЗОВАНИЕМ |
|
ГРАФИЧЕСКОГО РЕДАКТОРА MS VISIO ............................................................. |
44 |
3.1. НАЗНАЧЕНИЕ MS VISIO ..................................................................... |
44 |
3.2. СОЗДАНИЕ ДОКУМЕНТА, ОТКРЫТИЕ И СОХРАНЕНИЕ ФАЙЛОВ ................... |
44 |
3.3. СОЗДАНИЕ ПРОСТЫХ СХЕМ .................................................................... |
49 |
3.4. НАСТРОЙКА ВНЕШНЕГО ВИДА БЛОКОВ СХЕМЫ АЛГОРИТМА ........................ |
53 |
3.5. РАБОТА С ТЕКСТОМ.............................................................................. |
59 |
СПИСОК ЛИТЕРАТУРЫ.............................................................................. |
64 |
4
Введение
Решение задач с использованием компьютера включает в себя несколько этапов:
1.Постановка задачи.
2.Анализ и исследование задачи.
3.Разработка алгоритма.
4.Программирование.
5.Тестирование и отладка.
6.Анализ результатов решения задачи.
7.Сопровождение программы.
Одним из самых трудоемких и ответственных этапов этой последовательности является этап разработки алгоритма решения задачи. Этот этап можно опустить только при решении очень простых задач. Но для большинства задач перед написанием программы требуется разработать последовательность действий, приводящую к решению задачи, то есть алгоритм ее решения. Причем, при разработке алгоритма сложной задачи целесообразно провести декомпозицию вычислительного процесса. То есть вначале, с целью выявления типовых участков алгоритма и использования для их реализации стандартных или ранее разработанных алгоритмов, составить укрупненную схему алгоритма, а затем детализированную.Следует отметить, что время, потраченное на разработку вначале укрупненного, а затем детализированного алгоритма, полностью окупается на этапах программирования и отладки программы.
Данное пособие содержит все основные сведения, необходимые для создания и оформления схем алгоритмов решения задач, которые используют методы вычислительной математики. Понятие алгоритма, его свойства и способы описания алгоритма решения задачи представлены в первом разделе пособия.
Второй раздел пособия посвящен алгоритмам наиболее распространенных численных методов, используемых при решении вычислительных задач. При этом все схемы алгоритмов оформлены в виде процедур, в каждой из которых в комментариях указан список необходимых для ее выполнения входных (формальных) параметров. Если при решении реальной задачи требуется использование дополнительных переменных, то список формальных параметров должен быть расширен.
В третьем разделе пособия дано краткое описание графического редактора MSVisio, и приведены необходимые сведения, касающиеся автоматизации создания различных схем алгоритмов.
5