Генератор задач с комплексными числами для обучения и самоконтроля

Размещено на http://www.allbest.ru/

Федеральное агентство связи

Федеральное государственное бюджетное образовательное учреждение высшего образования

«Поволжский государственный университет телекоммуникаций и информатики»

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

Направление (специальность) Информатика и вычислительная техника

Кафедра Теоретических основ радиотехники и связи

Выпускная квалификационная работа (бакалаврская работа)

Генератор задач с комплексными числами для обучения и самоконтроля

Руководитель доцент к.т.н., доцент Ю.В. Алышев

Н. контролер доцент к.т.н. Д.В. Суханов

Разработал ПО-32 Д.А. Темников

Самара 2017

Введение

Впервые мнимые величины были упомянуты в трудах Кардано в 1545 году. Позже, в 1572 году, итальянский математик Бомбелли нашел возможность использования этих величин при решении кубического уравнения, а также описал правила сложения, вычитания, умножения и деления. Задача, выражающая корень степени n из мнимого числа, была решена в работах Муавра (1707 г.) и Котса (1772 г.). В 1799 году Гаусс доказал алгебраическую замкнутость данных чисел, а позже ввел термин «комплексное число».

Арифметическая (стандартная) модель комплексных чисел представлена как пара вещественных чисел и имеет вид: a + bi, где a и b вещественные числа, i - мнимая единица (величина, для которой справедливо равенство i2 = -1).

В настоящее время комплексные числа (далее КЧ) используются не только в математике, а также в физике и химии. Их применяют в авиационной, космической и компьютерной индустрии. Используют в решении дифференциальных уравнений, в преобразовании Фурье, в электродинамике, в механике сплошных сред, в квантовой механике, в теории электрических цепей и во многих других областях. Не трудно заметить на сколько велика роль КЧ в современном мире. Следовательно, важно уметь правильно работать с ними.

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

Данная тема особенно актуальна при изучении таких дисциплин как «Теория электрических цепей» и «Основы теории связи». В этих дисциплинах решаются очень много задач с КЧ, поэтому проблема, связанная с отсутствием умения правильной работы с КЧ имеет особенный характер. Стоит отметить что данные дисциплины изучаются в нашем университете на кафедре «ТОРС».

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

Так же актуальность данной темы состоит в отсутствии на данный момент программного обеспечения (далее ПО), которое генерирует, решает и проверят задачи с КЧ.

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

1.1 Язык программирования

Java - это строго типизированный объектно-ориентированный язык программирования, который был разработан компанией Sun Microsystems. Дата официального выпуска - 23 мая 1995 года.

Программы на Java транслируются в байт-код Java, который выполняется виртуальной машиной Java (JVM) - программой, обрабатывающей байтовый код и передающей инструкции оборудованию как интерпретатор.

Благодаря данному способу выполнения программ байт-код является полностью независимым от операционной системы и оборудования, то есть является кроссплатформенным. Так же достоинством языка является гибкая система безопасности. Любые операции, которые превышают установленные полномочия программы (например, попытка несанкционированного доступа к данным или соединения с другим компьютером), вызывают немедленное прерывание.

К недостаткам относят относительно низкую производительность (в сравнении с языками более низкого уровня, такими как C/C++) и необходимость предустановленной виртуальной машины.

Язык Java благодаря своим особенностям и специальным средствам дает большие возможности разработчику для достижения поставленных целей. Программист концентрируется только на алгоритмах задачи и не отвлекается на написание кода связанного с архитектурой ЭВМ.

Основные возможности языка:

· автоматическое управление памятью;

· расширенные возможности обработки исключительных ситуаций;

· богатый набор средств фильтрации ввода-вывода;

· набор стандартных коллекций: массив, список, стек и т. п.;

· наличие простых средств создания сетевых приложений (в том числе с использованием протокола RMI);

· наличие классов, позволяющих выполнять HTTP-запросы и обрабатывать ответы;

· встроенные в язык средства создания многопоточных приложений, которые потом были портированы на многие языки (например, Python);

· унифицированный доступ к базам данных:

· на уровне отдельных SQL-запросов -- на основе JDBC, SQLJ;

· на уровне концепции объектов, обладающих способностью к хранению в базе данных -- на основе Java Data Objects (англ.) и Java Persistence API;

· поддержка обобщений (начиная с версии 1.5);

· поддержка лямбд, замыканий, встроенные возможности функционального программирования (с 1.8);

· множество вариантов реализации многопоточных программ.

Подробнее все тонкости языка Java описаны в одной из книг компьютерной литературы - «Философия Java» [1].

1.2 Фреймворк Spring, Spring MVC

