Размещено на http://www.allbest.ru/

1. Искусственный интеллект

Все начиналось с:

- программирования игр (КАИССА - 1974 - ЧМ по шахматным программам);

- доказательства теорем;

- распознавания образов;

- ЭС;

- естественных языков (ЕЯ).

Язык РЕФАЛ - 1968 г. - Турчин В.Ф.

В то же время был создан и язык LISP.

АПЛЕВ - 1969 - 1-я автоматизированная система доказательства теорем.

УСК - 1974 - универсальный семантический код - Мартынов В.В.

Типы информационных систем:

Всю символьную информацию можно разделить на структурированную (таблицы и т. д.) и неструктурированную (свободный текст).

Информационные системы:

- фактографические (системы обработки структурной информации);

- ДИПС - документально - информационно - поисковые системы;

- САД - системы автоматизации документооборота (LOTUS NOTES).

БД (по сложности алгоритмов и частоте изменения):

- OLTP (системы оперативной обработки данных) - большое количество простых запросов над быстро изменяющимися данными;

- OLAP (аналитические системы) - большое количество сложных запросов над большими массивами медленно изменяющихся данных.

Главные качества:

OLTP:

- надежность;

- время реакции;

- доступ.

OLAP:

- алгоритмы обработки;

- быстрый доступ к большим размерам данных.

В аналитических системах (АС) широко используются интеллектуальные (эвристические) алгоритмы анализа данных.

Введение в реляционные СУБД.

Существуют основные типы моделей данных: иерархическая, сетевая, реляционная, пост реляционная, ООБД (объектно-ориентированная).

Таблица состоит из записей. Запись в реляционной таблице соответствует объекту внешнего мира и содержит описание некоторых его свойств (атрибутов). У всех однотипных объектов используется один и тот же набор атрибутов. Каждая табл. соответствует n-местному отношению.

Первичным (основным) ключом (PK) называется атрибут или группа атрибутов, которые однозначно характеризуют запись.

В качестве PK, как правило, используются искусственные атрибуты, дополнительно включаемые в состав реляционных таблиц. В некоторых СУБД для этой цели используется специальный тип данных (в Access - поле типа «счетчик»). Для быстрого доступа к данным используется индекс - служебная таблица (типа В-дерева), обеспечивающая быстрый доступ.

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

Возможны типы связи: 1:1, 1:N, M:N. Связь M:N реализуется через вспомогательные таблицы.

Access состоит из следующих компонентов:

- таблицы (средства для создания, изменения и просмотра БД);

- запросы (извлечение и изменение информации в БД;

- формы;

- отчеты (вывод на принтер);

- макросы;

- модули (компоненты на VB).

Замечания к созданию системы БД.

Типы данных:

- числовые;

- символьные;

- дата/время;

- подстановка.

При создании поля необходимо указывать основные атрибуты. При использовании поля типа «дата» надо задавать краткий формат.

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

Создание схемы БД:

1. размещаем в окне необходимые таблицы;

2. проводим связи между таблицами;

3. задаем свойства связи:

- ограничение целостности;

- каскадное обновление;

- каскадное удаление.

Ограничение целостности - это, в первую очередь, корректность использования внешних ключей.

Замечание 1:

Для того, чтобы удалить таблицу из схемы БД, необходимо сначала удалить ее связи с другими таблицами.

Замечание 2:

Для просмотра и корректировки содержимого таблицы, запроса и т. д. может использоваться кнопка режима работы «Конструктор/просмотр».

Замечание 3:

В процессе создания таблиц БД можно использовать операцию копирования.

Замечание 4:

При изменении структуры БД желательно каждое изменение выполнять последовательно.

Замечание 5:

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

Запросы.

Запросы делятся на:

- Запрос-выборку;

- Запрос-действие:

- создание новых таблиц;

- модификация данных;

- добавление записей;

- удаление записей;

- Перекрестный запрос.

Сценарий создания запроса:

1. В бланк запроса добавляется необходимая таблица. Таблица «Справочник клиента» добавляется дважды.

Замечание:

При реализации запроса можно использовать дополнительные связи между таблицами и запросами и устанавливать дополнительные свойства для существующих связей.

2. Выбираются необходимые поля.

3. Задаются условия назначения полей (условия, записанные в соседних ячейках одной строки, считаются соединенными логическими операциями «и», в соседних строчках - «или»). Частичное совпадение текстовых строк - Like. Можно использовать .

Для задания интервала значений можно использовать оператор between (Between #17.06.2005# And #23.07.2006#). Для выбора значения из множества - In. В запросе можно использовать вычисляемые поля (значение которых вычисляется исходя из значений других полей используемых таблиц). В выражении для вычисляемого поля можно использовать арифметические и логические операции, функции, логические операторы. Эти выражения задаются в заголовке поля. Для ввода формул и задания условия можно пользоваться «Построителем выражений».

Замечание:

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

Замечание:

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

Групповые операции - операции, выполняющиеся над определенным полем записи, удовлетворяющим условиям запроса.

К ним относятся: max, min, sum, last, first и т. д.

LAST - последняя, с точки зрения порядка, запись, удовлетворяющая условиям запроса.

FIRST - первая, с точки зрения порядка, запись, удовлетворяющая условиям запроса.

Пример запроса, решаемого с помощью групповых операций (Вычисление стоимости накладной при определенных условиях):

1. Создаем запрос, включаем поле «цена - количество»;

2. Нажимаем кнопку «-»:

a. Группировка;

b. Групповые операции;

c. Условие;

d. Выражение.

Стоимость накладных, отгруженных каждым клиентом между определенными числами.

A:

1) Найти клиента из таблицы «Клиент»;

2) Дата из ТТН;

