1. Задачи сортировки; внутренняя и внешняя сортировка

В общей постановке задача ставится следующим образом. Имеется последовательность однотипных записей, одно из полей которых выбрано в качестве ключевого (далее мы будем называть его ключом сортировки). Тип данных ключа должен включать операции сравнения ("=", ">", "<", ">=" и "<="). Задачей сортировки является преобразование исходной последовательности в последовательность, содержащую те же записи, но в порядке возрастания (или убывания) значений ключа. Метод сортировки называется устойчивым, если при его применении не изменяется относительное положение записей с равными значениями ключа.

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

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

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

2. Подклассы асинхронного процесса. Эффективный асинхронный процесс

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

Действие – переход от одного состояния к другому.

Асинхронность – отсутствие ограничения на относительных – длительность, состояние и действие, т.е. длительность-состояние и длительность-действие имеют конечную продолжительность.

Согласованность – свойство, отражающее причинно-следственную связь между состояниями. Переход из одного состояния в другое происходит только после окончания первого.

Событие – мгновенное действие, которое в рассматриваемой нами модели не имеет продолжительности.

Ситуация – сочетание условий и обстоятельств, создающих определенную обстановку.

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

Асинхронный процесс (AP)

Эта модель ориентирована в основном на анализ свойств системы и решение вопросов ее аппаратной реализации.

Уточнение: асинхронность в этой модели подчеркивает, что категория времени формально не фигурирует в определении. Привязка к сущности времени осуществляется с помощью отношения F, т.е. если F, то время перехода из подмножества ситуаций  в подмножество ситуаций  не определено, но конечно.

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

F:

 - подмножество (совокупность) причин;

 - совокупность следствий.

Инициаторы

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

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

Асинхронный процесс – четверка <S, E, I, R>, в которых:

S – непустое множество системы;

E – отношение непосредственного следствия ситуаций, определенная на множестве SS, т.е. E  SS – бинарное (декартово) множество;

I – множество инициаторов, при этом I является подмножеством ситуаций S, т.е. I  S, причем таких, где:

• если iES_K, где i  I, S_K  I

R – множество результантов, R  S, при этом r  S, r  R, то и S  R.

Подклассы асинхронного процесса

Пусть имеется последовательность, возможно бесконечная, ситуации S(1)…S(i), S(i+1)…, где элемент S(i) стоит на i-месте в последовательности.

Для AP можно составить множество последовательностей ситуаций, в которых для каждого места i справедливо отношение S(i) E S(i+1), кроме последнего места. Причем ни одна из этих последовательностей не является частью другой. Такие последовательности называются допустимыми. Каждая допустимая последовательность ситуаций описывает возможный ход процесса смены ситуаций и соответствует реализации AP, иначе такая последовательность называется траекторией AP.

Эффективный AP – если все траектории ведут в результант и каждая из траекторий, приводящих к результанту, начинается в каком-либо инициаторе.

Автономный АП, удовлетворяющий свойствам 1)и 2)и имеющий фрагменты траекторий вида …i1…i2…s1…s2…, где g(s1)=r1, g(s2)=r2, называется конвейерным АП.

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

3. Граф диалога при человеко-машинном взаимодействии. Время ответа и время отображения результата. Составляющие длительности работы пользователя. Этапы взаимодействия пользователя с системой. Обратная связь. Длительность реакции системы. Индикация выполнения процесса. Субъективное восприятие скорости работы.

Время ответа и отображения результата это задержки компьютера.

Длительность выполнения работы пользователем состоит из

• Длительности восприятия исходной информации

• Длительности интеллектуальной работы

• Длительности физических действий пользователя

• Длительности реакции системы

Взаимодействие пользователя с системой (не только компьютерной) состоит из семи шагов:

1. формирование цели действий;

2. определение общей направленности действий;

3. определение конкретных действий;

4. выполнение действий;

5. восприятие нового состояния системы;

6. интерпретация состояния системы;

7. оценка результата.

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