Задания к контрольной работе

Задание № 1.

Компьютерные сети и технологии

1. Топологии компьютерных сетей, их преимущества и недостатки.

2. История создания глобальной компьютерной сети Интернет.

3. Протоколы сети Интернет.

4. Адресация и система доменных имен сети Интернет.

5. Программы для работы в сети.

Задание № 2

Системы управления базами данных

1.Функции реляционных баз данных.

2.Языки баз данных.

3.Типовая организация баз данных.

Задание № 3

Решить транспортную задачу методом потенциалов. Потребителям Б₁, Б₂, Б₃ и Б₄ требуется песок в количествах соответственно б₁, б₂, б₃ и б₄ тонн. На складах имеется следующее количество песка: А₁ - а₁ т, А₂ - а₂ т и А_{3т -} а₃ т. Требуемое и имеющееся количество песка приведено в таблице 4. Расстояния между поставщиками и получателями песка приведены в таблице 5. Необходимо составить план перевозок песка (план закрепления потребителей за поставщиками) так, чтобы при минимальной транспортной работе были удовлетворены запросы всех потребителей.

Требуемое и имеющееся количества песка Таблица 4

Рассмотрим процедуру вычислений на конкретном примере. Пусть потребителям Б₁, Б₂, Б₃ и Б₄ требуется песок в количествах соответственно 30, 70, 40 и 30 тонн. На складах имеется следующее количество песка: А₁ = 80 т, А₂ = 50 т и А₃ = 40 т. Расстояния между поставщиками и получателями песка приведены в таблице 6. Необходимо составить план перевозок песка (план закрепления потребителей за поставщиками) так, чтобы при минимальной транспортной работе были удовлетворены запросы всех потребителей.

Расстояние между поставщиками и потребителями Таблица 6

Очевидно, что транспортная работа будет минимальной, если доставлять песок каждому потребителю с ближайшего к нему склада. В таком случае решение было бы очевидным. Однако в рассматриваемой задаче это невозможно, так как для потребителей Б₁, Б₂ и Б₄ с суммарной потребностью в 130 т ближайшим является склад А₂, где имеется лишь 50 т песка. Поэтому для полного удовлетворения потребности этих потребителей неизбежны перевозки с других складов. При этом возможны различные варианты.

1. Составление матрицы условий.

2. Запишем условия задачи в форме матрицы (таблица 7).

Условия задачи Таблица 7

В правых верхних углах клеток, представляющих собой реальные маршруты перевозок, указаны расстояния между соответствующими пунктами. В процессе решения задачи в средней части этих клеток записывают значения Х_ij, которые делятся на основные и не основные. Не основные Х_ij в таблице-матрице не пишутся и считаются равными нулю. К основным относятся все Х_ij >0, а также те из Х_ij =0, которые записываются в матрице. Основные Х_ij записанные в матрице, обычно называют загрузками, а клетки, в которых они находятся, - занятыми. Клетки матрицы без загрузок называют незанятыми.

2. Составление допустимого исходного плана.

Решение задачи начинается с составления допустимого плана. Производится это способом минимального элемента по строке следующим образом. Сначала планируем перевозки с первого склада, записывая их в соответствующие клетки первой строки. Производим это следующим образом. Сначала полностью удовлетворяем потребность ближайшего потребителя Б₃, записав в клетку с наименьшим расстоянием 40 т. Поскольку в пункте Ai остается еще 40 т, удовлетворяем потребность следующего ближайшего потребителя Б₄, записав в соответствующую клетку нужные ему 30 т. Оставшиеся 10 т заносим в клетку А₁Б₁ и переходим к следующей строке матрицы. Теперь груз второго отправителя А₂ планируем к перевозке ближайшим из еще неудовлетворенных потребителей, записывая соответствующие объемы в клетки второй строки последовательно, начиная с клетки с наименьшим расстоянием:, в клетку А₂Б₁ - 20 т и в клетку А₂Б₂ - 30 т. Перейдя к третьей строке матрицы, видим, что остался неудовлетворенным только один потребитель Б₂. Планируем ему перевозку из А₃, записав в клетку А₃Б₂ 40 т. Вычисления закончены. Полученный допустимый план представлен в таблице 8. По этому плану перевозок потребность всех потребителей удовлетворяется полностью, а транспортная работа составит

Р = 10*9+40*5+30*8+20*4+30*9+40*22 = 1760 тонно-километров.

3. Проверка оптимальности плана производится с помощью индексов, которые рассчитывают прямо на матрице.

При этом индексы Ui, записывают в клетки вспомогательного столбца, а индексы Vj - в клетки вспомогательной строки (таблица 8). Для определения индексов используют следующие правила:

1) индекс первой клетки вспомогательного столбца всегда равен нулю (U₁ = 0);

2) для каждой занятой клетки матрицы сумма соответствующих ей индексов U и V (записанных против нее сверху и сбоку во вспомогательных клетках) равна расстоянию, указанному в данной клетке.

Из последнего правила следует, что если у занятой клетки один из индексов известен, то другой равен разности ее расстояния и известного индекса, т.е.

U_i = L_ij - V_j и V_j = L_ij - U_i

Запишем в матрицу индекс U₁ = 0.

Тогда у занятых клеток А₁Б₁, А₁Б₃ и А₁Б₄ один индекс известен и можно, используя равенство (1), определить индексы V₁, V₂ и V₄ (таблица 9):

