Информатика. Текстовый редактор

РЕФЕРАТ
Основными задачамиучебной практики по информатике являлись:
— освоение способовускоренного набора текста на примере десятипальцевого метода;
— закрепление навыковсамостоятельного оформления технической документации по специальности всоответствии с ГОСТом и иными требованиями, предъявляемыми к ним законодательством,
— формирование умений изакрепление навыков работы в текстовом редакторе MS Word в задачах оформления технической документации;
— формирование умений изакрепление навыков работы с электронными таблицами MS Excel в задачах обработки, анализа и визуализациистатистического и графического материала технической документации;
— закрепление уменийавтоматизировать рутинные процессы формирования технической документации сиспользованием макроязыка VBA иформул электронных таблиц.
Соло наклавиатуре, MS Word, MS Exсel, Visual Basic
Д.091400.01.1.01.05/147.УП
Фамилия    Подпись     Дата
Разработал        
Рук.практики
Н.контр.

СОДЕРЖАНИЕ
1. Введение.
2. Общая часть.
2.1. Методдесятипальцевого набора текста
2.1.1. Тема, задание,цель
2.1.2. Отчет о выполнении
2.1.3. Вывод
2.2. Средство обработкиинформации MS Word
2.2.1. Тема, задание,цель
2.2.2. Исходные данные ииндивидуальное задание
2.2.3. Отчет о выполнении
2.2.4. Вывод
2.3. Средство обработкиинформации MS Excel
2.3.1. Тема, задание,цель
2.3.2. Исходные данные ииндивидуальное задание
2.3.3. Отчет о выполнении
2.3.4. Листинг модуля
2.3.4. Вывод
2.4. Средство обработкиинформации VBA
2.4.1. Тема, задание,цель
2.4.2. Исходные данные ииндивидуальное задание
2.4.3. Алгоритм
2.4.4. Листинг работымакроса
2.4.5. Отчет о выполнении
2.4.6. Вывод
3. Заключение
4. Список использованнойлитературы

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

2. ОБЩАЯ ЧАСТЬ
 
Общая часть включает всебя отчеты индивидуальных заданий, выданные руководителем практики.
2.1 Методдесятипальцевого набора текста
Соло на клавиатуре –программа, которая обучает основным навыкам набора слепым десятипальцевымметодом. Программа реализована для начинающих пользователей, а также дляулучшения набора. Она состоит из 100 заданий, которые оцениваются 5-ойсистемой.
2.1.1 Тема, задание,цель
 
Тема — основные навыки успешногоспециалиста.
Задание — пройти 10 уроков «Соло наклавиатуре».
Цель — получить мотивацию обучения умениюи получения навыкам
слепого набора.
2.1.2 Отчет овыполнении
 
Отчетом о выполнении 10уроков является ниже приведенный рисунок статистики прохождения программы.
/>
Рисунок 2.1 Статистикапрохождения программы «Соло на клавиатуре»
Рисунок 2.1подтверждающий факт прохождения программы. На нем изображена общая статистка.
2.1.3 Вывод
Выполнив задание даннойпрограммы, я получил мотивацию обучения умению и получения навыкам слепогонабора.
2.2 Средство обработкиинформации MSWord
Microsoft Word – мощноесредство обработки информации корпорации Майкрософт, которая имеет множествоутилит необходимых для набора и обработки информации.
2.2.1 Тема, задание,цель
Тема — набор и форматирование документовв Word.
Задание — безошибочно набрать около 14страниц сложного текста, получить основные умения по форматированию.
Цель — получить основные умения по наборутекстового и графического материала, привести материал в соответствии с ГОСТ.
2.2.2 Исходные данныеи индивидуальное задание
Исходными данными ииндивидуальным заданием является электронная книга, выданная руководителемпрактики и номер задание из списка журнала (6. Ахо.pdf 104-116).
2.2.3 Отчет овыполнении
Отчетом о выполненииданного задания будет набранный и отформатированный текст, приведенный ниже.
ТЕСТ ПО ИНДИВИДУАЛЬНОМУЗАДАНИЮ
/>/>/>Уровень 3                            1 (1,2)
/>/>/>/>/>/>/>/>Уровень 2              1 (0,0,0)                   2 (0,1,1)/> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> /> />

/>/>/>/>Уровень1      0      0      0        1 (0,0)     0     1(0,0)/> /> /> /> /> /> /> /> /> /> /> /> /> /> /> />

Уровень0                         0      0       0     0
Рисунок3.4. а) Числа, приписанные алгоритмом распознавания изоморфизма деревьев.

/>/>Уровень 3                          1 (1,2)
/>/>/>/>/>/>/>/>/>Уровень 2              1 (0,0,0)                   2 (0,1,1)/> /> /> /> /> /> /> /> /> /> /> /> /> /> /> />

/>/>/>/>/>Уровень 1    1(0,0)   0     1 (0,0)    0        0     0/> /> /> /> /> /> /> /> /> /> /> /> />

Уровень      0       0       0        0
ДеревоТ2
Рисунок3.4. б) Числа, приписанные алгоритмом распознавания изоморфизма деревьев.
Тогдаизоморфизм двух помеченных деревьев можно распо­знать за линейное время, есливключить метку каждого узла в ка­честве первой компоненты кортежа,приписываемого этому узлу из­ложенным выше алгоритмом. Таким образом,справедливо
Следствие. Распознавание изоморфизма двухпомеченных деревь­ев с п узлами, метками которых служат целые числа между 1 ип, занимает время 0(п).
3.3.СОРТИРОВКА С ПОМОЩЬЮ СРАВНЕНИЙ
Здесь мыизучим задачу упорядочения последовательности из п элементов, взятых из линейноупорядоченного множества 5, о структуре которых ничего не известно. Информациюоб этой после­довательности можно получить только с помощью операции сравне­ниядвух элементов. Сначала мы покажем, что любой алгоритм, упорядочивающий спомощью сравнений, должен делать по крайней мере О (n log n) сравнений на некоторой последовательности дли­ны n. Пусть надо упорядочитьпоследовательность, состоящую из nразличных элементов аг, а2,..., аn.
Алгоритм,упорядочивающий с помощью сравнений, можно представить в виде дерева решенийтак, как описано в разделе 1.5. На рис. 1.18 изображено дерево реше­ний,упорядочивающее последовательность a, b, c. Далее мы пред­полагаем, что если элемент a сравнивается с элементом b в некотором узле v дерева решений, то надо перейти клевому сыну узла v при a  b.
Какправило, алгоритмы сортировки, в которых для разветвле­ния используютсясравнения, ограничиваются сравнением за один раз двух входных элементов. Всамом деле, алгоритм, который ра­ботает на произвольном линейно упорядоченноммножестве, не мо­жет никак преобразовать входные данные, поскольку при самой об­щейпостановке задачи операции над данными «не имеют смысла». Так илииначе, мы докажем сильный результат о высоте любого де­рева решений,упорядочивающего последовательность из п эле­ментов.
Лемма3.1. Двоичное деревовысоты Н содержит не более 1п ли­стьев.
Доказательство. Элементарная индукция по h. Нужно лишь заметить, что двоичноедерево высоты h составлено из корня и самое большеедвух поддеревьев, каждое высоты не более h — 1.
Теорема3.4. Высота любогодерева решений, упорядочивающего последовательность из п различных элементов,не меньше log n!.
Доказательство. Так как результатом упорядоченияпоследовательности из п! элементов может быть любая из п\ переста­новок входа,то в дереве решений должно быть по крайней мере n! листьев. По лемме 3.1 высота такого дерева должна быть неменьше log n!..
Следствие. В любом алгоритме, упорядочивающем спомощью сравнений, на упорядочение последовательности из п элементов тра­титсяне меньше сп log п сравнений при некотором с>0 идостаточ­но большом п.
Доказательство. Заметим, что при n >1
n!/>n(n-1)(n-2)…(/>)/>/>(/>)/>,
так что log n!/>(n/2)log(n/2)/>(n/4)log n при n />4
Поформуле Стирлинга точнее приближает n! функция (п/е)п, так что n(log п — log е)=п log п — 1,44n служит хорошим приближе­нием нижней границы числа сравнений, необходимыхдля упорядо­чения последовательности из п элементов.
3.4. СОРТ ДЕРЕВОМ — УПОРЯДОЧЕНИЕ С ПОМОЩЬЮ О(n log n) СРАВНЕНИЙ
Так каклюбой сортирующий алгоритм, упорядочивающий с помощью сравнений, затрачивает понеобходимости п log п срав­ненийдля упорядочения хотя бы одной последовательности длины n, естественно спросить, существуют лисортирующие алгоритмы, затрачивающие не более О (п log п) сравнений для упорядочения любойпоследовательности длины п. Один такой алгоритм мы уже видели — это сортировкаслиянием из разд. 2.7. Другой алгоритм — Сортдеревом. Помимо того, что этополезный алгоритм упорядо­чения, в нем используется интересная структураданных, которая находит и другие приложения.
Сортдеревомлучше всего понять в терминах двоичного дерева вроде изображенного на рис. 3.5,у которого каждый лист имеет глубину d. или d-1. Узлы дерева помечаются элементамипоследова­тельности, которую хотят упорядочить. Затем Сортдеревом меняетразмещение этих элементов на дереве до тех пор, пока элемент, соответствующийпроизвольному узлу, станет не меньше элементов, соответствующих его сыновьям.Такое помеченное дерево мы будем называть сортирующим.
Пример3.3. На рис. 3.5изображено сортирующее дерево. За­метим, что последовательность элементов,лежащих на пути из любого листа в корень, линейно упорядочена и наибольший эле­ментв поддереве всегда соответствует его корню.
Наследующем шаге алгоритма Сортдеревом из сортирующего дерева удаляетсянаибольший элемент — он соответствует корню дерева. Метка некоторого листапереносится в корень, а сам лист уда­ляется. Затем полученное деревопеределывается в сортирующее, и процесс повторяется. Последовательностьэлементов, удаленных из сортирующего дерева, упорядочена по невозрастанию.
Удобнойструктурой данных для сортирующего дерева служит такой массив А, что А[1] —элемент в корне, а А[2i] и A[2i+1] – элементы в левом и правом сыновьях (если онисуществуют) того узла, в котором хранится А[i].
/>

