- •Лекция 1 Основные понятия Об информационно-библиотечной культуре
- •Информация, сведения, данные, знания
- •Лекция 2 Неформальные и формальные каналы коммуникации
- •Библиотеки, библиография и библиографическое описание
- •Библиотечная и информационная деятельность
- •Тенденции развития основных видов документов
- •Закономерности роста и старения
- •Оценка значимости (влиятельности) ученых и журналов
- •Закон рассеяния статей конкретной тематики по журналам
- •Лекция 3 Предыстория и сущность
- •Процедуры и понятия
- •Координатное индексирование
- •Цитирование, библиографическое сочетание, социтирование
- •Рубрикаторы информационных изданий
- •Лекция 4 Электронные издания
- •Информационные ресурсы, структуры и инфраструктура
- •Информационные продукты и услуги
- •Лекция 5 Основные понятия и проблемы становления информационного общества. Информатизация как процесс перехода к информационному обществу
- •Возникновение, этапы развития и технологические аспекты информатизации
- •Положительные и отрицательные последствия информатизации
- •Программы информатизации
- •Программы информатизации России
- •Электронное правительство
- •Лекция 6 Представления информации Сообщение как материальная форма представления информации
- •Формы сообщений (сигналы, изображения, знаки, языковые сообщения)
- •Основные понятия теории формальных языков
- •Модели источников сообщений. Конечный вероятностный источник сообщений
- •Кодирование сообщений источника и текстов. Равномерное кодирование. Дерево кода
- •Неравномерное кодирование. Средняя длина кодирования
- •Префиксные коды
- •Необходимые и достаточные условия существования префиксного кода с заданными длинами кодовых слов. Неравенство Крафта
- •Методы построения кодов. Код Фано
- •Избыточность кодирования. Нижняя граница средней длины кодирования
- •Оптимальное кодирование, свойства оптимальных кодов, построение оптимальных кодов методом Хафмена
- •Лекция 7 Модель процесса передачи. Двоичный симметричный канал
- •Способы повышения надежности передачи сообщений
- •Принципы обнаружения и исправления ошибок с использованием кодов
- •Расстояние Хеминга и корректирующие возможности кодов
- •Оценки верхних границ корректирующих способностей кодов
- •Особенности векторных пространств над конечным полем gf(2). Линейный групповой код
- •Построение линейного кода по заданной порождающей матрице
- •Декодирование линейного кода по синдрому
- •Описание процесса обработки данных. Понятие алгоритма и его свойства. Способы формальной записи алгоритмов
- •Модель процесса обработки данных. Конечные автоматы
- •Сеть Петри как модель параллельно выполняемых процессов обработки
- •Формальное определение сети Петри
- •Основные задачи анализа процессов обработки, решаемые с использованием сетей Петри
- •Матричный метод анализа сетей Петри
- •Иерархия информационных систем управления Трансакционные системы
- •Системы бизнес-интеллекта
- •Аналитические приложения
- •Сущность erp-систем
- •Управление запасами и производством
- •Управление спецификациями изделий и технологиями производства
- •Планирование операций
- •Управление продажами
- •Управление запасами
- •Управление закупками
- •Управление производственными процессами
- •Учет и управление финансами Сущность финансового и управленческого учета
- •Главная книга
- •Расчеты с дебиторами
- •Расчеты с кредиторами
- •Основные средства
- •Денежные средства
- •Материально-производственные запасы
- •Расчеты с персоналом
- •Налоговый учет
- •Бухгалтерская отчетность
- •Аналитические возможности
- •Управление персоналом
- •Ограниченность erp-систем
- •Сущность систем бизнес-интеллекта
- •Хранилища данных Функциональность
- •Olap-системы Функциональность
- •Средства формирования запросов и визуализации данных Функциональность
- •Основные виды аналитических приложений
- •Системы управления эффективностью бизнеса (bpm-системы) Сущность концепции bpm
- •Функциональность bpm-систем
- •Управление по ключевым показателям Balanced Scorecard и другие методики управления по ключевым показателям
- •Функциональность bsc-систем
- •Корпоративное планирование и бюджетирование Основы корпоративного планирования и бюджетирования
- •Многомерное хранение информации
- •План счетов
- •Календарь планирования
- •Мультивалютность
- •Бизнес-правила
- •Описание финансовой структуры предприятия
- •Описание пользователей
- •Сценарии и версии
- •Управление процессом планирования
- •Формирование и анализ консолидированной финансовой отчетности Сущность консолидированной финансовой отчетности
- •Информационные системы консолидации финансовой отчетности
- •Аналитические направления
- •Сбор и структурирование исходной информации
- •Мультивалютность
- •Бизнес-правила
- •Журналы
- •Организация процесса консолидации
- •Процедуры консолидации
- •Bi-приложения
- •Системы финансового моделирования
- •Системы имитационного моделирования
- •Определения и термины
- •Области применения имитационных моделей
- •Последовательность разработки имитационных моделей
- •Компьютерная реализация имитационной модели
- •Система Arena
- •Экспертные системы
- •Архитектура экспертной системы
- •Классы экспертных систем
- •Технология создания экспертных систем
- •Рекомендации по выбору экспертной системы
- •Системы поддержки принятия решений
- •Определение систем поддержки принятия решений
- •Характеристика различных систем поддержки принятия решений
- •Выделение признаков классификации сппр
- •Особенности Экспертной системы поддержки принятия решений
- •Архитектура эсппр
- •Реализация выбора метода принятия решения в эсппр
- •Характеристика эсппр по выделенным признакам
- •Специализированные аналитические приложения
- •Принципы построения компьютера История и тенденции развития вычислительной техники
- •Основные характеристики и классификация компьютеров
- •Принципы построения компьютера
- •Структурные схемы и взаимодействие устройств компьютера
- •Компьютерные системы
- •Системы счисления
- •Перевод целых чисел
- •Перевод дробных чисел
- •Арифметические основы эвм Представление числовой информации в компьютере
- •Машинные коды
- •Арифметические операции над числами с фиксированной точкой
- •Логические основы эвм Основные сведения из алгебры логики
- •Законы алгебры логики
- •Техническая интерпретация логических функций
- •Кодирование информации в компьютере
- •Кодирование нечисловой информации
- •Кодирование текстовой информации
- •Кодирование графических данных
- •Кодирование звуковой информации
- •Основная память
- •Сверхоперативная память
- •Ассоциативная память
- •Центральный процессор эвм
- •Система команд микропроцессора
- •Взаимодействие элементов при работе микропроцессора
- •Системы визуального отображения информации (видеосистемы)
- •Клавиатура
- •Принтеры
- •Внешние запоминающие устройства (взу)
- •Накопитель на жестком магнитном диске
- •Оптические запоминающие устройства
- •Организация функционирования эвм с магистральной архитектурой
- •Организация работы эвм при выполнении задания пользователя
- •Особенности управления основной памятью эвм
- •Система прерываний эвм
- •Параллельные вычисления
- •Характеристика и особенности лкс
- •Протоколы и технологии локальных сетей
- •Сетевые устройства лкс
- •Структурированная кабельная система и логическая структуризация лкс
- •Виды глобальных сетей
- •Глобальные сети России РосНиирос
- •Магистральная сеть науки и образования rbNet (Russian Backbone Network)
- •Сеть runNet
- •Узел маршрутизации Российского фонда фундаментальных исследований (рффи)
- •Msk-IX (Московский центр взаимодействия компьютерных сетей Internet eXchange)
- •Сервисы Internet
- •Isp (Internet Service Provider)
- •Ipp (Internet Presence Provider)
- •Pcp (Private Content Publisher)
- •Характеристики хостинг-провайдеров
- •Программное обеспечение Интернета
Модель процесса обработки данных. Конечные автоматы
Важную роль в процессе обработки данных (поимо самих данных, подвергаемых обработке) играет активная составляющая процесса - некоторая сущность, выполняющая обработку. Таким обработчиком, или преобразователем данных, могут быть как люди, так и некоторые устройства. Важнейшие характеристики процесса обработки данных зависят от того, как функционирует преобразователь. Поэтому создание и исследование различных моделей обработки имеет важное теоретическое и практическое значение. Одной из таких моделей является понятие конечного автомата [32],[36]. Конечный автомат можно охарактеризовать как устройство, имеющее входной и выходной каналы; в процессе функционирования на каналы поступают дискретные порции данных (буквы алфавита). Автомат может находиться в одном из конечного числа внутренних состояний. По определенному закону (в зависимости от состояния автомата и входных данных) осуществляется преобразование входной порции данных в выходные данные и смена состояния автомата. Формально конечный автомат определяется следующим образом.
Определение. Конечным автоматомназывается набор из пяти объектов, в котором:
- входной алфавит;
- выходной алфавит);
- множествовнутренних состоянийавтомата;
- функция перехода в следующее состояние (переходная функция);
- функция выхода (выходная функция).
Таким образом, конечный автомат математически описывается тремя множествами и двумя функциями. Функционирование автомата состоит в том, что он "считывает" последовательность входных символов ("программу") и затем "выпечатывает" последовательность выходных символов. Действие происходит последовательно. Конечный автомат, находящийся сначала во внутреннем состоянии , считывает первый входной символ. Функцияпринимает на парезначение, которое выпечатывается в качестве первого выходного символа. Функцияпринимает на парезначение, которое является следующим внутренним состоянием автомата. Затем автомат считывает новый входной символ, выпечатывает выходной, переходит в следующее состояние и т.д., пока не кончится программа.
На рис.8.1дан удобный способ представления последовательных тактов работы автомата.
Будем предполагать, что программа записана на входной ленте. Автомат считывает с нее входные знаки один за другим. По прочтении каждого входного знака выпечатывается выходной знак на выходной ленте, и автомат переходит в следующее состояние прежде чем считать следующий символ программы. Позже мы введем другие способы представления: графы и таблицы состояний.
В нашем определении подразумевается, что функции ив описа-нии автоматавсюду определены: каждый элементзадает их значения. Такое описание автомата является полным. Коль скоро задано начальное состояние такого автомата, он способен считывать любую программу и выдавать однозначно определенную цепочку символов. Иными словами, существует функция, которая ставит в соответствие любому начальному состояниюи любой последовательности входных символов вполне определенную последовательность выходных символов.
Рис. 8.1. Конечный автомат
Пусть - полученный на вход автомата знак на-м шаге,- состояние, в котором находился автомат на-м шаге, а- знак, который вырабатывает автомат на-м шаге в качестве выходного значения. Работа автомата, то есть переход из состояния в состояние и появление выходных знаков, с использованием функцийиможет быть описано выражениями
( 8.1) | |||
( 8.2) |
|
Поскольку множества иконечны, функции, заданные на их декартовом произведении, удобно задавать табличным способом. Нарис.8.2показан общий вид таблиц, задающих переходную функциюи выходную функциюконечного автомата.
Рассмотрим пример конечного автомата, у которого , имеется два состояния, а функцииизадаются таблицами
0 |
1 | ||||
0 |
1 |
| |||
0 |
0 |
| |||
1 |
1 |
|
Пусть на вход автомата подается последовательность знаков (слово) 1,0,0,1,1,0,1 или в более короткой записи 1001101. Проследим, как меняется состояние автомата в процессе обработки этого слова и какая после-довательность знаков формируется на выходе. Для этого рассмотрим таблицу, состоящую из трех строк. В первой строке записаны знаки, поступающие на вход автомата. Во второй строке записываются состояния, в которых оказывается автомат в процессе обработки входного слова. Наконец, в третьей строке записываются знаки, которые появляются на выходе автомата в результате его работы.
Рис. 8.2. Табличное задание переходной и выходной функций
вход |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
состояния | |||||||
выход |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
Обработка входной последовательности знаков производится по шагам. На каждом шаге обрабатывается один знак. В таблице каждому шагу обработки соответствует один столбец. Пусть в момент поступления первого знака, которым является 1, автомат находился в состоянии . Тогда вна выходе появится знак 0, а в соответствии с определением функцииавтомат перейдет в состояние, которое записывается во вторую строку следующего (второго) столбца таблицы. При поступлении второго знака обрабатываемого слова получим(записывается в третью строку второго столбца таблицы) и(записывается во вторую строку следующего (третьего) столбца таблицы). Процесс обработки следующих знаков происходит аналогичным образом и завершает-ся после обработки последнего знака. В результате исходное слово 1001101 преобразуется в слово 0100110, которое, как можно заметить, является "сдвигом" исходного слова, то есть получается удалением последнего знака из исходного слова и добавлением знака "0" в начало исходного слова.
Помимо рассмотренного табличного способа существует еще графический способ описания (задания) конечных автоматов в виде помеченного ориентированного графа, который называется "диаграмма состояний". Вершины этого графа помечены символами, обозначающими внутренние состояния. Каждое ребро помечено парой символов , где- входной знак, который вызывает переход в следующее состояние, отвечающее этому ребру, а- выходной знак, который автомат выдает в результате обработки входного знака. Из каждой вершины диаграммы выходит столько дуг, сколько знаков имеется во входном алфавите.
Рис. 8.3. Диаграмма состояний сдвигающего автомата
Диаграмма состояний рассмотренного автомата, сдвигающего вправо на один знак входное слово, показана на рис.8.3.
Табличный и графический способы описания конечных автоматов дополняют друг друга. Использование таблиц удобнее для вычислений, а диаграммы более наглядны.
Пусть - некоторый автомат. Выделим одно состояние, которое назовем начальным и с которого будет начинаться обработка всех входящих слов. Тогда любой входной строкедлины, где- знак на-м месте входной последовательности, однозначно соответствует строка внутренних состояний,, длины, где- состояние после-го шага работы, которая получается последовательным применением отображенияпо формуле (8.1). Аналогично выходная строкадлины, где- знак на-м месте выходной последовательности, однозначно определится последовательным применением отображения у/по формуле (8.2).
Таким образом, автомат можно рассматривать как устройство, преобразующее для заданного начального состояния входную строкув строкуи выходную строкуи тем самым реализующее функции (преобразования)и, которые рекурсивно строятся по функциями.