User Rating: 5 / 5

Курсовая работа
Сбалансированные деревья

Основные понятия 3

Включение в сбалансированное дерево 5

Удаление из сбалансированного дерева 12

Заключение18

Задачи 18

Приложение 19

Основные понятия

Связанный граф без циклов называется деревом.
Определим терминологию деревьев:
• Корнем дерева называют единственную вершину, находящуюся вверху « первернутого » дерева;
• Самые нижние вершины называются листьями;
• Вершину называют внутренней, если она не является ни корнем, и ни листом;
• О вершине, которая находится непосредственно над другой вершиной, говорят, что она – родитель (предок), а вершина, которая расположена непосредственно под другой вершиной, называется потомком.

Считают, что корень дерева расположен на первом уровне. Его потомки находятся на втором и т.д. максимальный уровень какой – либо вершины дерева называется глубиной, или высотой дерева. Число потомков вершины называется ее степенью. Максимальное значение этих степеней есть степень дерева.
Суть двоичных деревьев, широко распространенных в программировании, следует из названия. Степень дерева равна двум. Вершина (узел) дерева может иметь не более двух потомков, их называют левыми и правыми. Двоичные (бинарные) деревья поиска (подкласс двоичных деревьев) характеризуются тем, что значение информационного поля, связанного с вершиной дерева, больше любого соответствующего значения из левого поддерева и меньше, чем содержимое любого узла его правого поддерева. Описание этой вершины имеет вид:
Type Ref = ^Item;
Item = Record
Key: Integer;
Left, Right: Ref; (0)
End;
С таким деревом можно легко осуществлять простейшие операции: вставка, удаление, обход дерева. Деревья упрощают оперирование с данными, поскольку имеют ряд преимуществ по сравнению с другими структурами данных, как то: динамический принцип выделения памяти под переменные, быстрый поиск переменной с нужным числовым полем и наглядность работы с переменными.
Двоичное дерево считается идеально сбалансированным, если для каждой его вершины количество вершин в его левом и правом поддеревьях различается не более чем на 1. Для одних и тех же данных, например, целых чисел от 1 до N (в зависимости от порядка их поступления в обработку), структура двоичного дерева поиска будет различной. Возможны варианты как от идеально сбалансированного дерева, так и до простого линейного списка, когда или все левые, или все правые ссылки узлов равны nil. Реализация операций восстановления идеальной сбалансированности при случайной вставке или удалении элемента из двоичного дерева поиска, разумеется, возможна, однако она не рассматривается в учебной литературе из-за ее сложности.
Рассмотрим сбалансированные деревья по тому определению, которое было предложено Г.М. Андельсоном – Вельским и Е.М. Ландисом в 1962г.

Критерий сбалансированности следующий
Дерево называются сбалансированным тогда и только тогда, когда для каждого узла высота его двух поддеревьев различается не более чем на единицу.
Деревья, удовлетворяющие этому условию, часто называют АВЛ-деревьями (по фамилиям их изобретателей). Будем называть их просто сбалансированными деревьями, так как их критерий сбалансированности оказывается наиболее подходящим. (Отметим, что все сбалансированные деревья так же являются АВЛ-сбалансированными.)
Это определение не только простое, но также приводит к легко выполнимой балансировке, а средняя длина поиска остается практически такой же, как у идеально сбалансированного дерева.
Со сбалансированными деревьями можно выполнять следующие операции за O(Log(n)) единицу времени даже в наихудшем случае:
1. Найти узел с данным ключом.
2. Включить узел с данным ключом.
3. Удалить узел с данным ключом.
Это является прямым следствием теоремы, доказанной Андельсоном – Вельским и Ландисом, которая утверждает, то сбалансированное дерево никогда не будет более чем на 45% выше соответствующего идеально сбалансированного дерева независимо от количества узлов. Если обозначить высоту сбалансированного дерева с n узлами через hb(n), то
log(n+1)<= hb(n)<=1.4404*log(n+2)-0.328 (1)
Разумеется, оптимум достигается, если дерево идеально сбалансировано, при n=2k-1. Но какова структура наихудшего АВЛ-сбалансированного дерева?
Чтобы найти максимальную высоту h всех сбалансированных деревьев с n узлами, возьмем фиксированное h и попробуем построить сбалансированное дерево минимальным количеством узлов. Такая стратегия рекомендуется, поскольку, как и в случае минимального h, это значение может быть достигнуто только при некоторых, определенных значениях n.

Рис. 1. Деревья Фибоначчи высотой 2,3 и 4.

Обозначим такое дерево с высотой h через Th. Очевидно, что T0 – пустое дерево, а T1- дерево с одним узлом. Чтобы построить дерево Th для h>1, зададим корень с двумя поддеревьями, которые также имеют минимальное число узлов. Следовательно, поддеревья также являются T – деревьями. Очевидно, что одно поддерево обязано иметь высоту h-1, а другому позволено иметь высоту на единицу меньше, т.е. h-2. на рис. 1 показаны деревья высотой 2, 3 и 4. Поскольку принцип их организации напоминает принцип построения чисел Фибоначчи, подобные деревья называют деревьями Фибоначчи. Они определяются следующим образом:
1. Пустое дерево есть дерево Фибоначчи с высотой 0.
2. Один узел есть дерево Фибоначчи с высотой 1.
3. Если Th-1 и Th-2 – деревья Фибоначчи с высотой h-1 и h-2, то Th=< Th-1, X, Th-2> есть дерево Фибоначчи с высотой h.
4. Никакие другие деревья не являются деревьями Фибоначчи.
Число узлов в Th определяется простым рекуррентным соотношением:
N0=0, N1=1, Nh= Nh-1+ Nh-2, (2)
Ni – это количество узлов, для которых можно получить наихудший случай (верхнюю границу h).

Включение в сбалансированное дерево

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

Рис.2. Сбалансированное дерево.

Возможны три случая:
1. hL= hR : L и R становятся неравной высоты, но критерий сбалансированности не нарушается.
2. hL< hR : L и R приобретают равную высоту, т.е. сбалансированность даже улучшается не нарушается.
3. hL> hR : критерий сбалансированности нарушается, и дерево нужно перестраивать.
Рассмотрим дерево на рис 2. Узлы с ключами 9 и 11 можно вставить без балансировки; дерево с корнем 10 становится односторонним (случай 1), а с корнем 8 улучшает свою сбалансированность (случай 2). Однако включение узлов с корнями 1, 3, 5 или 7 требует последующей балансировки.
При внимательном изучении этой ситуации можно обнаружить, что имеются лишь две существенно различные возможности, требующие индивидуального подхода. Оставшиеся могут быть получены симметричными преобразованиями этих двух. Случай 1 определяется включением ключа 1 или 3 в дерево на рис. 2, случай 2 – включением ключа 5 или 7.
Случай 1.                                                                                                     Случай 2.

Рис.3. Несбалансированность, возникающая при включении.

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

Случай 1.                                                                                                    Случай 2.

Рис. 4. Восстановление баланса.

Алгоритм включения и балансировки полностью определяется способом хранения информации о сбалансированности дерева. Крайнее решение состоит в хранении этой информации полностью неявно в самой структуре дерева. Но в этом случае показатель сбалансированности узла должен заново вычисляться каждый раз, когда узел затрагивается включением, что приводит к чрезвычайно высоким затратам. Другая крайность – явно хранить показатель сбалансированности в информации, связанной с каждым узлом. Тогда определение типа узла расширяется до
Type node = record
key: integer;
Count: integer;
Left, right: ref; (3)
Bal: -1..+1
End;

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

Хотя этот метод и требует некоторой избыточной проверки (если сбалансированность установлена, то для предков соответствующего узла ее проверять уже не надо), будем придерживаться этой, очевидно, корректной схемы, так как ее можно реализовать с помощью простого расширения уже разработанной процедуры поиска с включением из программы для идеально сбалансированных деревьев. Эта процедура описывает операцию поиска для каждого отдельного узла, и благодаря рекурсивной формуле ее можно дополнить операцией, выполняемой «по дороге назад вдоль пути поиска». На каждом шаге должна передаваться информация о том, увеличилась ли высота поддерева (в которое произведено включение). Поэтому добавим к списку параметров процедуры булевскую переменную h, означающую «высота поддерева увеличилась». Очевидно, что h должна быть параметром-переменной, поскольку используется для передачи результата.
Теперь предположим, что алгоритм возвращается к узлу с левой ветви (см. рис. 3) с указанием, что ее высота увеличилась. Мы должны различать три возможные ситуации в зависимости от высоты поддеревьев перед включением:
1. hL< hR : P^.bal=+1, предыдущая несбалансированности в p уравновешивается.
2. hL= hR : P^.bal=0 вес склонился влево.
3. hL> hR : P^.bal=-1, необходима балансировка.
В третьем случае показатель сбалансированности корня левого поддерева (P^.bal) определяет, который из случаев (1 или 2 на рис. 3) имеет место. Если левое поддерево этого узла тоже выше правого, то мы имеем дело со случаем 1, иначе – со случаем 2. (В этом случае левое поддерево корня не может иметь показатель сбалансированности, равный 0.) Необходимые операции балансировки полностью заключаются в обмене значениями ссылок (указателей, «поинтеров»). Фактически, ссылки обмениваются значениями по кругу, что приводит к однократному или двукратному «повороту» двух или трех узлов. Кроме «вращения» ссылок следует также изменить соответствующие показатели сбалансированности узлов. Подробно это показано в процедуре поиска, включения и балансировки (4).
Принцип работы алгоритма показан на рис. 5. Рассмотрим бинарное дерево (а), которое состоит только из двух узлов. Включение ключа 7 вначале дает несбалансированное дерево (т.е. линейный список). Его балансировка требует однократного правого (RR) поворота, давая в результате идеально сбалансированное дерево (b). Последующее включение узлов 2 и 1 дает несбалансированное поддерево с корнем 4. Это поддерево балансируется однократным левым (LL) поворотом (d). Далее включение ключа 3 сразу нарушает критерий сбалансированности в корневом узле 5. Сбалансированность теперь восстанавливается с помощью более сложного двукратного поворота налево и направо (LR), результатом является дерево (e). теперь при следующем включении потерять сбалансированность может лишь узел 5. Действительно, включение узла 6 должно привести к четвертому виду балансировки, описанному в (4): двукратному повороту направо и налево (RL). Окончательное дерево показано на рис. 5 (f). С эффективностью алгоритма включения в сбалансированное дерево связаны следующие два особо интересных вопроса:
1. Если все n! Перестановок n включений появляются с одинаковой вероятностью, то какова ожидаемая высота формируемого сбалансированного дерева?
2. Какова вероятность, что включение приведет к балансировке?

