Сортировка данных и реализация быстрого поиска в уже отсортированном массиве

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

Методы, разрабатываемые дискретной математикой, часто используются в различных направлениях информатики. Так, теоретическая информатика (или теоретическая кибернетика) использует математические методы для построения и изучения моделей обработки, передачи и использования информации. Объекты ее изучения — дискретные множества. Теоретическая информатика является как поставщиком задач, так и потребителем методов дискретной математики.

Достижения математической логики используются для анализа процессов переработки информации с помощью ЭВМ.

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

Теория информации изучает вид тех форм, в которых информация представляется в компьютере. Формализация любой информации, реально существующей в живой и неживой природе, происходит через компьютерное моделирование.

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

Все вышеперечисленное объясняет актуальность изучения тематики данной курсовой работы.

1. Законы алгебры Буля и их применение для преобразования логических выражений

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

Алгебра логики (алгебра высказываний) — раздел математической логики, в котором изучаются логические операции над высказываниями. Чаще всего предполагается (т. н. бинарная или двоичная логика, в отличие от, например, троичной логики), что высказывания могут быть только истинными или ложными.

Базовыми элементами, которыми оперирует алгебра логики, являются высказывания. Высказыванием является повествовательное предложение, которое формализуетнекоторое выражениемысли. Это утверждение, которому всегда можно поставить в соответствие одно из двух логических значений: ложь (0, ложно, false) или истина (1, истинно, true). Логическое высказывание принято обозначать заглавными латинскими буквами.

Таблица истинности — это таблица, описывающая логическую функцию (см. таблицу 1).

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

Таблица 1 Таблица истинности

Понятие множества обычно принимается за одно из исходных (аксиоматических) понятий, то есть не сводимое к другим понятиям, а значит и не имеющее определения. Однако тяжело оперировать объектом, не имеющим определения. Одно из простых и понятных абстрактных определений дал Бертран Рассел — «Множество есть совокупность различных элементов, мыслимая как единое целое». Множество может быть замкнутым и незамкнутым, полным и пустым, упорядоченным и неупорядоченным, счётным и несчётным, конечным и бесконечным. Более того, как в наивной, так и в формальной теориях множеств любой объект обычно считается множеством.

Операция — отображение, ставящее в соответствие одному или нескольким элементам множества (аргументам) другой элемент (значение). Термин «операция» как правило, применяется к арифметическим или логическим действиям, в отличие от термина «оператор», который чаще применяется к некоторым отображением множества на себя, имеющим замечательные свойства. В работе будут рассмотрены унарные и бинарные операции.

Унарной операцией или одноместной операцией на множестве M называется отображение множества в себя, которое каждому элементу множества M, называемому операндом, ставит в соответствие некоторый элемент того же множества, называемый результатом.

Высказывания строятся над множеством {B,, ,, 0, 1}, где B — непустое множество, над элементами которого определены три операции:

— - отрицание — унарная операция над суждениями, результатом которой является суждение (в известном смысле) «противоположное» исходному. Обозначается знаком перед или чертой над суждением. Синоним: логическое «НЕ» .

— - конъюнкция — (от лат. conjunctio союз, связь) — логическая операция, по своему применению максимально приближённая к союзу «и». Синонимы: логическое «И», логическое умножение, иногда просто «И». Конъюнкция может быть бинарной операцией, то есть, иметь два операнда, тернарной операцией, т. е. иметь три операнда или n-арной операцией, т. е. иметь n операндов.

— - дизъюнкция -(лат. disjunctio — разобщение) логическая операция, по своему применению максимально приближённая к союзу «или» в смысле «или то, или это, или оба сразу». Синонимы: логическое «ИЛИ», включающее «ИЛИ», логическое сложение, иногда просто «ИЛИ».

— константы — логический ноль 0 и логическая единица 1.

Дизъюнкт — пропозициональная формула, являющаяся дизъюнкцией одного или более литералов (например).

Конъюнкт — пропозициональная формула, являющаяся конъюнкцией одного или более литералов (например).

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

Булевой алгебройназывается непустое множествоA с двумя бинарными операциями,, унарной операцией и двумя выделенными элементами: 0и 1такими, что для всех a, b и c из множества A верны следующие аксиомы:

— Ассоциативность — (от лат. associatio— соединение) — свойство любой операции, такое, что для неё выполняется равенство: для любых элементов. Например, для умножения:

.

