1610906280-c80d8404f2eaa01776b47d41b0f18e85 (824375), страница 2
Текст из файла (страница 2)
, xn i ∈ R, то говорят, что предикат R истиннен на элементах x1 , . . . , xn , и пишут R(x1 , . . . , xn ), иначе говорят,что предикат R ложен на элементах x1 , . . . , xn , и пишут ¬R(x1 , . . . , xn ).Любое подмножество R ⊆ An называется n-местным отношением (предикатом)на множестве A.Определение. Композицией отношений R1 ⊆ A × B и R2 ⊆ B × C называетсяотношение R1 ◦ R2 = {ha, ci | ∃b(ha, bi ∈ R1 и hb, ci ∈ R2 )}.Определение. Обратным отношением к отношению R ⊆ A × B называется отношение R−1 = {hb, ai | ha, bi ∈ R}.Определение. Отношение f ⊆ A × B называется функцией (отображением), еслидля любого a ∈ A существует не более одного b ∈ B такого, что ha, bi ∈ f .Для данного a ∈ A, если существует b ∈ B со свойством ha, bi ∈ f , то говорят, чтозначение f (a) определено и равно b, и пишут f (a) ↓, в противном случае говорят, чтозначение f (a) не определено, и пишут f (a) ↑.Областью определения f называется множество dom(f ) = {a ∈ A | f (a) ↓}.Областью значений f называется множество range(f ) = {f (a) | a ∈ A, f (a) ↓}.Определение.
Запись f : A → B означает, что для некоторых множеств X, Y отношение f ⊆ X × Y является функцией такой, что dom(f ) = A и range(f ) ⊆ B. Приэтом говорят, что f является функцией из A в B.Определение. Говорят, что функция f : A → B является инъективной (разнознач1−1ной), и пишут f : A −−→ B, если для любого b ∈ B существует не более одного a ∈ Aтакого, что f (a) = b.Определение. Говорят, что функция f : A → B является сюръективной (отобранажением на), и пишут f : A −→ B, если range(f ) = B.§ 2.
Алфавиты и формальные языки7Определение. Говорят, что функция f : A → B является биективной (взаимно1−1однозначной), и пишут f : A −−→ B, если f одновременно инъективна и сюръективна.наОпределение. Если f ⊆ A×B, g ⊆ B×C — функции, то их композиция f ◦g ⊆ A×Cопределяется как композиция отношений. Легко видеть, что f ◦ g тоже являетсяфункцией.1−1Определение. Если f : A −−→ B — биективная функция, то обратная функциянаf −1 определяется как обратное отношение.
Легко видеть, что f −1 является биекцией1−1вида f −1 : B −−→ A.наОпределение. Функция вида f : X → A, где X ⊆ An называется n-местной частичной функцией на A.Замечание. Заметим, что существуют только два вида 0-местных частичных функций — это либо нигде не определенная функция f = ∅, либо функция вида f ={h∅, ai} для некоторого a ∈ A. Во втором случае мы будем называть функцию константой и отождествлять ее с элементом a, т. е. f = a.§ 2.Алфавиты и формальные языкиВ большинстве случаев данные, с которыми работают алгоритмы, представляются ввиде слов некоторого языка.
Алгоритмы подобного вида можно назвать словарными.Например, все алгоритмы из следующей главы безусловно являются словарными.Более того, описание самих алгоритмов, как правило, осуществляется с помощьюспециального текста, который обычно называют программой.Понятия слова, языка и текста имеют очень широкий спектр значений, выходящий за рамки математической науки. Мы будем работать только с формальнымиязыками, т.
е. с языками, которые поддаются формальному описанию в рамках теории множеств и которые можно изучать, используя строгие математические методы.Определение. Алфавитом будем называть любое непустое конечное множествоA = {a0 , . . . , an }. Элементы алфавита принято называть буквами, или символами.Определение. Словом длины n в алфавите A мы будем называть любой кортежha1 , a2 , . . . , an i длины n, где a1 , . . .
, an — буквы алфавита A. Слова обычно записывают в виде a1 a2 . . . an . Пустое слово ∅ не содержит ни одной буквы, имеет длину 0и обозначается через Λ.Замечание. В дальнейшем запись слова в виде a1 a2 . . . an подразумевает, в частности, что при n = 0 это слово пусто. Это же соглашение распространяется на конечныекортежи и конечные множества, т. е. ha1 , . . . , an i = {a1 , . .
. , an } = ∅ при n = 0.Определение. Множество всех слов в алфавите A, включая пустое слово, обозначается через A∗ . Множество всех непустых слов в алфавите A обозначается черезA+ , т. е. A+ = A∗ \ {Λ}.Определение. Длина слова w ∈ A∗ обозначается через |w|.8Глава I. Предварительные сведенияОпределение. Слово u называется подсловом слова v, если существуют слова w1и w2 такие, что v = w1 uw2 , при этом вхождением подслова u в слово v назовемупорядоченную тройку hw1 , u, w2 i. Отметим, что одно и то же слово u может иметьнесколько различных вхождений в слово v.Определение. Слово u называется префиксом слова v, если v = uw для некоторогослова w. Слово u называется суффиксом слова v, если v = wu для некоторого w.Определение.
Введем следующие операции над словами в алфавите A:(а) Конкатенацией слов u и v называется слово uv, полученное приписыванием кслову u слова v справа.(б) Степень слова u определяется индукцией по n ∈ ω следующим образом: u0 = Λ,un+1 = un u.(в) Обращением слова u = a1 a2 . . . an , где a1 , a2 , . . . , an — буквы алфавита A, называется слово uR = an .
. . a2 a1 .Пример. Конкатенацией слов kein и mehrheit является слово keinmehrheit. Еслитеперь взять конкатенацию тех же слов, но в другом порядке, то получится словоmehrheitkein. Слово ei является подсловом слова keinmehrheit, причем оно имеетдва вхождения: первое вхождение начинается со 2-го символа слова, а второе — с10-го символа. Обращением слова mehrheit будет слово tiehrhem. Степенями словаkein являются слова Λ, kein, keinkein, keinkeinkein и т. д. При этом каждое словоиз данной последовательности является префиксом всех последующих слов.Определение. Любое подмножество L ⊆ A∗ называется формальным языком надалфавитом A.Определение.
Введем следующие операции над языками в алфавите A:(а) Объединение L1 ∪ L2 и пересечение L1 ∩ L2 языков L1 и L2 определяются какобычные теоретико-множественные объединение и пересечение.(б) Дополнением языка L называется язык L = A∗ \ L.(в) Конкатенацией языков L1 и L2 называется язык L1 L2 = {uv | u ∈ L1 , v ∈ L2 }.(г) Степень языка L определяется индукцией по n ∈ ω следующим образом: L0 ={Λ}, Ln+1 = Ln L.S n(д) Звездочкой Клини от языка L называется язык L∗ =L . Другими словами,n∈ωL∗ = {w | w = w1 w2 .
. . wn для некоторых n ∈ ω и w1 , w2 , . . . , wn ∈ L}.В частности, всегда имеет место Λ ∈ L∗ (при n = 0).Замечание. Заметим, что определение звездочки Клини согласуется с введенымвыше обозначением A∗ . Звездочка Клини от алфавита — это и есть множество всехслов в данном алфавите.Пример. С помощью введенных операций можно определять формально те языки,которые изначально имеют неформальное описание.Например, язык всех слов в алфавите A = {a, b}, имеющих хотя бы одно вхождение буквы a, совпадает с языком {b}∗ {a}{a, b}∗ .
Действительно, в любом таком словеможно выделить первое вхождение буквы a, т. е. представить в виде bn aw, где n ∈ ω,w — некоторое слово в алфавите A. С другой стороны, любое слово вида bn aw лежитв языке {b}∗ {a}{a, b}∗ .§ 3. Интуитивные свойства алгоритмов9Другой пример — это язык всех слов четной длины в том же алфавите, которыйможно представить как {aa, ab, ba, bb}∗ . Действительно, слово w имеет четную длинутогда и только тогда, когда его можно представить в виде w = w1 . . . wn для некоторого n ∈ ω и некоторых слов wi , каждое из которых имеет длину 2, т.
е. каждоеwi ∈ {aa, ab, ba, bb}.Отсюда следует, что язык всех слов нечетной длины можно получить как дополнение предыдущего языка, т. е. {a, b}∗ \ {aa, ab, ba, bb}∗ , а язык всех слов четной длины, содержащих букву a, можно получить, используя операцию пересечения({b}∗ {a}{a, b}∗ ) ∩ {aa, ab, ba, bb}∗ .Язык всех слов четной длины, содержащих букву a, можно получить и другимспособом, а именно как язык {bb}∗ {aa, ab, ba}{aa, ab, ba, bb}∗ .§ 3.Интуитивные свойства алгоритмовF11 12 13 14 1518 17 161069¾ 22 218?195120607432Понятие алгоритма известно в математике сдревних времен. Однако до определенного времени алгоритмы возникали лишь при описании алгоритмических решений вполне конкретных математичеких задач. При этом автор решения вявном виде предъявлял описание своего алгоритма и доказывал, что его алгоритм приводит кверному результату.
Этого было достаточно, чтобы по достоинству оценить новый математический результат. Но позднее, ближе к эпохе современности, в различных областях математики(чаще всего в алгебре) стали возникать задачи,относительно которых предполагалось, что они не имеют алгоритмического решения.Чтобы формально доказывать такие гипотезы, естественно, потребовалось более общее, формальное описание понятия алгоритма.Прежде чем вводить формальные определения различных алгоритмических систем, мы попытаемся выявить с интуитивной точки зрения те характерные черты,которыми обладают алгоритмы.
В дальнейшем мы убедимся в том, что все существующие подходы к формализации понятия алгоритма удовлетворяют этим свойствам.Это наблюдение будет служить подтверждением того, что данные подходы являютсяестественными и адекватными.Чтобы наши интуитивные рассуждения были более наглядными, рассмотрим следующую несложную задачу, имеющую алгоритмическое решение.Пример. На плоскости задан прямоугольник, разбитый на одинаковые клетки состороной единичной длины. Некоторые клетки заштрихованы — это стены, остальные клетки — это коридоры.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