3) Стоимость (вычисляемое поле) из Спецификации.

B: Записываем условие для поля «Дата».

C: Наименование клиента. Условие группировки - Дата. Стоимость - sum.

а) Посчитать для каждого клиента сальдо за период (разность между отгруженным и полученным).

Ситуация, когда по клиенту была только отгрузка или получение товара.

1) Стоимость отгруженных товаров за период (связь от Справочника товаров к Отправителю);

2) Получено: по каждому клиенту;

4) Запрос Справочник клиента:

Запрос Отгружено.

Запрос Получено.

б) Наименование клиента:

1) Стоимость - отгружено;

2) Стоимость - получено;

3) Сальдо Отгружено - Получено.

В результате берутся только те записи, которые есть во всех таблицах.

Стоимость получено/отгружено:



Можно использовать оператор NZ.

Функция NZ позволяет подставить вместо пустого значения любое значение.

1) NZ ст-ть отгруж.;

2) NZ ст-ть получ.;

3) Разница между двумя NZ.

в) Устанавливаем параметры объединения:

1) Объединение только тех записей, в которых связанные поля обеих таблиц совпадают;

2) Объединение всех записей из 1-й таблицы и только тех записей из 2-й таблицы, у которых значения связанных полей совпадают;

3) Объединение всех записей из 2-й таблицы и совпадающих записей из 1-й таблицы.

Замечание 1. В запросах могут использоваться параметры, значения которых вводятся при выполнении запроса. Параметром считается любая символьная строка, заключенная в и не являющаяся именем объекта БД.

Замечание 2. Параметр всегда имеет символьный тип. Для преобразования его в числовой тип используется функция Val.

Перекрестные запросы.

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

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

Модели данных.

Реляционная алгебра.

Существуют следующие модели типов данных:

I. Иерархическая. Схема БД представляет собой совокупность ориентированных деревьев. Записи соответствует путь в дереве. Для реализации связи «многие - ко - многим» используется 2 варианта иерархий.

II. Сетевая. Представляет собой сеть, т. е., ориентированный граф. Вершины - объекты с атрибутами. Связи - связи между объектами. Сложность навигации. Большая мощность.

III. Реляционная. Простота функционирования системы, но медленное быстродействие.

Основное отличие между II и III состоит в том, что связь между объектами в сетевой модели реализуется на внутреннем уровне и недоступна пользователю.

IV. Пост реляционная. Гибрид II и III.

V. ООБД. Одна из наиболее перспективных моделей СУБД.

Реляционная алгебра - алгебра отношений. Реляционная алгебра - это процедурный язык высокого уровня, который применяется в СУБД, для описания манипуляций над данными. Реляционное исчисление - это непроцедурный язык, с помощью которого могут описываться новые отношения допустимые в базе данных. Доказано, что реляционная алгебра логически эквивалентна безопасному подмножеству реляционного исчисления. Доменом называется множество значений атрибута.

Реляционной схемой называется именованное отношение, которое определено на множестве атрибутов и имен доменов. Реляционная схема БД - это совокупность логически связанных реляционных схем.

Где:

R - отношение (имя);

A_i - имя атрибута.

R =

Элементарные понятия - отношения, над ними выполняются следующие операции:

1. Объединение:

Qⁿ=Rⁿ-Sⁿ

2. Пересечение:

Qⁿ=Rⁿ-Sⁿ

3. Разность:

Qⁿ=Rⁿ\Sⁿ

4. Декартово произведение:

Q^n+m=Rⁿ * S^m

5. Сечение или проекция - выделение из таблицы подтаблицы с заданным числом столбцов: Rⁿ.

6. Селекция - выбор элемента, удовлетворяющего условию:

7. Соединение:



Естественное соединение:

Внешнее соединение (левая, правая).

Примеры:

R S:	1	2	3	5	6
	1	2	3	7	8
	4	5	6	7	8

R S	A	B	C	D
	a	b	c	h
	d	b	c	h
	f	c	d	e

Реляционная алгебра является ядром языка манипулирования данными реляционных СУБД.

Реляционное исчисление.

Реляционное исчисление не содержит описания процедур реляционного запроса, а содержит описание свойств отношения, являющегося результатом запроса. Говорим, что является запросом.

Формулой исчисления является конструкция вида:

Где:

t - переменный кортеж;

F - формула.

1. Атом;

2. Если F и G атом F&G, F^G, not F - формула;

3. Если F формула, t - свободная переменная формулы F, t;

4. Все остальное формулой не является.

Атом:

1. R(t) имя отношения t переменная кортежа;

2. RS, где R и S отношения, R - атрибут отношения R;

3. Все остальное не атомы.

- соответствует запросу в реляционной СУБД.

Среди всех формул, допустимых в реляционном исчислении, существуют формулы, задающие бесконечное множество (эти формулы содержат знак “-”). Для преодоления опасных формул оговаривается полное множество всех допустимых значений кортежа. Пример:

_{a1,а2,…,аn}(R)

Где:

t^k - k- местный предикат.

Главным недостатком реляционной модели является ограниченная семантика, поэтому применение реляционных БД сопряжено с большими трудностями.

Предложено:

1. Бинарная реляционная модель;

2. Объектно-реляционная модель.

Основной особенностью реляционной модели является расширенная конструкция, позволяющая описывать семантику предметной области.

Расширенная реляционная модель:

1. на множестве отношений и атрибутов строится модель, аналогичная объектной.

2. используются базовые отношения:

a. наследование (Is-a);

b. часть-целое (Part-of).

Этот подход находит применение в объектно-ориентированных БД. Состоит в иерархическом представлении семантики предметной области.

Модель предметной области включает в себя:

1. интенсиональную;

2. экстенсиональную;

3. процедурную составляющие.

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

Экстенсиональная составляющая - это собственно СУБД. Это описание семантики предметной области в каком-либо языке.

При извлечении информации, запрос описывается в терминах интенсиональной составляющей и это описание транслируется в запросы экстенсиональных составляющих записанных в терминах СУБД.

Формальная модель БД. Технология построения предметной области.

С формальной точки зрения БД состоит из 4 компонент:

Где:

I - пространство ввода;

O - пространство вывода;

М - пространство памяти;

С - пространство кода.

БД на основе имеющейся в ней информации в ответ на запрос q выдает ответ:

Где:

L_I - множество всех запросов к базе данных, L_O - множество всех ответов.

С формальной точки зрения БД - это копия алгоритмов, преобразующая элементы входного языка L_I в элементы внутреннего языка L_М и элементы выходного языка L_O.

Основной проблемой построения БД является построение корректной модели предметной области.

Инфологическая модель предметной области БД состоит из описания объектов, свойств объектов, отношений между объектами, свойств отношений между объектами и ограничения целостности. Описание предметной области в терминах объектов, их свойств, а также ограничение их целостности называется концептуальной моделью предметной области.

Концептуальная модель предметной области - это модель, не зависящая от всех физических подробностей.

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

Особенность: развитие ER модели на основе объектно-ориентированного подхода.

Центральным понятием является понятие объема:

1. идентификатор объема;

2. адекватное описание;

3. выделение свойств объекта.

Идентификатор объема выражается 2-ым наименованием:

1. внешнее имя;

2. внутренне имя - это имя, под которым объект идентифицируется в системе.

Денотат - предмет обозначения знаком, концепт - смысл знака. Объекты могут менять свои имена с течением времени. Формальное разделение объектов и их свойств не возможна. Пример: студент П. родился в 1985 г. И знает английский язык. Под объектом понимают реальную или абстрактную вещь или сущность.

Концептуальная модель предметной области - это описание её в терминах типов объектов и отношений между ними.

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

Пример: Занятие (Предмет, преподаватель, вид занятия, группа, место (корпус, аудитория), время (год, месяц, день)). Однозначное описание объекта описывается местом и временем.

Могут быть объекты или типы объектов, которые исключают любого оператора изменения ими объекта.

На множестве типов объектов с точки зрения ER модели устанавливается только одно отношение:

- объект участвует в ситуации;

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

В рассмотренной объектной модели на множестве типов введено 2 базовых отношения: Is-a, Ins-off.

Задаем на множестве типов решетку - позволяет описывать семантику предметно области.

В каждый момент времени можем проводить только в одной области.

EER не реализует в полной мере средств реляционных СУБД.

Нормальные формы

Для удобства обработки данных в реляционных СУБД используется нормализация, т. е., преобразование схемы БД к виду, обеспечивающему корректность и эффективность выполняемого запроса.

В теории принята следующая классификация:

1. НФ (Первая нормальная форма): каждой нормальной форме соответствует набор ограничений. Отношение находится в первой нормальной форме, если значение атрибута атомарные.

2. НФ: в каждой записи каждый не ключевой атрибут функционально-полно зависим от первичного ключа (первичный ключ может быть составным).

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

Спецификация: нельзя одновременно использовать количество, цену, стоимость.

4. НФБК (НФ Бойса-Кодда): отсутствие транзитивных зависимостей.

Есть и другие нормальные формы, но на практике используются первые 4.

Понятие транзакции.

Сервер как физическое устройство - это 1 или несколько компьютеров, обеспечивающих все операции по хранению и обработке данных.

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

Файл-серверные системы - только хранение данных и доступ к ним.

Клиент северные системы - все действия над файлами выполняются на сервере.

Пример файл-серверной системы: средствами СУБД Access организована одновременно работа с нескольких терминалов с общей БД.

Клиент-серверная архитектура:

- надежность;

- меньше хранимых данных.

Однако необходим мощный сервер.

Транзакция - это неделимая последовательность операций манипулирования данными (с точки зрения СУБД).

