I Международный конкурс научно-исследовательских и творческих работ учащихся

Старт в науке

"ИСПОЛЬЗОВАНИЕ ЯЗЫКА ПРОГРАММИРОВАНИЯ «ПРОЛОГ» ПРИ РЕШЕНИИ ЗАДАЧ ГИА ПО ИНФОРМАТИКЕ "

• Авторы
• Файлы работы
• Наградные документы

Криворотов Д.А. 1

---

1МБОУ "УНГ"

Работа в формате PDF

188.1 KB

Автор работы награжден дипломом победителя III степени

Диплом школьника

Введение…………………………………………………………………………...3

I. Теоретическая часть…………………………………………………………….5

1.  

   1. Основы алгебры логики……………………………………………………5

   2. Логические задачи по информатике……………………………………...9

   3. Язык программирования «ПРОЛОГ»……………………………………10

II. Практическая часть…………………………………………………………...16

2.1 Решение заданий по информатике с использованием языка Пролог…………………………………………………………………………….16

Заключение…………………………………………………………….................21Литература……………………….........................................................................22

Введение

Подготовка к ГИА по информатике стала актуальной с введением экзамена по информатике по выбору при окончании основной школы и введением в некоторых ВУЗах, включая и гуманитарные, вступительных экзаменов по информатике. Чтобы успешно пройти эти испытания необходимо качественно подготовиться к экзамену.

Тема «Логика. Логические основы компьютера» – один из разделов, изучаемых в рамках учебной дисциплины «Информатика и ИКТ» на профильном уровне.

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

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

«Пролог» самый популярный язык логического программирования с многолетней историей развития, огромным сообществом и достаточным количеством качественной литературы.

Цель работы: изучить использование языка программирования «Пролог» при решении задач ГИА по информатике

Для достижения цели проекта были поставлены следующие задачи:

1.  
   1.  
      •  

        • проанализировать научно-методическую литературу, интернет-ресурсы по данной теме;

        • рассмотреть методику применения языков программирования при подготовке к экзамену по информатике;

        • изучить и применить язык программирования «Пролог» при решении логических задач;

Объект исследования: процесс решения логических задач на языке программирования «Пролог».

Предмет исследования:язык логического программирования «Пролог».при решении логических задач ГИА.

Практическая значимость работы состоит в:

• разработке методов решения логических задач ГИА на «Прологе»;

• применение полученных навыков программирования в разных областях науки.

Методы исследования^: сбор информации, анализ, сравнение, обобщение.

Глава 1: Теоретические основы решения логических задач ГИА по информатике

1.1. Основы алгебры логики

Логика - наука о способах и формах мышления, которая возникла в Древнем Китае и Индии. Основоположником формальной логики по праву считается Аристотель. Логика позволяет, отвлекаясь от содержательной стороны, строить формальные модели окружающего мира. Свойства, связи, и отношения объектов окружающего мира в сознании человека отражают законы логики. Мышление всегда осуществляется в следующих формах: понятие, высказывание и умозаключении. Алгебра высказываний позволяет определять истинность или ложность составных высказываний.

В алгебре высказываний простым высказываниям или суждениям соответствуют логические переменные. Истинному высказыванию соответствует значение логической переменной 1, а ложному — значение 0. Над высказываниями можно производить определенные логические операции, в результате которых получаются новые, составные высказывания.

Высказывание – это любое предложение, в отношении которого имеет смысл утверждение о его истинности или ложности. Высказывание может принимать только два значения – «истина» (обозначается «1») и «ложь» (обозначается «0»). При этом считается, что высказывание удовлетворяет закону исключенного третьего, т.е. каждое высказывание или истинно, или ложно и не может быть одновременно и истинным, и ложным.

В алгебре логики все высказывания обозначают буквами «A», «B», «C» и т.д. Содержание высказываний учитывается только при введении их буквенных обозначений, и в дальнейшем над ними можно производить любые действия, предусмотренные данной алгеброй. Причем если над исходными элементами алгебры выполнены некоторые разрешенные в алгебре логики операции, то результаты операций также будут элементами этой алгебры.

Логические выражения

Логические выражения могут быть простыми и сложными. Простое логическое выражение состоит из одного высказывания и не содержит логические операции. В простом логическом выражении возможно только два результата – или «истина», или «ложь».

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

