2.3 Понятие функции
Понятие функции является одним из основных математических понятий, и в ряде точных наук функцией называются отношения между объектами, когда изменение одного из них ведет к изменению другого.
Обычно функция (с 17 века) задается формулой, выражающей зависимую переменную через одну или несколько независимых переменных. Например, площадь круга есть функция его радиуса, и эта зависимость записывается формулой A = pr2; периметр прямоугольника является функцией его длины и ширины или P = 2(l + w). Функцию можно изобразить графически, нанося точки, координатами которых служат независимые и зависимые переменные, на координатную плоскость.
Традиционная запись y = f(x) означает, что y является функцией от x. Переменная x называется аргументом функции.
Многие конкретные функции имеют свои названия; обычно такие функции задаются формулами. К числу элементарных функций относятся многочлены.
2.4 Понятие отношения
Отношение — математическая структура, которая формально определяет свойства различных объектов и их взаимосвязи. Отношения обычно классифицируются по количеству связываемых объектов (арность) и собственным свойствам (симметричность, транзитивность и пр.). В математике примерами отношений являются равенство (=), коллинеарность, делимость и т. д. Отношение может также означать результат операции деления.
Формальное определение. n-местным (n-арным) отношением, заданным на множествах, называется подмножество прямого произведения этих множеств.
Арность.
Одноместные отношения соответствуют свойствам или атрибутам.
Двуместные отношения называют бинарными и обычно записывают инфиксной записью: x R y. Примерами множеств с введёнными на них бинарными отношениями являются графы и частично упорядоченные множества.
Трёхместные отношения называют тернарными.
Определение 5. Функцией f, действующей из множества X в множество Y (f: X Y) называется правило или закон, по которому каждому элементу xX ставится в соответствие один или несколько yY. Если каждому x ставится в соответствие один y , то функция называется однозначной.
Определение 6. Образом множества AX при отображении f:X Y называют множество
f(A): = {y Y: x A и y = f(x)}
Пример 9. y = x2; A = [0,1]; f(A) = [0,1]
Определение 7. Множество
f-1 (B): = {x X:f(x) B}
тех элементов X, образы которых содержатся в B, называется прообразом множества B.
Определение 8. Бинарным отношением называется множество упорядоченных пар (x,y). Если x связан с y отношением R, то это обозначают как xRy.
Определение 9. Отношение называется функциональным, если
(xRy1) и (xRy2) (y1 = y2).
График функции f:X Y - это подмножество X Y
Г: = {(x,y) X Y, y = f(x) }.
2.5 Графы и деревья
Многие структуры, представляющие практический интерес в информатике, могут быть представлены графами. Понятия теории графов используются в сетях, операционных системах и компиляторах. В качестве моделей графы удобно использовать в тех случаях, когда рассматривается система каких-либо объектов, между которыми существуют определенные связи, отношения, когда изучается структура системы, возможности ее функционирования. Множество самых разнообразных задач естественно формулируется в терминах графов. Так, например, могут быть сформулированы задачи составления расписаний в исследовании операций, анализа сетей в электротехнике, установления структуры молекул в органической химии, сегментации программ в программировании, анализа цепей Маркова в теории вероятностей.
Граф состоит из множества вершин и множества ребер, которые соединяют между собой вершины. С точки зрения теории графов не имеет значения, какой смысл вкладывается в вершины и ребра. Вершинами могут быть населенными пункты, а ребрами дороги, соединяющие их, или вершинами могут являться подпрограммы, соединение вершин ребрами означает взаимодействие подпрограмм. Часто имеет значение направления дуги в графе. Если ребро имеет направление, оно называется дугой, а граф с ориентированными ребрами называется орграфом.
Таким образом, граф — это совокупность объектов со связями между ними. Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра.
Граф G = (V, Е) задается парой конечных множеств V и Е. Элементы первого множества v1, v2,..., vM называются вершинами графа. Элементы второго множества el, e2, ..., eN называются ребрами. Каждое ребро определяется парой вершин.
Если ребра графа определяются упорядоченными парами вершин, то такой граф называют ориентированным (на чертеже при изображении ориентированного графа на каждом ребре ставят стрелку, указывающую его направление).
Рис.7 - Ориентированный граф с пятью вершинами и семью ребрами
Степенью вершины графа называется количество выходящих из нее ребер. Граф называется связным, если любая пара его вершин связана.
Если две вершины соединены двумя или более ребрами, то эти ребра называют параллельными (ребра е4 и е5). Если начало и конец ребра совпадают, то такое ребро называется петлей (ребро e7). Граф без петель и параллельных ребер называется простым.
Маршрут, в котором все определяемые им ребра различны, называют цепью. Цепь считают замкнутой, если ее концевые вершины совпадают. Замкнутая цепь, в которой все вершины различны, называется циклом.
Важным частным случаем графа является дерево, наиболее широко применяемое в программировании..
Существует довольно много равносильных определений деревьев, вот лишь некоторые из них.
Дерево - это связный граф без циклов.
Дерево - это связный граф, в котором при N вершинах всегда ровно N-1 ребро.
Дерево - это граф, между любыми двумя вершинами которого существует ровно один путь.
С точки зрения представления в памяти важно различать два типа деревьев: бинарные и сильноветвящиеся.
В бинарном дереве из каждой вершины выходит не более двух дуг. В сильноветвящемся дереве количество дуг может быть произвольным.
Дерево часто используют для изображения различных отношений (например, иерархических отношений).
Пример 10. Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Вене; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса ?
Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.
Теперь сразу видно, что долететь с Земли до Марса нельзя.