Пример 2. Деки

1) Предметная область "Формирование железнодорожного состава".

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

3) В предметной области решаются задачи одного класса. Постановка задач данного класса.

Дано: пришедший состав, состоящий из вагонов.

Найти: уходящий состав.

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

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

6) Прикладная логическая теория имеет название "Сортировка вагонов". При ее построении используются стандартное расширение ST и специализированное расширение "Последовательности". Запишем теорию на языке прикладной логики.

Формирование составов(ST, Последовательности)

6.1) сорт вагоны: {}N

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

6.2) сорт пункт назначения: (вагоны ® {А, В})

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

6.3) составы º seq вагоны

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

6.4) сорт пришедший состав: составы

моделью объема понятия, обозначенного термином "пришедший состав" является бесконечное множество, являющееся значением термина "составы

6.5) сорт уходящий состав: составы

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

6.6) n º length(пришедший состав)

значением термина "n" является значение длины пришедшего состава

6.7) сорт процесс сортировки: (I[0,n] ® (составы Ý 3))

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

6.8) p(1, процесс сортировки(0)) = пришедший состав

6.9) p(2, процесс сортировки(0)) = L

на первом шаге сортировки в тупике находится пришедший состав, а двухсторонний путь пуст

6.10) уходящий состав = p(2, процесс сортировки(n))

уходящий состав – это состав, полученный на двухстороннем пути в результате процесса сортировки

6.12) (v: I[1,n]) процесс сортировки(v) = <head(p(1, процесс сортировки(v-1))), / (пункт назначения(last(p(1, процесс сортировки(v-1))) = A Þ addend(p(3, процесс сортировки(v-1)), last(p(1, процесс сортировки(v-1))))) (пункт назначения(last(p(1, процесс сортировки(v-1))) = B Þ addbeg(p(3, процесс сортировки(v-1)), last(p(1, процесс сортировки(v-1))))/>

7) Запишем программу на алгоритмическом языке программирования Паскаль.

program сортировка_вагонов;

type составы = ^ вагоны;

вагоны = record

номер вагона: integer;

пункт_назначения: char;

следующий: составы;

предыдущий: составы;

end;

var начало_уходящего: составы,

конец_уходящего: составы,

начало_пришедшего: составы;

конец_пришедшего: составы;

текущий_вагон: составы;

все_вагоны: byte;

процесс_сортировки: record

конец_первого: составы;

начало_второго: составы;

конец_второго: составы;

end;

function head(конец_состава: составы): составы;

begin

head:= конец_состава.предыдущий;

head^.следующий:= nil;

end;

procedure addbeg(var начало_состава: составы;

добавляемый: составы);

begin

добавляемый.следующий:= начало_состава;

начало_состава:= добавляемый;

начало_состава.предыдущий:= nill;

end;

procedure addend(var конец_состава: составы;

добавляемый: составы);

begin

добавляемый.предыдущий:= конец_состава;

конец_состава:= добавляемый;

конец_состава.следующий:= nill;

end;

begin

{ ввод информации о пришедшем составе }

writeln('введите информацию о вагонах пришедшего состава');

все_вагоны:= 2;

конец_пришедшего:= nil;

начало_пришедшего:= nil;

while все_вагоны = 2 do

begin

write('номер вагона и пункт назначения:');

new(текущий_вагон);

with текущий_вагон^ do

readln(номер вагона, пункт_назначения);

addend(конец_пришедшего, текущий_вагон);

if начало_пришедшего = nil

then начало_пришедшего:=

конец_пришедшего;

writeln('все вагоны? 1 – да, 2 – нет ');

readln(все_вагоны);

end;

процесс_сортировки.конец_первого:= конец_пришедшего;

процесс_сортировки.начало_второго:= nil;

процесс_сортировки.конец_второго:= nil;

while процесс_сортировки.конец_первого <> nil do

if процесс_сортировки.конец_первого.пункт_назначения = 'A'

then

begin

текущий_вагон:= процесс_сортировки.конец_первого;

процесс_сортировки.конец_первого:=

head(процесс_сортировки.конец_первого);

addend(процесс_сортировки.конец_третьего,

текущий_вагон);

end

else

if процесс_сортировки.конец_первого.пункт_назначения = 'B'

then

begin

текущий_вагон:= процесс_сортировки.конец_первого;

процесс_сортировки.конец_первого:=

head(процесс_сортировки.конец_первого);

addbeg(процесс_сортировки.начало_третьего,

текущий_вагон);

end;

начало_уходящего:= процесс_сортировки.начало_второго;

конец_уходящего:= процесс_сортировки.конец_второго;

end;

Литература

1. А.С.Клещев. Основы анализа и формализации информации. Лекции по курсу. Электронный вариант. 2001.

2. Ф.Л.Бауэр, Г.Гооз. Информатика. Вводный курс: В 2-х частях. М:Мир, 1990.

3. В.А.Успенский, А.Л.Семенов. Теория алгоритмов: основные открытия и приложения. М: Наука, Гл. ред.физ.мат.лит., 1987, 288 с.

4. А.С.Клещев, И.Л.Артемьева. Необогащенные системы логических соотношений. Ч.1. // Научно-техническая информация. Сер.2. Информ. процессы и системы, 2000, № 7, с. 18-28.