Определение
Отображение называется биективным (или биекцией), если оно инъективно и сюръективно.
Свойства
Композиция
инъекции и сюръекции, дающая биекцию.
Отображение является биективным тогда и только тогда, когда существует обратное отображение
такое,
что
где
обозначает
тождественное
отображение,
а
композицию
функций.
Пусть даны два отображения и
а
-
их композиция. Тогда h
биективно тогда и только тогда, когда
f
инъективно, а g
сюръективно.
В частности, композиция двух биективных отображений сама биективна. Обратное, вообще говоря, неверно.
Примеры
—
функция,
сохраняющая все элементы множества X,
биективна на этом множестве.
—
биективные
функции из
в
себя. Вообще, любой одночлен
одной переменной
нечётной
степени является биекцией.
—
биективная
функция
в
.
Но если её рассматривать как функцию
в
,
то она уже не будет биективной (у
отрицательных чисел
не будет прообразов).
не
является биективной функцией, если
считать её определённой на всём
.
11) Алгоритмы Маркова. Определение нормального алгоритма и его выполнение
В середине прошлого века выдающийся русский математик А.А. Марков ввел понятие нормального алгоритма (алгорифма) с целью уточнения понятия "алгоритм", что позволяет решать задачи по определению алгоритмически неразрешимых проблем. Позже это понятие получило название нормального алгоритма Маркова (НАМ). Язык НАМ, с одной стороны, намеренно беден, что необходимо для цели введения понятия "алгоритм". Однако, с другой стороны, идеи НАМ положены в основу большой группы языков программирования, получивших название языки логического программирования, которые являются темой данного пособия.
Для
определения НАМ вводится произвольный
алфавит - конечное непустое множество
символов, при помощи которых описывается
алгоритм и данные. В алфавит также
включается пустой символ, который мы
будем обозначать греческой буквой
.
Под словом понимается любая
последовательность непустых символов
алфавита либо пустой символ, который
обозначает пустое слово.
Всякий НАМ определяется конечным упорядоченным множеством пар слов алфавита, называемых подстановками . В паре слов подстановки левое (первое) слово непустое, а правое (второе) слово может быть пустым символом. Для наглядности левое и правое слово разделяются стрелкой. Например,
В качестве данных алгоритма берется любая непустая строка символов. Работа НАМ состоит из последовательности совершенно однотипных шагов. Шаг работы алгоритма может быть описан следующим образом:
В упорядоченной последовательности подстановок ищем самую первую подстановку, левое слово которой входит в строку данных.
В строке данных ищем самое первое (левое) вхождение левого слова найденной подстановки.
Это вхождение в строке данных заменяем на правое слово найденной подстановки (преобразование данных).
Шаг работы алгоритма повторяется до тех пор, пока
либо не возникнет ситуация, когда шаг не сможет быть выполнен из-за того, что ни одна подстановка не подходит ( левое слово любой подстановки уже не входит в строку данных ) - правило остановки ;
либо не будет установлено, что процесс подстановок не может остановиться.
В первом случае строка данных, получившаяся при остановке алгоритма, является выходной (результатом) и алгоритм применим к входным данным, а во втором случае алгоритм не применим к входным данным.
Так,
определенный выше в примере нормальный
алгоритм Маркова преобразует слово
в
слово
следующим
образом (над стрелкой преобразования
мы пишем номер применяемой подстановки,
а в преобразуемой строке подчеркиваем
левое слово применяемой подстановки
):
,
а при преобразовании слова abbc этот же алгоритм будет неограниченно работать, так как имеет место цикличное повторение данных:
Таким образом, всякий нормальный алгоритм Маркова определяет функцию, которую мы назовем нормальной (или вычислимой по Маркову), которая может быть частичной и которая в области определения входному слову ставит в соответствие выходное слово.
12 ) Матрица смежностей. Примеры.
Матрица смежности — один из способов представления графа в виде матрицы.