Логические языки программирования: особенности, примеры
Как часто вы сталкивались с непонятным термином «логическое программирование» и не могли понять, что это? Сегодня мы окончательно определимся с тем, что такое языки программирования логического типа, и рассмотрим примеры таких языков.
Прежде чем начинать обзор языков, необходимо сначала узнать, что это такое и зачем оно нужно.
Что такое логическое программирование?
Это подход к программированию, основанный на доказательстве теорем и выводе информации на основе фактов. Вывод результата является побочным продуктом работы программы. Логическое программирование основано на теории математической логики, включает в себя раздел дискретной математики и некоторые другие.
В чем различия?
Многие объединяют логические языки программирования с функциональными, однако они обладают некоторыми различиями, о которых мы далее поговорим.
В отличие от функциональных, логические очень хорошо подходят для создания искусственного интеллекта. Также иногда очень удобно, когда в языке переменные не делятся на входные и выходные. Именно в таких языках это и происходит, что иногда упрощает работу с кодом. Опять же программы являются более быстрыми и выполняют свои задачи иногда эффективнее. Основная особенность логических языков программирования заключается в том, что программа представляет определенные отношения между элементами.
Однако существуют и минусы. Не все можно описать с помощью логики, поэтому в таких программах функции будут работать не всегда так, как нужно, или вообще не будут работать.
Кому полезно учить языки программирования логического типа?
Стоит сразу ответить на вопрос: учить данные языки полезно всем – от школьника до человека в возрасте. Ведь логические языки программирования способны буквально заставить наш мозг думать логически. Также такие языки будут очень полезны в создании искусственного интеллекта или при работе с данными.
Логические языки программирования
Таких языков не так много, и они отличаются между собой. Мы поговорим только о двух, а начнем с того, с которого началась эра логических языков, и имя ему Prolog.
Данный язык был разработан в 1972 году Аленом Колмероэ и является актуальным и свежим и на сегодняшний день. Хоть это и не самый простой язык в плане синтаксиса, но зато весьма полезен в понимании логики компьютера. Посмотрите, как выглядит код, описывающий книгу:
Такое описание довольно просто понять и разобрать что к чему. Именно поэтому обучение подобному языку дальше не составит огромных трудностей и не потребует танцев с бубном.
Давайте дальше разберем его плюсы и минусы.
1. Код легко понять и запомнить.
Как уже упоминалось выше, код в языке Prolog пишется не так уж и сложно. Он довольно прост, в понимании обычного пользователя.
2. Выражения и факты.
Данный язык можно использовать без каких-либо вычислений, опираясь только на выражения и факты.
Какой бы путь к реализации вашей задумки вы ни выбрали, он практически никогда не влияет на результат выполнения программы.
1. Слабые инвестиции.
Из-за того, что этот язык мало поддерживают в материальном плане – он развивается довольно медленно, маленькими шажками.
2. Невозможность создания комплексных программ.
Данный язык будет невозможно использовать без связки с другим, если вы хотите создавать более сложные программы с большим функционалом.
3. Вычислительные операции.
Для вычислительных операций опять же придется использовать другие языки.
Пошедший от языка Prolog, Mercury создан, чтобы решить две проблемы, связанные с популярным языком программирования.
Логические языки программирования довольно сильно уступают в производительности императивному типу.
В языках такого типа уходит довольно много времени на отладку программы, а также производится меньше проверок на ошибки в программе, из-за чего порой происходят неприятности.
Пример кода на Mercury:
Синтаксис и понимание данного языка, как можно заметить, весьма отличаются от «Пролога», что немного усложняет обучение, однако некоторые его плюсы, помогающие решить проблемы «Пролога», весьма полезны.
Заключение
Языком логического программирования является язык, который обрабатывает выражения и факты, а побочным эффектом выдает результат работы данной программы. Такие языки весьма полезны в создании искусственного интеллекта и работы с данными, однако редко применяются без сторонних языков программирования.
Функциональное и логическое программирование – стили декларативного программирования
В настоящее время декларативная парадигма программирования реализуется с помощью одного из следующих стилей программирования: функционального и логического программирования.
Основной конструкцией в функциональных языках служит символьное выражение (S-выражение). К S-выражениям относятся скалярные константы, структурированные объекты, функции, тела функций и вызовы функций.
Функция трактуется как однозначное отображение из области определения функции в область значений функции, что полностью соответствует математическому определению функции.
Функциональный язык программирования включает следующие элементы:
• классы констант, которыми могут манипулировать функции;
• набор базовых (определенных в данной системе) функций, называемых примитивами;
• правила построения новых функций на основе примитивов;
• правила формирования выражений па основе вызовов функций.
Программа представляет собой совокупность описаний функций и выражений, которые необходимо вычислить. Заданное в программе выражение вычисляется посредством редукции, то есть серии упрощений по следующим правилам:
• вызовы функций-примитивов заменяются соответствующими значениями;
• вызовы определенных программистом функций заменяются их телами, в которых параметры замещены аргументами.
В функциональном программировании не используется концепция памяти как хранилища значений переменных, характерная для фон-неймановской вычислительной архитектуры. Операторы присваивания отсутствуют, вследствие чего переменные обозначают не области памяти, а объекты программы, что полностью соответствует понятию переменной в математике. В функциональном программировании нет существенных различий между константами и функциями, то есть между данными и программами. В результате этого функция может быть значением вызова другой функции, а также элементом структурированного объекта. Число аргументов при вызове функции не обязательно должно совпадать с числом параметров, указанных при ее описании. Таким образом, функциональные языки можно определить как языки сверхвысокого уровня по отношению к языкам высокого уровня.
Логическое программирование базируется на понятии отношения (реляция). Поэтому существует другое название логического программирования – реляционное программирование. Программа представляет собой совокупность определений отношений между объектами и цели.
Процесс выполнения логической программы трактуется как процесс доказательства общезначимости логической формулы, построенной из программы по правилам, установленным семантикой используемого языка. Результат вычисления является побочным продуктом этого процесса.
В логическом программировании нужно только специфицировать факты, описывающие задачу, а не определять последовательность шагов, которые требуется выполнить. Это свидетельствует о декларативном характере языков логического программирования, которые характеризуются:
• строгой ориентацией на символьные вычисления;
• возможностью инверсных вычислений, то есть переменные в процедурах не делятся на входные и выходные.
Следует отметить, что логическое программирование в принципе неэффективно с вычислительной точки зрения. Программы на языке логического программирования имеют небольшое быстродействие, так как вычисления осуществляются методом проб и ошибок, поиском с возвратами к предыдущим шагам. Несмотря на это, логическое программирование привлекательно именно с точки зрения приближения к декларативной парадигме программирования. Наибольший эффект логическое программирование дает при решении неформальных задач, задач, алгоритм решения которых неизвестен или получение алгоритма сопряжено с большими трудностями. В этом случае описание задачи в терминах того, что надо получить, приводит к цели с наименьшими затратами.
Наибольшее количество описанных выше задач относится к сфере проблем искусственного интеллекта.
Системы искусственного интеллекта – основная область приложения функционального и логического программирования
Под термином системы искусственного интеллекта (СИИ) понимаются кибернетические системы, моделирующие некоторые стороны интеллектуальной деятельности человека – логическое, аналитическое мышление. Задачей-максимум в области СИИ можно считать понимание принципов и механизмов интеллектуальной деятельности человека. Однако в идеале вряд ли такая задача достижима когда-либо вообще. Практически работы в области СИИ проводились по отдельным задачам, каждая из которых предполагала имитирование отдельной, строго ограниченной области интеллектуальной деятельности. Ниже следует перечень основных из этих задач:
• проблемы естественного языка (ЕЯ-проблемы), основная цель – общение с ЭВМ на естественном для человека языке;
• экспертные системы – системы обработки данных, основанные на знаниях и экспертных оценках в некоторой области;
• распознавание образов – автоматическое наблюдение и идентификация (классификация) объектов;
Основные пути для решения этих задач – эвристическое программирование и с помощью нейрокомпьютерных систем. Эвристическое программирование предполагает описание логической спецификации задачи. При решении задачи с помощью нейрокомпьютерных систем моделируется система, функционирующая на основе имитации некоторых известных свойств организации нервной деятельности высших животных. В этом случае не требуется описания логики задачи, достаточно набора примеров, на решение которых настраивается нейронная сеть.
Программы на декларативных языках гораздо ближе к логической спецификации (ЛС), чем на любом императивном языке. В большинстве случаев – это просто записывание логической спецификации задачи в терминах конкретного языка программирования. Для большинства программных систем искусственного интеллекта характерно то, что они имеют дело со сложными проблемами, которые недостаточно хорошо понимаемы. Для многих проблем искусственного интеллекта не существует четко заданных алгоритмических решений, но они могут быть исследованы с помощью механизмов символических рассуждений.
Разработка естественно-языковых интерфейсов и машинный перевод. В настоящее время используется более сложная модель, включающая анализ и синтез естественно-языковых сообщений. Модель состоит из нескольких блоков: морфологический анализ – анализ слов в тексте; синтаксический анализ – анализ предложений, грамматики и связей между словами; семантический анализ – анализ смысла каждого предложения на основе некоторой предметно-ориентированной базы знаний; прагматический анализ — анализ смысла предложений в окружающем контексте на основе собственной базы знаний. Синтез включает аналогичные этапы, но несколько в другом порядке.
Билет№26. Императивные, функциональные и логические языки программирования
Интерпретатор — это программа, обеспечивающая перевод с алгоритмического языка высокого уровня на машинный с одновременным выполнениемоператоров программы. Трансляция программы — преобразование программы, представленной на одном из языков программирования, в программу на другом языке и, в определённом смысле, равносильную первой. Язык, на котором представлена входная программа, называется исходным языком, а сама программа — исходным кодом. Выходной язык называется целевым языком или объектным кодом.
Языки программирования принадлежат трем классам:1)интеративный(процедурные)-это парадигма программирования, которая, в отличие от декларативного программирования, описывает процесс вычисления в виде инструкций, изменяющих состояние программы. Императивная программаочень похожа на приказы, выражаемые повелительным наклонением в естественных языках, то есть это последовательность команд, которые должен выполнить компьютер. Императивные языки программирования противопоставляются функциональным и логическим языкам программирования. Функциональные языки, например, Haskell, не представляют собой последовательность инструкций и не имеют глобального состояния. Логические языки программирования, такие как Prolog, обычно определяют что надо вычислить, а не как это надо делать. Функциона́льное программи́рование(LISP, HASKEL) — раздел дискретной математики и парадигма программирования, в которой процесс вычисления трактуется как вычисление значений функций в математическом понимании последних (в отличие от функций как подпрограмм в процедурном программировании). При необходимости, в функциональном программировании вся совокупность последовательных состояний вычислительного процесса представляется явным образом, например как список.Функциональное программирование предполагает обходиться вычислением результатов функций от исходных данных и результатов других функций, и не предполагает явного хранения состояния программы. Соответственно, не предполагает оно и изменяемость этого состояния (в отличие от императивного, где одной из базовых концепций является переменная, хранящая своё значение и позволяющая менять его по мере выполнения алгоритма). На практике отличие математической функции от понятия «функции» в императивном программировании заключается в том, что императивные функции могут опираться не только на аргументы, но и на состояние внешних по отношению к функции переменных, а также иметь побочные эффекты и менять состояние внешних переменных. Таким образом, в императивном программировании при вызове одной и той же функции с одинаковыми параметрами, но на разных этапах выполнения алгоритма, можно получить разные данные на выходе из-за влияния на функцию состояния переменных. А в функциональном языке при вызове функции с одними и теми же аргументами мы всегда получим одинаковый результат: выходные данные зависят только от входных. Это позволяет средам выполнения программ на функциональных языках кэшировать результаты функций и вызывать их в порядке, не определяемом алгоритмом. Логи́ческое программи́рование(алгоритма нет, объявление неких фактов) — парадигма программирования, основанная на автоматическом доказательстве теорем, а также раздел дискретной математики, изучающий принципы логического вывода информации на основе заданных фактов и правил вывода. Логическое программирование основано на теории и аппарате математической логики с использованием математических принципов резолюций. Самым известным языком логического программирования является Prolog. Первым языком[источник не указан 971 день] логического программирования был язык Planner, в котором была заложена возможность автоматического вывода результата из данных и заданных правил перебора вариантов (совокупность которых называлась планом). Planner использовался для того, чтобы понизить требования к вычислительным ресурсам (с помощью метода backtracking) и обеспечить возможность вывода фактов, без активного использования стека. Затем был разработан язык Prolog, который не требовал плана перебора вариантов и был, в этом смысле, упрощением языка Planner.
Билет№27 Парадигмы программирования. Подпрограммы, модульность, структурные программирования, объективно ориентировочные программирования.
Билет№28 Этапы разработки программы тестирования. Откладка. Верификация.
Билет№29 Оценка эффективности нерекурсивных алгоритмов. пример.
Билет№30 Оценка эффективности рекурсивных алгоритмов. пример.
Билет № 31 Реккурентные соотношения. Решения методом обратной подстановки.
M(n)=M(n-1)+1 (на другой строке/)/ M(n-1)=M(n-2)+1 / M(n-2)=M(n-3)+1 /…./M(n)=M(n-2)+1+1 / =M(n-3)+3 / =M(n-4)+4 / M(n)=M(n-k)+k / k=n/ M(n-n)=M(0) / M(n)=n
Билет№32 Основные функции, используемые в оценках алгоритма.
Билет №33 Алгоритм сортировки методом пузырька.
Сортировка простыми обменами, сортиро́вка пузырько́м— простой алгоритм сортировки. Для понимания и реализации этот алгоритм — простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n²). Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма. Возьмём массив с числами «5 1 4 2 8» и отсортируем значения по возрастанию, используя сортировку пузырьком. Выделены те элементы, которые сравниваются на данном этапе:
Первый проход:(5 1 4 2 8) (1 5 4 2 8), Здесь алгоритм сравнивает два первых элемента и меняет их местами./(1 5 4 2 8) (1 4 5 2 8), Меняет местами, так как 5 > 4/(1 4 5 2 8) (1 4 2 5 8), Меняет местами, так как 5 > 2/(1 4 2 5 8) (1 4 2 5 8), Теперь, ввиду того, что элементы стоят на своих местах (8 > 5)/ алгоритм не меняет их местами. Второй проход:(1 4 2 5 8) (1 4 2 5 8)/ (1 4 2 5 8) (1 2 4 5 8), Меняет местами, так как 4 > 2/ (1 2 4 5 8) (1 2 4 5 8)/ (1 2 4 5 8) (1 2 4 5 8)Теперь массив полностью отсортирован, но алгоритм не знает так ли это. Поэтому ему необходимо сделать полный проход и определить, что перестановок элементов не было. Третий проход:(1 2 4 5 8) (1 2 4 5 8)/ (1 2 4 5 8) (1 2 4 5 8)/ (1 2 4 5 8) (1 2 4 5 8)/ (1 2 4 5 8) (1 2 4 5 8)/ Теперь массив отсортирован и алгоритм может быть завершён.
Билет№34 Алгоритм сортировки выбором.
Билет№35 Алгоритм линейного поиска.
Линейный, последовательный поиск — алгоритм нахождения заданного значения произвольной функции на некотором отрезке. Данный алгоритм является простейшим алгоритмом поиска и в отличие, например, от двоичного поиска, не накладывает никаких ограничений на функцию и имеет простейшую реализацию. Поиск значения функции осуществляется простым сравнением очередного рассматриваемого значения (как правило поиск происходит слева направо, то есть от меньших значений аргумента к большим) и, если значения совпадают (с той или иной точностью), то поиск считается завершённым.Пример в тетр.
Билет№36 Алгоритм бинарного поиска.
Идея этого алгоритма проста(работает на отсортированных массивах\списках):Сначала высчитываем индекс среднего элемента по формуле (m+n)//2.Где n это индекс начального элемента, а m количество элементов в массиве В случае нечетного числа элементов округляем до ближайшего целого полученный результат.А дальше уже смотрим что получается:а) Элемент найден и мы возвращаем его индекс б) Средний элемент меньше ключа поиска в) Средний элемент больше ключа поиска В случае б) мы должны отсечь те элементы которые меньше среднего, то есть правую часть массива\списка. Дробится этого можно приняв за начальную границу поиска первый элемент со значением больше чем средний элемент, а у нас массив\список сортированный значит это элемент с индексом i+1, где i индекс среднего элемента. а конечная граница поиска последний элемент. в случае в) нам нужно принять за начальную границу первый элемент меньший среднего, а значит нам нужен элемент с индексом i-1. Как конечная граница поиска естественно принять индекс первого элемента. Итак весь процесс будем повторять пока не выполниться любое из трех условий:1) Элемент найден 2) Начальная граница стала равна наибольшему элементу массива3) Начальная граница стала равна индексу наименьшего элемента.Самый положительный для нас случай 1.Преимущество алгоритма в том что при каждом сравнении убавляется половина отрезка, где происходит поиск элементов.Краткое описание алгоритма:1. Взять индекс первого элемента (n)2. Взять индекс конечного элемента (длину массива ) (m)3. Рассчитать индекс среднего элемента по формуле (m+n)\2 (i) 4. Сравнить средний элемент с ключом4a Пока 0 элементу,то n=i+1 m=len(l) 5в Если ключ
Дата добавления: 2015-04-24 ; Просмотров: 1712 ; Нарушение авторских прав?
Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет