Прикладная информатика

Министерство образования и науки Российской Федерации

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

ФАКУЛЬТЕТ ДИСТАНЦИОННОГО ОБУЧЕНИЯ (ФДО)

П. С. Мещеряков

ПРИКЛАДНАЯ ИНФОРМАТИКА

Учебное пособие

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

Томск
2015

УДК
004.94:51(075.8)
ББК
32.973.2я73
М 565

Рецензенты:

Крайнов А. Ю., докт. физ.-мат. наук, профессор Национального
исследовательского Томского политехнического университета;

Силич В. А., докт. техн. наук, профессор кафедры экономической математики,
информатики и статистики ТУСУРа.

Мещеряков П. С.
М 565
Прикладная информатика : учебное пособие. / П. С. Мещеряков. —
Томск : факультет дистанционного обучения ТУСУРа, 2015. — 130 с.

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

Учебное пособие по дисциплине «Прикладная информатика» предназначено для студентов факультета дистанционного обучения ТУСУРа.

УДК
004.94:51(075.8)
ББК
32.973.2я73

Мещеряков П. С., 2015

Оформление.
ФДО, ТУСУР, 2015

ОГЛАВЛЕНИЕ

Введение
5

I
Теоретический раздел
8

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

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

1.2
Структурное программирование . . . . . . . . . . . . . . . . . . . . . . .
12

1.3
Пошаговая разработка программ . . . . . . . . . . . . . . . . . . . . . . .
13

1.4
Рекуррентные алгоритмы . . . . . . . . . . . . . . . . . . . . . . . . . . .
14

1.5
Рекурсия
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
19

1.6
Структуры данных . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20

2
Информатика и электрические цепи
23

2.1
Модель цепи в пространстве состояний . . . . . . . . . . . . . . . . . .
23

2.2
Получение модели цепи в пространстве состояний на основе
системы уравнений Кирхгофа . . . . . . . . . . . . . . . . . . . . . . . .
24

2.3
Пример построения модели цепи в пространстве состояний
. . . . .
25

2.4
Проблема вычислений . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
28

3
Численные алгоритмы
30

3.1
Решение систем линейных уравнений . . . . . . . . . . . . . . . . . . .
31

3.1.1
Метод Гаусса . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33

3.1.2
Обусловленность матрицы . . . . . . . . . . . . . . . . . . . . . .
34

3.1.3
Большие разреженные системы . . . . . . . . . . . . . . . . . . .
38

3.2
Собственные значения и собственные вектора . . . . . . . . . . . . . .
42

3.2.1
Метод непосредственного развертывания . . . . . . . . . . . . .
42

3.2.2
Метод итераций . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44

3.3
Интерполяция . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44

3.3.1
Полиномиальная интерполяция . . . . . . . . . . . . . . . . . . .
45

3.3.2
Сплайн-интерполяция . . . . . . . . . . . . . . . . . . . . . . . . .
47

3.4
Численное интегрирование . . . . . . . . . . . . . . . . . . . . . . . . . .
49

3.4.1
Формула прямоугольников . . . . . . . . . . . . . . . . . . . . . .
50

3.4.2
Формула трапеций . . . . . . . . . . . . . . . . . . . . . . . . . . .
51

3.4.3
Формула Симпсона . . . . . . . . . . . . . . . . . . . . . . . . . .
52

3.5
Численное решение задачи Коши для обыкновенных
дифференциальных уравнений . . . . . . . . . . . . . . . . . . . . . . . .
53

3.5.1
Метод Эйлера . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
54

3.5.2
Ошибки численного интегрирования . . . . . . . . . . . . . . .
56

3.5.3
Методы Рунге—Кутта . . . . . . . . . . . . . . . . . . . . . . . . .
58

Оглавление

3.5.4
Многошаговые методы Адамса . . . . . . . . . . . . . . . . . . .
61

3.5.5
Неявные разностные формулы . . . . . . . . . . . . . . . . . . .
62

3.5.6
Устойчивость разностных схем . . . . . . . . . . . . . . . . . . .
63

3.6
Решение трансцендентных уравнений . . . . . . . . . . . . . . . . . . .
65

II
Прикладной раздел
70

4
Методы решения СЛАУ
71

4.1
Метод Гаусса . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
71

4.2
Метод прогонки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
75

4.3
Итерационные методы решения СЛАУ . . . . . . . . . . . . . . . . . . .
76

4.3.1
Метод простых итераций . . . . . . . . . . . . . . . . . . . . . . .
77

4.3.2
Метод итераций . . . . . . . . . . . . . . . . . . . . . . . . . . . .
79

5
Вычисление полиномов
82

6
Интерполяция
83

7
Численное интегрирование
86

7.1
Метод прямоугольников . . . . . . . . . . . . . . . . . . . . . . . . . . . .
86

7.2
Метод трапеций . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
88

7.3
Метод Симпсона
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
89

8
Численное решение задачи Коши для
обыкновенных дифференциальных уравнений
90

8.1
Метод Эйлера . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
90

8.2
Метод Рунге—Кутта . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
91

9
Решение трансцендентных уравнений
94

