Файл: информатика.doc

О(nlogn) алгоритмы сортировки.Обменная сортировка.

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

(Пузырьковая сортировка).

• Заключается в сравнении двух соседних элементов массива, в результате которого меньшее число (более легкий пузырёк) перемещается на одну позицию влево. Обычно такой просмотр организуют с конца массива и после первого прохода самое маленькое число перемещается на первое место. Затем все повторяется от конца массива до второго элемента и так далее.

• Метод назван «методом пузырька», потому что маленькие элементы, подобно пузырькам, «всплывают» на соответствующую позицию.

Время работы этого алгоритма определяется тремя параметрами: числом проходов А, числом обменов В и числом сравнений С. Улучшение этого алгоритма происходит само собой. Из примера видно, что три последовательных элемента не влияют на порядок элементов из-за того, что они уже отсортированы. Один из примеров улучшения этого метода – запоминать, были или нет перестановки в процессе некоторого прохода.

Сортировка методом слияния.(двухпутевое слияние)

Слияние означает объединение двух или более упорядоченных массивов в один упорядоченный массив.

Самый простой способ сделать это – сравнить два наименьших элемента, вывести наименьшее из них и повторить процедуру

Слияние означает объединение двух или более упорядоченных массивов в один упорядоченный массив.

Самый простой способ сделать это – сравнить два наименьших элемента, вывести наименьшее из них и повторить процедуру

структура

М1. Установить i←1, j←1, k←1.

М2. Если xi ≤ yj,, перейти к М3, в противном случае к М5.

М3. Установить zk ← xi, k ← k+1, i←i+1. Если i ≤ m , вернуться к М2.

М4. Установить (zk, …, z(m+n)) ← (yj, …, yn) и завершить выполнение.

М5. Установить zk ← yj,, , k ← k+1, j←j+1. Если j≤n, вернуться к шагу М2.

М6. Установить (zk, …, z(m+n))←(xi, …,xm) и завершить алгоритм.

А) Алгоритмы быстрой сортировки. (Сортировка Хоара или сортировка с помощью разделения)

Этот алгоритм является примером использования рекурсии. Он был разработан в 1962 году, профессором Оксфордского университета Хоаром. (Основан на алгоритме сортировки обменами).

Принцип метода: для достижения наилучшей эффективности сначала лучше производить перестановки на большие расстояния. Выберем наугад какой-либо элемент (х) и будем просматривать слева массив до тех пор, пока не обнаружим элемент Ri> x, затем будем просматривать массив справа, пока не встретим Rj<x. Теперь поменяем их местами и продолжим процесс просмотра и обмена, пока оба просмотра не встретятся в середине массива. В результате массив окажется разбитым на левую часть с ключами ≤ x, и правую – с ключами ≥ x.

Таким образом, относительно значения x массив получается отсортированным, но левая и правая части ещё не упорядочены.

Сортировка с помощью включений с уменьшающимися расстояниями (Сортировка Шелла)

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

Его суть: сначала отдельно группируются и сортируются элементы, отстоящие друг от друга на n/2 (n – количество элементов массива). Каждая группа состоит из 2 элементов. Если n/2=4 , такой процесс называется четвертной сортировкой. После первого прохода элементы перегруппировываются – теперь каждый элемент группы отстоит от другого на n/4 позиции – и вновь сортируются. Если n/4=2 то этот процесс называется двойной сортировкой. Процесс завершается проходом, во время которого сортируются все n записей.

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

Поиск элементов в массивах – одно из наиболее часто встречающихся в программировании действий.

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

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

Последовательный (линейный) поиск.

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

Условия окончания поиска таковы:

1. Элемент найден, т.е. Ki=K.

2. Весь массив просмотрен и совпадения не обнаружено.

Бинарный поиск (поиск делением пополам).

Поиск можно сделать значительно более эффективным, если данные будут упорядочены. Основная идея – выбрать случайно некоторый элемент, предположим, Ki, и сравнить его с аргументом поиска. Если он равен K, то поиск заканчивается, если он меньше K, то мы заключаем, что все элементы с индексами <=i можно исключить из дальнейшего поиска. Если же он >K, то исключаются индексы >=i. Здесь используем два указателя l и u, которые указывают верхнюю и нижнюю границы поиска.

7. Программные продукты и их основные характеристики: основные понятия программного обеспечения; характеристики программных продуктов; защита программных продуктов; классификация программных продуктов

Основные понятия программного обеспечения

Программа (program) — упорядоч. последовательность ко­манд компьютера для решения задачи.

Программное обеспечение (sowtware) — совокупность программ обработки данных и необходимых для их эксплуатации документов.

Программы предназначены для машинной реализации задач. Термины задача и приложение имеют очень широкое употребление в контексте информатики и про­граммного обеспечения. При этом задача (problem) — это проблема, подлежащая решению, а приложение (application) — программная реализация на компьютере решения задачи. Т. о., задача означает проблему, подлежащую реализации с использованием средств информационных технологий, а приложение — реализованное на компьютере решение этой задачи. Приложение считается более удачным термином и широко исп-ся в информатике. Необходимо заметить, что термин задача также употребляется в сфере программирования как единица работы вычислительной системы, требующая выделения вычислительных ресурсов (процессорного времени, основной памяти и т.п.).

Существует разнообразные классификации задач. С позиций специфи­ки разработки и вида ПО— тех­нологические и функциональные.

Технологические задачи ставятся и решаются при организации технологи­ческого процесса обработки информации на компьютере. Функциональные задачи требуют решения при реализации функций управления в рамках информационных систем предметных областей. Предметная (прикладная) область (application domain) — это совокупность связанных между собой функций, задач управления, с помощью которых достигается выполнение поставленных целей.

Все программы по характеру использования и категориям пользователей можно разделить на два класса — утилитарные программы и программные продукты (изделия).

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

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

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

• freeware — бесплатные программы, свободно распространяемые, поддерживаются самим пользователем, который правомочен вносить в них необходимые изменения;

• shareware— некоммерческие (условно-бесплатные) программы, которые могут ис­пользоваться, как правило, бесплатно. При условии регулярного использования подоб­ных продуктов осуществляется взнос определенной суммы.

Ряд производителей использует ОЕМ-программы (Original Equipment Manufac­turer), т.е. встроенные программы, устанавливаемые на компьютеры или поставляемые вместе с вычислительной техникой.

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

Программные продукты могут создаваться как:

• индивидуальная разработка под заказ;

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

Сопровождение программного продукта — это поддержка работоспособнос­ти программного продукта, переход на его новые версии, внесение измене­ний, исправление обнаруженных ошибок и т.п.

Основными характеристиками программ являются:

1)алгоритмическая сложность (логика алгоритмов обработки информации); 2)состав и глубина проработки реализованных функций обработки; 3)полнота и системность функций обработки; 4)объем файлов программ; 5)требования к операционной системе и техническим средствам обработки со стороны и др.

Программные продукты имеют многообразие показателей качества

Структура характеристик качества программных продуктов можно представить в виде схемы :

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