Индивидуальные задания

1. Напишите программу, которая преобразует логическую форму­лу F1 в логическую формулу F2, используя следующие аксиомы:

true V F=true и false & F=false, где F – логическая формула.

2. Напишите программу, которая определяет, является ли данный граф свободным деревом. Свободное дерево – это связный граф, не имеющий циклов.

3. Напишите программу, определяющую, в нормальной ли форме задана арифметическая сумма, т.е. имеет ли она вид A+B, где A -константа, а В - сумма в нормальной форме.

4. Напишите программу, которая преобразует логическую формулу F1 в логическую формулу F2 внесением всех операторов отрицания внутрь конъюнкций и дизъюнкций.

5. Определите отношение tree_insert(X, Tree, Tree1), выполненное, если упорядоченное дерево Tree1 получается вставкой элемента X в упорядоченное дерево Tree. Если X уже присутствует в Tree, то Tree1 совпадает с Tree.

6. Напишите программу, которая по заданному направленному графу определяет самый длинный цикл.

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

((X& Y) V ¬X)V ¬ (У &Z) - тавтология.

8. Определите отношение ex_tree(Tree, Ex), выполненное, если число Ex является значением выражения, представленного в виде дво­ичного дерева. Допустимыми операциями в арифметическом выражении являются: +, -, /, *.

9. Определите отношение sum_tree(Tree_of_integer, Sum) выполненное, если число Sum равно сумме целых чисел, являющихся вершинами дерева Tree_of_integer.

10. Определите отношение ordered(tree), выполненное, если дерево Tree является упорядоченным деревом целых чисел, т.е. число, стоящее в любой вершине дерева, больше любого элемента в левом поддереве и меньше любого элемента в правом поддереве.

11.Определите процедуру, вычисляющую глубину двоичного дерева. Глубина пустого дерева равна 0, одноэлементного – 1.

12. Определите отношение max_element(Tree, Element), выполненное, если, Element является максимальным среди элементов, хранящих­ся в дереве.

13. Составьте программу subtree(S,T), определяющую, является ли S поддеревом Т.

14. Напишите программу, которая по заданному конечному авто­мату и слову в некотором алфавите определяет, принадлежит ли данное слово языку, допускаемому данным автоматом.

Контрольные вопросы

1. Рекурсивные структуры и их способы описания в Прологе.

2. Двоичные деревья и типичные операции над деревьями.

3. Упорядоченные деревья или справочники.

4. Двоично-троичные справочники.

5. Описание n-ичных деревьев.

6. Способы задания графов и типовые операции над графами в Прологе.

7. Предикат отсечения в Прологе и его назначение.

8. Зеленые и красные отсечения.

9. Достоинства и недостатки использования предиката отсечения в логическом программировании.

10. Отсечение и отрицание как неуспех.

11. Основные трудности в использовании отсечений и отрицаний в программировании на Прологе.

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

Встроенные предикаты Турбо-Пролога. Предикаты ввода-вывода, предикаты обработки строк

Цель работы

Изучить особенность использования предикатов данных типов и получить навык использо­вания этих предикатов при проектировании программ на Прологе.

Содержание работы

1. Прочитать теоретический материал [1, с.141-144], [2, с.186-207], [3, с.45-59].

2. Составьте план эксперимента для изучения работы предикатов ввода-вывода и предикатов работы со строками. В первом случае ваша задача - определить особенности работы каждого преди­ката, их ос­новные отличия. Кроме того, необходимо понять внелогическую приро­ду преди­катов ввода-вывода. Во втором случае, основываясь на логи­ческой природе предикатов работы со строками, рассмотреть все возможные цели, разрешаемые этими предикатами.

3. Выполнить индивидуальное задание.

4. Оформить отчет.

5. Защитить работу.

Содержание отчета

1. Описать результаты эксперимента по изучению работы встроенных предикатов.

2. Привести текст индивидуального задания.

3. Привести текст программы на Прологе, описывая декларативный смысл каждой проце­дуры.

4. Привести тесты и результаты работы программы.

Методические указания

В Прологе имеется ряд предикатов, находящихся за рамками модели логического програм­мирования. Они называются внелогическими предикатами. Такие предикаты в про­цессе решении логических целей порождают побочные эффекты. Существует три основных вида внелогических предикатов: предикаты, относящиеся к вводу-выводу, предикаты, обеспечиваю­щие доступ к программе и ее обработку, и предикаты для связи с внешней операционной системой. В данной лабораторной работе рассматриваются предикаты Пролога, связанные с вводом-выводом.

Любой практический язык программирования должен обеспечивать программиста средства ввода и вывода. Однако вычислительная модель Пролога не поддерживает операции ввода-вывода в виде чистых компонентов языка.

Турбо Пролог включает в себя несколько стандартных предикатов для ввода с клавиатуры. Из них пять основных: readln (для чтения строк символов целиком), readint readreal, readchar (для чтения целых, вещественных и символьных значений соответственно), readterm (для чтения составных объектов). Все эти предикаты могут быть переопределены для чтения из файлов.

Выполнение всех этих предикатов аналогично друг другу. Рассмотрим, например, предикат readln(X). Домен для переменной X должен быть типа строкового (string) или символьного (symbol) типа. Перед тем как вызвать readln(X), переменная X должна быть свободна. Во время работы Пролог-программы выполнение предиката readln приводит к тому, что на экран выводится запрос о вводе строки. После того, как строка введена и нажата клавиша <Enter>, введенное значение присваивается переменной X.

Основной предикат вывода - write(X). Решение этой цели приво­дит к записи значения переменной X, которое должно быть известно к моменту выполнения предиката, в текущий выходной поток, определяемый опера­ционной системой: по умолчанию это данные, выводимые на терминал.

Ни различные версии предикатов ввода, ни предикат write не дают альтернативных решений при возвра­те (предикаты являются детерминированными), т.е. каждое новое обращение к этим процедурам будет выполнять­ся с различными значениями X.

В дополнение к перечисленным ниже приведены наиболее распространен­ные предикаты ввода-вывода Турбо Пролога. Более подробную информацию об этих предикатах можно найти в [3, с. 45-60],[4]:

write(X₁, X₂ ,…, X_n) – бесформатный вывод;

writef(Format_string, X₁, X₂ ,…, X_n ) – форматированный вывод;

nl - переход на новую строку;

readdevice(symbolic_name_of_file) - переопределение текущего устройства ввода;

writedevice(symbolic_name_of_file) – переопределение текущего устройства вывода;

openread(symbolic_name_of_file, dos_file_name) – открывает файл для записи;

openappend(symbolic_name_of_file, dos_file_name) – открывает файл для записи в конец файла;

openmodify(symbolic_name_of_file, dos_file_name) – открывает файл для записи и чтения;

closefile(symbolic_name_of_file) – закрывает указанный файл;

eof(symbolic_name_of_file) – проверка конца файла;

existfile(dos_file_name) – проверяет наличие файла в каталоге на текущем дисководе;

Замечание к использованию предикатов:

dos_file_name оформляется как строка, в которой указывается путь доступа к файлу. Например: “c:\user\pm03\ex01.pro”;

Symbolic_name_of_file – символическое имя файла, которое должно начинаться с маленькой буквы и должно быть объявлено в описании домена file. Например, file = myfile; file 1;…; file n.

В любой программе разрешен только один домен file.

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

P : - read(X), P(X). P : - read(X), P(X).

P(X) : - end_of_file(X). или P(X) : - end_of_file(X).

P(X) : - write(X), P. P(X) : - write(X), nl, read(Y), ! , P(Y).

|______________________________|

|

на месте write может стоять любой предикат обработки терма X,

на месте read – любой из вышеперечисленных предикатов ввода