9.1
Метод половинного деления . . . . . . . . . . . . . . . . . . . . . . . . .
94

9.2
Метод Ньютона . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
95

9.3
Метод секущих . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
96

10 Указания к выполнению лабораторных работ
97

11 Варианты заданий
98

Задание №1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
98

Задание №2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
Задание №3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
Задание №4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115

Заключение
120

Литература
121

Глоссарий
122

Предметный указатель
128

ВВЕДЕНИЕ

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

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

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

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

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

Введение

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

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

Соглашения, принятые в книге

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Эта пиктограмма означает определение или новое понятие.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

. . .. . . . . . . . . . . . . . . . . . . . . .
Пример
. . .. . . . . . . . . . . . . . . . . . . . . .

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

Соглашения, принятые в книге
7

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Контрольные вопросы по главе
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

РАЗДЕЛ I

Теоретический

Глава 1

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

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

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

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

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

Шаг 1. Присвоить P значение 0.

Шаг 2. Присвоить K значение 0.

Шаг 3. Если I равно 0 или J равно 0, то перейти к шагу 7.

Шаг 4. Присвоить P значение P + I.

Шаг 5. Присвоить K значение K + 1.

Шаг 6. Если K меньше J, то перейти к шагу 4.

Шаг 7. Конец.

РАЗДЕЛ I. Теоретический

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

Исчерпывающее определение алгоритма дано выдающимся отечественным
математиком А. А. Марковым [5]. Алгоритм — это точное, общепринятое предписание, определяющее процесс преобразования исходных данных в искомый результат. Алгоритм должен обладать следующими свойствами:

определенностью, т. е. точностью, не оставляющей места для произвола,
и общепонятностью;

выполнимостью (или массовостью), т. е. возможностью исходить из любых исходных данных, принадлежащих некоторому множеству G исходных
данных;

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

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

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

Для работоспособности алгоритма каждая из этих инструкций должна удовлетворять условиям определенности и выполнимости [4].

Для определенности алгоритма каждая из составляющих его инструкций должна быть определена четко и недвусмысленно. Если алгоритм выражен на какомнибудь естественном языке, то возможно появление неоднозначности. Рассмотрим
третий шаг алгоритма умножения (на примере, приведенном ранее). Если I равно 0, то должен произойти переход на шаг 7, если J равно 0 — произойдет то же
самое, но что произойдет, если I, и J равны 0? В математической логике условие
«A или B» истинно, если A истинно или B истинно, или истинны — A и B. Но
в русском и, особенно, английском языках под словом «или» вполне может подразумеваться исключение случая, когда оба случая истинны (т. е. если под этим выражением подразумевается оборот «или. . .или. . .», для которого в математической
логике предусмотрена операция «исключающего или» — XOR). Таким образом, пока мы оговорили точное значение термина «или», шаг 3 не будет определенным.

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

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

полнимой, демонстрирует следующий простой пример — вычислить наибольшее
вещественное число, меньшее единицы. Ясно, что с точки зрения математики такое число определить невозможно, например если выбрать число 0.9999, число
0.99994 будет больше и т. д.

Обеспечить выполнимость алгоритма — означает исключить из него все невыполнимые инструкции; обеспечить определенность — означает исключить неясные
или бессмысленные инструкции.

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

Шаг 1. Присвоить I значение 0.

Шаг 2. Присвоить I значение I+1.

Шаг 3. Перейти к шагу 2.
Для любого алгоритма желательно доказать его конечность (хотя бы неформально). К сожалению, такие доказательства обычно чрезвычайно сложны. При
этом можно выделить два класса алгоритмов.

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

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

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

РАЗДЕЛ I. Теоретический

1.2 Структурное программирование

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

оператор присваивания «:=»;

условный оператор «if. . .then. . .else»;

оператор цикла «do. . .while».

Хотя этих трех операторов достаточно для построения программ различной
сложности, вышесказанное не надо воспринимать как догму [1]. Разумеется, вполне допустимы и другие структурные операторы — оператор выбора, другие операторы цикла и т. д. Структурное программирование предполагает при построении
программ метод пошаговой детализации, при котором, вначале разрабатывается
общая структура программы, состоящая из записи алгоритма не с помощью элементарных операций, а более крупными блоками. Впоследствии, на следующих
этапах каждый из этих блоков детализируется на более мелкие, пока в результате
не получатся элементарные действия, которые можно выразить непосредственно
средствами языка программирования.

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

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

Несколько принципов, которыми желательно пользоваться при написании программ.

1. Не применять всевозможные трюки или заумные методы. Не надо использовать сложные методы там, где есть простые.

2. Использовать как можно меньше переходов goto. Автор языка Паскаль
Н. Вирт предлагает их использовать только для выхода из циклов, многократно вложенных друг в друга.

3. Операторы цикла должны быть использованы самым простым образом. Не
надо использовать цикл do. . .while там, где проще и нагляднее выглядит
цикл for. . .to. . .do.

4. Громоздкие программы, состоящие из одной основной программы, как правило, невозможно читать. Зачастую глубина вложенности циклов и условных операторов такова, что для каждого if. . .then затруднительно найти
соответствующий else. Чтобы обойти указанную трудность, каждую боль