В булевой алгебре:

— Коммутативность — (от позднелат. commutativus — «меняющийся»), свойство переместительностибинарной операции, такое, что для нее выполняется равенство:

для любых элементов .

— Законы поглощения.

— Дистрибутивность — (от лат. distributivus — «распределительный»), также распределительность — свойство согласованности двух бинарных операций, определённых на одном и том же множестве. Говорят, что две бинарные операции + и Ч удовлетворяют свойству дистрибутивности, если для любых трех элементов :

 — дистрибутивность слева;

 — дистрибутивность справа.

Если операция Ч является коммутативной, то свойства дистрибутивности слева и справа совпадают.

— Дополнительность.

В математических обозначениях эти аксиомы записываются так:

Первые три аксиомы означают, что (A, ,) является решёткой.

Решётка, структура — частично упорядоченное множество, в котором каждое двухэлементное подмножество имеет как точную верхнюю (sup), так и точную нижнюю (inf) грани. Отсюда вытекает существование этих граней для любых непустых конечных подмножеств.

Дистрибутивная решётка — решетка, в которой справедливо тождество

(a + b)c = ac + bc

равносильное тождествам

ab + c = (a + c)(b + c)

и

(a + b)(a + c)(b + c) = ab + ac + bc

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

а также и

где J(i) — конечные множества, а Ц — множество всех однозначных функций ?, ставящих в соответствие элементу i из I элемент ?(i) из J(i). В полной дистрибутивной решётке указанные равенства имеют смысл и в случае бесконечных множеств I и J(i). Однако справедливы они не всегда. Полные дистрибутивные решётки, удовлетворяющие последним двум тождествам для любых множеств I и J(i), называются вполне дистрибутивными.

Таким образом, булева алгебра может быть определена как дистрибутивная решётка, в которой выполнены две последние аксиомы. Структура, в которой выполняются все аксиомы, кроме предпоследней, называется псевдобулевой алгеброй.

1.1 Свойства и тождества булевой алгебры

Из аксиом видно, что наименьшим элементом является 0, наибольшим является 1, а дополнение a любого элемента a однозначно определено. Для всех a и b из A верны также следующие равенства:

;

;

;

;

;

;

;; дополнение 0 есть 1 и наоборот.

Законами или правилами де Моргана называются логические правила, связывающие пары дуальных логических операторов при помощи логического отрицания.

Огастес де Морган первоначально заметил, что в классической пропозициональной логике справедливы следующие соотношения:

not (P and Q) = (not P) or (not Q)

not (P or Q) = (not P) and (not Q)

Обычная запись этих законов в формальной логике:

или

в теории множеств:

или:

Если существует операция логического умножения двух и более элементов, операция «и» —(A&B), то для того, чтобы найти обратное от всего суждения ~(A&B), необходимо найти обратное от каждого элемента и объединить их операцией логического сложения, операцией «или» — (~A+~B). Закон работает аналогично в обратном направлении: ~(A+B) = (~A&~B).

Применительно к нашим основным обозначениям:

; .

Инволюция — преобразование, которое является обратным самому себе. Если P(a) — инволюция, то

1. ;

2. ;

3. .

В связи с этим свойством: .

Правило Блейка-Порецкого:

; .

Идемпотентность означает свойство математического объекта, которое проявляется в том, что повторное действие над объектом не изменяет его:

; .

Правило склеивания:

; .

Принцип двойственности

В булевых алгебрах существуют двойственные утверждения, они либо одновременно верны, либо одновременно неверны. Именно, если в формуле, которая верна в некоторой булевой алгебре, поменять все конъюнкции на дизъюнкции, 0 на 1,? на? и наоборот, то получится формула, также истинная в этой булевой алгебре. Это следует из симметричности аксиом относительно таких замен.

1.2 Решение логических задач

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

Пример

Условие задачи

В школе-новостройке в каждой из двух аудиторий может находиться либо кабинет информатики, либо кабинет физики. На дверях аудиторий повесили шутливые таблички. На первой повесили табличку «По крайней мере, в одной из этих аудиторий размешается кабинет информатики», а на второй аудитории — табличку с надписью «Кабинет физики находится в другой аудитории». Проверяющему, который пришел в школу, известно только, что надписи на табличках либо обе истинны, либо обе ложны. Помогите проверяющему найти кабинет информатики.

Решение задачи логический реляционный поиск сортировка