Spring Framework (Spring) - универсальный фреймворк с открытым исходным кодом для Java-платформы. Автором данного фреймворка является Род Джонсон, написавший его в 2002 году. Spring представляет большие возможности для Java-разработчиков в проектировании, он содержит ряд хорошо документированных и легких в использовании средств решения проблем, которые возникают при создании приложений корпоративного масштаба. Стоит отметить, что особенности ядра фреймворка применимы в любом Java-приложении, и существует множество расширений и усовершенствований для построения web-приложений. Подробно фреймворк описан в книге «Spring 4 для профессионалов» [2].

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

Сервлет - это интерфейс Java, который расширяет функциональные возможности сервера (как правило web-сервера). Взаимодействие клиентов и сервлета осуществляется по принципу запрос-ответ.

MVC (Model-View-Controller) - это схема разделения данных приложения, пользовательского интерфейса и управляющей логики на три отдельных компонента: модель, представление и контролер. Благодаря данному разделению возможно независимое изменение компонентов.

Основные функции компонентов:

· Model (Модель) - предоставление данных, реакция на команды контроллера, изменение своего состояния;

· View (Представление) - отображение данных в зависимости от изменения модели;

· Controller (Контроллер) - обрабатывает действия пользователя, оповещая модель о необходимости изменений.

Рис. 1.1 - Изображение архитектурной концепции MVC

Основным контроллером Spring MVC является класс DispatcherServlet, который отвечает за делегирование управления различными интерфейсами, на всех этапах выполнения HTTP-запроса.

Spring MVC обладает следующими особенностями:

· Ясное и понятное представление концепции MVC;

· Каждый интерфейс отвечает только за свою часть работы;

· Любой интерфейс может быть заменен на альтернативный;

· Тесная связь интерфейсов с Servlet API;

· Высокий уровень абстракции для web-приложений.

1.3 Web-технологии

Для создания графического интерфейса были применены такие web-технологии как HTML, CSS, JavaScript, jQuery.

HTML - стандартизированный, теговый язык разметки web-страниц. Данная разметка интерпретируется браузерами, после чего полученный форматированный текст отображается на устройстве пользователя. HTML-документы, как правило, передаются от сервера к браузеру по протоколам HTTP в виде простого текста, или по протоколам HTTPS с использованием шифрования.

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

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

В web-документ язык может быть встроен: внутри документа, внутри тега или вынесен в отдельный файл. В web-приложениях JavaScript используется в клиентской части приложения (в качестве клиента выступает браузер, в качестве сервера web-сервер).

jQuery - библиотека JavaScript, направленная на взаимодействие JavaScript и HTML. Благодаря данной библиотеке разработчик может легко получить доступ к любому элементу web-документа, обращаться к атрибутам и содержимому элементов, а также манипулировать ими. Стоит отметить, что jQuery предоставляет API удобный для работы с AJAX. Встраивается в web-документ аналогично JavaScript. Таким образом jQuery имеет полезную функциональность для широкого круга задач, что в свою очередь упрощает работу web-разработчика при «оживлении» web-страницы.

Для овладения web-инструментами были изучены следующие книги: «HTML5, CSS3 и JavaScript. Исчерпывающее руководство» [3], «JavaScript и jQuery. Исчерпывающее руководство» [4].

1.4 Web-фреймворк Bootstrap

Bootstrap - это интерфейсный web-фреймворк, который включает в себе HTML и CSS шаблоны для различных компонентов web-интерфейса (оформление типографики, web-формы, кнопки, метки, блоки навигации и т.д.), а также JavaScript расширения. Одной из особенностей фреймворка является возможность создания адаптивного дизайна (дизайн web-страниц, динамически подстраивающийся под заданные размеры окна браузера).

Bootstrap изначально разрабатывался как внутренняя библиотека компании Twitter и назывался “Twitter Blueprint”. Спустя несколько месяцев (в августе 2011 года) разработки фреймворк вышел в свет под названием Bootstrap. С тех пор выпущено три стабильные версии и на данный момент ведется работа над четвертой.

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

Bootstrap поддерживается большинством современных браузеров.

Список поддерживаемых браузеров приведен ниже.

Рис. 1.2 - Поддержка браузеров фреймворком Bootstrap

1.5 Интегрированная среда разработки IntelliJ IDEA

IntelliJ IDEA - интегрированная среда разработки ПО, разработанная компанией JetBrains и выпущена в 2001 году. Данная среда разработки поддерживает достаточно большое количество языков, среди них Java, Python, PHP, JavaScript, HTML, CSS, Ruby, C, C++ и многие другие.

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

В настоящее время IntelliJ IDEA может похвастаться умным автодополнением, инструментами для анализа качества кода, удобной навигацией, расширенным рефакторингом и форматированием кода для многих языков. Имеется поддержка всех популярных фреймворков и платформ, которые с лёгкостью подключаются к проекту. Есть интеграция с серверами приложений, с автоматизированными инструментами сборки и управления проектом, с системами управления версиями. Это лишь часть возможностей данной среды. IntelliJ IDEA выпускается в двух версиях: Ultimate - платная версия включающая все возможности среды и Community Edition - бесплатная версия включающая только необходимые инструменты.

