Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 348
Текст из файла (страница 348)
Непрерывные переменные имеют бесконечное количество значений, и если распределение вероятностей этих значений не характеризуется наличием пиковых значений в отдельных точках, то вероятность любого отдельно взятого значения равна (). Поэтому определим ск функцию плотности вероятностей, которая также обозначается как Р (х), но имеет немного иной смысл по сравнению с дискретной функцией вероятностей Р(/)) . Функция плотности вероятностей Р(х=с) определяется как отношение вероятности того, что Х попадает в интервал вокруг с, к ширине этого интервала, измеряемая в пределе приближения ширины интервала к нулю: Р(Хгс) = 11м Р(с < Х < с + <(х) /с(х е о Функция плотности должна быть неотрицательной при всех х и соответствовать следующему требованию: Р(Х) Вх = 1 Может быть также определена 'в.
кумулятивная функция плотности вероятностей Р(Х), которая представляет собой вероятность того, что некоторая случайная переменнаяменьшех Р(Х) = .(Х)с)х Следует отметить, что функция плотности вероятностей измеряется в определенных единицах, а дискретная функция вероятностей является безразмерной. Например, если переменная х измеряется в секундах, то плотность измеряется в Гц (т.е. 1/с). Если х — точка в трехмерном пространстве, измеряемом в метрах, то плотность измеряется в 1/м'. Математические основы 1295 Одним из наиболее важных распределений вероятностей является тк гауссово распределение, известное также под названием нормального распределения.
Гауссово распределение со средним Н и среднеквадратичным отклонением о (и поэтому с дисперсией о') определяется следуюшей формулой: ( -Н) l(2о ) Р(х) = е оХ/2я где х — непрерывная переменная, изменяюшаяся в пределах от — до + . Если среднее н=О и дисперсия о'=1, то имеет место частный случай нормального распределения, называемый 'ъ. стандартным нормальным распределением. Если распределение задано на векторе х в пространстве с с) измерениями, то оно представляет собой 'ъ. многомерное гауссово распределение: 1 — — ( (х-н) Х (х-н) ) Р(х) = е (2я)"]Х] где Н вЂ” вектор средних; Š— еь матрица ковариации этого распределения. При наличии одного измерения можно также определить функцию Ж кумулятивного распределения Р(х) как вероятность того, что случайная переменная будет меньше чем х.
Для стандартного нормального распределения эта функция задается следуюшим образом; где етГ(х) — так называемая функция ошибок, не имеюшая представления в замкнутой форме. В 'в. центральной предельной теореме утверждается, что среднее и случайных переменных приближается к нормальному распределению по мере того, как и стремится к бесконечности. Такому свойству подчиняется почти любая коллекция случайных переменных, при том условии, что значение дисперсии любого конечного подмножества переменных не доминирует над значениями дисперсии других конечных подмножеств.
БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ ЗАМЕТКИ Система обозначений О ( ), которая в наши дни широко используется в компьютерных науках, была впервые определена в контексте теории чисел немецким математиком П.Г. Н. Бахманом [57]. Понятие ХР-полноты было предложено Куком [289], а современный метод определения способа сведения одной проблемы к другой предложен Карпом [772]. И Кук, и Карп получили за свою работу премию Тьюринга — высшую награду в компьютерных науках. В число классических работ по анализу и проектированию алгоритмов по праву входят [8] и [809]; более современные достижения отражены в [295] и [1489].
Эти 1296 Приложение А книги в основном посвящены проектированию и анализу алгоритмов решения разрешимых задач. Сведения в области теории ХР-полноты и других форм неразрешимости приведены в книгах Гэри и Джонсона [520], а также Пападимитриу [1168]. В своей книге Гэри и Джонсон не только изложили теоретические основы, но и привели примеры, наглядно показывающие, по каким причинам специалисты в области компьютерных наук считают бесспорным утверждение, что линии водораздела между разрешимыми и неразрешимыми задачами проходит по границе между полиномиальной и экспоненциальной временной сложностью. Кроме того, эти ученые представили объемистый каталог задач, известных как ХР-полные или неразрешимые по каким-то другим критериям. К числу хороших учебников по теории вероятностей относятся [122], [254], [463] и [1310].
Б.1. ОПРЕДЕЛЕНИЕ ЯЗЫКОВ С ПОМОЩЪЮ ФОРМЫ БЭКУСА — НАУРА В настояшей книге определено несколько языков, включая языки пропозициональной логики (с. 1), логики первого порядка (с. 1) и подмножество английского языка (с. 1). Формальный язык определяется как множество строк, в котором каждая строка представляет собой последовательность символов. Все языки, которые были необходимы нам в этой книге, состоят из бесконечного множества строк, поэтому нужен краткий способ, позволяюший охарактеризовать это множество. Дзи этого служит грамматика. Авторы приняли в качестве способа оформления грамматик формальную систему, называемую Ж формой Вакуса — Наура (Вас1газ — Хааг гопп — ВЬЩ. Грамматика ВХР состоит из четырех компонентов, перечисленных ниже. ° Множество Ж терминальных символов.
Это — символы или слова, из которых состоят строки языка. В качестве таких символов могут использоваться буквы (А, В, С, ...) или слова (а, аакйчакуе аЬасзгв, ...). ° Множество 'гк нетерминальных символов, которые обозначают компоненты предложений языка. Например, нетерминальный символ ггоипрьхаве (именное словосочетание) в английском языке обозначает бесконечное множество строк, которое включает "уои" и "гЬе Ь(я з!оЬЬегу г(оя". ° Ж Начальный символ, который представляет собой нетерминальный символ, обозначаюший законченные строки языка.
В описанной выше грамматике 1298 Приложение Б английского языка таковым является символ Бепсепогя в грамматике арифметических выражений может быть задан символ Ехрт ° Множество правил подстановки в форме ьеБ — ьеББ, где ьеБ — нетерминальный символ; кнБ — последовательность, в которую входят от нуля и больше символов (терминальных или нетерминальных). Правило подстановки в приведенной ниже форме означает, что при наличии двух строк, обозначенных как иоипрлхаве (именное словосочетание) и цехьрлеаве (глагольное словосочетание), их можно соединить друг с другом и обозначить результат как Бепсепое'.
Яепеепое -> ГтоипРЛгазе 1ГехЬРЛхаве Несколько правил с одинаковой левой частью могут быть заданы как одно правило с той же левой частью и со всеми правыми частями этих правил, разделенными символом ~ . Ниже приведена грамматика ВХР для простых арифметических выражений. ехрг — > ехри Ореха сох ехрх ~ ( ехрг ) ! ИитЬег ЕитЬех -~ О191 Е ~ ЕитЬег О191 Е р191с -+ 0 ) 1 ! 2 ! 3 ! 4 ! 5 ! 6 ) 7 ! В ! 9 Орехаеог -э +/ †/-:)х Более подробные сведения о языках и грамматиках приведены в главе 22. Следует отметить, что в других книгах в системе обозначений ВХР могут использоваться немного другие правила, например, нетерминальные символы обозначаются как (Оуд1с) вместо Ойд11, терминальные символы — 'ыотс1', а не згокст, а в правилах используются символ:: = вместо — >.
Б.2. ОПИСАНИЕ АЛГОРИТМОВ С ПОМОЩЬЮ ПСЕВДОКОДА В настоящей книге подробно определено свыше 80 алгоритмов. Авторы решили не останавливаться на каком-то одном языке программирования (и рисковать тем, что читатели, не знакомые с этим языком, не смогут воспользоваться приведенными здесь алгоритмами) и вместо этого представить алгоритмы на псевдокоде. Основные конструкции этого псевдокода должны быть знакомы пользователям таких языков, как )ача, С++ и Ьйзр. В некоторых местах для описания вычислений используются математические формулы или текст на естественном языке, поскольку в противном случае пришлось бы применять более громоздкие конструкции.
Необходимо также отметить, что в алгоритмах используются приведенные ниже соглашения. ° Статические переменные. Ключевое слово всасйс используется для указания на то, что переменной присваивается начальное значение при первом вызове некоторой функции, после чего это значение (или значение, присвоенное переменной с помощью выполненных в дальнейшем операторов присваивания) сохраняется при всех последующих вызовах функции. Таким образом, статические переменные напоминают глобальные переменные в том, что они сохраняют свое значение после каждого вызова содержащей их функции, но остаются доступными только в этой функции.
В программах агентов, приведенных в данной книге, статические переменные используются в качестве Об)цие сведения о языках и алгоритмах, используемых в книге 1299 "оперативной памяти". Программы со статическими переменными могут быть реализованы в объектно-ориентированных языках, таких как )ауа и Бгпа!1)айг, в виде "объектов". В функциональных языках они могут быть реализованы с помощью функциональных замыканий в той среде, в которой определены требуемые переменные.
° Функции как значения. Имена функций и процедур начинаются с прописных букв, а имена переменных состоят из строчных букв и выделяются курсивом. Поэтому чаще всего вызов функции выглядит наподобие вп)х) . Однако допускается, чтобы значением переменной была функция; например, если значением переменной Г является функция вычисления квадратного корня, то выражение Г19) возвращает 3.
° Начальный индекс массива, равный 1. Если не указано иное, то первым индексом массива является 1, как в обычной системе математических обозначений, а не о, как в языках )ача и С. ° Значимость отступов. По аналогии с языком Ругйоп и в отличие от языков )ача и С++ (в которых используются фигурные скобки) или языков Рааса! и т)аца! Ваз)с (в которых используется оператор епс)) для обозначения области действия цикла или условного выражения применяются отступы. Б.З.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
