Дипломная работа (бакалавр/специалист) на тему Визуализаторы алгоритмов дискретной математики на основе автоматного подхода

Содержание:

ВВЕДЕНИЕ 3
1. АНАЛИТИЧЕСКАЯ ГЛАВА 5
1.1 Понятие автомата и автоматного подхода 5
1.2 Обзор автоматов 8
1.3 Роль средств визуализации в процессе обучения 11
1.3 Автоматный подход в образовательной сфере 14
2. ОБЗОР АЛГОРИТМОВ, ПОДЛЕЖАЩИХ ВИЗУАЛИЗАЦИИ 18
2.1 Асимптотические оценки сложности 18
2.2 Алгоритмы сортировки 19
2.3 Алгоритмы поиска 20
2.4 Комбинаторные задачи 21
3. ПРОЕКТНАЯ ГЛАВА 24
3.1 Преобразование алгоритмов в автоматы 24
3.2 Описание реализации 26
3.3 Общее описание разработанного комплекса 30
3.4 Тестовые запуски 33
ЗАКЛЮЧЕНИЕ 36
СПИСОК ЛИТЕРАТУРЫ 38
ПРИЛОЖЕНИЯ 41
Приложение 1. Пример автоматного способо построения диалога 41
Приложение 2. Теоретические сложности рассмотренных методов сортировки 42
Приложение 3. Листинг кода 43

Введение:

Понятие «сложность алгоритма» связана, в первую очередь, с использованием ресурсов компьютера. Сложность алгоритма определеят количесвто процессорного времени, требуемого программой, расход памяти и других ресурсов. Как правило, память, расходуемая для записи команд программы не берется во внимание, а учет ведется по объему данных. Принято, что для машин с разной тактовой частотой и с незначительными вариациями в архитектуре, время, по возможности, рассчитывается в относительных единицах и так, что ты эта оценка имела незначительные отклонения.
Прежде всего, такой подход ориентирован на инженерные и научные приложения теории алгоритмов. Исторически так сложилось, что объемы входящих данных могут значительно превышать размеры самой программы, а программа может выполнятся несколько часов. При таком подходе, особенно при критической важности ресурсов, может возникнуть проблема целесообразности решаемой задачи или всего проекта, из-за неэффективной работы программы. Например, к таким областям относятся системы реального времени (real-time systems).
Конкретной направленностью работы является автоматный подход в программированиии.
Исследования в области теории автоматов начались еще в середине 50-х годов прошлого века. Несмотря на свою простоту, модель конечного автомата оказалась чрезвычайно удобной в применении не только в информатике, но и во многих других отраслях инженерной деятельности. Большой интерес к этой теории объясняется именно широкими возможностями ее применения.
Без преувеличения можно сказать, что теория автоматов является одним из фундаментальных блоков современной теоретической и практической информатики. Наряду с классическими приложениями теории автоматов, такими как проектирование встроенных систем логического управления, обработка текстов и построение компиляторов искусственных языков, в последнее время появились новые, нетрадиционные области применения этой теории — спецификация и верификация систем взаимодействующих процессов (в частности, протоколов коммуникации), языка описания документов и объектно-ориентированных программных систем, оптимизация логических программ и другие.
Объектом исследования работы является понятие автомата и автоматного подхода.
Предметом исследования является применение автоматного подхода к реализации программы – визуализатора работы выбранных алгоритмов (сортировки, поиска и др.)
Цель работы – реализовать программный комплекс на основе автоматного подхода для визуализации работы выбранных алгоритмов.
Для достижения цели необходимо реализовать следующие задачи:
изучить теоритическую часть, определить основные поянятия, расмотреть примеры и различные типы автоматов;
сделать литературный обзор в области применения автоматного подхода к учебным визуализирующим среждствам, определить назначения и преимущества использования визуальных средств при изучении различных предметов, и конкретно в области изучения алгоритмов;
выбрать набор алгоритмов для визуализации;
предствить алгоритмы с использованием автоматного подхода;
реализовать программно систему, визуализирующую алгоритмы;
проветси тестирование системы;
разработать документацию в виде пояснительной записки к работе.
 

Заключение:

