|
Корни многочленов и их кратность. Осн. теорема алгебры комплексных чисел и следствия из неё.⇐ ПредыдущаяСтр 20 из 20 Опр. Многочленом от перемен. x над кольцом R наз-ся выражение вида
arg(bk (coskφ+isinkφ))=arg(-b0). Положим φ=1/k*arg(-b0/bk). Тогда f(x)=b0(1- Опр Многочл. f Определение 2. Многочлен. f Следствие 1. Над полем комплексных чисел неприводимы только многочлены первой степени. Следствие 2. Пусть a0– старший коэффициент многочлена f, z1,z2,..,zn– корни многочлена f. такое представление однозначно с точностью до порядка следования сомножителей. 24.Графы, способы представл. графов в памяти компьютера, обход графов в ширину и глубину. Простым ориентир.графом наз-ся пара объектов G = (V, E), где V – конечное мн-во, Е – конечное подм-во V´V, при этом V наз-ся множеством вершин, Е – множеством дуг графа G. Любая дуга графа представима в виде упорядоченной пары (v1, v2), где v1 – начало, v2 – конец дуги, вершина v2 является смежной с вершиной v1.Граф G наз-ся симметрическим, если " i, j (vi, vj) ÎE => (vj, vi) ÎE. Часто в симметрических графах пары дуг (vi, vj) и (vj, vi) заменяют ребрами, при этом получают неориентированный граф.Две вершины могут быть соединены несколькими дугами, идущими в одном направлении. Такие дуги называются кратными, а граф, содержащий их, - мультиграфом. Дугу uÎE и вершину vÎV называют инцидентными, если дуга u либо входит в вершину v, либо выходит из нее. Степенью вершины наз-ся кол-во инцидентных с ней ребер (дуг). Путем в графе G = (V, E) наз-ся последовательность вершин v1, v2, …, vn, для которых существуют дуги (v1, v2), (v2, v3), …, (vn-1, vn). Длина пути – количество дуг, составляющих этот путь. Иногда каждой дуге присваивают некоторую стоимость. В этом случае под длиной пути понимается сумма стоимостей всех дуг, составляющих этот путь.Путь наз-ся простым, если все вершины в нем, за исключением возможно 1-ой и последней, различны. Цикл – это простой путь длиной не менее 1, который начинается и заканчивается в 1 и той же вершине.Граф G = (V, E) наз-ся сильносвязным, если " vi, vj Î V, vi ¹ vj $ путь из vi, в vj. Способы представл. графов 1) матрица смежности Матрица смежности для графа G = (V, E), где V={1, 2, …, n}- это матрица А размером n´n где А[i, j]=1 ó когда $ дуга (i, j). Все остальные эл-ты матрицы =0. Если каждому ребру графа поставлен в соответствие некоторый вес (стоимость), то матрица смежности часто заменяется матрицей стоимостей. Недостатки:требует объема памяти порядка n2 поиск в матрице смежности так же пропорционален n2 С другой стороны матрица смежности имеет большой плюс – прямой доступ к ее элементам.2) списки смежности Список смежности представляет собой массив указателей размером n, каждый элемент которого указывает на смежный с этим узлом элемент (вершину). Последовательность смежных вершин представляет собой линейный список. Списки смежности в среднем требуют меньше памяти, и при малом количестве дуг поиск происходит быстрее, но в случае полносвязных графов поиск так же пропорционален n2, кроме того, в списках невозможен прямой доступ к элементам. Поэтому списки в настоящее время для представления графов используется редко. Обход графа в ширину Пусть имеется граф G=(V, E). Необходимо построить путь из вершины vi в вершину vj содержащий минимальное кол-во дуг. Для нахождения такого пути используется волновой алгоритм (или обход в ширину).Первоначал. пометим все вершины метками-1.Присвоим вершине vi метку 0, далее пометим все вершины, смежные с vi, меткой 1. Далее пометим все вершины, смежные с «1-ми» вершинами, меткой 2 и т. д. до тех пор пока либо не будет помечена вершина vj, либо на очередном шаге не появилось ни одной вновь помеченной вершины. В 1-ом случае метка вершины vj будет соответствовать min количеству дуг, которые необходимо пройти от vi к vj. Сам путь можно найти обратным проходом от vi к vj по вершинам с уменьшающимися значениями меток. Во 2-м случае пути из vi в vj не $. Д анная процедура осуществляет пометку всех вершин, начиная с i-ой. Для поиска нужного пути необходимо пройти по массиву pu, начиная с j-ой вершины в сторону уменьшения меток.В случае если стоимости всех ребер графа одинаковые, волновой обход дает так же путь кратчайшей длины. Если ребра имеют различную стоимость, то в общем случае это не так. Обход графа в глубину Пусть имеется граф G, в котором первоначально все вершины помечены меткой «не посещалась». Обход в глубину начинается с выбора начальной вершины v графа G, которая помечается «посещалась». Затем для каждой вершины, смежной с v, которая еще не посещались, рекурсивно применяем поиск в глубину. Когда все вершины, которых можно достичь из вершиныv, будут посещены, обход заканчивается. Если при этом некоторые вершины остались непосещенными, выбирается одна из них и обход повторяется начиная с нее. Этот процесс продолжается до тех пор, пока все вершины не помечены как посещенные. Данный метод называется поиском (обходом) в глубину, т. к. поиск не посещенных вершин идет в направлении вперед (вглубь графа) от некоторой вершины до тех пор, пока это возможно. const n=10; type mas=array[1..n, 1..n] of word; mas1=array[1..n] of word; var count, v:word; m:mas; metka:mas1; procedure obhod(v:word); var i:word; begin metka[v]:=n+1; for i:=1 to n do if (m[v,i]=1)and(metka[i]=0) then obhod(i); end; begin count:=1; for v:=1 to n do if metka [v]=0 then obhod[v]; end. 24.Используя методы операционного исчисления, решить уравнение Вольтерра второго рода Обозначим Определение. Свёрткой функций f(t) и g(t), определённых при t Теорема (изображение свёртки функции). Если Применив преобразование Лапласа к обеим частям уравнения и воспользовавшись теоремой об изображении свёртки функций, получим:
Билет 24 ![]() ![]() ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между... ![]() Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам... ![]() Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все... ![]() Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|