Сортировка Вставкой
Сортировка вставкой - это метод который почти настолько же прост, что и сортировка выбором, но гораздо более гибкий. Этот метод часто используют при сортировке карт: берем один элемент и вставляем его в нужное место среди тех, что мы уже обработали (тем самым оставляя их отсортированными).
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=Х
Зк. Отрицания. 
Зк. Дополнительности. 
Зк. Двойственности.
Комбинационные законы:
Тавтология Х+Х=Х Х*Х=Х
Коммутативные или переместительные Х1+Х2=Х2+Х1 Х1*Х2=Х2*Х1
Сочетательные (Х1+Х2)+Х3=Х1+(Х2+Х3) (Х1*Х2)*Х3=Х1*(Х2*Х3)
Распределительный Х1*(Х2+Х3)=Х1*Х2+ Х1*Х3 Х1+Х2+Х2=(Х1+Х2)*(Х1+Х3)
Поглощение Х1+Х1*Х2=Х1 Х1*(Х1+Х2)=Х1
Склеивание 
Зк. Де Моргана
17.Упрощения логических формул.
Зк. Однородности элементов.
Х+0=Х Х+1=1 Х*0=0 Х*1=Х
Зк. Отрицания. 
Зк. Дополнительности. 
Зк. Двойственности.
Комбинационные законы:
Тавтология Х+Х=Х Х*Х=Х
Коммутативные или переместительные Х1+Х2=Х2+Х1 Х1*Х2=Х2*Х1
Сочетательные (Х1+Х2)+Х3=Х1+(Х2+Х3) (Х1*Х2)*Х3=Х1*(Х2*Х3)
Распределительный Х1*(Х2+Х3)=Х1*Х2+ Х1*Х3 Х1+Х2+Х2=(Х1+Х2)*(Х1+Х3)
Поглощение Х1+Х1*Х2=Х1 Х1*(Х1+Х2)=Х1
Склеивание 
Зк. Де Моргана
18.Вычислительные сети.
Электронно-вычислительная сеть (или просто компьютерная сеть) – это совместное подключение нескольких отдельных компьютеров к единому каналу передачи данных.
Основное назначение вычислительной сети состоит в совместном использовании ресурсов и осуществление быстрой связи как внутри организации, так и за ее пределами.
Рассмотрим основные понятия, которые используются в вычислительных сетях.
Клиент – компьютер, подключенный к вычислительной сети.
Сервер (server) – компьютер, предоставляющий свои ресурсы клиентам сети. Различают следующие виды серверов:
Ø файловый сервер предназначен для хранения и предоставления файлов, с которыми работают пользователи;
Ø сервер баз данных обеспечивает доступ клиентам к общим базам данных;
Ø сервер приложений служит для предоставления пользователям прикладных программ;
Ø сервер печати обеспечивает печать на общем печатном устройстве со всех рабочих мест;
Ø Web-сервер обеспечивает предоставление информации через сеть Internet;
Ø почтовый сервер обеспечивает циркуляцию электронной почты, как внутри организации, так и во внешней сети.
Среда - способ соединения компьютеров.
Ресурсы – диски, файлы, принтеры, модемы и другие элементы, используемые при работе в сети.
В зависимости от размера все электронно-вычислительные сети делятся на:
1. Локальные вычислительные сети (ЛВС), абоненты которых сосредоточены на расстоянии 10 - 15 км. Такие сети объединяют компьютеры, размещенные внутри одного здания или в нескольких рядом расположенных зданиях.
2. Региональные сети, абоненты которых сосредоточены на расстоянии 10 - 100 км. К таким сетям относятся районные, городские и областные сети.
3. Глобальные сети, сосредоточенные на расстоянии 1000 и более километров. К таким сетям относятся сети, объединяющие города, области, районы, страны. Наиболее известные среди них - Internet, Fido, Sprint, Relcom.
Во многих организациях, в которых эксплуатируются персональные компьютеры, создаются локальные вычислительные сети. Это делается потому, что ЛВС предоставляет ряд значительных преимуществ, по сравнению с использованием отдельных компьютеров. Рассмотрим эти преимущества.
Разделение ресурсов – позволяет экономно использовать ресурсы в информационной системе. Например, производить печать со всех компьютеров на одном принтере, использовать один дисковод DVD и т.д.
Разделение данных – позволяет иметь доступ с разных рабочих мест к файлам, которые расположены на других компьютерах. Благодаря разделению данных можно организовать работу нескольких пользователей по созданию общего документа.
Разделение программных средств - позволяет пользователям использовать программы, установленные на других компьютерах.
19. Назначение вычислительных сетей.
Основное назначение вычислительной сети состоит в совместном использовании ресурсов и осуществление быстрой связи как внутри организации, так и за ее пределами.
20. Основные характеристики ВС.
Вжнейшие показатели работы сети: производительность, надежность и безопасность, расширяемость и масштабируемость, прозрачность, поддержка разных видов трафика, характеристики качества обслуживания, управляемость и совместимость.
-Производительность
Потенциально высокая производительность -- это одно из основных преимуществ распределенных систем, к которым относятся компьютерные сети. Это свойство обеспечивается принципиальной, но, к сожалению, не всегда практически реализуемой возможностью распределения работ между несколькими компьютерами сети.
Основные характеристики производительности сети:
· время реакции;
· скорость передачи трафика;
· пропускная способность;
· задержка передачи и вариация задержки передачи.
-Надежность и безопасность
Одна из первоначальных целей создания распределенных систем, к которым относятся и вычислительные сети, состояла в достижении большей надежности по сравнению с отдельными вычислительными машинами.
Важно различать несколько аспектов надежности. Для сравнительно простых технических устройств используются такие показатели надежности, как:
- среднее время наработки на отказ;
- вероятность отказа;
- интенсивность отказов.
Однако эти показатели пригодны для оценки надежности простых элементов и устройств, которые могут находиться только в двух состояниях -- работоспособном или неработоспособном. Сложные системы, состоящие из многих элементов, кроме состояний работоспособности и неработоспособности, могут иметь и другие промежуточные состояния, которые эти характеристики не учитывают.
Для оценки надежности сложных систем применяется другой набор характеристик:
· готовность или коэффициент готовности;
· сохранность данных;
· согласованность (непротиворечивость) данных;
· вероятность доставки данных;
· безопасность;
· отказоустойчивость.
-Расширяемость и масштабируемость
Масштабируемость означает, что наращивать сеть можно в очень широких пределах, при сохранении потребительских свойств сети.
-Прозрачность
Прозрачность (transparency) сети достигается в том случае, когда сеть представляется пользователям не как множество отдельных компьютеров, связанных между собой сложной системой кабелей, а как единая традиционная вычислительная машина с системой разделения времени.
-Поддержка разных видов трафика
Компьютерные сети изначально предназначались для совместного доступа к ресурсам компьютеров: файлам, принтерам и т. п. Трафик, создаваемый этими традиционными службами компьютерных сетей, имеет свои особенности и существенно отличается от трафика сообщений в телефонных сетях или, например, в сетях кабельного телевидения. Однако в 90-е годы в компьютерные сети проник трафик мультимедийных данных, представляющих в цифровой форме речь и видеоизображение. Компьютерные сети стали использоваться для организации видеоконференций, обучения на основе видеофильмов и т. п. Естественно, что для динамической передачи мультимедийного трафика требуются иные алгоритмы и протоколы, и, соответственно, другое оборудование. Хотя доля мультимедийного трафика пока невелика, он уже начал проникать как в глобальные, так и в локальные сети, и этот процесс, очевидно, будет активно продолжаться.
-Управляемость
В идеале средства управления сетями представляют собой систему, осуществляющую наблюдение, контроль и управление каждым элементом сети -- от простейших до самых сложных устройств, при этом такая система рассматривает сеть как единое целое, а не как разрозненный набор отдельных устройств.
Управляемость сети подразумевает возможность централизованно контролировать состояние основных элементов сети, выявлять и решать проблемы, возникающие при работе сети, выполнять анализ производительности и планировать развитие сети.
-Совместимость
Совместимость или интегрируемость означает, что сеть может включать в себя разнообразное программное и аппаратное обеспечение, то есть в ней могут сосуществовать различные операционные системы, поддерживающие разные стеки коммуникационных протоколов, и работать аппаратные средства и приложения от разных производителей. Сеть, состоящая из разнотипных элементов, называется неоднородной или гетерогенной, а если гетерогенная сеть работает без проблем, то она является интегрированной. Основной путь построения интегрированных сетей -- использование модулей, выполненных в соответствии с открытыми стандартами и спецификациями.
-Качество обслуживания
Качество обслуживания (Quality of Service, QoS) определяет количественные оценки вероятности того, что сеть будет передавать определенный поток данных между двумя узлами в соответствии с потребностями приложения или пользователя.
21.Основные компоненты и типы ЛВС. Их преимущества.
Перечисляя основные компоненты лвс, стоит отметить: активное оборудование сети, которое включает в себя коммутаторы, маршрутизаторы, концентраторы и пр.; и пассивное оборудование, состоящее из кабелей, монтажных шкафов, коммутационных панелей, информационных розеток и кабельных каналов.
Основными компонентами ЛВС являются физическая среда передачи, топология и метод доступа к физической среде. В современных ЛВС применяются: витые пары, коаксиальные и оптоволоконные кабели. Топология определяет общую структуру взаимосвязей и характеризует сложность интерфейса.
Рассмотрим преимущества, получаемые при сетевом объединении персональных компьютеров в виде внутрипроизводственной вычислительной сети.
Разделение ресурсов
Разделение ресурсов позволяет экономно использовать ресурсы, например, управлять периферийными устройствами, такими как лазерные печатающие устройства, со всех присоединенных рабочих станций производственной ЛВС.
Разделение данных
Разделение данных предоставляет возможность доступа и управления базами данных с периферийных рабочих мест, нуждающихся в информации.
Разделение программных средств
Разделение программных средств предоставляет возможность одновременного использования централизованных, ранее установленных программных средств.
Разделение ресурсов процессора
При разделении ресурсов процессора возможно использование вычислительных мощностей для обработки данных другими системами, входящими в сеть.
Многопользовательский режим
Многопользовательские свойства системы содействуют одновременному использованию централизованных прикладных программных средств, ранее установленных и управляемых, например, если пользователь системы работает с другим заданием, то текущая выполняемая работа отодвигается на задний план.
22. Понятие топологии сети. Базовые топологии. Сравнительные характеристики.
Под топологией вычислительной сети понимается способ соединения ее отдельных компонентов (компьютеров, серверов, принтеров и т.д.). Различают три основные топологии:
- топология типа звезда;
- топология типа кольцо;
- топология типа общая шина.
При использовании топологии типа звезда информация между клиентами сети передается через единый центральный узел. В качестве центрального узла может выступать сервер или специальное устройство - концентратор (Hub).
Преимущества данной топологии состоят в следующем:
1. Высокое быстродействие сети, так как общая производительность сети зависит только от производительности центрального узла.
2. Отсутствие столкновения передаваемых данных, так как данные между рабочей станцией и сервером передаются по отдельному каналу, не затрагивая другие компьютеры.
Однако помимо достоинств у данной топологии есть и недостатки:
1. Низкая надежность, так как надежность всей сети определяется надежностью центрального узла. Если центральный компьютер выйдет из строя, то работа всей сети прекратится.
2. Высокие затраты на подключение компьютеров, так как к каждому новому абоненту необходимо ввести отдельную линию.
При топологии типа кольцо все компьютеры подключаются к линии, замкнутой в кольцо. Сигналы передаются по кольцу в одном направлении и проходят через каждый компьютер.
Передача информации в такой сети происходит следующим образом. Маркер (специальный сигнал) последовательно, от одного компьютера к другому, передается до тех пор, пока его не получит тот, которому требуется передать данные. Получив маркер, компьютер создает так называемый "пакет", в который помещает адрес получателя и данные, а затем отправляет этот пакет по кольцу. Данные проходят через каждый компьютер, пока не окажутся у того, чей адрес совпадает с адресом получателя.
После этого принимающий компьютер посылает источнику информации подтверждение факта получения данных. Получив подтверждение, передающий компьютер создает новый маркер и возвращает его в сеть.
Преимущества топологии типа кольцо состоят в следующем:
1. Пересылка сообщений является очень эффективной, т.к. можно отправлять несколько сообщений друг за другом по кольцу. Т.е. компьютер, отправив первое сообщение, может отправлять за ним следующее сообщение, не дожидаясь, когда первое достигнет адресата.
2. Протяженность сети может быть значительной. Т.е. компьютеры могут подключаться к друг к другу на значительных расстояниях, без использования специальных усилителей сигнала.
К недостаткам данной топологии относятся:
1. Низкая надежность сети, так как отказ любого компьютера влечет за собой отказ всей системы.
2. Для подключения нового клиента необходимо отключить работу сети.
3. При большом количестве клиентов скорость работы в сети замедляется, так как вся информация проходит через каждый компьютер, а их возможности ограничены.
4. Общая производительность сети определяется производительностью самого медленного компьютера.
При топологии типа общая шина все клиенты подключены к общему каналу передачи данных. При этом они могут непосредственно вступать в контакт с любым компьютером, имеющимся в сети. 
Передача информации в данной сети происходит следующим образом. Данные в виде электрических сигналов передаются всем компьютерам сети. Однако информацию принимает только тот компьютер, адрес которого соответствует адресу получателя. Причем в каждый момент времени только один компьютер может вести передачу данных.
Преимущества топологии общая шина:
1. Вся информация находится в сети и доступна каждому компьютеру.
2. Рабочие станции можно подключать независимо друг от друга. Т.е. при подключении нового абонента нет необходимости останавливать передачу информации в сети.
3. Построение сетей на основе топологии общая шина обходится дешевле, так как отсутствуют затраты на прокладку дополнительных линий при подключении нового клиента.
4. Сеть обладает высокой надежностью, т.к. работоспособность сети не зависит от работоспособности отдельных компьютеров.
К недостаткам топологии типа общая шина относятся:
1. Низкая скорость передачи данных, т.к. вся информация циркулирует по одному каналу (шине).
2. Быстродействие сети зависит от числа подключенных компьютеров. Чем больше компьютеров подключено к сети, тем медленнее идет передача информации от одного компьютера к другому.
3. Для сетей, построенных на основе данной топологии, характерна низкая безопасность, так как информация на каждом компьютере может быть доступна с любого другого компьютера.
Самым распространенным типом сети с топологией общая шина является сеть стандарта Ethernet со скоростью передачи информации 10 - 100 Мбит/сек.
23. Комбинированные топологии.
Комбинированные топологии это использование при построении сети нескольких видов топологии одновременно(звезда-шина, звезда кольцо и т.д.).
24. Физическая среда передачи данных. Компоненты кабельной системы.
Физическая среда передачи данных (medium) может представлять собой кабель, то есть набор проводов, изоляционных и защитных оболочек и соединительных разъемов, а также земную атмосферу или космическое пространство, через которые распространяются электромагнитные волны.
В зависимости от среды передачи данных линии связи разделяются на следующие (рис. 2.2.):
проводные (воздушные);
кабельные (медные и волоконно-оптические);
радиоканалы наземной и спутниковой связи.
Кабельные линии представляют собой достаточно сложную конструкцию. Кабель состоит из проводников, заключенных в несколько слоев изоляции: электрической, электромагнитной, механической, а также, возможно, климатической. Кроме того, кабель может быть оснащен разъемами, позволяющими быстро выполнять присоединение к нему различного оборудования. В компьютерных сетях применяются три основных типа кабеля: кабели на основе скрученных пар медных проводов, коаксиальные кабели с медной жилой, а также волоконно-оптические кабели.
25. Локальные и глобальные сети.