автореферат и диссертация по педагогике 13.00.02 для написания научной статьи или работы на тему: Компьютерные средства обучения молекулярным вычислениям бакалавров информационных систем и технологий

Автореферат диссертации по теме "Компьютерные средства обучения молекулярным вычислениям бакалавров информационных систем и технологий"

На правах рукописи УДК 37.016:004 37.016:51

Ракитин Александр Георгиевич

КОМПЬЮТЕРНЫЕ СРЕДСТВА ОБУЧЕНИЯ МОЛЕКУЛЯРНЫМ ВЫЧИСЛЕНИЯМ БАКАЛАВРОВ ИНФОРМАЦИОННЫХ СИСТЕМ И ТЕХНОЛОГИЙ

Специальность: 13.00.02 - теория и методика обучения и воспитания (информатика, уровень профессионального образования)

Автореферат диссертации на соискание ученой степени кандидата педагогических паук

13 МАЙ 2015

Санкт-Петербург 2015 г.

"Л

005568796

005568796

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

Научный руководитель:

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

Официальные оппоненты:

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

кандидат педагогических наук, доцент автономной некоммерческой организации высшего профессионального образования «Смольный институт Российской академии образования» Титова Юлияна Фраицевна

Ведущая организация:

Автономное образовательное учреждения высшего профессионального образования «Ленинградский государственный университета имени A.C. Пушкина»

Защита состоится 25 июня 2015 года в 11 часов на заседании совета Д 212.199.03 по защите диссертаций на соискание ученой степени кандидата наук, на соискание учёной степени доктора наук на базе федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Российский государственный педагогический университет им. А.И. Герцена» по адресу: 191186, г. Санкт-Петербург, наб. реки Мойки, дом 48, корп. 1, ауд. 237.

С диссертацией можно ознакомиться в Фундаментальной библиотеке имени императрицы Марины Федоровны Российского государственного университета им. А.И. Герцена, 191186, т. Санкт-Петербург, наб. реки Мойки, дом 48, корп. 5 и на сайте университета (URL: http://disser.herzen.spb.ru/Preview/Karta/karta_000000228.html)

Автореферат разослан <7 3» АПР 2015 2015 года

Учёный секретарь Диссертационного совета, доктор педагогических наук, профессор

И.В. Симонова

ОБЩАЯ ХАРАКТЕРИСТИКА ИССЛЕДОВАНИЯ

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

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

Актуальность исследования подтверждают следующие противоречия:

1) активное взаимопроникновение информационных технологий, биотехнологий, нанотехнологий и когнитивных технологий (>ГО1С-технологий) предполагает возникновение нового содержания обучения и средств обучения, т.е. необходимость теоретической систематизации новых знаний, лежащих в основании КВ1С-технологий;

2) в настоящее время содержание обучения, относящееся к понятию «вычислимость», содержит класс моделей, которые мы называем «классическими вычислительными моделями» и источником которых является математика. Однако Природа обладает внутренними средствами, позволяющими реализовывать вычислительные процессы более эффективно. В учебном процессе подобные вычислительные модели пока не находят достаточного отражения в учебных и методических пособиях. Перечислим несколько существующих научных изданий, в которых затрагиваются вопросы молекулярных вычислений: «Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология» (Д. Гасфилд, 2003), «Анализ биологических последовательностей» (Р. Дурбин, Ш. Эдди, А. Крог, Г.

Митчисон, 2006), «Вычисление на ДНК. Эксперименты. Модели. Алгоритмы. Инструментальные средства» (Г.Г. Малинецкий, С.А. Науменко, 2005), «Алгоритмы обработки строк» (С.М. Окулов, 2009), «ДНК-компьютер. Новая парадигма вычислений» (Г. Паун, Г. Розенберг, А. Саломаа, 2004), «Методы и алгоритмы вычислений на строках» (Б. Смит, 2006), «Введение в вычислительную молекулярную биологию» (Ж. Сетубал, Ж. Мейданис, 2007), «Методика обучения неклассическим вычислительным моделям бакалавров физико-математического образования (Т.С. Стефанова, 2008);

3) в современной информатике существуют алгоритмы, которые невозможно эффективно реализовать с помощью классического компьютера. Эти проблемы могут помочь решить неклассические вычислительные модели;