Переведем условие задачи на язык логики высказываний. Так как в каждой из аудиторий может находиться кабинет информатики, то пусть: А = «В первой аудитории находится кабинет информатики»; B = «Во второй аудитории находится кабинет информатики».

Отрицания этих высказываний:

А= «В первой аудитории находится кабинет физики»; В = «Во второй аудитории находится кабинет физики».

Высказывание, содержащееся на табличке на двери первой аудитории, соответствует логическому выражению:

X = АВ

Высказывание, содержащееся на табличке на двери второй аудитории, соответствует логическому выражению:

У = А

Содержащееся в условии задачи утверждение о том, что надписи на табличках либо одновременно истинные, либо одновременно ложные в соответствии с законом исключенного третьего записывается следующим образом:

(X Y) (X Y) = 1.

Подставим вместо X и У соответствующие формулы:

(X Y) (X Y) = ((А В) А) ((А В) А)

Упростим сначала первое слагаемое. Всоответствии с законом дистрибутивности умножения относительно сложения:

(А В) А = А, А В А

В соответствии с законом непротиворечия:

А, А В, А = 0 В А

Упростим теперь второе слагаемое. В соответствии с первым законом де Моргана и законом двойного отрицания:

(А В) А=АВА = ААВ

В соответствии с законом непротиворечия:

ААВ=0В= 0

В результате получаем:

(0 В А) 0 = В А

Полученное логическое выражение оказалось простым и поэтому его можно проанализировать без построения таблицы истинности. Для того чтобы выполнялось равенство ВА = 1, В и, А должны быть равны 1, то есть соответствующие им высказывания истинны.

Ответ: В первой аудитории находится кабинет физики, а во второй — кабинет информатики.

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

2. Практическая часть

2.1 Общая характеристика задачи

В предметной области «Изготовление деталей» ведется учет выработки продукции рабочими механического цеха. Для изготовления одной детали необходимо произвести несколько операций на разных видах оборудования. Расценка за выполнение одной и той же операции для разных деталей разная. Рабочий может выполнять несколько разных операций на протяжении одного рабочего дня.

Образцы справочных, нормативных и оперативных документов, используемых в предметной области, приведены ниже в таблицах.

Таблица 2.1 Штатное расписание

Таблица 2.2 Справочник деталей

Таблица 2.3 Расценки

Таблица 2.4 Выработка

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

а) выдать список ФИО рабочих, профессия которых — фрезеровщик;

б) выдать ФИО рабочих, которые обрабатывали деталь «цилиндр» в феврале текущего года;

в) увеличить расценку за выполнение операции с кодом 20 для детали 013 на 30%.

2.2 Расчет информационной емкости документов предметной области

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

В таблицах2.5 — 2.8 приведены номера реквизитов и их максимально допустимая длина.

Таблица 2.5 Штатное расписание

Таблица 2.6 Справочник деталей

Таблица 2.7 Расценки

Таблица 2.8 Выработка

По формуле:

где

q_ij— количество символов в j-ом реквизите i-ого документа,

k_i — число строк в i-ом документе,

m — количество реквизитов в документе,

n — количество рассматриваемых документов.

определим среднюю информационную емкость приведенных в варианте документов (среднее количество символов в документе) по формуле: 2219 / 4 = 554,75.

2.3 Построениеинфологической, реляционной и даталогической моделей предметной области

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

Построим инфологическую модель предметной области в виде IDEF1Xдиаграммы (рис. 2.1).

В таблице 2.9 приведена структура входящих в инфологическую модель предметной области атрибутов.

Рисунок 2.1 — Инфологическая модель предметной области

Таблица 2.9 Описание структуры атрибутов

Свойства отношений между объектами описаны в таблице 2.10

Таблица 2.10 Свойства между объектами предметной области

Полученную инфологическую модель предметной области представим в виде совокупности схем отношений реляционной модели данных с указанием ключевых атрибутов.

ШТАТНОЕ РАСПИСАНИЕ: (Табельный номер, Номер цеха, Номер участка, ФИО рабочего, Профессия)

ВЫРАБОТКА: (ФИО рабочего, Название детали, Название операции, Количество сделанных деталей)

РАСЦЕНКИ: (Код детали, Код операции, Название операции, Расценка)

СПРАВОЧНИК ДЕТАЛЕЙ: (Код детали, Название детали)

Для реляционной инфологической модели базы данных построим даталогическую модель базы данных в виде взаимосвязанных файлов (рис. 2.2).