Приведем пример процедуры вставки узла в дерево.
Procedure Search(X:Byte; Var Q:Ref; Var H:Boolean); Создание сбалансированного дерева
Var Q1,Q2:Ref; H=False
Begin
If Q=Nil Then Слова нет в дереве, включить его
Begin
New(Q);
H:=True;
With Q^ Do
Begin Непосредственная процедура инициализации вершины
Key:=X;
Count:=1;
Left:=Nil;
Right:=Nil;
Bal:=0
End
End
Else
If X<q^.key then="" Если="" вставляемая="" величина="" меньше="" вершины,="" рекурсивно="" входим="" опять="" в="" нее,="" считая="" корнем="" уже="" следующую="" вершину="" и="" будем="" сравнивать="" включаемый="" элемент="" с="" ней.<br="">Begin
Search(X,Q^.Left,H);
If H Then Выросла левая ветвь
Case Q^.Bal Of
1:
Begin
Q^.Bal:=0;
H:=False;
End;
0: Q^.Bal:=-1;
-1: Необходима балансировка
Begin
Q1:=Q^.Left;
If Q1^.Bal=-1 Then
Begin Однократный LL-поворот
Q^.Left:=Q1^.Right;
Q1^.Right:=Q;
Q^.Bal:=0;
Q:=Q1;
End
Else Двукратный LR-поворот
Begin
Q2:=Q1^.Right;
Q1^.Right:=Q2^.Left;
Q2^.Left:=Q1;
Q^.Left:=Q2^.Right;
Q2^.Right:=Q;
If Q2^.Bal= -1 Then Q^.Bal:=+1 Else Q^.Bal:=0;
If Q2^.Bal=+1 Then Q1^.Bal:=-1
Else Q1^.Bal:=0;
Q:=Q2;
End;
Q^.Bal:=0;
H:=False
End
End
End
Else If X>Q^.Key Then Симметричную операцию проводим, если включаемый элемент больше значения корня. Рекурсивно вызываем процедуру Search для правого поддерева рассматриваемой вершины. для правого поддерева рассматриваемой вершины.
Begin
Search(X,Q^.Right,H);
If H Then Выросла правая ветвь
Case Q^.Bal Of
-1:
Begin
Q^.Bal:=0;
H:=False;
End;
0:Q^.Bal:=+1;
1 : Begin Балансировка
Q1:=Q^.Right;
If Q1^.Bal=+1 Then
Begin Однократный RR-поворот
Q^.Right:=Q1^.Left;
Q1^.Left:=Q;
Q^.Bal:=0;
Q:=Q1;
End
Else Двукратный RL-поворот
Begin
Q2:=Q1^.Left;
Q1^.Left:=Q2^.Right;
Q2^.Right:=Q1;
Q^.Right:=Q2^.Left;
Q2^.Left:=Q;
If Q2^.Bal=+1 Then Q^.Bal:=-1
Else Q^.Bal:=0;
If Q2^.Bal=-1 Then Q1^.Bal:=+1
Else Q1^.bal:=0;
Q:=Q2;
End;
Q^.Bal:=0;
H:=False;
End;
End;
End
Else
Begin
Q^.Count:=Q^.Count+1;
H:=False;
End;
End; Конец процедуры вставки элемента
(4)
Математический анализ этого сложного алгоритма пока не произведен. Эмпирические проверки показывают, что ожидаемая высота сбалансированного дерева, которое строится в (4), равна h=log(n)+c, где с – малая константа (с~0,25). Это значит, что на практике АВЛ-сбалансированные деревья ведут себя так же, как идеально сбалансированные деревья, хотя с ними намного легче работать. Эмпирически можно также предположить, что в среднем балансировка необходима приблизительно один раз на каждые два включения. При этом однократный и двукратный повороты одинаково вероятны. Понятно, что пример на рис. 5 явно был тщательно подобран, чтобы показать как можно больше поворотов при минимальном количестве включений.
Из-за сложности операций балансировки считается, что сбалансированные деревья следует использовать лишь в том случае, когда поиск информации происходит значительно чаще, чем включение. Это, в частности, верно потому, что узлы таких деревьев поиска обычно для экономии памяти реализуются как плотно упакованные записи. «Скорость» изменения показателей сбалансированности, занимающих только по два разряда каждый, и обращения к ним часто является решающим фактором, определяющим эффективность операции перебалансировки. Эмпирические оценки говорят, что сбалансированные деревья теряют большую часть своей привлекательности, если нужна плотная упаковка записи. Но это уже относится к разделу хранения информации непосредственно на компьютере, а не к ее представлению, поэтому не будем рассматривать проблемы, связанные с размахом хранения динамической информации на носителе.

Рис. 5. Включение в сбалансированное дерево.

Удаление из сбалансированного дерева

Представляя структуру сбалансированных деревьев, можем предположить, что удаление в случае сбалансированных деревьев будет еще более сложным, чем включение. Это верно, хотя операция балансировки остается в основном такой же, что и при включении. В частности, балансировка состоит из однократного или двукратного поворота узла.
Удаление из сбалансированного дерева показано на рис.6. Простыми случаями являются удаления терминальных узлов и узлов с одним потомком. Если же узел, который нужно удалить, имеет два поддерева, то, как и в обычных деревьях, будем заменять его самым правым узлом левого поддерева. Как и в случае включения (4), добавляется булевский параметр-переменная h, означающий, что «высота поддерева уменьшилась». Вопрос о перебалансировке рассматривается только при h=true. Значение true присваивается h при нахождении и удалении узла или если сама балансировка уменьшает высоту поддерева. В программе (5) в виде процедур вводим две (симметричные) операции балансировки, поскольку обращение к ним встречается более чем в одной точке алгоритма исключения. Отметим, что BalanceL используется при уменьшении высоты левого поддерева, а BalanceR – при уменьшении высоты правого.
Рис. 6 иллюстрирует работу нашей процедуры. Из исходного сбалансированного дерева (а) последовательно исключаются вершины с ключами 4, 8, 6, 5, 2, 1 и 7 и получаются деревья (b) .. (h).

Исключение ключа 4 выглядит просто, поскольку он представляет собой терминальную вершину. Однако в результате получается несбалансированная вершина 3. Соответствующая операция балансировки требует единственного (LL) – поворота. Удаление вершины 8 проходит без балансировки «с минимальными потерями» – ее физически заменяем ее полем left. При исключении вершины 6 вновь требуется балансировка. В этот момент одиночным (RR) – поворотом балансируется правое поддерево вершины 7. Удаление корня дерева 5 проходит «по сценарию» - заменяем его правым элементом из левого поддерева; «запас прочности» баланса нашего дерева еще терпит такую операцию. Исключение вершины 2, хотя само по себе простое, поскольку вершина имеет лишь одного потомка, приводит к усложненному двукратному (RL) – повороту. И четвертый случай: безболезненно удалив вершину 1, проведем двукратный (LR) – поворот при изъятии вершины 7, вместо которой вначале помещался самый правый элемент ее левого поддерева, т.е. вершина с ключом 3.

Рис.6. Исключение из сбалансированного дерева.

Приведем пример элемента программы, отвечающий за удаление элемента из дерева.
Procedure Delete(X:Integer; Var Q:Ref; Var H:Boolean); Удаление узла сбалансированного дерева
Var P:Ref; Значение H в данном случае будет False
Procedure BalanceL(Var Q:Ref; Var H:Boolean);
Var Q1,Q2:Ref; Проводится при H=True, левая ветвь стала короче
B1,B2:-1..1;
Begin Помня, что H, т.е. левая ветвь стала короче
Case Q^.Bal Of Дальнейшие действия осуществляем, исходя из значения показателя сбалансированности для данной вершины – поле Bal
-1:Q^.Bal:=0;
0:
Begin
Q^.Bal:=1;
H:=False;
End;
1: Трубуется балансировка
Begin
Q1:=Q^.Right;
B1:=Q1^.Bal;
If B1>=0 Then Однократный RR-поворот
Begin
Q^.Right:=Q1^.Left;
Q^.Left:=Q;
If B1=0 Then
Begin
Q^.Bal:=1;
Q1^.Bal:=-1;
H:=False;
End
Else begin
q^.bal:=0; q1^.bal:=0;
q:=q1;
end;
end
else Двукратный RL-поворот Begin
Q2:=Q1^.Left;
B2:=Q2^.Bal;
Q1^.Left:=Q2^.Right; Q2^.Right:=Q1;
Q^.Right:=Q2^.Left;
Q2^.Left:=Q;
If B2=+1 Then Q^.Bal:=-1 Else Q^.Bal:=0;
If B2=-1 Then Q1^.Bal:=+1 Else Q1^.Bal:=0; Q:=Q2;
Q2^.Bal:=0;
End;
End;
End; Конец процедуры балансировки по L
End;

Procedure BalanceR (Var Q:Ref; Var H:Boolean); При реализации данной процедуры всегда
Var Q1,Q2:Ref; H=True, правая ветвь стала короче
B1,B2: -1..1;
Begin Будем помнить, что H, правая ветвь стала короче
Case Q^.Bal Of
1:Q^.Bal:=0; Дальнейшие действия осуществляем, исходя из значения показателя сбалансированности для данной вершины – поле Bal

