Теорема Кронекера – Капелли.

Опр Системой m лин-ных ур-ний с n-неизвестными наз-ся система вида (1)

Опр. Реш-ем сист m лин ур-й с n неизв. наз-ся любой упоряд. набор чисел α1,α2,..,αn, при подстановке котор. в кажд. ур-е сист оно превр. в верное рав-во Опр. Если слу имеет реш-е, она наз-ся совместной, иначе – несовместной.

Опр Рангом матрицы А наз-ся ранг системы ее строк, если строки рассматривать как n-мерные числ. векторы. Опр Ранг матрицы- это число базисных строк матрицы, или это макс. число лнз строк матрицы.

Пусть дана слу:

(1), А- матрица системы (1), А= ,

А1= расшир. матр сист (1)

Т.(Кронекера-Капелли крит. совместности слу). Чтобы слу (1) была совместной необх. и достат., чтобы ранг матрицы системы был равен рангу расшир.матрицы системы, т. е. rang(A)=rang(A1). Д-во. 1) Пусть система (1) совместна, тогда такие что справедливы рав-ва (2):

Пусть r= rang(A). Рассмотрим L – лин. оболочку системы из r базисных столбцов матрицы A. Любой столбец А линейно выражается через базисные столбцы, значит, любой столбец А принадлежит L, но из рав-в (2) следует, что последний столбец матрицы A1 - -линейно выражается через столбцы матрицы A с коэффициентами c1,..,cn. Но т. к. любой столбец A1 L, то и L, тогда все столбцы A1 линейно выражаются через r базисных столбцов A. Значит столбцовые ранги матриц A и А1 равны, след-но rang(A)=rang(A1).

2) Пусть rang(A)=rang(A1)=r, тогда сущ. r базисных столбцов матрицы А, а т. к. они принадлежат и матрице А1 и явл-ся базисными в А1, след-но, любой столбец А и А1 линейно выражается через базисные столбцы.

П оследний столбец А1 не входит в базис, так как его нет в А, но линейно выражается через базисные столбцы, значит, его можно линейно выразить и через все столбцы матрицы А, тогда найдутся с1,..,сn P, такие что справедливо (2), следовательно, набор c1,..,cn – решение системы (1), следовательно, система (1) совместна.

15.Задача поиска. Дерево поиска. Одной из главных задач при работе с данными большого объема является поиск некоторых данных по заданному шаблону. В общем виде задачу поиска можно рассматривать так: пусть дано n записей R1, R2,..,Rn со значениями некоторого ключевого поля k1,k2,..,kn. Также дано некоторое значение ключа key. Требуется найти все записи R, такие что k=key.

Дерево поиска. Все данные помещаются в бинарное дерево, формируемое след. образом: в корень идет 1-й ключ, если очередной ключ < значения в текущем узле, он идет налево, если больше- направо. Поиск по такому дереву произв-ся сравнением ключа со значением в текущем узле и движением по дереву в соотв. сторону. В лучшем случае сложность алгоритма О(log₂n), в худшем случае дерево может вырождаться в линейный список, тогда сложность O(n).

Дерево – совокупность элементов, называемых узлами, один из которых определен как корень и родительских отношений, образующих иерархическую структуру узлов. (бинарное дерево – дерево, каждый узел которого может иметь не более двух сыновей.)

Пример. Дан массив: 2 17 3 1 4 0 9 19

Пример. Дан текстовый файл, в каждой строке которого нах-ся некоторое слово. Определить частоту вхождения каждого слова в файл.

type ss=^zveno;

zveno=record

zn: string;

k: integer;

left, right: ss;

end;

procedure FormTreePoisk (var z: ss; x: string);

begin

if z=nil then

begin

new(z); z^.zn:=x;

z^.left:=nil;z^.right:=nil;z^.k:=1;

end

else

if x<z^.zn then

FormTreePoisk (z^.left, x)

else if x>z^.zn then

FormTreePoisk (z^.right, x)

else z^.k:=z^.k+1;

end;

При симметричном обходе дерева получается отсортированная по возрастанию последовательность.

(существует три стандартных обхода деревьев. Обход – упорядочивание узлов дерева по какому-либо признаку.

1. прямой обход. Сначала рассматривается корень, потом левое поддерево и затем правое. Правило применяется рекурсивно ко всем поддеревьям.

2. обратный обход. Вначале посещается левое поддерево, далее правые поддеревья и затем корень. Правило применяется рекурсивно.

3. симметричный обход. Вначале посещается левое поддерево, затем корень, затем правые поддеревья. Правило применяется рекурсивно.

Дерево называется сбалансированным, если количество уровней в левом и правом поддеревьях отличаются не более чем на 1 и количество узлов тоже.)

15.Докажите, что сущ. предел (n возведений в степень) и найдите, чему он равен. (Послед., стоящая под знаком предела, задается рекуррентно следующим образом: a1=0,25, an+1= при n 1.)

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...

Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом...

ЧТО ТАКОЕ УВЕРЕННОЕ ПОВЕДЕНИЕ В МЕЖЛИЧНОСТНЫХ ОТНОШЕНИЯХ? Исторически существует три основных модели различий, существующих между...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: