Файл: ответы.doc

5.Сравнительный анализ алгоритмов поиска: линейный, двоичный

Само действие поиска элемента в наборе данных требует возможности отличать элементы друг от друга. Очевидно, сравнение числовых типов не вызывает трудности. В случае сравнения строк процедура усложняется. Можно выполнять сравнение чувствительное или нечувствительное к регистру, сравнение по локальным таблицам символов, когда оно выполняется на основе алгоритмов, специфичных для определенной страны или языка и т.д. При работе с объектами вообще не существует заранее определенной схемы сравнения за исключением сравнения указателей на эти объекты.

В таком случае лучше всего рассматривать процедуру сравнения в виде «черного ящика» – функции с четко определенным интерфейсом, которая в качестве входных параметров принимает указатели на два элемента и возвращает результат сравнения – первый элемент больше, меньше или равен второму.

Линейный поиск. Единственно возможным методом поиска элемента по значению ключа, находящегося в неупорядоченном наборе данных, является последовательный (линейный) просмотр каждого элемента, который продолжается до тех пор, пока не будет найден искомый элемент. Если просмотрен весь набор, но элемент не найден, искомый ключ отсутствует. Для последовательного поиска в среднем требуется (n+1)/2 сравнений и порядок алгоритма линейный O(n).

Программная иллюстрация линейного поиска в неупорядоченном массиве приведена ниже, где aList – исходный массив, aItem – искомый ключ; функция возвращает индекс найденного элемента или -1, если элемент отсутствует.

{ Линейный поиск в неотсортированном массивом }

function LineNonSortedSearch(aList: TList;

aItem: Pointer; aCompare: TCompareFunc): Integer;

var i: Integer;

begin

Result:=-1;

for i:=0 to aList.Count-1 do

if aCompare(aList.List[i],aItem) = 0 then

begin

Result:=i;

Break;

end;

end;

Последовательный поиск для отсортированного массива ничем не отличается от приведенного и имеет линейный порядок алгоритма O(n).

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

В методе сначала приближенно определяется запись в середине массива и анализируется значение ее ключа. Если оно слишком велико, то анализируется значение ключа, соответствующего записи в середине первой половины массива, и указанная процедура повторяется в этой половине до тех пор, пока не будет найдена требуемая запись. Если значение ключа слишком мало, испытывается ключ, соответствующий записи в середине второй половины массива, и процедура повторяется в этой половине.

Процесс продолжается до тех пор, пока не найден требуемый ключ или не станет пустым интервал, в котором осуществляется поиск. Чтобы найти элемент, в худшем случае требуется log₂(N) сравнений, что значительно лучше, чем при последовательном поиске. Программная иллюстрация бинарного поиска в упорядоченном массиве приведена ниже.

{ Двоичный поиск }

function BinarySearch(aList: TList;

aItem: Pointer; aCompare: TCompareFunc): Integer;

var L, R, M, CompareResult: Integer;

begin

{ Значения индексов первого и последнего элементов }

L:=0; R:=aList.Count-1;

while L <= R do

begin

{ Индекс среднего элемента }

M:=(L + R) div 2;

{ Сравнить значение среднего элемента с искомым }

CompareResult:=aCompare(aList.List[M], aItem);

{ Если значение среднего элемента меньше искомого -

переместить левый индекс на позицию до среднего индекса }

if CompareResult < 0 then

L:=M+1 else

{ Если значение среднего элемента больше искомого -

переместить правый индекс на позицию после среднего индекса }

if CompareResult > 0 then

R:=M-1 else

begin

Result:=M;

Exit;

end;

end;

Result:=-1;

end;

2. Реляционная модель данных. Базовые понятия. Отношения и свойства отношений. Составляющие реляционной модели данных.

Реляционная база данных — база данных, основанная на реляционной модели. Слово «реляционный» происходит от английского «relation» (отношение[1]). Для работы с реляционными БД применяют Реляционные СУБД.

Теория реляционных баз данных была разработана доктором Коддом из компании IBM в 1970 году. В реляционных базах данных все данные представлены в виде простых таблиц, разбитых на строки и столбцы, на пересечении которых расположены данные. Запросы к таким таблицам возвращают таблицы, которые сами могут становиться предметом дальнейших запросов. Каждая база данных может включать несколько таблиц. Кратко особенности реляционной базы данных можно сформулировать следующим образом:

• Данные хранятся в таблицах, состоящих из столбцов ("атрибутов") и строк ("записей");

• На пересечении каждого столбца и строчки стоит в точности одно значение;

• У каждого столбца есть своё имя, которое служит его названием, и все значения в одном столбце имеют один тип.

• Запросы к базе данных возвращают результат в виде таблиц, которые тоже могут выступать как объект запросов.

Строки в реляционной базе данных неупорядочены - упорядочивание производится в момент формирования ответа на запрос.

Общепринятым стандартом языка работы с реляционными базами данных является язык SQL.

Существуют определенные правила, которые должны соблюдаться при создании базы данных. Пользователь должен пройти следующие этапы, которые называют "нормализацией":

• удалить повторяющиеся группы атрибутов. Группой считаются два и более атрибута, их необходимо вынести в отдельную таблицу.

• удалить неключевые атрибуты и те, которые не имеют отношения к первичному ключу или относятся только к части первичного ключа. Если первичный ключ составной, то любой атрибут таблицы должен быть связан с обоими частями ключа.