Для создания ПО, реализуемого в рамках данной темы, необходима полная версия среды, так как будет использоваться фреймворк Spring Framework и сервер Tomcat.

1.6 Web-сервер Apache Tomcat

Apache Tomcat (в старых версиях имел имя Catalina) - написанный на Java сервер, который предоставляет поддержку сервлетов и обеспечивает их жизненный цикл. Tomcat разрабатывается фондом Apache Software Foundation и реализует спецификации сервлетов, JSP (JavaServer Pages) и JSF (JavaServer Faces).

Tomcat может использоваться как самостоятельный web-сервер, так и в сочетании с web-сервером Apache HTTP Server в качестве контент-сервера или же в сочетании с серверами приложений JBoss и GlassFish в качестве контейнера сервлетов.

1.7 Автоматизированный сборщик проектов Apache Maven

Apache Maven - автоматизированный сборщик проектов написанных на Java, C#, Ruby, Scala и других языков. Проект Maven разрабатывается фондом Apache Software Foundation c 2003 года.

Под сборкой Java проекта подразумевается: компиляция, создания jar архива и дистрибутива программы, генерация документации. Простой проект можно собрать в командной строке, однако для сложных проектов команды для сборки будут очень длинными. Конечно можно создать командный файл, но он будет зависимым от операционной системы. Для решения данной проблемы были придуманы специальные инструменты для сборки проекта, которые позволяли избавиться от платформенной зависимости и упростить написание команд сборки. Одним из таких инструментов является Maven.

Maven обеспечивает автоматизированную сборку за счет описания на языке POM (является подмножеством XML) структуры проекта. Данное описание содержится в XML-файле pom.xml. При запуске Maven проверяет синтаксис конфигурационного файла и наличие всех необходимых данных в нём. Основными преимуществами Maven являются:

· Независимость от операционной системы;

· Управление зависимостями (Maven предотвращает конфликты версий при использовании сторонних библиотек (зависимостей));

· Возможность собрать проект из командной строки;

· Декларативное описание проекта;

· Интеграция с различными средами разработки.

1.8 Система управления версиями Git

Git - распределенная система управления версиями (или система контроля версий). Проект изначально разрабатывался для управления разработкой ядра Linux. Git используют такие проекты как: Ядро Linux, Swift, Android, Drupal, jQuery, PHP.

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

СУВ могут быть трех видов:

· Локальные (все версии хранятся на локальном устройстве);

· Централизованные (версии хранятся на центральном сервере, пользователи выгружают лишь последнюю версию файла);

· Распределенные.

Git является распределённой системой управления версиями, это значит, что на всех устройствах хранятся полные копии всех данных. Это позволяет обезопасить данные в случае выхода из строя центрального сервера. Кроме того, это позволяет одновременно вести несколько разных рабочих процессов в одном проекте.

Git имеет ряд преимуществ:

· Высокая производительность;

· Средства интеграции с другими СУВ;

· Продуманная и удобная система команд;

· Интеграция со многими средами разработки;

· Наличие различных графических интерфейсов.

Для изучения особенностей работы данной СУВ была изучена книга «Git для профессионального программиста» [5].

2. Описание задач и требований к ПО

2.1 Главная задача

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

2.2 Архитектура ПО

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

2.3 Генерация задачи

ПО должно генерировать задачи, которые будут состоять из выражения с КЧ. Следовательно, необходимо реализовать два генератора: первый будет генерировать КЧ, второй выражения. Оба генератора должны обладать гибкой настройкой. Генератор КЧ должен генерировать числа в двух формах: алгебраической и показательной. Также генератор КЧ должен выдавать легкие для вычисления числа, так как нашей задачей является обучение операциям над КЧ. В сгенерированных выражениях должны отсутствовать способы явного решения, то есть возможность сократить часть задачи.

2.4 Вычисляющий механизм

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

Для того, чтобы по действиям вычислить выражение нужно реализовать алгоритм «Обратной польской записи», а для выполнения операций над КЧ нужно реализовать специальные методы вычисления. При вычислении необходимо следить за формой КЧ, так как для каждой формы применяется свой метод. Также должны быть реализованы механизмы конвертирования форм КЧ. Это потребуется для вычисления операций, в которых вычисление в данной форме невозможно.

генерация вычислительный цепочка множитель

2.5 Графическое отображение выражений и КЧ

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

Рис. 2.1 - Пример отображения свёрстанного документа в TeX

TeX - это система компьютерной верстки применяющаяся для компьютерной типографии. Однако отличительной способностью TeX является удобство набора сложных математических формул.

Благодаря данной верстке выражения будут иметь такой же вид, как и в учебной литературе. На практике обычно используют макропакет системы TeX - LaTeX.

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

В качестве обучающего материала для данной верстки была изучена книга «Набор и верстка в пакете LATEX» [6].

Документы TeX набираются на собственном языке разметки, поэтому необходимо реализовать конвертер для преобразования выражения к данной разметке. Язык Java не имеет собственных решений для работы с TeX. Поэтому необходимо найти и подключить стороннюю библиотеку. Такой библиотекой является jLatexMath. Она независима от операционной системы, не нуждается в дополнительных библиотеках для промежуточного преобразования в отличие от других подобных библиотек. А также имеет хорошую документацию и возможность настройки выходного изображения.

2.6 Графический интерфейс

Основными требованиями к графическому интерфейсу (далее ГИ) являются совместимость со всеми современными браузерами и создание комфортного использования ПО. Так как архитектурой ПО является web-приложение, то для создания ГИ необходимо использовать web-инструменты, основные из которых HTML, CSS, JavaScript. Для ускорения работы будут задействованы фреймворки Bootstrap и jQuery. Комфортность при использовании ГИ обеспечит технология AJAX. Благодаря данной технологии для обучающегося все действия будут происходить в рамках одной страницы. Также будет использовано применение адаптивного дизайна. «На рис. 2.2 изображен макет будущего интерфейса».

Рис. 2.2 - Макет будущего интерфейса

2.7 Подробное решение

Для создания подробного решения необходимо реализовать алгоритм хранения данных о действиях и интегрировать его в вычисляющий механизм. Затем с помощью ГИ вывести данные подробного решения. При выводе необходимо настроить возможность вывода краткого или полного решения. Формулы решения будут выводиться при помощи механизма графического отображения выражений.

2.8 Проверка введенного ответа

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

3. Генерация случайных выражений. Теория

3.1 Возможные алгоритмы генерации выражений

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

3.1.1 Генерация выражений с заранее заданным результатом

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

Рассмотрим данный алгоритм на примере генерации выражения с результатом 30:

1) Сгенерируем случайный операнд и операцию. Пусть число будет 10, а операция сложение

2) Так как операция сложение, то вторым операндом является результат разности:

3) На выходе получается выражение из двух операндов и операции:

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

Краткий пример с тем же результатом выражения и тремя действиями:

1) Разложим 30:

2) Разложим 20:

3) Разложим 4:

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

Плюсы алгоритма:

· Вычисление результата выражения на стадии генерирования;

· Возможность самому задать результат выражения, что увеличивает гибкость генератора.

Минусы алгоритма:

· Данный алгоритм не позволяет контролировать количество КЧ в выражении. Это уменьшает не только гибкость генератора, но и делает вывод выражений громоздким.

· Невозможно контролировать значения КЧ, что приведет к неудобным для расчета значениям КЧ, а также уменьшит гибкость генератора.

· Излишнее количество скобок в выражении.

Последние два пункта в минусах алгоритма возможно нейтрализовать путем усовершенствования алгоритма. Для этого необходимо будет перебирать КЧ и операции, пока сгенерированная пара КЧ не будет удовлетворять настройкам генератора. Также придется анализировать необходимость расстановок скобок. Но тогда к минусам алгоритма добавится излишняя сложность и низкая производительность, связанная с усложнением алгоритма.

3.1.2 Последовательная генерация случайного выражения

Алгоритм последовательной генерации случайного выражения отличается простотой своей реализации. Сначала генерируется операнд, затем действие. Основным ограничением при генерации является количество действий. Сначала генерируется случайное число, затем (если требуется) действие.

Рассмотрим пример генерации выражения с тремя действиями:

1) Генерируем пару [5, +];

2) Генерируем пару [3, *];

3) Генерируем пару [2, -];

4) Так как три действия сгенерированы, завершаем выражение генерацией случайного числа [1];

5) Объединяем получившиеся значения в единую строку:

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

Плюсы алгоритма:

· Простой в реализации;

· Алгоритм позволяет повторно использовать уже существующие КЧ, следовательно, возможно контролировать количество КЧ;

· Также алгоритм позволяет легко контролировать значения КЧ;

· Более быстрая генерация выражения.

Минусы алгоритма:

· Нельзя задать заранее результат выражения;

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

3.2 Выбор алгоритма генерации выражения

Так как основным критерием при выборе генератора выражения является гибкость настройки генерации, то выбор падает на алгоритм последовательной генерации. Он не только позволяет увеличить возможности настройки генератора, но и является более легким в реализации. Также благодаря возможности использовать повторно КЧ становится возможным сделать вывод задачи более компактным и легким для восприятия.

3.3 Проблема сокращения переменных в выражении

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