Рисунок 3.5 Сортирующеедерево.
Например,сортирующее дерево на рис. 3.5 можно представить массивом4 11 9 10 5 6 8 1 2 16
Заметим,что узлы наименьшей глубины стоят в этом массиве первыми, а узлы равной глубиныстоят в порядке слева направо.
Некаждое сортирующее дерево можно представить таким спо­собом. На языкепредставления деревьев можно сказать, что для образования такого массиватребуется, чтобы листья самого низ­кого уровня стояли как можно левее (как, например,на рис. 3.5).
Еслисортирующее дерево представляется описанным массивом, то некоторые операции изалгоритма Сортдеревом легко выполнить. Например, согласно алгоритму, нужноудалить элемент из корня, где-то запомнить его, переделать оставшееся дерево всортирующее и удалить непомеченный лист. Можно удалить наибольший эле­мент изсортирующего дерева и запомнить его, поменяв местами A[1] и A[n], и затем не считать более ячейку пнашего массива частью сортирующего дерева. Ячейка п рассматривается как лист, удаленныйиз этого дерева. Для того чтобы переделать дерево, хра­нящееся в ячейках 1,2,…, n—1, в сортирующее, надо взять новый элементA[1] и провести его вдоль подходящегопути в дереве. Затем можно повторить процесс, меняя местами A[1] и A[п—1] и считая, что дерево занимает ячейки 1,2 … п—2 и т. д.
Пример3.4. Рассмотрим напримере сортирующего дерева рис. 3.5, что происходит, когда мы поменяем местамипервый и по­следний элементы массива, представляющего это дерево. Новый массив16 11 9 10 5 6 8 1 2 4
соответствует помеченному дереву нарис. 3.6, а. Элемент 16 ис­ключается из дальнейшего рассмотрения. Чтобыпревратить полу­ченное дерево в сортирующее, надо поменять местами элемент 4 сбольшим из его сыновей, т. е. с элементом 11.
В своемновом положении элемент 4 обладает сыновьями 10 и 5. Так как они больше 4, то 4переставляется с 10, большим сыном. После этого сыновьями элемента 4 в новомположении становятся 1 и 2. Поскольку 4 превосходит их обоих, дальнейшиеперестановки не нужны.