Теперь у занятой клетки А₂Б₁ известен индекс V₁ и можно найти индекс U₂ = L₂₂ - U₂ = 4-9 = -5. После этого определяем индекс V₂, а затем индекс U₃:

V₂ = L₂₂ - U₂ = 9 - (-5) = 14 и U₃ = L₃₂ - V₂ = 22 - 14 = 8

Таким образом, все индексы найдены (таблица 9) и можно приступить к проверке плана, которая сводится к сравнению расстояния каждой незанятой клетки матрицы с суммой соответствующих ей индексов с целью выявления клеток, в которых расстояние меньше указанной суммы. В нашем примере имеем:

(U₁ + V₂ = 0 + 14) < (L₁₂ = 15)

(U₂ + V₃ = -5 + 5 = 0) < (L₂₃ = 6)

(U₂ + V₄ = -5 + 8 = 3) < (L₂₄ = 5)

(U₃ + V₁ = 8 + 9 =17) > (L₃₁ = 16)

(U₃ + V₃ = 8 + 5 = 13) > (L₃₃ =10)

(U₃ + V₄ = 8 + 8) < (L₃₄ = 18)

У незанятых клеток А₃Б₁ и А₃Б₃ расстояние меньше суммы их индексов. Следовательно, составленный план не является оптимальным.

4. Улучшение неоптимального плана. Выявленные на предыдущем этапе вычислений клетки А₃Б₁ и А₃Б₃ являются резервом улучшения плана и потому их называют потенциальными, а превышение суммы индексов над расстоянием - потенциалом.

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

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

Составив цепочку, помечают знаком «+» ее нечетные вершины (считая первой вершину в потенциальной клетке), а четные знаком «—». Наименьшая из четных загрузок определяет величину перемещаемой загрузки. Уменьшив на эту величину объемы перевозок, записанные в клетках со знаком минус, и увеличив на ту же величину объемы клеток со знаком плюс, получают новый вариант плана с меньшей транспортной работой.

В рассматриваемом примере построена цепочка для потенциальной клетки А₃Б₃ и расставлены знаки (таблица 10).

Наименьшая среди четных загрузок (отмеченных знаком минус) равна 20 (в клетке А₂Б₁). Уменьшив на 20 загрузки клеток А₁Б₃, А₂Б₁ и А₃Б₂ и увеличив также на 20 загрузки клеток А₃Б₃, А₁Б₁ и А₂Б₂, получим новый план, представ

ленный в таблице 11. По этому варианту плана транспортная работа составит 1700 тонно-километров, или на 60 тонно-километров меньше.

Построение возможных перемещений Таблица 10

Скорректированный план 1 Таблица 11

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

Из таблицы 11 видно, что план, как и предыдущий, не является оптимальным. Об этом говорит наличие в матрице потенциальной клетки А₁Б₂. Изменив уже известным способом загрузки в клетках, отмеченных вершинами вновь построенной цепочки, получаем новый план, представленный в таблице 12. Для его проверки на оптимальность приступаем к расчету индексов и убеждаемся, что все их определить не удается. Причиной этого является так называемое вырождение плана, т.е. уменьшение числа занятых клеток против необходимого. Дело в том, что все индексы могут быть найдены, и притом однозначно, только при строго определенном количестве занятых клеток, равном в общем случае m+n—1, где m—число пунктов отправления, n—число пунктов назначения. В нашей задаче m=3, n=4. Следовательно, для определения всех индексов нужно иметь в матрице 3+4—1=6 занятых клеток. В таблице их только пять, поэтому индексы U₃ V₃ не удается определить.

Скорректированный план 2 Таблица 12

Скорректированный план 3 Таблица 13

Вырождение матрицы так же, как и излишнее количество занятых клеток, нарушают нормальную процедуру вычислений и их нужно устранять. Избавиться от вырождения можно путем записи в одной из незанятых клеток матрицы перевозки объемом 0 тонн. В таблице 13 нулевую загрузку можно поставить в одну из клеток А₁Б₃, А₂Б₃, А₃Б₁, А₃Б₂ и А₃Б₄. Легко проверить, что только эти клетки, став занятыми нулевой загрузкой, позволят найти недостающие индексы U₃ и V₃.

Скорректированный план 4 Таблица14

Лучше всего поставить нулевую перевозку в клетку с меньшим расстоянием, т.е. в клетку А₁Б₃. Теперь определив недостающие индексы, убеждаемся, что последний план является оптимальным, поскольку у всех незанятых клеток матрицы расстояния больше суммы соответствующих им индексов (таблица 14). Транспортная работа по этому плану составит 1600 тонно- километров.

В случае если число занятых клеток в матрице больше, чем m+n—1, поступают следующим образом. В таблице 15 - семь занятых клеток вместо необходимых шести (m+n-1=3+4—1=6). Лишняя занятая клетка приводит к тому, что индексы определяются неоднозначно. В первом случае U₂=9—15 = -6, во втором U₂=6—5= 1.

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

Скорректированный план 5 Таблица 15

Скорректированный план 6 Таблица 16

Такая цепочка в матрице с числом занятых клеток более m+n -1 всегда имеется. На вершинах цепочки, начиная с клетки, имеющей наименьшую загрузку, расставляют попеременно знаки минус и плюс, после чего загрузки со знаком минус уменьшают, а со знаком плюс увеличивают на величину наименьшей из них. В результате число занятых клеток уменьшится не менее чем на одну. При необходимости данную процедуру повторяют столько раз, сколько это необходимо для получения m+n -1 занятых клеток.