Рассмотрим выражение имеющее данную проблему:

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

Для решения данной проблемы необходимо ввести два термина: множитель и слагаемое.

Множитель - это обычное число, КЧ, переменная, функция или выражение заключенное в скобки.

Слагаемое - это цепочка из одного и более множителя, которые связанны между собой операциями умножения или деления.

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

Из случайного количества множителей (верхний предел количества ограничен количеством действий и количеством уникальных множителей) генерируется слагаемое. Главное правило при генерации слагаемого - все его составляющие (множители) не должны повторяться. В свою очередь из случайного количества слагаемых (также верхний предел количества ограничен количеством действий и количеством уникальных слагаемых) генерируется еще одна цепочка, которая является выражением. В выражении также все составляющие не должны повторяться. Из-за отсутствия повторений в цепочках выражение лишено случаев, в которых возможно явное сокращение.

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

Рассмотрим пример с двумя переменными:

1) Генерируем слагаемое из случайного количество множителей без повторений (2):

[Z1, Z2]

2) Добавляем слагаемое в цепочку выражения, так как это первый элемент в цепочке, то его мы не проверяем:

[[Z1, Z2]]

3) Генерируем слагаемое из случайного количество множителей без повторений (1):

[Z1]

4) Добавляем слагаемое в цепочку выражения, так как такой элемент еще не встречался:

[[Z1, Z2], [Z1]]

5) Генерируем слагаемое из случайного количество множителей без повторений (1): [Z2]

6) Добавляем слагаемое в цепочку выражения, так как такой элемент еще не встречался: [[Z1, Z2], [Z1], [Z2]]

7) Генерируем слагаемое из случайного количество множителей (1): [Z2]

8) Так как такой элемент уже есть, то мы его не добавляем.

Не трудно заметить, что больше нельзя добавить действие в выражение.

Теперь необходимо расставить в цепочках знаки операций:

1) Случайным образом расставляем знаки операций умножения или деления между множителями. Этого требует только одно слагаемое: Z1 * Z2

2) Случайным образом расставляем знаки операций сложения или вычитания между слагаемыми: Z1 * Z2 + Z1 - Z2

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

3.4 Генерация псевдослучайных чисел

Основным инструментом при генерации задач является генератор псевдослучайных чисел (далее ГПСЧ). Сгенерированные таким генератором числа являются псевдослучайными, то есть данные числа почти не зависимы друг от друга и подчиняются заданному распределению.

ГПСЧ необходим для генерации значений и знака КЧ, выбора операций и переменных в выражении. Язык Java имеет собственный ГПСЧ, который полностью подходит для решения данных задач.

4. Вычисление результата выражения. Теория

4.1 Преобразование выражения в обратную польскую запись

Перед вычислением результата выражение необходимо преобразовать из инфиксной записи в обратную польскую запись (далее ОПЗ).

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

Для преобразования выражения в ОПЗ можно использовать два наиболее известных алгоритма - с использованием стека или с помощью рекурсивного спуска.

4.1.1 Преобразование выражения в ОПЗ с использованием стека

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

Алгоритм:

· Пока есть элементы для чтения:

o Читаем очередной элемент.

o Если элемент число (или переменная), то добавляем его к выходной строке.

o Если символ функции, то добавляем в стек

o Если открывающаяся скобка, то добавляем в стек

o Если закрывающаяся скобка, то: выталкиваем элемент из стека в выходную строку, пока не встретится открывающаяся скобка. Открывающаяся скобка просто удаляется из стека, без добавления в выходную строку. Если стек закончился, а открывающийся скобки не обнаружено, значит неверно расставлены скобки.

o Если оператор O1, то:

§ Выталкиваем из стека верхний элемент в выходную строку пока приоритет O1 меньше (если O1 право-ассоциированный) или меньше либо равен (если O1 ассоциированный, либо лево-ассоциированный) приоритету оператора находящегося на вершине стека.

§ Помещаем оператор O1 в стек.

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

Приоритеты операций:

§ ^ - высокий (4);

§ */ - средний (3);

§ +- - низкий (2);

§ () - самый низкий (1).

Пример:

Вход: a + (b - c) * d

1)

Читаем: a

Добавляем 'a' к выходной строке.

Выход: a

2)

Читаем: +

Добавляем '+' в стек.

Выход: a

Стек: +

3)

Читаем: (

Добавляем '(' в стек.

Выход: a

Стек: + (

4)

Читаем: b

Добавляем 'b' к выходной строке.

Выход: a b

Стек: + (

5)

Читаем: -

Добавляем '-' в стек

Выход: a b

Стек: + ( -

6)

Читаем: c

Добавляем 'c' к выходной строке.

Выход: a b c.

Стек: + ( -

7)

Читаем: )

