ОСНОВЫ АНАЛИЗА И ФОРМАЛИЗАЦИИ ИНФОРМАЦИИ

Министерство образования Российской федерации

ДАЛЬНЕВОСТОЧНЫЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

 

ОСНОВЫ АНАЛИЗА И ФОРМАЛИЗАЦИИ ИНФОРМАЦИИ

 

 

Методические указания

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

и индивидуальных заданий

 

Владивосток

 

 

Составители: Клещев А.С. профессор, д.ф.-м.н.

Артемьева И.Л., доцент, к.т.н., с.н.с.

 

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

 

 

ã Клещев А.С., Артемьева И.Л., 2002

 

 

ВВЕДЕНИЕ

 

Информатика – это наука о передаче, хранении и обработке информации. При изучении дисциплины "Основы анализа и формализации информации" рассматривается компьютерная обработка информации, а компьютерные системы обработки информации называются информационными системами.

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

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

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

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

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

 

I. Индивидуальное задание по теме "Обработка информации".

Придумать пример обработки информации и ответить на следующие вопросы.

1) Какая информация на входе?

2) Какая информация на выходе?

3) Какое правило обработки информации.

4) Каким дискретным сообщением представлена информация на входе?

5) Из какого набора знаков построено это сообщение и как?

6) С помощью какого сигнала и параметра сигнала это сообщение может быть передано и как оно хранится?

7) Каким дискретным сообщением представлена информация на выходе?

8) Из какого набора знаков построено это сообщение и как?

9) С помощью какого сигнала и параметра сигнала это сообщение может быть передано и хранится?

10) Какое правило интерпретации этих сообщений? Какое правило кодировки известной и неизвестной информации?

11) Какое правило обработки сообщения, какое правило кодировки информации?

12) Каким дискретным сообщением это правило может быть представлено?

Показать, что диаграмма обработки сообщений коммутативна.

 

Пример выполнения задания по теме "Обработка информации".

1) На входе информация о том, далеко или близко находится поезд

2) На выходе информация о том, можно ехать через переезд или нельзя

3) Правило обработки информации:

если поезд далеко, то можно ехать через переезд;

если поезд близко, то нельзя ехать через переезд

4) Информация на входе представлена следующим дискретным сообщением: звонок начал звонить, звонок кончил звенеть

5) При построении сообщения используется двоичный набор знаков. Само сообщение состоит из одного знака.

6) Сообщение передается при помощи звукового сигнала, параметром сигнала является амплитуда звуковой волны

7) Информация на выходе представлена при помощи следующего дискретного сообщения: шлагбаум имеет вертикальное положение, шлагбаум имеет горизонтальное положение

8) При построении сообщения используется двоичный набор знаков. Само сообщение состоит из одного знака.

9) Сообщение передается при помощи движения шлагбаума, параметром сигнала является положение шлагбаума в пространстве

10.1) Правило интерпретации сообщений.

Правило интерпретации известного сообщения: если звонок не звенит, то поезд далеко; если звонок звонит, то поезд близко.

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

10.2) Правило кодировки информации.

Правило кодировки известной информации: если поезд далеко, то звонок не звенит; если поезд близко, то звонок звонит.

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

11) Правило обработки сообщения следующее: если звонок начал звенеть, то перевести шлагбаум в горизонтальное положение, если звонок кончил звенеть, то перевести шлагбаум в вертикальное положение

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

На рис. 1 и 2 представлены диаграммы обработки сообщений для данного примера.

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

Рассмотрим исходную информацию "Поезд далеко" (рис.1), получим:

1) поезд далеко -> звонок не звенит -> шлагбаум имеет вертикальное положение (переходы: исходная информация -> исходное сообщение -> неизвестное сообщение);

2) поезд далеко -> ехать через переезд можно -> шлагбаум имеет вертикальное положение (переходы: исходная информация -> неизвестная информация -> неизвестное сообщение).

Рассмотрим исходную информацию "поезд близко" (рис. 2), получим:

1) поезд близко -> звонок звенит -> шлагбаум имеет горизонтальное положение (переходы: исходная информация -> исходное сообщение -> неизвестное сообщение);

2) поезд близко -> ехать через переезд нельзя -> шлагбаум имеет горизонтальное положение (переходы: исходная информация -> неизвестная информация -> неизвестное сообщение).

Следовательно, диаграмма обработки сообщений является коммутативной.

 

II. Индивидуальные задания по разделу "Свойства объектов предметной области и их представление в математических и компьютерных моделях"

 