Логические операции

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

1. Операция «НЕ» – логическое отрицание (инверсия)

Логическая операция «НЕ» применяется к одному аргументу, в качестве которого может и простое, и сложное логическое выражение.

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

Для операции отрицания приняты следующие условные обозначения: ¬А; Ā или not A. Результат операции отрицания определяется следующей таблицей истинности

или

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

Для операции дизъюнкции приняты следующие условные обозначения: А или B; A/B или A or B. При выполнении сложных логических преобразований для наглядности иногда используют обозначение A + B, где A и B – аргументы (исходные высказывания). Результат операции дизъюнкции определяется следующей таблицей истинности:

3. Операция «И» – логическое умножение (конъюнкция)

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

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

Для операции дизъюнкции приняты следующие условные обозначения: А и B; A ^ B; A & B или A and B. При выполнении сложных логических преобразований для наглядности иногда используют обозначение A · B, где A и B – аргументы (исходные высказывания). Результат операции дизъюнкции определяется следующей таблицей истинности:

4. Операция «ЕСЛИ-ТО» – логическое следование (импликация)

Операция импликации связывает два простых логических выражения, из которых первое является условием или предпосылкой, а второе – следствием или заключением.

Результат операции импликации ложен только тогда, когда предпосылка А истинна, а заключение В (следствие) ложно.

Для операции импликации приняты следующие условные обозначения: если А, то B; A влечёт B; ifAthenB; A ‹=› B или A → B. Результат операции импликации определяется следующей таблицей истинности:

5. Операция «А тогда и только тогда, когда В» (эквивалентность, равнозначность)

Операция импликации связывает два простых логических выражения, из которых первое является условием или предпосылкой, а второе – следствием или заключением.

Результат операции эквивалентности истинен только тогда, когда предпосылка А и В одновременно истинны или одновременно ложны.

Для операции эквивалентности приняты следующие условные обозначения: А ~ B или A ≡ B. Результат операции эквивалентности определяется следующей таблицей истинности:

1.  

   1. Логические задачи ГИА по информатике.

ОГЭ (ГИА) по информатике – это необязательный экзамен при окончании 9-го класса, может сдаваться по выбору самим учеником или может быть назначен всем ученикам на региональном уровне. При сдаче ОГЭ по информатике ученик заранее указывает, с каким программным обеспечением он знаком и на каком языке программирования он собирается выполнять часть С.

Время проведения экзамена: 150 минут (2,5 часа). Разрешённые материалы: для 1-й и 2-й частей не используются дополнительные материалы, для 3-й части – компьютер со знакомым ученику программным обеспечением.

Минимальный балл (соответствует тройке): 5.

Максимальный балл: 22.

Количество заданий: 20.

Примеры заданий по теме Основы логики:

1.  

   1. Язык программирования «ПРОЛОГ»

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

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

Основная идея Пролога как языка записи фактов, вопросов и правил заключается в том, что они записываются в форме предикатов математической логики. Все они интерпретируются ЭВМ строго в соответствии с законами математической логики и ничем более.

Основные конструкции языка Пролог - это факты, вопросы и правила. Все эти три конструкции записываются в форме предикатов и их комбинаций. Рассмотрим правила их записи на языке Пролог.

Факты - это конкретные сведения о ком-то либо о чем-то. Факты на языке Пролог записываются в форме предикатов с конкретными аргументами-значениями. Примеры записи фактов на Прологе:

папа (Вова, Лена); - Вова - папа Лены

любит (Лена, музыка); - Лена любит музыку

оценка (Лена, русский, 5); - У Лены 5 по русскому языку

Вопросы на Прологе - это запросы к совокупности данных или процедурам, хранящимся, в ЭВМ. Запись вопросов начинается со знака ?, за которым записывается предикат или группа предикатов, разделяемых запятыми. Примеры записи простых вопросов на языке Пролог:

? папа (х, Лена) - Кто папы Лены?

х = Вова

? мама (х, у) - Кто у кого - мама ?

НЕТ

? оценка (х, _ , 5) - Кто имеет оценки 5?

х = Лена

Здесь буквы х, у - обозначения переменных, а числа и слова - конкретные значения аргументов в соответствующих предикатах. Знак подчеркивания «_» представляет неопределенное значение, которое несущественно для ответа на вопросы.

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

? мама (х, у), мама (у, Оля) - Кто мама у мамы Оли?

х = Зина у = Люба

? мама (х, у), папа (у, Оля) - Кто мама у папы Оли?

НЕТ

Правила в Прологе - это правила логического вывода. Слева в правилах записывается следствие, а справа - предусловие. Предусловие может состоять из одного или нескольких предикатов, разделяемых запятыми. Примеры записи правил вывода на Прологе:

студент (х)  занятие (х, учеба); - Студент - тот, кто занят учебой;

нумизмат (х)  собирает (х, монеты); - Нумизмат - тот, кто собирает монеты.

Примеры вопросов на использование этих правил:

? студент (х) - Кто - студент?

х = Алеша

х = Лена

? нумизмат (у) - Кто - нумизмат?

у = Алеша

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

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

что им нравится;

что они коллекционируют;

чем они занимаются;

какие оценки они имеют.

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

нравится (, );

собирает (, );

занимается (, );

оценка (, , );

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

Пусть об Оле и Алеше известно следующее:

1. Оле нравится музыка. Она собирает фотографии любимых певцов. Занимается домоводством. Оля имеет 4 по русскому языку и 5 по алгебре.

2. Алеше нравится история, он собирает монеты, естественно, имеет 5 по истории, занимается в археологическом кружке.

Соответствующая база данных на языке Пролог:

нравится (Оля, музыка); - Оле нравится музыка

нравится (Алеша, история); - Алеше нравится история

собирает (Оля, фотографии); - Оля собирает фотографии

собирает (Алеша, монеты); - Алеша собирает монеты

собирает (Алеша, значки); - Алеша собирает значки

оценка (Оля, русский, 4); - Оля имеет 4 по русскому языку

занимается (Алеша, бизнес); - Алеша занимается бизнесом

оценка (Оля, алгебра, 5); - Оля имеет оценку 5 по алгебре

оценка (Алеша, история, 5); - Алеша имеет оценку 5 по истории

К составленной базе данных можно обращаться с самыми разными вопросами об интересах, занятиях, склонностях и успехах в учебе. Примеры самых простых вопросов и ответов, получаемых от ЭВМ:

? занимается (Алеша, футбол) - Занимается ли Алеша футболом?

нет

? нравится (Оля, музыка) - Нравится ли Оле музыка?

да

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

Например:

? нравится (х, у) - Кому что нравится?

х = Оля у = музыка

х = Алеша у = история

Если какая-то часть информации по той или иной причине не нужна, то вместо соответствующей переменной в вопросе ставится знак подчеркивания«_»:

? собирает (_, х) - Что собирают друзья?

х = фотографии

х = монеты

х = значки

Наконец, в вопросах можно одновременно использовать как переменные, так и конкретные значения. Например:

? занимается (х, музыка) - Кто занимается музыкой?

нет

? занимается (Алеша, у) - Чем занимается Алеша?

у = бизнес

? собирает (х, монеты) - Кто собирает монеты?

х = Алеша

? оценка (х, _ , 5) - Кто имеет пятерки?

х = Оля

х = Алеша

Примеры сложносоставных вопросов:

1. Кто занимается бизнесом и собирает монеты?

? занимается (х, бизнес), собирает (х, монеты)

х = Алеша

2. Какие оценки имеет тот, кто собирает монеты?

? собирает (х, монеты), оценка (х, р, z)

х = Алеша

р = история

z = 5

К составленной базе данных можно добавить следующие правила вывода:

книголюб (х)  нравится (х, книги), - Книголюб - тот, кто

собирает (х, книги) любит и собирает книги

бизнесмен (х)  собирает (х, монеты), - Бизнесмен - тот, кто

занятие (х, бизнес) собирает монеты и занимается бизнесом

Примеры использования правил-определений:

? книголюб (х) - Кто - книголюб?

НЕТ

? бизнесмен (у) - Кто - бизнесмен?

у = Алеша

II. Практическая часть

2.1 Решение заданий по информатике с использованием языка Пролог

Способности к описанию логических задач являются наиболее сильной стороной ПРОЛОГа.

Мы рассмотрели решение нескольких логических задач ГИА по теме: «Основы логики» разными способами.

Задача 1: (Х>3˅X