0:
Begin
Q^.Bal:=-1;
H:=False;
End;
-1: В этом случае необходима балансировка
Begin
Q1:=Q^.Left;
B1:=Q1^.Bal;
If B1<=0 Then
Begin Однократный LL-поворот Q^.Left:=Q1^.Right;
Q1^.Right:=Q;
If B1=0 Then
Begin
Q^.Bal:=-1;
Q1^.Bal:=1;
H:=False;
End
Else
Begin
Q^.Bal:=0;
Q1^.Bal:=0;
End;
Q:=Q1;
End
Else Двукратный LR-поворот
Begin
Q2:=Q1^.Right;
B2:=Q2^.Bal;
Q1^.Right:=Q2^.Left;
Q2^.Left:=Q1;
Q^.Left:=Q2^.Right;
Q2^.Right:=Q;
If B2=-1 Then Q^.Bal:=+1 Else Q^.Bal:=0;
If B2=+1 Then Q1^.Bal:=-1 Else Q1^.Bal:=0;
Q:=Q2;
Q2^.Bal:=0;
End
End
End
End; Конец балансировки по R– процедуры balanceR
Procedure Del(Var R:Ref;Var H:Boolean); Это, что называется, «чистая» процедура «физического» удаления.
Будем помнить, что при вызове процедуры восстанавливается значение H=False, и в этом режиме происходит удаление вершины
Begin
If R^.Right<>Nil Then
Begin
Del(R^.Right,H);
If H Then BalanceR(R,H)
End
Else
Begin
P^.Key:=R^.Key;
P^.Count:=R^.Count;
R:=R^.Left;
H:=True;
End
End; Конец подпроцедуры удаления – процедуры Del
Begin
If Q=Nil Then Ключа в дереве нет
Begin
WriteLn ( 'Дерево пусто');
H:=False;
End
Else
If X<q^.key then="" В="" зависимости="" от="" соотношений="" значений="" вершин,="" входим="" рекурсивно="" в="" левое="" или="" правое="" поддерево="" вершины,="" с="" целью="" найти="" удаляемый="" элемент.="" Рекурсивная="" процедура="" будет="" считать="" эту="" вершину="" корнем="" дерева.<br="">Begin
Delete(X,Q^.Left,H);
If H Then BalanceL (Q,H);
End
Else
If X>Q^.Key Then
Begin
Delete(X, Q^.Right, H);
If H Then BalanceR(Q,H)
End
Else
Begin Удаление Q^
P:=Q;
If P^.Right=Nil Then
Begin
Q:=P^.Left;
H:=True;
End
Else
If P^.Left=Nil Then
Begin
Q:=P^.Right;
H:=True;
End
Else
Begin
Del(P^.Left,H);
If H Then BalanceL(Q,H);
End;
End
End; Конец большой процедуры удаления
(5)
К счастью, исключение любого элемента из любого сбалансированного дерева можно в самом худшем случае провести за O(log(n)) операций. Однако не следует упускать из виду существенное различие в проведении процедур включения и исключения. В то время как включение одного ключа может привести самое большое к одному повороту (двух или трех вершин), исключение может потребовать поворотов во всех вершинах вдоль пути поиска. Рассмотрим, например, исключение из дерева Фибоначчи самой правой вершины.
В этом случае исключение любой одной вершины приводит к уменьшению высоты дерева, и кроме того, исключение самой правой вершины требует максимального числа поворотов. Таким образом, мы имеем дело с самой неудачной вершиной и самым неудачным случаем сбалансированного дерева – достаточно редкая комбинация. А вообще, какова вероятность поворотов? Визуально наблюдаем, что на каждые два включения встречается один поворот, а при исключении поворот происходит даже в одном случае из пяти. Поэтому исключение из сбалансированного дерева почти столь же просто или столь же сложно, что и включение.

Заключение

Анализируя алгоритм реализации работы со сбалансированными деревьями, предложенный Н. Виртом, приходим к выводу, что это достаточно экономная структура хранения данных, а тем более для современных ЭВМ.
Но возникает вполне естественный, и к тому же интересный вопрос: а не упростится ли логика, если в каждом узле ввести адрес связи к родителю?
В приложении к этой работе приведен пример программной реализации принципа сбалансированных деревьев описанным выше методом. Рассмотрим же некоторые задачи, представляющие интерес при работе с данной структурой.

Задачи

Для самостоятельной работы можно придумать задачи, связанные с вставкой, удалением, сменой местами элементов по ключам или ветвям.
1. Проверить наличие заданного элемента в дереве.
2. Подсчет суммы элементов дерева.
3. Определение наибольшего (наименьшего) элемента в дереве.
4. Подсчет количества элементов в дереве.
5. Сравнение двух деревьев.
6. Определение высоты дерева.
7. Определить количество нечетных чисел.
8. Вычислить сумму элементов дерева, кратных 3.
9. Определить число вершин в дереве на каждом уровне.
10. Число вершин в правом и левом поддеревьях определенной вершины.
11. Построить дерево с 12 узлами, чтобы его высота была максимальной. В какой последовательности нужно вводить элементы, чтобы наша процедура сформировала это дерево?
Рассмотрим последний пример немного подробнее.
Рассмотрим такую последовательность включения элементов: 10, 5, 20, 30, 3, 6, 15, 2, 13, 25, 35, 40. Сразу сознаемся, что это подобранный пример. Составленный таким образом. Что включая элементы именно в такой последовательности, получим максимальную длины дерева с 12 элементами – 4. Этот факт не требует доказательства, так как элементы вставлялись постоянно вправо, но с тем расчетом, чтобы постоянно поддерживать балансировку во всех узлах дерева. Как и прежде. Длина правого и левого поддерева отличается на каждом этапе не более чем на 1.
А алгоритм формирования нужного нам дерева прост: нужно вводить его элементы построчно, так как оно выглядит у Вас на бумаге

Литература

1. Вирт Н., - Алгоритмы + структуры данных = программы, - М.: Мир, 1985.
2. Вир Н., Алгоритмы и структуры данных, - М., 1989.
3. Кондратьева С.Д., - Введение в структуры данных, - М.: Издательство МГТУ им. Баумана, 2000.
4. Окулов С.М., - Основы программирования. Часть 4: учебное пособие, - Киров, Издательство ВГПУ, 2001.

Приложение

Пример программного кода для реализации работы со структурой данных «Сбалансированные деревья» по схеме, предложенной в [1].
Program Example;
Uses CRT;
Const N=10;
Type Ref=^Item; Описываем поля вершин дерева
Item=Record
Key: Byte;
Count:Byte;
Left:Ref ;
Right:Ref ;
Bal:-1..1;
End;
Var Q,L,R:Ref; Используемые при работе переменные
X,Y,C,Xc:Byte;
J,K:Integer;
H:Boolean;
Ch:Char;
Level:Integer;

Procedure WriteTreel (Q:Ref ) ; Вывод дерева на экран
Var X,Y,S,T,B,ZeroX,ZeroY,Labl,Line,R:Integer;
Procedure Init;
Var Bin:Integer;
Begin
Bin:=1;
Repeat Bin:=Bin*2 Until (N Div Bin)=0;
Labl:=Round(Bin/2)*6;
Line:=1 ;
ZeroX:=Round((80-Labl-3)/2) ;
ZeroY:=5;
R:=Round(Labl/2);
End;
Procedure OutTree (Q:Ref; R,Line:Integer);
Var I:Integer;
Begin
X:=ZeroX+R;
Y:=ZeroY+Line;
GotoXY(X,Y);
Write (Q^.Key);
Delay(10);
Line:=Line+1;
B:=1;
If Q^.Left <> Nil Then
Begin
For I:=1 To Line Do B:=B*2;
S:=R-Round(Labl/B);
OutTree (Q^.Left,S,Line);
End;
If Q^.Right<>Nil Then
Begin
For I:=1 To Line Do B:=B*2;
T:=R+Round(Labl/B);
OutTree(Q^.Right,T,Line);
End;
End;
Begin
Init;
OutTree(Q,R,Line);
End;
Procedure Search(X:Byte; Var Q:Ref; Var H:Boolean); Создание сбалансированного дерева
Var Q1,Q2:Ref; H=False
Begin
If Q=Nil Then Слова нет в дереве, включить его
Begin
New(Q);
H:=True;
With Q^ Do
Begin Непосредственная процедура инициализации вершины
Key:=X;
Count:=1;
Left:=Nil;
Right:=Nil;
Bal:=0
End
End
Else
If X<q^.key then="" Если="" вставляемая="" величина="" меньше="" вершины,="" рекурсивно="" входим="" опять="" в="" нее,="" считая="" корнем="" уже="" следующую="" вершину="" и="" будем="" сравнивать="" включаемый="" элемент="" с="" ней.<br="">Begin
Search(X,Q^.Left,H);
If H Then Выросла левая ветвь
Case Q^.Bal Of
1:
Begin
Q^.Bal:=0;
H:=False;
End;
0: Q^.Bal:=-1;
-1: Необходима балансировка
Begin
Q1:=Q^.Left;
If Q1^.Bal=-1 Then
Begin Однократный LL-поворот
Q^.Left:=Q1^.Right;
Q1^.Right:=Q;
Q^.Bal:=0;
Q:=Q1;
End
Else Двукратный LR-поворот
Begin
Q2:=Q1^.Right;
Q1^.Right:=Q2^.Left;
Q2^.Left:=Q1;
Q^.Left:=Q2^.Right;
Q2^.Right:=Q;
If Q2^.Bal= -1 Then Q^.Bal:=+1 Else Q^.Bal:=0;
If Q2^.Bal=+1 Then Q1^.Bal:=-1
Else Q1^.Bal:=0;
Q:=Q2;
End;
Q^.Bal:=0;
H:=False
End
End
End
Else If X>Q^.Key Then Симметричную операцию проводим, если включаемый элемент больше значения корня. Рекурсивно вызываем процедуру Search для правого поддерева рассматриваемой вершины. для правого поддерева рассматриваемой вершины.
Begin
Search(X,Q^.Right,H);
If H Then Выросла правая ветвь
Case Q^.Bal Of
-1:
Begin
Q^.Bal:=0;
H:=False;
End;
0:Q^.Bal:=+1;
1 : Begin Балансировка
Q1:=Q^.Right;
If Q1^.Bal=+1 Then
Begin Однократный RR-поворот
Q^.Right:=Q1^.Left;
Q1^.Left:=Q;
Q^.Bal:=0;
Q:=Q1;
End
Else Двукратный RL-поворот
Begin
Q2:=Q1^.Left;
Q1^.Left:=Q2^.Right;
Q2^.Right:=Q1;
Q^.Right:=Q2^.Left;
Q2^.Left:=Q;
If Q2^.Bal=+1 Then Q^.Bal:=-1
Else Q^.Bal:=0;
If Q2^.Bal=-1 Then Q1^.Bal:=+1
Else Q1^.bal:=0;
Q:=Q2;
End;
Q^.Bal:=0;
H:=False;
End;
End;
End
Else
Begin
Q^.Count:=Q^.Count+1;
H:=False;
End;
End; Конец процедуры вставки элемента
Procedure Delete(X:Integer; Var Q:Ref; Var H:Boolean); Удаление узла сбалансированного дерева
Var P:Ref; Значение H в данном случае будет False
Procedure BalanceL(Var Q:Ref; Var H:Boolean);
Var Q1,Q2:Ref; Проводится при H=True, левая ветвь стала короче
B1,B2:-1..1;
Begin Помня, что H, т.е. левая ветвь стала короче
Case Q^.Bal Of Дальнейшие действия осуществляем, исходя из значения показателя сбалансированности для данной вершины – поле Bal
-1:Q^.Bal:=0;
0:
Begin
Q^.Bal:=1;
H:=False;
End;
1: Трубуется балансировка
Begin
Q1:=Q^.Right;
B1:=Q1^.Bal;
If B1>=0 Then Однократный RR-поворот
Begin
Q^.Right:=Q1^.Left;
Q^.Left:=Q;
If B1=0 Then
Begin
Q^.Bal:=1;
Q1^.Bal:=-1;
H:=False;
End
Else begin
q^.bal:=0; q1^.bal:=0;
q:=q1;
end;
end
else Двукратный RL-поворот Begin
Q2:=Q1^.Left;
B2:=Q2^.Bal;
Q1^.Left:=Q2^.Right; Q2^.Right:=Q1;
Q^.Right:=Q2^.Left;
Q2^.Left:=Q;
If B2=+1 Then Q^.Bal:=-1 Else Q^.Bal:=0;
If B2=-1 Then Q1^.Bal:=+1 Else Q1^.Bal:=0; Q:=Q2;
Q2^.Bal:=0;
End;
End;
End; Конец процедуры балансировки по L
End;

