Викиконспекты - Вклад участника [ru]

Устранение левой рекурсии

2022-06-03T16:58:09Z

77.234.193.84: Отмена правки 82337, сделанной 162.247.74.206 (обсуждение)

__TOC__
{{Определение
|definition=Говорят, что [[Контекстно-свободные грамматики, вывод, лево- и правосторонний вывод, дерево разбора|контекстно-свободная (КС) грамматика]] <tex>\Gamma</tex> содержит '''непосредственную левую рекурсию''' (англ. ''direct left recursion''), если она содержит правило вида <tex>A \to A\alpha</tex>.
}}
{{Определение
|definition=Говорят, что КС-грамматика <tex>\Gamma</tex> содержит '''левую рекурсию''' (англ. ''left recursion''), если в ней существует вывод вида <tex>A \Rightarrow^* A\alpha</tex>.
}}

[[Методы трансляции#Нисходящий разбор|Методы нисходящего разбора]] не в состоянии работать с леворекурсивными грамматиками. Проблема в том, что продукция вида <tex>A \Rightarrow^* A\alpha</tex> может применяться бесконечно долго, так и не выработав некий терминальный символ, который можно было бы сравнить со строкой. Поэтому требуется преобразование грамматики, которое бы устранило левую рекурсию.

==Устранение непосредственной левой рекурсии==
Опишем процедуру, устраняющую все правила вида <tex>A \to A\alpha</tex>, для фиксированного нетерминала <tex>A</tex>.

<ol>
<li>Запишем все правила вывода из <tex>A</tex> в виде:
<tex>A \to A\alpha_1 \mid \ldots \mid A\alpha_n \mid \beta_1 \mid \ldots \mid \beta_m </tex>, где
<ul>
<li> <tex>\alpha</tex> {{---}} непустая последовательность терминалов и нетерминалов (<tex>\alpha \nrightarrow \varepsilon </tex>);</li>
<li> <tex>\beta</tex> {{---}} непустая последовательность терминалов и нетерминалов, не начинающаяся с <tex>A</tex>.</li>
</ul>
<li>Заменим правила вывода из <tex>A</tex> на <tex>A \to\beta_1A^\prime \mid \ldots\ \mid \beta_mA^\prime \mid \beta_1 \mid \ldots \mid \beta_m</tex>.</li>

<li>Создадим новый нетерминал <tex>{A^\prime} \to \alpha_1{A^\prime} \mid \ldots \mid \alpha_n{A^\prime} \mid \alpha_1 \mid \ldots \mid \alpha_n</tex>. </li>
</li>
</ol>

Изначально нетерминал <tex>A</tex> порождает строки вида <tex>\beta\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}</tex>. В новой грамматике нетерминал <tex>A</tex> порождает <tex>\beta{A^\prime}</tex>, а <tex>A^\prime</tex> порождает строки вида <tex>\alpha_{i0}\alpha_{i1} \ldots \alpha_{ik}</tex>. Из этого очевидно, что изначальная грамматика эквивалентна новой.

===Пример===
<tex>A \to S\alpha \mid A\alpha</tex>

<tex>S \to A\beta</tex>

Есть непосредственная левая рекурсия <tex>A \to A\alpha</tex>. Добавим нетерминал <tex>A^\prime</tex> и добавим правила <tex>A \to S\alpha{A^{\prime}}</tex>, <tex> A^{\prime} \to \alpha{A^{\prime}} </tex>.

Новая грамматика:

<tex>A \to S\alpha{A^{\prime}} \mid S\alpha</tex>

<tex>A^{\prime} \to \alpha{A^{\prime} \mid \alpha}</tex>

<tex>S \to A\beta</tex>

В новой грамматике нет непосредственной левой рекурсии, но нетерминал <tex>A</tex> леворекурсивен, так как есть <tex> A \Rightarrow S\alpha{A^{\prime}} \Rightarrow A\beta\alpha{A^{\prime}} </tex>

==Алгоритм устранения произвольной левой рекурсии==
Воспользуемся [[Удаление_eps-правил_из_грамматики | алгоритмом удаления <tex> \varepsilon </tex>-правил]]. Получим грамматику без <tex> \varepsilon </tex>-правил для языка <tex>L(\Gamma) \setminus \lbrace \varepsilon \rbrace</tex>.

Упорядочим нетерминалы, например по возрастанию индексов, и будем добиваться того, чтобы не было правил вида <tex>A_i \to A_j\alpha</tex>, где <tex>j \leqslant i</tex>.
Если данное условие выполняется для всех <tex>A_i</tex>, то в грамматике нет <tex>A_i \Rightarrow^* A_i</tex>, а значит не будет левой рекурсии.

Пусть <tex>N = \lbrace A_1, A_2, \ldots , A_n \rbrace</tex> {{---}} упорядоченное множество всех нетерминалов.

'''for''' <tex>A_i \in N</tex>
'''for''' <tex>A_j \in \{ N \mid 1 \leqslant j < i \}</tex>
'''for''' <tex>p \in \{ P \mid A_i \to A_j\gamma \}</tex>
удалить продукцию <tex>p</tex>
'''for''' <tex>Q \to x_i \in \{A_j \to \delta_1 \mid \ldots \mid \delta_k\}</tex>
добавить правило <tex>A_i \to x_i\gamma</tex>
устранить непосредственную левую рекурсию для <tex>A_i</tex>

Если <tex>\varepsilon</tex> присутствовал в языке исходной грамматики, добавим новый начальный символ <tex>S'</tex> и правила <tex>S' \to S \, \mid \, \varepsilon </tex>.

После <tex>i</tex> итерации внешнего цикла в любой продукции внешнего цикла в любой продукции вида <tex>A_k \to A_l\alpha, k < i</tex>, должно быть <tex>l > k</tex>. В результате при следующей итерации внутреннего цикла растет нижний предел <tex>m</tex> всех продукций вида <tex>A_i \to A_m\alpha</tex> до тех пор, пока не будет достигнуто <tex>i \leqslant m </tex>.

После <tex>i</tex> итерации внешнего цикла в грамматике будут только правила вида <tex>A_i \to A_j\alpha</tex>, где <tex>j > i</tex>.
Можно заметить, что неравенство становится строгим только после применения алгоритма устранения непосредственной левой рекурсии. При этом добавляются новые нетерминалы. Пусть <tex>{A^\prime}_i </tex> новый нетерминал. Можно заметить, что нет правила вида <tex>\ldots \to {A^\prime}_i</tex>, где <tex>{A^\prime}_i</tex> самый левый нетерминал, а значит новые нетерминалы можно не рассматривать во внешнем цикле. Для строгого поддержания инвариантов цикла можно считать, что созданный на <tex>i</tex> итерации в процессе устранения непосредственной левой рекурсии нетерминал имеет номер <tex>A_{-i}</tex> (т.е. имеет номер, меньший всех имеющихся на данный момент нетерминалов).

На <tex>i</tex> итерации внешнего цикла все правила вида <tex>A_i \to A_j \gamma</tex> где <tex> j < i </tex> заменяются на <tex>A_i \to \delta_1\gamma \mid \ldots \mid \delta_k\gamma</tex> где <tex>A_j \to \delta_1 \mid \ldots \mid \delta_k</tex>. Очевидно, что одна итерация алгоритма не меняет язык, а значит язык получившийся в итоге грамматики совпадает с исходным.

===Оценка времени работы===
Пусть <tex>a_i</tex> количество правил для нетерминала <tex>A_i</tex>.
Тогда <tex>i</tex> итерация внешнего цикла будет выполняться за <tex>O\left(\sum\limits_{A_i \to A_j, j < i} a_j\right) + O(a_i)</tex>, что меньше чем <tex>O\left(\sum\limits_{i=1}^n a_j\right)</tex>, значит асимптотика алгоритма <tex>O\left(n\sum\limits_{i=1}^n a_j\right)</tex>.

===Худший случай===
Проблема этого алгоритма в том, что в зависимости от порядка нетерминалов в множестве размер грамматки может получиться экспоненциальным.

Пример грамматики для которой имеет значение порядок нетерминалов

<tex>A_1 \to 0 \mid 1</tex>

<tex>A_{i+1} \to {A_i}0 \mid {A_i}1 </tex> для <tex>1 \leqslant i < n</tex>

Упорядочим множество нетерминалов по возрастанию индексов. Легко заметить, что правила для <tex>A_i</tex> будут представлять из себя все двоичные вектора длины <tex>i</tex>, а значит размер грамматики будет экспоненциальным.
===Порядок выбора нетерминалов===
{{Определение
|definition=Говорят, что нетерминал <tex>X</tex> {{---}} '''прямой левый вывод''' (англ. ''direct left corner'') из <tex>A</tex>, если существует правило вида <tex>A \to X\alpha</tex>.
}}

{{Определение
|definition='''Левый вывод''' (англ. ''left corner'') {{---}} [[Транзитивное_отношение|транзитивное]], [[Рефлексивное_отношение|рефлексивное]] замыкание отношения «быть прямым левым выводом».
}}

Во внутреннем цикле алгоритма для всех нетерминалов <tex>A_i</tex> и <tex>A_j</tex>, таких что <tex>j < i</tex> и <tex>A_j</tex> {{---}} прямой левый вывод из <tex>A_i</tex> заменяем все прямые левые выводы <tex>A_j</tex> из <tex>A_i</tex> на все выводы из <tex>A_j</tex>.

Это действие удаляет левую рекурсию только если <tex>A_i</tex> {{---}} леворекурсивный нетерминал и <tex>A_j</tex> содержится в выводе <tex>A_i</tex> (то есть <tex>A_i</tex> {{---}} левый вывод из <tex>A_j</tex>,в то время как <tex>A_j</tex> {{---}} левый вывод из <tex>A_i</tex>).

Перестанем добавлять бесполезные выводы, которые не участвуют в удалении левой рекурсии, упорядочив нетерминалы так: если <tex>j < i</tex> и <tex>A_j</tex> {{---}} прямой левый вывод из <tex>A_i</tex>, то <tex>A_i</tex> {{---}} левый вывод из <tex>A_j</tex>.
Упорядочим их по уменьшению количества различных прямых левых выводов из них.

Так как отношение «быть левым выводом» транзитивно,то если <tex>C</tex> {{---}} прямой левый вывод из <tex>B</tex>, то каждый левый вывод из С также будет левым выводом из <tex>B</tex>. А так как отношение «быть левым выводом» рефлексивно, <tex>B</tex> явлеяется своим левым выводом, а значит если <tex>C</tex> {{---}} прямой левый вывод из <tex>B</tex> {{---}} он должен следовать за <tex>B</tex> в упорядоченном множестве, если только <tex>B</tex> не является левым выводом из <tex>C</tex>.

==Пример==
Дана грамматика:

<tex>A \to S\alpha </tex>

<tex>S \to S\beta \mid A\gamma \mid \beta</tex>

Среди правил <tex>A</tex> непосредственной рекурсии нет, поэтому во время первой итерации внешнего цикла ничего не происходит.
Во время второй итерации внешнего цикла правило <tex> S \to A\gamma </tex> переходит в <tex> S \to S\alpha\gamma </tex>.

Грамматика имеет вид

<tex>A \to S\alpha </tex>

<tex>S \to{S}{\beta} \mid {S}{\alpha}{\gamma} </tex>

Устраняем левую рекурсию для <tex>S </tex>

<tex> S \to\beta{S_1} \mid \beta</tex>

<tex> {S_1} \to\beta{S_1} \mid \alpha\gamma{S_1} \mid {\beta} \mid {\alpha}{\gamma} </tex>

== См. также ==
* [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|Контекстно-свободные грамматики]]
* [[Нормальная_форма_Хомского|Нормальная форма Хомского]]
* [[Удаление_eps-правил_из_грамматики | Удаления <tex> \varepsilon </tex>-правил из грамматики]]

