Богомолов О.Д. Теоретические основы информационных систем и технологий
Подождите немного. Документ загружается.
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
Государственное образовательное учреждение
высшего профессионального образования
Тихоокеанский государственный университет
Институт экономики и управления
Кафедра Экономическая кибернетика
Методические указания по практическим рабтам
По дисциплине Теоретические основы
информационных систем и технологий
Для специальности
«Прикладная информатика в экономике»
Методические указания разработаны в соответствии с составом УМКД
Методические указания разработала Богомолов О.Д. _____________
Методические указания утверждены на заседании кафедры,
протокол № ______ от «___» _______________ 200__ г.
Зав. кафедрой _________ «___» ______________ 200__ г. Пазюк К.Т.
Методические указания по практическим занятиям по дисциплине
«Теоретические основы информационных систем и технологий» включают
тематику вопросов, выносимых для самостоятельной подготовки, задачи,
которые решаются студентами под контролем преподавателя или
самостоятельно во время аудиторных занятий.
Методические указания рассмотрены и утверждены на заседании УМКС и
рекомендованы к изданию
протокол № ______ от «___» _______________ 200__ г.
Председатель УМКС _______ «___» __________ 200__ г.
Директор института _________ «___» ____________ 200__ г. Зубарев А.Е.
2
Практическое занятие №1
на тему: «Изучение определения и свойств алгоритма
с использованием положений теории алгоритмов»
Цель занятия – изучить элементы теоретического представления
информации (буквы, слова, конструкции) и свойства первичного алгоритма
как одного из элементов строгого и полного теоретического определения
алгоритма, исследовать теоретическое определение алгоритма, получить
представления о коллективах алгоритмов и эквивалентных алгоритмах для
информационных систем, рассматриваемых как большие и сложные системы.
Задание
По рекомендованной литературе изучить основные понятия об
информации и ее преобразованиях. Разработать первичный алгоритм и
записать объявление операции нулевого ранга.
Варианты задания
Номер
варианта
0 1 2 3 4 5 6
Результат
выполнения
первичного
алгоритма
Α
1
A
2
A
1
A
2
Слово
являетс
я
двухбу
к-
венным
В слове
все
нечетные
буквы –
буква А
В слове
все
нечетн
ые
буквы –
буква В
Пус-
тое
слово
Слово
является
двухбук-
венным
из одина-
ковых
букв
В слове
каждая
буква
является
буквой А
Номер
варианта
7 8 9 10 11 12
Результат
выполнения
первичного
алгоритма
В слове
каждая
буква
является
буквой В
Α
1
A
2
A
2
A
1
Слово
являетс
я
трехбук
венным
Слово
начинается и
заканчивается
одной и той же
буквой
Слово
начинаетс
я с буквы
А и
заканчива
ется на
букву Я
Α
2
A
2
A
1
A
2
Номер
варианта
13 14 15 16 17 18
Результат
выполнени
я
первичного
алгоритма
В слове
две
последних
буквы –
буква А
Α
2
A
2
A
1
A
1
В слове
две
первых
буквы –
буква В
Слово не
является
однобукве
нным
Α
2
A
2
A
1
A
1
Слово
является
однобукве
нным
3
Методические указания к выполнению задания
По Н.Криницкому, конструкцией называется совокупность
конструктивных элементов и связей, которая либо является пустой, либо
содержит не менее одного конструктивного элемента и удовлетворяет двум
условиям:
а) любая связь в ней насыщена ее конструктивными элементами;
б) любые два конструктивных элемента в ней связаны ее связями.
Конструктивным элементом может быть либо буква, либо заключенная
в оболочку конструкция.
Словом называется конструкция, которая либо является пустой, либо
удовлетворяет следующим условиям:
1) все ее буквы связаны с помощью связей трех типов: начинающей
связи ранга 1, кончающей связи ранга 1 и продолжающей связи ранга 2,
имеющей характеристику 1,1;
2) в ней присутствует одна начинающая связь и одна заканчивающая
связь;
3) каждая буква является связуемым элементом двух связей;
4)если посчитать, что жанр ветви начинающей связи –второй, а ветви
кончающей связи – первый, то ветви связей, связывающих каждую
букву слова, относятся к разным жанрам.
Буква слова, связанная начинающей связью, называется началом слова,
а связанная кончающей – концом слова. Пустое слово не имеет ни начала, ни
конца.
Слово, все буквы которого попарно неодинаковы, называют
алфавитом. Всякая буква, одинаковая с одной из букв этого слова,
называется буквой в этом алфавите.
Известно, что прямым назначением любого алгоритма является его
выполнение. Поэтому особенности алгоритма определяются особенностями
алгоритмических операций, а для формирования понятия алгоритма
необходимо уточнить понятие операции.
Операции определяются как некоторые построения из первоначальных
операций, причем по отношению к построениям совершается акт их
объявления операциями.
Операции подразделяются на действия и условия. Действиями
называются натуральные действия, линеаризация и делинеаризация,
конкатенация.
Состав натуральных операций и их обозначения приведены в таблице
1. Натуральные условия:
а) «рассматриваемое слово непусто» (условие непустоты);
б) «рассматриваемая буква является началом данного слова» (условие
начала);
в) «рассматриваемая буква является концом данного слова» (условие
конца);
4
г) «рассматриваемая буква одинакова с данной буквой α» (условие
одинаковости).
Таблица 1
Название натуральной операции Знак операции
Порождение слова S
α-генерация hα
Аннигиляция Δ
Нахождение начала слова *
Продвижение вперед →
Продвижение назад ←
Удлинение вперед
Отбрасывание конца
Замена буквы на α !α
Отключение буквы X
Условие непустоты
Условие начала н
Условие конца к
Условие одинаковости
Пустое действие
Рассмотрим приведенный Н.Криницким пример первичного алгоритма
с необходимыми пояснениями.
Пример 1. Разработать первичный алгоритм для объявления операции
нулевого ранга, результатом которой является слово
.
121
1: s :2; /* начать рассмотрение пустого слова */
2:
1
h
:3; /*вместо данного пустого слова рассматривать однобуквенное,
состоящее из буквы
.
1
*/
3: * :4; /* выбрать и пометить специальной связью начало слова – букву
.
1
*/
4: :5; /* без продвижения вперед после рассматриваемой буквы
1
приписать одинаковую с ней букву
.
1
*/
5: :6 ; /* от рассмотрения первой буквы слова перейти к
рассмотрению второй -
.
1
*/
6:
2
!
:7; /* заменить букву
1
на букву
2
*/
7: :8; /* без продвижения вперед после рассматриваемой буквы
2
приписать одинаковую с ней букву
.
2
*/
8: :9 ; /* от рассмотрения второй буквы слова перейти к
рассмотрению третьей-
.
2
*/
9:
1
!
:10; /* заменить букву
2
на букву
1
*/
10:
:11; /* прекратить рассмотрение буквы */
11: : ; /* не выполнять никаких действий */
5
Используются конструкции двух видов:
<метка>:<знак действия>:<отсылка>
<метка>:<знак условия>:<отсылка>/<отсылка>
где <метка>:=<метка-действия>|<отсылка>.
Рассмотрим первоначальное полное определение алгоритма.
Алгоритм – совокупность правил, механическое исполнение которых
(по совокупности правил выполнения) исполнителем определяет процесс
получения искомого конечного результата от варьируемых исходных
данных.
Более точное определение алгоритма приведено в материалах,
подготовленных Институтом кибернетики Академии Наук:
«Алгоритм – строго сформулированное правило действий, для
которого задано правило его применения к варьируемым исходным данным
задачи для получения ее решения».
Там же вводится понятие алфавитного оператора как правила
преобразования информации, устанавливающего соответствие слова на входе
оператора и слова на выходе оператора.
Рассмотрим первоначальное неполное определение алгоритма.
Алгоритм – предписание (приказ или система приказов), определяющее
процесс преобразования исходных данных в искомый результат и
обладающее свойствами определенности, результативности и массовости.
Эти определения (полное и неполное) являются неточными
(нестрогими). Рассмотрим точное полное определение алгоритма (по
Н.Криницкому).
Предположим, что заданы два языка L
1
и L
2
. Пусть L
3
– язык,
конструкциями которого являются пары (t,s), где t – конструкция языка L
1
, а
s – конструкция языка L
2
. Тогда
1.Всякий первичный алгоритм на языке L
1
над языком L
2
называется
алгоритмом на языке L
1
над языком L
2
.
2.Если задан алгоритм W (на некотором языке) над языком L
3
, то
любая конструкция t, рассматриваемая вместе с W называется алгоритмом
на языке L
1
над языком L
2
. Сама по себе конструкция t называется записью
алгоритма.
При этом всякая конструкция s, которая вместе с t образует исходное
данное для W, по отношению к алгоритму, имеющему запись t, называется
исходным данным, а конструкция r,получаемая от применения W к t,s
называется (искомым) результатом; W называется алгоритмом выполнения.
Тогда L
1
- алгоритмический язык вместе с L
2
(языком исходных
данных).
Если t – алгоритм над языком L
2
, то все его результаты принадлежат
некоторому языку. Более того, существует язык, содержащий результаты
6
алгоритма t, который, кроме этих результатов, не содержит никаких других
конструкций.
Таким образом, необходимо различать алгоритм, определяемое им
отображение (функцию) и его запись. Эти объекты должны иметь различное
обозначение. При этом определенный вначале алгоритм называют
алгоритмом первого ранга.
Пусть конструкция X содержит подконструкции Y, Z
1
, Z
2
, …,Z
n
.
Пусть F – некоторая n - местная операция. Рассмотрим первичный
алгоритм:
1.Выполнить F над исходными данными Z
1
, Z
2
, …,Z
n
; перейти к п.2.
2.Полученным результатом заменить в конструкции X
подконструкцию Y; стоп.
Объявляя отображение, соответствующее данному алгоритму,
операцией, обозначим ее
Y:=F (Z
1
, Z
2
, …,Z
n
)
Определенные таким образом операции будем называть локальными
операциями над X.
Пусть P(Z
1
, Z
2
, …,Z
n
) – уже известный предикат с предметными
переменными Z
1
, Z
2
, …,Z
n
, а λ – имя конструкции для логического
значения. Рассмотрим следующий первичный алгоритм:
1.Если P(Z
1
, Z
2
, …,Z
n
), то перейти к п.2, иначе – к п.3.
2. λ:=1, стоп;
3. λ:=0, стоп;
Если
1
Z
X,
n
Z
X, то отображение, соответствующее данному
первичному алгоритму будем называть локальным предикатом
P(Z
1
, Z
2
, …,Z
n
) над X.
Отображение как операция ожидания условия, обозначенная символом
Ожидать P(Z
1
, Z
2
, …,Z
n
)
соответствует первичному алгоритму:
1.Если P(Z
1
, Z
2
, …,Z
n
), то стоп, иначе перейти к п. 1
Операция ожидания имеет смысл для рассмотренных конструкций.
Первичные алгоритмы, в которых используются только локальные
операции и локальные предикаты, называются локальными первичными
алгоритмами.
Приказ, содержащийся в записи первичного алгоритма, называется
подчиненным предикату Р, если он предписывает ожидание Р или
непосредственно перед его выполнением имеет место Р=1.
Пусть U={U
1
, U
2
, …,U
n
}- множество не имеющих внешних частей
подконструкций конструкции X. Предположим, что U разбито на
непересекающиеся подмножества Y
1
, … , Y
n
;S
1
, …, S
k
.
Определим через регулирующие предикаты множество локальных
алгоритмов как коллектив алгоритмов.
7
Пусть R={A
i
} – конечное множество локальных алгоритмов, имеющих
общее для них исходное данное X и удовлетворяющих следующим
условиям:
1)запись каждого A
i
содержит только приказы, основанные на
подконструкциях , принадлежащих Y
i
, и, может быть, на
подконструкциях, принадлежащих некоторым S
j
;
2)для каждого A
i
и каждого S
j
, содержащего основания {Z
i
} приказов,
которые содержатся в записи A
i
, задан предикат P
i
(Z
j
), локальный над
X; причем совокупность таких предикатов обладает следующими
свойствами:
а)
t
i
ji
,)S(P
1
1
где t=n или t=n+1;
б)
0 )S(P)S(P
jrji
при
;ir
3)каждый приказ алгоритма A
i
, основание которого принадлежит S
j
,
подчинен предикату P
i
(S
j
).
Описанное множество локальных алгоритмов называется коллективом
алгоритмов. Названные выше предикаты называются регулирующими
предикатами коллектива.
Если существует S
j
, такое, что регулирующие предикаты P
q
(S
j
)=1 и
P
r
(S
j
)=1, то говорят, что алгоритмы A
q
и A
r
находятся в контакте.
Два алгоритма A
q
и A
r
одного коллектива называются объединенными,
если они являются контактирующими между собой, либо контактируются с
алгоритмом, который объединен с одним из них.
Если для всех j имеет место P
n+1
(U
j
)
0 или t=n, то коллектив R={A
i
}
называется замкнутым. В остальных случаях он называется открытым.
Утверждается, что для любого замкнутого коллектива алгоритмов
существует эквивалентный ему локальный алгоритм.
Литература
1.Глушков В.М. Основы информатики.-М, 1987.
2. Криницкий Н.А. и др. Программирование и алгоритмические языки-
М,1979.
8
Практическое занятие №2
на тему: «Исследование функционирования системы с
использованием основных элементов теории автоматов»
Цель занятия – изучение возможностей применения для исследования
функционирования системы положений теории автоматов как главного
раздела теории алгоритмов по отношению к рекурсивным функциям.
Задание
Изучить по рекомендованной литературе основные положения теории
автоматов как одной из основных частей теоретических основ
информационных систем и технологий.
Объект S представляет собой управляемую систему, решающую
актуальные задачи. Изменение состояния среды, изменяющее вход объекта,
вызывает изменение его состояния в части перехода к реализации
определенного процесса (к выполнению функции). Результатом выполнения
функции является изменение выхода объекта. На выходе – изменения в
ресурсах, технологии, продукции и метаинформации.
Объект S состоит из подобных ему элементов P и R, находящихся в
линейной последовательности P R. Для P и R заданы таблицы переходов
и выходов.
Требуется исследовать функционирование объекта S при изменении
среды для заданных начальных состояний P и R. Результаты представить в
таблице и проанализировать на предмет выявления периодичности и
структурированности. Описать взаимодействие P и R с помощью любых
известных не вполне формализованных и формализованных языковых
средств.
Для объекта S построить граф переходов.
Краткие указания. Элемент матрицы (таблицы) переходов и выходов
x
ij
/y
ij
определяет переход из состояния j в состояние x
ij
, если состоянием
входа является V
i
. При этом на выходе формируется y
ij
. Например, переход
из состояния a в состояние b осуществляется, если на входе α . При этом на
выходе будет z. Графически это представляется следующим образом.
9
a b
α /z
В частности, если на входе P будет α , то выполнится переход из i в k .
При этом на выходе будет y. (1 вариант).
При исследовании объекта рекомендуется обратить внимание на
положения современной экономической теории информационных систем.
Ученые и специалисты указывают на двойственную природу организации:
организация как автомат и организация как создатель смысла. В целом
организация (объект, информационная система, информационная
технология) и ее часть – коллектив экономистов - рассматривается как сеть
рекурсивной коммуникации и действий, как система, осуществляющая
обработку информации, формирование знаний и принятие решений, которая
производит смысл и управляется смыслом.
С учетом современных подходов студент может самостоятельно
изучить рекурсивные функции как альтернативный раздел теории
алгоритмов.
Студент выполняет задание с использованием учебника Б.Советова
«Моделирование систем» и учебника А.Мишенина «Теория экономических
информационных систем».
Варианты задания
1 вариант
Таблица переходов и выходов для P
i j k
α k/y i/x j/y
β j/z i/x k/w
Таблица переходов и выходов для R
а b c d
x d/P c/Q d/Q b/M
y a/Q c /l c/K a/T
z d/M b/M c/M a/T
w a/N b/N c/N a/T
2 вариант
Таблица переходов и выходов для Р
i j k
10