1. Тема "Размерные объекты". План ответа:

1) название предметной области;

2) характеристика профессиональной деятельности в этой предметной области;

3) постановка всех классов задач, решаемых в ходе этой профессиональной деятельности;

4) замкнутая система размерных объектов предметной области с указанием стандартных обозначений размерностей и её обоснование;

5) система размерных понятий предметной области и ее обоснование;

6) обоснование процесса "обезразмеривания";

7) прикладная логическая теория, моделирующая систему размерных понятий;

8) программы (на любом языке программирования, но с комментариями!) решения всех классов задач, решаемых в ходе профессиональной деятельности;

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

 

Пример выполнения задания

1) Предметная область "Вычисление объемов прямоугольных параллелепипедов

2) Профессиональная деятельность в этой предметной области состоит в вычислении объемов прямоугольных параллелепипедов по их длине, ширине и высоте.

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

Дано: длина, ширина и высота прямоугольного параллелепипеда

Найти: объем прямоугольного параллелепипеда

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

5) Размерными понятиями данной предметной области являются "длина", "ширина", "высота", "объем". Объемы понятий "длина", "ширина" и "высота" состоят из положительных размерных значений, имеющих размерность "м". Объем понятия "объем" состоит из положительных размерных значений, имеющих размерность "м³".

6) Формула связи между размерными понятиями: объем = длина * ширина * высота, отсюда следует формула связи между размерностями:

м³ = м * м * м

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

7) Моделью системы размерных понятий является прикладная логическая теория, имеющая название "Объемы прямоугольных параллелепипедов". При ее построении используются стандартное расширение ST и специализированное расширение "Интервалы". Запишем теорию на языке прикладной логики. Здесь и во всех последующих примерах для удобства чтения каждое предложение прикладной логической теории имеет номер и снабжено содержательным комментарием.

Объемы прямоугольных параллелепипедов(ST, Интервалы)

7.1) сорт длина: R[0,¥]

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

7.2) сорт ширина: R[0,¥]

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

7.3) сорт высота: R[0,¥]

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

7.4) сорт объем: R[0,¥]

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

7.5) объем = длина * ширина * высота

предложение задает связь между терминами "объем", "длина", "высота" и "ширина"

7.6) длина > 0

длина не может иметь значение, равное 0

7.7) ширина > 0

ширина не может иметь значение, равное 0

7.8) высота > 0

высота не может иметь значение, равное 0

7.9) объем > 0

объем не может иметь значение, равное 0

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

Program Объемы;

var длина, ширина, высота, объем : real;

begin

{ ввод значений исходных данных задачи }

readln (длина, ширина, высота);

{ проверка правильности введенных значений }

if длина <= 0 then writeln("длина задана не правильно") else

if ширина <= 0 then writeln("ширина задана не правильно ") else

if высота <= 0 then writeln("высота задана не правильно") else

begin

объем:= длина * ширина * высота;

{ вывод значения результата решения задачи }

writeln ("объем = ", объем);

end;

end.

9) Ситуация предметной области имеет вид: длина 5 м, ширина 7 м, высота 1 м, объем 35 м³

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

длина º 5

ширина º 7

высота º 1

объем º 35

Память имеет несколько состояний: до выполнения оператора ввода значения всех идентификаторов не определены, после выполнения оператора ввода неопределенным остается значение идентификатора "объем", при правильных исходных данных в конце работы программы состояние памяти имеет вид: длина: 5, ширина: 7, высота: 1, объем: 35

 

2. Тема "Скалярные объекты". План ответа:

1) название и характеристика предметной области;

2) характеристика профессиональной деятельности в этой предметной области;

3) постановка всех классов задач, решаемых в ходе этой профессиональной деятельности;

4) замкнутые системы скалярных объектов предметной области и их обоснование;

5) система скалярных понятий предметной области и ее обоснование;

6) прикладная логическая теория, моделирующая эту систему понятий;

7) программы (на любом языке программирования, но с комментариями!) решения всех классов задач, решаемых в ходе профессиональной деятельности.

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

 

Пример выполнения задания

1) Предметная область "Вычисление массы тела".

2) Профессиональная деятельность в этой предметной области состоит в решении задачи вычисления массы тел, изготовленных из разных материалов. Характеристикой материала является химическое вещество.

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

Дано: объем тела и вещество, из которого оно сделано

Найти: массу тела

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

