шпоры 3 (шпоры в ворде на печать)
Описание файла
Файл "шпоры 3" внутри архива находится в папке "шпоры в ворде на печать". Документ из архива "шпоры в ворде на печать", который расположен в категории "". Всё это находится в предмете "математический анализ" из 7 семестр, которые можно найти в файловом архиве МГТУ им. Н.Э.Баумана. Не смотря на прямую связь этого архива с МГТУ им. Н.Э.Баумана, его также можно найти и в других разделах. Архив можно найти в разделе "к экзамену/зачёту", в предмете "высшая математика" в общих файлах.
Онлайн просмотр документа "шпоры 3"
Текст из документа "шпоры 3"
Вопрос №33 | Вопрос №34 | Вопрос №35 | Вопрос №36 |
Взвешенный граф – это граф, для которого задано отображение w:ER0, где R0 – множество действительных неотрицательных чисел. Алгоритм Прима для нахождения минимального остовного дерева. e1; 1-й шаг. w(e1) w(e) eEG. P1={e1} i-й шаг. Pi-1 – дерево. Ei={e1EG|Pi-1{e} – тоже дерево}. ei*eEi; w(ei) w(e) eEi Pn-m – минимальное остовное дерево. Скорость работы порядка o(n*m).//Начинаем с пустого U=0. Добавляем к U вершины, каждый раз находя ребро наименьшей стоимости между U и V\U.Положить в U любую вершину; // изначально U - пусто. while ( V\U не пусто ) { Выбрать ребро (u, v) наименьшей стоимости, u из U, v из V\U; Добавить v к U и убрать из V\U; } | Алгоритм Краскала состоит в «сшивании» искомого дерева из компонент остовного леса, первоначально представляющего собой множество изолированных вершин исходного графа, по следующему правилу: из текущего списка ребер (первоначально – это список всех ребер), упорядоченного по возрастанию весов, извлекается ребро наименьшего веса; если оно соединяет вершины, принадлежащие разным компонентам текущего остовного леса, то оно добавляется к текущему множеству ребер искомого дерева (первоначально это множество пусто) при одновременном слиянии указанных компонент в одну; иначе ребро отвергается. После удаления очередного ребра из списка процесс повторяется до тех пор, пока число компонент остовного леса не окажется равным 1 – это и будет искомое остовное дерево наименьшего веса. Доказательство. Ci (I<n-1); |Vci|=n; |Ec_i|=I<n-1; Ci – не связан Ei+10 Ci+1 – строится Сn-1 будет всегда построен. Ci-1 – ацикличный. |Vc_n-1|=|Ec_n-1|+1 Cn-1 – дерево. Докажем, что дерево минимально (от противного). Пусть Cn-1 не МОД. Выберем T – МОД, такое, что количество общих ребер у T и Cn-1 максимально. Сn-1 ei – ребро с наименьшим номером, не входящее в T. В T есть путь , соединяющий a и b. T{ei} – содержит единственный цикл. Создаем список вершин L, в неубывающем по весу порядке while ( число отмеченных вершин < |V|-1 ) {w = L.Remove(); // удалить из головы списка if ( w соединяет две несвязных компоненты ) отметить w и добавить к MST else // w - внутри компоненты не отмечать w // это приведет к циклу в MST } | Неориентированный (ориентированный) граф G – это пара множеств G=<V,E>, где V – конечное множество, элементы которого называют вершинами или узлами. E – множество неупорядоченных (упорядоченных) пар на V, т.е. подмножество множества двухэлементных подмножеств V (VV), элементы которого называют ребрами (дугами). Матрица смежности вершин – это квадратная матрица B n-го порядка, элементы которой определяются для неориентированного графа следующим образом: bij={1, если из i-ой вершины в j-ую ведет дуга,0, иначе. Замечание: в k-ой строке матрицы орграфа количество единиц равно полустепени исхода dg+vk вершины vk, а количество единиц в k-ом столбце – полустепени захода dg-vk. Матрица достижимости – это матрица C размера |V||V|, каждый элемент которой Cij={1, если j-я вершина достижима из I-й,0, иначе. Согласно определению достижимости, элементы Cij=1. Матрица достижимости несет очень важную информацию о графе. C для любой пары индексов i, j Cij=Cji=1, дает номера вершин, образующих бикомпоненту, а для любых i, j Cij=1 или Cij=1, дает номера вершин, образующих компоненту. Элемент a<l>ij матрицы меток дуг Al, l0 равен стоимости прохождения из i в j по всем путям длины l. Т.к. стоимость прохождения между парой вершин <vi,vj> равна сумме меток всех путей, ведущих из первой вершины во вторую, а указанную сумму можно получить, суммируя последовательно метки путей длины 0, длины 1, длины 2 и т.д., то матрица стоимостей взвешенного орграфа может быть представлена в виде C=A0+A1+A2+An+…=n0An или C=A*. Матрица меток дуг, размеченная над булевым полукольцом B=({0,1}, +, , 0, 1) – матрица смежности. Решая в B=({0,1}, +, , 0, 1) систему уравнений при всех j=1..n: =A+j , где j – j-й единичный вектор, получаем наименьшее решение вида =A*j. Тогда столбец =A*j есть j-й столбец матрицы достижимости С=A*. | Взвешенный орграф – это пара W=<G,>, где G=<V,E> - обычный орграф, а :ER – весовая функция со значениями в некотором замкнутом полукольце R=<R,+,*,0,1>. Задача о кратчайшем пути – вычисление наименьших расстояний между всеми парами вершин в орграфе. Неориентированный (ориентированный) граф G – это пара множеств G=<V,E>, где V – конечное множество, элементы которого называют вершинами или узлами. E – множество неупорядоченных (упорядоченных) пар на V, т.е. подмножество множества двухэлементных подмножеств V (VV), элементы которого называют ребрами (дугами). Элемент a<l>ij матрицы меток дуг Al, l0 равен стоимости прохождения из i в j по всем путям длины l. Т.к. стоимость прохождения между парой вершин <vi,vj> равна сумме меток всех путей, ведущих из первой вершины во вторую, а указанную сумму можно получить, суммируя последовательно метки путей длины 0, длины 1, длины 2 и т.д., то матрица стоимостей взвешенного орграфа может быть представлена в виде C=A0+A1+A2+An+…=n0An или C=A*. Решая в полукольце R+=(R+{+}, min, +, +, 0) систему уравнений при всех j=1..n: =B+j , где j – j-й единичный вектор, получаем наименьшее решение вида =B*j. Тогда столбец =B*j есть j-й столбец матрицы стоимости кратчайших путей С=A*. Матрица смежности вершин – это квадратная матрица B n-го порядка, элементы которой определяются для неориентированного графа следующим образом: bij={1, если из i-ой вершины в j-ую ведет дуга,0, иначе. Замечание: в k-ой строке матрицы орграфа количество единиц равно полустепени исхода dg+vk вершины vk, а количество единиц в k-ом столбце – полустепени захода dg-vk. Матрица меток дуг, размеченная над булевым полукольцом B=({0,1}, +, , 0, 1) – матрица смежности. |
Вопрос №37 | Вопрос №38 | Вопрос №39 | Вопрос №40 |
Взвешенный орграф – это пара W=<G,>, где G=<V,E> - обычный орграф, а :ER – весовая функция со значениями в некотором замкнутом полукольце R=<R,+,*,0,1>. Задача о кратчайшем пути – вычисление наименьших расстояний между всеми парами вершин в орграфе. Неориентированный (ориентированный) граф G – это пара множеств G=<V,E>, где V – конечное множество, элементы которого называют вершинами или узлами. E – множество неупорядоченных (упорядоченных) пар на V, т.е. подмножество множества двухэлементных подмножеств V (VV), элементы которого называют ребрами (дугами). Алгоритм Дейкстры. Дан взвешенный орграф G=(V,E); :ER>0. Началоvs: l(s)=0, постоянная. l(v)=, временная, V’:=V\{s}. Текущая вершина p:=s. Итерация: N(p)={vV| (p,v)E}. Просмотр vN(p), l(v) – временные. Если l(v)>l(p)+ (p,v), то l(v):=l(p)+ (p,v); (v)=p, иначе ничего не меняется и переходим к следующей вершине. Правило появления постоянных меток: V’={v|l(v)-временная}. Ищется v*: l(v*)=min{l(v)|vV}, тогда l(v*) – постоянная. | Конечный автомат – орграф, размеченный над полукольцом R(V) регулярных языков в алфавите V, с выделенной вершиной q0 , которая называется начальной и ограниченным набором заключительных вершин. Конечный автомат называется детерминированным, если в нем нет дуг с меткой и из любого состояния по любому входному символу возможен переход ровно в одно состояние. Способы задания: граф, таблица. | Конечный автомат – орграф, размеченный над полукольцом R(V) регулярных языков в алфавите V, с выделенной вершиной q0 , которая называется начальной и ограниченным набором заключительных вершин. Конечный автомат называется детерминированным, если в нем нет дуг с меткой и из любого состояния по любому входному символу возможен переход ровно в одно состояние. Постановка задачи о минимизации. Существует автомат M. Существует ли автомат M’, который так же реагирует на входные последовательности, но имеет меньшее число состояний. Автомат называется минимальным, если его нельзя покрыть автоматом с меньшим числом состояний. Два состояния s1 и s2 Er эквивалентны если для любого aAr (s1,a)= (s2,a). Два состояния называются E эквивалентными, если они Er эквивалентны для любого r. Теорема. Пусть задан автомат M. S’ – множество классов эквивалентности его состояний. S’ является множеством состояний автомата M’. M’ – минимальный автомат, эквивалентный M. | Конечный автомат – орграф, размеченный над полукольцом R(V) регулярных языков в алфавите V, с выделенной вершиной q0 , которая называется начальной и ограниченным набором заключительных вершин. Конечный автомат называется детерминированным, если в нем нет дуг с меткой и из любого состояния по любому входному символу возможен переход ровно в одно состояние. Отношение 0-эквивалентности: q1 0 q2 (q1 F)(q2 F) или (q1 F)(q2 F). Т.е. оба сост. одновр. являются или нет заключит. Отношение К-эквивалентности: q1 k q2 q1 k-1 q2 и aV(q1,a) k-1 (q1,a), k1. Т.е К-экв. состояния по любому входному символу переходят из (к-1) обратно в (к-1) класс эквивалентности. Минимальный автомат – КА, содержащий наименьшее число состояний среди эквивалентных ему (т.е. реализующих тот же язык). Минимизация КДА состоит в разбиении множества состояний автомата на классы эквивалентности до тех пор, пока не получится минимальное разбиение. Тогда мы получим КДА с наименьшим числом состояний, эквивалентный исходному. Алгоритм: Строим КДА, эквивалентный исходному КА. Если в нем есть состояния, недостижимые из начального, удаляем их. Полученный КА разбиваем на классы эквивалентности (сначала на 0, потом дробим на К). |
Вопрос №41 | Вопрос №42 | Вопрос №43 | Вопрос №44 |
Алфавит – произвольное непустое конечное множество V={a1 ,…,an }, элементы которого называют буквами или символами. Словом или цепочкой в алфавите V называют произвольный кортеж из множества VК (К-ой декартовой степени алфавита V) для различных К=0, 1, … . Длина слова – число компонент кортежа. Языком в алфавите V называется произвольное подмножество множества V*. Множество всех языков в алфавите V, т.е. 2 V*, есть булеан счетного множества и имеет мощность континуума. Операции над языками: Соединение (конкатенация) слов: для х=х(1) х(2)… и у= у(1) у(2)… соединение ху = х=х(1) х(2)…у(1) у(2)… . Из определения следует, что конкатенация ассоциативна и множество V* всех слов в алфавите V образует моноид. Конкатенация языков L1 и L2 – язык L1L2, состоящий из всех возможных соединений слов ху, где слово хL1, а yL2 . Итерация языка L - объединение всех его степеней. L* = Ln, где n = 0…. | Регулярные языки порождаются регулярными грамматиками, для которых АаВ или Аа, где а – либо терминал, либо пустая цепочка (В -нетерминал). В замкнутом полукольце всех языков в алфавите V < 2V, , , , {}> рассмотрим подалгебру, порожденную множеством из , {} и всех однобуквенных языков {a}V, и замкнутую относительно итерации. Эта подалгебра, обозначаемая R(V), является полукольцом с итерацией. Элементы полукольца R(V) называются регулярными языками. Пусть фиксирован некий алфавит V. Тогда:
Каждое регулярное выражение представляет некоторое однозначно определяемый регулярный язык и используется для представления алгебраических операций над регулярными языками. Мощность множества регулярных языков равна 2V . | Регулярные языки порождаются рег. грамматиками, для кот. АаВ или Аа, где а – либо терминал, либо пустая цепочка (В -нетерминал). Язык – мн-во всех терминальных цепочек, порождаемых аксиомой грамматики. Конечный автомат – орграф, размеченный над полукольцом R(V) рег. языков в алфавите V, с выделенной вершиной q0 , которая называется нач. и ограниченным набором заключительных вершин. Теорема: Язык LV* является рег. тогда и только тогда, когда он допускается некоторым конечным автоматом. Доказательство: Необх. Воспользуемся методом индукции по построению рег. языка как элемента замыкания множества {, {}, {a1},…, {an}} (т.е. сначала утвержд. доказывается для языков исходного мн-ва, замыкание которого строится, а затем в предположении, что утв-ние доказано для рег. языков L и K, оно док-ся для LK, LK, L*). Допустим, что кон. автоматы для языков L и K построены. Автоматы для LK, LK, L* строятся так же, как и в дз. Итак, каждый рег. язык допускается некоторым конечным автоматом. Достат. Язык кон. автомата – это конечное объединение языков, являющихся определенными элементами матрицы стоимостей автомата, а именно: находящимися в строке, соответствующей начальному состоянию q0 и в столбцах, соотв. всем заключ. сост. qf. Матрица стоимостей – итерация матрицы меток дуг, задающей автомат. Метка каждой дуги – рег. выражение=>матрица стоимостей состоит из рег.=>язык конечного автомата – рег. Задача построения языка по автомату. Для решения этой задачи достаточно любым методом вычислить матрицу стоимости автомата (напр., решить в полукольце R(V) систему уравнений =A+, где -столбец, компоненты которого равны , кроме тех, которые соответствуют заключ. состояниям). Задача синтеза – задача построения автомата по языку. | Регулярные языки порождаются рег. грамматиками, для кот. АаВ или Аа, где а – либо терминал, либо пустая цепочка (В -нетерминал). Язык – мн-во всех терминальных цепочек, порождаемых аксиомой грамматики. Конечный автомат – орграф, размеченный над полукольцом R(V) рег. языков в алфавите V, с выделенной вершиной q0 , которая называется нач. и ограниченным набором заключительных вершин. Теорема: Язык LV* является рег. тогда и только тогда, когда он допускается некоторым конечным автоматом. Доказательство: Необх. Воспользуемся методом индукции по построению рег. языка как элемента замыкания множества {, {}, {a1},…, {an}} (т.е. сначала утвержд. доказывается для языков исходного мн-ва, замыкание которого строится, а затем в предположении, что утв-ние доказано для рег. языков L и K, оно док-ся для LK, LK, L*). Допустим, что кон. автоматы для языков L и K построены. Автоматы для LK, LK, L* строятся так же, как и в дз. Итак, каждый рег. язык допускается некоторым конечным автоматом. Достат. Язык кон. автомата – это конечное объединение языков, являющихся определенными элементами матрицы стоимостей автомата, а именно: находящимися в строке, соответствующей начальному состоянию q0 и в столбцах, соотв. всем заключ. сост. qf. Матрица стоимостей – итерация матрицы меток дуг, задающей автомат. Метка каждой дуги – рег. выражение=>матрица стоимостей состоит из рег.=>язык конечного автомата – рег. Задача построения языка по автомату. Для решения этой задачи достаточно любым методом вычислить матрицу стоимости автомата (напр., решить в полукольце R(V) систему уравнений =A+, где -столбец, компоненты которого равны , кроме тех, которые соответствуют заключ. состояниям). |
Вопрос №45 | Вопрос №46 | Вопрос №47 | Вопрос №48 |
Лемма о разрастании: Если L – регулярный язык, то существует N(L) : для любой цепочки xL, длина которой N, х допускает представление в виде х=u v w, где v и |v|N, причем для n0 цепочка хn=u vn w L. Иначе говоря, эта лемма утверждает, что любой регулярный язык допускает представление всех своих достаточно длинных цепочек в виде соединения трех цепочек, причем средняя их них не пуста, ограничена по длине и ее итерация не приводит к выбросу за пределы языка. Доказательство: Т.к. язык регулярен, следовательно существует конечный автомат, реализующий его. Положив N=|Q|, фиксируем произвольную цепочку xL, длина которой N, а т.к. N > 0, то x=x(0)…x(l). l>0. Т.к. автомат является КДА, то существует единственный путь ведущий из начального состояния в одно из конечных на котором читается х. Т.к. длина цепочки х не меньше числа состояний М, т.е. числа всех вершин графа М, то, поскольку число вершин в любом пути на 1 больше числа дуг в этом пути, число вершин в рассмотренном пути будет больше, чем число всех вершин графа. Это значит, что хотя бы одна из вершин данного пути повторяется и она, т.обр. она содержится в некотором контуре. Тогда путь, несущий цепочку х, делится на 3 части: до контура, контур и после контура. Пример нерегулярного языка: L={an bn | n0}, к этому языку не применима лемма о разрастании. Доказательство: Выберем достаточно большое n и получим следующие варианты подцепочки v:
| Лемма о разрастании: Если L – регулярный язык, то существует N(L) : для любой цепочки xL, длина которой N, х допускает представление в виде х=u v w, где v и |v|N, причем для n0 цепочка хn=u vn w L. Иначе говоря, эта лемма утверждает, что любой регулярный язык допускает представление всех своих достаточно длинных цепочек в виде соединения трех цепочек, причем средняя их них не пуста, ограничена по длине и ее итерация не приводит к выбросу за пределы языка. Доказательство: Т.к. язык регулярен, следовательно существует конечный автомат, реализующий его. Положив N=|Q|, фиксируем произвольную цепочку xL, длина которой N, а т.к. N > 0, то x=x(0)…x(l). l>0. Т.к. автомат является КДА, то существует единственный путь ведущий из начального состояния в одно из конечных на котором читается х. Т.к. длина цепочки х не меньше числа состояний М, т.е. числа всех вершин графа М, то, поскольку число вершин в любом пути на 1 больше числа дуг в этом пути, число вершин в рассмотренном пути будет больше, чем число всех вершин графа. Это значит, что хотя бы одна из вершин данного пути повторяется и она, т.обр. она содержится в некотором контуре. Тогда путь, несущий цепочку х, делится на 3 части: до контура, контур и после контура. Пример нерегулярного языка: (Язык допускается КА тогда и только тогда, когда он порождается регулярной грамматикой). L={an bn | n0}, к этому языку не применима лемма о разрастании. Доказательство: Выберем достаточно большое n и получим следующие варианты подцепочки v:
v=ap aq , 0<p<n, 0<q<n; в данном случае возникнет вхождение подцепочки ba, в слово, которое уже не принадлежит нашему языку. Следовательно, язык L не регулярен. | Грамматика G={XT, XN, A, M} ={терм.алфавит; нетерм. алф.; аксиома; множ. правил вывода или продукций} XC=XNXТ Порождающая грамматика является классическим способом определения языка. Порождающая грамматика позволяет выводить цепочки языка из некоторой начальной цепочки с помощью определенных правил замены. Процесс порождения – пошаговый. Язык, порождаемый грамматикой G – множество всех терминальных цепочек, выводимых из аксиомы грамматики. L(G)={xSx, xXT*} Вывод в грамматике: цепочка 0, 1, …,n, если i-1; n- длина вывода; 0 – аксиома грамматики. Иерархия Хомского. Согласно иерархии Хомского грамматики делятся на классы:
| НК-грамматики – неукорачивающие грамматики. G является НК-грамматикой, если для ее продукции длина |||| Теорема: Для НК-грамматики может быть построена эквивалентная ей контекстная грамматика. Доказательство: 1А21 2, Требуется изменить систему продукции, не меняя языка. Переопределим систему продукции: XN’=XN{D1…Dn} Составим следующую систему продукции. - плохая грамматика. =xi1…xin; =xj1…xjn Xi1…xinD1X12…x1n D … D1…Dn-1XinD1…Dn-1x1n D1…Dnxj1 D2…Dn … xj1…xjn-1Dnxj1…xjn= Теперь для аXT XN’=XN{Ea}, Во всех продукциях все терминалы заменены на нетерминалы, но наш язык пуст. Добавим продукции типа Ea а а. Мы получили К-грамматику, но язык не изменился. |