Порядок подстановки задается формулой.

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

Пример 2.4.

Построим таблицу значений функции

Вычисление функции f(x1 х2, х3)

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

Графы и деревья

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

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

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

Графом G (в широком понимании) называется любая пара (X, А), где Х= {х1 х2,…} — множество элементов любой природы, а А = {а1, а2, …} — семейство пар элементов из X, причем допускаются пары вида (хi х,) и одинаковые пары. Если пары в X рассматриваются как неупорядоченные, то граф называется неориентированным, если как упорядоченные, то граф называется ориентированным {орграфом).

Элементы множества X называются вершинами графа, а пары из А — его ребрами; в орграфе они называются ориентированными ребрами или дугами.

Таким образом, граф G задается множеством точек или вершин х1 х2,…,хn (которое обозначается через X) и множеством линий или ребер а1, а2, …, ат (которое обозначается символом А), соединяющих между собой все или часть этих точек. Таким образом, граф G полностью задается (и обозначается) парой (Х.A).

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

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

Другое, употребляемое чаще описание ориентированного графа G состоит в задании множества вершин X и соответствия Г, которое показывает, как между собой связаны вершины. Соответствие Г называется отображением множества X в X, а граф в этом случае обозначается парой G = {X, Г).

Для графа на рисунке (а) имеем Г(х1) = {х2, x5}, т. е. вершины x2и x5 являются конечными вершинами дуг, у которых начальной вершиной является x1

Г(х2)={х1,х3},

Г(х3) ={х1},

Г(х4) = O — пустое множество,

Г(х5)={х4}.

А) ориентированный граф;

Статьи к прочтению:

Перестановки. Тема

Похожие статьи: