Задание 4. 1. Для реквизита, указанного в варианте задания, выполнить сортировку (по возрастанию) заданной последовательности значений реквизита методами пузырька

1. Для реквизита, указанного в варианте задания, выполнить сортировку (по возрастанию) заданной последовательности значений реквизита методами пузырька, турниров, простых вставок, деревьев сравнений, слияния (метод Неймана). Конкретные методы сортировки указаны в варианте Задания 4.

В процессе применения методов подсчитать число выполняемых операций сравнения и заполнить таблицу следующего вида (n - длина сортируемой последовательности):

Метод	Tmax	Число выполненных сравнений S	Δ=Tmax-S
пузырька
турниров	(n-1)+(n-1)log2n
простых вставок
деревьев сравнений	n2
слияния	nlog2n

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

2. В полученной отсортированной последовательности значений реквизита выполнить поиск элемента, указанного в варианте задания в позиции № 6, используя методы простого перебора, двоичного (дихотомического) поиска и деревьев сравнений. При использовании деревьев сравнений, считается, что отсортированная последовательность хранится в виде дерева. Подсчитать число операций сравнения, выполненных в процессе поиска, и заполнить таблицу следующего вида (Т_ср – среднее число операций сравнения):

Метод	Тср	Число выполненных сравнений S
простого перебора
двоичного поиска
деревьев сравнений	1,39log2 n

На основе таблицы сделать вывод о сравнительной эффективности рассмотренных методов поиска.

5.2. Варианты предметных областей к заданиям 1 – 3

Вариант № 1.

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

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

Справочник поставщиков

Справочник товаров

Договора с поставщиками (фрагмент)

Журнал учета прихода товаров (фрагмент)

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

а) вывести информацию о ценах на товары, которые поступают от поставщика с кодом 544;

б) вывести перечень товаров, которые поставляются поставщиком, название которого «Эра»;

в) удалить из договора 1256 информацию о поставке товара с кодом 13260.

Вариант № 2.

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

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

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

Список продавцов

Справочник товаров в отделах

Журнал учета продажи товаров (фрагмент)

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

а) вывести список продавцов отдела 12;

б) определить, какие товары продавались в молочном отделе на конкретную (заданную) сумму;

в) ввести информацию о новом продавце отдела 12 (с конкретным ФИО), должность – продавец.

Вариант № 3.

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

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

Список автомобилей

Справочник автомобилей

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

Путевой лист (фрагмент)

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

а) предоставить информацию о грузоподъемности и нормах расхода топлива для автомобилей марки КАМАЗ;

б) предоставить информацию о расходах дизтоплива в феврале текущего года;

в) во вновь созданную таблицу АРХИВ перенести информацию о рейсах прошлого года.

Вариант № 4.

В предметной области «Покупки» ведется учет продажи товаров в магазине по заказам покупателей. На покупку каждого товара выбивается отдельный чек. Отделы магазина специализированы, т.е. каждый вид товара может продаваться только лишь в одном определенном отделе.

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

Справочник покупателей

Список отделов

Справочник товаров

Чек

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

а) сформулировать список товаров молочного отдела, цена которых находится в пределах от ____ до _____;

б) выдать информацию о покупателе, который 20 августа текущего года осуществил покупку товара «кофе растворимый» в количестве 1 кг;

в) для товаров с кодами 23440 и 23460 увеличить цену на 20 %.

Вариант № 5.

В предметной области «Хранение товара» ведется учет товаров, хранимых на складах фирмы. Каждый товар имеет ограниченный срок хранения.

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

Справочник складов

Справочник товаров

Карточка складского учета

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

а) вывести информацию о товарах, дата пригодности которых заканчивается в мае текущего года;

б) вывести название склада, на котором хранятся товары с названием, содержащем слово «кофе»;

в) удалить из БД информацию о хранении товаров с кодами 23440 и 23460.

Вариант № 6.

В предметной области «Оплата коммунальных услуг» ведется учет оплаты предоставленных населению коммунальных услуг. Учет ведется в пределах одного года, после чего информация переносится в архив. Для каждого плательщика открыт индивидуальный счет в Сбербанке для каждого вида оплачиваемой услуги. Оплату можно осуществить в любом филиале Сбербанка. Факт оплаты фиксируется в квитанции об оплате соответствующей услуги за указанный месяц.

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

Список филиалов Сбербанка

Справочник плательщиков

Список услуг

Квитанция об оплате услуги

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

а) предоставить информацию о клиентах, проживающих по ул. Зеленой;

б) вывести дату оплаты, а также адрес и телефон кассы, в которой клиент Шевчук Б.А. уплатил за газ за январь текущего года;

в) во вновь созданную таблицу АРХИВ перенести информацию об оплате электроэнергии за январь месяц текущего года.

Вариант № 7.

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

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

Справочник заказчиков

Список поставщиков

Справочник товаров

Журнал заказов

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

а) выдать информацию о цене товара с названием «Колбаса любительская»;

б) выдать информацию о всех заказах Климова Ю.В. в таком виде: дата заказа, название товара, количество заказанного товара, цена товара;

в) внести информацию о новом заказчике Ивахненко О.В. с номером 238, проживающем по ул. Лесной, 25 и имеющем номер счета 15147, авансовый платеж на счете составляет 30 тыс. руб.

Вариант № 8.

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

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

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

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

Расценки

Выработка

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

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

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

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

Вариант № 9.

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

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

Справочник библиотек

Библиотечный каталог

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

Читательский формуляр

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

а) выдать номера читательских билетов Иванова А.И.;

б) определить, какие книги брал Иванов А.И. в апреле – мае текущего года;

в) удалить из БД информацию о обслуживании читателей в библиотеке № 11 во II квартале предыдущего года.

Вариант № 10.

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

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

Справочник поставщиков

Заказ

Журнал учета выполнения заказов

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

а) выдать информацию о поставщиках из г. Калуги и Калужской области;

б) выдать информацию о выполнении заказов в феврале текущего года в виде: номер заказа, название поставщика, название товара, дата поставки, количество поставленного товара;

в) внести информацию о новом поставщике (данные выбрать самостоятельно).

Вариант № 11.

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

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

Классификатор товаров

Справочник поставщиков

Регистрационный журнал накладных

Накладная

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

а) определить название товара, код которого 15473, а код группы

товара – 07;

б) выдать информацию о приходе товара в марте текущего года в формате: название группы товара, название товара, название поставщика, количество товара;

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

Вариант № 12.

В предметной области «Учет кадров» обрабатывается информация о кадровом составе некоторого предприятия. Данные о каждом работнике фиксируются в личном листке по учету кадров, в которой также фиксируются данные о внутреннем перемещении работника на данном предприятии. Должностные оклады работников определяются штатным расписанием.

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

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

Личный листок по учету кадров (фрагмент)

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

а) выдать ФИО, даты рождения и домашние адреса работников, возраст которых меньше 18 лет (на текущую дату);

б) выдать список сотрудников в виде: название подразделения, ФИО, название должности, оклад, дата назначения на должность;

в) увеличить оклад должности «экономист» на 25 %.

Вариант № 13.

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

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

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

Справочник ставок таможенных платежей

Реестр таможенных деклараций

Таможенная декларация

Досмотровое предписание

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

а) вывести нормы таможенных платежей для товара «кофе»;

б) вывести информацию о таможенных платежах за товары, ввозимые с сопроводительным документом 1252 в виде: код товара, название товара, количество товара, стоимость товара;

в) во вновь создаваемую таблицу АРХИВ перенести информацию о таможенных платежах с сопроводительными документами прошлого года.

Вариант № 14

В предметной области «Грузоперевозки» осуществляется обработка информации о результатах работы водителей и автомобилей автопредприятия на основе данных, взятых из путевых листов и товаро – транспортных накладных (ТТН). За каждым автомобилем могут быть закреплены несколько водителей, однако каждый водитель работает только на одном автомобиле. На каждый день работы автомобиля выписывается отдельный путевой лист. К одному путевку листу могут прилагаться несколько ТТН (т.е. могут выполняться несколько рейсов в день). В одной ТТН может указываться только один вид перевозимого груза.

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

Список автомобилей

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

Путевой лист (фрагмент)

Товарно-транспортная накладная

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

а) найти ФИО водителей, оклад которых составляет больше 30 тыс. руб.;

б) выдать информацию о грузоперевозках водителями в феврале текущего года в виде: ФИО водителя, марка автомобиля, дата путевого листа, номер ТТН, название груза, масса груза, расстояние;

в) в ТТН с номером 612371 изменить количество мест груза на 100.

Вариант № 15.

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

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