4) для организации процесса обучения, отмеченного в пп. (1), (2) и (3), необходимы программные средства учебного назначения, но подобных программ крайне мало.

Для дальнейшего изложения определим некоторые термины.

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

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

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

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

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

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

Объектом исследования является процесс обучения ДНК-вычислениям бакалавров информационных систем и технологий.

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

Гипотеза исследования.

Если содержание обучения молекулярным вычислениям структурировать следующим образом:

1) компьютерное моделирование алгоритмов поиска подстроки в строке (раздел «Алгоритмы поиска подстроки»);

2) компьютерное моделирование алгоритмов на подпоследовательностях (раздел «Алгоритмы на подпоследовательностях»);

3) моделирование молекул ДНК и операций над ними (раздел «Операции над цепочками ДНК»);

4) компьютерное моделирование классических молекулярных алгоритмов (раздел «Молекулярные алгоритмы»)

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

-ДНК-интерпретатор на базе языка 1С, с помощью которого можно реализовать классические молекулярные алгоритмы (опыт Эдлмана, решение задачи о выполнимости пропозициональных формул, решение задачи о рюкзаке);

— интерпретатор • языка пробирок для ДНК-вычислений на языке функционального программирования;

— фреймворк для анализа биологических строк.

Использование этих средств обучения в учебном процессе позволит бакалаврам информационных систем и технологий:

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

— приобрести знания об алгоритмах поиска подстроки в строке и алгоритмах на подпоследовательностях, что позволяет обучаемым осознать фундаментальность структуры данных «строка» для моделирования конструктивных объектов (в частности, объектов молекулярной биологии);

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

— приобрести умения применять алгоритмы поиска подстроки в строке и алгоритмы на подпоследовательностях;

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

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

Первая группа задач (теоретического характера)'.

1) сформулировать внешние и внутренние цели обучения;

2) на базе понятия «природные вычисления», используемого для получения новых неклассических вычислительных моделей, сформулировать принципы отбора содержания и выделить новые концептуальные содержательные линии раздела «Молекулярные вычисления»;

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

Вторая группа задач {практического характера) - это частичная практическая реализация теоретических положений исследования:

1) разработать новые учебные компьютерные программы (интерпретаторы), симулирующие ДНК-компьютер;

2) использовать методы математической статистики для проверки гипотез, выдвинутых в ходе исследования, а также для анализа контрольных работ, проводимых в рамках педагогического эксперимента;

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

Для решения задач исследования применялись следующие научные методы:

1) анализ научной литературы по проблемам построения содержания обучения;

2) анализ научной литературы по математике, программированию, биологии;

3) анализ учебных пособий для педагогических вузов, университетов и технических вузов, а также научных публикаций по теме нашего исследования;

4) анализ вузовских стандартов, различных программ подготовки бакалавров информационных систем и технологий, учебников и учебных пособий по информатике и по теории алгоритмов;

5) анализ процесса обучения информатике в РГПУ им. А. И. Герцена;

6) методы обработки результатов эксперимента (применялись при констатирующем и контролирующем эксперименте для проверки отдельных теоретических положений);

7) моделирование содержания обучения молекулярным вычислениям с помощью аппарата теории графов.

На защиту выносятся следующие положения:

1) содержание обучения ДНК-вычислениям бакалавров информационных систем и технологий, дополненное разделами «Алгоритмы поиска подстрок»,

«Алгоритмы на подпоследовательностях», представленное в виде графа понятий и полученное на основе анализа научной литературы по математике, биологии и информатике;

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

3) компьютерные средства обучения молекулярным вычислениям перечисленные ниже в разделе «Практическая значимость»;

4) методика проведения педагогического эксперимента для случая выборок малого объёма.

Научная новизна.

1) к существующей структуре содержания обучения, построенной Т.С. Стефановой, добавлены два раздела «Алгоритмы поиска подстрок» и «Алгоритмы на подпоследовательностях»;

2) в содержание обучения добавлены три классических молекулярных алгоритма: опыт Р. Липтона, решение задачи о рюкзаке, опыт Э. Шапиро по молекулярному моделированию конечных автоматов;

3) построен новый алгоритм решения задачи о нахождении les, для которого произведено сравнение эффективности с существующими алгоритмами;

4) введено понятие «методические связи» для эффективного построения средств обучения.

Теоретическая значимость исследования.

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

Практическая значимость.

Построены следующие средства обучения (моделирующие, предметно ориентированные, по классификации И.В. Роберт):

- интерпретаторы ДНК-вычислений для работы с пробирками, написанные на языках 1С и Haskell;

- интерпретаторы ДНК-вычислений для работы со стикерами, написанные на языках 1С и Haskell;

- реализация опыта JI. Эдлмана, опыта Р. Липтона и молекулярного решения задачи о рюкзаке с помощью интерпретатора ДНК-вычислений на языке 1С;

- реализован фреймворк для анализа ДНК строк;

- реализован пакет процедур для реализации алгоритмов поиска подстроки в строке (простой алгоритм, алгоритм Вагнера-Фишера, алгоритмы Хершберга, алгоритм Укконена-Майерса).

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

Логика и основные этапы исследования.

Исследование проводилось с 2011 по 2015 год и включало три этапа:

1) поисковый этап (2011-2012 гг.). На данном этапе осуществлялось изучение и анализ отечественной и зарубежной литературы по проблеме исследования. В указанный период был произведен выбор темы исследования и обоснована её актуальность. Произведен выбор методологических основ и методов исследования. На основании полученных данных определена проблема, цель, предмет и объект' исследования. Выдвинута гипотиза и задачи исследования, намечен план экспериментальной работы;

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

3) формирующий этап (2013-2015 гг.). В рамках данного этапа проводилась

9

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

Апробаиия результатов исследования:

-конференция «Герценовские чтения» (2011, 2012, 2013 гг., Санкт-Петербург);

— конференция «Решения 1С для бизнеса: эффективное управление и учет» (13.11.2013-14.11.2013, Санкт-Петербург);

— международная научно-практическая конференция «Высокотехнологичная информационная образовательная среда» (15.04.2014, РГПУ им. А.И. Герцена);

— международная научно-практическая конференция «Педагогический опыт: теория, методика, практика» (октябрь 2014, Чебоксары);

— международная научно-практическая конференция «Новый информационные технологии в образовании» (Применение технологий «1С» для формирования инновационной среды образования и бизнеса) (03.02.2015-04.02.2015, Москва).

Внедрение результатов исследований проводилось с 2008 по 2014 гг. в следующих курсах:

1) «Вычислительные модели» для обучения магистрантов 1-го курса (фак. математики, 2008-2009);

2) «Современные аспекты методики обучения информатике» для обучения магистрантов 1-го курса (фак. математики, 2008-2011);

3) «Молекулярные вычисления» для обучения бакалавров 4-го курса (фак. информационных технологий, 2011-2012);

4) «Прикладное программирование на языках высокого уровня» для обучения бакалавров 3-го курса (фак. информационных технологий, 2013-2014).

В качестве объектов в проведенном педагогическом эксперименте выступали студенты 1П и IV курсов, магистранты и аспиранты кафедры информатики и кафедры информационных систем и программного обеспечения РГПУ им. А. И. Герцена.

Диссертация состоит из введения, трёх глав, заключения, библиографии и приложений. Основной текст занимает 154 страницы, в том числе 65 рисунков, 2 таблицы, библиография 110 наименований - 11 страниц, приложение 13 страниц.

ОСНОВНОЕ СОДЕРЖАНИЯ ИССЛЕДОВАНИЯ

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

В первой главе «Теоретические основы построения методической системы обучения молекулярным вычислениям» определяются понятия, которые позволяют выделить современные акценты в классическом понятии «межпредметность». Далее рассматривается взаимовлияние технологий (ЬГВ1С-конвергенция). Затем определено место молекулярных вычислений в ЖЛС-конвергенции. Далее рассмотрены понятия «природные вычисления» и «методические связи».

В §1.1 определяются понятия «междисциплинарность», «полидисциплинарность», «трансдисциплинарность». В исследовании мы существенно опираемся на понятие «трансдисциплинарность», которое характеризует исследования, которые идут через, сквозь границы нескольких дисциплин, выходят за пределы конкретных дисциплин.

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

1) открыта по отношению к новым когнитивным схемам, переносимым из смежных и более отдалённых научных дисциплин и имеющим для неё эвристическую значимость; готова к кооперации в другими научными дисциплинами, к реализации совместных исследовательских проектов;

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

11

Молекулярные вычисления (ДНК-вычисления) как раз являются подобным проектом. Дисциплины «Информационные технологии» и «Биология», между которых расположены молекулярные вычисления, открыты с точки зрения реализации совместных исследовательских проектов, но при этом замкнуты с точки зрения предмета и ракурса исследования.

В §1.2 рассматривается взаимовлияние технологий, которое получило название МВ1С-конвергенция.

ИВТС-конвергснция - это процесс становления связанного кластера информационных технологий, биотехнологий, нанотехнологий и когнитивной науки. В дальнейшем мы будем рассматривать только направления «В» и «С».

В §1.3 определено место молекулярных вычислений в МИС-конвергенции, рассмотрены преимущества и недостатки молекулярных вычислений. Схематично место молекулярных вычислений указано ниже (см. Рис 1).

В § 1.4 определено понятие «природные вычисления», к которому относятся молекулярные вычисления (ДНК-вычисления). Приведенные выкладки мы используем для развития содержания обучения неклассическим (природным) вычислительным моделям.

информатика математика вычислительная техника

медицина биология

биохимия

Рис 1. Место молекулярных вычислений в №ИС-конвергенции

В §1.5 определено понятие «методические связи» для методической системы обучения, описаны достаточные условия их конструирования, а также в качестве конкретного примера представлены методические связи содержания

12

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

Во второй главе «Развитие содержания обучения молекулярным вычислениям» проведен отбор содержания обучения ДНК-вычислениям бакалавров информационных систем и технологий, приведены необходимые теоретические сведения, которые использовались при проведении исследования.

Отбор содержания обучения базируется на следующих принципах:

1) концепция содержания образования В. В. Краевского;

2) принцип использования трансдисциплинарных связей;

3) учёт отечественного и международного опыта формирования содержания учебных программ, относящихся к неклассическим вычислительным моделям;

4) принцип «межпарадигмальной рефлексии».

В §2.1 описана структура ДНК, а также операции с цепочками ДНК.

Цепочка ДНК представляет собой полимерную молекулу, состоящую из нуклеотидов, обозначаемых буквами А (аденин), Ц (цитозин), Г (гуанин), Т (тимин). При определённых условиях две цепочки могут соединиться и образовать двойную цепочку, при этом аденин (А) комплементарен тимину (Т), гуанин (Г) комплементарен цитозину (Ц).

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

На основании отбора содержания сформирован граф содержания обучения по темам «Цепочки ДНК и их моделирование» (см. Рис 2) и операции над цепочками ДНК.

Рассмотрено понятие «мультимножество» и возможность использования мультимножества для моделирования молекулярных вычислений. Построен граф содержания обучения для темы «Мультимножества».

В §2.2 рассмотрены способы моделирования классических алгоритмов над молекулами ДНК: опыт Эдлмана, опыт Липтона, опыт Шапиро, задача о

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

Рис 2. Граф содержания обучения по теме «Цепочки ДНК и их моделирование»

В §2.3 проведён отбор содержания обучению поиска подстроки в строке. Определены предварительные понятия, изучаемые алгоритмы. Определена

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

В §2.4 произведен отбор содержания обучению алгоритмам на подпоследовательностях. Определены предварительные понятия, изучаемые алгоритмы. Определена структура курса обучения и взаимосвязь с другими курсами обучения. Приведены некоторые примеры практических задач, приводящих к задаче нечёткого сравнения строк:

1) программа проверки правописания (поиск наиболее подходящего слова для любой строки символов, отсутствующей в словаре);

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

3) в криминалистике требуется определить схожесть цепочек ДНК оставленных на месте преступления с ДНК подозреваемого;

4) компьютерная программы реализующие эффективный поиск сходных последовательностей в больших базах данных последовательностей ДНК.

В §2.5 описана новая реализация алгоритма поиска наибольшей общей подпоследовательности. Произведен анализ быстродействия по сравнению с простым алгоритмом и алгоритмом Укконена-Майерса.

В третьей главе «Средства обучения молекулярным вычислениям» рассматриваются разработанные средства обучения: интерпретаторы ДНК-вычислений и подпрограммы для интерпретатора, реализующие классические алгоритмы. Рассмотрены различные варианты моделирования ДНК компьютера на «обычном» компьютере. В конце третьей главы описан педагогический эксперимент.