5) Размерными понятиями данной предметной области являются "объем" и "масса". Объем понятия "объем" состоит из положительных размерных значений, имеющих размерность "см³". Объем понятия "масса" состоит из положительных размерных значений, имеющих размерность "г". Скалярным понятием данной предметной области является "вещество"; его объем есть множество скалярных значений {железо, медь, серебро, золото}.

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

Массы тел(ST, Интервалы)

6.1) сорт объем: R[0,¥]

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

6.2) сорт масса: R[0,¥]

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

6.3) сорт вещество: {железо, медь, серебро, золото}

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

6.4) масса = объем * / (вещество = железо => 7.9), (вещество = медь => 8.1), (вещество = серебро => 10.5), (вещество = золото => 19.3) /

предложение задает связь между значениями терминов

6.5) объем > 0

объем не может иметь значение, равное 0

6.6) масса > 0

масса не может иметь значение, равное 0

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

Program Массы;

var объем, масса : real;

вещество: (железо, медь, серебро, золото);

pl: real; (* вспомогательная переменная *)

{ описание процедуры ввода значения вещества }

procedure ввод_значения_вещества;

{ в данном языке элементы типа "перечисление" }

{ не имеют внешнего представления }

{ поэтому ввод скалярного значения заменяется }

{ вводом строки или числа }

var vv: byte;

begin

{ ввод исходных данных до тех пор, пока не будут заданы правильные значения}

repeat

writeln('введите вещество: 1- железо, 2 – медь, 3 – серебро,

4 – золото');

readln (vv);

if (vv < 1) or (vv > 4) then writeln("неправильное задание вещества");

until (vv >= 1) and (vv<=4);

case vv of

1: вещество:= железо;

2: вещество:= медь;

3: вещество:=серебро;

4: вещество:= золото;

end;

end;

{ основная программа }

begin

repeat

writeln('введите значение объема');

readln (объем);

if объем <= 0 then writeln("объем задан не правильно");

until объем > 0;

ввод_значения_вещества;

{ в данном языке нет условных выражений, }

{ но есть условные операторы }

{ вычислим значение вспомогательной переменной }

if вещество = железо then pl := 7.9;

if вещество = медь then pl := 8.4;

if вещество = серебро then pl := 10.5;

if вещество = золото then pl := 19.3;

{ вычисление массы тела }

масса:= объем * pl ;

writeln ("масса = ", масса);

end.

9) Ситуация предметной области имеет вид: объем 1 см³, вещество медь, масса 8.4 г

Логическая модель представляется с использованием предложений-описаний значений имен языка прикладной логики:

объем º 1

вещество º медь

масса º 8.4

Память имеет несколько состояний: в начальный момент до выполнения ввода значения всех идентификаторов не определены, после выполнения ввода неопределенным остается значение идентификатора "масса" и "pl", при правильных исходных данных в конце работы программы состояние памяти имеет вид: pl: 5, объем : 1, вещество: медь, масса: 8.4

 

3. Тема "Множества"

3.1. "Конечные множества". План ответа:

1) название и характеристика предметной области;

2) характеристика профессиональной деятельности в этой предметной области;

3) постановка всех классов задач, решаемых в ходе этой профессиональной деятельности;

4) замкнутые системы конечных множеств предметной области и их обоснование;

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

6) прикладная логическая теория, моделирующая эту систему понятий;

7) программы (на любом языке программирования, но с комментариями!) решения всех классов задач профессиональной деятельности

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

 

3.2. "Разрежённые множества". План ответа:

1) название и характеристика предметной области;

2) характеристика профессиональной деятельности в этой предметной области;

3) постановка всех классов задач, решаемых в ходе этой профессиональной деятельности;

4) замкнутые системы разреженных множеств предметной области и их обоснование;

5) система понятий предметной области, соответствующих разреженным множествам, и ее обоснование;

6) прикладная логическая теория, моделирующая эту систему понятий;

7) программы (на любом языке программирования, но с комментариями!) решения всех классов задач, указанных в п.3.

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

 

Пример выполнения задания.

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

1) Предметная область "Изменение состава группы студентов".

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

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

Дано: состав группы в текущем учебном году, состав отчисленных, состав восстановленных, состав переведенных.

Найти: состав группы в следующем учебном году

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

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

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

Изменение состава группы студентов(ST)

6.1) сорт группа в текущем году: {}N

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

6.2) сорт отчисленные: {}группа в текущем году

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

6.3) сорт восстановленные: {}N

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

6.4) сорт переведенные: {}N

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

6.5) сорт группа в следующем году: {}N

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

6.6) группа в следующем году = (группа в текущем году È восстановленные È переведенные ) отчисленные

предложение задает связь между терминами

6.7) группа в текущем году ¹ Æ

группа в текущем году не может быть пустой

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

множество (строки): группа в текущем году, восстановленные, переведенные, группа в следующем году;

ввод : группа в текущем году, восстановленные, переведенные, группа в следующем году;

если пусто(группа в текущем году)

тогдавывод "неправильное задание группы студентов"

иначе

начало

множество (группа в текущем году) : отчисленные;

ввод : отчисленные;

группа в следующем году := группа в текущем году объединение восстановленные объединение переведенные) разность отчисленные;

вывод: "группа в следующем году состоит из студентов: ", группа в следующем году;

конец

 

4. Тема "Отображения".

4.1. "Конечные отображения". План ответа:

1) название и характеристика предметной области;

2) характеристика профессиональной деятельности в этой предметной области;

3) постановка всех классов задач, решаемых в ходе этой профессиональной деятельности;

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

5) система понятий предметной области и ее обоснование;

6) прикладная логическая теория, моделирующая эту систему понятий;

7) программы (на любом языке программирования, но с комментариями!) решения всех классов задач, указанных в п.3.

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

 

4.2. "Разрежённые отображения" (необязательное задание). План ответа:

1) название и характеристика предметной области;

2) характеристика профессиональной деятельности в этой предметной области;

3) постановка всех классов задач, решаемых в ходе этой профессиональной деятельности;

4) замкнутые системы разреженных отображений предметной области и их обоснование;

5) система понятий предметной области, соответствующих разреженным отображениям, и ее обоснование;

6) прикладная логическая теория, моделирующая эту систему понятий;

7) программы (на любом языке программирования, но с комментариями!) решения всех классов задач, указанных в п.3.

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

 

Пример выполнения задания

1) Предметная область "Масса совокупности тел".

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

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

Дано: множество тел, объемы тел, возможные вещества, вещества, из которого изготовлен материал тела, плотности веществ

Найти: суммарную массу всех тел

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

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

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

Масса совокупности тел(ST, Интервалы, Математические кванторы)

6.1) сорт тела: {}N

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

6.2) сорт вещества: {}N

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

6.3) сорт объем: (тела ®R[0,¥])

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

6.4) сорт масса: (тела ® R[0,¥])

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

6.5) сорт вещество: (тела ® вещества)

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

6.6) сорт плотность: (вещества ® R[0,¥])

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

6.7) сорт масса совокупности тел: R[0,¥]

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

6.8) (v: тела) масса(v) = плотность((вещество(v)) * объем(v)

предложение задает связь между терминами масса, плотность и объем

6.9) масса совокупности тел = (S(v: тела) масса(v))

предложение задает связь между терминами "масса" и "масса совокупности тел"

6.10) (v: тела) масса(v) > 0 & объем(v) > 0 & плотность(v) > 0 & масса совокупности тел(v) > 0

предложение уточняет область значений отображений

6.11) вещества ¹ Æ

значением термина "вещества" не может быть пустое множество

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

множество (строки): тела, вещества;

ввод : тела;

повторить

ввод: вещества;

если пусто(вещества)

тогда вывод: "не правильно задано множество веществ";

пока not (пусто(вещества));

массив[тела] вещ : объем, масса;

массив[тела] вещества: вещество;

массив[вещества] вещ : плотность;

{ процедура "ввод значений" производит ввод значений }

{ и проверку правильности ввода}

ввод значений (объем, вещество, плотность);

для v Î тела выполнить масса[v] = плотность[вещество[v]] * объем[v];

масса совокупности тел:=0;

для v Î тела выполнить масса совокупности тел:= масса совокупности тел + масса[v];

вывод: "масса совокупности тел равна ", масса совокупности тел;

 

5. Тема "Объединенные величины" (необязательное задание). План ответа:

1) название и характеристика предметной области;

2) характеристика профессиональной деятельности в этой предметной области;

3) постановка всех классов задач, решаемых в ходе этой профессиональной деятельности;

4) замкнутые системы объединённых величин предметной области и их обоснование;

5) система понятий предметной области, соответствующих объединенным величинам, и ее обоснование;

6) прикладная логическая теория, моделирующая эту систему понятий;

7) программы (на любом языке программирования, но с комментариями!) решения всех классов задач, указанных в п.3.

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

Примериспользования объединенных величин см. в следующем разделе.

 

Тема "Структурные объекты".