Procedure BalanceR (Var Q:Ref; Var H:Boolean); При реализации данной процедуры всегда
Var Q1,Q2:Ref; H=True, правая ветвь стала короче
B1,B2: -1..1;
Begin Будем помнить, что H, правая ветвь стала короче
Case Q^.Bal Of
1:Q^.Bal:=0; Дальнейшие действия осуществляем, исходя из значения показателя сбалансированности для данной вершины – поле Bal

0:
Begin
Q^.Bal:=-1;
H:=False;
End;
-1: В этом случае необходима балансировка
Begin
Q1:=Q^.Left;
B1:=Q1^.Bal;
If B1<=0 Then
Begin Однократный LL-поворот Q^.Left:=Q1^.Right;
Q1^.Right:=Q;
If B1=0 Then
Begin
Q^.Bal:=-1;
Q1^.Bal:=1;
H:=False;
End
Else
Begin
Q^.Bal:=0;
Q1^.Bal:=0;
End;
Q:=Q1;
End
Else Двукратный LR-поворот
Begin
Q2:=Q1^.Right;
B2:=Q2^.Bal;
Q1^.Right:=Q2^.Left;
Q2^.Left:=Q1;
Q^.Left:=Q2^.Right;
Q2^.Right:=Q;
If B2=-1 Then Q^.Bal:=+1 Else Q^.Bal:=0;
If B2=+1 Then Q1^.Bal:=-1 Else Q1^.Bal:=0;
Q:=Q2;
Q2^.Bal:=0;
End
End
End
End; Конец балансировки по R– процедуры balanceR
Procedure Del(Var R:Ref;Var H:Boolean); Это, что называется, «чистая» процедура «физического» удаления.
Будем помнить, что при вызове процедуры восстанавливается значение H=False, и в этом режиме происходит удаление вершины
Begin
If R^.Right<>Nil Then
Begin
Del(R^.Right,H);
If H Then BalanceR(R,H)
End
Else
Begin
P^.Key:=R^.Key;
P^.Count:=R^.Count;
R:=R^.Left;
H:=True;
End
End; Конец подпроцедуры удаления – процедуры Del
Begin
If Q=Nil Then Ключа в дереве нет
Begin
WriteLn ( 'Дерево пусто');
H:=False;
End
Else
If X<q^.key then="" В="" зависимости="" от="" соотношений="" значений="" вершин,="" входим="" рекурсивно="" в="" левое="" или="" правое="" поддерево="" вершины,="" с="" целью="" найти="" удаляемый="" элемент.="" Рекурсивная="" процедура="" будет="" считать="" эту="" вершину="" корнем="" дерева.<br="">Begin
Delete(X,Q^.Left,H);
If H Then BalanceL (Q,H);
End
Else
If X>Q^.Key Then
Begin
Delete(X, Q^.Right, H);
If H Then BalanceR(Q,H)
End
Else
Begin Удаление Q^
P:=Q;
If P^.Right=Nil Then
Begin
Q:=P^.Left;
H:=True;
End
Else
If P^.Left=Nil Then
Begin
Q:=P^.Right;
H:=True;
End
Else
Begin
Del(P^.Left,H);
If H Then BalanceL(Q,H);
End;
End
End; Конец большой процедуры удаления
Основная программа.
В комментариях не нуждается.
Begin
Repeat
ClrScr;
GotoXY(4,7);
WriteLn('Меню');
WriteLn;
WriteLn('1. Добавить элемент в дерево');
WriteLn('2. Вывести дерево на экран');
WriteLn('3. Удаление узла');
WriteLn('4. Выход');
GotoXY(1,17);
WriteLn('Нажмите нужную цифру');
Ch:=ReadKey;
Case Ch Of
'1':
Begin
СlrScr;
WriteLn('Вводите цифры, по окончании нажмите 0');
Repeat
ReadLn(C);
if c <> 0 then Search(C,Q,H);
Until C=0;
X:=255;
Level:=1;
End;
'2' :
Begin
ClrScr;
WriteTreel(Q);
ReadLn;
End;
'3' :
Begin
ClrScr;
C:=100;
WriteLn('Вводите удаляемые узлы, по окончанию нажмите 0: ') ;
While C<>0 Do
Begin
WriteLn('Введите удаляемый узел');
ReadLn(C);
if c <>0 then Delete(C,Q,H);
End;
X:=35;
Level:=12;
End;
End;
Until(Ch='4');
End.

User Rating: 2 / 5

Курсовая работа
на тему :
«Теория массового обслуживания».