Транзакция - это осмысленно-законченное действие (с точки зрения клиента).

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

1. Атомарность;

2. Согласованность;

3. Изолированность (транзакции различных задач выполняются независимо друг от друга и не пересекаются при обработке одних данных).

4. Долговечность (результаты выполнения транзакции не могут быть потеряны ни при каких условиях).

Фиксация транзакции - это запись в БД всех изменений выполненных транзакцией.

Откатка транзакции - это отмена части или полная отмена всех изменений выполненных транзакцией.

Все действия в БД есть совокупность транзакций.

В состав СУБД входят специальные компоненты, называемые монитором транзакций, они обеспечивают их корректное выполнение.

Монитор транзакций функционирует на основе журнала транзакций - специальный механизм выполнения фиксации и отката транзакции.

Основная проблема синхронизации транзакции - проблема блокировки.

Две транзакции блокирую друг друга:

Данная задача алгоритмически не разрешима и для её разрешения используется некий набор правил.

В стандарт SQL входят специальные операции для фиксации и отката транзакций.

Распределенная транзакция выполняется одновременно на нескольких компьютерах.

Распределенная транзакция реализуется по следующей схеме:

1. Компьютер инициализирует транзакцию, рассылая задачи по всем компьютерам сети.

2. Каждый компьютер выполняет свою часть транзакции.

3. Начальный компьютер рассылает команду о фиксации транзакции.

Если 2 пункт на каком-либо этапе выполниться не может, тогда выполняется откат на всех компьютерах сети.

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

Можно выделить 2 подхода:

1. Тиражирование данных.

2. Механизм репликаций (обеспечивает согласование данных при их асинхронном изменении).

Документные информационные поисковые системы (ДИПС).

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

Информационная потребность пользователя - это та информация, которая необходима пользователю (формируется в виде запроса по специальным правилам).

Пертинентность - это соответствие содержания документа информационной потребности пользователя.

Релевантность - это соответствие содержания документа информационному запросу.

Качество ДИПС зависит от технологии поиска релевантных документов. Общая схема ДИПС:

Подсистема А: ввод и регистрации документов.

Решаемые задачи:

- преобразование документов в электронный вид;

- регистрация документов;

- удаленный доступ.

Подсистема В: обработка документов:

- ведение словаря;

- формирование поискового образа документа;

- поисковые предписания (то на основе чего выполняется поиск).

Для эффективности поиска документов поисковые образы отражаются в структуре (индекс).

Подсистема С: поиск документов:

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

Подсистема D: ведение и хранение документов.

Качество ИПС:

1. Модель документа (ПОД);

2. КСС (алгоритм поиска релевантных документов).

Модель документа описывается в неком языке:

1. Формальный язык;

2. Подмножество естественного языка.

Основная проблема - это проблема неоднозначного смысла естественного языка, который связан с наличием контекста (синонимы, омонимы).

Пример построения ДИС. Кластеризация документов.

Набор понятий в этой предметной области d_ij - это значение j - того термина в i - том документе.

В простейшем случае:

Запрос:

- значимость j - того термина для запроса.

Пусть в базе данных m-документов , I =1. В качестве соответствия могут использоваться следующие функции: S (z,d) - мера Дайеса:

S (z,d) =

S (z,d) =

Эффективность такого подхода зависит от качества словаря.

Формально, качество словаря можно оценить следующим образом.

Назовем центроидом:

G = g_{j =}

Где:

- параметр, подбираем эмпирически.

SD =

- плотность простр. документов.

SD_j =

- плотность простр. документов без j - того термина.

Все термины делятся на три группы (из семантики терминов):

1. часто встречающиеся слова;

2. слова с высокой разрешимой способностью;

3. редко встречающиеся, существенные термины.

Закон Ципфа:

Где:

- частота встречи слова;

- значимость.

Те слова, у которых большое:

I - отбрасываются вообще;

III - могут заменяться синонимами.

Слова с отрицательной разрешимой способностью в группы.

Слова с невысокой разрешимой способностью заменяются синонимами.

Кластеризация:

Так как количество документов m>, то для эффективного поиска желательно объединить документы в группы. Этот процесс называется кластеризацией. А группа - кластером.

D^nxm = d_ij =

D^nxm-S_ij = d_ij/

S_ij= d/

C^nxn = Sx *

- матрица коэффициентов покрытия.

С' =

- взаимозависимость документов.

С - значимость термина в документе

С' - значимость документа для термина

Где:

- средний коэффициент уникальности;

- средний коэффициент связи;

- теоретическое число кластеров.

m_c = 1 / s

- среднее число документов в кластере.

Кластер - это группа документов близких по содержанию.

p_i =

Где:

t_i = - собирательная способность документа.

1. Вычисление p_i;

2. Выбирается документов, с max значением собирательной способности;

3. Для каждого элемента в матрице С находим ядра ;

4. Для каждого находим d_k :

Где:

d_j - относительно к кластеру С_k если .

При совпадении с_jk для нескольких кластеров выбирается кластер с максимальной собирательной способностью.

Для документа, у которого с_jk=0 образуют отдельный кластер, либо присоединяются к кластеру в который входит документ наиболее близкий к ним по смыслу.