Рисунок 2.2 — Даталогическая модель предметной области

В соответствии с даталогической моделью базы данных сформируем таблицы реляционной базы данных и заполним их данными в соответствии с заданием (таблицы 2.11 — 2.14).

Таблица 2.11 Штатное расписание

Таблица 2.12 Справочник деталей

Таблица 2.13 Расценки

Таблица 2.14 Выработка

2.4 Формирование информационных запросов к реляционной базе данных с помощью операций реляционной алгебры

Запрос 1

Текст запроса: выдать список ФИО рабочих, профессия которых — фрезеровщик.

Запрос:

selectФИО

fromШтатное_расписание

whereПрофессия= `Фрезеровщик'

Запрос 2

Текст запроса: выдать ФИО рабочих, которые обрабатывали деталь «цилиндр» в феврале текущего года.

SelectФИО

FromВыработка

WhereНазвание_детали = `Цилиндр'andMonth (Дата)=2

Запрос 3

Текст запроса: увеличить расценку за выполнение операции с кодом 20 для детали 013 на 30%.

UpdateРасценки

SetРасценка=Расценка * 1,3

WhereКод_операции = 20and

Название_детали =

(SelectНазвание_детали

FromСправочник_деталей

WhereКод_детали = 13)

2.5 Применение методов поиска и сортировки данных

Таблица 2.15 Массив кодов товаров

Задан массив кодов деталей (таблица 2.15). Отсортировать массив следующими методами сортировки: пузырька, турниров, деревьев сравнений. Рассмотрим процесс сортировки исходного массива методом пузырька. Промежуточные проходы и окончательный результат приведены в таблице 2.16.

Таблица 2.16 Сортировка методом пузырька

Тот же массив исходных данных отсортируем методом турниров. Построим дерево сортировки. Промежуточные проходы и окончательный результат приведены на рисунке2.3(а-к).

а) б)

в) г)

д) е)

ж) з)

и) к)

Рисунок 2.3 — Турнирная сортировка

Тот же массив исходных данных отсортируем с помощью дерева сравнений. Построенное дерево сравнений и полученный с помощью обхода бинарного дерева симметричным методом упорядоченный массив приведены на рисунке 2.4.

Рисунок 2.4 — Отсортированное бинарное дерево Для каждого метода сортировки посчитаем число выполняемых операций сравнения и заполним таблицу 2.17.

(log₂ 10 = 3.321 928 094 887 362? 3,32)

Таблица 2.17 Число операций сравнения во время сортировок

Из результатов таблицы 2.17 можно сделать вывод о предпочтительности метода сортировки с помощью дерева сравнений.

В отсортированном массиве произведем поиск элемента 26 914 методами простого перебора, двоичного (дихотомического) поиска и деревьев сравнений. Подсчитаем число операций сравнения, выполненных в процессе поиска, и заполним таблицу 2.18.

Таблица 2.18 Число операций сравнения во время поиска

Для полученной отсортированной последовательности наиболее эффективным методом алгоритма поиска является метод деревьев сравнений.

Заключение

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

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

Для создания моделей и диаграмм были освоены и использованы пакетыDiaи AllFusionErwinDataModeler.

Для создания тестовой базы данных и проверки выполнения SQL-запросов использовалась СУБД MicrosoftAccess.

Пояснительная записка была создана в текстовом процессоре пакета MicrosoftOffice — Word.

1. Иванов Б. Н. Дискретная математика. Алгоритмы и программы. Расширенный курс. М.: Известия, 2011, 512 с.

2. Когаловский М. Р. Энциклопедия технологий баз данных — М.: Финансы и статистика, 2002. — 800 с. — ISBN 5−279−2 276−4.

3. Коннолли Т., Бегг К. Базы данных. Проектирование, реализацияисопровождение. Теорияипрактика = Database Systems: A Practical Approach to Design, Implementation, and Management — 3-еизд. — М.: Вильямс, 2003. — 1436 с. — ISBN 0−201−70 857−4.

4. Кузнецов С. Д. Основы баз данных — 2-е изд. — М.: Интернет-Университет Информационных Технологий; БИНОМ. Лаборатория знаний, 2007. — 484 с. — ISBN 978−5-94 774−736−2.

5. Яшин В. Н. Информатика: аппаратные средства персонального компьютера. М.: ИНФРА-М, 2008.