Содержание:
1.Модели массового обслуживания
1.1.Задачи, связанные с обслуживанием очередей -3
1.2.Функционирование моделей систем массового обслуживания -4
1.3.Описание математической модели -5
2.Система обслуживания с пуассоновским потоком на входе и выходе.
2.1.Система массового обслуживания со специальными свойствами -7
2.2.Входной поток -8
2.3.Выходной поток -10
2.4.Верификация пуассоновского закона распределения при анализе реальных систем -12
3.Системы массового обслуживания при наличии входного и выходного потоков.
3.1.Типы структур систем массового обслуживания -12
3.2.Операцинные характеристики систем массового обслуживания -14
3.3. Модель(M/M/1):(GD//) -15
3.4. Модель(M/M/1)(GD/N/) -16
4.Литература. -18

1. Модели массового обслуживания

1.1. Задачи, связанные с обслуживанием очередей

В окружающей нас действительности много реально протекающих процессов обслуживания на транспорте, в торговле, в медицине, в связи и т.д. Все они могут быть изучены, исходя из соответствующих им моделей систем обслуживания. Создание систем телефонной связи и необходимость расчета их пропускной способности послужили в 20-х годах ХХ века стимулом раз¬вития теории массового обслуживания. Первые исследования группы Operations research британских ВВС была посвящена решению задач этой же тема¬тики (очередь самолетов противника, которая обслуживается снарядами зе¬нитных батарей)~ С 1970-х годов интенсивно разрабатываются методы анали¬за и оптимизации процессов обслуживания требований на вычисления с ис¬пользованием одного или нескольких компьютеров (системы разделенного времени).

Представим себе несколько ситуаций:

—очередь покупателей возле касс продовольственного магазина;

—скопление больных, ожидающих своей очереди на прием к врачу;

—группу самолетов, ожидающих разрешения на взлет в крупном аэропор-ту;

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

Все приведенные ситуации объединяет одно общее обстоятельство: пре-бывание в состоянии ожидания. Избавиться от этого в принципе невозможно. Можно лишь надеяться на возможность сокращения времени ожидания до некоторого «приемлемого» предела. Явление ожидания является следствием того, что ни время возникновения потребностей в обслуживании, ни продол¬жительность обслуживания поступившего в обслуживающую систему клиента обычно заранее неизвестны. В математическую модель, адекватно описывающую ситуации, аналогичные приведенным, включается предположение, что входящий поток требований на обслуживание является случайным. Иными словами, последовательность моментов времени поступления требова¬ний (t~,}, рассматривается как последовательность случайных величин. Требо¬вания на обслуживание характеризуются объемом (или длительностью) работы по обслуживанию и могут относиться к определенным классам. Принадлежность требований (клиентов) к определенным классам могут служить основанием для приоритетного обслуживания. Требования, имеющие абсолютный приоритет, обслуживаются в первую очередь. Например, некоторые виды отказов в вычислительных системах имеют абсолютный приоритет и«обслуживание» таких отказов состоит в их выявлении и устранении.
Для правильного описания вероятностного закона функционирования обслуживающей системы необходимо выделить некоторые количественные характеристики (параметры) обслуживающей системы, ее описывающие. Одной из традиционных характеристик обслуживающей системы является время пребывания в очереди на обслуживание другой характеристикой системы массового обслуживания может служить доля времени, в течение которого находящаяся в функциональной готовности система из-за отсутствия заявок находится в состоянии бездействия (простаивает). Первая характеристика оценивает систему с позиции клиента. Вторая — с позиции загруженности системы. Интуитивно ясно, что чем большее время затрачивает клиент в ожидании обслуживания, тем меньше время, которое система проводит в состоянии бездействия, и, наоборот. Варьируя операционные характеристики обслуживающей системы, можно добиться разумного компромисса клиентов с обслуживающей системой.

1.2. Функционирование моделей систем массового обслуживания

На обслуживающую систему поступают требования (заявки на обслуживание), которые присоединяются к очереди других (ранее поступивших) требований. Обслуживающий узел выбирает одно (из очереди) требование‚ чтобы приступить к его обслуживанию. После завершения процедуры обслужи¬вания ~поступившего из очереди требования система приступает к обслуживанию следующего требования (если таковое есть в блоке ожидания). Цикл функционирования такого рода системы многократно повторяется. При этом предполагается, что переход от обслуживания одного требования к другому происходит мгновенно (без какой-либо задержки).

Основными элементами системы массового обслуживания являются требования (заявки на обслуживание) и механизм обслуживания (обслуживающая система). Основной количественной характеристикой в моделях массо¬вого обслуживания является продолжительность h интервала времени, которое требуется для полного обслуживания i-ого требования с момента ti его поступления в обслуживающую систему до момента ti+h — завершение обслуживания. для характеристики самой обслуживающей системы (собственно обслуживание без ожидания в очереди) достаточно ввести показатель, характеризующий время, расходуемое на обслуживание одного требования.

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

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

—первый пришел — первым обслуживается (собственно очередь);

—пришел последним — первым обслуживается (стек);

—случайный отбор требований из очереди;

—обслуживание в соответствии с уровнем приоритета.

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

1.З. Описание математической модели

Характеристика входного потока. Обозначим через Рn(t) вероятность наступления n событий (поступлений требований на обслуживание в обслуживающую систему) в интервале времени, длина которого равна t. Среднее число поступающих заявок (требований на обслуживание) в единицу времени будем обозначать  (интенсивность поступления требований).

Характеристика выходного потока. Пусть Qn(t) — вероятность того, что в течение t единиц времени из системы выбывает n клиентов (после завершения их обслуживания). Процесс выбывания такого рода называют процессом чистой гибели. Интенсивность выбывания обслуженных клиентов обозначим

 - среднее число обслуженных клиентов в единицу времени.

Если предположить (это обычно делается при разработке математической модели), что длина интервала времени, в течение которого наступает каждое последнее событие, не зависит от времени, требуемого для реализации пред-шествующего события, то можно определить функцию f(t) — плотность вероятности того, что длина интервала времени между последовательными наступлениями случайного события (поступление требования на обслуживание) равняется t единиц времени (t0). Так ~как функция f(t) является плотностью распределения вероятностей, то

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

где P{tT} вероятность того, что интервал времени реализации случайного события не менее Т, а Р0(Т) — вероятность того, что в течение времени Т не реализуется ни одного события.

Поскольку f(t) — плотность вероятности того, что интервал времени между последовательными реализациями случайного события равняется t, то
Поэтому выполняются следующие равенства:
Таким образом, 1-F(T) = -Р0(Т), (Т>О).
Дифференцируя правую и левую части последнего неравенства по верхнему пределу Т. получаем

Из теории вероятностей известно, что при заданной плотности распределения вероятностей f(t) наступления случайного события можно найти математическое ожидание (среднее значение) этой случайной величины по формуле

Величина М{Т} — среднее значение временных интервалов между двух последовательных реализаций события. Таким образом, интенсивность потока требований  (среднее количество требований, поступающих в единицу времени) есть величина обратная М(Т), то есть

= 1/М(Т).

Пусть g(t) — плотность вероятности того, что длина интервала времени между двумя последовательными наступлениями случайного события (завершение обслуживания одного клиента) равна t. Тогда, рассуждая аналогично тому, что мы только что сделали (вместо f(t) ~ g(t)), можно найти выражение для f1(t), если известны плотности Qn(t). Точнее, получим:

В последних равенствах М1(Т) — среднее значение временных интервалов между двумя последовательными обслуживаниями, а — интенсивность потока обслуживания (среднее количество обслуживаний в единицу времени).
Понятно, что возможность полного расчета характеристик системы обслуживания возможен лишь для конкретных случаев обслуживающих систем(задание функций Рn(t) и Qn(t)). Наиболее хорошо изучена система обслужи¬вания, состоящая из одного обслуживающего канала, в который поступает пуассоновский поток требований интенсивности , а на выходе — пуассоновский поток обслуженных интенсивности .

2. Система обслуживания с пуассоновским потоком на входе и на выходе.

2.1. Система массового обслуживания со специальными свойствами.

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

Свойство 1. Процессы поступления требований на обслуживание и выбытия обслуженного клиента имеют стационарный характер (стационарный процесс). Это означает, что вероятность наступления событий (на входе и на выходе) в интервале [t, t+h] зависит лишь от h, то есть вероятность такого события не зависит ни от количества событий, ни от момента времени t.

Свойство 2. Для бесконечно малого значения длины интервала h вероятность реализации события больше нуля, но меньше единицы.

Свойство 3. На бесконечно малом отрезке времени h реализуется не более одного события.
Свойство 1 означает, что события равновероятны и независимы. Отсюда по теореме умножения вероятностей при n = 0 следует, что

Р0(t+h) = Р0(t).Р0(h).

Вычитая из правой и левой частей последнего равенства величину P0(t), поделив левую и правую части на h, сгруппировав члены левой и правой частей равенства нужным образом, получим равенство, тождественное исходному

(Р0(t+h) — Р0(t))/h = - [(1 – Р0(h))/h].Р0(t).

Перейдя в последнем равенстве к пределу при h 0 и обозначив через  величину Р0(t) (производная от Р0(t) в точке 0), получим
P0(t)= - P0(t)

По свойству З выполняется равенство Р0(0)=1. Таким образом, получили обыкновенное дифференциальное уравнение с начальным условием, которое математически описывает свойства 1—З. Решение этого уравнения хорошо известно — P0(t)=e-t, t0
Для достаточно малых значений h имеем разложение в ряд Тейлора

В силу свойства 3

Р1(h)= 1 - Р0(h)h

Последнее равенство означает, что вероятность реализации в интервале времени длины h (h - мало) одного события (одно требование на обслуживание) прямо пропорциональна h (коэффициент пропорциональности ).

Сделаем некоторые выводы:

1. Используя результаты п.б.1.З.; при Po(t)=е-t, получаем, что плотность вероятности f(t) того, что длина интервала времени между двумя случайными событиями равна Т, имеет экспоненциальный вид, то есть

f(T) = - Р0(Т) =  ехр(-Т), (T>0).

2. Математическое ожидание случайной величины Т, распределенной экспоненциально равно М{Т}=1/ (единиц времени). Тогда среднее число требований в единицу времени (интенсивность потока требований) будет равна =, поэтому в дальнейшем, когда будем говорить о плотности экспоненциального распределения интервалов времени между двумя последовательными требований на обслуживание с интенсивностью  будем записывать
f(T)=.ехр(-Т).

Аналогично, в случае, когда временные интервалы между двумя обслуженными клиентами распределены по экспоненциальному закону, плотность такого распределения будем записывать в виде

g(T)= exp(- t)

где  (единиц обслуженных клиентов) — интенсивность исходного потока, которая равна =1/М1 (М1 (единиц времени) — математическое ожидание величины интервала времени между двумя событиями). -

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

P{t>T+s 1 Рs} = P{t>T+s, t>~}IР(t)~s) = Р(t)~Т+s}/Р{t>s) =

= exp(—a.(T+s))Iexp(--a.s) exp(—wT) = Р {t>T}.

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

2.2. Входной поток

В предыдущем пункте был рассмотрен случайный процесс с <чистыми поступлением требований, для которого характерно, что поступившее в систему требование присоединяется к очереди и не покидает ее до тех пор, пока не будет обслужено. Такие процессы называют процессами чистого рожде¬ния. Найдем аналитические представления Р~(t) для процесса чистого рожде¬ния с экспоненциальным распределением вероятностей интервалов времени между двумя последовательными поступлениями требований на обслужива¬ние.

Для сколь угодно малого, но не равного нулю интервала h при n>0, имеем

n поступлений в течение t единиц времени и ни
одного поступления в интервале h
Рn(t+h) = или
n-1 поступление в течение t единиц времени и
одно поступление в интервале h.

Применяя теоремы сложения и умножения вероятностей, получаем Рn(t+h) = Рn(t).Ро(h) + Рn-1(t)*Р1(h), n=1,2,...

Po(t+h) = Р0(t).Р0(h)

