Laboratorny_praktikum_1

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«МОРДОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМ. Н. П. ОГАРЁВА»

Факультет математики и информационных технологий

ОТЧЕТ по лабораторному практикуму по дисциплине «Интеллектуальные системы»

Автор ___________________ В. М. Бабанова

Группа 102

Направление подготовки: 010300.62 Фундаментальная информатика и информационные технологии

Преподаватель канд. физ.-мат. наук ___________________ А. Н. Мадонов

Отметка: ____________

Саранск 2014

Лабораторная работа № 1

Анализ текстовой информации с помощью интеллектуальной системы TextAnalyst

Подготовим в текстовом редакторе Microsoft Office Word текстовой до­кумент объемом около 13 страниц на тему «Языки программирования систем искусственного интеллекта» и проведем семантический анализ текста с помощью ин­теллектуальной системы

Прогресс компьютерных технологий определил процесс появления новых разнообразных знаковых систем для записи алгоритмов – языков программирования. Смысл появления такого языка – оснащенный набор вычислительных формул дополнительной информации, превращает данный набор в алгоритм.

Язык программирования служит двум связанным между собой целям: он дает программисту аппарат для задания действий, которые должны быть выполнены, и формирует концепции, которыми пользуется программист, размышляя о том, что делать. Первой цели идеально отвечает язык, который настолько "близок к машине", что всеми основными машинными аспектами можно легко и просто оперировать достаточно очевидным для программиста образом. Второй цели идеально отвечает язык, который настолько "близок к решаемой задаче", чтобы концепции ее решения можно было выражать прямо и коротко.

Связь между языком, на котором мы думаем/программируем, и задачами и решениями, которые мы можем представлять в своем воображении, очень близка. По этой причине ограничивать свойства языка только целями исключения ошибок программиста в лучшем случае опасно. Как и в случае с естественными языками, есть огромная польза быть, по крайней мере, двуязычным. Язык предоставляет программисту набор концептуальных инструментов, если они не отвечают задаче, то их просто игнорируют. Например, серьезные ограничения концепции указателя заставляют программиста применять вектора и целую арифметику, чтобы реализовать структуры, указатели и т.п. Хорошее проектирование и отсутствие ошибок не может гарантироваться чисто за счет языковых средств.

Может показаться удивительным, но конкретный компьютер способен работать с программами, написанными на его родном машинном языке. Существует почти столько же разных машинных языков, сколько и компьютеров, но все они суть разновидности одной идей простые операции производятся со скоростью молнии на двоичных числах.

Можно писать программы непосредственно на машинном языке, хотя это и сложно. На заре компьютеризации(в начале 1950-х г.г.), машинный язык был единственным языком, большего человек к тому времени не придумал. Для спасения программистов от сурового машинного языка программирования, были созданы языки высокого уровня (т.е. немашинные языки), которые стали своеобразным связующим мостом между человеком и машинным языком компьютера. Языки высокого уровня работают через трансляционные программы, которые вводят "исходный код" (гибрид английских слов и математических выражений, который считывает машина), и в конечном итоге заставляет компьютер выполнять соответствующие команды, которые даются на машинном языке.

Рассмотрим некоторые из языков программирования, разработанных для интеллектуальных систем.

Prolog — язык логического программирования. Логическое программирование, так же как и родственное ему направление — функциональное программирование, радикально отклоняется от основного пути развития языков программирования. Логическое программирование строится не с помощью некоторой последовательности абстракций и преобразований, отталкивающейся от машинной архитектуры фон Неймана и присущего ей набора операций, а на основе абстрактной модели, которая никак не связана с каким-либо типом машинной модели. Логическое программирование базируется на убеждении, что не человека следует обучать мышлению в терминах операций компьютера (на некотором историческом этапе определенные ученые и инженеры считали подобный путь простым и эффективным), а компьютер должен выполнять инструкции, свойственные человеку. В своем предельном и чистом виде логическое программирование предполагает, что сами инструкции даже не задаются, а вместо этого явно, в виде логических аксиом, формулируются сведения о задаче и предположения, достаточные для ее решения. Такое множество аксиом является альтернативой обычной программе. Подобная программа может выполняться при постановке задачи, формализованной в виде логического утверждения, подлежащего доказательству, — такое утверждение называется целевым утверждением. Выполнение программы состоит в попытке решить задачу, т. е. доказать целевое утверждение, используя предположения, заданные в логической программе.

Логическое программирование — это подход к информатике, при котором в качестве языка высокого уровня используется логика предикатов первого порядка в форме фраз Хорна. Логика предикатов первого порядка — это универсальный абстрактный язык предназначенный для представления знаний и для решения задач. Его можно рассматривать как общую теорию отношений. Логическое программирование базируется на подмножестве логики предикатов первого порядка, при этом оно одинаково широко с ней по сфере охвата. Логическое программирование дает возможность программисту описывать ситуацию при помощи формул логики предикатов, а затем, для выполнения выводов из этих формул, применить автоматический решатель задач (т. е. некоторую процедуру). При использовании языка логического программирования основное внимание уделяется описанию структуры прикладной задачи, а не выработке предписаний компьютеру о том, что ему следует делать. Другие понятия информатики из таких областей, как теория реляционных баз данных, программная инженерия и представление знаний, также можно описать (и, следовательно, реализовать) с помощью логических программ. Однако вернемся к языку Prolog: первая часть введения посвящена истории языка Prolog.

• История создания и развития языка Prolog

Разработка языка Prolog началась в 1970 году Аланом Кулмероэ и Филиппом Расселом. Их целью было создание языка, который мог бы делать логические заключения на основе заданного текста. Название Prolog является сокращением от "Programming in logic". Итак, Prolog, как язык, был разработан в Марселе в 1972 году. Предварительно на основе некоторого "принцип резолюции" Ковальского, сотрудника Эдинбургского университета, была создана модель, на основе которой и был разработан механизм логических выводов.

Первая реализация языка Prolog с использованием компилятора Никлауса Вирта "Algol-W" была закончена в 1972 году, а основы современного языка были заложены позднее, в 1973 г. Использование языка Prolog постепенно распространялось среди тех, кто занимался логическим программированием, в основном благодаря личным контактам, а не через коммерциализацию продукта. В настоящее время существует несколько различных, но довольно похожих между собой версий языка. Хотя стандарта языка Prolog не существует, однако версия, разработанная в Эдинбургском университете, стала наиболее широко используемым вариантом.

Теория логического программирования со временем совершенствовалась. Существенный вклад в ее развитие внесла работа Р. Ковальского "Логика предикатов как язык программирования". В 1976 г. Ковальский и М. ван Эмден предложили два подхода к прочтению текстов логических программ — процедурный и декларативный. Оба этих подхода стали активно использоваться при написании программ на языке Prolog.

Только в 1977 году Д. Уоррен и Ф. Перейра создают в университете Эдинбурга интерпретатор/компилятор языка Prolog для ЭВМ DEC-10, тем самым переведя методы логического программирования в практическую плоскость. Позднее в 1980 году К. Кларк и Ф. Маккейб в Великобритании разработали версию Prolog для персональных ЭВМ.

Также есть интересный факт: в октябре 1981 года мир облетела новость о японском проекте создания ЭВМ пятого поколения. В основу методологии разработки программных средств было положено логическое программирование. Целью проекта декларировалось создание систем обработки информации, базирующихся на знаниях, а главным средством реализации должен был стать именно язык Prolog. В это же время (начало 1980-х годов) появляется множество коммерческих реализаций Prolog практически для всех типов компьютеров. К наиболее известным можно отнести "Visual Prolog", "Тurbo Prolog", "SWI-Prolog". и др.

Существует мнение, что Prolog — уже почти умерший язык, что он за небольшой промежуток времени (1970-1980-е годы) смог пройти весь жизненный цикл — от начальных разработок, стремительного повышения интереса со стороны узких специалистов, затем стремительный взлет популярности, падение интереса и почти полное забвение. Мнение вызвано тем, что такая судьба — обычное явление в мире информационных технологий, где новые, более совершенные, дидактически верные и теоретически более красивые языки программирования возникают каждый год и тихо умирают. Сторонники мнения аргументируют его тем, что структура Prolog-программ очень трудна для восприятия из-за того, что иногда невозможно визуально предугадать ход логического вывода — единственный предикат-факт, запрятанный где-то в конце текста программы, может направить работу в совершенно непредсказуемое русло. В некотором они правы: трудность сопровождения Prolog-программ и трудность мышления на Prolog для рядовых программистов оказались непреодолимыми препятствиями для его широкого распространения. Да и, конечно, во времена разработки Prolog ждали от него большего, но потом оказалось, что сам по себе язык программирования помочь в решении серьезнейших задач, например, связанных с принятием компьютером решений (machine reasoning), не может. Но всё же язык Prolog используется и сегодня при решении целого класса достаточно специфических задач.

У каждого из языков программирования есть свой круг задач, при решении которых он используется с наибольшей эффективностью.

Для Prolog это задачи, связанные с разработкой систем искусственного интеллекта (различные экспертные системы, программы-переводчики, интеллектуальные игры). Он используется для обработки естественного языка и обладает мощными средствами, позволяющими извлекать информацию из баз данных, причем методы поиска, используемые в нем, принципиально отличаются от "традиционных".

Prolog нашел применение и в ряде других областей, например, при решении задач составления сложных расписаний. При этом он не является универсальным языком программирования и не предназначен, например, для решения задач, связанных с графикой или численными методами.

Prolog используется в различных системах, но обычно не в качестве основного языка, а в качестве языка для разработки некоторой части системы. Так Prolog достаточно часто используется для написания функций взаимодействия с базами данных. Prolog используется при разработки расширенных поисковых систем, то есть систем, которые не просто занимаются поиском текста (поиск текста — задача техническая, инженерная), но и играют роль некоторой "отвечающей системы" — программного комплекса, который умеет извлекать информацию (знания) из большой выборки текстовых файлов, а затем вести диалог с пользователем, отвечая (в обычном понимании этого слова) на вопросы посвященный этой теме. Почему в таком случае используется именно Prolog, а не какой-либо другой язык? Потому что именно он разрабатывался для задач, связанных с так называемым "искусственным интеллектом".

Также Prolog используется при написании новых специфичных языков программирования. Например, функциональный язык Erland постороен на основе Prolog. По сути, Erland является усовершенствованием Prolog для некоторых специфических целей, связанных с задами реального времени.

Некоторые приложения в таких областях, как экспертные системы, планирование, машинное обучение, так называемый "искусственный интеллект" игр, реализованы именно с помощью Prolog. Так что, несмотря на то, что сферы использования этого языка, хоть и не так велики и обширны, как сферы применения "традиционных" языков (C, Java и т.п.), представляют свой интерес.

Можно констатировать, что по большому счету ПРОЛОГ не занял в 90-е годы тех позиций, которые ему пророчили в начале 80-х. Нашумевший проект создания ЭВМ пятого поколения привел не к тем последствиям, которые от него ожидали. В практическом плане широкое внедрение графического интерфейса систем разработки программ и развитие визуального программирования придали «второе дыхание» традиционным процедурным языкам программирование. Широкую популярность завоевал объектно-ориентированный подход, позволяющий объединить описание объектов предметной области с процедурами их обработки, а также строить иерархические описания объектов с помощью механизма наследования.

В теоретическом плане самым важным является тот факт, что логика предикатов первого порядка, на которой построен ПРОЛОГ, имеет очевидные ограничения, поскольку требует структурно упрощать описываемую область. Говорить о доказательном выводе можно в сравнительно небольшом числе случаев, когда предметная область хорошо известна.

Большинство же реальных задач относится к условиям неполноты и некорректности данных и знаний. Поэтому большинство существующих экспертных систем активно используют такие механизмы обработки неточных и неопределенных знаний, как нечеткая логика и нейронные сети.

В данном курсовом проекте была рассмотрена история создания и развития языка Prolog, сферы его использования. Также рассмотрены структура программы SWI-Prolog, Тurbo Prolog и Visual Prolog. Начиная с первой версии SWI-Prolog этот язык программирования окончательно превратился в язык, способный решать практически любые задачи современного программирования, система программирования, которая с успехом может применяться не только в традиционных для логического программирования приложениях.

Тем не менее, корни этого языка находятся в области логического программирования: имеется достаточно широкий круг задач, традиционно относящихся к задачам искусственного интеллекта, для которых первоначально предназначался, а впоследствии совершенствовался, язык Пролог (Программирование на основе Логики).

Тем не менее, интерес к ПРОЛОГу не ослабевает, поскольку логическое мышление остается основным инструментом умственной деятельности человека. Возможно, эпоха массового использования ПРОЛОГа просто наступит несколько позже.

История универсального языка программирования Lisp пронизана острыми дискуссиями, жаркими спорами, противоречивыми суждениями, яркими достижениями и смелыми изобретениями. В нашей стране знакомство программистов с этим языком состоялось из первых рук. Совершая в конце 1968 года турне по СССР , Джон Маккарти прочел в Москве и Новосибирске циклы лекций, посвященных языку Lisp и автоматизации доказательств теорем. В рабочем порядке он описал с помощью языка Algol-60 основные алгоритмы системы программирования для языка Lisp 1.5, выражая при этом серьезный скепсис относительно возможности полноценной ее реализации на нашей лучшей ЭВМ БЭСМ-6. Этот скепсис прозвучал как интеллектуальный вызов. К этому времени С.С. Лавровым и А.П. Ершовым уже были развернуты проекты по созданию отечественных систем программирования на языке Lisp 1.5 на БЭСМ-6.

Московская реализация языка Lisp много лет служила базовым инструментарием работ по искусственному интеллекту и символьной обработке. В дальнейшем были выполнены подобные реализации языка Lisp на ОДРА 1204 и ЕС ЭВМ .Ряд интересных работ по автоматизации представления и анализа сложных молекул на этой системе выполнил В.С.Лозовский . Поддержка системы и ее модернизация осуществлялись В.М. Юфой. Этот проект в своей биографии С.С. Лавров признает одной из самых успешных разработок.

Новосибирская (ВЦ СО АН СССР) Лисп-система, разработанная Л.В. Городней, Л.В. Черноброд и Т.С. Янчук под руководством А.П. Ершова, слабо освещена в публикациях . Новосибирская реализация языка Lisp применялась в пионерских исследованиях проблемы автоматизации проверки доказательств теорем и правильности высказываний о программах, преимущественно о типах данных. Кроме того — в студенческих работах и экспериментах по преобразованию и макетированию программ с целью поддержки процесса их разработки. Согласно новосибирской моде того времени система включает русифицированную версию языка. Эксплуатировалась система без особых переделок практически до демонтажа БЭСМ-6.

Историю языка Lisp обычно датируют 1958 годом, начиная с публикации, хотя многие идеи сложились ранее в работах Дж. Маккарти(1956—1957), посвященных формализации средств и методов для решения задач искусственного интеллекта.

В исследованиях истории Лиспа профессор H. Stoyan показывает насколько непредвзято и тщательно, изобретательно и ответственно оттачивались решения по языку и методам его реализации. Были учтены как математические и лингвистические, так и эргономические и технологические аспекты разработки и применения будущих систем программирования на нового языка. Большое внимание было уделено расширению круга специалистов, заинтересованных в программировании на Лиспе.

За краткий период времени были разработаны три версии языка Lisp 1, Lisp 1.5, Lisp 2, определения которых показывают высокий темп изменения круга понятий и выбора практичного компромисса для входного языка системы программирования. Lisp 2 представляет собой перенос решений, выработанных дляLisp 1.5, на задачи вычислительного характера в стиле языка Algol 60.

При первых реализациях языка сложилась структура системы программирования как комплекса из интерпретатора, компилятора, средств ввода-вывода списков и доступа к памяти с автоматической «сборкой мусора»и встроенной базой данных с динамически изменяемым форматом записей, хранящих информацию об атомах, обеспечивающих взаимодействие всех элементов системы и программы.

