Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 346
Текст из файла (страница 346)
Кроме того, технологические возможности, открывающиеся на этом уровне, могут быть также применены для создания автономного оружия, появление которого многие считают нежелательным. Наконец, кажется вполне вероятным, что крупномасштабный успех в создании искусственного интеллекта (появление интеллекта на уровне человека и превосходящего его) повлияет на сугцествование большинства представителей рода человеческого. Изменится сам характер нашей работы и развлечений, так же как и наши представления об интеллекте, сознании и будущей судьбе человечества. На этом уровне системы искусственного интеллекта могут создать более непосредственную угрозу самоопределению, свободе и даже выживанию людей. По этим причинам нельзя рассматривать исследования в области искусственного интеллекта в отрыве от их этических последствий.
Каким мы видим будущее? Авторы научно-фантастических романов, повидимому, чаше публикуют пессимистические, а не оптимистические сценарии грядущего, возможно, потому, что это позволяет сочинять более увлекательные сюжеты. Но создается впечатление, что искусственный интеллект пока развивается по такому же принципу, как и другие революционные технологии !типографское дело, инженерное оборудование, воздухоплавание, телефония и т.д.), отрицательные последствия внедрения которых перевешиваются положительными результатами. Глава 27. Настоящее и будущее искусственного интеллекта 1287 В заключение следует отметить, что за свою короткую историю искусственный интеллект добился существенного прогресса, но последнее утверждение из эссе Алана Тьюринга Сотригтд Майтегу ал з' 7пге~(18епсе продолжает оставаться неоспоримым и в наши дни.
Мы способны заглянуть вперед лишь на очень короткое расстояние, но все равно можем увидеть, как много еше предстоит сделать. А.1. АнАлиз сложности и системА оьознлчений 00 Специалистам в области компьютерных наук часто приходится решать задачу сравнения алгоритмов для определения того, насколько быстро они действуют или сколько памяти для них требуется. Для решения этой задачи предусмотрены два подхода. Первым из них является 'а. применение эталонных тестов — прогон реализующих алгоритмы программ на компьютере и измерение быстродействия в секундах и потребления памяти в байтах. Верно, что в конечном итоге нас действительно интересуют именно такие практические характеристики, но эталонное тестирование может оказаться неприемлемым потому, что оно слишком узко направлено, — в нем измеряется производительность конкретной программы, написанной на конкретном языке, функционируюшей на конкретном компьютере с конкретным компилятором и с конкретными входными данными.
К тому же на основании единственного результата, полученного с помо)цью эталонного тестирования, трудно предсказать, насколько успешно этот алгоритм будет действовать в случае использования другого компилятора, компьютера или набора данных. Асимптотический анализ Второй подход опирается на математический 'ж анализ алгоритмов, независимый от конкретной реализации и входных данных. Рассмотрим этот подход на приведенном ниже примере программы, которая вычисляет сумму последовательности чисел (листинг А. )). Листинг А.1. Программа вычисления суммы последовательности чисел аппоеаоп Яшмаасгоп(ледиепсе) теептпн сумма яим еим ь — О аот 1 < — 1 ео Ьепдс)т)яедиепсе) яша < — лип + лециепсе!1] теептп ешп Математические основы 1289 Первый этап анализа состоит в том, что создается определенное абстрактное представление входных данных, позволяющее найти какой-то параметр (или параметры), который характеризует объем входных данных.
В рассматриваемом примере объем входных данных можно охарактеризовать с помощью такого параметра, как длина последовательности, которая будет обозначаться как л. На втором этапе необходимо определить абстрактное представление реализации и найти какой-то критерий, отражающий продолжительность прогона алгоритма, но не привязанный к конкретному компилятору или компьютеру. Применительно к программе Яижпас1ол этим критерием может служить количество строк выполняемого кода; кроме того, данный критерий может быть более детализированным и измеряющим количество сложений, присваиваний, обращений к элементам массивов, а также ветвлений, выполняемых в этом алгоритме.
В любом случае будет получена характеристика общего количества шагов, выполняемых алгоритмом, как функция от объема входных данных. Обозначим эту характеристику как т(л) . Если за основу берется количество строк кода, то в данном примере т(л) =2п+2. Если бы все программы были такими же простыми, как Бивхвас1ол, то область анализа алгоритмов не заслуживала бы названия научной. Но исследования в этой области существенно усложняются из-за наличия двух проблем.
Первая проблема заключается в том, что редко удается найти параметр, подобный Т(л), который полностью характеризует количество шагов, выполняемых в алгоритме. Вместо этого обычно можно самое большее вычислить этот показатель для наихудшего случая т„„„(л) или для среднего случая т,„,(п) . А для вычисления среднего требуется, чтобы аналитик принял какие-то обоснованные предположения по распределению наборов входных данных. Вторая проблема состоит в том, что алгоритмы обычно не поддаются точному анализу.
В этом случае приходится прибегать к аппроксимации и использовать, например, такую формулировку, что быстродействие алгоритма Яцлввасуол характеризуется величиной о(л) . Это означает, что быстродействие алгоритма измеряется величиной, пропорциональной и, возможно, за исключением нескольких небольших значений л. Более формально это определение можно представить с помощью следующей формулы: т(п) равие О(Г(л) ), если т(л) < хЕ(п) лля иекстерсгс )г, лри всех л > ло Перейдя к использованию системы обозначений 0( ), мы получаем возможность воспользоваться так называемым ',ж асимптотическим анализом.
А в рамках этого подхода можно, например, безоговорочно утверждать, что если л асимптотически приближается к бесконечности, то алгоритм, характеризующийся показателем 0(л), проявляет себя лучше по сравнению с алгоритмом 0(л'), тогда как единственное число, полученное с помощью эталонного тестирования, не может служить обоснованием подобного утверждения. Система обозначений О( ) позволяет создать абстрактное представление, в котором не учитываются постоянные коэффициенты, благодаря чему она становится более простой в использовании, но менее точной, чем система обозначений г( ) .
Например, в конечном итоге алгоритм 0(п') всегда будет считаться худшим по сравнению с алгоритмом О(л), но если бы эти два алгоритма характеризовались значениями Т(п'+1) и Т(100л+1000), то фактически алгоритм 0(л') был бы лучше при л<110. 1290 Приложение А Несмотря на этот недостаток, асимптотический анализ представляет собой инструментальное средство, наиболее широко используемое для анализа алгоритмов. Этот метод можно считать достаточно точным, поскольку в процессе анализа создается абстрактное представление и для точного количества операций (поскольку игнорируется постоянный коэффициент )с), и для точного содержимого входных данных (поскольку рассматривается исключительно их объем п); благодаря этому анализ становится осуществимым с помощью математических методов.
Система обозначений 0 ( ) представляет собой хороший компромисс между точностью и простотой анализа. Изначально сложные и недетерминированные полиномиальные задачи С помощью анализа алгоритмов и системы обозначений О() мы получаем возможность рассуждать об эффективности конкретного алгоритма. Однако эти методы не позволяют определить, может ли существовать лучший алгоритм для рассматриваемой задачи. В области Ъ. анализа сложности исследуются задачи, а не алгоритмы.
Первая широкая градация в этой области проводится между задачами, которые могут быть решены за время, измеряемое полиномиальиым соотношением, и задачами, которые не могут быть решены за время, измеряемое полиномиальным соотношением, независимо от того, какой алгоритм для этого используется. Класс полиномиальных задач (которые могут быть решены за время 0(п") для некоторого )с) обозначается как Р. Эти задачи иногда называют "легкими", поскольку данный класс содержит задачи, имеющие такую продолжительность прогона, как 0(1одп) и 0(п) . Но он содержит и задачи с затратами времени 0(п""), поэтому определение "легкий" не следует понимать слишком буквально.
Еше одним важным классом является )МР (сокращение от Хопдегегш)п)зг)с Ро!упоппа1) — класс недетерминированных полиномиальных задач. Задача относится к этому классу, если существует алгоритм, позволяющий выдвинуть гипотезу о возможном решении, а затем проверить правильность этой гипотезы с помощью полиномиальных затрат времени. Идея такого подхода состоит в том, что если бы можно было воспользоваться сколь угодно большим количеством процессоров, чтобы проверить одновременно все гипотезы, или оказаться крайне удачливым и всегда с первого раза находить правильную гипотезу, то ХР-трудные задачи стали бы Р-трудными задачами.
Одним из самых важных нерешенных вопросов в компьютерных науках является то, будет ли класс ХР эквивалентным классу Р, если нельзя воспользоваться бесконечным количеством процессоров или способностью находить правильную гипотезу с первого раза. Большинство специалистов в области компьютерных наук согласны с тем, что Р~)чр, иными словами, что задачи г(Р являются изначально трудными и для них не существует алгоритмов с полиномиальными затратами времени.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
