![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Характеристики Простейших СортировокСтр 1 из 3Следующая ⇒
Сортировка Вставкой
type Также как и в сортировке выбором, в процессе сортировки элементы слева от указателя i находятся уже в сортированном порядке, но они не обязательно находятся в своей последней позиции, поскольку их еще могут передвинуть направо чтобы вставить более маленькие элементы встреченные позже.. Однако массив становится полностью сортированным когда указатель достигает правого края. Пузырьковая Сортировка Следующий метод - это пузырьковая сортировка. Проходить через массив, обменивая если нужно элементы; когда на каком-то шаге обменов не потребуется - сортировка окончена. Реализация этого метода дана ниже. procedure bubble; Чтобы поверить в то, что она на самом деле работает, может потребоваться некоторое время. Для этого заметьте, что когда во время первого прохода встречаем максимальный элемент, обмениваем его с каждым элементом справа от него пока он не окажется в крайне правой позиции. На втором проходе помещаем второй максимальный элемент в предпоследнюю позицию и так далее. Пузырьковая сортировка работает также как и сортировка выбором, хотя она и делает гораздо больше работы на то, чтобы переместить элемент в его конечную позицию. Характеристики Простейших Сортировок Свойство 1 Сортировка выбором использует около N2/2 сравнений и N обменов. Свойство 2 Сортировка вставкой использует около N2/4 сравнений и N2/8 обменов в среднем, и в два раза больше в наихудшем случае. Свойство 3 Пузырьковая сортировка использует около N2/2 сравнений и N2/2 обменов в среднем и наихудшем случаях. Свойство 4 Сортировка вставкой линейна для " почти сортированных" файлов. Свойство 5 Сортировка выбором линейна для файлов с большими записями и маленькими ключами.
13.Логические основы компьютера. Логические функции. Компьютер работает на электричестве, т.е. логические элементы компьютера оперируют с сигналами, представляющими собой электрические импульсы. Есть импульс – логический смысл сигнала – 1, нет импульса – 0. На входы логического элемента поступают Преобразование сигнала логическим элементом является таблицей состояния, которая фактически является таблицей истинности, соответствующей логической функции. Базовые логические элементы реализуют рассмотренные выше три основные логические операции:
14.Алгебра логики (основные схемы). 1.Элемент НЕ(инверсия)
2.Дизьюнкция(ИЛИ)
4.Исключаюшие или
Для 2 и 3 возможно 2 и более входов, также возможны комбинации 1-2, 1-3, 1-4.
15.Триггер. Сумматор. Триггер — это электронная схема, широко применяемая в регистрах компьютера для надёжного запоминания одного разряда двоичного кода. Триггер имеет два устойчивых состояния, одно из которых соответствует двоичной единице, а другое — двоичному нулю. Самый распространённый тип триггера — так называемый RS-триггер (S и R, соответственно, от английских set — установка, и reset — сброс).
Сумматор — это электронная логическая схема, выполняющая суммирование двоичных чисел. Многоразрядный двоичный сумматор, предназначенный для сложения многоразрядных двоичных чисел, представляет собой комбинацию одноразрядных сумматоров, с рассмотрения которых мы и начнём. Условное обозначение одноразрядного сумматора на рис. 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. Основные характеристики ВС. Вжнейшие показатели работы сети: производительность, надежность и безопасность, расширяемость и масштабируемость, прозрачность, поддержка разных видов трафика, характеристики качества обслуживания, управляемость и совместимость.
|