== Источники информации ==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
* ''Robert C. Moore'' — [https://aclanthology.org/A00-2033.pdf Removing Left Recursion from Context-Free Grammars ]

[[Категория: Теория формальных языков]]
[[Категория: Контекстно-свободные грамматики]]
[[Категория: Нормальные формы КС-грамматик]]

Заглавная страница

2022-06-03T16:57:00Z

77.234.193.84: Отмена правки 82336, сделанной 162.247.74.206 (обсуждение)

Добро пожаловать на сайт [[Викиконспекты:Описание|вики-конспектов]]!

= Проверяемые конспекты =

== [[Дискретная математика | Дискретная математика]]==
* [[Дискретная математика#Отношения| Отношения]]
* [[Дискретная математика#Булевы функции| Булевы функции]]
* [[Дискретная математика#Схемы из функциональных элементов| Схемы из функциональных элементов]]
* [[Дискретная математика#Представление информации| Представление информации]]
* [[Дискретная математика#Алгоритмы сжатия| Алгоритмы сжатия данных]]
* [[Дискретная математика#Комбинаторика| Комбинаторика]]
* [[Дискретная математика#Производящая функция|Производящая функция]]

==[[Теория вероятностей | Теория вероятностей]]==

* [[Теория вероятностей # Теория вероятностей| Базовые определения и формулы расчета вероятности]]
* [[Теория вероятностей #Марковские цепи| Марковские цепи]]

==[[Теория формальных языков|Теория формальных языков]]==
* [[Теория формальных языков#Автоматы и регулярные языки|Автоматы и регулярные языки]]
* [[Теория формальных языков#Контекстно-свободные грамматики|Контекстно-свободные грамматики]]

== [[Теория матроидов | Теория матроидов]]==

* [[Теория матроидов#Основные факты теории матроидов | Основные факты]]
* [[Теория матроидов#Пересечение матроидов | Пересечение матроидов]]
* [[Теория матроидов#Объединение матроидов | Объединение матроидов]]

== [[Теория расписаний | Теория расписаний]]==

*[[Теория расписаний#Задачи с одним станком | Задачи с одним станком]]
*[[Теория расписаний#Специальные случаи задач для двух станков | Специальные случаи задач для двух станков]]
*[[Теория расписаний#Задачи для произвольного числа станков | Задачи для произвольного числа станков]]

== [[Теория вычислимости | Теория вычислимости]]==
* [[Теория вычислимости#Разрешимые и перечислимые языки | Разрешимые и перечислимые языки]]
* [[Теория вычислимости#Вычислительные формализмы | Вычислительные формализмы]]
* [[Теория вычислимости#Примеры неразрешимых задач | Примеры неразрешимых задач]]

==[[Теория сложности | Теория сложности]]==
* [[Теория сложности#Детерминированные и недетерминированные вычисления, сложность по времени и по памяти | Детерминированные и недетерминированные вычисления, сложность по времени и по памяти]]
* [[Теория сложности#Схемная сложность | Схемная сложность]]
* [[Теория сложности#Вероятностные сложностные классы | Вероятностные сложностные классы]]

== [[Алгоритмы и структуры данных | Алгоритмы и структуры данных]]==
* [[Алгоритмы и структуры данных#Амортизационный анализ | Амортизационный анализ]]
* [[Алгоритмы и структуры данных#Персистентные структуры данных | Персистентные структуры данных]]
* [[Алгоритмы и структуры данных#Приоритетные очереди | Приоритетные очереди]]
* [[Алгоритмы и структуры данных#Система непересекающихся множеств | Система непересекающихся множеств]]
* [[Алгоритмы и структуры данных#Поисковые структуры данных | Поисковые структуры данных]]
* [[Алгоритмы и структуры данных#Запросы на отрезках | Запросы на отрезках]]
* [[Алгоритмы и структуры данных#Дерево Фенвика | Дерево Фенвика]]
* [[Алгоритмы и структуры данных#Задача о наименьшем общем предке | Задача о наименьшем общем предке]]
* [[Алгоритмы и структуры данных#Хеширование | Хеширование]]
* [[Алгоритмы и структуры данных#Сортировки | Сортировки]]
* [[Алгоритмы и структуры данных#Сортирующие сети | Сортирующие сети]]
* [[Алгоритмы и структуры данных#Алгоритмы поиска | Алгоритмы поиска]]
* [[Алгоритмы и структуры данных#Динамическое программирование | Динамическое программирование]]
* [[Алгоритмы и структуры данных#Алгоритмы во внешней памяти | Алгоритмы во внешней памяти]]

== [[Теория графов | Теория графов]]==
* [[Теория графов#Основные определения теории графов | Основные определения теории графов]]
* [[Теория графов#Связность в графах | Связность в графах]]
* [[Теория графов#Остовные деревья | Остовные деревья]]
* [[Теория графов#Обходы графов | Обходы графов]]
* [[Теория графов# Укладки графов | Укладки графов]]
* [[Теория графов#Раскраски графов | Раскраски графов]]
* [[Теория графов#Обход в глубину | Обход в глубину]]
* [[Теория графов#Кратчайшие пути в графах | Кратчайшие пути в графах]]
* [[Теория графов#Задача о паросочетании | Задача о паросочетании]]
* [[Теория графов#Задача о максимальном потоке | Задача о максимальном потоке]]
* [[Теория графов#Задача о потоке минимальной стоимости | Задача о потоке минимальной стоимости]]
* [[Теория графов#Cлучайные графы | Cлучайные графы]]

== [[Алгоритмы на строках | Алгоритмы на строках]]==
* [[Алгоритмы на строках# Поиск подстроки в строке | Поиск подстроки в строке]]
* [[Алгоритмы на строках#Суффиксное дерево |Суффиксное дерево]]
* [[Алгоритмы на строках#Суффиксный массив | Суффиксный массив]]

== [[Методы трансляции | Методы трансляции]] ==
* [[Методы трансляции#Нисходящий разбор|Нисходящий разбор]]
* [[Методы трансляции#Восходящий разбор | Восходящий разбор]]

== [[Вычислительная геометрия|Вычислительная геометрия ]]==
* [[Вычислительная геометрия#Основание вычислительной геометрии|Основание вычислительной геометрии]]
* [[Вычислительная геометрия#Вычисление геометрических предикатов|Вычисление геометрических предикатов]]
* [[Вычислительная геометрия#Пересечение отрезков|Пересечение отрезков]]
* [[Вычислительная геометрия#Выпуклые оболочки|Выпуклые оболочки]]
* [[Вычислительная геометрия#Поиск|Поиск]]
* [[Вычислительная геометрия#Триангуляция|Триангуляция]]
* [[Вычислительная геометрия#ППЛГ и РСДС|ППЛГ и РСДС]]
* [[Вычислительная геометрия#Алгоритмы локализации|Алгоритмы локализации]]
* [[Вычислительная геометрия#Триангуляция Делоне и диаграмма Вороного|Триангуляция Делоне и диаграмма Вороного]]
* [[Вычислительная геометрия#Планирование движения (Motion planning)|Планирование движения (Motion planning)]]

== [[Язык программирования Java|Язык программирования Java]]==
*[[Основная информация о языкe]]
*[[Программирование по контракту]]
*[[Обработка ошибок и исключения]]
*[[Generics]]
*[[Перечисления]]

== [[Параллельное программирование|Параллельное программирование]]==
*[[Очередь Майкла и Скотта]]

== [[Машинное обучение|Машинное обучение]]==

*[[Модель алгоритма и ее выбор]]
*[[Переобучение]]
*[[Кросс-валидация]]
*[[Выброс]]
*[[Машинное обучение|Другие темы]]

= Непроверяемые конспекты =

*[[Алгебра и геометрия 1 курс | Алгебра и геометрия — 1, 2 семестр]]
*[[Математический анализ 1 курс | Математический анализ — 1, 2 семестр]]
*[[Математический анализ 2 курс | Математический анализ — 3, 4 семестр]]
*[[Математическая логика|Математическая логика — 3 семестр]]
*[[Участник:Qwerty787788/плюсы3сем | С++ — 2, 3 семестр]]
*[[Дифференциальные уравнения | Дифференциальные уравнения — 3 семестр]]
*[[Assembler|Assembler — 4 семестр]]
*[[Алгоритмы алгебры и теории чисел|Алгоритмы алгебры и теории чисел — 4 семестр]]
*[[Функциональный_анализ_3_курс | Функциональный анализ — 5, 6 семестр]]
*[[Параллельное программирование|Параллельное программирование — 6 семестр]]
*[[Базы данных|Базы данных — 7 семестр]]
*[[Компьютерные сети|Компьютерные сети — 7, 8 семестр]]
*[[Эволюционные алгоритмы|Эволюционные алгоритмы — 10 семестр]]

[[Категория:Всё]]

Предел отображения в метрическом пространстве

2021-10-24T14:43:17Z

77.234.193.84: /* Окрестность точки в метрическом пространстве */

{{В разработке}}

== Подмножества метрического пространства ==

Если <tex> (X, \rho) </tex> {{---}} [[метрическое пространство]], то <tex>\forall\ Y \subset X : (Y, \rho)</tex>, очевидно, тоже метрическое пространство.

== Окрестность точки в метрическом пространстве ==

{{Определение
|definition =
Пусть <tex>x \in A</tex>. Тогда <tex>A</tex> {{---}} '''окрестность''' точки <tex>x</tex>, если существует открытый шар <tex>V: x \in V \subset A </tex>. При этом <tex>A \backslash \{x\}</tex> называется '''проколотой окрестностью''' точки <tex>x</tex>.
}}

Окрестность точки <tex>x</tex> обозначается как <tex>O(x)</tex>, ее проколотая окрестность {{---}} <tex>\dot{O}(x)</tex>.

=== Примеры ===

* Любой открытый шар <tex> V_r(x) </tex> является окрестностью точки <tex>x</tex>.

* Числовая прямая {{---}} окрестность любого числа.

== Предельная точка ==

{{Определение
|definition =
Рассмотрим <tex>A \subset X</tex>. Тогда <tex>b \in X</tex> {{---}} '''предельная точка''' для <tex>A</tex>, если в любой окрестности <tex>O(b)</tex> содержится бесконечное число точек, принадлежащих <tex>A</tex>.
}}

=== Пример(ы) ===

#<tex> X = \mathbb R, A = (0; 1);\ 0 \notin A</tex>, <tex>0</tex> {{---}} предельная точка(как и <tex>1</tex>, например).

== Предел отображения ==
{{Определение
|definition =
Пусть даны два метрических пространства <tex> (X,\rho) </tex> и <tex> (Y, \tilde \rho) </tex>, <tex> A \subset X</tex> и <tex>\ a </tex> {{---}} предельная точка <tex>A</tex>. Пусть <tex> f: A \rightarrow Y </tex>.
* Тогда <tex> b = \lim\limits_{x \rightarrow a} f(x), b \in Y</tex> , если <tex>\forall \varepsilon > 0 \, \exists \delta > 0: 0 < \rho(x, a) < \delta \Rightarrow \tilde \rho(f(x), b) < \varepsilon </tex>.
}}

Так как <tex>a</tex> {{---}} предельная точка <tex>A</tex>, то у нас есть гарантии, что <tex>0 < \rho(x, a) < \delta</tex> выполнимо для бесконечного числа точек <tex> x \in A</tex>. Отметим: если <tex>a \in A</tex>, то <tex>f(a)</tex> нас не интересует.

=== Пример(ы) ===
<tex>X = Y = \mathbb R, f: (a - 1; a + 1) \rightarrow \mathbb R, a</tex> {{---}} предельная точка.
Тогда <tex> \lim\limits_{x \rightarrow a} f(x) = b\ \Leftrightarrow\ \forall \varepsilon > 0\ \exists \delta > 0 : 0 < |x - a| < \delta \Rightarrow |f(x) - b| < \varepsilon </tex>.

{{Определение
|definition=
Если при <tex>a \in A выполняется \lim\limits_{x \rightarrow a}f(x) = f(a)</tex>, тогда говорят, что отображение <tex>f</tex> '''непрерывно''' в точке <tex>a</tex>.
}}

== Предел сложного отображения ==
Если <tex>f</tex> имеет предел, то в ситуации общих МП:

{{Теорема
|about=
предел сложного отображения
|statement=
Пусть даны 3 МП: <tex> X, Y, Z</tex>, у каждого своя метрика; <tex> A \subset X,\ B \subset Y</tex>.

Пусть также заданы отображения

<tex>f: A \rightarrow B, \qquad g: B \rightarrow Z </tex>

<tex> (f(x) \ne b \forall x \in A) </tex>

<tex>a</tex> {{---}} предельная точка <tex>A</tex>, <tex>b</tex> {{---}} предельная точка B, при этом:

<tex> b = \lim\limits_{x \rightarrow a} f(x) \qquad d = \lim\limits_{y \rightarrow b} g(y) </tex>

Пусть <tex>z(x) = g(f(x)) </tex>

Тогда утверждается, что <tex> \lim\limits_{x \rightarrow a} z(x) = d </tex>. Если вы дочитали условие до этого места, возьмите с полки пирожок. _о_
|proof=
: <tex>\forall \varepsilon > 0 \, \exists \delta_1 > 0 : 0 < \bar \rho (y, b) < \delta_1 \Rightarrow \bar{\bar \rho}(g(y), d) < \varepsilon \\
\forall \delta_1 > 0 \, \exists \delta > 0 : 0 < \rho (x, a) < \delta \Rightarrow \bar \rho (f(x), b) < \delta_1 </tex>
:<tex>f(x) \ne b \Rightarrow 0 < \bar \rho (f(x), b) < \delta_1 </tex>, а тогда <tex>y = f(x) </tex>
:<tex>\forall \varepsilon > 0 \, \exists \delta > 0: 0 < \rho (x, a) < \delta \Rightarrow \bar{\bar \rho} (g(y), d) < \varepsilon \Rightarrow \lim\limits_{x \rightarrow a} g(f(x)) = d </tex>( у сложной функции предел совпадает с пределом внешней фукнции)
}}

Итак, сложная фукнция от двух непрерывных {{---}} непрерывна.

== Некоторые непрерывные отображения ==
{{Теорема
|statement=
Пусть задана <tex> f: X \rightarrow R_+, f(x) = \rho(x, a) </tex>
Проверим, что <tex> \forall x_0\ f(x_0) </tex> - непрерывное отображение.
|proof=
Воспользуемся свойством метрического пространства - неравенством треугольника:

<tex> \rho(x_2, a) \le \rho(x_1, a) + \rho(x_2, x_1) \ \Leftrightarrow\ \rho(x_2, a) - \rho(x_1, a) \le \rho(x_2, x_1)</tex>

<tex> \rho(x_1, a) \le \rho(x_2, a) + \rho(x_1, x_2) \ \Leftrightarrow\ \rho(x_1, a) - \rho(x_2, a) \le \rho(x_1, x_2)</tex>

Отсюда, <tex> |\rho(x_2, a) - \rho(x_1, a)| \le \rho(x_2, x_1) </tex>.

<tex> f(x_2) = \rho(x_2, a), f(x_1) = \rho(x_1, a)</tex>, значит, <tex> |f(x_2) - f(x_1)| \le \rho(x_2, x_1) </tex>

Полагаем в этом неравенстве <tex> x_1 = x, x_2 = x_0 </tex> и обращаемся к определению непрерывного отображения:

<tex> \forall \varepsilon > 0\ \exists \delta: 0 < \rho(x, x_0) < \delta \Rightarrow |f(x_0) - f(x)| < \varepsilon</tex>
Из неравенства напрямую следует, что условие выполняется при <tex> \delta = \varepsilon</tex>, поэтому <tex> \forall x_0 \Rightarrow f(x_0) </tex> непрерывна.
}}

{{Определение
|definition=
<tex>\rho(x, A) = \inf\limits_{a \in A} \rho(x, a) </tex> - расстояние от x до A.
}}

{{Теорема
|statement=
<tex> \forall x_0\ f(x_0) = \rho(x_0, A) </tex> - непрерывна.
|proof=
<tex> f(x_1) \le \rho(x_1, a) \le \rho(x_2, a) + \rho(x_2, x_1) </tex>

По определению нижней грани, <tex>\forall \varepsilon > 0\ \exists a^* \in A: \rho(x, a^*) < \rho(x, A) + \varepsilon</tex>, значит, <tex>f(x_1) \le \rho(x_2, A) + \varepsilon + \rho(x_2, x_1) </tex>.

Делая предельный переход при <tex> \varepsilon \rightarrow 0</tex>, получаем неравенство
<tex> f(x_1) \le \rho(x_2, A) + \rho(x_2, x_1) </tex>.

Аналогично, <tex> f(x_2) \le \rho(x_1, A) + \rho(x_1, x_2) </tex>.

Дальнейшие рассуждения аналогичны предыдущему доказательству непрерывности.

}}

{{Теорема
|statement=
Пусть F - замкнуто. Тогда <tex>x \in F \Leftrightarrow \rho(x, F) = 0 </tex>
|proof=
<tex> \Rightarrow </tex>:
: <tex> \rho(x, F) = \inf\limits_{a \in F} \rho(x, a) </tex>.
: Но <tex> x \in F</tex>, а <tex> \rho(x, x) = 0 </tex>, по определению <tex> \rho >= 0 </tex>, значит, <tex> \rho(x, F) = 0, </tex>
<tex> \Leftarrow </tex>:
: Пусть <tex> x \notin F </tex>, тогда <tex>x \in X \backslash F = G = \bigcup\limits_{\alpha}{V_{r_\alpha}(x_{\alpha}})</tex>.
: Значит, <tex> x \in V_r(y) </tex> и <tex> \rho(x, y) < r</tex>, <tex> F \bigcap V = \varnothing</tex>.
: Но, так как <tex>\rho(x, F) = 0</tex>, то <tex>\forall \varepsilon > 0\ \exists a \in F: \rho(x, a) < \varepsilon</tex>.

: По неравенству треугольника, <tex> \rho(y, a) < \rho(y, x) + \rho(x, a) < r + \varepsilon </tex>. При <tex>\varepsilon \rightarrow 0</tex> получаем, что <tex> \rho(y, a) < r </tex>, значит, точка <tex> a </tex> принадлежит открытому шару, значит <tex> F \bigcap V \ne \varnothing</tex>, получили противоречие.
}}

{{Теорема
|about=
о нормальности МП
|statement=
Любое МП - нормальное.

Пусть <tex> (X, \rho) </tex> - МП. <tex> F_1 \cap F_2 = \varnothing , F_1, F_2</tex> - замкнутые <tex> \Rightarrow \exists G_1, G_2: F_1 \subset G_1, F_2 \subset G_2; G_1 \cap G_2 = \varnothing </tex>
|proof=
<tex> f(x) = \frac {\rho(x, F_1)} {\rho(x, F_1) + \rho(x, F_2)} </tex>. Т.к. <tex> F_1 \cap F_2 = \varnothing </tex> и <tex> F_1, F_2 </tex> - замкнуты, то знаменатель не равен 0. Следовательно, <tex> f(x) </tex> корректна и непрерывна в силу непрерывности <tex> \rho </tex>. При этом: <tex> x \in F_1 \Rightarrow f(x) = 0; x \in F_2: f(x) = 1 </tex>. Рассмотрим на R пару интервалов: <tex> (- \infty; \frac 1 3) </tex> и <tex> (\frac 1 2, + \infty) </tex>. Т.к. <tex> f(x) </tex> неперывна, то прообраз открытого множества - открытое множество(это другое определение непрерывного отображения, оно почти эквивалентно тому, которое было дано ранее).
: <tex> G_1 = f^{-1} ( - \infty; \frac 1 3); G_2 = f^{-1}(\frac 1 2, + \infty) </tex>
: <tex> F_1 \in G_1; F_2 \in G_2; G_1 \cap G_2 = \varnothing </tex>, ч.т.д.
}}

{{Теорема
|about=топологическое определение непрерывности
|statement=
Пусть у нас есть <tex> f :(X, \rho) \to (Y, \rho), </tex> тогда
<tex> f </tex> - непрерывная <tex> \iff </tex> прообраз любого открытого множества открыт.
|proof=
1.Докажем в одну сторону
Рассмотрим открытое множество G в У.
Рассмотрим произвольную точку f(p) из G.
Так как G открытое то <tex> \exists \varepsilon >0 : V_\varepsilon(f(p)) \in G </tex>
По непрерывности <tex> \exists \delta : x \in V_\delta(p) \Rightarrow f(x) \in V_\varepsilon(f(p)) </tex>
Подберем такое <tex> \delta </tex>
Из выше сказанного следует что <tex> V_\delta(p) \in f^-1(p) </tex>.
<tex> \delta </tex> можно найти для любого p значит прообраз открыт
}}
Замечание: так как замкнутые множества являются дополнениями открытых, то отсюда напрямую следует, что прообраз замкнутого множества при непрерывном отображении замкнут.

== Свойства непрерывных отображений. Определение компакта ==
{{Определение
|definition=
Множество ''ограниченное'', если его можно поместить в шар.
}}
1)
{{Определение
|definition=
Пусть <tex> (X, \rho) </tex> {{---}} МП. <tex> K \in X </tex> является '''компактом''' в X, если из любой последовательности точек принадлежащих K можно выделить сходящуюся подпоследовательность <tex> x_n: \lim x_n \in K </tex>.
}}
<tex> [a, b] </tex> на <tex> \mathbb{R} </tex> - классический пример.
{{Утверждение
|statement = Легко видеть что если K {{---}} компакт, то оно ограниченное, замкнутое. Обратное в общем случае не верно.
|proof =
Докажем от противного.

Предположим, что K неограниченное.
То есть <tex> \forall x \in K, \forall\varepsilon > 0 \exists x_1 \in K : \rho (x, x_1) > \varepsilon</tex>.

Тогда мы можем построить последовательность из таких точек <tex>x_i: \rho (x_i, x_{i+1}) > \varepsilon</tex>.

Эта последовательность неограниченна и из нее нельзя выделить сходящуюся. Но К {{---}} компакт, получили противоречие с определением компакта.
То, что K {{---}} замкнутое, следует из основного характеристического свойства замкнутых множеств.
}}

2)
{{Определение
|definition=
<tex> A \in X </tex> является связным, если нельзя подобрать пару имеющих хотя бы одну общую точку с <tex>A</tex> множеств <tex> G_1, G_2 \in \tau: G_1 \cap G_2 = \varnothing, A = (A \cap G_1) \cup (A \cap G_2) </tex>
}}
Например, любой промежуток на R - связное множество.

{{Теорема
|about=
свойство связанного множества на вещественной оси
|statement=
Вместе с парой точек оно содержит отрезок с концами в этих точках.
Пусть A - связное в R. Пусть <tex> a, b \in A </tex>. Если <tex> \forall c \in (a, b): c \in A </tex>, свойство верно.
|proof=
<tex> G_1 \cup G_2 = R \backslash \{c\}, c \in A. A = (A \cap G_1) \cup (A \cap G_2) \Rightarrow A </tex> не связно, получили противоречие, <tex> c \in A </tex>, ч.т.д.
}}

Эти классы определены, т.к:
{{Теорема
|statement=
Пусть K - компакт в <tex> (X, \rho); f: K \rightarrow (Y, \rho'), f </tex> {{---}} непрерывное отображение. Тогда <tex>f(K) </tex> - компакт в <tex> (Y, \rho') </tex> (непрерывный образ компакта {{---}} компакт).
|proof=
Рассмотрим <tex> y_n \in f(K) \Rightarrow y_n = f(x_n), x_n \in K </tex>.
<tex> \exists x_{n_k} \rightarrow x \in K </tex>. По непрерывности <tex> f(K): y_{n_k} = f(x_{n_k}) \rightarrow y = f(x) \in f(K) </tex>, ч.т.д.
}}

== Равномерно непрерывные отображения ==
{{Определение
|definition=
Пусть заданы МП: <tex> (X, \rho), (Y, \rho'), E \subset X</tex>. Тогда <tex> f: E -> Y</tex> {{---}} '''равномерно непрерывное отображение''', если
<tex> \forall \varepsilon > 0\ \exists \delta > 0: \forall x{'}, x{''} \in E:\ \rho(x{'}, x{''}) < \delta \Rightarrow \rho'(f(x{'}), f(x{''})) < \varepsilon</tex>
}}

{{Теорема
|statement=
Отображение, равномерно непрерывное на <tex> E </tex>, непрерывно в любой точке <tex> a </tex> множества <tex> E </tex>.
|proof=
Достаточно положить <tex> x = x{'}, a = x{''} </tex>, тогда отображение будет непрерывным по определению.
}}
Замечание: обратное в общем случае неверно.

Например, пусть <tex> X = Y = \mathbb R, E = (0, 1), f(x) = \sin(\frac1x)</tex> - непрерывная функция.

Положим <tex> x{'}_n = \frac1{\pi n}, x{''}_n = \frac1{\frac{\pi}{2} + 2\pi n} </tex>.
Тогда <tex> |x{'}_n - x{''}_n| \rightarrow 0 </tex>, но <tex> |f(x{'}_n) - f(x{''}_n)| \rightarrow 1 </tex>, значит, <tex> f(x) </tex> - не равномерно непрерывное отображение.

{{Теорема
|author=
Кантор
|statement=
Пусть даны МП <tex> (X, \rho), (Y, \rho)</tex>, <tex> K \subset X</tex> - компакт, <tex> f: K \rightarrow Y </tex> - непрерывное отображение. Тогда <tex> f </tex> также и равномерно непрерывное на <tex> K </tex>.
|proof=
Допустим, что это не так. Тогда, по логическому отрицанию: <tex>\exists \varepsilon_0 > 0~ \, \forall \delta > 0~ \exists {x'}_\delta, {x''}_\delta \in K: \rho({x'}_\delta, {x''}_\delta) < \delta ; \rho(f({x'}_\delta), f({x''}_\delta)) \ge \varepsilon_0; </tex>

Рассмотрим:<tex> \partial_{n}=\frac{1}{n}: {x}'_{n}={x}'_{\partial_{n}}, {x}''_{n}={x}''_{\partial_{n}}, \rho({x}''_{n},{x}'_{n})< \frac{1}{n}; \rho(f({x}''_{n}),f({x}'_{n}))\geq \varepsilon _{0}</tex>

т.к. K {{---}} компакт, т.е. в послед <tex>{x}'_{n}</tex> можно выделить сходящуюся подпоследовательность меньшую <tex>\frac{1}{{n}'_{k}}</tex>следовательно стремящуюся к нулю.

<tex>{x}'_{n_{k}} \rightarrow x\in K</tex>

<tex>\rho ({x}''_{n_{k}},x)< \rho ({x}''_{n_{k}},{x}'_{n_{k}}) + \rho ({x}'_{n_{k}},x) \rightarrow 0</tex>

<tex>{x}''_{n_{k}}\rightarrow x</tex> т.к. f {{---}} непрерывна на K, из получаем <tex>f({x}'_{n_{k}})\rightarrow f(x)</tex>, значит растояние между ними стремится к нулю: противоречие. Как то так.
}}

'''Частный случай: <tex>[a,b]\subset \mathbb{R}, f:[a,b]\rightarrow \mathbb{R}</tex>'''

по т. Кантора f {{---}} равномерно и непрерывна на <tex>[a,b]</tex> т.е.

<tex>\forall \varepsilon > 0 \exists \delta > 0 : \left | \bigtriangleup x \right | < \delta ; x, x+ \bigtriangleup x \in [a,b] \rightarrow \left | f(x+ \bigtriangleup x)-f(x) \right |<\varepsilon </tex>

{{Теорема
|statement=
Непрерывный образ связного множества связен.
|proof=
A {{---}} связно в X,
f(a) {{---}} непрерывный образ,
<tex> \sqsupset f(A) </tex> {{---}} не связно <tex>\Rightarrow G_{1}\cap G_{2} = \varnothing </tex> в Y <tex>; G_{1}\cap G_{2} </tex> - открытые множества

<tex>f(A)\subset G_{1}\cup G_{2}</tex>

<tex>A\subset f^{-1}(G_{1})\cup f^{-1}(G_{2})</tex>

прообразы открытых множеств открыты, оба они входят в A, а значит A {{---}} не связно {{---}} противоречие.
}}

{{Теорема
|author=
Коши
|about=
о промежуточных значениях функции
|statement=
Пусть <tex> f: \mathbb R \rightarrow \mathbb R </tex> {{---}} непрерывная функция на <tex> [a; b], f(a) = A, f(b) = B</tex>, для определенности считаем, что <tex> A < B </tex>.
Тогда <tex> \forall D: A < D < B\ \exists d \in (a; b): f(d) = D </tex>.
|proof=
Поскольку отрезок <tex> [a; b] </tex> {{---}} связное множество, значит, его образ <tex> f([a; b]) </tex> при непрерывном отображении связен. По свойству связных на <tex> R </tex> множеств, так как <tex> A, B \in f([a; b]) </tex>, то и <tex> [A; B] \in f([a; b]) </tex>. Значит, для любого <tex> D \in [A; B] </tex> соответствующий прообраз <tex> d </tex> найдется.
}}

{{Теорема
|id=
weirstrass
|author=
Вейерштрасс
|statement=
Пусть <tex> f: K \rightarrow \mathbb R </tex> {{---}} непрерывная функция на компакте <tex> K </tex>.
Тогда существуют такие <tex> x_1, x_2 </tex>, что <tex> f(x_1) = \inf\limits_{K}f, f(x_2) = \sup\limits_{K}f </tex>.
|proof=
Пусть <math>f(x)</math> — функция, отвечающая условиям теоремы (на компакте <math>A</math>), <math>M = \sup_A f</math>. Возьмём последовательность чисел <math>a_m</math> таких, что <math>\lim a_m = M</math> и <math>a_m < M</math>. Для каждого <math>m</math> найдётся точка <math>x_m</math>, такая что
<math>a_m < f(x_m)</math>. Имеем дело с компактом, поэтому, согласно [[Теорема Больцано — Вейерштрасса|теореме Больцано — Вейерштрасса]] из последовательности <math>x_m</math> можно выделить сходящуюся последовательность <math>\{x_{m_k}\}</math>, предел которой лежит в <math>A</math>.

Для любого <math>x_m</math> справедливо <math>a_m < f(x_{m_k}) < M</math>, поэтому, применяя [[предельный переход]], получаем <math>\lim f(x_{m_k}) = M</math> и в силу непрерывности функции существует точка <math>x_0</math> такая, что <math>\lim f(x_{m_k}) = f(x_0)</math> и, следовательно <math>M = f(x_0)</math>.

Таким образом функция <math>f(x)</math> ограничена и достигает своей верхней грани при <math>x = x_0</math>. Аналогично и для нижней грани.
}}

[[Категория:Математический анализ 1 курс]]

Список заданий по ДМ 2к 2021 осень

2021-09-11T18:39:04Z

77.234.193.84: enter fix

# Во всех задачах этой серии графы неориентированные, ребро соединяет две различные вершины, между парой вершин есть не более одного ребра. Какое максимальное число ребер может быть в графе с $n$ вершинами?
# Какое максимальное число ребер может быть в графе с $n$ вершинами и двумя компонентами связности?
# Постройте граф с $n$ вершинами, $m$ ребрами и $k$ компонентами связности. Здесь и далее ""постройте граф с $n$ вершинами, ..."" означает, что вы должны рассказать способ для любого $n$ построить искомый граф, либо рассказать, для каких $n$ такой граф существует и указать способ его построить, а для остальных $n$ доказать, что такого графа не существует. Аналогично следует поступить с другими параметрами, указанными в условии задачи.
# Обозначим как $N(u)$ множество соседей вершины $u$. Постройте граф с $n$ вершинами, в котором множества $N(u)$ совпадают для всех вершин $u$. Опишите все такие графы.
# Обозначим как $N[u]$ множество, содержащее вершину $u$, а также соседей вершины $u$. Постройте граф с $n$ вершинами, в котором множества $N[u]$ совпадают для всех вершин $u$. Опишите все такие графы.
# Постройте граф с $n$ вершинами, где каждая вершина имеет степень $d$.
# Докажите, что любой граф, содержащий хотя бы две вершины, имеет две вершины одинаковой степени.
# Докажите, что в графе число вершин нечетной степени четно.
# Докажите, что если в графе ровно две вершины нечетной степени, то они лежат в одной компоненте связности.
# Обозначим как $\delta(G)$ минимальную степень вершины в графе, как $\Delta(G)$ - максимальную степень вершины в графе. Для заданных $n$ и $k$ постройте граф с $n$ вершинами, в котором $\delta(G) + \Delta(G) = k$.
# Для заданных $n$, $d$ и $D$ постройте граф с $n$ вершинами, в котором $\delta(G) = d$, $\Delta(G) = D$.
# Докажите, что для любого графа $G$ можно записать в каждой вершине $u$ такое число $d(u)$, что числа $d(u)$ и $d(v)$ имеют общий делитель, отличный от 1, тогда и только тогда, когда в графе $G$ есть ребро $uv$.
# В графе $G$ можно записать в каждой вершине $u$ такое число $d(u)$, что числа $d(u)$ и $d(v)$ равны тогда и только тогда, когда в графе $G$ есть ребро $uv$. Что можно сказать про граф $G$?
# Граф называется кубическим, если степень всех вершин равна 3. Какое минимальное число вершин может быть в кубическом графе?
# Три вершины графа образуют треугольник, если они попарно соединены ребром. Постройте кубический граф с $n$ вершинами, не содержащий треугольников.
# Доказать или опровергнуть, что если ребро $uv$ - мост, то $u$ и $v$ - точки сочленения.
# Доказать или опровергнуть, что если $u$ и $v$ - точки сочленения, то $uv$ - мост.
# Рассмотрим отношение на рёбрах - $R$. $ab R cd$, если 1) $ab$ и $cd$ имеют общую вершину; 2) $ab$ и $cd$ лежат на цикле. Доказать, что вершинная двусвязность - это $R^*$.
# Доказать, что ребро $uv$ - мост тогда и только тогда, когда $uv$ вершинно двусвязно только с самим собой.
# Докажите, что если в графе с $n$ вершинами $\delta(G) > (n - 1) / 2$, то он связен.
# Докажите, что наименьшее число вершин в кубическом графе, в котором есть мост, равно 10.
# Докажите, что любой кубический граф, который содержит точку сочленения, содержит также мост.
# Граф называется самодополнительным, если он изоморфен своему дополнению. Приведите примеры самодополнительных графов с 4 и 5 вершинами. Докажите, что если граф является самодополнительным, то он содержит либо $4n$ либо $4n+1$ вершину для некоторого целого положительного $n$.
# Докажите, что для любого целого положительного $n$ существует самодополнительный граф, содержащий $4n$ вершин, а также самодополнительный граф, содержащий $4n+1$ вершину.
# Докажите, что граф связен тогда и только тогда когда для любого разбиения его множества вершин $V$ на два непустых непересекающихся множества $X$ и $Y$ существует ребро, соединяющее эти множества.
# Докажите, что в связном графе любые два самых длинных простых пути имеют общую вершину.
# Докажите или опровергните, что в связном графе все простые пути, имеющие максимальную возможную длину в этом графе, имеют общую вершину.
# Докажите, что либо граф $G$, либо его дополнение $\overline{G}$ связен.
# Будем говорить, что $G$ связан короткими путями, если между любыми двумя вершинами в $G$ есть путь длины не более 3. Докажите, что либо $G$, либо $\overline G$ связан короткими путями.
# Приведите пример графа, что ни он, ни его дополнение не связаны путями длины не больше 2.
# Найдите максимальное число ребер в графе с $n$ вершинами, не содержащем нечётных простых циклов.
# Найдите максимальное число ребер в графе с $n$ вершинами, не содержащем чётных простых циклов.
# Докажите, что граф с $n$ вершинами и $n + 4$ ребрами содержит два простых цикла, не имеющих общих ребер.