Лекции по информатике (984119), страница 36
Текст из файла (страница 36)
Таким образом„с1ерСЬ веагсЬ может быть использован д;ш поиска в любых графах, в том числе и таких, число ребер в которых хотя и является конечным, но очень большим. Еще одним стандартным предикатом является птептЬегсЬ1с. Этот предикат находит первое вхождение элемента в список и тоже может быть реализован на Прологе.
Кроме него существует предикат гпепгЬег, который при помощи переборов с возвратами найдет все вхождения данного элемента в список. Существенно более сложный алгоритм поиска в глубину запишется на Прологе лишь немегого сложнее: аг1чапсе(~Хос1е ~ Ра!Ц, Се??егХагпе, Кса): — СеКг»г .. ?Сег!егХаше, ?~ос?е, ХсММос?е ), йпс?а11Ц?х?ев Ь?ог?е, х?ог1е ! РаЩ.
(Се!.?ег» по$(шегп!эегс1й(?Меи Хог?е, ~Хос!е ! 1эа?Ь))))» Кеэ). Ьгеас??Ь аеагсЬ(?г1!г!а?, Г!па?» СеггегХаше, Раг?г): — !эгеас??Ь веагсЬ Ь(Г!п»ч!» Сеггег?~аггге, ??1гг!г!а?Ц, Кеэ), гетегае(Кеэ, Ра?Ь). Ьгеас1?Ь аеагсЬ Ь(Гша?,, !?Г!па? ! Ра??г1 ! ~» !ГЬ1а! ! Ра??1?).
Ьгеас?ГЬ веагсЬ Ь(Г?па?, Се??ег~аше, ?РагЬ / Ра?Ьв~, Кеа): — ас1ъапсе(Ра?Ь, СеггегМапге, Мегера?Ьа), аррепг?(Ра?Ьв,?хея1'агЬв, РаГ1гв1), !эгеас?гЬ ьеагсЬ Ь( Гша?, СеггегМаше, Раг?гэ1, Кеэ). Этот пример сложнее поиска в глубину. По сложность связана главным образом с реализацией очереди путей в виде списка списков. Предикат ЬгеадФЬ веагсЬ Ь использует прсдикат адчапсе для построения всех продолжений какого-либо пути. Предикат Йпда11 находит все варианты продолжений, проверяя их на, допустимость (вершины не должны повторяться во избежание зацикливания!) и помещая все допустимые пути в список (списков!) Лез.
После получения всех продолжений они дописываются в конец очереди Рагб» и поиск продолжается. Сравните этот пример с приведенным ранее примером на языке Паскаль! Пример на Прологе оказывается более естественным за счет наличия в нем встроенных в язык естественных структур данных, а также за счет того, что собственно алгоритм поиска неявно содержится в логическом интерггретаторе» а Пролог-г11эограмма являет собой лишь список свойств процесса поиска. Впрочем, и Пролог не свободен от недостатков. Одним из них является предикат по$. Операция отрицания многократно усложняет логику первого порядка, и в принципе не все ангра,жеггия этой логики могут быть вычис:юны име~ггго из-за по$.
Поэтому эт»а опер»чгщя в рамках Пролога означает «не удалось доказать». С этим связана еще одна особенность всех Пролог-систем. Возвращаясь к примеру с экзаменом рассмотрим такой запрос; ? — эюзамее»(кол»я» Х). Х 3 Интересный результат! Дело в том, что Пролог-система ничего не знает о таком студенте, поэтому не может доказать, что он получит 5 или 4.
Единственное, что остается это оценка 3. Эту особенность называют прсдпологлсети'м о замьнвтпоспш мири» т, е. любая Пролог-система может считать истинными тс и только те факты, которые есть в ее базе данных. 8.3 Языки функционального программирования (ЫЯР, АГР) В настоящее время мы можем констатировать лишь такие особенности Лиепа как список общего вида в кагюстве основной структуры данных, !эекурсивно-ггнтерпретативнук> природу выполнения и возможность смешанных вычислений. Знакомство с элементами Лиепа полезно для понимания многих примеров, программ и идей, излагаемых в обычных книгах по информатике.
Это элемент американской информатической культуры ~501. Система функционального программирования Л!"Р была предложена Дж. Бэкусом в его знаменитой статье о порочности фон Е!еймановского стиля программирования ~261. Предметный указатель Аксиома, 38 Алфавит, 19 Алгоритм, 7 Автоматизация, 7 Детерминированность, 54 Детерминистичность, 53 Диапазон представления, 157 ЭВМ,7 Характеристика, 29 Информация, 7, 16 Информатика, 7 Интерпретация сообщений.
16 Кнут, Д., 7 Кодировка дополнительная, 27 обратная, 27 Композиция машин Тьюринга, 106 Литера, 19 Мантисса, 28 Машина Тьюринга универсальная, 104, 111 Машина фон Неймана, 118 Модель, 37 Носитель информации, 16 Плавающая точка, 28 Полулогарифмическое представление, 28 Порядок, 28 Процессор фон Неймана, 115 построение, 116 согласование, 117 Программирование, 7 Разделитель, 19 Сигнатура, 37 Система счисления кардинальная, 25 натуральная, 25 позиционная, 25 Сложность пространственная, 34 времени'ая, 34 Согласование типов, 171 Сообщение, 16 Сведения, 16 Теория, 37 Тип литерный, 169 отрезок, 172 перечисление, 172 Типы данных небазовыс, 172 согласование, 171 структурные, 172 Вирт, .Н..
172 Язык, 17 описания программ для машины фон Неймана, 120 описания схем машин Тьюринга, 107 Словарь, 19 Учебное издание Бум. офсетная Уел. печ. л. 26 Тираж 5000 экз. Гайсарян Сергей Суренович Зайцев Валентин Евгеньевич КУРС ИНФОРМАТИКИ Редактор Р.М. Ва.поввровп Художественный редактор Д. А. Абрамов ТЕХнический редактор Д. В. Соилииков Корректор В..Е. Зайцев Обложка художника А. В. Крапиввнко Сдано в набор 31.10.93 Формат 60 х 90 в Издательство МЛИ 125993, Москва, Волоколамское пгоссе, 4. Подписано в печать 28.12.93 Гарнитура Соп1рпгег гпос1егп.
Уч.-изд. л. 25 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