Теория алгоритмов изучает алгоритмы, а конкретно их свойства, и закономерности порождаемые подходами и конкретными реализациями алгоритмов. Формализация понятия и различные абстрактные модельные представления дают возможность сравать алгоритмы по критерию эффективности, проверять алгоритмы на эквивалентность, позволяют определить приенимость в той или инной области.
Теория сложности алгоритмов предлагает достаточные эффективные методы решения поставленной проблемы. Точное решение возможно в подавляющем большинстве практически важных ситуаций.
В ходе дипломной работы был выполнен перечень работ по изучению теоритического аспекта алгоритмов, а так же выполнены некоторые практические задания. Приведены листинги некоторых алгоритмов, а так же результаты выполнения задач.
Визуализаторы алгоритмов призваны помочь разобраться начинеающему программисту (или просто интересующемуся человеку) как работает тот или иной алгоритм.
В отличие от существующих методов организаации обучающих диалогов в АОС, применение автоматного подхода на всех уровнях построения РАОС, включая адаптивные сценарии обучающих диалогов, позволяет отказаться от сложного семантического и синтаксического анализа ответа учащегося. Предлагаемая технология дает возможность существенно упростить программные алгоритмы, реализовать в обучающей системе относительную предметную независимость, использовать естественный язык для ввода ответов учащихся, а преподавателям самостоятельно, без привлечения программиста, создавать и модифицировать сценарии адаптивных диалогов посредством экранных форм пользовательского интерфейса. Практическое применение предложенных теоретических положений возможно:
для построения самостоятельной адаптивной обучающей системы;
в качестве структурной основы для построения отдельных модулей к различным обучающим системам.
Работа сотоит из вступления, заключения и3 глав основной части.
В певой главе рассмотрено поянятие автомта как математической абстракции, приведены конкретные примеры автоматов. Также первая глава включает обзор литерутуры по теме. Не только с точки зрения математики (понятие автоматов), но и сточки зрения автоматного подхода в обучении.
Вторая гглава посвящена обзору самих алгоритмов, которые подлежат визуализации в практической части. Рассматриваются понятия временной и алгоритмической сложности, делается сравнение алгоритмов.
Последняя глава рассматривает непосредственно практическую реализацию. Описываются моменты анализа, проектирования, тестирования разработанного приложения. Даются общая характеристика разработанного программного комплекса.
Практическая часть работы имеет две направленности. С одной стороны работа предполагает выработку навыков программирования, и непосредственно, программирования в стиле автоматного подходя. С другой стороны практические результаты, полученные в работе, вполне могут использоваться как демонстрационные материалы на занятияхъ по изучению алгоритмов. 

Фрагмент текста работы:

1. АНАЛИТИЧЕСКАЯ ГЛАВА
1.1 Понятие автомата и автоматного подхода
Автоматный подход в программировании, который еще называют «программированием от состояний» или «программирование с явным выделением состояний» по своей сути являются методом разработки ПО, в основании которого используется расширенная модель конечных автоматов. Метод может иметь очень широкое применение и ориентироваться на реализацию широкого класса программных средств.
Автоматный подход, в целом, не ограничивается четким использованием конечных автоматов, в широком понимании автоматное программирование основано на методе создания программных приложений с поведением, описываемом автоматами. Автоматное программирование (АП) и основополагающие идеи возникли достаточно давно. Различные аспекты и понятия, связанные с идеей АП, рассматривали многие авторы. Исследуя вопросы и проблемы под различными углами зрения, авторы исследований получали различные результаты, которые, со временем, сформировались в четкие формальные модели.
Автоматное программирование как самостоятельная, целостная парадигма предложена, в частности, в 1991 году автором многих исследований в направлении АП. Основные концепции изложены в работах [2,3,11]. В ранее упомянутых источниках описываются многие моменты, но в настоящий момент невозможно говорить о полном и исчерпывающем описании данного подхода, а тем более об устоявшейся парадигме в программировании. Основная причина – отсутствие массовости использования и малый накопленный опыт использования АП при разработке программных приложений.
Центральная идея парадигмы, по мнению автора Шалыто А. А., которую он изложил в работах [2,11] – разделение логики поведения (условий сценария и поведенческих линий) от описания самого поведения (описания реализации самих действий). АП свойственна жесткость описания логики поведения, что позволяет формализовать и упростить понимание систем со сложным поведением.
Основная рекомендация, сформулированная автором, по применению автоматного программирования очень проста использовать автоматный подход при создании любой программной системы, в которой есть сущности со сложным поведением. В то же время автор [2,11] отмечает, что не стоит перегружать программный код строго-формализованным описанием логики там, где в этом нет необходимости. В своей концепции автор Шалыто предлагает рассматривать конечный автомат как комбинацию (рис. 1.1):
АВТОМАТ БЕЗ ВЫХОДОВ +«ВЫХОДНОЕ ВОЗДЕЙСТВИЕ»
Автомат реагирует на входное воздействие не только сменой состояния, но и формированием определенных значений на выходах. Функция выходов автомата определяется правилами формирования выходных воздействий.
Естественно в основе автоматного подхода в программировании лежит само понятия автомата. В теории алгоритмов различают автоматы абстрактные и автоматы, которые являются подклассами класса «абстрактный автомат». Абстрактный автомат является вершиной иерархии в теории автоматов. Налагая различные ограничения и правила на абстрактный автомат получают производные конструкции: автомат с инициализации, конечный автомат, машина Тюринга и ряд других подклассов.
В разрезе тематики работы и применения АП для реализации практической прикладной задачи нас в первую очередь интересуют конечные автоматы.
Конечный автомат (КА) в теории алгоритмов математическая абстракция, позволяющая описывать пути изменения состояния объекта в зависимости от его текущего состояния и входных данных, при условии, что общее возможное количество состояний конечно. Конечный автомат является частным случаем абстрактного автомата.