Выталкиваем из стека все элементы до '(', '(' удаляем из стека.

Выход: a b c -.

Стек: +.

8)

Читаем: *.

Добавляем '*' в стек.

Выход: a b c -

Стек: + *

9)

Читаем: d

Добавляем 'd' к выходной строке.

Выход: a b c - d

Стек: + *

10)

Конец выходной строки.

Переносим элементы из стека в выходную строку.

Выход: a b c - d * +.

4.1.2 Преобразование выражения в ОПЗ методом рекурсивного спуска

В основе реализации данного алгоритма несколько функций которые вызывают друг друга. Сначала запускается стартовая функция begin(), которая обрабатывает операции сложения и вычитания. Затем begin() вызывает функцию multAndDiv(), обрабатывающую операции умножения и деления, и ждет пока ей передастся управление. В свою очередь multAndDiv() вызывает функцию symbol(), обрабатывающую числа (или переменные) и скобки. Если symbol(), встречает открывающуюся скобку то она вызывает begin() (получается рекурсия).

Пример:

Вход: a + (b - c) * d

1)

Читаем элемент, вызывая последовательно функции.

begin()1->multAndDiv()1->symbol()1

Добавляем к выходу, так как элемент переменная.

Выход: a

2)

Читаем элемент, вызывая последовательно функции.

begin()1->multAndDiv()1->symbol()1

Добавляем в память begin()1, так как операция сложение.

Выход: a

Память: begin()1: +

3)

Читаем элемент, вызывая последовательно функции.

begin()1->multAndDiv()1->symbol()1

Вызываем begin()2, так как открывающаяся скобка.

4)

Читаем элемент, вызывая последовательно функции.

begin()2->multAndDiv()2->symbol()2

Добавляем к выходу, так как элемент переменная.

Выход: a b

5)

Читаем элемент, вызывая последовательно функции.

begin()2->multAndDiv()2->symbol()2

Добавляем в память begin()2, так как операция вычитание.

Память: begin()2: -

6)

Читаем элемент, вызывая последовательно функции.

begin()2->multAndDiv()2->symbol()2

Добавляем к выходу, так как элемент переменная.

Выход: a b c

7)

Читаем элемент, вызывая последовательно функции.

begin()2->multAndDiv()2->symbol()2

Добавляем элементы из памяти begin()2 к выходу, так как встретили закрывающуюся скобку.

Выход: a b c -

8)

Читаем элемент, вызывая последовательно функции.

begin()1->multAndDiv()1->symbol()1

Добавляем в память multAndDiv()1, так как операция умножение.

Выход: a b c -

Память: begin()1: + ; multAndDiv()1 *

9)

Читаем элемент, вызывая последовательно функции.

begin()1->multAndDiv()1->symbol()1

Добавляем к выходу, так как элемент переменная.

Выход: a b c - d

10)

Так как достигнут конец входной строки, то добавляем элементы из памяти к выходу.

begin()1->multAndDiv()1

Выход: a b c - d *

begin()1

Выход: a b c - d * +

4.2 Выбор алгоритма преобразования выражения в ОПЗ

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

4.3 Вычисление результата выражения в ОПЗ

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

Алгоритм:

1) Читаем входной символ

· Если это операнд, то помещаем на вершину стека

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

2) Если не достигли конца входной строки, переходим к пункту 1.

3) Если конец строки, то результат выражения находится на вершине стека.

Пример:

Инфиксная запись: 5 * (3 + 2) - 8 = 5 * 5 - 8 = 17

Вход: 5 3 2 + * 8 -

1)

Читаем входной символ 5

Помещаем 5 стек

Стек: 5

2)

Читаем входной символ 3

Помещаем 3 стек

Стек: 5 3

3)

Читаем входной символ 2

Помещаем 2 стек

Стек: 5 3 2

4)

Читаем входной символ +

Вытаскиваем два операнда из вершины стека (3 2)

Выполняем операцию сложения и записываем результат в стек

Стек: 5 5

5)

Читаем входной символ *

Вытаскиваем два операнда из вершины стека (5 5)

Выполняем операцию умножения и записываем результат в стек

Стек: 25

6)

Читаем входной символ 8

Помещаем 8 стек

Стек: 25 8

7)

Читаем входной символ -

Вытаскиваем два операнда из вершины стека (25 8)

Выполняем операцию вычитания и записываем результат в стек

Стек: 17

Результат: 17

При вычислении результата выражения необходимо выполнять операции над КЧ. Так как в языке программирования Java нет стандартных средств для работы с КЧ, то их придется реализовать.

5. Описание устройства и работы генератора

5.1 Общее описание генератора

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

На выходе генератор КЧ возвращает список сгенерированных объектов класса Complex (класс, описывающий КЧ), а генератор выражений возвращает выражение в инфиксной записи в виде строки. Программный код генератора задач представлен в «Приложении А».

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

