Программа-минимум кандидатского экзамена по специальности 05.13.17 «Теоретические основы информатики» (стр. 23 из 29)
Как принцип байесовский подход выглядит прекрасно, но есть и несколько проблем, связанных с его применением.
Первое замечание касается возможности вычисления величины Р(Е). Эту величину легко определить, если есть возможность вычислить Р(Е:неН), а это не всегда можно сделать.
Одна из возможностей обойти это затруднение состоит в переходе к полной группе событий, однако это не спасает положение, если состав полной группы событий неизвестен. Можно пользоваться и грубыми оценками, если сохраняется точность диагноза. Кроме того, если Р(Н) уточняется в ходе работы, то Р(Е) можно тоже уточнять.
Второе замечание касается используемого в этом подходе предположения о независимости свидетельств. С теоретической точки зрения это замечание очень серьезно, но поскольку в конце процесса диагноза нас интересуют не столько точные значения вероятностей (это больше беспокоит статистиков), сколько соотношения вероятностей, то при одинаковом порядке ошибочности оценок вероятностей гипотез для практики более важной оказывается правильность общей картины, создаваемой экспертной системой.
Наиболее развитой и успешной оказалась схема, реализованная Шортлиффом в MYCIN, представляющая собой основанную на здравом смысле модификацию байесовского метода, позволяющую достаточно просто решить поставленные во вступлении к данному разделу четыре основных вопроса:
а) как количественно выразить достоверность, надежность посылок?
б) как выразить степень поддержки заключения конкретной посылкой?
в) как учесть совместное влияние нескольких посылок на заключение?
г) как строить цепочки умозаключений в условиях неопределенности?
Коэффициенты уверенности для правила с одной посылкой. В данном случае речь идет о вычислении коэффициентов уверенности для правил вида:
Е→С ("если Е то С").
Если иметь возможность присваивать коэффициент уверенности как посылке, так и импликации, то их можно использовать для оценки степени определенности заключения, выводимого по данному правилу. Шортлифф применяет в данном случае коэффициенты уверенности подобно вероятностям: коэффициент уверенности ct(E) в посылке подобен p(E); коэффициент уверенности сt(Е→С) в импликации подобен p(C:E). Для определения коэффициента уверенности в заключении Шортлифф использует схему:
ct(посылки)∙ct(импликации)=ct(заключения).
Логические комбинации посылок в одном правиле. Посылкой в правиле считается все, что находится между если и то. В MYCIN избран принцип: делать все правила простыми. Тогда простейшими логическими комбинациями посылок являются их конъюнкия или дизъюнкция, т.е. правила вида:
(Е1&Е2)→С или (Е1v Е2)→С.
Коэффициент уверенности конъюнкции посылок в MYCIN принято оценивать по наименее надежному свидетельству:
ct(Е1&Е2) = min {ct(Е1), ct(E2)}.
Соответственно, коэффициент уверенности дизъюнкции посылок в MYCIN принято оценивать по наиболее надежному свидетельству:
ct(Е1v Е2) = max {ct(Е1), ct(E2)}.
Впрочем, дизъюнкции стараются разбивать на отдельные правила, т.е. вместо правила (Е1v Е2)→С создается пара правил: Е1→С и Е2→С, так как это позволяет лучше видеть роль каждой посылки в формировании заключения. Но, если эксперт полагает, что дизъюнкция, как она описана выше, лучше отражает суть дела, то возможно использование правила с логической комбинацией посылок в форме дизъюнкции.
Поддержка одного заключения множеством правил. В этой ситуации тоже могут быть предложены различные способы учета совместного влияния свидетельств на заключение. В MYCIN применена схема, подобная схеме вычисления суммарной вероятности нескольких независимых событий.
Пусть имеются правила Е1→С и Е2→С, первое из которых обеспечивает поддержку заключения С с уверенностью ct1, а второе - с уверенностью ct2. По логике вещей, если обе посылки Е1 и Е2 верны, эти два правила совместно должны обеспечивать заключению С большую поддержку, чем каждое из них в отдельности. В MYCIN это достигается вычислением степени совместной поддержки по следующей формуле:
ct = ct1 + ct2 - ct1
ct2 .
При наличии более двух правил, поддерживающих одно и то же заключение, их совместное влияние может быть учтено последовательным применением этой схемы для объединения суммарной поддержки уже учтенных правил с поддержкой очередного, еще не учтенного правила.
Использованная Шортлиффом схема объединения поддержки одного заключения множеством правил позволяет учитывать коэффициенты уверенности поддерживающих правил в произвольном порядке и объединять их по мере поступления свидетельств.
Вместе с тем, важно помнить, что эти принципы учета коэффициентов уверенности исходят из предположения о независимости свидетельств, а также о том, что правомерность такого способа комбинирования не имеет иного обоснования, кроме того, что он прост, соответствует здравому смыслу и общему правильному поведению людей, если не относиться к нему излишне доверчиво.
Биполярные схемы для коэффициентов уверенности. Коэффициенты уверенности, примененные в MYCIN, представляют собой грубое подобие вероятностей. В усовершенствованной системе EMYCIN для выражения степени определенности использован интервал [-1, +1] в следующем смысле:
+1 - полное доверие посылке или заключению;
0 - отсутствие знаний о посылке или заключении;
-1 - полное недоверие посылке или заключению.
Промежуточные значения выражают степень доверия или недоверия к ситуации. Все описанные для однополярных коэффициентов процедуры здесь тоже имеют место, но при вычислении max и min учитываются знаки при величинах коэффициентов (например, что +0, 1 > - 0, 2). Биполярность коэффициентов повлияла и на вид используемых формул.
Так для вычисления коэффициента уверенности отрицания посылки достаточно лишь поменять знак коэффициента, т.е. ct(неЕ) = - ct(E).
Процедура расчета степени поддержки заключения несколькими правилами тоже претерпела соответствующие изменения:
а) если оба коэффициента положительны, то
ct = ct1 + ct2 - ct1
ct2 ;
б) если оба коэффициента отрицательны, то
ct = ct1 + ct2 + ct1
ct2 ;
в) если один из коэффициентов положителен, а другой отрицателен, то
,при этом, если один из коэффициентов равен +1, а другой - 1, то ct=0.
Работа с биполярными коэффициентами может привести к нереальным результатам, если правила сформулированы неточно. В частности, ошибка возникает, если не учитывается, что правила бывают обратимыми (применимыми при любых значениях коэффициентов уверенности в посылке) и необратимыми (применимыми лишь при положительных значениях коэффициента уверенности в посылке).
Многоступенчатые рассуждения и сети вывода. До сих пор речь шла о ситуациях, когда заключение отделялось от посылки одним шагом рассуждений. Более типична ситуация, когда вывод от посылок отделен рядом промежуточных шагов рассуждений.
Принцип последовательного учета свидетельств работает успешно в том случае, когда применима так называемая монотонная логика. Но часто встречаются ситуации, когда она не имеет места. Это те случаи, когда какое-либо очередное свидетельство опровергает выводы, сделанные на основе предшествующих свидетельств. Для таких ситуаций разрабатываются специальные типы логик. Другого типа трудность возникает вследствие "незамкнутости мира": птицы летают, но не все; можно перечислить все предметы в комнате, но нельзя перечислить то, что вне ее. В таких случаях принимается "гипотеза закрытого мира": все, что вне его, то - ложь.
Реляционная алгебра и исчисление
http://www.citforum.ru/database/osbd/contents.shtml
Основы современных баз данных (про реляционное исчисление)
5. Программные средства информатики и информационных технологий
Краткий ответ на вопросы раздела:
Классы программных средств
Операционные системы
Иснструментальное ПО
Прикладное ПО
| Операционная система набор программно-аппаратных средств, обеспечивающих управление компьютером. |
Классификация ОС
По назначению
Общего пользования / Специальные (например, для управления спутником)
По количеству пользователей
Однопользовательские (MS DOS) / Многопользовательские (Windows, UNIX)
По сетевой функциональности
Локальные / Сетевые
По управлению задачами
Пакетные (перед началом работы – список задач на выполнение, вмешиваться в работу системы нельзя, пример – ввод с перфокарт) / С разделением времени (несколько задач, работающих одновременно, пример – Windows, UNIX) / ОС реального времени (особый приоритет отдается задачам, критичным по времени, пример – ОС спутников, фотоаппаратов)
Состав ОС
Загрузчик ОС
Ядро ОС
Планировщик процессов
Подсистема ввода/вывода
Драйверы ОС
Специальные программы, предназначенные для управления внешними устройствами.
Являются частью подсистемы ввода/вывода ОС.
Резидентные программы
В ОС MSDOS программа, вернувшая управление ОС, но оставшееся в оперативной памяти компьютера.
Основные функции ОС
Управление памятью
Организация доступа к внешним устройствам
Управление задачами
Организация сетевого взаимодействия
Разграничение прав доступа
Организация интерфейса к пользователю
управление вводом-выводом
управление файловой системой
управление взаимодействием процессов
диспетчеризация процессов
защита и учет использования ресурсов
обработка командного языка
Утилиты ОС
Программы, входящие в поставку ОС, предназначенные для предоставления функций ОС пользователю.
Основные объекты ОС
Процесс