Так как Р0(h) = ехр(-*h), Р1(h) = 1- Р0(h)=1 - ехр(-*h), то для малых значений h можно написать приближенные равенства
• Р0(h)= 1 –*h, Р1(h)=*h,
Р0(t+h)= Р0(t)*(1-*h).
Последние равенства перепишем в следующем виде:
[Рn(t+h)- Рn(t)]/h=- *Рn(t) + *Pn-1(t)
• [Р0(t+h)- Po(t)]/h=- *Ро(t)
При h0 эти равенства становятся точными и переходят в разностно--дифференциальные уравнения
Pn(t)=-  *Pn(t)+ *Pn-1(t),n>0,
Р0 (t)==- *P0(t).
Решение последнего уравнения нам известно Po(t) = ехр(- *t). В теории разностно-дифференциальных уравнений с постоянными коэффициентами хорошо изучены полученные уравнения (n>О). Их решениями являются сле-дующие функции
Pn(t)=[( *t)n* exp(- *t)]/n,n=1,2...
Убедиться в справедливости написанных представлений функций Рn(t) можно непосредственной подстановкой их в соответствующие уравнения.
В теории вероятностей распределение вероятностей Рn(t) известно как распределение Пуассона. Среднее значение (математическое ожидание) этого распределения равно *t.
Итак, если временные интервалы между моментами двух последовательных событий распределены по экспоненциальному закону с интенсивностью, то число поступлений требований на обслуживание в интервале времени t единиц времени характеризуется пуассоновским распределением со средним значением равным *t.
Пример 6.1. Найти математическое ожидание и дисперсию для распреде-ления вероятностей (Пуассона)
Рn(t)=[( *t)n*ехр(-*t)]/n!, n=0,1,2,...
Решение. В начале заметим, что справедливы два равенства
M[t] =п*Pn(t)= (n-1)*( *t)n-1 *ехр(*t)/(n-1)! = *t
и (*t)n-1*exp(-*t)/(п-1)! = ехр(-*t)*ехр(*t) = 1.
Чтобы установить справедливость этих равенств, достаточно вспомнить разложение функции ехр(*t) в ряд Тейлора-Маклорена