1) название и характеристика предметной области; 2) характеристика профессиональной деятельности в этой предметной области; 3) постановка всех классов задач, решаемых в ходе этой профессиональной деятельности;

Пример выполнения задания

1) Предметная область "Объемы тел правильной формы".

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

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

Дано: множество тел и их типов, значения характеристик тел.

Найти: объем каждого тела.

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

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

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

Объемы тел правильной формы(ST, Интервалы)

6.1) pi º 3.1415

предложение определяет значение термина, обозначенного "pi"

6.2) сорт шары: {}N

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

6.3) сорт кубы: {}N

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

6.4) сорт прямоугольные параллелепипеды: {}N

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

6.5) сорт радиус: (шары ® R[0,¥])

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

6.6) сорт длина ребра: (кубы ® R[0,¥])

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

6.7) сорт ширина: (прямоугольные параллелепипеды ® R[0,¥])

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

6.8) сорт длина: (прямоугольные параллелепипеды ® R[0,¥])

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

6.9) сорт высота: (прямоугольные параллелепипеды ® R[0,¥])

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

6.10) тела º шары È кубы È прямоугольные параллелепипеды

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

6.11) сорт объем: (тела ® R[0,¥])

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

6.12) (v: тела) объем(v) = / (v Î шары Þ 4/3 * (радиус(v) ­3) *pi), (v Î кубы Þ длина ребра(v) ­3), (v Î прямоугольные параллелепипеды Þ длина(v) * ширина(v) * высота(v)) /

предложение задает связь между атрибутами

6.13) (v: шары) радиус(v) > 0

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

6.14) (v: кубы) длина ребра(v) > 0

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

6.15) (v: прямоугольные параллелепипеды) длина(v) > 0 & ширина(v) > 0 & высота(v) > 0

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

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

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

ввод : шары, кубы, прямоугольные параллелепипеды;

массив[шары] вещ : радиус;

ввод : радиус;

массив[кубы] вещ : длина ребра;

массив[прямоугольные параллелепипеды] вещ : ширина, длина, высота;

ввод : радиус, длина ребра, ширина, высота, длина;

объединение (шары, кубы, прямоугольные параллелепипеды) : тела;

для v Î тела выполнитьесли v Î шары тогда объем[v] = 4/3 * (радиус[v] ­3)*pi; если v Î кубы тогда объем[v] = длина ребра[v]­3; если v Î прямоугольные параллелепипеды тогда объем[v] длина[v] * ширина[v] * высота[v];

для v Î тела выполнитьвывод: "объем тела ", v, "равен ", объем;

Запишем программу на алгоритмическом языке программирования Паскаль. Для моделирования структурных объектов будем использовать тип данных "запись с вариантами".

Program объемы_тел;

Type

TBodyType = (шары, кубы, прям_парал);

TBody = record

ИмяТела:string[8];

ТипТела: TBodyType;

Атрибуты: record case BodyType: TBodyType of

шары: (шары: record радиус:Real; end);

кубы: (кубы: record длина_ребра: Real; end);

прям_парал: (прям_парал:

record

ширина, длина, высота: Real;

end);

end; end;

TbodySet = array[1..10] of TBody;

Var МножТел: TbodySet;

Numb: byte;

ОбъемыТел: array[1..10] of real;

Procedure ввод_тела (var numb:byte);

Var name: string[8]; BodyType: byte;

Begin

Repeat

Writeln(‘введите название тела или *, если все тела’);

Readln(name);

If name <> ‘*’ then numb:= numb+1;

Repeat

Writeln(‘введите тип тела’);

Writeln(‘ 1: шар’);

Writeln(‘ 2: куб’);

Writeln(‘ 3: прямоугольный параллелепипед’);

Readn(BodyType);

