Файл: ИНФОРМАТИКА 2-15.doc

Сортировка вставками

С ортировка вставками похожа на процесс тасования карточек с именами. Регистратор заносит каждое имя на карточку, а затем упорядочивает карточки по алфавиту, вставляя карточку в верхнюю часть стопки в подходящее место. Опишем этот процесс на примере нашего пятиэлементного списка A = 50, 20, 40, 75, 35 (рисунок 1).

В функцию InsertionSort передается массив A и длина списка n. Рассмотрим i-ый проход (1<i<n-1). Подсписок от A[0] до A[i-1] уже отсортирован по возрастанию. В качестве вставляемого (TARGET) выберем элемент A[i] и будем продвигать его к началу списка, сравнивая с элементами A[i-1], A[i-2] и т.д. Просмотр заканчивается на элементе A[j], который меньше или равен TARGET, или находится в начале списка (j = 0). По мере продвижения к началу списка каждый элемент сдвигается вправо (A[j] = A[j-1]). Когда подходящее место для A[i] будет найдено, этот элемент вставляется в точку j.

Рис. 1

«Быстрая» сортировка

Итак, мы рассмотрели алгоритм сортировки массива, имеющий сложность порядка O(n2). Алгоритмы, использующие деревья (турнирная сортировка, сортировка посредством поискового дерева), обеспечивают значительно лучшую производительность O(n log2n). Несмотря на то, что они требуют копирования массива в дерево и обратно, эти затраты покрываются за счет большей эффективности самой сортировки.

Широко используемый метод пирамидальной сортировки также обрабатывает массив «на месте» и имеет эффективность O(n log2n). Однако «быстрая» сортировка, которую изобрел К.Хоар, для большинства приложений превосходит пирамидальную сортировку и является самой быстрой из известных до сих пор.

Описание «быстрой» сортировки

Алгоритм QuickSort

• выбрать элемент, называемый опорным.

• сравнить все остальные элементы с опорным, на основании сравнения разбить множество на три — «меньшие опорного», «равные» и «большие», расположить их в порядке меньшие-равные-большие.

• повторить рекурсивно для «меньших» и «больших».

Подробно:

1. Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен. С точки зрения повышения эффективности алгоритма выбираться должна медиана, но без дополнительных сведений о сортируемых данных её обычно невозможно получить. Известные стратегии: выбирать постоянно один и тот же элемент, например, средний или последний по положению; выбирать элемент со случайно выбранным индексом.

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

   1. Два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива соответственно.

   2. Вычисляется индекс опорного элемента m.

   3. Индекс l последовательно увеличивается до m до тех пор, пока l-й элемент не превысит опорный.

   4. Индекс r последовательно уменьшается до m до тех пор, пока r-й элемент не окажется меньше либо равен опорному.

   5. Если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент.

   6. Если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно.

3. Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.

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

[править] Вычислительная сложность «быстрой» сортировки

Общий анализ эффективности «быстрой» сортировки достаточно труден. Будет лучше показать ее вычислительную сложность, подсчитав число сравнений при некоторых идеальных допущениях. Допустим, что n – степень двойки, n = 2^k (k = log₂n), а центральный элемент располагается точно посередине каждого списка и разбивает его на два подсписка примерно одинаковой длины.

Рис.7 Сравнение сортировок порядка O(n2).

Сортировка пузырьком

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

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

Идея этого метода заключается в следующем. Множество элементов просматривается последовательно в некотором порядке, гарантирующем, что будут просмотрены все элементы множества (например, слева направо). Если в ходе просмотра множества будет найден искомый элемент, просмотр прекращается с положительным результатом; если же будет просмотрено все множество, а элемент не будет найден, алгоритм должен выдать отрицательный результат.

Алгоритм последовательного поиска

Шаг 1. Полагаем, что значение переменной цикла i=0.

Шаг 2. Если значение элемента массива x[i] равно значению ключа key, то возвращаем значение, равное номеру искомого элемента, и алгоритм завершает работу. В противном случае значение переменной цикла увеличивается на единицу i=i+1.

Шаг 3. Если i<k, где k – число элементов массива x, то выполняется Шаг 2, в противном случае – работа алгоритма завершена и возвращается значение равное -1.

При наличии в массиве нескольких элементов со значением key данный алгоритм находит только первый из них (с наименьшим индексом).

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

Бинарный поиск применяется к отсортированным множествам и заключается в последовательном разбиении множества пополам и поиска элемента только в одной половине на каждой итерации.

Алгоритм бинарного поиска

Шаг 1. Определить номер среднего элемента массива middle=(high+low)/2.

