![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Классификация вычислений
К настоящему времени выделено 5 классов вычислений: 1. аналоговые вычисления; 2. цифровые вычисления; 3. словесные вычисления; 4. реляционные вычисления; 5. смысловые вычисления; Особенность аналоговых вычислений состоит в том, что аргументы являются непрерывными величинами. Исследуются аналоговые вычисления в вычислительной математике: дифференцирование, интегрирование и т.д. Цифровые вычисления определяются тем, что аргументы дискретны. Они исследуются в дискретной математике. Для словесных вычислений аргументами являются последовательности символов, лишенные кого-либо смысла. Реляционные вычисления определяют в качестве аргументов отношения между последовательностями символов. Иногда говорят, что отношения могут задавать смысловую характеристику символов. Общим свойством этих четырех типов вычислений является то, что функция является величиной определенной, известной. Для смысловых вычислений характерно неполное или вообще неизвестное задание самой функции. Аргументами смысловых вычислений являются последовательности отношений между структурами символов. Причем интеллектуальный объект должен сам определить или доопределить функцию вычислений и построить структуру взаимосвязи между отношением. В настоящее время под обработкой знания понимаются вычисления словесного уровня и выше. К сожалению, смысловые вычисления так и не разработаны. Под обработкой знаний понимается вычисление от символьного уровня и выше. Основные направления в развитии систем ИИ, подразделяются: 1. экспертные системы – 60% исследований; 2. естественные языковые системы – 25% исследований; 3. прочие направления: эволюционные, генетические алгоритмы, интеллектуальные технические системы, в том числе системы технического зрения, многозначные логики; История развития ИИ. Родоначальником принято считать испанского философа и математика Раймонда Луллийя, жившего в VIII веке. Он впервые создал механическую машину для решения любых задач на основе всеобщей классификации. В 1960 году была создана лабиринтная модель мышления, а также, велись разработки поисковых эвристик для лабиринтной модели мышления. Эвристика – это практически рациональная, но фактически не обоснованная модель. В 70-е годы 20-го века - развитие логического подхода в ИИ. Были разработаны: метод резолюций, заложенный в язык пролог, и обратный метод Маслова. Вместе с тем логический подход оказался ограниченным, так как в условиях задачи обязательно должны были присутствовать аксиомы из предметной области, а это не всегда возможно. С 80-го года развивается направление – экспертные системы. (Экспертная система – специализирующая программа, ориентированная на решение поисковых и ориентированных задач на основе заложенных знаний экспертов). Успех экспертных систем предопределён отказом от глобальных направлений жесткости ориентации на предметную область, вместе с тем, в рамках экспертных систем были получены новые модели знаний, в том числе фреймовая модель. Рассмотрим задачу линейного программирования с точки зрения неопределенности вычислительного процесса и свобода выбора действий исполнителя. Важнейшими свойствами, присущими представлениям знаний в СППР [Еремеев А.П. Организация параллельных вычислений на основе моделей потока данных // Изв. РАН. Техн. кибернет., 1993, № 3, с. 212-225] являются внутренняя интерпретируемость, структурированность, связность, семантическая метрика, активность. Качественная диаграмма перехода от данных к знаниям представлена на рисунке 1.2. Перечисленные пять свойств информационных единиц - знаний - определяют ту грань, за которой данные превращаются в знания, а базы данных - в базы знаний. Совокупность средств, обеспечивающих работу с знаниями, образуют систему управления базой знаний (СУБЗ). В настоящее время не существует баз знаний, в которых в полной мере были реализованы внутренняя интерпретируемость, структуризация, связность, введена семантическая мера и обеспечена активность знаний. Рисунок 1.3 - Диаграмма свойств информационных единиц «данные –знания» Внутренняя интерпретируемость. Каждая информационная единица должна иметь уникальное имя, по которому инструментальная единица находит ее, а также отвечает на запросы, в которых это имя упомянуто. Когда данные, хранящиеся в памяти системы, были лишены имен, то отсутствовала их идентификация системой. Данные могла идентифицировать лишь программа, извлекая их из памяти по указанию программиста, написавшего программу. Семантика данных, заключенная в машинном коде машинного слова, является неопределенной. Знания же всегда содержательны как на уровне представления, так и на уровне обработки и интерпретации. При переходе к знаниям в память ЭВМ вводится информация о некоторой схеме информационных единиц. При этом должны быть заданы специальные словари, в которых перечислены имеющиеся в памяти системы сведения об информационных единицах. В настоящее время СУБД обеспечивает реализацию внутренней интерпретируемости всех информационных единиц, хранимых в базе данных. Структурированность. Информационные единицы должны обладать гибкой структурой. Для них должен выполняться «принцип матрешки», т. е. неограниченная рекурсивная вложенность одних информационных единиц в другие. Каждая информационная единица может быть включена в состав любой другой, и из каждой информационной единицы можно выделить некоторые составляющие ее информационные единицы. Другими словами, должна существовать возможность произвольного установления между отдельными информационными единицами трех важнейших отношений типа «часть-целое», «род-вид» или «элемент-класс». Эти отношения определяют компактность описания информационных единиц и наследуемость ее свойств. Связность. Между информационными единицами должна быть предусмотрена возможность установления связей произвольного типа. Прежде всего, связи могут характеризовать отношения между информационными единицами. Семантика отношений может носить декларативный или продукционный характер. Например, две и более информационные единицы могут быть связаны отношением «одновременно», две информационные единицы — отношением «причина-следствие» или отношением «быть рядом». Приведенные отношения характеризуют декларативные знания. Если между двумя информационными единицами установлено отношение «аргумент—функция», то оно характеризует процедурные знания, связанные с вычислением определенных функций. Существуют отношения структуризации, функциональные отношения, каузальные отношения и семантические отношения. С помощью первых задаются иерархии информационных единиц, вторые несут процедурную информацию, позволяющую находить (вычислять) одни информационные единицы через другие, третьи задают причинно-следственные связи, четвертые соответствуют всем остальным отношениям. Между информационными единицами могут устанавливаться и иные связи, например, определяющие выбор информационных единиц из памяти или указывающие на то, что две информационные единицы несовместимы друг с другом в описании. Перечисленные три особенности знаний позволяют ввести модель представления знаний - семантическую сеть, представляющую собой граф, в вершинах которого находятся информационные единицы. Эти единицы снабжены индивидуальными именами. Дуги семантической сети соответствуют различным связям между информационными единицами. При этом иерархические связи определяются отношениями структуризации, а не иерархические связи — отношениями иных типов. Семантическая метрика. На множестве информационных единиц полезно задавать отношения, характеризующие ситуационную близость информационных единиц, т. е. силу ассоциативной связи между информационными единицами. Его можно назвать отношением релевантности для информационных единиц. Такое отношение позволяет выделять в базе знаний некоторые типовые ситуации. Отношение релевантности при работе с информационными единицами позволяет находить новые знания, близкие к уже найденным, что позволяет вести. Активность. С момента появления ЭВМ и разделения, используемых в ней информационных единиц на данные и команды создалась ситуация, при которой данные пассивны, а команды активны. Все процессы, протекающие в ЭВМ, инициируются командами, а данные используются этими командами лишь в случае необходимости. Для ИнС характерна ситуация, при которой выполнение программы запускается текущим состоянием информационной базы. Появление в базе фактов или описание событий может стать источником активности системы. Таким образом, свойство активности имеет наибольший ранг в понимании информационных единиц как знаний. Независимо от реализации ЯПЗ должен отвечать следующим требованиям: наличие простых и вместе с тем достаточно мощных средств представления сложно структурированных и взаимосвязанных объектов; возможность отображения описаний объектов на разные виды памяти ЭВМ; наличие гибких средств управления выводом, учитывающих необходимость структурирования правил работы решателя; «прозрачность» системных механизмов для программиста, т. е. возможность их до определения и переопределения на уровне входного языка; возможность эффективной реализации, как программной, так и аппаратной; Конечно, перечисленные требования во многом противоречивы. Но лишь тогда, когда в рамках разумного компромисса учтены все эти требования, создаются удачные ЯПЗ.
Пусть требуется достигнуть минимум целевой функции;
Приведем систему ограничений к виду уравнений путем добавления новых переменных Для системы двух уравнений с шестью переменными существует бесконечное множество решений, среди которых оптимальное получается путем выбора базисных переменных. Набор базисных переменных описывается следующим образом, (
Формируем первое базисное решение на основе полученной системы:
Для увеличения значений Возьмём, например, в качестве базисной переменной
Поскольку ограничения роста по Выразим новую базисную переменную через свободную. Тогда
Получим для базисных переменных Вычислим значения целевой функции при базисных переменных Значение целевой функции, равной 36, не является минимальной, так как его можно уменьшить за счет переменных Определим свободную переменную
Поскольку на Получим новый базис Выразим новые базисные переменные через свободные. Для этого возьмём исходную систему уравнений, и второе уравнение увеличим вдвое
На основании полученного значения для Базисное решение будет иметь вид:
Вычислим значение целевой: Данное значение является минимальным, так как при свободных переменных все коэффициенты положительные. Вернемся к базису
Поскольку на Значение базисных переменных через свободные рассчитаем Рассчитаем для базиса В дальнейшем необходимо
Для исходной системы уравнений возможно четыре варианта выбора первого базисного набора переменных. Набор Рассмотрим некоторые пути в дереве решений данной задачи. Данное дерево решений описывает все возможные траектории для получения оптимального результата, поскольку оптимальный результат единственный, и существует, то конкретная траектория движения не имеет значения достижения результата. Вместе с тем, при существовании времен, ограничен поиск решения, актуальным встает вопрос поиска минимальной траектории.
ЛЕКЦИЯ 4
|