5.2 Генерация комплексных чисел

Генерация КЧ это отдельный процесс, имеющий следующие входные параметры:

· Количество переменных;

· Максимальное значение (по модулю) чисел R, Re и Im;

· Форма представления генерируемых КЧ.

Для каждой формы КЧ (алгебраической или показательной) применяется свой алгоритм генерации. Для генерации КЧ в алгебраической форме необходимо, чтобы хотя бы одна из составляющих была отлична от нуля. Если обе составляющие КЧ будут равны нулю, то операции с этим числом можно будет пропустить или вовсе произойдет деление на нуль. Для показательной формы необходимо, чтобы модуль числа был отличен от нуля, а аргумент не превосходил по модулю 2? или был равен 0.

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

Подробнее можно рассмотреть алгоритм генерации КЧ на рисунке 5.1 и 5.2.

Рис. 5.1 - реализация генерации КЧ в алгебраической форме

На рисунке 5.1 видно, что значение действительной и мнимой части ограничено значением переменной maximumValuePart.

Рис. 5.2 - реализация генерации КЧ в показательной форме

Из реализации алгоритма видно (строки 46, 48, 61, 63), что каждая составляющая КЧ может стать с вероятностью 0.5 отрицательной. На строке 56 (рисунок 5.2) происходит подбор аргумента ?.

5.3 Генерация выражений

5.3.1 Общее описание генератора выражений

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

Входные параметры генератора выражений:

· Список переменных, которые можно использовать для генерации;

· Количество действий;

· Список операций, которые можно использовать для генерации;

· Максимальная степень, в которую можно возвести переменную или выражение.

Генератор выражений имеет два основных метода - генерация цепочки слагаемых и генерация цепочки множителей.

5.3.2 Генерация цепочки множителей

Рассмотрим подробный алгоритм генерации цепочки множителей на рисунке 5.3.

N - количество действий которое можно сгенерировать.

K - количество сгенерированных действий.

1 - Проверка, запрещены ли операции умножения или деления. В случае, если данные операции запрещены, то метод вернет лишь один множитель, которым является просто переменная или переменная в степени.

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

3 - Получаем случайный множитель, в данном случае переменную.

4 - Получаем случайную операцию, если это операция возведения в степень, то возводим множитель в степень.

5 - Возводим множитель в степень.

6 - Так как произошло возведение в степень, то количество сгенерированных действий равно одному.

7 - Получаем случайный множитель, в данном случае переменную.

8 - Так как в степень множитель не был возведен, то количество сгенерированных действий равно 0.

9 - Если количество разрешенных действий не меньше количества переменных, то верхним пределом количества сгенерированных операций будет количество переменных минус один (так как действий в выражении на 1 меньше чем операндов). Иначе верхним пределом является количество разрешенных операций.

10 - Количеству сгенерированных действий присваиваем случайное число от 0 до количества переменных минус один. То есть определяем сколько будет сгенерировано действий в цепочке.

11 - Количеству сгенерированных действий присваиваем случайное число от 0 до количества действий, которые можно сгенерировать. То есть определяем сколько будет сгенерировано действий в цепочке.

12 - Если во входном параметре сообщилось, что необходимо сгенерировать строгое количество действий, то присваиваем K значение N.

13 - Присваиваем количеству сгенерированных действий значение N.

14 - Цикл итераций, в теле которого генерируется цепочка.

15 - Получаем случайную переменную из списка, которая будет являться множителем.

16 - Цикл, в теле которого генерируется множитель, которого до этого еще не было.

17 - Если был сгенерирован множитель, которого еще не было или превышен лимит попыток, то выходим из цикла. Лимит попыток может быть превышен в случае, если нельзя добавить уникальный множитель. Это означает, что необходимо принудительно добавить множитель.

18 - Если выход из цикла не произошел, пытаемся получить снова случайный множитель.

19 - Если есть свободные действия (есть количество сгенерированных действий меньше количества разрешенных действий), то можно попытаться возвести в степень.

20 - Получаем случайную операцию, если это операция возведения в степень, то возводим множитель в степень.

21 - Возведение множителя в степень.

22 - Добавляем множитель в список (в цепочку).

23 - Увеличение счетчика итераций на количество сгенерированных действий на данной итерации (на 1 если был сгенерирован просто множитель, на 2 если сгенерированный множитель был возведен в степень).

24 - Расстановка операций умножения или деления между множителями. Если какая-то из двух операций запрещена, то выставляем только одну.

На выходе получается строка из множителей в инфиксной записи.



Рис. 5.3 - алгоритм генерации цепочки множителей

5.3.3 Генерация цепочки слагаемых

Алгоритм генерации цепочек, слагаемых представлен на рисунке 5.4

