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

Отметим основные свойства, присущие любому алгоритму.

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

2. Понятность алгоритма. Алгоритм составляется с ориентацией на определенного исполнителя. У каждого исполнителя имеется свой перечень допустимых предписаний, которые этот исполнитель понимает и может выполнить. Этот перечень называется системой команд исполнителя (СКИ). Алгоритм должен включать в себя только те предписания, которые входят в СКИ.

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

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

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

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

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

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

30. Основные этапы и методы разработки алгоритма. Типы алгоритмов. Понятие блок-схемы. Способы записи алгоритмов.

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

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

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

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

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

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

Алгоритмы решения задач могут реализовывать различные методы. При решении задач на ЭВМ широко используются методы эвристики и имитации.

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

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

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

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

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

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

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

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

Наиболее распространенным способом - описание в виде структурных блок-схем.

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

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

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

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

Как только алгоритм описан, наступает этап реализации алгоритма. На этой стадии осуществляется написание кода программы для ЭВМ на одном из искусственных языков.

Для того чтобы сделать разработанный алгоритм «понятным» для выполнения на компьютере, его нужно записать с помощью языка программирования.

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

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

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

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

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

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