В §3.1 рассмотрена классификация программных средств учебного назначения по И.В. Роберт. Проведена классификация, описанных в диссертации средств обучения по методическому и функциональному назначению.

В §3.2 рассмотрена система программ «1С: Предприятие», встроенный язык 1С. На базе встроенного языка 1С разработаны подпрограммы работы с различными типами данных, которые могут быть использованы при моделировании молекулярных вычислений.

В §3.3 рассмотрен разработанный интерпретатор ДНК-вычислений на базе языка Haskell. Интерпретатор позволяет моделировать перечень операций над цепочками ДНК и стакерами в режиме командной строки.

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

В §3.4 рассмотрен разработанный интерпретатор ДНК-вычислений на базе языка 1С. Описаны перечень операций, которые моделируются данным интерпретатором и приведено сравнение с интерпретатором ДНК-вычислений на базе языка Haskell.

В §3.5 рассмотрен вариант компьютерной реализации опыта Эдлмана при помощи интерпретатора ДНК-вычислений на базе языка 1С. Исходные данные введены в текстовые файлы, которые обрабатывает интерпретатор. Результат опыта отображается на экране интерпретатора.

JI. Эдлман провел опыт в лаборатории, позволяющий доказать при помощи цепочек ДНК наличие гамильтонового пути в графе.

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

Поиск такого пути выполняется в лаборатории по следующему алгоритму:

1) в пробирку помещаются все ДНК-цепочки, кодирующие вершины и дуги. Последовательность нуклеотидов, подобирается так, чтобы «половина» цепочки ДНК, кодирующая вершину, могла соединиться только с «половиной» цепочки ДНК, кодирующей дугу;

2) проводится операция «Ренатурация» для получения ДНК-цепочек, которые содержат всевозможные пути;

3) выбираются только те ДНК-цепочки, которые имеют длину, соответствующую длине всех вершин;

4) поочередно выбираются из пробирки те ДНК-цепочки, которые содержат каждую из вершин;

5) проверяется наличие ДНК-цепочек в пробирке.

В том случае, если после шага 5 в пробирке остались цепочки ДНК, то можно говорить, что гамильтонов путь в графе найден, в противном случае гамильтонова пути в графе не существует.

В §3.6 рассмотрен вариант реализации задачи о выполнимости пропозициональных формул при помощи интерпретатора ДНК-вычислений на базе языка 1С. Исходные данные для интерпретатора приведены в текстовых файлах, загружаемых в интерпретатор.

Задача о выполнимости формулируется следующим образом: задана формула языка нулевого порядка в конъюнктивной нормальной форме (КНФ). Необходимо определить, существует ли набор значений её атомов И или Л, при котором значением формулы является И.

В §3.7 рассмотрен вариант реализации задачи о рюкзаке при помощи интерпретатора ДНК-вычисления на базе языка 1С.

Задача о рюкзаке формулируется следующим образом: имеется п грузов определённого веса и ценности. Обозначим С>0 ценность ¡-го груза, Р;>0 - его вес. Требуется упаковать в «ранец» ограниченной грузоподъемности Р такие грузы, чтобы суммарная ценность упакованных грузов была максимальной.

Алгоритм решения содержит следующие этапы:

1) кодирование веса и ценности предметов и связей между предметами. Верхняя нить двухспиральной ДНК соответствует весу, а комплементарная нить, соответствует ценности предмета. Пример файла с сиходными условиями задачи приведен ниже (см. Рис 3): предметы обозначены Бь Б2, Бз, Б4, связующие для предметов цепочки ДНК обозначены Ою...

Предмет Вес Ценность вес рюкзака - 38 1 18 10

2 10 4

3 17 7

4 11 5

Ответ: предметы - 1,3, вес - 38, ценность - 17 51 -ССССАСТСАСТАСгеСС-З' (3' -СС<ГГСАТСАСТСАССеС-5 1)

01: с ста | сссстсдоте | сета

ССССАСТСАС 02: ААТ|А(ЗАТ|ТТС ТСГА

03: АСбСТ | АТСАССа IТССАТ

ТАСТССС 04: ССС|САСет|ААС

отсса

01-2: ССАС^СЗА

01-3: бСАС|ТйССА

01-4: ссАс|сес

02-3: ААСЗIТССвА

02-4: ААбкаез

03-4: АССТА|сса

Рис 3. Исходные условия задачи о рюкзаке

2) смешать цепочки ДНК и провести ренатурацию;