N - количество действий которое нужно сгенерировать.

M - количество переменных.

K - количество действий в сгенерированной цепочке множителей.

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

2 - Получаем случайную операцию, если это операция возведения в степень, то возводим цепочку множителей в степень.

3 - Генерируем цепочку множителей из N действий (сообщаем генератору множителей, что нужно сгенерировать строгое количество действий).

4 - Генерируем цепочку множителей из N - 1 действий (так как одно действие потрачено на возведение в степень). Также строгое количество действий.

5 - Возводим цепочку множителей в степень.

6 - Цикл до тех пор, пока не сгенерированы все действия.

7 - Проверка, если количество действий, которое нужно сгенерировать больше количества переменных, то верхним пределом длины (количества действий) цепочки множителей будет количество переменных. Иначе верхним пределом будет количество действий.

8 - Генерируем цепочку множителей не превышающей N действий.

9 - Генерируем цепочку множителей не превышающей M действий.

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

11 - Добавляем цепочку множителей (слагаемое) в список.

12 - Так как сгенерированы не все операции, то мы можем попытаться возвести полученную цепочку в степень. Если сгенерирована операция возведения в степень, то возводим в степень цепочку множителей.

13 - Возводим в степень слагаемое.

14 - Если получившейся цепочки нет в списке или число попыток превысило лимит, то добавляем цепочку в список (из которого состоит цепочка слагаемых). Лимит попыток может быть превышен в случае, если нельзя добавить уникальное слагаемое. Это означает, что необходимо принудительно добавить слагаемое.

15 - Добавляем слагаемое в список.

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

17 - В случае, если цепочка не добавлена увеличиваем на один счетчик попыток.

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

На выходе получается полноценное выражение в виде строки.



Рис. 5.4 - алгоритм генерации цепочки слагаемых

5.3.4 Эффективное использование переменных

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

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

Рассмотрим алгоритм эффективного использования переменных на рисунке 5.5.

1 - Генерируется цепочка слагаемых (выражение).

2 - Происходит зацикливание в случае, если N > M + 1, где N - количество переменных, а M - количество действий.

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

4 - Повторно генерируем выражение.

Рис. 5.5 - Алгоритм обеспечивающий эффективное использование переменных

6. Описание устройства и работы вычислительного механизма

6.1 Общее описание вычислительного механизма

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

В основе вычислений алгоритм ОПЗ с использованием стека, а также специальные методы для выполнения операций над КЧ.

На выходе механизм возвращает комплексное число (результат выражения), а также подробное решение всего выражения.

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

Перед написанием вычислительного механизма было изучено учебное пособие «Комплексные числа» [7], из которого были получены навыки работы с КЧ.

6.2 Упрощенная схема работы вычислительного механизма

Рассмотрим упрощенную схему работы вычислительного механизма на рисунке 6.1.

1 - Входящие выражение записано в виде строки. В таком виде сложно работать с выражением, поэтому его необходимо разбить на составляющие (операнды и операции). На выходе получается массив элементов выражения.

2 - После того, как выражение было подготовлено, его нужно перевести в ОПЗ. Это позволит последовательно по действиям вычислить выражение. Подробно алгоритм перевода в ОПЗ описан в пункте 4.1.1.

3 - Вычисление выражения, записанного в ОПЗ. При вычислении происходит работа с КЧ с помощью отдельных методов. Также на данном этапе формируется подробное решение. Подробно алгоритм вычисления выражения, записанного в ОПЗ описан в пункте 4.3.

4 - Для работы с КЧ реализованы специальные методы, которые вызываются при вычислении выражения. Программный код класса, выполняющего математические операции над КЧ представлен в «Приложении В».

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

Рис. 6.1 - схема работы вычислительного механизма

6.3 Округление результата

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

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

6.4 Степень подробности решения

При формировании подробного решения записываются данные двух типов: краткие (промежуточные выражения и их результат) и полные.

Полное подробное решение включает в себя:

· Промежуточные выражения;

· Результат промежуточного выражения;

· Словесное описание;

· Подробности промежуточного вычисления.

Посмотреть пример подробного решения одного действия можно на рисунке 6.2.



Рис. 6.2 - Пример подробного решения

7. Описание приложения

7.1 Описание устройства ПО

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

Для начала работы обучающемуся необходимо настроить генератор задач. После настройки на вход генератора подаются корректные параметры настройки генерации. Генератор задач генерирует КЧ и выражение, которые затем преобразовываются в компьютерную верстку TeX. Из преобразованной задачи с помощью библиотеки jLaTeXMath получается изображение, на котором отображена сгенерированная задача. Программный код преобразования в LaTeX представлен в «Приложении Е». Программный код реализующий получение изображения представлен в «Приложении Ж». Схема данного процесса изображена на рисунке 7.1.

...