Всякая формула задает способ вычисления функции, если известны значения переменных.
Пример 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) = Ø - пустое множество,
Г(х5)={х4}.
А) ориентированный граф;