Астахова Е.В. Теоретические основы информатики

Подождите немного. Документ загружается.

где n — число состояний системы; р

— вероятность (относительная частота)

перехода системы в i-е состояние (сумма всех p

равна 1).

Исходы называются равновероятными, если они могут совершиться с равной

долей вероятности.

S Для равновероятных состояний р

= 1/n, I = log

В общем случае выполняется неравенство:

S Сообщение о наступлении события с меньшей вероятностью несет в себе больше

информации, чем сообщение о наступлении события с большей вероятностью.

S Сообщение о наступлении достоверно наступающего события несет в себе нулевую

информацию.

Пример 1. Определить, сколько бит информации несет произвольное двузначное

десятичное число со всеми значащими цифрами. Каждая из возможных цифр может

появиться на данном месте, в данном разряде с одинаковой вероятностью. Так как таких

чисел может быть всего 90 (10-99), то количество информации будет I = log

(приблизительно I = 6,5). Так как в двузначных числах первая значащая цифра может

принимать 9 значений (1-9), а вторая — 10 значений (0-9), то I = log

90 = log

9 + log

10.

Итак, сообщение в одну десятичную единицу несет в себе в 3,32 (значение log

10) больше

информации, чем в одну двоичную единицу (log

2 = 1). Вторая цифра в двузначном

десятичном числе несет в себе больше информации, чем первая.

Количество информации I можно понимать как среднеарифметическое величин

= - nlog

.Тогда f

можно интерпретировать как информационное содержание символа

алфавита с индексом i и величиной p

вероятности появления этого символа в сообщении.

Пример 2. Определить количество информации в сообщении из 4-х букв "a", 2-х

букв "б", 1-й буквы "и", 6-ти букв "р". Число N различных сообщений длиной 13 букв

будет равно величине: N=13!/(4!×2!×1!×6!)=180180. Количество информации I в одном

сообщении будет равно величине: I=log

(N)=log

180180≈18 (бит).

Пусть по результатам некоторого опыта получено n сообщений с вероятностью p

Тогда количество информации в i-том сообщении определяется по формуле: I = - log

Пример 3. Определить количество информации в сообщении о результатах сдачи

экзамена нерадивым студентом, если известны вероятности получения оценок:

«отлично» — р(5) = 0,1;

«хорошо» — р(4) = 0,2;

«удовлетворительно» — р(3) = 0,4;

«неудовлетворительно» — р(2) = 0,3.

Тогда количество информации в каждом сообщении будет равно:

I(5) = - log

0,1 = 3,32;

I(4) = - log

0,2 = 2,32;

I(3) = - log

0,4 = 1,32;

I(3) = - log

0,3 = 1,74.

Пример 4. Определить среднее количество информации в сообщении о

результатах сдачи экзамена нерадивым студентом. По формуле Шеннона получим:

ср

= - (0,1* log

0,1 + 0,2* log

0,2 + 0,4* log

0,4 + 0,3* log

0,3) = 1,73.

S Если у опыта два равновероятных исхода, то I

ср

= - (0,5* log

0,5 + 0,5* log

0,5) = 1.

Это аналитическое определение бита по Шеннону.

1.6.3. Термодинамическая мера

В реальной жизни всегда присутствует некоторая степень неопределенности.

Л. Бриллюэн охарактеризовал информацию как отрицательную энтропию. Так как

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

мера упорядоченности материальных систем.

Пусть потребитель имеет предварительные сведения о системе α до получения

информации. Н (β) — мера его неосведомленности о системе (или мера неопределенности

состояния системы). I

(α) — дополнительная информация после получения сообщения β,

уменьшившая неопределенность состояния системы Н

(α).

Количество информации о системе, полученной в сообщении β:

(α) = Н(α) - Н

(α)

Другими словами, количество информации измеряется изменением

неопределенности состояния системы.

S Энтропия системы Н(α) может рассматриваться как мера недостающей информации.

Информационно-термодинамический подход связывает величину энтропии

системы с недостатком информации о внутренней структуре. Число состояний определяет

степень неполноты сведений о системе.

Пусть дана термодинамическая система (процесс) S, а Н

, Н

—

термодинамические энтропии системы S в начальном (равновесном) и конечном

состояниях термодинамического процесса. Тогда термодинамическая мера информации

(негэнтропия) определяется формулой: Н(Н

,Н

) = Н

- Н

. Уменьшение Н(Н

,Н

) говорит о

приближении термодинамической системы S к состоянию статического равновесия, а

увеличение — об удалении.

Пусть до начала процесса можно дать p

равновероятных ответов на вопрос о

состоянии термодинамической системы, а после окончания процесса — p

ответов.

Изменение информации определяется выражением ΔI = k ln(p

/ p

) = k (ln p

- ln p

Если p

(ΔI>0), то сведения о системе стали более определенными. Если p

(ΔI<0) — менее определенными.

Пример. Имеется термодинамическая система — газ в объеме V , который

расширяется до объема 2V. Каковы координаты молекулы m газа в новом объеме? До

расширения объема координаты были известны p

=1 (lnp

=0). Число ответов было

пропорционально lnV. После расширения мы знаем эту координату по изменившейся

информации о состоянии системы как ΔI = -k ln(2V /V) = -k ln 2 (нат).

Величина ΔI может быть интерпретирована как количество информации,

необходимой для перехода от одного уровня организации системы к другому (при ΔI>0 —

более высокому, а при ΔI>0 — более низкому уровню организации).

1.6.4. Семантический подход

Для оценки количества информации с позиций целесообразности используется

формула I = log(p

/ p

), где р

— вероятность достижения цели после получения

сообщения, р

— вероятность достижения цели до получения сообщения.

Пример. Определить количество информации, содержащейся в шпаргалке, если

известно, что вероятность сдачи экзамена без шпаргалки равна 0,2. Использование

шпаргалки увеличивает вероятность сдачи до 0,8.

Следовательно, I = log

(0,8/0,2) = log

4 = 2. Пусть шпаргалка содержала неверную

информацию, вследствие чего вероятность сдачи экзамена уменьшилась до 0,1. Тогда

I = log

(0,1/0,2) = log

0,5 = -1. Отрицательный знак результата говорит о дезинформации.

1.7 ПОЛОЖЕНИЯ КОМБИНАТОРИКИ, ИСПОЛЬЗУЕМЫЕ В ИЗМЕРЕНИИ

ИНФОРМАЦИИ

;

Комбинаторика – раздел дискретной математики, изучающий способы

формирования подмножеств из элементов исходного множества.

Из конечного счетного множества элементов мощности h можно сформировать

такие виды комбинаций элементов как:

1. Сочетания — группировка элементов исходного множества в подмножества

одинаковой мощности так, что элементы в них отличаются составом, а порядок элементов

произвольный. Число сочетаний из h элементов по L без повторений: C(

) = h!/(L!(h - L)!).

Пример. Пусть {a,b,c} — исходное множество мощности h=3. По правилу

сочетаний можно получить следующие подмножества мощности 2: {a,b}, {a,c}, {b,c}.

Множества типа {a,b}, {b,a} являются идентичными и не формируются. Число сочетаний

из трех элементов по два без повторений С(

) = 3!/(2!(3 - 2)!) = 3.

2. Перестановки — группировка элементов исходного множества в подмножества

одинаковой мощности так, что элементы в них отличаются только порядком. Число

перестановок из h элементов без повторений: П(h) = h!

Пример. Пусть {a,b,c} — исходное множество мощности h=3. По правилу

перестановок можно получить следующие подмножества: {a,b,c}, {a,c,b}, {b,c,a}, {b,a,c},

{c,a,b}, {c,b,a}. Число перестановок из трех элементов по три П(3) = 3! = 6.

3. Размещения — группировка элементов исходного множества в подмножества

одинаковой мощности так, что элементы в них отличаются и составом и порядком. Число

размещений из h элементов по L без повторений: Р(

) = h!/(h - L)!

Пример 1. Пусть {a,b,c} — исходное множество мощности h=3. По правилу

размещений можно получить следующие подмножества мощности 2: {a,b}, {a,c}, {b,c},

{b,a}, {c,a}, {c,b}. Число размещений из трех элементов по два без повторений

Р(

) = 3!/(3 - 2)! = 6.

Число размещений из h элементов по L с повторениями: Р

(

) = h

Пример 2. Пусть {0,1} — исходное множество мощности h=2. По правилу

размещений можно получить следующие подмножества мощности 3: {0,0,0}, {0,0,1},

{0,1,0}, {1,0,0}, {1,1,0}, {1,0,1}, {0,1,1}, {1,1,1}.

Число размещений из двух элементов по три с повторениями Р

(

) = 2

= 8.

S Определить количество различных последовательностей из символов «*» и «#»

длиной в 5 символов. (Ответ: 32)

1.8 ИНФОРМАЦИОННЫЙ ПРОЦЕСС

Под информационными процессами понимаются любые действия, выполняемые

над информацией. При работе с информацией всегда имеется ее источник и потребитель.

;

Информационные коммуникации — это пути и процессы, обеспечивающие

передачу сообщений от источника информации к ее потребителю.

При передаче информации от источника потребителю она проходит фазы,

составляющие информационный процесс:

• восприятие (сбор);

• передачу данных (скорость, пропускная способность, защита от шума);

• хранение данных (объем информации, надежность, время доступа);

• обработку данных (математические вычисления, логические рассуждения,

поиск, кодирование).

Информационный процесс может проходить только в системе, в которой

присутствует

человек, например, процессы познания, обучения, управления.

;

Информационное взаимодействие — это взаимодействие между людьми

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

мнениях, представлениях, знаниях.

1.9 ИНФОРМАЦИОННЫЕ СИСТЕМЫ

;

Система — это совокупность элементов, находящихся в отношениях и связях

между собой и образующих определенную целостность.

Система создается для описания каких-то процессов. Если процесс

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

образования, система экономики, правовая система.

;

Информационная система — это взаимосвязанная совокупность средств,

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

интересах достижения поставленной цели.

;

Информационная система — это организационно упорядоченная совокупность

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

Управление системой (в системе) используется в целях:

• увеличения скорости передачи сообщений;

• увеличения объема передаваемых сообщений;

• уменьшения времени обработки сообщений;

• модификации связей системы.

Управление любой системой можно представить в виде общей схемы (рис. 2).

Рис. 2 Схема управления системой

1.10 МЕТОДЫ ПОЛУЧЕНИЯ И ИСПОЛЬЗОВАНИЯ ИНФОРМАЦИИ

Методы получения и использования информации можно разделить на три группы:

1. Эмпирические (наблюдение, сравнение, измерение, эксперимент).

2. Теоретические:

a. восхождение от абстрактного к конкретному;

b. идеализация — представление систем, не существующих в

действительности;

c. формализация — математическое, формальное описание;

d. виртуализация — создание особой среды для исследуемого объекта.

3. Эмпирико-теоретические:

a. абстрагирование — установление общих свойств объекта, замещение

его моделью;

b. анализ — разъединение системы на подсистемы с целью выявления их

взаимосвязей;

c. декомпозиция — разъединение системы на подсистемы с сохранением

их взаимосвязей с окружением;

d. синтез — соединение подсистем в систему с целью выявления их

взаимосвязей;

e. композиция — соединение подсистем в систему с сохранением их

взаимосвязей с окружением;

Управляющая

система

Управляемая

система

Внешняя среда

Управляющее воздействие

Информация о состоянии

выхода и внутренних текущих

состояний системы

Информация о реакции на

управление

Информация о режиме и

способах управления

f. индукция — получение знания о системе по знаниям о подсистемах;

g. дедукция — получение знания о подсистемах по знаниям о системе;

h. эвристики — получение знания о системе по знаниям о подсистемах,

наблюдениям и опыту;

i. моделирование — получение знания об объекте с помощью модели;

j. макетирование — представление подсистем в упрощенном виде;

k. мониторинг — наблюдение и анализ состояния системы;

l. имитация — подражание;

m. верификация — сопоставление с опытом.

2 ЛОГИЧЕСКИЕ ОСНОВЫ ЭВМ

2.1 ОСНОВНЫЕ ПОНЯТИЯ АЛГЕБРЫ ЛОГИКИ

 Алгебра логики (булева алгебра) занимается исчислением высказываний и

применяется для описания работы дискретных устройств, к которым относятся и ЭВМ.

Любая формальная математическая система состоит из трех множеств: элементов,

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

бинарными символами {0,1} или логическими значениями {Истина (1), Ложь (0)}.

Элементы бинарной алгебры B = {0,1} называются константами или логическими нулем и

единицей.

;

Утверждение — основная единица, неделимая с точки зрения отражения смысла

информации.

;

Высказывание — повествовательное утверждение, про которое можно однозначно

сказать, истинно оно или ложно.

;

Предикат — высказывательная форма с логическими переменными, имеющая

смысл при любых допустимых значениях этих переменных.

S «Теплое лето», «Берегись автомобиля» — утверждения.

S «Москва — столица РФ», «Юпитер — ближайшая к Солнцу планета» — высказывания.

S «х > 100» — предикат.

;

Логические связки — это слова и словосочетания «не», «и», «или», «если …, то»,

«тогда и только тогда» и т.п.

Логические связки позволяют из элементарных высказываний строить новые

составные высказывания.

Элементарные высказывания «Иванов — студент», «Иванов — футболист». Связка

«И» дает составное высказывание: «Иванов — студент, хорошо играющий в футбол».

S Истинность составного высказывания зависит от истинности или ложности

элементарных высказываний.

S Логические связки рассматриваются как операции над логическими высказываниями.

Базовые логические операции булевой алгебры (по убыванию приоритета):

НЕ — логическое отрицание;

И — логическое умножение (конъюнкция);

ИЛИ — логическое сложение (дизъюнкция).

;

Таблица истинности — таблица всех значений некоторой логической функции.

S Булева функция n переменных полностью определяется таблицей из 2

строк.

Базовые операции булевой алгебры

Переменные Логические операции

Х Y

∧

Y Х∨Y

0 0 0 0 1

0 1 0 1 1

1 0 0 1 0

1 1 1 1 0

Кроме базовых операций существуют достаточно важные операции, такие как:

1. Импликация (X→Y) ≡ (¬X∨Y)

2. Эквивалентность (X↔Y) ≡ (X∧Y∨¬X∧¬Y)

S Доказать с помощью таблицы истинности, что логическая функция F = ¬A&B∨¬(A&B)

принимает значение Ложь (0) при А = 1, В = 1.

S Определить по таблице истинности логическую операцию в последнем столбце

a b c

∨b (a∨b) ? с

0 0 0 0 0 Варианты ответа:

0 0 1 0 1

1. (a

∨b)&(c∨¬c)

0 1 0 1 1

2. (a

∨b)∨c

0 1 1 1 1

3. (a

∨b)&c

1 0 0 1 1

¬(a∨b)

1 0 1 1 1

1 1 0 1 1

1 1 1 1 1

S Логические функции эквивалентны, если совпадают их таблицы истинности.

;

Тавтологии — всегда истинные формулы.

Основные законы (аксиомы) булевой алгебры

¬(¬X) = Х

Двойное отрицание

X∧Y = Y∧Х; X∨Y = Y∨Х

Коммутативность

(X∨Y)∨Z = X∨(Y∨Z) = X∨Y∨Z

(X∧Y)∧Z = X∧(Y∧Z) = X∧Y∧Z

Ассоциативность

X∧X = X; X∨X = X

Идемпотентность

X∨(X∧Y) = Х; X∧(X∨Y) = Х

Поглощение

X∨(Y∧Z) = (X∨Y)∧(X∨Z)

X∧(Y∨Z) = (X∧Y)∨(X∧Z)

Дистрибутивность

¬(X∨Y) = ¬X∧¬Y

¬(X∧Y) = ¬X∨¬Y

Моргана (перенесение бинарной

операции на операнды)

X∨(Y∧¬Y) = Х

X∧(Y∨¬Y) = Х

Нейтральность

¬0 = 1; ¬1 = 0;

¬Х∨Х = 1; ¬Х∧Х = 0

Существование единицы

Из аксиом можно вывести ряд полезных соотношений:

Х∧1 = Х Х∧0 = 0 Х∨0 = Х Х∨1 = 1

Рассмотрим сложение по mod 2 (неравнозначность)

1 ⊕ X = ¬X 0 ⊕ X = X X ⊕ ¬X = 1

S X ⊕ X ⊕ X ⊕…….⊕ X = X — при нечетном числе членов, 0 — при четном.

Таблица истинности для неравнозначности

Переменные Mod 2

Х Y

⊕

0 0 0

0 1 1

1 0 1

1 1 0

2.2 ФОРМАЛИЗАЦИЯ ВЫСКАЗЫВАНИЙ

Формализация высказывания заключается в замене его логической формулой,

составленной из логических переменных и символов логических операций.

Пример. Иванов, Петров и Сидоров утверждают, что видели виновника ДТП.

Иванов говорит, что это были белые «Жигули», Петров — что черная «Волга», Сидоров —

что «Москвич», но не белый. Как определить истинный цвет и марку автомобиля?

Составим простые высказывания:

X = «машина — белая», Y = «машина — жигули», Z = «машина — черная»,

U = «машина — волга», V = «машина — москвич»

На основе высказываний запишем логические выражения для каждого очевидца

Иванов: X∧Y Петров: Z

∧

U Сидоров: ¬X∧V

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

значение «истина». Тогда будут истинны и дизъюнкции вида:

X∨Y = 1 Z∨U = 1 ¬X∨V = 1

По определению конъюнкции получим следующее выражение

(X∨Y) ∧(Z∨U) ∧(¬X∨V) = 1 (*)

Упростим данное выражение

(X∨Y) ∧(Z∨U) ∧(¬X∨V) = (X∧Z∨Y∧Z∨X∧U∨Y∧U)∧(¬X∨V) =

= X∧Z∧¬X∨Y∧Z∧¬X∨X∧U∧¬X∨Y∧U∧¬X∨X∧Z∧V∨Y∧Z∧V∨X∧U∧V∨Y∧U∧V =

= 0∨Y∧Z∧¬X∨0∨0∨0∨0∨0 = Y∧Z∧¬X = 1.

Откуда следует, что конъюнкция истинна при Y = 1, Z = 1, ¬X = 1. Поскольку два

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

заключение, что автомобиль был черными жигулями. Аналогичный вывод может быть

получен и при составлении таблицы истинности для выражения (*).

S Формализовать высказывание: «Если ты будешь говорить правду, то тебя

возненавидят люди. Если ты будешь лгать, то тебя возненавидят боги. Но ты должен говорить

правду или лгать. Значит, тебя возненавидят люди или возненавидят боги».

2.3 ЛОГИЧЕСКИЕ СХЕМЫ

;

Синтез логической схемы заключается в соединении известных элементарных

логических схем в новую схему.

;

Анализ логической схемы состоит в установлении ее выходных значений по

значениям логических входов.

;

Логический элемент компьютера — это часть электронной логической схемы,

которая реализует элементарную логическую функцию.

Рис. 3 Базовый вентиль

Элементарная

логическая

функция

…

(

,…..,

)

Входные

сигналы

Выходной сигнал

S По приведенной схеме определить логическую функцию

Варианты ответа:

1. И

2. ИЛИ

3. НЕ

4. И-НЕ

5. ИЛИ-НЕ

S Набор {И, ИЛИ, НЕ} является функционально полным, так как на его основе можно

представить любую логическую функцию.

Для реализации элементарных схем И-НЕ, ИЛИ-НЕ используют графическое

изображение инвертора (НЕ) на выходе.

Рис. 4 Элементарный вентиль

3 АЛГОРИТМЫ

3.1 ПОНЯТИЕ АЛГОРИТМА

Понятие алгоритма относится к фундаментальным концепциям информатики,

возникло задолго до появления ЭВМ и стало одним из основных понятий математики.

 Слово «алгоритм» использовалось в математике для обозначения правил выполнения

четырех арифметических действий: сложения, вычитания, умножения и деления. В настоящее

время его применяют во многих областях человеческой деятельности, например, говорят об

алгоритме управления производственным процессом, алгоритме поиска пути в лабиринте и т. п.

 Значение слова «алгоритм» близко по смыслу к значению слов «указание» или

«предписание».

;

Алгоритм — это некоторый конечный набор операций, рассчитанных на

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

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

Алгоритм указывает последовательность действий по переработке исходных данных в

результаты.

Основные особенности алгоритма

1. Массовость. Алгоритм имеет некоторое число входных величин — аргументов,

задаваемых до начала работы. Один и тот же алгоритм применим для работы на разных

наборах исходных данных.

2. Дискретность. Алгоритм представлен в виде конечной последовательности

шагов, т. е. имеет дискретную структуру. Выполнение каждого очередного шага

начинается после завершения

предыдущего.

3. Конечность. Выполнение алгоритма заканчивается после выполнения

конечного числа шагов.

4. Детерминированность (определенность). Каждый шаг алгоритма должен

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

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

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

5. Эффективность. Алгоритм должен быть эффективным, т. е. действия

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

Элементарная

логическая

функция

…

¬F(Х

2,…..,

)

Входные

сигналы

Выходной сигнал

6. Результативность. Алгоритм должен завершаться определенными

результатами.

;

Команды — отдельные указания исполнителю на каждом шаге алгоритма.

;

Система команд исполнителя — совокупность команд, которые могут быть

выполнены конкретным исполнителем.

3.2 ЗАПИСЬ АЛГОРИТМОВ

Если алгоритм предназначен для исполнителя-человека, то для его записи может

использоваться естественный язык, лишь бы запись отражала все основные особенности

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

необходима формализация.

Средства, используемые для записи алгоритмов

1. Словесная запись алгоритма

Команды алгоритма нумеруют, чтобы можно было на них ссылаться.

Пример. Алгоритм Евклида для нахождения наибольшего общего делителя двух

натуральных чисел:

1. Если числа равны, то взять первое число в качестве ответа и закончить

исполнение алгоритма, иначе перейти к п. 2.

2. Определить большее из двух чисел.

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

4. Перейти к п. 1.

Команды такого алгоритма выполняются в естественной последовательности, если

не оговорено противного.

2. Блок-схемы алгоритмов

S Для визуализации формальной модели алгоритма используется блок-схема.

Блок-схемы представляют алгоритм в наглядной графической форме. Команды

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

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

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

естественный язык с элементами математической символики.

Наглядность быстро теряется при изображении большого алгоритма, так как схема

получается плохо обозримой

3. Псевдокоды

Псевдокод представляет собой систему обозначений и правил, предназначенную

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

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

4. Языки программирования

На практике в качестве исполнителей алгоритмов используются ЭВМ.

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

формализован. Такой язык

принято называть языком программирования, а запись алгоритма на этом языке —

программой.

;

Машинный язык — внутренний язык ЭВМ, на котором представляется и

исполняется программа.

В языках программирования высокого уровня принята символическая форма

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

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

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

арифметическим, если его значением является число. Арифметическое выражение

записывается в строку.

S При записи нельзя опускать знак умножения.

Правила выполнения операций в арифметическом выражении

Действия выполняются слева направо с соблюдением приоритета операций (по

убыванию):

1. действия в скобках;

2. вычисление функций;

3. NOT;

4. *, /, DIV, MOD, AND;

5. +, -, OR;

6. =, <>, <, >, <=, >=.

При одинаковом приоритете, выполняется операция, стоящая левее.

S Дано выражение

−

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

a. = ((a*b) – c/(a+c))/(2*b*c)

b. ((a*b) – c/(a+c))/(2*b*c)

c. (a*b) – c/(a+c)/2*b*c

d. ((ab) – c/(a+c))/(2bc)

3.3 СТРУКТУРЫ АЛГОРИТМОВ

Алгоритмы можно представлять как некоторые жесткие структуры, состоящие из

отдельных базовых элементов.

Простая команда является элементарной структурной единицей любого

алгоритма. Она обозначает один элементарный шаг переработки или отображения

информации. Переработка информации состоит в изменении значений некоторых величин,

с которыми работает алгоритм.

S Величины делятся на постоянные, значения которых остаются неизменными в

процессе исполнения алгоритма, и переменные.

С величиной связано имя, используемое для обозначения. В качестве имени

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

виде функционального блока, имеющего один вход и один выход (рис. 5).

Рис. 5 Функциональный блок простой команды

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

S Команда следования образуется из последовательности команд.

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

возможных действий в зависимости от условия: если условие соблюдено, то выполняется

действие 1, в противном случае — действие 2. Под действием понимается простая, или

составная команда. Существует команда ветвления в сокращенной форме (рис. 6-б).

Команда повторения (цикл). Алгоритм может содержать серии многократно

повторяемых команд. Составная команда цикла (команда повторения) содержит условие,

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

Команда повторения с предусловием (рис. 7-а). Исполнение команды состоит в

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

После этого снова проверяется условие. Выполнение цикла завершается, когда условие

перестает соблюдаться.

Команда повторения с постусловием (рис. 7-б). Условие проверяется после

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

соблюдено.