Лекция 3. Постановка задачи обработки информации

1. Лекция 3. Постановка задачи обработки информации. Основные виды, алгоритмы и процедуры обработки информации, модели и методы

решения задач обработки
информации.

2.

Любой вариант процесса обработки информации происходит по следующей
схеме:
В любом случае можно говорить о том, что в процессе обработки информации
решается некоторая информационная задача, которая предварительно может
быть поставлена в традиционной форме: дан некоторый набор исходных
данных — исходной информации; требуется получить некоторые результаты
— итоговую информацию. Сам процесс перехода от исходных данных к
результату и есть процесс обработки. Тот объект или субъект, который
осуществляет обработку, может быть назван исполнителем обработки.
Исполнитель может быть человеком, а» может быть специальным
техническим устройством, в том числе компьютером

3.

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

4.

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

5.

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

6.

• Другой
вид обработки информации — структурирование данных.
Структурирование связано с внесением определенного порядка,
определенной организации в хранилище информации. Расположение
данных в алфавитном порядке, группировка по некоторым признакам
классификации,
использование
табличного
или
графового
представления — все это примеры структурирования.
• Еще один важный вид обработки информации — поиск. Задача поиска
обычно формулируется так: имеется некоторое хранилище информации
— информационный массив (телефонный справочник, словарь,
расписание поездов и пр.), требуется найти в нем нужную информацию,
удовлетворяющую определенным условиям поиска (телефон данной
организации, перевод данного слова на английский язык, время
отправления данного поезда). Алгоритм поиска зависит от способа
организации информации. Если информация структурирована, то поиск
осуществляется быстрее, I можно построить оптимальный алгоритм.

7.

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

8.

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

9.

• Принято
относить существующие архитектуры ЭВМ с точки зрении
обработки информации к одному из следующих классов.
1.
Архитектуры с одиночным потоком команд и данных (SISD). К этому
классу относятся традиционные фоннеймановские однопроцессорные
системы, где имеется центральный процессор, работающий с парами
«атрибут - значение».

10.

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

11.

3. Архитектуры с множественным потоком команд и одиночным потоком
данных (MISD). К этому классу могут быть отнесены конвейерные
процессоры.
4. Архитектуры с множественным потоком команд и множественным
потоком данных (MIMD). К этому классу могут быть отнесены следующие
конфигурации:
мультипроцессорные системы;
системы с мульти обработкой;
вычислительные системы из многих машин;
вычислительные сети.

12.

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

13.

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

14.

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

15.

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

16.

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

17.

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

18.

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

19.

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

20. В настоящее время принято выделять два типа информационных систем поддержки принятия решений.

поддержки принятия решений DSS (Decision Support
System) осуществляют отбор и анализ данных по различным
характеристикам и включают средства:
• Системы
доступа к базам данных;
извлечения данных из разнородных источников;
моделирования правил и стратегии деловой деятельности;
деловой графики для представления результатов анализа;
анализа «если что»;
искусственного интеллекта на уровне экспертных систем

21.

оперативной аналитической обработки OLAP (OnLine
Analysis Processing) для принятия решений используют следующие
средства:
• Системы
мощную многопроцессорную вычислительную технику в виде специальных
OLAPсерверов;
специальные методы многомерного анализа;
специальные хранилища данных Data Warehouse.

22. Модели решения задач обработки информации

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

23.

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

24.

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

25.

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

26. Методы решения задач обработки информации

Функционирование многих ИС носит целенаправленный характер
(примером могут служить автономные интеллектуальные роботы). Типичным
актом такого функционирования является решение задачи планирования
пути достижения нужной цели из некоторой фиксированной начальной
ситуации. Результатом решения задачи должен быть план действий частично-упорядоченная совокупность действий. Такой план напоминает
сценарий, в котором в качестве отношения между вершинами выступают
отношения типа: "цель-подцель" "цель-действие", "действие-результат" и т. п.
Любой путь в этом сценарии, ведущий от вершины, соответствующей текущей
ситуации, в любую из целевых вершин, определяет план действий.
Поиск плана действий возникает в ИС лишь тогда, когда она сталкивается с
нестандартной ситуацией, для которой нет заранее известного набора
действий, приводящих к нужной цели. Все задачи построения плана
действий можно разбить на два типа, которым соответствуют различные
модели: планирование в пространстве состояний (SS-проблема) и
планирование в пространстве задач (PR-проблема).

27.

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

28.

• При
планировании в пространстве задач ситуация несколько иная.
Пространство образуется в результате введения на множестве задач
отношения типа: "часть - целое", "задача - подзадача", "общий случай частный случай" и т. п. Другими словами, пространство задач отражает
декомпозицию задач на подзадачи (цели на подцели). PR-проблема
состоит в поиске декомпозиции исходной задачи на подзадачи,
приводящей к задачам, решение которых системе известно. Например,
ИС известно, как вычисляются значения sin x и cos x для любого
значения аргумента и как 30 производится операция деления.