/>

Рисунок 3.6. а — результат перестановки элементов 4 и 16 всортирующем дерев
/>

Рисунок3.6; б — результат перестройки сортирующего дерева и удаления элемента 16.
Полученноев результате сортирующее дерево показано на рис. 3.6,6. Заметим, что хотяэлемент 16 был удален из сортирующе­го дерева, он все же присутствует в концемассива А.
Теперьперейдем к формальному описанию алгоритма Сорт-деревом.
Пусть аг,а2,… ., ап — последовательность сортируемых эле­ментов.Предположим, что вначале они помещаются в массив А именно в этом порядке, т. е.A[i] = a/>,1/>i/>n. Первый шаг состоит в построении сортирующего дерева,т. е. элементы в А перераспре­деляются так, чтобы удовлетворялось свойствосортирующего де­рева: A[i]/>A[2i] при 1/>i/>/>n/2 и A[i]/>A[2i+1] при 1/>i/>n/2. Это делают, строя, начиная с листьев, все большиеи большие сор­тирующие деревья. Всякое поддерево, состоящее из листа, уже яв­ляетсясортирующим. Чтобы сделать поддерево высоты h сортирую­щим, надо переставить элемент в корне с наибольшимиз элементов, соответствующих его сыновьям, если, конечно, он меньше какого-тоиз них. Такое действие может испортить сортирующее дерево высоты h — 1, и тогда его надо снова перестроитьв сортирующее. Приведем точное описание этого алгоритма.
Алгоритм3.3. Построениесортирующего дерева
Вход.Массив элементов A[i], 1/>/>i/>n
Выход.Элементы массива А, организованные в виде сортирую­щего дерева, т. е.A[i]/>A[/>] для 1n.
Метод. Воснове алгоритма лежит рекурсивная процедура пересыпка. Ее параметры i и j задают область ячеек массива А, обладающую свойствомсортирующего дерева; корень строящегося дерева помещается в i.
procedureПЕРЕСЫПКА ((i,j):
1. if i — не лист и какой-то его сын содержит элемент, пре­восходящийэлемент в i then begin
2.        пустьk— тот сын узла i, в котором хранится
наибольшийэлемент;
3.                переставить А[i] и А[k];
4.                ПЕРЕСЫПКА (k,j)
5.                end
Параметрj используется, чтобы определить,является ли i листом и имеет он одного или двухсыновей. Если i > j/2, то i —лист, и процедуре ПЕРЕСЫПКА(i,j) ничего не нужно делать, посколькуА[i] — уже сортирующее дерево.
Алгоритм,превращающий весь массив А в сортирующее дерево, выглядит просто:
procedure ПОСТРСОРТДЕРЕВА:
for i />п1) stер —1 until 1 do ПЕРЕСЫПКА (i,n) 
Покажем,что алгоритм 3.3 преобразует А в сортирующее дере­во за линейное время.
Лемма3.2. Если узлы i+1, i+2,… ., nявляются корнями сор­тирующих деревьев, то после вызова процедуры ПЕРЕСЫПКА (i, п) все узлы i, i+1,… ., п будут корнями сортирующих деревьев.
Доказательство.Доказательствопроводится возврат­ной индукцией по I.
Базис,т. е. случай i=п, тривиален, так как узел п долженбыть листом и условие, проверяемое в строке 1, гарантирует, что ПЕ­РЕСЫПКА (п,п) ничего не делает.
Для шагаиндукции заметим, что если i —лист или у него нет сына с большим элементом, то доказывать нечего (как и приобо­сновании базиса). Но если у узла i есть один сын (т. е. если 2i=n) и A[i]A[2i], то дерево с корнем i также оказывается сортирующим.
Аналогично,если узел i имеет двух сыновей (т. е. если 2i+1/>n) и наибольший из элементов в А [2i] и в А [2i+1]больше элемента в A [i], то, рассуждая, как и выше, можнопоказать, что после вызова процедуры ПЕРЕСЫПКА(i,n) все узлы i, i+1,..., nбудут кор­нями сортирующих деревьев.
Теорема3.5. Алгоритм 3.3преобразует А в сортирующее дере­во за линейное время.
Доказательство. Применяя лемму 3.2, можно с по­мощьюпростой возвратной индукции по iпоказать, что узел i становитсякорнем какого-нибудь сортирующего дерева для всех i, 1/>i/>n
Пусть Т(h) — время выполнения процедурыПЕРЕСЫПКА на узле высоты h.Тогда Т (h)/>Т (h — 1)+с для некоторой постоянной с. Отсюда вытекает, что Т (h) есть О (h).
Алгоритм3.3 вызывает процедуру ПЕРЕСЫПКА, если не счи­тать рекурсивных вызовов, одинраз для каждого узла. Поэтому время, затрачиваемое на ПОСТРСОРТДЕРЕВА, имееттот же поря­док, что и сумма высот всех узлов. Но узлов высоты i не больше, чем />. Следовательно, общее время, затрачиваемое процедуройПОСТРСОРТДЕРЕВА, имеет порядок />in/2/>, т.е O(n)
Теперьможно завершить детальное описание алгоритма СОРТДЕРЕВОМ. Коль скоро элементымассива А преобразованы в сор­тирующее дерево, некоторые элементы удаляются изкорня по од­ному за раз. Это делается перестановкой А[1] и А[n] и последую­щим преобразованием A[1], А[2], ..., А[n — 1] в сортирующее дерево. Затемпереставляются А[1] и А[n — 1], а A[1], А[2], ..., А [п — 2]преобразуется в сортирующее дерево. Процесс продол­жается до тех пор, пока всортирующем дереве не останется один элемент. Тогда А[1], А[2], ..., А[n] — упорядоченная последова­тельность.
Алгоритм3.4. Сортдеревом
Вход.Массив элементов А[i], 1/>i/>n.
Выход.Элементы массива А, расположенные в порядке неубы­вания.
Метод.Применяется процедура ПОСТРСОРТДЕРЕВА, т. е. алгоритм 3.3. Наш алгоритмвыглядит так:
begin
ПОСТРСОРТДЕРЕВА;
For i/>n step -1 until2 do
Begin
переставитьА[1] и А[i];
ПЕРЕСЫПКА(i,i — 1)
End    end
Теорема3.6. Алгоритм 3.4 упорядочиваетпоследовательность из п элементов за время 0(n log п).
Доказательство. Корректность алгоритма доказывает­сяиндукцией по числу выполнений основного цикла, которое обозначим через m. Предположение индукции состоит втом, что по­сле m итераций список   A[n-m+1], ..., А [n] содержит m наи­больших элементов,расположенных в порядке неубывания, а спи­сок A[1], ..., А[n-m] образует сортирующее дерево. Деталидо­казательства оставляем в качестве упражнения. Время выполнения процедурыПЕРЕСЫПКА(1, i) есть 0(log i)- Следовательно, ал­горитм 3.4 имеет сложность О (n log i ).
Следствие. Алгоритм Сортдеревом имеет временнуюсложность O/>(nlog n)
3.5. БЫСТРСОРТ — УПОРЯДОЧЕНИЕ ЗА СРЕДНЕЕ ВРЕМЯ О(n log n)
До сихпор мы рассматривали поведение сортирующих алгорит­мов только в худшем случае.Для многих приложений более реа­листичной мерой временной сложности являетсяусредненное вре­мя работы. В случае сортировки с помощью деревьев решений мывидим, что никакой сортирующий алгоритм не может иметь сред­нюю временнуюсложность, существенно меньшую n 1оg n. Однако известны алгоритмы сортировки, которые работают вхудшем слу­чае сn2 времени, где с — некотораяпостоянная, но среднее время работы, которых относит их к лучшим алгоритмамсортировки. При­мером такого алгоритма служит алгоритм Быстрсорт, рассматривае­мыйв этом разделе.
Чтобыможно было рассуждать о среднем времени работы алгоритма, мы должныдоговориться о вероятностном распределе­нии входов. Для сортировки естественнодопустить, что мы и сде­лаем, что любая перестановка упорядочиваемойпоследовательности равновероятна в качестве входа. При таком допущении ужеможно оценить снизу среднее число сравнений, необходимых для упорядо­ченияпоследовательности из nэлементов.
Общийметод состоит в том, чтобы поставить в соответствие каж­дому листу v дерева решений вероятность бытьдостигнутым при данном входе. Зная распределение вероятностей на входах, можнонайти вероятности, поставленные в соответствие листьям. Таким образом, можноопределить среднее число сравнений, производи­мых данным алгоритмом сортировки,если вычислить сумму взятую по всем листьям дерева решений данного алгоритма, вко­торой рi —вероятность достижения i-голиста, а d/>, — его глубина. Это число называетсясредней глубиной дерева решений. Итак, мы пришли к следующему обобщению теоремы3.4.
Теорема3.7. Впредположении, что все перестановки п-элементной последовательности появляютсяна входе с равными вероят­ностями, любое дерево решений, упорядочивающеепоследователь­ность из п элементов, имеет среднюю глубину не менее log n!.
Доказательство. Обозначим через D (Т) сумму глубин листьев двоичногодерева Т. Пусть D (Т) — еенаименьшее значение, взятое по всем двоичным деревьям Т с m листьями. Покажем индук­цией по m, что D(m)/>m log m.
Базис,т. е. случай /п=1, тривиален. Допустим, что предположе­ние индукции верно длявсех значений m, меньших k. Рассмотрим дерево решений Т с и листьями. Оно состоит изкорня с левым подде­ревом Т с kлистьями и правым поддеревом T/>с k – 1листьями при некотором i, 1/>i/>k. Ясно, что
D(T)=i+D(T/>)+(k-i)+D(T/>)
Поэтомунаименьшее значение D (Т) даетсяравенством
D(k)=/>[k+D(i)+D(k-1)].  (3.1)
Учитываяпредположение индукции, получаем отсюда
D(k)/>k+/>[i logi+(k-i)log(k-i)]                                     (3.2)
Легкопоказать, что этот минимум достигается при i=k/2. Сле­довательно,D(k)/>k+k log /> =k log k
Такимобразом, D (m)/>m log m для всех m/>1.
Теперьмы утверждаем, что дерево решений Т, упорядочивающее n случайных элементов, имеет не меньше /г! листьев. Болеетого, в точности п\ листьев появляются с вероятностью 1/n! каждый, а остальные — свероятностью 0. Не изменяя средней глубины дерева Т можно удалить из него всеузлы, которые являются предками только листьев вероятности 0. Тогда останетсядерево Т' с n! листь­ями, каждый из которыхдостигается с вероятностью 1/п!.. Так как D(Т')/>n! log n!, то средняя глубина дерева Т' (азначит, и Т) не меньше (1/n!) n! log n! = log n!..
Следствие. Любая сортировка с помощью сравненийвыполняет в среднем не менее сп log n сравнений длянекоторой постоянной с>0.
Заслуживаетупоминания эффективный алгоритм, называемый Быстрсорт, поскольку среднее времяего работы, хотя и ограничено снизу функцией сn lоg n для некоторой постоянной с (как и увся­кой сортировки с помощью сравнений), но составляет лишь часть времениработы других известных алгоритмов при их реализации на большинствесуществующих машин. В худшем случае Быстрсорт имеет квадратичное время работы,но для многих приложений это не существенно.
Procedure БЫСТРСОРТ(S):
1.        if S содержит не больше одного элемента then return S
else
begin выбрать произвольный элемент a из S;
2.        пустьS1, S2 и S3 —последовательности элементов из S,
соответственноменьших, равных и больших а;
3.        return (БЫСТРСОРТ(S1), затем S2,затем БЫСТРСОРТ (S3))
end
Рисунок3.7. Программа Быстрсорт.
Алгоритм3.5. Быстрсорт
Вход.Последовательность S из n элементов aь a2,…, aп.
Выход.Элементы последовательности S,расположенные по порядку.
Метод.Рекурсивная процедура БЫСТРСОРТ определяется на рис. 3.7. Алгоритм состоит ввызове БЫСТРСОРТ(S).
Теорема3.8. Алгоритм 3.5.упорядочивает последовательность из п элементов за среднее время О (п log п).
Доказательство. Корректность алгоритма 3.5 доказы­ваетсяпрямой индукцией по длине последовательности S. Чтобы проще было анализировать время работы, допустим, чтовсе элементы в S различны. Этодопущение максимизирует размеры последова­тельностей S1 и S3,которые строятся в строке 3, и тем самым мак­симизирует среднее время,затрачиваемое в рекурсивных вызовах в строке 4. Пусть Т (n) — среднее время, затрачиваемоеалгоритмом БЫСТРСОРТ на упорядочение последовательности из n элементов. Ясно, что Т(0)=Т(1)=b для некоторой постоянной b.
Допустим,что элемент а, выбираемый в строке 2, является 1-м наименьшим элементом среди n элементов последовательности S. Тогда на два рекурсивных вызоваБЫСТРСОРТ в строке 4 тратится среднее время Т(i — 1) и Т (n — i) соответственно. Так как i равно­вероятно принимает любоезначение между 1 и n, а итоговое по­строениепоследовательности БЫСТРООРТ(S)очевидно занимает время cn длянекоторой постоянной с, то
T(n)/>cn+/>[T(i-1)+T(n-1)]для n/>2                       (3.3)
Алгебраическиепреобразования в (3.3) приводят к неравенству
T(n)/>cn+/>/>T(i)            (3.4)
Покажем,что при n/>2 справедливо неравенство Т (n)2с+2b непосредственно вытекает из (3.4). Для проведения шагаиндукции запишем (3.4) в виде
T(n)/>cn +/>+ />/>ki ln i  (3.5)
Так какфункция i ln i вогнута, легко показать, что
/>i lni /> />x ln x dx />/>                   (3.6)
Подставляя(3.6) в (3.5), получаем
T(n)/>cn + /> + kn ln n — />
Посколькуn/>2 и k=2с+2b, тосn+4 b/n/>kn/2. Таким образом, неравенство Т (n)/>kn 1n n следует из (3.7). 
Рассмотримдве детали, важные для практической реализации алгоритма. Первая — способ«произвольного» выбора элемента а в строке 2 процедуры БЫСТРСОРТ. Приреализации этого опера­тора может возникнуть искушение встать на простой путь,а именно всегда выбирать, скажем, первый элемент последовательности S. Подобный выбор мог бы оказатьсяпричиной значительно худшей работы алгоритма БЫСТРСОРТ, чем это вытекает из(3.3). После­довательность, к которой применяется подпрограмма сортировки,часто бывает уже «как-то» рассортирована, так что первый элемент малс вероятностью выше средней. Читатель может проверить, что в крайнем случае,когда БЫСТРСОРТ начинает работу на уже упо­рядоченной последовательности безповторений, а в качестве эле­мента а всегда выбирается первый элемент из S, в последователь­ности S всегда будет на один элемент меньше,чем в той, из которой она строится. В этом случае БЫСТРСОРТ требуетквадратичного числа шагов.
Лучшейтехникой для выбора разбивающего элемента в строке 2 было бы использованиегенератора случайных чисел для порожде­ния целого числа i, 1
Втораядеталь — как эффективно разбить S натри последова­тельности S1, S2 и S3? Можно (и желательно) иметь в массиве А все n исходных элементов. Так какпроцедура БЫСТРСОРТ вызы­вает себя рекурсивно, ее аргумент S всегда будет находиться в по­следовательныхкомпонентах массива, скажем A[f], A[f+1], ..., A[l] для некоторых f и l, 1S3— в A[k+1], A[k+2], ..., A[l] при некотором k, f/>k/>lЗатем можно, если нужно, расщепить S2/>S3, но обычно эффективнее просто рекурсивно вызвать БЫСТР­СОРТна S1 и S2/>S3, если оба этих множества не пусты.
По-видимому,самый легкий способ разбить S натом же месте — это использовать два указателя на массив, назовем их i и j. Вначале
1.    begin
2.    i/>f;
3.    whilei/>j do
begin
4.            whileA[i]>а и j>f do j/>j — 1;
5.            whileA[j]ldo i/>i + 1;
6.            if
begin
7.                   переставить А[i] и A[j];
8.                   i/>i + 1;
9.                   i/>j -1
end
еnd
еnd
Рис.3.8. Разбиение S на S1 и S2/>S3 на месте их расположения.
i=f, и все время в A [f], ..., А [i-1]будут находиться элементы из S1.Аналогично вначале i=f, а в A[j+1], ..., A[l] все время будут находиться элементы из S2/>S3.   Это разбиение производит подпрограмма на рис.3.8.
Затемможно вызвать БЫСТРСОРТ для массива A[f],… A[i—1], т.е. S1 и для массива A[j+1], ..., А[1], т.е. S2/>S3. Но если i=f то надо сначала удалить из S2/>S3хотя бы один элемент, равный а. Удобно удалятьтот элемент, по которому производилось разбиение. Следует также заметить, чтоесли это представление в виде массива применяется для последова­тельностей, томожно подать аргументы для БЫСТРСОРТ, просто поставив указатели на первую ипоследнюю ячейку используемого куска массива.
Пример3.5. Разобьем массив А1 2 3 4 5 6 7 8 9 6 9 3 1 2 7 1 8 3
по элементу а=3. while-оператор (строка 4) уменьшает j с 9 до 7, поскольку числа A[9]=3 и A[8]=8 оба не меньше а, но A[7]=1а. Поэтому мы переставляем A[1] и A [7], полагаем i=2, j=6 и получаем массив на рис. 3.9, а.Результаты, получаемые после следующих двух срабатываний цикла в строках 3—9,пока­заны на рис. 3.9, б и в. В этот момент i>j, ивыполнение while-опе­ратора, стоящего в строке 3,заканчивается.
a)1 9 3 1 2 7 6 8 3
/>/>i                     j
б)1 2 1 3 9 7 6 8 3
/>/>j     i
Рис.3.9. Разбиение массива.
 