При выполнении индивидуальной работы необходимо использовать еще один класс предикатов. Это предикаты работы со строками.

В отличие от предикатов ввода-вывода, предикаты обработки строк полностью соответствуют логической модели Пролога. Каждый из предикатов может решать как прямые, так и обратные задачи. Как го­ворилось выше, ваша задача – исследовать возможные режимы работы каждого предиката в данной реализации Пролога.

Ниже перечисляются основные предикаты обработки строк, более подробно об этих предикатах можно прочесть, например, в [3,с.85-89], [4]:

frontchar (String1,Char,String2), где String = Char+String2;

fronttoken (String1, Token, Rest), где String1 – исходная строка, Token – первая лексема строки, Rest – остаток строки без первой лексемы, String1= Token+ Rest. /*Последовательность знаков является лексемой, если:

- это имя в соответствии с синтаксисом Пролога;

- это число (предшествующий ему знак является отдельной лек­семой);

- это отличный от пробела знак */;

frontstr (Number_of_char, Startstr, Endstr), где Number_of_char – количество первых букв, выделяемых из строки (String1), String1 – строка, Startstr - начало строки String1 длиною в Number_of_char, Endstr – остаток строки , таким образом Number_of_char = Startstr + Endstr ;

concat ( String1 , String2 , String3 ), String1 = String2 + String3 ;

str_len ( String , integer_length ) , String - строка., integer_length - длина строки .

Индивидуальные задания

1. Дан текстовый файл, разделенный на строки. Выравнивание строки заключается в том, что между ее отдельными словами дополни­тельно вносятся пробелы так, чтобы длина строки стала равной заданной длине (требуемая длина не меньше исходной), а последнее слово строки сдвинулось к ее правому краю. Напишите программу выравнивания строк данного текста.

2. Дан символьный файл F. Записать в файл 6 с сохранением порядка следования те символы файла F:

а) которым в этом файле предшествует буква "а";

б) вслед за которыми в этом файле идет буква "а".

3. Дан символьный файл F. Группы символов, разделенные пробе­лами (одним или несколькими) и не содержащие пробелов внутри себя, будем называть словами. Удалить из файла все однобуквенные слова лишние пробелы. Результат записать в файл G.

4. Дан символьный файл F. Найти самое длинное слово среди слов, вторая буква которых есть "е", если таких слов несколько, то найти последнее. Если таких слов нет вообще, то сообщить об этом. Решить эту задачу:

а) полагая, что слова состоят не более чем из 10 символов;

б) без ограничения на число символов в слове.

5. Дан символьный файл F. Предполагается, что длина одного слова не превосходит десяти и что число слов делится на 100. Под­готовить файл для печати слов в две колонки по пятьдесят строк на странице. Слова должны быть размещены в файле F1 в следующем по­рядке:

1-е слово, 51-е слово, 2-е слово, 52-е слово и т.д.

6. Дан символьный файл F, содержащий сведения о сотрудниках учреждения, записанные по следующему образцу:

фамилия имя отчест­во, фамилия имя отчество, ... .

Записать эти сведении в файле G, используя образцы:

а) имя отчество фамилии, имя отчество фамилия, ...;

б) фамилия и.о., фамилия и.о., ... .

7. Даны два символьных файла F1 и F2, Файл F1 содержит произ­вольный текст. Слова в тексте разделены пробелами и знаками препи­нания. Файл F2 содержит не более сорока слов, которые разделены запятыми. Эти слова образуют пары; каждое первое слово считается заменяемым, каждое второе заменяющим. Найти в файле F1 все заменяемые слова и заменить их на соответствующие заменяющие. Резуль­тат поместить в файл G.

8. Даны натуральное число К, символьный файл F и текстовый файл F1. Файл F содержит 30 слов, каждое из которых будем называть ключе­вым. Сформировать файл G, который содержит строки файла F1, цикли­чески сдвинутые так, чтобы каждое ключевое слово, входящее в стро­ку, начиналось с K-й позиции. Строки, не содержащие ключевых слов, в файл G не включаются. Строки, которые содержат n ключевых слов, записываются в файл G n раз.

9. Дан текстовый файл F. Переписать компоненты файла F в файл G, вставляя в начало каждой строки номер этой строки. Порядок ком­понент должен быть сохранен.

10. Даны текстовый файл F и строка S. Получить все строки файла F, содержащие в качестве фрагмента строку S.

11. Даны два текстовых файла f и g. Определить, совпадают ли компоненты файла f с компонентами файла g. Если нет, то получить номер первой строки и позицию первого символе в этой строке, в ко­торых файлы f и g отличаются между собой.

12. Дан текстовый файл, разделенный пробелами на слова.

а) найти все слова, содержащие наибольшее количество гласных латинских букв (a, e, i, o, u ).

б) Найти все слова, в которых доля букв а, b максимальна.

в) В тех словах, которые оканчиваются сочетанием букв ing, заменить это окончание на ed.

13. Для большинства существительных, оканчивающихся на -онок и -енок, множественное число образуется от другой основы. Как пра­вило, это происходит по образцу: цыпленок - цыплята, мышонок - мышата и т.д. (в новой основе перед последней буквой т пишется а или я в зависимости от предыдущей буквы: если это шипящая, то а, иначе - я). Имеются слова-исключения, из которых укажем следующие: ребе­нок (дети), бесенок (бесенята), опенок (опята), звонок (звонки), позвонок (позвонки), подонок (подонки), колонок (колонки), жаворо­нок (жаворонки), бочонок (бочонки). Есть еще несколько малоупотре­бительных слов-исключений, которые мы не рассматриваем. Дан текс­товый файл. Все существительные, встречающиеся в этом тексте с окончаниями -онок и -енок, заменить на множественное число.

Контрольные вопросы

1. Перечислите основные предикаты ввода-вывода. Почему эти предикаты называют внелогическими предикатами?

2. Приведите основную схему программы, работающей с файлами. Покажите, как эта схема реали­зована в Вашей программе.

3. Как осуществляется форматирование данных в Турбо-Прологе при вводе и выводе? Сравните с другими языками программирования

4. Перечислите основные предикаты обработки строк.

5. Рассмотрите логическую природу предикатов обработки строк. Какие ограничения накладывает реальная модель логического программирования, в частности Турбо-Пролога, на действия этих пре­дикатов?

7. Приведите примеры использования предикатов обработки строк в Вашей программе. Объяс­ните, как действуют эти предикаты в данном случае.

Список литературы

Основная

1. Стерлинг Л., Шапиро Э. Искусство программирования на языке Пролог.- М.: Мир, 1990.

2. Братко И. Программирование на языке Пролог для искусственного интеллекта. – М.: Мир, 1990.

3. Сырецкий Г.А. Информатика, Основы логического программиро­вания на PDC prolog: Учеб.пособие. - Новосибирск: НГТУ.- 1994. Ч.3.

4. Янсон А. Турбо-Пролог в сжатом изложении. - М: Мир, 1991.

5. Гаврилов А.В., Новицкая Ю.В. Основы программирования на Турбо Прологе: учеб. пособие Новосибирск: НГТУ. - 1993.

6. Метакидес Г. Нероуд А. Принципы логики и логического программирования. - М.: "Факториал", 1998.

Дополнительная

7. Логическое программирование / Пер. с англ. и фр.- М: Мир, 1988.

8. Клоксин У., Меллиш К. Программирование на Прологе. - М: Мир, 1987.

9. Хоггер К. Введение в логическое программирование М: Мир, 1988.

10. Доорс Дж. и др. Пролог - язык программирования будущего. -М.: Финансы и статистика, 1990.

11. Малиас Дж. Реляционный язык Пролог и его применение. - М.: Мир, 1990.

12. Ин Ц., Соломон Д. Использование Турбо-Пролога, - М.: Мир, 1993.