КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Способы записи алгоритма программы
Алгоритм.Алгоритм - это точная последовательность предписаний, исполнение которых позволяет посредством конечного числа шагов получить решение задачи, однозначно определяемое исходными данными Свойства алгоритма. При составлении и записи алгоритма необходимо обеспечить, чтобы он обладал рядом свойств. Однозначность алгоритма, под которой понимается единственность толкования исполнителем правила построения действий и порядок их выполнения. Чтобы алгоритм обладал этим свойством, он должен быть записан командами из системы команд исполнителя. Конечность алгоритма – обязательность завершения каждого из действий, составляющих алгоритм, и завершимость выполнения алгоритма в целом. Результативность алгоритма, предполагающая, что выполнение алгоритма должно завершиться получением определённых результатов. Массовость, т. е. возможность применения данного алгоритма для решения целого класса задач, отвечающих общей постановке задачи. Для того чтобы алгоритм обладал свойством массовости, следует составлять алгоритм, используя обозначения величин и избегая конкретных значений. Правильность алгоритма, под которой понимается способность алгоритма давать правильные результаты решения поставленных задач. Эффективность – для решения задачи должны использоваться ограниченные ресурсы компьютера (процессорное время, объём оперативной памяти и т. д.).Способы записи алгоритмов:На практике наиболее распространены следующие способы представления алгоритмов:Словесно-формульный способ (запись на естественном языке); Словесно-формульный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке.Например. Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел (алгоритм Эвклида).Алгоритм может быть следующим: 1. задать два числа; 2. если числа равны, то взять любое из них в качестве ответа и остановиться, в противном случае продолжить выполнение алгоритма; 3. определить большее из чисел; 4. заменить большее из чисел разностью большего и меньшего из чисел; 5. повторить алгоритм с шага 2.Словесный способ не имеет широкого распространения, так как такие описания: V строго не формализуемы; V страдают многословностью записей; V допускают неоднозначность толкования отдельных предписаний.Графический способ (с использованием графических примитивов, блок-схем); Для разработки структуры программы удобнее пользоваться записью алгоритма в виде блок-схемы (в англоязычной литературе используется термин flow-chart). Для изображения основных алгоритмических структур и блоков на блок-схемах используют специальные графические символы. Они приведены на рисунке: Начало/конец алгоритма Блок вычислений Начало (заголовок) цикла Проверка условий Ввод/Вывод данных Псевдокоды(полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.); Псевдокод представляет собой систему обозначений и правил, предназначенную для единообразной записи алгоритмов. Псевдокод занимает промежуточное место между естественным и формальным языками. С одной стороны, он близок к обычному естественному языку, поэтому алгоритмы могут на нем записываться и читаться как обычный текст. С другой строны, в псевдокоде используются некоторые формальные конструкции и математическая символика, что приближает запись алгоритма к общепринятой математической записи. В псевдокоде не приняты строгие синтаксические правила для записи команд, присущие формальным языкам, что облегчает запись алгоритма на стадии его проектирования и дает возможность использовать более широкий набор команд, рассчитанный на абстрактного исполнителя. Однако в псевдокоде обычно имеются некоторые конструкции, присущие формальным языкам, что облегчает переход от записи на псевдокоде к записи алгоритма на формальном языке. В частности, в псевдокоде, так же, как и в формальных языках, есть служебные слова, смысл которых определен раз и навсегда. Они выделяются в печатном тексте жирным шрифтом, а в рукописном тексте подчеркиваются. Единого или формального определения псевдокода не существует, поэтому возможны различные псевдокоды, отличающиеся набором служебных слов и основных (базовых) конструкций. Примером псевдокода является школьный алгоритмический язык в русской нотации (школьный АЯ), описанный в учебнике А.Г. Кушниренко и др. "Основы информатики и вычислительной техники", 1991. Этот язык в дальнейшем мы будем называть просто "алгоритмический язык". Пример записи алгоритма на школьном АЯ: алг Сумма квадратов (арг цел n, рез цел S) дано | n > 0 надо | S = 1*1 + 2*2 + 3*3 + ... + n*n нач цел i ввод n; S:=0 нц для i от 1 до n S:=S+i*i кц вывод "S = ", S кон Формальные языки (QBasic, Pascal и тд.). Пример:'Вывод выражений с помощью оператора PRINTPRINT "Вывод чисел:"PRINT 23.4PRINT-10.2PRINTPRINTPRINT "Вычислим (10+4) - 4*(2-3'^2)"PRINT (10 + 4)-4* (2-3^2)PRINTPRINT "В заключение объединим отдельные"PRINTPRINT "слова в текст:"PRINT "Сегодня" + " " + "хорошая" + " погода"'Конец программы Основные алгоритмические конструкции: Линейный алгоритм. В алгоритмическом языке лин ейным является алгоритм, состоящий из команд, выполняющихся одна за другой. Они в записи алгоритма располагаются в том порядке, в каком должны быть выполнены предписываемые ими действия. Такой порядок выполнения называется естественным. Последовательность команд образует составную команду «цепочка», которая в записи блок-схемой имеет вид, приведенный на рисунке 1. В математике к линейным алгоритмам относятся алгоритмы, представленные формулами. Они наиболее просты для программирования. Заметим, что естественный способ кодировки формул делает программу легкочитаемой, но нередко приводит к лишним вычислениям, поэтому, чтобы избежать повторных вычислений и сократить общее количество операций выполняйте тождественные преобразования выражений. С другой стороны, надо знать, что не всегда следует осуществлять оптимизацию, поскольку она является не правилом, а исключением. Этому есть три причины, главная из которых состоит в том, что оптимизация ухудшает наглядность программ, вторая - выгоды от оптимизации должны быть существенными и третья - современные системы, как правило, имеют удовлетворительные оптимизирующие компиляторы. Основные алгоритмические конструкции: Ветвящийся алгоритм. При исполнении алгоритмов приходится не только находить значения величин, но и анализировать их свойства, сравнивать их друг с другом и в зависимости от результата сравнения выбирать ту или иную ветвь алгоритма. Алгоритмы, имеющие несколько ветвей, называются нелинейными. К таким относятся разветвляющиеся и циклические алгоритмы. Для их записи применяются составные команды. Базовая структура "ветвление". Определяет выполнение действий в зависимости от выполнения условия. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путьбудет выбран.|Язык QBasic |Язык блок-схем ||Неполное |[pic] ||IF Условие THEN действия | ||Полное |[pic] ||IF Условие THEN действия 1 | ||ELSE действия 2 | | Пример алгоритма ветвления на алгоритмическом языке QBasic: INPUT «1 или 2?»IF=1 OR I=2 THENPRINT “Ок”ELSEPRINT “Вне диапазона”END IF Основные алгоритмические конструкции: Циклический алгоритм. Повторяющееся выполнение действий (групп действий),зависящее от выполнения условия, называется циклом. Любой цикл состоит из трех частей: начала, проверки и тела цикла. Начало – всегда первая часть цикла. Главная его функция – подготовить цикл.Проверка определяет момент выхода из цикла. Базовая структура "цикл". Обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла. Основные разновидности циклов представлены в таблице:|Язык QBasic |Язык блок-схем ||Цикл типа пока. ||Do Until условие |[pic] ||тело цикла (последовательность действий) | ||Loop | ||Do While условие |[pic] ||тело цикла (последовательность действий) | ||Loop | ||Цикл типа для. ||For i=i1 to i2 |[pic] ||тело цикла (последовательность действий) | ||Next i | | Пример алгоритма цикл на алгоритмическом языке QBasic: FOR I=1 TO 15PRINT INEXT I FOR I=7 TO –6 STEP –3PRINT INEXT I I=0PRINT «Значение I в начале равно»; IDO WHILE I<10I=I+1LOOPPRINT “Значение I в конце цикла равно”; I Выводы: Чем отличается программный способ записи алгоритмов от других? При записи алгоритма в словесной форме, в виде блок-схемы или на псевдокоде допускается определенный произвол при изображении команд. Вместе с тем такая запись точна настолько, что позволяет человеку понять суть дела и исполнить алгоритм. Однако на практике в качестве исполнителей алгоритмов используются специальные автоматы — компьютеры. Поэтому алгоритм, предназначенный для исполнения на компьютере, должен быть записан на понятном ему языке. И здесь на первый план выдвигается необходимость точной записи команд, не оставляющей места для произвольного толкования их исполнителем. Следовательно, язык для записи алгоритмов должен быть формализован. Такой язык принято называть языком программирования. Что такое уровень языка программирования? В настоящее время в мире существует несколько сотен реально используемых языков программирования. Для каждого есть своя область применения. Любой алгоритм, как мы знаем, есть последовательность предписаний, выполнив которые можно за конечное число шагов перейти от исходных данных к результату. В зависимости от степени детализации предписаний обычно определяется уровень языка программирования — чем меньше детализация, темвыше уровень языка. По этому критерию можно выделить следующие уровни языков программирования: машинные;машинно-оpиентиpованные (ассемблеpы);машинно-независимые (языки высокого уровня). Машинные языки и машинно-ориентированные языки — это языки низкого уровня, требующие указания мелких деталей процесса обработки данных. Языки же высокого уровня имитируют естественные языки, используя некоторые слова разговорного языка и общепринятые математические символы. Эти языки более удобны для человека. Языки высокого уровня делятся на:процедурные (алгоритмические) (Basic, Pascal, C и др.), которыепредназначены для однозначного описания алгоритмов; для решения задачипроцедурные языки требуют в той или иной форме явно записать процедуру еерешения;логические (Prolog, Lisp и др.), которые ориентированы не на разработкуалгоритма решения задачи, а на систематическое и формализованное описаниезадачи с тем, чтобы решение следовало из составленного описания;объектно-ориентированные (Object Pascal, C++, Java и др.), в основе которыхлежит понятие объекта, сочетающего в себе данные и действия над нами.Программа на объектно-ориентированном языке, решая некоторую задачу, по сути описывает часть мира, относящуюся к этой задаче. Описание действительности в форме системы взаимодействующих объектов естественнее, чем в форме взаимодействующих процедур. В чем преимущества алгоритмических языков перед машинными? Основные преимущества таковы:алфавит алгоритмического языка значительно шире алфавита машинного языка, что существенно повы шает наглядность текста программы;набор операций, допустимых для использования, не зависит от набора машинных операций, а выбирается из соображений удобства формулирования алгоритмов решения задач определенного класса;формат предложений достаточно гибок и удобен для использования, что позволяет с помощью одного пред ложения задать достаточно содержательный этап обра ботки данных;требуемые операции задаются с помощью общепринятых математических обозначений;данным в алгоритмических языках присваиваются индивидуальные имена, выбираемые программистом;в языке может быть предусмотрен значительно более широкий набор типов данных по сравнению с набором машинных типов данных. Таким образом, алгоритмические языки в значительной мере являются машинно- независимыми. Они облегчают работу программиста и повышают надежность создаваемых программ. Какие компоненты образуют алгоритмический язык? Алгоритмический язык (как и любой другой язык) образуют три егосоставляющие: Алфавит — это фиксированный для данного языка набор основных символов, т.е. "букв алфавита", из которых должен состоять любой текст на этом языке — никакие другие символы в тексте не допускаются. Синтаксис — это правила построения фраз, позволяющие определить, правильно или неправильно написана та или иная фраза. Точнее говоря, синтаксис языка представляет собой набор правил, устанавливающих, какие комбинации символов являются осмысленными предложениями на этом языке. Семантика определяет смысловое значение предложений языка. Являясь системой правил истолкования отдельных языковых конструкций, семантика устанавливает, какие последовательности действий описываются теми или иными фразами языка и, в конечном итоге, какой алгоритм определен данным текстом на алгоритмическом языке.
2. -Экспертные системы: классификация и структура
Системы, основанные на знаниях – это системы программного обеспечения, основными структурными элементами которых являются база знаний и механизм логических выводов. В первую очередь к ним относятся экспертные системы, способные диагностировать заболевания, оценивать потенциальные месторождения полезных ископаемых, осуществлять обработку естественного языка, распознавание речи и изображений и т.д. Экспертные системы являются первым шагом в практической реализации исследований в области ИИ. В настоящее время они уже используются в промышленности.
Экспертная система – это вычислительная система, в которую включены знания специалистов о некоторой конкретной проблемной области и которая в пределах этой области способна принимать экспертные решения.
Наверное, в настоящее время нет человека, занимающегося или просто интересующегося информатикой, которому не было бы знакомо это словосочетание. Экспертные системы (ЭС) составляют часть систем искусственного интеллекта (ИИ), причем самую существенную их часть. Экспертные системы обычно определяют как программы ЭВМ, моделирующие действия эксперта-человека при решении задач в узкой предметной области, на основе накопленных знаний, составляющих базу знаний (БЗ).
По функциональному назначению ЭС можно разделить на следующие типы. Во-первых, это мощные ЭС, рассчитанные на узкий круг пользователей (например, ЭС, предназначенные для управления технологическими процессами, или некоторые ЭС военного применения). Такие системы работают в реальном масштабе времени и являются довольно дорогими. Во-вторых, это мощные ЭС, рассчитанные на широкий круг пользователей. К ним можно отнести системы медицинской диагностики. Также существуют и более простые ЭС, содержащие небольшое число правил (в виде которых чаще всего представляются знания в базе знаний) и, соответственно недорогие. Это системы, рассчитанные на массового потребителя. И наконец, есть довольно простые ЭС, предназначенные для индивидуального пользования. Это может быть даже “самодельная” система, применяемая изготовителем в повседневной жизни.
Общее представление о функционировании экспертной системы дает рис. 1.
Рис. 1.
Все экспертные системы включают в себя по крайней мере три основных элемента: базу знаний (БЗ), машину вывода (МВ), интерфейс пользователя (ИП).
БАЗА ЗНАНИЙ (БЗ) создается людьми - консультантами, исследователями либо самими экспертами. Она содержит информацию о том, что известно о данном предмете в настоящий момент. Эта информация выражена в виде объектов, атрибутов и условий. Помимо описательных представлений о действительности, она включает выражение неопределенности - ограничения на достоверность факта.
БЗ отличается от традиционной базы данных из-за своего символьного, а не числового или буквенного содержания. При обработке информации базы данных пользуются заранее определенными логическими правилами.
В БЗ поступают факты. Связь между фактами представлена эвристическими правилами.
МАШИНА ВЫВОДА (МВ) обеспечивает функционирование механизма, осуществляющего поиск в базе знаний по правилам рациональной логики для получения решений. Эта МВ приводится в действие при получении запроса пользователя и выполняет следующие задачи:
¨ сравнивает информацию, содержащуюся в запросе пользователя, с информацией базы знаний;
¨ ищет определенные цели или причинные связи;
¨ оценивает относительную определенность фактов, основываясь на соответствующих коэффициентах доверия. связанных с каждым фактом.
МВ предназначена для построения заключений. Ее действие аналогично рассуждениям эксперта-человека, который оценивает проблему и предлагает гипотетические решения. В поиске целей на основе предложенных правил, МВ обращается к БЗ до тех пор, пока не найдет вероятный путь к получению приемлемого результата.
МВ применяет логику, четкие рассуждения, установленные правилами, для проверки заключений и получения выводов.
ИНТЕРФЕЙС ПОЛЬЗОВАТЕЛЯ (ИП) способствует взаимодействию между системой и пользователем, т. е. организует обмен информацией между оператором и МВ. Интерфейс с использованием естественного языка создает видимость повседневной беседы, применяя правильно построенные фразы и предложения. Системы, предоставляющие пользователю максимум удобств, расходуют больше ресурсов основной машины. ИП часто служит определяющей мерой достоинств ЭС, когда простота общения играет не меньшую роль, чем эффективность МВ или полнота БЗ.
Через ИП система проводит свое исследование и поддерживает связь с человеком, который ею управляет.
Правила (эвристические правила) определяют прямую или обратную причинно-следственную связь между объектами и значениями БЗ. Каждое правило выглядит следующим образом:
правилоN: если
ПРЕДПОСЫЛКА
то
ЗАКЛЮЧЕНИЕ.
Это предложение начинается с номера правила N, за которым следует двоеточие. Предпосылки и заключения составляют пары ОБЪЕКТ=ЗНАЧЕНИЕ. Заключение может, кроме того, иметь связанный с ним коэффициент доверия в виде ОБЪЕКТ=ЗНАЧЕНИЕ,кд=M
КОЭФФИЦИЕНТ ДОВЕРИЯ (или СТЕПЕНЬ УВЕРЕННОСТИ). Степень определенности утверждений не всегда абсолютна, т.е. в большинстве утверждений уровень доверия может быть более или менее условным.
Следовательно, количественные коэффициенты определенности увеличивают точность рассуждения ЭС. Такие выражения относительной уверенности часто основываются на статистических, вероятностных или просто субъективных предпосылках. Общепринятая схема состоит в том, чтобы варьировать уровень доверия от 0, представляющего минимальную степень уверенности, до 100 - высшей степени.
ИСПОЛЬЗОВАНИЕ ЭКСПЕРТНЫХ СИСТЕМ.
Для того, чтобы задействовать нашу ЭС, нам необходимо создать осмысленную БЗ для конкретной предметной области. Любой эксперимент начинается с анализа целей проекта. Разработчикам необходимо знать природу проблем, которые им предстоит решать. Они должны иметь возможность описать задачу, последствия или результаты, ожидаемые от ее решения. Поставив правильные цели, планировщики получат полезные решения.
Цели системы можно разделить на три типа: конечные, промежуточные и вспомогательные. Каждая цель - это предполагаемый результат, который может быть получен, если программа предлагает решение специфических проблем. Установление их в качестве отправных точек нужно для того, чтобы дать разработчикам ясное представление, какие задания должна выполнять ЭС и как она должна действовать при их выполнении.
Если цели определены, то типы проблем, которые предстоит решать, становятся более очевидными. На данном этапе возникает потребность в ограничениях. Хотя БЗ должна быть исчерпывающей, но тем не менее ее следует ограничивать по фактам и правилам, требующимся для достижения поставленных целей. Например, возраст и вес больного с заболеваниями внутренних органов важны для постановки правильного диагноза, а цвет его глаз или волос - нет.
Вторая фаза включает в себя сбор, структуризацию и перевод основного материала, необходимого для решения поставленной задачи (для достижения конечной цели). В этом процессе обычно участвуют специалисты в предметной области - эксперты. Небольшие БЗ часто извлекаются из справочников или учебных пособий. Экспертные системы, создаваемые на персональных компьютерах, чаще всего ограничиваются небольшим кругом проблем, и базу знаний можно накопить самостоятельно. Содержание такой базы знаний обуславливается определением проблем. Это значит, что база знаний может охватывать любую предметную область, которая описывается набором правил “если - то”.
КОНЕЧНАЯ ЦЕЛЬ описывает, какое действие, исход или результат должны получать пользователи вследствие консультации, когда система решит проблему. Цель должна выражать действие или событие, отображающее воздействие ЭС на общий ход событий. На этом уровне описаний степень уверенности должна быть достаточно большой.
ПРОМЕЖУТОЧНЫЕ ЦЕЛИ системы подразделяют общую проблему на подзадачи, описывая проблемы, которые должны быть решены для достижения конечной цели.
Вспомогательные цели помогают планировщикам определить конкретные области экспертизы, необходимые для решения поставленной задачи. Каждая вспомогательная цель предполагает содержание в БЗ ряда связанных задач.
Существует два метода достижения цели системы: метод прямых цепочек и метод обратных цепочек.
В процессе работы при запуске того или иного правили его левая часть загружается в рабочую память (аналог интерфейса пользователя).
МЕТОД ПРЯМЫХ ЦЕПОЧЕК состоит в следующем: проверяется наличие левых частей правил в рабочей памяти (РП); готовыми к исполнению являются те правила, левые части которых хранятся в РП. Если таких правил несколько, то возникает конфликтная ситуация, для исключения которых применяются специальные методы. Такой процесс вывода продолжается до исчерпания правил, готовых к исполнению, или до выполнения правила остановки. Можно сказать, что метод прямых цепочек основан на выводе, исходя из фактов.
МЕТОД ОБРАТНЫХ ЦЕПОЧЕК строит вывод с конца, т.е. с цели, подлежащей доказательству: от цели переходят к подцели и т.д.
Дата добавления: 2015-04-21; просмотров: 160; Мы поможем в написании вашей работы!; Нарушение авторских прав |