2.2.4Вывод
Проделав индивидуальноезадание, были получены основные умения по набору текстового и графическогоматериала, приведя материал в соответствии с ГОСТ.
2.3 Средство обработкиинформации MSExcel
 
MS Exсel — мощноесредство обработки информации корпорации Майкрософт, которая имеет множествоутилит необходимых для набора и обработки информации.
2.3.1 Тема, задание,цель
Тема — работа с электронными таблицами MS Excel.
Цель — получить основные умения по работес электронными таблицами.
Задания индивидуальные врабочем порядке.
2.3.2 Исходные данныеи индивидуальное задание
Дан файл Excel, содержащий данные о студентахгруппы с указанием номера зачетки, ФИО студента, размера стипендии, годарождения и пола. На другом листе вывести список, упорядоченный по увеличениюстипендии. Форматирование и заполнение итоговых ячеек выполнить в модуле.
 
2.3.3 Отчет овыполнении
Отчетом о выполненииданного задания будет электронный вид листа excel,предоставленный руководителю практики. В данном отчете будет предоставлен рисунокработы exel файла, а также следующий пунктсодержит листинг модуля.
ФИО
Номер зачетной книжки
Стипендия
Год рождения
Пол Азаров Игорь 87934 150.5 16.10.1988 м Анцибор Наталья 87967 151.0 13.05.1988 ж Бандорчук Алексей 65477 143.5 03.07.1987 м Булавин Александр 77685 155.5 04.05.1988 м Гуляева Мария 67545 120.5 12.07.1989 ж Давыдова Екатерина 45654 160.0 01.07.1988 ж Дандыкин Александр 65465 130.0 23.12.1988 м Звада Инна 56765 110.0 25.11.1987 ж Калашников Максим 86985 123.5 19.10.1988 м Морчук Станислав 65365 143.0 25.10.1988 м Полярова Ксения 35676 150.0 13.05.1989 ж Солодовник Михаил 35686 147.0 18.08.1988 м Усенко Тарас 45676 159.5 23.11.1987 м
Рисунок 2.3.1 Лист Excel, содержащий данные о студентахгруппы с указанием номера зачетки, ФИО студента, размера стипендии, годарождения и пола.