Характеристики Простейших Сортировок

Сортировка Вставкой

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

type
Index = 0..n;
var
a: array[1..n] of elem;
procedure Insert;
var i, j: index;
x: elem;
begin
for i: = 1 to n do
begin
x: = a[i]; a[0]: = x; j: = i-1;
while x.key < a[j].key do
begin
a[j+1]: = a[j]; j: = j-1;
end;
a[j+1]: = x;
end;
end;

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

Пузырьковая Сортировка

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

procedure bubble;
var i, j, t: byte;
begin
for i: =2 to N do
for j: =N down to i do
if x[i-1]> x[j] then
begin t: =x[j-1]; x[j-1]: =x[j]; x[j]: =t; end;
end;
end;

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

Характеристики Простейших Сортировок

Свойство 1 Сортировка выбором использует около N2/2 сравнений и N обменов.

Свойство 2 Сортировка вставкой использует около N2/4 сравнений и N2/8 обменов в среднем, и в два раза больше в наихудшем случае.

Свойство 3 Пузырьковая сортировка использует около N2/2 сравнений и N2/2 обменов в среднем и наихудшем случаях.

Свойство 4 Сортировка вставкой линейна для " почти сортированных" файлов.

Свойство 5 Сортировка выбором линейна для файлов с большими записями и маленькими ключами.

13.Логические основы компьютера. Логические функции.

Компьютер работает на электричестве, т.е. логические элементы компьютера оперируют с сигналами, представляющими собой электрические импульсы. Есть импульс – логический смысл сигнала – 1, нет импульса – 0. На входы логического элемента поступают
сигналы-значения аргументов, на выходе появляется сигнал-значение функции.

Преобразование сигнала логическим элементом является таблицей состояния, которая фактически является таблицей истинности, соответствующей логической функции.

Базовые логические элементы реализуют рассмотренные выше три основные логические операции:
• логический элемент «И» - логическое умножение;
• логический элемент «ИЛИ» - логическое сложение;
• логический элемент «НЕ» - инверсию.
Поскольку любая логическая операция может быть представлена в виде комбинаций трех основных, любые устройства компьютера, производящие обработку или хранение информации, могут быть собраны из базовых логических элементов, как из «кирпичиков».

14.Алгебра логики (основные схемы).

1.Элемент НЕ(инверсия)

2.Дизьюнкция(ИЛИ)

3.Коньюкция(И)

4.Исключаюшие или

Для 2 и 3 возможно 2 и более входов, также возможны комбинации 1-2, 1-3, 1-4.

15.Триггер. Сумматор.

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

Самый распространённый тип триггера — так называемый RS-триггер (S и R, соответственно, от английских set — установка, и reset — сброс).

Сумматор — это электронная логическая схема, выполняющая суммирование двоичных чисел.

Многоразрядный двоичный сумматор, предназначенный для сложения многоразрядных двоичных чисел, представляет собой комбинацию одноразрядных сумматоров, с рассмотрения которых мы и начнём. Условное обозначение одноразрядного сумматора на рис. 5.8.

Рис. 5.8

При сложении чисел A и B в одном i -ом разряде приходится иметь дело с тремя цифрами:

1. цифра a _i первого слагаемого;

2. цифра b _i второго слагаемого;

3. перенос p _i–1 из младшего разряда.

В результате сложения получаются две цифры:

1. цифра c _i для суммы;

2. перенос p _i из данного разряда в старший.

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

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

16.Законы алгебры логики.

Зк. Однородности элементов.

Х+0=Х Х+1=1 Х*0=0 Х*1=Х

Зк. Отрицания.

Зк. Дополнительности.

Зк. Двойственности.

Комбинационные законы:

Тавтология Х+Х=Х Х*Х=Х

Коммутативные или переместительные Х₁+Х₂=Х₂+Х₁ Х₁*Х₂=Х₂*Х₁

Сочетательные (Х₁+Х₂)+Х₃=Х₁+(Х₂+Х₃) (Х₁*Х₂)*Х₃=Х₁*(Х₂*Х₃)

Распределительный Х₁*(Х₂+Х₃)=Х₁*Х₂+ Х₁*Х₃ Х₁+Х₂+Х₂=(Х₁+Х₂)*(Х₁+Х₃)

Поглощение Х₁+Х₁*Х₂=Х₁ Х₁*(Х₁+Х₂)=Х₁

Склеивание

Зк. Де Моргана

17.Упрощения логических формул.

Зк. Однородности элементов.

Х+0=Х Х+1=1 Х*0=0 Х*1=Х

Зк. Отрицания.

Зк. Дополнительности.

Зк. Двойственности.

Комбинационные законы:

Тавтология Х+Х=Х Х*Х=Х

Коммутативные или переместительные Х₁+Х₂=Х₂+Х₁ Х₁*Х₂=Х₂*Х₁

Сочетательные (Х₁+Х₂)+Х₃=Х₁+(Х₂+Х₃) (Х₁*Х₂)*Х₃=Х₁*(Х₂*Х₃)

Распределительный Х₁*(Х₂+Х₃)=Х₁*Х₂+ Х₁*Х₃ Х₁+Х₂+Х₂=(Х₁+Х₂)*(Х₁+Х₃)

Поглощение Х₁+Х₁*Х₂=Х₁ Х₁*(Х₁+Х₂)=Х₁

Склеивание

Зк. Де Моргана

18.Вычислительные сети.

Электронно-вычислительная сеть (или просто компьютерная сеть) – это совместное подключение нескольких отдельных компьютеров к единому каналу передачи данных.

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

Рассмотрим основные понятия, которые используются в вычислительных сетях.

Клиент – компьютер, подключенный к вычислительной сети.

Сервер (server) – компьютер, предоставляющий свои ресурсы клиентам сети. Различают следующие виды серверов:

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

Ø сервер баз данных обеспечивает доступ клиентам к общим базам данных;

Ø сервер приложений служит для предоставления пользователям прикладных программ;

Ø сервер печати обеспечивает печать на общем печатном устройстве со всех рабочих мест;

Ø Web-сервер обеспечивает предоставление информации через сеть Internet;

Ø почтовый сервер обеспечивает циркуляцию электронной почты, как внутри организации, так и во внешней сети.

Среда - способ соединения компьютеров.

Ресурсы – диски, файлы, принтеры, модемы и другие элементы, используемые при работе в сети.

В зависимости от размера все электронно-вычислительные сети делятся на:

1. Локальные вычислительные сети (ЛВС), абоненты которых сосредоточены на расстоянии 10 - 15 км. Такие сети объединяют компьютеры, размещенные внутри одного здания или в нескольких рядом расположенных зданиях.

2. Региональные сети, абоненты которых сосредоточены на расстоянии 10 - 100 км. К таким сетям относятся районные, городские и областные сети.

3. Глобальные сети, сосредоточенные на расстоянии 1000 и более километров. К таким сетям относятся сети, объединяющие города, области, районы, страны. Наиболее известные среди них - Internet, Fido, Sprint, Relcom.

Во многих организациях, в которых эксплуатируются персональные компьютеры, создаются локальные вычислительные сети. Это делается потому, что ЛВС предоставляет ряд значительных преимуществ, по сравнению с использованием отдельных компьютеров. Рассмотрим эти преимущества.

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

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

Разделение программных средств - позволяет пользователям использовать программы, установленные на других компьютерах.

19. Назначение вычислительных сетей.

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

20. Основные характеристики ВС.

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