15.Внешняя сортировка наборов данных

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

Наиболее часто внешняя сортировка используется в СУБД(системы управления базами данных). Основным понятием при использовании внешней сортировки является понятие отрезка. Отрезком длины K является последовательность записей Ai, Ai+1,…,Ai+k, что в ней все записи упорядочены по некоторому ключу. Максимальное количество отрезков в файле N(все элементы не упорядочены). Минимальное количество отрезков 1(все элементы являются упорядоченными)

Например в некотором файле А есть одномерный массив: 12 35 65 0 24 26 3 5 84 90 6 2 30 Поделим массив на отрезки: 12 35 65|0 24 36|3 5 84 90|6|2 30 Можно сказать, что массив в файле А состоит из 5 отрезков.

Например в некотором файле B есть одномерный массив: 1 2 3 4 5 6 7 8 9 10 Поделим массив на отрезки: |1 2 3 4 5 6 7 8 9 10| Можно сказать, что массив в файле B состоит из 1 отрезков.

Например в некотором файле А есть одномерный массив: 20 17 16 14 13 10 9 8 6 4 3 2 0 Поделим массив на отрезки: |20|17|16|14|13|10|9|8|6|4|3|2|0| Можно сказать, что массив в файле А состоит из 13 отрезков.

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

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

Основные методы сортировок: 1)Естественная сортировка(метод естественного слияния) 2)Сортировка методом двух путевого сбалансированного слияния 2.1)Сортировка методом n-путевого слияния. 3)Многофазная сортировка(Фибоначчиевая)

16.Жизненный цикл программы, тз..

Опр: Программный продукт – программа + пользовательская документация. ПП можно эксплуатировать без участия его автора.

Этапы ЖЦ:

Анализ

Проектирование

Реализация

Сборка, тестирование, испытание

Внедрение (выпуск)

Сопровождение

Анализ

Различают 2 случая производства ПП: 1) ПП делается для конкретного заказчика. В этом случае нужно прикладную задачу преврашать в программистскую. Нужно понять как функционирует та среда, которую нужно автоматизировать (анализ бизнес-процессов). В результате появляется документация-спецификация требования, где указаны какие именно задачи д.б. решены и при каких условиях. Эту работу выполняет системный аналитик (аналитик бизнес-процессов).

2) ПП разрабатывается для рынка. Нужно проводить маркетинговые исследования и найти какого продукта на рынке нет. Это связано с большим риском. Цель – разработка спецификации требований.

Проектирование

Цель – определение общей структуры (архитектуры) ПП. Результат – спецификация ПП. Эту работу выполняет системный программист.

Реализация

Написание программного кода. Реализация включает и разработку, и тестирование, и документацию.

Сборка, тестирование, испытние

Сборка всего, что сделано разными программистами. Тестирование всего программного комплекса. Отладка – поиск и устранение причин ошибок. Испытание – уточнение технических характеристик. В результате – гарантия работоспособносит программы.

Внедрение (выпуск)

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

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

Если на рынок выпускается принципиально новый ПП, то возможно несколько бета-тестирований. После бета-тестирование – выпуск коммерческой версии.

Сопровождение

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

Модели жизненного цикла ПО

[править]

Каскадная модель

Каскадная модель жизненного цикла («модель водопада», англ. waterfall model) была предложена в 1970 г. Уинстоном Ройсом. Она предусматривает последовательное выполнение всех этапов проекта в строго фиксированном порядке. Переход на следующий этап означает полное завершение работ на предыдущем этапе. Требования, определенные на стадии формирования требований, строго документируются в виде технического задания и фиксируются на все время разработки проекта. Каждая стадия завершается выпуском полного комплекта документации, достаточной для того, чтобы разработка могла быть продолжена другой командой разработчиков.

Этапы проекта в соответствии с каскадной моделью:

Формирование требований;

Проектирование;

Реализация;

Тестирование;

Внедрение;

Эксплуатация и сопровождение.

[править]

Спиральная модель

Спиральная модель (англ. spiral model) была разработана в середине 1980-х годов Барри Боэмом. Она основана на классическом цикле Деминга PDCA (plan-do-check-act). При использовании этой модели ПО создается в несколько итераций (витков спирали) методом прототипирования.

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

На каждой итерации оцениваются:

риск превышения сроков и стоимости проекта;

необходимость выполнения еще одной итерации;

степень полноты и точности понимания требований к системе;

целесообразность прекращения проекта.

Один из примеров реализации спиральной модели — RAD (англ. Rapid Application Development, метод быстрой разработки приложений).

[править]