Until not(BodyType in {1, 2, 3 };

With МножТел[numb] do begin

ИмяТела:= name;

ТипТела:= bodyType;

Case BodyType of

1: begin ТипТела:= шары;

writeln(‘задайте радиус’);

readln(Атрибуты.шары.радиус);

end;

2: begin ТипТела:= кубы;

writeln(‘задайте длину ребра’);

readln(Атрибуты.кубы.длина_ребра);

end;

1: begin ТипТела:= прям_парал;

writeln(‘задайте ширину,

высоту и длину’);

readln(Атрибуты.прям_парал.ширина,

Атрибуты.прям_парал.высота,

Атрибуты.прям_парал.длина,);

end;

end;

end;

Until (name = ‘*’);

End;

Begin

numb:=0;

Ввод_тела(numb);

For i:=1 to numb do

With МножТел[i] do begin

If ТипТела = шары then ОбъемыТел[i]:= 4/3*pi*

Атрибуты.шары.радиус* Атрибуты.шары.радиус* Атрибуты.шары.радиус;

If ТипТела = кубы then ОбъемыТел[i]:=

Атрибуты.кубы.длина_ребра*

Атрибуты.кубы.длина_ребра*

Атрибуты.кубы.длина_ребра;

If ТипТела = прям_парал then ОбъемыТел[i]:=

Атрибуты.прям_парал.высота*

Атрибуты.прям_парал.длина*

Атрибуты.прям_парал.ширина;

End;

End.

7. Тема "Последовательности". Обязательным для выполнения является одно из заданий по данной теме. Никаких ограничений на выбор задания нет.

7.1. "Последовательности общего вида". План ответа:

1) название и характеристика предметной области;

2) характеристика профессиональной деятельности в этой предметной области;

3) постановка всех классов задач, решаемых в ходе этой профессиональной деятельности;

4) замкнутые системы величин последовательностей предметной области и их обоснование;

5) система понятий предметной области, соответствующих последовательностям, и ее обоснование;

6) прикладная логическая теория, моделирующая эту систему понятий;

7) программы (на любом языке программирования, но с комментариями!) решения всех классов задач, указанных в п.3.

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

 

7.2. "Стеки". План ответа:

1) название и характеристика предметной области;

2) характеристика профессиональной деятельности в этой предметной области;

3) постановка всех классов задач, решаемых в ходе этой профессиональной деятельности;

4) замкнутые системы величин стеков предметной области и их обоснование;

5) система понятий предметной области, соответствующих стекам, и ее обоснование;

6) прикладная логическая теория, моделирующая эту систему понятий;

7) программы (на любом языке программирования, но с комментариями!) решения всех классов задач, указанных в п.3.

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

 

7.3. "Очереди". План ответа:

1) название и характеристика предметной области;

2) характеристика профессиональной деятельности в этой предметной области;

3) постановка всех классов задач, решаемых в ходе этой профессиональной деятельности;

4) замкнутые системы величин очередей предметной области и их обоснование;

5) система понятий предметной области, соответствующих очередям, и ее обоснование;

6) прикладная логическая теория, моделирующая эту систему понятий;

7) программы (на любом языке программирования, но с комментариями!) решения всех классов задач, указанных в п.3.

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

 

7.4. "Деки". План ответа:

1) название и характеристика предметной области;

2) характеристика профессиональной деятельности в этой предметной области;

3) постановка всех классов задач, решаемых в ходе этой профессиональной деятельности;

4) замкнутые системы величин деков предметной области и их обоснование;

5) система понятий предметной области, соответствующих декам, и ее обоснование;

6) прикладная логическая теория, моделирующая эту систему понятий;

7) программы (на любом языке программирования, но с комментариями!) решения всех классов задач, указанных в п.3.

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

Примеры выполнения задания

Пример 1. Стеки.

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(3, процесс сортировки(0)) = L

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

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

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

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

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

6.13) (v: I[1,n]) пункт назначения(last(p(1, процесс сортировки(v-1))) = B Þ p(3, процесс сортировки(v)) = addend(p(3, процесс сортировки(v-1)), last(p(1, процесс сортировки(v-1))) & p(2, процесс сортировки(v)) = p(2, процесс сортировки(v-1))

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

6.14) (v: I[1,n]) p(1, процесс сортировки(v)) = head(p(1, процесс сортировки(v-1)))

на каждом шаге процесса формирования из первого тупика забирается первый вагон

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

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

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

вагон = record

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

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

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

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

end;

var начало_уходящего, конец_уходящего,

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

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

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

i, n: integer;

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

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

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

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

end;

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

begin

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

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

end;

procedure addend(var конец_состава: составы; добавляемый: составы);

begin

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

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

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

end;

begin

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

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

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

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

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

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

begin

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

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

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

begin

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

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

предыдущий:=nil;

end;

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

n:= n+1;

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

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

end;

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

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

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

for i:=1 to n do

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

then

begin

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

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

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

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

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

end

else

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

then

begin

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

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

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

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

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

end;

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

{объединяем две последовательности}

{ так как обе моделируются стеком, то адрес начала не хранится}

текущий_вагон:= начало_уходящего;

while текущий_вагон <> nil do

begin

конец_уходящего:= текущий_вагон;

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

end;

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

Пример 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.