Восхищает смелость, общность и меткость большинства реализационных решений, противоречащих уже сложившейся технике программирования того времени ради освобождения программиста от сосредоточенности на непринципиальных затруднениях:

• На фоне тщательного программирования поячеечного распределения памяти и ее методичного, причем небезопасного, изменения предлагается схема беззаботного размещения гибких списков произвольного размера с автоматической «сборкой мусора» лишь при дефиците памяти.

• От вычислений в пределах машинного слова осуществлен прорыв к работе с целыми неограниченной длины и вещественными с задаваемой точностью.

• В сравнении с форматным вводом-выводом в Фортране или скалярным в Паскале Лисп сразу позволяет вводить и выводить данные любой сложности без особых ритуальных действий.

• Вместо серии мелких шагов целенаправленного накопления результатов обработки данных, хранимых в отдельных машинных словах, осуществлен переход к высокоуровневым выражениям, символизирующим отображения преобразуемых структур данных в интегральный результат посредством независимо программируемых рекурсивных функций, допускающих лаконичную форму.

• Унаследованная от Фортрана идея раздельной компиляции реализуется как встроенная функция, которую можно вызвать в любой момент выполнения программы и по мере необходимости уточнять границу между отлаженными, созревшими для компиляции частями и недоотлаженными и потому интерпретируемыми для удобства диалоговой отладки.

• Интерпретатор также входит в систему как встроенная функция, что позволяет программировать свои схемы вычислений, интерпретировать и компилировать динамически сконструированные программы как теперь говорят «на лету».

• В целях обучения выделено концептуальное подмножество (Pure Lisp), достаточное для освоения наиболее важных особенностей языка, и разработан небольшой, но содержательно полный, сборник задач с ответами(240 задач на обработку списков и символьные преобразования формул) для быстрого самостоятельного перехода к программированию на языке.

В архиве академика А.П. Ершова хранится более 340 документов с упоминанием Дж. Маккарти — это письма и телеграммы, программы встреч и отчеты о них, заметки по следам бесед и встреч на конференциях, проекты и отклики на события, обмен мнениями и идеями относительно перспектив становления и развития программирования. С 1965 года встречи становятся почти ежегодными. Язык Lisp упоминается в большинстве документов того времени — преимущественно Lisp 2.

Начиная в декабре 1965 года, по завершении проекта АЛЬФА, продумывать проект БЕТА, Андрей Петрович включает Lisp в обзор наиболее интересных языков для решения логических задач. Годом позже Lisp 2 рассматривается как возможный кандидат на выбор основы при разработке БЕТА-языка первой БЕТАгруппой. В наброске двухуровневого БЕТА-языка отражена полемика между сторонниками базиса на внутреннем (Lisp) или внешнем (Algol) языке. Независимо от альтернативы операции над списками выбраны как в языке Lisp 1.5. Именно с этого момента и стартует Новосибирский Лисп-проект в рамках дипломной работы Т.С. Янчук, материалы для которой были высланы С.С. Лавровым.

Татьяна Янчук очень быстро реализовала ядро интерпретатора для Лисп-системы (без «мусорщика»), что позволило инициировать в Новосибирске первые работы по методам автоматизации логического вывода в рамках курсовой работы Л.В. Суковотициной.

Джон Маккарти участвовал в ВКП-2 с докладом «Текущее состояние математической теории вычислений» и активно дискутировал в кулуарных обсуждениях (он хорошо владеет русским языком), разъясняя роль абстрактных построений в теории и практике программирования, особенно при разработке больших программ. После участия в Международном симпозиуме «Проблемы теории программирования» Джон Маккарти и Джекоб Шварц на две недели включились в работы ВЦ СО РАН СССР по реализации языков Лисп и Сетл, что и позволило ему поэкспериментировать с новой реализацией Lisp-системы на БЭСМ-6, разработанной в ВЦ СО АН СССР. Тест, показывает ключевые построения, отличающие язык Lisp от традиционных языков программирования.

Перекличка друзей выдержала многолетние испытания, и в 1987 году Джон Маккарти принял участие в работе ЛШЮП, традиции которой до сих пор поддерживаются ИСИ СО РАН

Много более давняя и тесная дружба связывает Андрея Петровича Ершова со Святославом Сергеевичем Лавровым. Научный архив С.С. Лаврова передан на хранение в электронный архив А.П. Ершова.

В предисловии авторы отмечают, что в основу языка Lisp «положены оригинальные идеи, знакомство с которыми обогащает программистскую квалификацию и культуру и приносит пользу, даже если программист в дальнейшем и не работает с этим языком». По мнению авторов приведенное в книге «описание интерпретатора может служить примером подхода к составлению любых больших программ, т.е. программ, значительно превосходящих по размеру и сложности те программы, которые встречаются в учебных пособиях или излагаются на занятиях по программированию». Далее они констатируют, что «язык Лисп устроен так, что он во многих случаях позволяет находить путь к решению задачи постепенно, последовательно сводя ее к более простым задачам».

Немаловажно, что положенные в основу языка «понятия символьного выражения и рекурсивной функции, имеющей такие выражения своими аргументами, определяются очень просто — проще, чем основные понятия большинства других алгоритмических языков». Авторы констатируют, что в Лиспе «наименование функции —это по сути дела разновидность константы, отличающаяся тем, что ее значением является так называемое определяющее выражение некоторой функции». Приняв, что «вся сила языка заключена в возможности свободно пользоваться рекурсивными функциями», авторы нашли реализационные решения, обеспечивающие возможность функциям могут быть аргументами, причем определения функций могут содержать свободные переменные, что приводит к так называемой FUNARG-проблеме: «Значения свободных переменных в момент задания функциональных аргументов и в момент его использования могут отличаться друг от друга. Считается, что при вычислении тела определяющего выражения должны использоваться те значения свободных переменных, которые эти переменные имели во время задания функциональных аргументов, а не те, которые они могли получить позже». При реализации системы изобретено и реализовано оригинальное эффективное решение FUNARG-проблемы, заключающееся в особой разметке областей действия переменных в ассоциативном списке с помощью специального мостика, позволяющего при вызове функциональных аргументов переходить к состоянию ассоциативного списка в момент вызова объемлющей функции. «Среди ячеек, содержащих пары переменная — значение, могут быть вкраплены ячейки, CAR указатель которых содержит адрес Nil, а CDR указатель — адрес одной из предшествующих ячеек ассоциативного списка».

Интересным является использование циклических списков для реализации разметки рабочих переменных:«Nillist — адрес циклической списочной структуры, имитирующей бесконечный список, составленный из атомов Nil».

Выражение (EVAL (LIST (QUOTE GO) X)) внутри формы PROG выполняет работу, подобную вычисляемому переходу в языке Fortran.

Средства ввода данных (READ) переводят текстовую форму любого символьного выражения в структуру данных, а средства вывода (PRINT) — печатают свой аргумент, являющийся значением функции, что удобно при отладке программ.

Некоторые реализационные ограничения связаны с организацией списков свойств атомов. Принимая, что«атомы могут быть наделены различными свойствами — атом может быть наименованием переменной, константы или функции или же числом. Функции и числа в свою очередь делятся на классы», в этой системе ради простоты реализации были ограничены средства работы с атомами: хранятся лишь значения и определения функций. Индикаторы свойств реализованы как разряды в информационной ячейке атома.

Приведено описание реализационных механизмов системы (интерпретатор, компилятор, ввод-вывод, форма PROG, арифметика, списки свойств и «уборка мусора».Язык описания Algol-60.

В своей биографии С.С. Лавров отмечает «Существенно более успешной была реализация языка Лисп на БЭСМ-6 (совместно с Г.С. Силагадзе). Удалось создать неплохие интерпретатор и компилятор Лиспа. В книге тех же авторов "Язык Лисп и его реализация" (М.: Наука, 1978) описана более совершенная реализация» .