Набор кластеров: с^k, k.

Для каждого кластера строится обобщенный образ документов этого кластера.

- средняя частота термина i в кластере в документе, который содержит этот термин.

Где:

- число кластеров документов, которые содержат этот термин;

Fⁱ_j - частота использования термина i в документе j кластера.

Замечание:

- коэффициент ослабления.

Если центроид кластеров содержит мало 1, то можно использовать для того, чтобы увеличить представление терминов.

Далее процесс повторяется для центра. При этом термины, значения которых = 0 для всех центров, могут быть исключены.

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

При расширенном поиске выделяем сразу группы кластеров. В качестве критерия семантического соответствия удобно использовать меры близости (коэффициент косинуса или меру Дайеса).

При поиске выбираем те вершины, у которых С_oi:

Из дерева кластеров вырезается поддерево. Если запрос содержит логические операции (и, не, или), то им соответствуют дополнение, пересечение, объединение.

Иногда вектор запроса допускает использование отрицания:

Z_i =

В качестве меры близости могут использоваться:

SIM(Z,g) =

F₁(Z_j,g_j) = ;

F₂(Z_j,g_j) =

1. Генетические алгоритмы;

2. Муравьиные алгоритмы;

3. Эволюционное программирование;

4. Нейронные сети;

5. DNA Computing;

6. Клеточные автоматы.

Генетические алгоритмы: Моделирование естественного отбора. Каждому объекту из «А» ставится в соответствие хромосома (последовательность элементов составл., которая называется геном) (как правило - это линейный вектор). U(a) - мера полезности состояния а (или мера близкая состоянию а к целевым состояниям).

На множестве А вводим операции, каждая описывает возможности преобразования хромосом:

Мутация: выбирается случайным образом генетическое значение, каждое заменяется (0->1).

Инверсия: V1(a), V2(a), V3(a) (порядок следования в средней части меняется на противоположное). Этапы:

1. А⁰ - случайное множество ситуаций (строится).

2. Выбираем подмножество ⁰ такое что:

Выбираем самые полезные пары функция полезности.

3. Строится S⁰(⁰) - множество позиций, каждая может быть построена с помощью операции:

