|
Теорема Кронекера – Капелли.Опр Системой m лин-ных ур-ний с n-неизвестными наз-ся система вида (1) Опр. Реш-ем сист m лин ур-й с n неизв. наз-ся любой упоряд. набор чисел α1,α2,..,αn, при подстановке котор. в кажд. ур-е сист оно превр. в верное рав-во Опр. Если слу имеет реш-е, она наз-ся совместной, иначе – несовместной. Опр Рангом матрицы А наз-ся ранг системы ее строк, если строки рассматривать как n-мерные числ. векторы. Опр Ранг матрицы- это число базисных строк матрицы, или это макс. число лнз строк матрицы. Пусть дана слу:
А1= расшир. матр сист (1) Т.(Кронекера-Капелли крит. совместности слу). Чтобы слу (1) была совместной необх. и достат., чтобы ранг матрицы системы был равен рангу расшир.матрицы системы, т. е. rang(A)=rang(A1). Д-во. 1) Пусть система (1) совместна, тогда Пусть r= rang(A). Рассмотрим L – лин. оболочку системы из r базисных столбцов матрицы A. Любой столбец А линейно выражается через базисные столбцы, значит, любой столбец А принадлежит L, но из рав-в (2) следует, что последний столбец матрицы A1 - 2) Пусть rang(A)=rang(A1)=r, тогда сущ. r базисных столбцов матрицы А, а т. к. они принадлежат и матрице А1 и явл-ся базисными в А1, след-но, любой столбец А и А1 линейно выражается через базисные столбцы. П оследний столбец А1 не входит в базис, так как его нет в А, но линейно выражается через базисные столбцы, значит, его можно линейно выразить и через все столбцы матрицы А, тогда найдутся с1,..,сn
15.Задача поиска. Дерево поиска. Одной из главных задач при работе с данными большого объема является поиск некоторых данных по заданному шаблону. В общем виде задачу поиска можно рассматривать так: пусть дано n записей R1, R2,..,Rn со значениями некоторого ключевого поля k1,k2,..,kn. Также дано некоторое значение ключа key. Требуется найти все записи R, такие что k=key. Дерево поиска. Все данные помещаются в бинарное дерево, формируемое след. образом: в корень идет 1-й ключ, если очередной ключ < значения в текущем узле, он идет налево, если больше- направо. Поиск по такому дереву произв-ся сравнением ключа со значением в текущем узле и движением по дереву в соотв. сторону. В лучшем случае сложность алгоритма О(log2n), в худшем случае дерево может вырождаться в линейный список, тогда сложность 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.Докажите, что сущ. предел ![]() ![]() Что будет с Землей, если ось ее сместится на 6666 км? Что будет с Землей? - задался я вопросом... ![]() Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем... ![]() ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования... ![]() Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)... Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:
|