3) выделить цепочки ДНК, которые больше чем ёмкость «рюкзака»;

4) провести денатурацию, удалить цепочки с весом предметов;

5) удалить из связей между предметами вспомогательные цепочки;

6) провести анализ решения, выбрать наиболее длинную цепочку ДНК. Пример файла с алгоритмом решения для интерпретатора ДНК-вычислений

и результаты выполнения алгоритма приведены ниже (см. Рис 4, Рис 5). Н

// добавим в пробирку 1 днк кодирующие предметы, вес и ценность (вершины) 0.1;ЮСТАССбСТ<ЗАетасетС#5 ССССАСТСАС$#ААТА<ЗАТТТС#$ ТСТА$#АС6СТАТ(ЗАС5(Г

// Добавим в пробирку 2 ДНК, кодирующие ребра 0. 2$ОСАСССА50САСТСССА56САСССС$ААОТ<ЗССА$АА6СС05АССТАССС5

// Добавим ребра к вершинам 1.1 21

П Осуществим ренатурацию

Р. 1

Р.1

Р.1

// Оставим в пробирке 1 ДНК длиной 38 (вес рюкзака) 5.1 2 38 //

// Осуществим денатурацию

Д.1

// Оставим в пробирке 1 ДНК, которые не содержат вершны И (оставим ребра и ценность предметов) :// для этого разделим - результат в пробирке 2. // помоем пробирку 1 и сольем в пробирку 1.

0. 2#ССТАСССОТ(^СТССаТС#МТА<1АТТТС«(АСеСТАТСАССетССАТ#ССССАСетААС# 4.1 2 8.1 1.1 2 //

Рис 4. Молекулярное решение задачи о рюкзаке 18

В §3.8 рассмотрено программное обеспечение, представляющее собой фреймворк для анализа биологических строк на языке 1С. Фреймворк позволяет как преподавателю, так и студенту производить эволюцию программного обеспечения, т.е. включать собственные алгоритмы с сохранением основных функций фреймворка.

; 0. Генерация ; :£. В^еевить'эд I ;;-10»яишпь|| ; 3. 1 :

1. Слать , . 117. Быдешть р.О 1 И - -Реме»™, и суфсшоу | ; Р. Ремк?| 1.................................!

: 2. Размножить . с Вь-йег-ить пс ■ 5 ГЬмьггь штине пробсту ! Д. Денгтуршкк ;

\ N цег:оч*а ДНК

.ШмИК г з'-сл.тсдсг^-з

2 3'-АТСТ-5 '

3 : 3 ' -СССГГСАТ-51 4Э'-Асета-5'

5 Э ' -ССОТСАТСАСТСАССОС - 5' ?: . :.7Г0Г?СТС*С.С0С-5' 7 З1 -таТСАТАТСТ-5'

ГЛЗадача о ркжззке {Кпэрааск РгеЫеп)? 4 Команда: | Зэкснченэ вьетогненме пилена

• Ы Нею« а«к

I цепсчка ДНК2

1 Э'-АОВСАСО-Б1 ..............7 я 1-йшратрйрп-ц1

ЗС:ГЬелп**«>тие ____

Пре&фкз не г/ста': Бясрб ДНК 1С- самзя глжнзя ДНК: ССЗТСй.ТО£ТСаССК:

: 5 3' -(КОВАА-г'

6 3'-ВвСАТССА-Э1

Рис 5. Результат решения задачи о рюкзаке в интерпретаторе ДНК-вычислений

на базе языка 1С

Студенты и преподаватели, используя данный фреймворк, могут самостоятельно добавлять новые алгоритмы над строками, основанные на методе динамического программирования. Экранная форма позволяет добавлять новые элементы интерфейса, сохраняя все возможности обработки (См. Рис 6).

В §3.9 описано проведение педагогического эксперимента с использованием непараметрической статистики (и - критерий Манна-Уитни, Н - критерий Крускала-Уоллиса, в - критерий знаков) и параметрической статистики (сравнение дисперсий с помощью Р-критерия Фишера.

TrCCftlGGCCfiOtTCftCTT HTiGCflflicGGflTTCflcnii

Вычислить

ICS

С jifcecsoa »пгоркт С П»ос?сйягг«Ж1М <«гмяг&

Q QXesaSBBT I» Окуясв)