ехр(*t)=1 + (*t)/1! + (*t)2/2! + ...+ (*t)n/n! +....
Первое приведенное равенство — математическое ожидание распределе¬ния Пуассона. Найдем дисперсию D[t]. Известно, что величину дисперсии можно найти по формуле
D[tI=а2—М2[t],
где а2 — второй начальный момент. Найдем а2.

а2 =n2(*t)*ехр(-*t)/n! = (*t )n(*t)n-1ехр(-*t)/(n-1)! =(*t)[(n-1)+1]* (*t)n-1*exp(-*t)/(n-1)!=
=( *t)*[(n-1)*( *t)n-1*exp(*t)/(n-1)!+( *t)n-1 *exp(*t)/(n-1)!]
Первая сумма в квадратных скобках равна *t, а вторая — равна 1, поэтому D[t]= (*t)2+(*t)-( *t)2=(*t).

Следслвие. Дисперсия дискретной случайной величины, распределенной по закону Пуассона, равна математическому ожиданию этой величины, то есть D[t] = M[t] =(*t). Отметим, что это уникальное свойство распределения Пуассона. Ни одно другое дискретное распределение случайной величины не обладает этим свойством. для предварительного суждения о том, является ли данное распределение пуассоновским, по эмпирическим данным достаточно
вычислить математическое ожидание и дисперсию. Если с удовлетворитель¬ной точностью математическое ожидание и дисперсия при этом совпадают, то можно быть уверенным в том, что оно пуассоновское.

2.3. Выходные потоки

Процесс на выходе системы массового обслуживания рассматривают в предположении, что система начинает функционировать при наличии ,в ней N клиентов, которые после обслуживания выбывают из системы с интенсив-ностью  (экспоненциальное распределение интервалов времени). Процессы такого рода называют процессами "чистой"гибели.
К категории процессов "чистой" гибели относится, например, изъятие из склада хранимых в нем запасов. В этом случае предполагается, что на складе имеется N единиц запасов, которые изымаются с интенсивностью  (единиц запасов в единицу времени).
При условии абсолютной случайности исходов для малого интервала h можно записать (так же как и в случае <чистого~ рождения)
Q0(h) = exp(-*h)=1-*h, Q1(h) = 1 - Q0(h)- *h=1-*h для величин Qn(t+h) имеют место следующие соотношения:
Qn(t+h)=Qn(t)*1 + Qn-1(t)( *h),
Qn(t+h)= Qn(t)(1-*h) + Qn-1(t)*( *h), n = N-1, N—2,. ..,1,
Qo(t+h)= Q0(t)*(1- *h).
Написанные приближенные равенства можно переписать в следующемвиде:

[QN(t+h)-QN(t)]/h=*QN-1(t),
[Qn(t+h) –Qn(t)]/h=-*Qn-1(t), n=N-l, N-2,...,1,
[Qo(t+h)- Qo(t)]/h =-*Qo(t).
Перейдя к пределу при h0, получаем систему разностно-дифференциальных уравнений
QN(t)= *QN-1(t),
Qn(t) =-*Qn(t)+ *Qn-1(t), n=N-1,N-2,...,1,
Q0(t) =-*Qo(t).
Второе и третье разностно-дифференциальные уравнения имеют единст-венные решения
Qn(t)=[ (*t)n*exp(-*t)]/n!, n=0,1,2,..,N-1
Решение первого уравнения задается формулой
QN(t)=1-Qn(t).
Чтобы убедиться, что написанные формулы действительно являются ре-шениями приведенных разностно-дифференциальных уравнений, достаточно продифференцировать их и подставить в соответствующее уравнение.

Напомним, что Qn(t) — это вероятность n единиц выбывания в течение t единиц времени. Часто интерес представляет вероятность того, что по исте-чении t единиц времени в системе остается n заявок на обслуживание (n кли-ентов). Обозначим эту вероятность Rn(t). Тогда, если предположить, что в начальный момент времени число находящихся в системе клиентов (заявок на обслуживание) равнялось N, то будем иметь
Rn(t) =QN-n(t)
Откуда следует, что

Rn(t) = [(*t)N-n*exp(-*t)]/(N-n)!, n = 1,2,..,N.
Ro(t) = 1 Rn(t).

Пример. В начале каждой недели складируется 15 единиц запасов, ко¬торые в течение недели расходуются. Изъятия запасов из складского поме¬щёния происходят лишь в первые шесть дней каждой недели и осуществляется в соответствии с пуассоновским распределением со средней интенсив¬ностью = 3 (единиц запасов в 1 рабочий день). Как только уровень запасов снижается до пяти единиц, делается новый заказ на поставку в конце недели пятнадцати единиц запасов. Запасы по своей природе таковы, что все неис¬пользованные до конца недели предыдущие запасы приходят в негодность исписываются (ликвидируются).

Исследование ситуации. Учтем, что средняя интенсивность потребления =3 (единиц в 1 день).
Вычислим вероятность того, что уровень запасов понизится до пяти еди¬ниц в t-й день. Вероятность такого события вычисляется по формуле
R5(t)= [(3t)15-5*ехр(-3t)]/(15—5)! = [(3t)10*exp(-3t)]/10! t=1,2,...,6.
Результаты для определенных значений t сведены в таблицу

По условиям примера R5(t) есть вероятность возникновения необходимо¬сти формирования в t-й день нового заказа на пополнение склада пятнадца¬тью единицами запасов. Эта' вероятность достигает наибольшего значения при t =3, а затем постепенно падает по мере возрастания t (от t=4 до t=6).

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

Rn<=5(t) = R0(t) + R1(t) +.. + R5(t)=1-[R1(t)+R2(t)+..+R15(t)]+R1(t)+..+R5(t)=1-[R6(t)+R7(t)+..+R15(t)]=
=1-15n=6(3t)15-n*exp(-3t)/(15-n)!.

Вычисления, проведенные по последней формуле, сведены в таблицу

Из таблицы видно, что вероятность возникновения необходимости делать новый заказ в t-й день монотонно возрастает.
В рассматриваемой ситуации необходимо также вычислить среднее число единиц запасов, которые будут по негодности ликвидироваться в конце неде¬ли. Это можно сделать, если вычислить математическое ожидание числа ос-тавшихся не Изъятыми из склада единиц запасов в конце шестого дня:

М{n | t=h} = n*Rn(6) = 0.5537 (единиц).

Это означает, что в конце недели в среднем обесценивается (идет на вы¬брос) меньше одной единицы запасов.

2.4. Верификация пуассоновского закона распределения при анали¬зе реальных систем.

Очень• важно иметь практически осуществимый алгоритм проверки гипо-тезы о том. Что входной или выходной поток действительно является пуас-соновским. Самыми простыми способами установления этого факта являют¬ся следующие:

1.. Организуется наблюдение за уже функционирующей сис¬темой массового обслуживания в течение некоторого времени с це¬лью выяснения являются ли поступления требований (или акты выбытия обслуженных клиентов) действительно случайными собы¬тиями. Если входной (или выходной) поток оказывается случайным, то это уже позволяет выдвинуть гипотезу о пуассоновском характе¬ре поступления требований на обслуживание (или выбывания об¬служенных клиентов из рассматриваемой системы).
2. Собирается информация о количестве заявок на обслужи¬вание, поступивших в систему в течение первого часа, второго часа и т.д. Аналогичная процедура, может осуществляться и на выходе системы массового обслуживания. Затем вычисляется среднее зна¬чение интервала времени между двумя последовательными поступ¬лениями требований (математическое ожидание) или соответст¬вующие характеристики на выходе. Кроме математического ожида¬ния вычисляется дисперсия соответствующей случайной величины. Если вычисленные две характеристики случайной величины оказы¬ваются приблизительно одинаковыми, то с уверенностью можно считать, что мы имеем дело с распределением Пуассона.

3. Системы массового обслуживания при наличии входного и вы-ходного потоков.

3.1. Типы структур систем массового обслуживания.

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

Заметим, что в любой произвольный момент времени всех находящихся клиентов можно разбить на тех. Кто находится в очереди (ждёт когда его начнут обслуживать) и тех, кто уже обслуживается.
В настоящее время для характеристики любой системы массового обслу-живания приняты стандартные обозначения. восходящие к Д.Г. Кендаллу(1953 г). Они имеют следующую структуру:
(а / b / с): (d / е / f ),
где символы а, b, c, d, e, f характеризуют некоторые существенные элементы модельного представления процессов массового обслуживания.

а — тип распределения моментов поступлений заявок на обслуживание;

b— распределение времени обслуживания (или выбывания обслуженных клиентов);

с — число параллельно функционирующих узлов обслуживания(с=1,2,...,);

d — дисциплина очереди;

е — максимальное число допускаемых в систему требований (Число требо-ваний в очереди + число требований, принятых на обслуживание);

f— емкость источника, генерирующего заявки на обслуживание.

для конкретизации а и Ь приняты следующие стандартныё обозначения:

М — пуассоновское распределение моментов поступлений заявок на об-служивание или выбывания из системы, обслуженных клиентов (или экспо-ненциальное распределение интервалов времени между моментами последо-вательных поступлений требований или Продолжительностей обслуживания клиентов);

D — фиксированный (детерминированный) интервал времени обслужива-ния одного клиента.

Например, структура (М /D/10): (GD/N/) означает, что речь идет о системе массового обслуживания с пуассоновским входным потоком, фикси¬рованным временем обслуживания и десятью параллельно функционирующими узлами обслуживания. дисциплина очереди не регламентирована Что подчеркивается парой символов GD. Кроме того, независимо от того, сколь¬ко требований поступает на вход обслуживающей системы, данная система(очередь + обслуживаемые клиенту) не может вместить более N требований(клиентов), то есть клиенты, не попавшие в блок ожидания, вынуждены об¬служиваться в другом месте. Наконец, источник, порождающий заявки на обслуживание, имеет неограниченную емкость.

Напомним, что под дисциплиной очереди понимаются три возможные принципа, заложенные в порядок обслуживания очереди:
— «первым пришел — первым обслужен (собственно очёредь);

— «последним пришел — первым обслужен (стек);

— случайный выбор заявок из очереди;

— выбор заявок из очереди в соответствии с некоторым приорите-том.

Целью анализа систем и процессов массового обслуживания является разработка критериев эффективности функционирования систем массового обслуживания. Поскольку процесс массового обслуживания .Протекает во времени, постольку он может быть неустановившимся (переходным) или стационарным. Неустановившийся процесс — это процесс, при котором пове-дение системы продолжает оставаться функцией времени. Процессы чистого рождения и чистой гибели всегда относятся к категории неустановившихся стохастических процессов. В системах массового обслуживания, в которых происходит, с одной стороны, поступление заявок на обслуживание, а с дру¬гой — обслуженные клиенты выбывают из системы, в начальный период функционирования всегда наблюдается неустановившийся режим, а по исте-чении достаточно большого периода времени устанавливается стационарный режим. Однако, если интенсивность () поступления требований на обслу-живание превышает интенсивность выходного потока (), то стационарный режим оказывается недостигаемым, то есть очередь со временем будет по-стоянно увеличиваться.

3.2. Операционные характеристики систем массового
обслуживания

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

pn — вероятность того, что в системе находятся n клиентов (заявок на об-служивание);

Ls — среднее число находящихся в системе клиентов (заявок на обслужи-вание);

Lq — среднее число клиентов в очереди на обслуживание;

Ws — средняя продолжительность пребывания клиента (заявки на обслу-живание) в системе;

Wq — средняя продолжительность пребывания клиента (заявки на обслу-живание) в очереди.

По определению
Ls=n*pn, Lq=(n-c)*pn.

Между Ls и Ws (между Lq и Wq) существует строгая зависимость. В част-ности, если частота поступлений заявок в систему равняется , то мы имеем
Ls= *Ws,Lq=*Wq
В случае, когда не все заявки имеют возможность попасть в обслужи-вающую систему (из-за небольшой вместимости блока ожидания), приведен¬ные соотношения надо видоизменить путем введения нового значения пара¬метра эфф, которое позволило бы учесть только действительно попавшие в систему требования. Определим это значение следующим образом

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

Ls=эфф*Ws, Lq=эфф*Wq.
В общем случае
эфф=*,0<<1.

Это означает, что только часть поступающих требований на обслужива¬ние действительно попадают в систему.
Если средняя скорость обслуживания равняется  в час, следовательно, средняя продолжительность обслуживания равняется 1/ и тогда справедли¬во соотношение.
Ws=Wq+ 1/.

Умножая левую и правую части этого неравенства на , получаем
Ls = Lq + / .
Последнее равенство остается справедливым и в случае замены  на эфф. При этом будет
Ls=Lq+ эфф/,или эфф=(Ls-Lq).

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

pnLs=n*pnWs=Ls/Wq=Ws-1/Lq=*Wq

3.3. Модель (M/ M/ 1): (GD//).

В этой модели имеется единственный узел обслуживания, а на вмести¬мость блока ожидания и емкость источника требований никаких ограничений не накладывается. Входной и выходной потоки являются пуассоновскими с параметрами  и  соответственно.
Сначала выведем уравнения для Pn(t) — вероятностей того, что в интервале времени t в системе находится n требований (клиентов). Выберем достаточно малое значение h>0. Тогда вероятность Pn(t+h) (вероятность поступления в
систему n>О требований в интервале (t+ h) складывается из следующих веро-ятностей:

1. В конце временного интервала t в системе находится n тре-бований, а в интервале h не происходит ни поступлений, ни выбы-вании.

2. В конце временного интервала t в системе находится (n-1) требований, а в интервале h происходит одно поступление, но не происходит ни одного выбывания.

3. В конце временного интервала t в системе находится (n+1) требований, а в интервале h не происходит ни одного поступления, но происходит одно выбывание.

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

Рn(t+h) =Рn(t)*(1-(*h))(1-(*h)) + Рn-1(t)(*h)( 1-(*h)) +Pn-1(t)*(1-(*h))(*h),n>0.

В последнем равенстве мы воспользовались тем, что при малых h>0 име¬ют место следующие представления вероятностей:
(1-*h ) — вероятность того, что в интервале h нет ни одного поступле¬ния;
(1-*h)  вероятность того, что в интервале h нет ни одного выбыва¬ния;

(*h) — вероятность того, что в интервале h только одно поступление;
(*h) — вероятность того, что в интервале h только одно выбывание. для n=0 вероятность того, что в интервале h не произойдет ни одного вы¬бывания, очевидно, равна единице.
Следовательно, Р0(t+h)=Р0(t)*(1-(*h) ) + Р1(t)*( *h)( 1-(*h)) группировав соответствующим образом члены написанных приближен¬ных равенств, разделив их на h и перейдя к пределу при h0, получим сле¬дующие дифференциально-разностные уравнения

Pn = *Pn-1(t) +*Рn+1(t) - (+)*Рn(t), n>0,

Po(t) = -*Р0(t) +*Р1(t), n=0.

В принципе написанная система разностно-дифференциальных уравнений разрешима, и поэтому она задает некоторый стохастический процесс (Pn(t)), который не обязательно стационарен. Однако, решения этой системы, выпи-санные в явном виде, весьма громоздки.
Можно доказать, что при < существует стационарный процесс, то есть при t существует решение полученной системы разностно¬-дифференциальных уравнений, не зависящее от t. В этом случае, очевидно, будут иметь место предельные переходы

Pn'(t)0, Pn(t)  pn ,t).
Осуществив предельный переход при t  в системе разностно¬-дифференциальных уравнений, приходим к равенствам
-*p0+*p1=0,n=0,
*pn-1+*pn+1-(+)*pn=0,n>0.

В математике полученные уравнения называются разностными. для раз-ностных уравнений с постоянными коэффициентами полностью разработана теория и известны способы представления их решений. Для нашего разност-ного уравнения решения таковы Pn=(1-)*n,n=0,1,2,.., где через  обозначена величина =/<1. Чтобы убедиться в справедливо¬сти представления решения, достаточно подставит его в разностное уравне¬ние.
Полученное распределение вероятностей pn=(1-)*n в теории вероят¬ностей называется геометрическим распределением.
Выражение для Ls получается путем элементарных преобразований:
Ls=n*pn=n*(1-)*n=(1-)**d/d*(1/(1-))=/(1-).
Заметим, что ряд n сходится как сумма бесконечной убывающей геометрической прогрессии со знаменателем <1 .
Используя выведенные ранее формулы, получаем Ls=М= *(1-), Lq =Ls-/=2/(1-),

Ws=Ls/=1/[(1-)], Wq=/[(1-)].

3.4. Модель (М/ М/ 1): (GD/N/)

Разница между моделью (М/М/1):(GD/N/) и уже рассмотренной мо¬делью (М/М/1):(GD//) заключается в том, что максимальное число требований, допускаемых в блок ожидания, равняется N (то есть максимальна длина очереди есть N-1). В результате эффективная частота эфф поступ¬лений требований становится меньше частоты  с которой заявки на обслу¬живание генерируются соответствующим источником.
Разностно-дифференциальные уравнения для n=0 и для 0N имеем Рn(t) =0, а для n = N можно написать

PN(t + h)=PN(t)*1*(1-*h) +PN-1(t)*(*h)*(1-(*h)).

Таким образом, для установившегося процесса в модели (М/М/1):(GD//) разностные уравнения имеют вид

-*p0+p1=0,-pn+*pN-1=0,
-(1+)*pn+pn+1+*pn-1=0,0<n<n.
Решение этого разностного уравнения имёет вид:

Следует отметить, что значение параметра =/ не обязательно меньше единицы, как это требовалось в модели (М/ М/ 1): (GD//). Это следует из того, что число допускаемых в систему требований контролируется путем введения ограничения на длину очереди (которая не может превышать N-1),

а не соотношением между интенсивностями входного и выходного потоков есть не отношением /.
С учетом формул для pn находим

Выражения для Lq, Ws, Wq можно получить из формулы для Ls если предварительно вывести формулу эфф. Поскольку вероятность того, что требование не имеет возможности присоединиться к очереди, равна рn(то есть вероятность того, что в системе уже находится N требований) доля тре¬бований, которым разрешено войти в блок ожидания, равняется

P{n<n}= 1-Рn.<br="">Отсюда следует, что

эфф=*(1-pN),
Wq=Lq/эфф =Lq/[*(1 —pN)],
Ls= Lq + эфф / = Lq +*(1-pN)/,
Ws=Wq+ 1/ =Ls/[*(1-pN)].

Таким образом, еще раз убедились, что

эфф = *(Ls-Lq) = *(1-pN).

Литература:

1. В.А.Онегов «Исследование операций».
2. Х.Хата «Введение в исследование операций» (том 2).
3. Е.С.Вентцель «Теория вероятностей».

Курсовая учебник яинформационных автоматизированных систем

Введение

I. Методические рекомендации по разработке электронного учебника.

1.1. Электронный учебник как новый вид учебной литературы

1.2. Основные формы электронного учебника

1.3. Дидактические требования к электронному учебнику

1.4. Психологические требования к электронному учебнику

II. Анализ этапов разработки и принципы создания электронного учебника

2.1. Принципы создания электронного учебника

2.2. Этапы разработки электронного учебника

III. Разработка электронного учебника «Основы проектирования автоматизированных информационных систем»

Заключение

Список литературы

Введение

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

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

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

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

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

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

Исходя из вышесказанного, я считаю важной тему: "Электронные учебники".

Цель – разработать удобный и простой в использовании электронный учебник.

Задачами данной работы является:

1. Изучение литературы по созданию электронного учебника, по языку программирования, использованного в работе.

2. Систематизирование накопленных сведений по данной теме.

3. Разработка электронного учебника.

Методические рекомендации по разработке электронного учебника.

1.1.Электронный учебник — новый жанр учебной литературы

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

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

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

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

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

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

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

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

1.2. Основные формы электронного учебника

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

1. Тест. Внешне, это простейшая форма электронного учебника.

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

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

3. Задачник. Задачник в электронном учебнике наиболее естественно осуществляет функцию обучения. Термин задачник не должен вводить в заблуждение. Задачник может быть и по гуманитарным дисциплинам.

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

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

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

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

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

1.3.Дидактические требования к электронным учебникам

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

О возможности повышения уровня реализации традиционных дидактических требований при создании электронных учебников

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

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

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

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

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

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

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

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

1.4.Психологические требования к электронным учебникам

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

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

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

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

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

Использование возможностей современной компьютерной техники позволяет легко управлять вниманием студентов с помощью следующих приемов: изменение цвета, яркости, масштабов изображений на экране, перемещение объектов и т.п.

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

Эргономические аспекты информационных технологий освещены в литературе в большей степени. В.П. Зинченко и Г.Я. Узилевский предлагают эргосемиотический подход к исследованию пользовательского интерфейса, обеспечивающий его системное исследование, проектирование и реализацию. Они считают плодотворным использовать прагматические и семантические аспекты семиотики для определения общих требований к пользовательскому интерфейсу.

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

Для борьбы со зрительным и мышечным утомлением рекомендуются, в частности, такие меры: 15 минут из каждого часа работы должны быть отданы активному отдыху. При этом общая продолжительность работы с компьютером не должна превышать 5 часов, а перерывы должны быть заполнены релаксационными упражнениями для глаз и скелетно-мышечного аппарата. Также рекомендуется разнообразить характер деятельности пользователя, например, можно чередовать работу с текстами и с движущимися объектами.

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

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

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

• единственности - .....;

• симметричности - асимметричности отображаемой информации; ......

• зависимости между числом и размерами окон: ......

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

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

На основании вышеизложенного сформулированы две группы психологических требований к электронным учебникам:

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

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

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

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

Анализ этапов разработки и принципы создания электронного учебника

2.1.Принципы создания электронного учебника

Принципы создания электронного учебника включают в себя:

1. Принцип квантования: разбиение материала на разделы, состоящие из модулей, минимальных по объему, но замкнутых по содержанию.

2. Принцип полноты: каждый модуль должен иметь следующие компоненты

o теоретическое ядро,

o контрольные вопросы по теории,

o примеры,

o задачи и упражнения для самостоятельного решения,

o контрольные вопросы по всему модулю с ответами,

o контрольная работа,

o контекстная справка (Help),

o исторический комментарий.

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

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

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

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

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

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

2.2. Этапы разработки электронного учебника

На первом этапе разработки электронного учебника целесообразно подобрать в качестве источников такие печатные и электронные издания, которые

• наиболее полно соответствуют стандартной программе,

• лаконичны и удобны для создания гипертекстов,

• содержат большое количество примеров и задач,

• имеются в удобных форматах (принцип собираемости).

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

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

На четвертом этапе перерабатываются тексты источников в соответствии с оглавлением, индексом и структурой модулей; исключаются тексты, не вошедшие в перечни, и пишутся те, которых нет в источниках; разрабатывается система контекстных справок (Help); определяются связи между модулями и другие гипертекстные связи.

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

На пятом этапе гипертекст реализуется в электронной форме.

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

На шестом этапе разрабатывается компьютерная поддержка: определяется, какие математические действия в каждом конкретном случае поручаются компьютеру и в какой форме должен быть представлен ответ компьютера; проектируется и реализуется ИЯ; разрабатываются инструкции для пользователей по применению интеллектуального ядра ЭУ для решения математических задач (правила набора математических выражений и взаимодействия с ИЯ).

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

Интеллектуальное ядро целесообразно сделать так, чтобы его можно было заменять на более мощный компьютерный пакет типа DERIVE, Reduce, MuPAD, Maple V и т.п.

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

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

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

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

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

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

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

Разработка электронного учебника «Основ проектирования автоматизированных информационных систем»

На первом этапе создания электронного учебника «Основы проектирования Автоматизированных Информационных систем » был проведен анализ литературы, содержащей информацию по выбранной теме, которая соответствует стандартной программе, лаконичной и удобной для создания гипертекстов т.к содержат множество тем в главах.

Для наполнения электронного учебника были выбраны следующие пособия:

1. Проектирование АИС / Н. М. Абдикеев, Н.З.Емельянова, Т. Л. Партыка, В. П. Романов; Под ред. К. И. Курбакова. М.: Изд-во Рос. экон. акад., 2004. 145 с.

2. ВасилевичЛ., Зиновьев С, Молотков Л. Онлайновый доступ к базам данных международной информационной сети STN International // Информационные ресурсы России. 1996. Вып. 4-5. С. 36-38.

3. Информационные ресурсы и документальные базы данных. Создание, использование, анализ: Учеб. пособие / Е. Н. Васина, О.Л.Голицына, Н.В.Максимов, И.И.Попов. М: РГГУ, 1997. 178 с.

4. Гайдамакин Н. А. Автоматизированные информационные системы, базы и банки данных. Вводный курс: Учеб. пособие. М.: Гелиос, 2002. 368 с.

5. Голицына О. Л., Максимов Н. В., Попов И. И. Базы данных: Учеб. Пособие. М.: ФОРУМ: ИНФРА-М, 2003, 352 с.

6. Голицына О. Л., Попов И, И. Основы алгоритмизации и программирования: Учеб. пособие. М.: ФОРУМ: ИНФРА-М, 2002. 432 с.

7. Горностаев Ю. М., Поляк Ю. Е. (ред). Русский Интернет. 7500 Webs. М.: ЦЭМИ РАН, МЦНТИ, 1998. 155 с,

8. ГОСТ 34.201-89. Виды, комплектность и обозначение документов при создании автоматизированных систем. М.: Изд-во стандартов, 1991. 43 с.

9. ГОСТ 34.601-90. Информационная технология. Комплекс стандартов на автоматизированные системы. Автоматизированные системы. Стадии создания. М.: Изд-во стандартов, 1991. 37 с.

10. ГОСТ 34.602-89. Техническое задание на создание автоматизированной системы. М.: Изд-во стандартов, 1991. 25 с.

11. и т.д.

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

• Информация и информационные системы.

• Базовые типы информационных систем.

• Технологии проектирования автоматизированных информационных систем.

• Автоматизированные информационные системы по областям применения.

Главы в свою очередь содержат множество контрольных вопросов по каждой теме.

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

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

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

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

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

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

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

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

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

На восьмом этапе произвел визуализацию текстов, т.е. компьютерное воплощение разработанных сценариев с использованием рисунков, графиков и, возможно, анимации.

При создании электронного учебника потребовалось изучить программный продукт Macromedia Dreamweaver 8, язык Hyper Text Markup Language (HTML - является стандартным языком, предназначенным для создания гипертекстовых документов в среде WEB). С его помощью было написано множество команд и процедур для электронного пособия.

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

Заключение

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

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

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

Тема учебника «Основы проектировании автоматизированных информационных систем». В связи с этим рассмотрены и описаны основные разделы и понятия и расположены в таком порядке, чтобы удобно было пользоваться.

Основные положения и результаты опыта могут быть использованы любым учителем информатики (или учеником).

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

Литература

1. Богословская Н.В., Бржезовский А. В., Жаков В.И., Фильчиков В.В. Системы автоматизации разработки программного обеспечения. Учебное пособие. – СПб.: СПВУРЭ ПВО, 1996.

2. Дьяконов Е.Г. Минимизация вычислительной работы. – М.: Наука, 1989.

3. Голицына О. Л., Попов И. И. Основы алгоритмизации и программирования: Учеб. пособие. М.: ФОРУМ: ИНФРА-М, 2002. 432 с.

4. Карасев П.Н. Задачи по информатике – Волгоград: учебное пособие для учащихся и учителей средних учебных заведений, 2002г.–116с.: ил.

5. Окулов С.М. Основы программирования. Ст. из газеты «информатика», 2000, №42, 43, 45, 46, 47, 2001, №6, 7, 8, 9, 10, 11.

6. Орлов С.А. Технологии разработки программного обеспечения – СПб: «Питер», 2002г.

7. Рудаков А. В. Технология разработки программных продуктов: Учеб. пособие для студ. сред. проф. Образования. – М.: Издательский дом «Академия», 2005. – 208 с.

8. Рассохин Д., Лебедев А. World Wide Web - всемирная информационная паутина в сети Internet– М.: учебное пособие для учащихся и учителей средних учебных заведений, 2002г.–187с.: ил.

9. Фуфаев Э.В., Фуфаева Л.И. Пакеты прикладных программ: Учеб. Пособие для сред, проф. Образования. – М.: Издательский центр «Академия», 2004. – 352с.

10. Фаронов В.В. Практика программирования. Учебное пособие. 1997.