Шаг 2. Если значение среднего элемента массива равно искомому, то возвращаем значение, равное номеру искомого элемента, и алгоритм завершает работу.

Шаг 3. Если искомое значение больше значения среднего элемента, то возьмем в качестве массива все элементы справа от среднего, иначе возьмем в качестве массива все элементы слева от среднего (в зависимости от характера упорядоченности). Перейдем к Шагу 1.

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

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

10.Основные задачи системного программирования. Ресурсы компьютера. Операционные системы (ОС) как средство распределения и управления ресурсами. Развитие и основные функции ОС. Состав ОС: внутренние (встроенные) и внешние (программы-утилиты). Команды ОС. Сетевые ОС.

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

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

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

Этот процесс называется загрузкой операционной системы.

В функции операционной системы входит:

• осуществление диалога с пользователем;

• ввод-вывод и управление данными;

• планирование и организация процесса обработки программ;

• распределение ресурсов (оперативной памяти и кэша, процессора, внешних устройств);

• запуск программ на выполнение;

• всевозможные вспомогательные операции обслуживания;

• передача информации между различными внутренними устройствами;

• программная поддержка работы периферийных устройств (дисплея, клавиатуры, дисковых накопителей, принтера и др.).

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

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

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

2. однопользовательские однозадачные с фоновой печатью, которые позволяют помимо основной задачи запускать одну дополнительную задачу, ориентированную, как правило, на вывод информации на печать. Это ускоряет работу при выдаче больших объёмов информации на печать;

3. однопользовательские многозадачные, которые обеспечивают одному пользователю параллельную обработку нескольких задач. Например, к одному компьютеру можно подключить несколько принтеров, каждый из которых будет работать на "свою" задачу;

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

Операционная система для персонального компьютера, ориентированного на профессиональное применение, должна содержать следующие основные компоненты:

• программы управления вводом/выводом;

• программы, управляющие файловой системой и планирующие задания для компьютера;

• процессор командного языка, который принимает, анализирует и выполняет команды, адресованные операционной системе.

Каждая операционная система имеет свой командный язык, который позволяет пользователю выполнять те или иные действия:

• обращаться к каталогу;

• выполнять разметку внешних носителей;

• запускать программы;

• ... другие действия.

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

Для управления внешними устройствами компьютера используются специальные системные программы — драйверы. Драйверы стандартных устройств образуют в совокупности базовую систему ввода-вывода (BIOS), которая обычно заносится в постоянное ЗУ компьютера.

Файл (англ.file,папка) — это место постоянного хранения информации: программ, данных для их работы, текстов, закодированных изображений, звуков и др.

Файловая система — это средство для организации хранения файлов на каком-либо носителе.

Файлы физически реализуются как участки памяти на внешних носителях — магнитных дисках или CD-ROM.

Каждый файл занимает некоторое количество блоков дисковой памяти. Обычная длина блока — 512 байт.

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

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

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

Каталог может иметь собственное имя и храниться в другом каталоге наряду с обычными файлами: так образуются иерархические файловые структуры.

Что происходит, когда пользователь подает операционной системе команду "открыть файл ...", в которой указано имя файла и имя каталога, в котором размещён этот файл?

Для выполнения этой команды драйвер файловой системы обращется к своему справочнику, выясняет, какие блоки диска соответствуют указанному файлу, а затем передает запрос на считывание этих блоков драйверу диска.

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

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

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

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

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

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

Операционная система MS DOS (Microsoft Disk Operating System) — самая распространенная ОС на 16-разрядных персональных компьютерах. Она состоит из следующих основных модулей:

• базовая система ввода/вывода (BIOS);

• блок начальной загрузки (Boot Record);

• модуль расширения базовой системы ввода/вывода (IO.SYS);

• модуль обработки прерываний (MSDOS.SYS);

• командный процессор (COMMAND.COM);

• утилиты MS DOS.

Каждый из указанных модулей выполняет определенную часть функций, возложенных на ОС. Места постоянного размещения этих модулей различны. Так, базовая система ввода/вывода находится в постоянном запоминающем устройстве (ПЗУ), а не на дисках, как все остальные модули.

Базовая система ввода/вывода (BIOS) выполняет наиболее простые и универсальные услуги операционной системы, связанные с осуществлением ввода-вывода. В функции BIOS входит также автоматическое тестирование основных аппаратных компонентов (оперативной памяти и др.) при включении машины и вызов блока начальной загрузки DOS.

Блок начальной загрузки (или просто загрузчик) — это очень короткая программа, единственная функция которой заключается в считывании с диска в оперативную память двух других частей DOS — модуля расширения базовой системы ввода/вывода и модуля обработки прерываний.