;|jOs3fteorcj!KiM £ Sa^ t^p-^mxp ICS

Схьжш» счрок

в S-SCCTCPiVe

ifc««}

J ■ ПТееП

! i QuSw: ICS DUSfwCKiiK® 1 Tic:?

: ■ iipMSrot*««!®^ ООЙСЭ! ' QTecti

n.Tt г. -w.re^,;- W,',':** ' jp

Расстояние.: Редакционное XCS: TTCATOGACACATT

D A' ra "3 01 ci ' A? 73 се 31S fu" С IS A 18 С 17 А В Г 13 73&

7 ! 2 1 2 3 4 £ 6 7 8 9 SO и 12 13 14 15 18

T; 3 2 1 2 3 4 s 6 7 8 9 10 1i 12 13 14 16 IS

:Ci 4 3 2 3 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

c* 6 4 3 4 3 4 5 e s 5 7 8 9 10 11 12 13 14 1S 10

AS 4 5 4 5 4 3 4 s 6 7 8 7 в 9 10 11 12 13 14 15

T6 5 4 S 6 5 4 5 4 5 6 7 8 7 8 9 10 11 12 13 14

37 e 5 6 S 6 5 6 5 e 5 6 7 8 9 10 11 12 13 14 15

S3 ? 6 7 6 7 6 7 6 7 8 5 e 7 8 9 to 11 12 13 14

;CS 3 7 8 T 6 7 S 7 6 7 e 7 8 9 S s 10 tl 12 13

CIO 9 8 S 8 7 9 9 8 7 8 7 8 9 10 9 10 9 ■J 11 12

г. 11 10 9 10 9 8 7 8 9 8 9 8 7 8 9 10 9 10 9 10 11

IC12 ii 10 11 10 9 9 9 10 9 10 9 8 9 10 9 10 9 10 11 12

Ali 12 11 12 11 10 9 s 9 10 11 10 9 10 11 10 9 10 9 10 11

T:* 13 12 11 12 11 10 9 8 9 10 11 10 9 10 11 10 11 10 9 10

„ . <* 41 .n . < -A о в .....Л . ЧГХ in *n . i ■ n 1Л

ICS Овгюяиип»

Рис 6. Фреймворк для анализа ДНК-строк

В ходе педагогического эксперимента мы сравнивали группы, в которых проходили практические занятия:

1) без использования интерпретатора ДНК-вычислений (2008-2012 уч. год);

2) с использованием интерпретатора ДНК-вычислений на базе языка Haskell (2012-2013 уч. год);

3) с использованием интерпретатора ДНК-вычислений на базе языка 1С (2013-2014 уч. год).

Для подтверждения гипотезы при сравнении групп мы выбрали в качестве критерия эффективность обучения. Применительно к ДНК-вычислениям мы предлагаем следующую структуру эффективности: сложность решения задач, скорость решения задач (получения правильного решения), качество решения, правильность.

После выполнения экспериментов мы оценили эффективность обучения при использовании различных средств обучения. Без использования интерпретаторов получена наименьшая эффективность обучения за счёт

снижения сложности решаемых задач, скорости решения задач и качества решения задач. Наибольшая эффективность обучения достигнута с использованием интерпретатора ДНК-вычислений на базе языка 1С за счёт увеличения сложности решаемых задач и скорости решения задач.

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

В приложениях приведены: графы содержания обучения молекулярным вычислениям, требования, предъявляемые к знаниям и умениям студентов, справочная информация к разработанному интерпретатору ДНК-вычислений на базе языка 1С.

ОСНОВНЫЕ ВЫВОДЫ И РЕЗУЛЬТАТЫ ИССЛЕДОВАНИЯ

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

Перечислим основные результаты исследования:

1) сформулированы внешние цели обучения;

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

3) сформулированы внутренние цели обучения;

4) разработаны новые учебные компьютерные программы (интерпретаторы), моделирующие ДНК-компьютер в режиме симуляции;

5) использованы методы математической статистики для проверки гипотез, выдвинутых в ходе исследования, а также анализа контрольных работ, проводимых в рамках педагогического эксперимента;

6) создан предметно-ориентированный язык (DSL-язык). Перспективные направления развития предложенной методической

системы обучения молекулярным вычислениям могут быть следующими:

1) развитие содержания обучения по разделам «Алгоритмы вычислительной молекулярной биологии» и «Компьютерное моделирование молекулярных вычислений на базе автоматов Уотсона-Крика»;

2) совершенствование существующих средств обучения молекулярным вычислениям;

3) компьютерная реализация с помощью интерпретатора молекулярных вычислений уже известных и вновь появляющихся молекулярных алгоритмов;

4) разработка новых средств обучения молекулярным вычислениям, например, программная реализация операции «сплетение» и включение многопоточного и параллельного программирования;

5) поиск новых моделей вычислений, основанных на биологических принципах.

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

СТАТЬИ, ОПУБЛИКОВАННЫЕ В ЖУРНАЛАХ, ВКЛЮЧЕННЫХ В ПЕРЕЧЕНЬ РОССИЙСКИХ РЕЦЕНЗИРУЕМЫХ НАУЧНЫХ ЖУРНАЛОВ

1. Ракитин А.Г., Стефанова Т.С., Швецкий М.В. Интерпретатор языка пробирок для ДНК-вычислений // Научное мнение, 2013. № 10. С. 214-219. (0,6 п.л./0,2 п.л.) - ISSN 2222-4378

2. Ракитин А.Г., Смирнова Т.С. Использование интерпретатора ДНК-вычислений для решения задачи о выполнимости пропозициональных формул // Известия Российского государственного педагогического

университета имени А.И. Герцена, 2014. № 171. С. 289-292. (0,35 п.л./0,17 п.л.) -ISSN 1922-6464

3. Ракитин А.Г. Интерпретатор ДНК-вычислений на функциональном языке программирования // Известия Российского педагогического университета им. А.И. Герцена, 2014. № 170. С. 34-37. (0,35 п.л.)-ISSN 1992-6464.

4. Ракитин А.Г. Письма в Эмиссия. Оффлайн (The Emissia. Offline Letters): электронный научный журнал: [сайт]. 2014. URL: http://www.emissia.org/offline/2014/2235.htm. (дата обращения: 8.10.2014) (0,5 пл.)-ISSN 1997-8588.

СТАТЬИ, ОПУБЛИКОВАННЫЕ В ДРУГИХ ИЗДАНИЯХ

5. Ракитин А.Г. Обучение языку программирования через написание интеллектуальной игры // Вестник студенческого научного общества РГПУ им. А. И. Герцена. Сборник лучших научных работ студентов. СПб.: Изд-во РГПУ им. А. И. Герцена, 2008. № 8. С. 83-86. (0,15 п.л.)

6. Ракитин А.Г. Электронное обучение на базе программы "1С: образование 4" школа 2.0. Плюсы и минусы // Электронное обучение и управление знаниями в системе профессиональной подготовки. Сборник научных статей конференции. СПб.: Астер-Пресс, 2009. С. 83-86. (0,1 п.л.)

7. Ракитин А.Г. Разработка конструктора выходных форм в среде 1С // Информационные системы и технологии: сборник научно-технических статей. Федер. агентство по образованию, Рос. гос. пед. ун-т им. А. И. Герцена, 2010. № 2. С. 84-86. (0,2 п.л.)

8. Ракитин А.Г. Платформа 1С как средство обучения программированию студентов технических специальностей // Педагогический опыт: теория, методика, практика: материалы междунар. науч.-практ. конф. / редкол.: О. Н. Широков [и др.]. Чебоксары: ЦНС Интерактив плюс, 2014. (0,25 пл.)

9. Ракитин А.Г. Вариант реализации алгоритма les поиска наибольшей общей подпоследовательности // Информационные системы и технологии. Сборник научно-технических статей. СПб.: Изд-во РГПУ им. А.И.Герцена, 2014. № 3. С. 77-85. (0,5 пл.)

Подписано в печать 21.04.2015 Формат 60x84'/i6 Цифровая Печ. л. 1.0 Тираж 100 Заказ №26/04 печать

Типография «Фалкон Принт» (197101, г. Санкт-Петербург, ул. Большая Пушкарская, д. 54, офис 2, Сайт: falconprint.ni)