Содержание к диссертации
Введение
ГЛАВА 1. Теоретические основы построения методической системы обучения молекулярным вычислениям 13
1.1. Парадигмы междисциплинарности 13
1.2. NBIC-конвергенции как новая технологическая парадигма 17
1.3. Молекулярные вычисления в NBIC-технологиях 19
1.4. Понятие «природные вычисления» 23
1.5. О понятии «методические связи» 25
Выводы по главе 1 31
ГЛАВА 2. Развитие содержания обучения молекулярным вычислениям 32
2.1. Отбор содержания обучения компьютерному моделированию структуры цепочек ДНК 34
2.2. Компьютерное моделирование классических алгоритмов над молекулами ДНК 50
2.3. Отбор содержания обучения алгоритмам поиска подстроки в строке 73
2.4. Отбор содержания обучения алгоритмам на подпоследовательностях 77
2.5. Новая реализация алгоритма поиска наибольшей общей подпоследовательности как фрагмент содержания обучения 89
Выводы по главе 2 99
ГЛАВА 3. Средства обучения молекулярным вычислениям 101
3.1. Классификация средств обучения 101
3.2. Платформа 1С как средство обучения программированию 105
3.3. Интерпретатор языка пробирок для ДНК-вычислений на языке Haskell как средство обучения 109
3.4. Интерпретатор языка пробирок на языке 1С как средство обучения 114
3.5. Компьютерная реализация опыта Эдлмана как средство обучения 123
3.6. Компьютерная реализация решения задачи о выполнимости пропозициональных формул 128
3.7. Компьютерная реализация решения задачи о рюкзаке 131
3.8. Фреймворк для анализа ДНК строк 136
3.9. Организация и проведение педагогического эксперимента 139
Выводы по главе 3 148
Заключение 151
Библиография 153
- NBIC-конвергенции как новая технологическая парадигма
- О понятии «методические связи»
- Отбор содержания обучения алгоритмам на подпоследовательностях
- Компьютерная реализация решения задачи о рюкзаке
NBIC-конвергенции как новая технологическая парадигма
Эпистемологический термин «междисциплинарность» очень важен для нашего исследования. Поэтому вначале осуществим анализ этого термина и терминов, ему сопутствующих.
Междисциплинарность соединяет вместе различные теоретические допущения, методологии и практики, которые исходят от дисциплин, вовлекаемых в научное исследование. Другими словами, междисциплинарность означает кооперацию различных научных областей, циркуляцию общих понятий для понимания изучаемого явления.
В позитивном смысле междисциплинарность является закономерным отказом от дисциплинарной ограниченности, исправлением последствий чрезмерной специализации научных дисциплин. Термин «междисциплинарность» также часто употребляется для обозначения синтеза теоретического знания и технологий, построенных на определённых когнитивных стратегиях, т. е. эпистемологический контекст междисциплинарных исследований является неотъемлемым их компонентом. Именно в этом смысле междисциплинарными являются, например, современные биотехнологии и нанотехнологии.
Наряду с термином «междисциплинарность» для характеристики научных направлений сегодня часто используются термины «полидисциплинарность» и «трансдисциплинарность». Проведем концептуальные разграничения этих терминов. Полидисциплинарность, которую в международном сообществе называют мультидисциплинарность (multidisciplinarity), является характеристикой такого исследования, когда какое-либо явление или объект изучается одновременно и с разных сторон несколькими научными дисциплинами. Однако полидисциплинарность – это смесь дисциплин, в которой каждая дисциплина сохраняет свою собственную методологию и свои собственные теоретические допущения, не видоизменяя и не дополняя их при влиянии со стороны других дисциплин. Полидисциплинарность отличается от междисциплинарности характером отношений, которые устанавливаются между различными дисциплинами: внутри полидисциплинарного комплекса знаний кооперация может быть взаимной и кумулятивной, но она не является интерактивной.
Наконец, трансдисциплинарность характеризует исследования, которые идут через, сквозь границы нескольких дисциплин, выходят за пределы конкретных дисциплин, что следует из смысла самой приставки «транс», т.е. создаётся холистическое видение предмета исследования, перенос когнитивных схем из одной дисциплинарной области в другую, разработка и осуществление совместных проектов исследования.
Термин «трансдисциплинарность» первоначально начал использоваться, центром современной антропологии Э. Морена в Париже. При этом Э. Морен, предлагает говорить о полидисциплинарных исследовательских полях, междисциплинарных исследованиях и трансдисциплинарных стратегиях исследования.
Э. Морен выделяет существенные различия между понятиями «междисциплинарность» и «трансдисциплинарность»: «Междисциплинарность может означать только и просто то, что различные дисциплины «садятся за общий стол», подобно тому, как различные нации собираются в ООН исключительно для того, чтобы заявить о своих собственных национальных правах и своём суверенитете по отношению к посягательствам соседа. Но междисциплинарность может стремиться также к обмену и кооперации... В трансдисциплинарных исследованиях существуют когнитивные схемы, которые могут переходить из одних дисциплин в другие, иногда настолько резко, что дисциплины «погружаются» в состояние интеллектуального транса» [21].
Забегая вперед, отметим, что нами будут рассматриваться молекулярные вычисления, которые расположены между дисциплинами «информационные технологии» и «биология». В процессе исследования становится понятным, как информационные технологии «погруженаются» в биологию.
Трансдисциплинарность (по Б. Николеску) базируется на следующих методологических постулатах, принципиально отличающих её от междисциплинарность и полидисциплинарности: 1) признание существования уровней реальности. Каждая дисциплина изучает только некоторый фрагмент реальности, только один из её уровней. Однако трансдисциплинарная стратегия стремится понять динамику процесса на нескольких уровнях реальности одновременно, именно поэтому она «перешагивает» границы конкретных дисциплин и создаёт универсальную картину процесса. В этом смысле трансдисциплинарность не антагонистична междисциплинарности, а дополняет её, так как соединяет различные фрагменты реальности в единую картину. Сегодня нередко речь идёт об инженерии трансдисциплинарности под которой понимается новый научный рационализм, или парадигма открытого разума, в которой познание опирается на такую способность ума, как способность «связывать разнородное» (имеется в виду связывание различных дисциплинарных знаний, а также знания и деятельности, традиции и новации); 2) логика, использующая принцип дополнительности (логика включённого третьего): трансдисциплинарность не противопоставляет, а объединяет, соединяет то, что рассматривалось как противоположное; 3) сложность: Трансдисциплинарность пытается понять сложность реальности и научиться справляться с ней. Таким образом, трансдисциплинарность - это теоретическая попытка «трансцендировать» дисциплины и тем самым отреагировать на специализацию -процесса, ведущего к росту фрагментации и раздробления знания. Переход от полидисциплинарности к трансдисциплинарности - это переход от параллельного (почти независимого) анализа к конструктивному диалогу и осуществлению совместных проектов. Однако требуется, чтобы каждая научная дисциплина, входящая в поли- и трансдисциплинарный комплекс, была одновременно и открыта, и замкнута: 1) открыта по отношению к новым когнитивным схемам, переносимым из смежных и более отдалённых научных дисциплин и имеющим для неё эвристическую значимость; готова к кооперации в другими научными дисциплинами, к реализации совместных исследовательских проектов; 2) замкнута, ибо она должна стремиться сохранить свой специфический предмет и ракурс исследования, развивать свои прогрессивные и наиболее продвинутые исследовательские методы и стратегии. Молекулярные вычисления как раз и являются подобным проектом. Дисциплины «Информационные технологии» и «Биология», между которых расположены молекулярные вычисления, открыты с точки зрения реализации совместных исследовательских проектов, но при этом замкнуты с точки зрения предмета и ракурса исследования.
О понятии «методические связи»
В данном параграфе мы осуществим отбор содержания обучения способам алгоритмического решения задача о поиске подслова в слове (подстроки в строке) некоторого алфавита.
В результате анализа литературы [12, 23, 24, 29, 32, 37, 40, 53, 58, 59, 65, 70, 73, 80, 85, 86, 104] мы построили следующий граф содержания обучения, представленный в виде бинарного дерева «левый - брат, правый - сын»: Предварительные понятия: алфавит, слово, подслово, пустое слово, префикс, суффикс; задача о поиске подслова в слове (подстроки в строке); - эффективность алгоритма в наилучшем (наихудшем, среднем) случае. Методы предварительного анализа строк: - грани строки, массив граней префиксов, массив граней суффиксов, блоки строки, массив блоков; поиск вхождений образца в текст с помощью массива граней; поиск вхождений образца в текст с помощью блоков строки; кратные строки, кратность строки, образующая подстрока; задача о нахождении кратных строк; - s-факторизация. Алгоритмы поиска подстроки в строке: - алгоритм последовательного поиска (SF-алгоритм); - обобщённый SF-алгоритм. Получисленное сравнение строк: - метод Shift-And для решения задачи точного совпадения: о задача о счёте совпадений; о задача о счёте совпадений с джокерами; - алгоритм Рабина-Карпа: о варианты программной реализации схемы Горнера; о сигнатура строки, ложное совпадение; о хэширование, хэш-функция. Алгоритм Кнута-Морриса-Пратта: - префикс-функция, грань строки, наибольшая грань строки; -префикс-функция, ассоциированная с образцом, алгоритм вычисления массива граней. Алгоритм Хорспула: - таблица сдвигов; - алгоритм для вычисления элементов таблицы сдвигов. Алгоритм Бойера-Мура: - таблица сдвиг несовпадающих символов; - таблица сдвигов совпадающих суффиксов; - быстрый алгоритм вычисления таблицы сдвигов совпадающих суффиксов; - «наследники» алгоритма Бойера-Мура: о алгоритм Чжу-Такаоки; о алгоритм Бойера-Мура-Санди. Использование детерминированных конечных автоматов для поиска подстроки в строке: - конструирование конечного автомата с помощью суффикс-функции; - конструирование конечного автомата с помощью префикс-функции; - алгоритм Ахо-Корасик. Древовидные структуры для поиска подстроки в строке: - деревья цифрового поиска (DST-деревья); - TRIE-структуры; - TRIE-деревья бинарного поиска; - деревья граней; - суффиксные деревья. Некоторые задачи вычислительной молекулярной биологии: - задача о загрязнении ДНК; - задача выбора праймера; - задача о нахождении всех максимальных повторов.
Этот граф позволяет в дальнейшем отбирать содержание обучения (конкретизировать его) в зависимости от уровня обучаемых, а также в условиях практических ограничений как по времени, так и по используемым компьютерным средствам обучения.
Теперь выскажем некоторые методические замечания по описанному содержанию обучения, которые позволяют уточнить некоторые элементы графа содержания.
1. В одном из разделов приходится использовать конечные автоматы Рабина-Скотта, поэтому необходимо привести результаты отбора содержания обучения этому разделу дискретной математики, следуя [34]: Вспомогательный блок (базовые понятия теории графов): -неориентированный граф, ориентированный граф, помеченный граф, дополнение графа, простой граф, мультиграф, псевдограф. Основной блок (основные понятия): - недетерминированный конечный автомат Рабина-Скотта, конфигурация автомата, начальная и заключительная конфигурация; -язык в алфавите, определяемый (распознаваемый, допускаемый) автоматом; -детерминированный конечный автомат Рабина-Скотта, полностью определённый детерминированный автомат Рабина-Скотта; - способы задания автомата (таблица переходов, граф переходов, матрица переходов); - эквивалентные состояния конечного автомата, эквивалентные автоматы, алгоритм построения детерминированного конечного автомата Рабина-Скотта, эквивалентного заданному недетерминированному конечному автомату Рабина-Скотта. Задачный материал включает два класса задач: - определение языка в алфавите, распознаваемого заданным конечным автоматом; - построение конечного автомата, распознающего заданный язык в алфавите. Решение этих классов задач позволяет преподавателю выработать у обучаемых умения и навыки владения следующими понятиями и алгоритмами: - способы задания конечных автоматов Рабина-Скотта; - алгоритм построения детерминированного конечного автомата, эквивалентного заданному недетерминированному конечному автомату; - построение конечного автомата по праволинейной грамматике; - построение регулярного языка по заданному конечному автомату; - построение конечного автомата, распознающего данный язык.
2. Значительный интерес для методики обучения молекулярным вычислениям представляют советы специалистам по информатике, приведённые в [12, с. 606-607]: - изучайте «настоящую» биологию так много, как это возможно; - читайте книги по биологии и журналы, присутствуйте на биологических беседах и конференциях, беседуйте с биологами и серьёзно рассматривайте вычислительные задачи и абстрактные модели, уже определённые биологами; - не ограничивайтесь уже формализованными вычислительными задачами и построенными моделями и не разочаровывайтесь, если вы не можете сразу включить всю сложность биологических проблем в ваши формализованные задачи. После погружения в биологию постарайтесь выделить и изучать ваши собственные вопросы (особенно вопросы биологического происхождения), руководствуясь вашим пониманием биологии, целью безусловно решить «полную задачу» и вашим пониманием того, что возможно, а что нет в вычислительном отношении. - больше сосредотачивайтесь на биологическом качестве вычисления, а не исключительно на уменьшении затрат времени и памяти. Так как формализация задачи биологического происхождения может быть трудной, должно проверяться биологическое качество результатов, с возможным последовательным изменением формальной задачи.
Отбор содержания обучения алгоритмам на подпоследовательностях
Цепочки ДНК представлены строками, стикеры разделены между собой символом «-». Если стикер включен, то на соответствующем месте в чётной пробирке стоят символы, которые по смыслу будут комплементарны соответствующей цепочке со стикером. По методическому назначению данный интерпретатор является моделирующим ПС, по функциональному назначению является предметно-ориентированным ПС. Интерпретатор позволяет получить навыки самостоятельного приобретения знаний и умений, которые потребуются при дальнейшем изучении молекулярных алгоритмов, и является одним из средств обучения молекулярным вычислениям и используется в процессе обучения студентов кафедры «Информационных систем и программного обеспечения» с 2012 г.
Для эффективного обучения студентов новым вычислительным моделям на базе NBIC-технологий создан программный интерпретатор, позволяющий имитировать пробирки с цепочками ДНК и осуществлять различные операции с ними.
Воспользуемся схемой анализа компьютерного средства обучения аналогично 3.3. Интерпретатор молекулярных вычислений реализован на встроенном языке 1С:Предприятие версии 8.2. Для достижения методических целей программный код процедур и функций снабжен подробными комментариями. Интерпретатор может использоваться при наличии учебной или стандартной лицензии 1С с платформой 8.х. Системные требования для работы интерпретатора аналогичны требованиям для работы с учебной версией платформы 8.х.
Данное средство обучения позволяет продемонстрировать выполнение операций над цепочками ДНК, стикерами и моделировать классические алгоритмы в наглядной форме. Студент может самостоятельно конструировать набор операций для реализации классических алгоритмов, которые не представлены в интерпретаторе. Подход, при котором обучающийся может самостоятельно работать с интерпретатором, позволяет приобрести знания и умения, которые потребуются в дальнейшем непрерывном образовании.
Практика использования интерпретатора на языке 1С показывает, что у студентов возникает интерес к изучению молекулярных вычислений, к изучению языка 1С, к разработке программ, построенных с использованием разнообразного визуального взаимодействия с пользователем, что в свою очередь активизирует познавательную деятельность студентов.
Таким образом, данное средство обучения [51, 52] по методическому назначению является моделирующим ПС, по функциональному назначению является предметно-ориентированным ПС.
При работе с интерпретатором можно использовать следующие формы обучения: «лабораторная работа», «практические занятия», «семинар», «дистанционное обучение».
Перед использованием интерпретатора ДНК-вычислений на базе языка 1С, студенту рекомендуется ознакомиться со справкой к интерпретатору (см. Приложение №3).
К интерпретатору относится фрагмент содержания обучения, связанный с операциями над цепочками ДНК, стикерами, классическими алгоритмами, который представлен на рисунке ниже (см. Рис 47). Фрагмент содержания обучения, относящийся к операциям над цепочками ДНК, стикерами и классическими алгоритмами
Опишем структуру интерпретатора и особенности работы с ним. Главное окно интерпретатора состоит из четырех функциональных областей (см. Рис 48). Главное окно программы содержит:
Выполнять операции над ДНК-цепочками можно в режиме «реального времени», что позволяет моделировать реальные физические опыты, которые могут быть проведены в лабораторных условиях. Перед применением операций над цепочками ДНК студент должен знать следующие основные понятия: 1) пробирка – это мультимножество слов (конечных строк) над алфавитом {A,T,G,C}; 2) основные операции над ДНК молекулами: а) Слить. Объединяет содержимое двух пробирок, представленных мультимножествами, в одну пробирку, представленную мультимножеством (см. Рис 49). N Цепочка ДНК Количество N Цепочка ДНК Количество в) Обнаружить. Операция является предикатом и возвращает значение «Ложь», если пробирка пуста и возвращает значение «Истина» в противном случае. На экране интерпретатора выдается информация о наличии цепочек ДНК в пробирке и количестве различных видов ДНК (см. Рис 51). N Цепочка ДНК Количество г) Разделить (или извлечь). По данным пробирке N и слову w над алфавитом {A,T,G,C} изготовить две пробирки +(N,w) и –(N,w) такие, что +(N,w) состоит из всех цепочек в N, содержащих w в качестве (последовательной) подстроки, а – (N,w) состоит из всех цепочек в N, которые не содержат w в качестве подстроки. Результат операции представлен рисунке ниже (см. Рис 52). е) Выделить по префиксу (суффиксу). По данным в пробирке N и слову w, изготовить пробирку B(N,w) (соответственно E(N,w)), состоящую из всех цепочек в N, начало (соответственно конец) которых совпадает со словом w. Исходные данные для проведения операции и результат изображены на рисунке ниже (см. Рис 54). При выполнении операций над ДНК-цепочками в интерпретаторе можно по шагам продемонстрировать научные опыты, рассмотренные в Главе 2. Последовательность операций над заранее сгенерированными цепочками ДНК можно определить в файле и представить в виде следующей последовательности операций, записанной на метаязыке: 5) выделенные особенности языка программирования Haskell привели к значительному росту времени на разработку интерпретатора и ограничение его возможностей. Необходимость считывания данных с клавиатуры и необходимость генерации случайных пробирок, моделирование пробирок массивами, определения 123 разных типов функций, выполняющих похожие действия потребовало использования монад; 6) исходный код интерпретатора ввиду особенностей выбранного языка получился громоздким, сложным для анализа, понимания и внесения изменений. Ленивые вычисления, большая точность вычислений и другие особенности языка, приводят к увеличению (по сравнению с другими языками программирования) скорости выполнения программ, росту объема занимаемой памяти для вычислений.
Тем не менее, интерпретатор на языке Haskell был внедрен в процесс обучения молекулярным вычислениям студентов факультета информационных технологий в 2012 г. и создал основу для создания расширенного интерпретатора с поддержкой графики и работы с файлами на базе 1С. Апробация интерпретатора на языке 1С была выполнена на факультете информационных технологий на базе кафедры информационных систем и программного обеспечения в 2012 г.
Компьютерная реализация решения задачи о рюкзаке
Применяя написанную нами программу на встроенном языке 1С для реализации критерия Манна-Уитни мы получили, что гипотеза H0 отклоняется.
Таким образом, количество решенных задач четвертого уровня в контрольной работе с помощью интерпретатора ДНК-вычислений на языке 1С в третьей группе превосходит количество решенных задач при помощи интерпретатора на языке Haskell во второй группе.
Итак, по оценке сложности решения задач, можем утверждать, что без интерпретатора ДНК-вычислений можно решать задачи первого, второго и третьего уровня сложности. При помощи интерпретаторов ДНК-вычислений можно решать задачи четвертого уровня сложности. Однако студенты, у которых проходили практические занятия с интерпретатором ДНК-вычислений на языке 1С, успешнее решают задачи четвертого уровня сложности. Скорость решения задач. Было проведено измерение скорости получения правильного решения задач контрольной работы.
Мы воспользовались критерием Крускала–Уоллиса, с помощью которого оценили различия по времени решения задач контрольной работы одновременно между тремя выборками.
Напомним ограничения используемого критерия: при сопоставлении трёх выборок допускается, чтобы в одной из них n=3, а двух других n=2. Но при таких численных составах выборок мы сможем установить различия лишь на низшем уровне значимости (0,05). Для того, чтобы оказалось возможным диагностировать различия на более высоком уровне значимости (0,01), необходимо, чтобы в каждой выборке было не менее трёх наблюдений.
Мы выдвинули две гипотезы: H0: между выборками 1, 2, 3 существуют лишь случайные различия по времени решения задач контрольной работы. H1: между выборками 1, 2, 3 существуют неслучайные различия по времени решения задач контрольной работы. 146 В результате эксперимента получены следующие выборки: - первая группа: 90, 85, 87, 84, 80, 75, 90, 77 (в мин); - вторая группа: 85, 65, 74, 76, 67, 61, 82, 88 (в мин); - третья группа: 59, 64, 44, 54, 70, 66, 66, 71 (в мин). Применяя написанную нами программу на встроенном языке 1С для реализации критерия Крускала-Уоллиса мы получили, что гипотеза Но отклоняется, т.е. время решения задач в контрольной работе имеет неслучайные различия в группах 1, 2, 3. Следует отметить, что в первой группе были студенты, которые не уложились в отведённое для контрольной работы время. После эксперимента мы можем утверждать, что различия в выборке по времени решения не случайны. Первая группа без использования интерпретатора ДНК-вычислений решает задачи медленнее, третья группа с использованием интерпретатора ДНК-вычислений решает задачи быстрее.
Качество решения задач. При решении контрольной работы для задач второго уровня сложности во второй группе мы отслеживали причину возникновения ошибки: ошибка по невнимательности или ошибка вследствие незнания алгоритма решения задачи. При неправильном результате у студента уточняли ход решения задачи. В данном эксперименте мы оценивали количество ошибок вследствие невнимательности.
Спустя один месяц мы предоставили студентам аналогичную контрольную работу, в которой предложили решить задачи второго уровня сложности на бумаге без помощи интерпретаторов.
Для оценки улучшения или ухудшения качества решения задач мы воспользовались G-критерием знаков, который предназначен для установления общего направления сдвига исследуемого признака при этом в выборке должно быть не менее пяти студентов. Мы выдвинули две гипотезы: Но: преобладание типичного направления сдвига является случайным; Hi: преобладание типичного направления сдвига не является случайным. В результате эксперимента получены следующие выборки: - вторая группа с использованием интерпретатора ДНК-вычислений на базе языка Haskell: 1, 1, 0, 1, 1, 2, 1, 0, 1, 0 (количество ошибок); - вторая группа без использования интерпретатора ДНК-вычислений: 2, 2, 1, О, 2, 4, 3, 2, 1, 0 (количество ошибок). Применяя написанную нами программу на встроенном языке 1С для реализации G-критерия знаков, мы получили, что гипотеза Но отклоняется, т.е. имеются достоверные различия в двух выборках, а направление сдвига -отрицательное. Таким образом, мы утверждаем, что без использования интерпретатора ДНК-вычислений на базе языка Haskell ухудшается качество решения задач.
Правильность решения задач. Студентам первой группы мы предложили контрольную работу с задачами первого, второго и третьего уровня сложности, которые нужно было решать на бумаге (без использования интерпретаторов ДНК-вычислений). При этом мы записали количество правильно решенных задач.
На следующем занятии мы предложили аналогичную контрольную работу. При этом половина первой группы решала данные задачи на бумаге, а вторая половина группы решала задачи при помощи интерпретатора ДНК-вычислений на базе языка 1С. Мы воспользовались критерием Фишера для оценки степени различия количества правильных ответов между студентами. Выдвигаем две гипотезы: Но: первая и вторая выборка принадлежат генеральным совокупностям с одинаковыми дисперсиями; Hi: первая и вторая выборка принадлежат генеральным совокупностям с разными дисперсиями;
В результате эксперимента получены следующие выборки: - первая группа без использования интерпретаторов ДНК-вычислений: 12, 13, 11, 15, 8, 14, 10, 12 (количество правильных ответов); - первая группа с интерпретатором ДНК-вычислений на базе языка 1С: 14, 15, 13, 15, 12, 10, 11, 12 (количество правильных ответов). Применяя написанную нами программу на встроенном языке 1С для реализации F-критерия Фишера, мы получили, что гипотеза Но принимается, изменение средства обучения не влияет на количество правильных ответов по задачам первого, второго и третьего уровня сложности.
После выполнения экспериментов мы оценили эффективность обучения при использовании различных средств обучения. Без использования интерпретаторов получена наименьшая эффективность обучения за счёт снижения сложности решаемых задач, скорости решения задач и качества решения задач. Наибольшая эффективность обучения достигнута с использованием интерпретатора ДНК-вычислений на базе языка 1С за счёт увеличения сложности решаемых задач и скорости решения задач.