Теорема Кронекера

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

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

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

Т.(Кронекера-Капелли крит. совместности слу). Чтобы слу (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).

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

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

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

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

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

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

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

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

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

при n

1.)

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

Система охраняемых территорий в США Изучение особо охраняемых природных территорий(ООПТ) США представляет особый интерес по многим причинам...

ЧТО ПРОИСХОДИТ, КОГДА МЫ ССОРИМСЯ Не понимая различий, существующих между мужчинами и женщинами, очень легко довести дело до ссоры...

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

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