• описать каждую таблицу: каждому атрибуту дать имя и указать вид информации, который используется в таблице (числовой, дата, денежный и т.п.). Название атрибута должно быть уникальным в рамках одной таблицы, обычно названия пишут латинскими буквами без пробелов.

• работа с пользовательским интерфейсом, обозначение обязательных и необязательных для заполнения полей.

• забота о безопасности, если это необходимо: шифрование данных, ограничение прав доступа.

3. Информация о студенте включает: ФИО, порядковый номер, название факультета, номер специальности, дату рождения, адрес проживания, телефон. Информация о студентах хранится в виде записей в массиве. Число записей в массиве 100. Отсортировать всех студентов в алфавитном порядке. Обосновать выбор алгоритма сортировки.

Билет 16.

1. Предваренная, скулемовская и клазуальная формы. Логическое следование. Унификация. Алгоритм унификации. Исчисление метода резолюций.

Предваренная нормальная форма

Для облегчения анализа сложных суждений формулы алгебры предикатов рекомендуется приводить к нормальной форме. Если в алгебре высказываний приняты две нормальные формы (ДНФ - дизъюнктивная и КНФ -конъюнктивная), то в алгебре предикатов - одна предваренная нормальная форма (ПНФ), суть которой сводится к разделению формулы на две части: кванторную и безкванторную. Для этого все кванторы формулы выносят влево, используя законы и правила алгебры предикатов.

В результате этих алгебраических преобразова­ний может быть получена формула вида: _x1 _x2 _xn(M), где {; } , а М – матрица формулы. Кванторную часть формулы _x1 _x2 _xn иногда называют префиксом ПНФ.

В последующем матрицу форму­лы преобразуют к виду КНФ, что облегчает механизм по принципу резолюции.

Сколемовская стандартная форма

Наличие разноимен­ных кванторов усложняет вывод заключения. Поэтому рассмотрим класс формул, содержащих только кванторы всеобщности. Фор­мула F называется  - формулой, если она представлена в ПНФ и содержит только кванторы всеобщности, т.е.

F = _x1_x2 _xn (M).

Для устранения кванторов существования из префикса формулы разработан алгоритм Сколема, вводящий сколемовскую функцию для связывания предметной переменной квантора существования с другими предметными переменными.

Принцип резолюции

Существует эффективный алгоритм логического вывода - алгоритм резолюции. Этот алгоритм основан на том, что выводимость формулы В из множества посылок F₁; F₂; F₃; . . . F_n равносильна доказательству теоремы

(F₁F₂F₃. . .F_nB),

формулу которой можно преобразовать так:

(F₁F₂F₃. . .F_nB) =

((F₁F₂F₃. . .F_n)B) =

(F₁F₂F₃. . .F_n( F₂ B)).

Следовательно, заключение В истинно тогда и только тогда, когда формула (F₁F₂F₃...F_n(B))=л. Это возможно при значении “л” хотя бы одной из подформул F_i илиB.

Для анализа этой формулы все подформулы F_i иB должны быть приведены в конъюнктивную нормальную форму и сформировано множество дизъюнктов, на которые распадаются все подформулы. Два дизъюнкта этого множества, содержащие пропозициональные переменные с противоположными знаками (контрарные атомы) формируют третий дизъюнкт - резольвенту, в которой будут исключены контрарные пропозициональные переменные. Неоднократно применяя это правило к множеству дизъюнктов и резольвент, стремятся получить пустой дизъюнкт. Наличие пустого дизъюнкта свидетельствует о выполнении условия F₁F₂F₃...F_nB=л.

Нормальные формы формул

В алгебре высказываний используют две нормальные фор­мы: дизъюнктивную и конъюнктивную нормальные формы формулы (ДНФ и КНФ).

ДНФ формулы есть формула, равносильная формуле исходной логической функции и записанная в виде дизъюнкции элементарных конъюнкций, построенных на пропозициональных переменных, т.е.

F = K₁ K₂ K₃ . . ., где K_i = ( ABC . . .).

В элементарной коньюнкции нет двух одинаковых пропозициональных переменных, т.к. по закону идемпотентности FF=F. В ДНФ нет двух одинаковых элементарных коньюнкций, т.к. по закону идемпотентности FF=F. Если одна из элементарных коньюнкций содержит F и F, то элементарную коньюнкцию следует удалить, т.к. FF=л.

КНФ формулы есть формула, равносильная формуле исходной логической функции и записанная в виде конъюнкции элементарных дизъюнкций, построенных на пропозициональных переменных, т.е.

F = D₁ D₂ D₃ . . . , где D_i = ( ABC . . . ).

В элементарной дизьюнкции нет двух одинаковых пропозициональных переменных, т.к. по закону идемпотентности FF=F. В КНФ нет двух одинаковых элементарных дизьюнкций, т.к. по закону идемпотентности FF=F. Если одна из элементарных дизьюнкций содержит F и F, то следует удалить, т.к. FF = и.

2. Структура внешнего описания ПС. Качество ПО. Критерии и примитивы качества.

Программа или логически связанная совокупность программ на носителях данных, снабженная программной документацией, называется программным средством (ПС). Программа позволяет осуществлять некоторую автоматическую обработку данных на компьютере. Программная документация позволяет понять, какие функции выполняет та или иная программа ПС, как подготовить исходные данные и запустить требуемую программу в процесс ее выполнения, а также: что означают получаемые результаты. Кроме того, программная документация помогает разобраться в самой программе, что необходимо, например, при ее модификации.