(⁰) = {a| a? S⁰(⁰) U(a)>

Получаем:

А1 = ⁰ - S(⁰)

Повторяем 1-4 до А_i=A_i-1.

Пример использования: (использование для поиска экстремумов функций для решения не полиномиальных задач).

Нахождение гамильтонового цикла: замкнутый цикл, проход по всем вершинам один раз минимального веса.

Любой гамильтоновый путь описывается числами 1,…,n.

Операция 1: 1, 2 выбираем случайным образом j (ген).

j=3.



Из вектора 1 выбираем первые j элементов, которые добавляем элементам 2 отсутствующие в первых элементах из 1.

Мутация: Выбираем два гена i и j и меняем местами.

Инверсия: Выбираем i и j и часть цепочки записываем в обратном порядке.

Частота использования мутации и инверсии ниже, чем операции 1.

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

Функция n - переменных.

F(x1, x2,…xn), x1 - 4 байта (вещественные числа).

4 n - байтов.

32 n - байта.

Муравьиный алгоритм.

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

Поведение муравьёв регулируется 4 факторами:

1. Случайность.

2. Многократность.

3. Положительная обратная часть.

4. Отрицательная обратная часть.

Задача состоит из многократных элементов по поиску муравьиного гамильтонового цикла:

d_ij - расстояние между городами;

1d_ij - видимость (длина дороги).

Для каждого муравья задаётся массив TL (список посещённых городов).

P_ijk - вероятность перехода муравья k из города i в j в момент времени t.

P_ijk(t) =

Замечание.

Для ускорения процесса сходимости можно использовать элитных муравьёв, которые на каждой итерации увеличивают оценки полезности рёбер, входящих в кратчайший путь на величину е_min.

Использование нескольких элитных муравьёв ускорят сходимость алгоритма к субоптимальным решениям.

Выбор оптимального количества муравьёв зависит от задачи. Если мы не используем элитных муравьёв, то мы найдем оптимальное решение, но это достаточно долго. Если 1 или 2 муравья (элитных), то найдем быстрее решение, но с недостаточной точностью. Количество муравьёв = число вершин.

Вычислительные задачи.

Называется тройка: А=(B, R, F), где В - исходное множество объектов, R - множество условных зависимостей, F - множество функциональных зависимостей.

F : 2^B->B

Где:

2^B - множество всех подмножеств множества В.

Условные зависимости - это зависимости вида: если p(x) - предикат, то F(x) - функциональная зависимость.

Понятие вершин в графе.

Последовательность вершин в гиперграфе V₁,…V_n называется гипер путём в гиперграфе Н, если существует (e₁,…,e_k) - линейная последовательность такая, что принадлежит {V₁,…V_n}.

Разбиение:

(V₁,…V_n) = {V₁¹,…V_n1} - {V₁²,…V_n2²}

Существует гипер ребро, инцидентное вершинам, как из первого, так и из второго подмножества.

Для нахождения гипер пути можно воспользоваться алгоритмом обхода в ширину.

На практике используются 3 модификации этого алгоритма:

1. Прямая волна (X->Z);

2. Обратная волна(Z->X);

3. Встречная волна (минимальное пересечение прямой и обратной волны).

Для больших задач 3 алгоритм эффективнее, чем 1 и 2.

Замечание.

Вычислительная модель - это компактный способ описания А (множество ситуаций). Вместо перечисления описывается схема генерации элементов.

В рекурсивной вычислительной модели число элементов множества А экспоненциально зависит от количество элементов.

Использование рекурсивных вычислительных моделей требует использования «общих знаний о мире».

Это отношение равенства.

Продукционные системы.

Продукция или правило: если А, то В.

{P_i}_i^u - множество операндов (вместо последовательности).

Множество продукций выполняется параллельно или асинхронно.

Недостатки:

1. Сложность отладки;

2. Не противоречивость или верификация;

3. Эффективность.

Продукцией называется выражение следующего вида:

Q, P, AB, N, где i - имя продукции, Q - сфера примененной продукции, Р - условие применимости продукции (набор предикатов).

A->B называется ядром продукции. Как правило можно интерпретировать: если А, то В

Если А, то В иначе С.

Если А, то В.

Если не А, то С.

А - не обязательно логическое выражение. Условие применимой продукции может быть выражена структурно. Например: наличие некоторой конструкции в предметной области.

N - пустословие. Некая последовательность действий, которая выполняется после успешного выполнения продукции. Транзакции являются частным случаем продукции.

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

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

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

С этими данными работают компоненты Q, N, P. Информационная доска объявлений позволяет процессам вывода в продукционной системе и делает наглядный процесс отладки. Структура алгоритма отражается в доске объявлений.

управление информацией	предметная область
доска объявлений (взаимодействие между продукцией)	ядра (описание предметной области)

Возможно не только параллельное выполнение системы, но и разработка системы. Существуют различные способы реализации продукции систем.

Использование: В системе автоматического проектирования - таблица принятия решения. Описания продукции систем являются табличной формой. Базовой формой ТПР является следующая структура.

	Условия
Операнд 1	Значение
Операнд 2
	действие

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

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

Существуют различные виды таблиц принятия решения. По типам элементов ТПР подразделяются на:

1. таблицы с ограниченными элементами;

2. таблицы с расширенными элементами;

3. таблицы со смешенными элементами.

Ограниченные элементы: да, нет, неопределенно. Действия могут также отсутствовать. Расширенные элементы исполнения числовых значений и отношений <, >, =, а так же логические операции отношения между ними.

Смешенные элементы - это объединения в одной таблице элементов двух типов.

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

Каждой ТПР соответствует дерево, и эффективность работы таблиц напрямую связана со структурой дерева.

Формат таблиц принятия решения.

Чаще всего описания модели предметной области задаётся в виде совокупности таблиц принятия решений.

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

Иногда в описании таблицы включены компоненты p и q.

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

Как правило, действия бывают следующих 3-х видов:

1. присвоить - изменение значения переменной соответствующей заголовку данного столбца;

2. вычислить - результат выражения присваивается некоторому столбцу;

3. выполнить - выполняется процедура, соответствующая столбцу.

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

2. Экспертные системы

Предпосылки возникновения экспертных систем (ЭС).

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

2. Проблема отчуждения знаний или создание некого информационно-переносимого источника знаний.

3. «Математика как универсальный язык бесполезна в ИИ. Языком ИИ должен быть язык интеллектуальных программ». Компонента объяснения не противоречит.

ЭС должна не только формулировать ответ на зарос, но и объяснять, почему этот ответ корректен.

Схема ЭС:



Интерфейс должен включать в себя:

- программу грамматического разбора;

- подсистему интерпретации выходной информации;

- подсистему оформления результатов работы ЭС;

- подсистему формирования выходной информации.

Доска объявлений - подсистема, демонстрирующая процесс принятия решений экспертной системой.

Доска объявлений содержит следующие основные компоненты:

- планы (способы, которые предполагается решать);

- заявки (потенциальные действия);

- решения (решения текущих подзадач в системе со связями между ними).

Диспетчер управляет заявками и определяет порядок их выполнения.

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

Компонента объяснения непротиворечивости согласовывает полученные решения и обеспечивает уверенность в том, что полученные решения разумны.

Компонента оправдания объясняет пользователю действия системы и правдоподобность полученного решения.

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

Создание ЭС возможно и оправдано, если выполняются следующие требования:

- существуют эксперты, которые решают эту задачу лучше, чем начинающие специалисты;

- эксперты принимают согласованные решения, т. е., они сходятся в оценке предлагаемых решений;

- эксперты способны формализовать, вербализовать, т. е., выразить на естественном языке, и объяснить используемые ими методы;

- задача не должна быть слишком трудной, т. е., для ее решения эксперты должны тратить дни, а не недели;

- предметная область задачи должна быть достаточно структурирована, т. е., возможно построение информационной модели предметной области;

- решение задачи должно в основном упираться не на общие, а на частные знания о мире;

- решение задачи требует только рассуждений, а не действий.

ЭС оправдана, если имеет место:

- решение задачи принесет значительный эффект, например, экономический;

- использование человека-эксперта невозможно;

- процесс разработки ЭС значительно меньше, чем подготовка эксперта-человека.

Замечания по структуре.

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

Наиболее часто эта подсистема использует генетические алгоритмы и/или нейронные сети.

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

Этапы разработки ЭС.

Разработка ЭС имеет ряд отличий от разработки обычного ПО.

- Концептуализац;

- Тестирование;

- Опытная эксплуатация;

- Идентификация;

- Реализация;

- Формализация.

Идентификация - определение задач, целей и разработки, пользователей и экспертов. Решается вопрос о целесообразности и возможности создания ЭС.

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

На этапе формализации строится формальная модель предметной области, среда разработки, способы представления всех видов знаний, фиксируются понятия, методы решения, средства представления и манипулирования знаниями.

Этап реализации включает в себя с одной стороны создание кода информационной системы, с другой стороны - наполнение экспертами БЗ. Эти процессы взаимно влияют друг на друга.

На этапе опытной эксплуатации сопоставляются решения, принятые экспертами, с результатами работы ЭС. Качество работы системы оценивается экспертами.

Тестирование соответствует этапу внедрения обычной системы. Система оценивается пользователем.

Пример построения ЭС. Подход на основе теоремы Байеса.

Пусть имеется набор признаков q₁,q₂,…,q_k. Необходимо по набору значений, признаков определить наиболее вероятную гипотезу.

Эмпирическим путем можно определить следующие параметры:

- p(S_i) - априорная вероятность;

- (p) появления признака S_i, не зависящая ни от чего.

Признаки q_i не независимы и не образуют полного разбиения вероятностного пространства. БД информационной системы (ИС) состоит из следующих наборов данных:

1. описание признаков (j,N_j,W_j,T_j):

j - номер признака;

N_j - наименование признака;

W_j - вопрос, с помощью которого проверяется наличие признака;

T_j - тип признака (шкала).

2. таблица гипотез (i,N_i,P_i):

i - номер гипотезы;

N_i - наименование гипотезы;

P_i - априорная вероятность появления гипотезы.

3. таблица соответствия признаков и гипотез (i,j,p⁺,p^-):

i - номер гипотезы;

j - номер признака;

p⁺ - вероятность наличия j-го признака при наличии i-ой гипотезы;

p^- - вероятность наличия j-го признака при отсутствии i-ой гипотезы.

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

p(q_j) = p(q_j/S_i) - p(S_i) + p(q_j/S_i) - p(S_i) = p(q_j/S_i) - p(S_i) + p(q_j/S_i) - (1 - p(S_i))

- априорная вероятность при ответе «да».

p(S_i/q_j) = (1-p(q_j/S_i)) - p(S_i)/p(q_j)

p(q_j) = (1-p(q_j/S_i)) - p(S_i) + (1-p(q_j/S_i)) - (1- p(S_i))

- априорная вероятность при ответе «нет».

Признак q_i - подтверждающий гипотезу S_i, если:

p(S_i/q_j) - p(S_i)

Тогда для любой гипотезы можно подсчитать - max возможная апостериорная вероятность гипотезы S_i, т. е., вероятность, которая получается при ответах «Да» на все подтверждающие вопросы и при ответах «Нет» на опровергающие вопросы. - min возможная апостериорная вероятность (текущие оценки).

Очевидно, что для того, чтобы система была корректной, допустимые интервалы для любой гипотезы должны пересекаться. Это значит, если возникает ситуация , то система некорректна, т. к., это значит, что гипотеза S_i никогда не может быть принята:

Замечание 1:

Точная оценка вероятности весьма затруднительна, т. к., множество всех гипотез может быть весьма большим. Если мы уверены, что гипотезы S₁,…,S_k образуют полное пространство гипотез, то для оценки можно воспользоваться формулой полной вероятности.

Замечание 2:

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

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

В каждый момент времени:

- - -

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

Две гипотезы равноправны, если:

|P*(S_i)- P*(S_j)|

Пусть для некоторой гипотезы:

-

И для всех остальных гипотез:

Тогда все гипотезы правдоподобны.

Это значит, что для любой гипотезы могут быть дополнительно заданы:

 : - - -

И при этом гипотеза считается неправдоподобной, если:

p*(S_i) >

p*(S_i) -

Ценой свидетельства называется следующая величина:

z(q_j) = ^k_i=1 |p (S_i/q_j) - p (S_i/q_j)|

Логично, что в первую очередь рассматриваются вопросы/признаки, имеющие наибольшую цену. Кроме порядка, налагаемого ценой свидетельства, используется порядок, объясняющий пользователю результат работы системы.

Общий сценарий работы системы:

1. вычисляем цены свидетельств z(q_j);

2. проверяем свидетельство с max ценой;

3. вычисляем:

p * (S_i / q_j)

- гипотезы, i=1,k.

4. отбрасываем неправдоподобные гипотезы.

Представление знаний в ЭС. Логический вывод. Логика предикатов I-го порядка.

Автоматическое доказательство теорем.

Основ АДТ заложены математиком Эрдан (1930 г.). В 1965 г. Робинсон предложил метод резолюций, который и составляет основу Prolog'а. В ЛОМИ создали АПЛЕВ (1969 г.).

Исчисление высказываний.

Высказывание - некоторые логические конструкции, о которых можно сказать, истинны они или ложны.

Приняты обозначения:

Для каждой из логических операций строится таблица истинности. Все логические операции можно свести к одной (стрелка Пирса или штрих Шеффера). Истинность логической формулы проверяется с помощью таблиц истинности.

Если в формуле используется n переменных, то таблица истинности содержит 2ⁿ вариантов.

Интерпретацией формулы называется приписывание истинностных значений входящим в формулу высказываниям (атомам).

Формула называется общезначимой или тавтологией, если она истинна для всех своих интерпретаций.

Формула называется ложной или противоречивой, если она ложна при любых своих интерпретациях.

Если формула не является ложной, то она называется непротиворечивой или выполнимой.

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

Такого рода конструкции называются ДНФ или КНФ.

Конструкция вида:

- называется теоремой.

Логика предикатов I-го порядка. Запись вида f (x1,…,xn) будем называть n-местным функциональным символом, а P (x1,…,xn) - n-местным предикатным символом. Функция - это отображение, ставящее в соответствие списку констант с1,с2…,сn константу y.

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

- сумма (х, у);

- площадь (a, b, c).

Каждый n-местный функциональный символ может быть сведен к (n+1) - местному предикату.

Для каждой переменной указывается область допустимых значений.

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

Терм - это:

1. константа;

2. переменная;

3. n-местный функциональный символ;

4. все остальное термом не является.

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

Замечание.

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

Предваренная нормальная форма (ПНФ).

Формула F находится в GYA тогда и только тогда, когда она имеет вид:

(Q₁x₁) (Q₂x₂)…(Q_kx_k) (М)

Формула М не содержит кванторов.

(М) - матрица, (Q₁x₁) (Q₂x₂)…(Q_kx_k) - префикс.

Для преобразования произвольной формулы в GYA используется правила 3.1-3.4.

Скулемовская стандартная форма (ССФ).

Пусть формула F находится в ПНФ. Выполним следующее преобразование. Пусть Q_i - квантор существ с минимальным номером. Заменим все вхождения x_i на c_i при i=1, а если i>1.

Применяя последовательно этот процесс, получим формулу, в которой все переменные связаны только квантором всеобщности. В этом случае говорят, что формула f находится в ССФ.

Резольвентой формул F₁ и F₂ называется формула:

G = P - R

Формула G является логическим следствием формул F₁ и F₂.

Доказательство:

Если F1 истина, то Q={и, л}.

Дизъюнктом называется конъюнкция формул, каждая из которых состоит из атомарных предикатов, возможно со знаком отрицания, соединенных операцией «или».

Унификация 2-х формул состоит в выборе подстановки, превращающей две формулы в эквивалентные строки.

Запись вида {x|t} будет обозначать: t является подстановкой для x.

Имеет место следующее правило подстановки:

- нельзя заменять константы, имена функций;

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

- переменная не может быть заменена термом, её содержащей.

Две различные формулы, содержащие одинаковое имя предиката, не всегда унифицируемы. Резолюция - это процедура вывода, основанная на построении опровержений.

Количество дизъюнктов в резолюции растёт экспоненциально, поэтому для управления выводом используются эвристики.

Набор дизъюнктов называется невыполнимым, если не существует интерпретации, доказывающей истинность этого набора.

Правило вывода (процедура вывода) называется полным в смысле опровержения, если невыполнимость любого набора дизъюнктов может быть доказана с помощью этого правила.

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

Алгоритм метода резолюций:

1) Каждая формула F_i и G преобразуется к ССФ;

2) Строим совокупность дизъюнктов для этой задачи;

3) Используя полный обход в ширину, последовательно строим пустой дизъюнкт.

Замечание.

Если теорема не может быть доказана, то процесс вывода может быть бесконечным. Количество дизъюнктов не ограничено.

Кроме полного перебора, используются:

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

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

- стратегия множества поддержки (на каждом шаге одна из 2-х резолюций является предком множества:

T * (С = T - S)

Заключение

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

Семантические сети (СС).

Сетевое представление является развитием логического подхода представления информации.

Основные направления:

- семантические сети;

- концептуальные графы;

- фреймы.

Информация представляется в виде ориентированного графа или гиперграфа.

Вершины соответствуют объектам, дуги или гипердуги - отношениям.

СС представляет собой двудольный граф, вершины одной доли соответствуют объектам, второй - отношениям между ними.

Многоуровневые многозадачные логики.

Концептуальный граф соответствует логической формуле или простому предложению естественного языка. Объединение концептуальных графов иногда называется СС. Наиболее удобным для сетевого представления являются бинарные отношения, поэтому произвольные n-местные предикаты заменяются бинарным (n+1) предикатом. Это представление часто используется при создании объектно-ориентированных БД. В СС должны быть представлены объекты, отношения, типы объектов, типы отношений, экземпляры объектов и отношений. Кроме того, на множестве типов объектов заданы базовые отношения: элементы множества и множество подмножества. Т. о., получается решетка типов объектов, которая обеспечивает наследование свойств объекта.

...