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

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

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

ДНК

§2.3. Отбор содержания обучения алгоритмам поиска подстроки в строке

§2.4. Отбор содержания обучения алгоритмам на подпоследовательностях

§2.5. Новая реализация алгоритма поиска наибольшей общей

подпоследовательности как фрагмент содержания обучения

Выводы по главе 2

ГЛАВА 3. СРЕДСТВА ОБУЧЕНИЯ МОЛЕКУЛЯРНЫМ ВЫЧИСЛЕНИЯМ

§3.1. Классификация средств обучения

§3.2. Платформа 1С как средство обучения программированию

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

средство обучения

§3.4. Интерпретатор языка пробирок на языке 1С как средство обучения

§3.5. Компьютерная реализация опыта Эдлмана как средство обучения

§3.6. Компьютерная реализация решения задачи о выполнимости

пропозициональных формул

§3.7. Компьютерная реализация решения задачи о рюкзаке

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

§3.9. Организация и проведение педагогического эксперимента

Выводы по главе 3

ЗАКЛЮЧЕНИЕ

Библиография

ПРИЛОЖЕНИЕ 1. ГРАФЫ СОДЕРЖАНИЯ ОБУЧЕНИЯ

ПРИЛОЖЕНИЕ 2. ТРЕБОВАНИЯ, ПРЕДЪЯВЛЯЕМЫЕ К ЗНАНИЯМ И

УМЕНИЯМ СТУДЕНТОВ

ПРИЛОЖЕНИЕ 3. СПРАВОЧНАЯ ИНФОРМАЦИЯ К РАЗРАБОТАННОМУ ИНТЕРПРЕТАТОРУ ДНК-ВЫЧИСЛЕНИЙ НА БАЗЕ ЯЗЫКА 1С

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

ВВЕДЕНИЕ

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

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

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

2) в настоящее время содержание обучения, относящееся к понятию «вычислимость», содержит класс моделей, которые мы называем «классическими вычислительными моделями» и источником которых является математика. Однако Природа обладает внутренними средствами, позволяющими реализовывать вычислительные процессы более эффективно. В учебном процессе подобные вычислительные модели пока не находят отражения в учебных и методических пособиях. Перечислим несколько существующих научных изданий, в которых затрагиваются вопросы молекулярных вычислений [12, 15, 33, 37, 38, 58, 56] и методичесские исследования Т.С. Стефановой [60, 61];

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Первая группа задач {теоретического характера):

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В первой главе определяются понятия «междисциплинарность», «полидисциплинарность», «трансдисциплинарность», которые позволяют выделить современные акценты в классическом понятии «межпредметность». Далее рассматривается взаимовлияние информационных технологий, биотехнологий, нанотехнологий и когнитивной науки, получившее название ЫВЮ-конвергенция; определено место молекулярных вычислений в ЫВ1С-конвергенции и рассмотрено понятие «природные вычисления»; определено понятие «методические связи».

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

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

F-критерия Фишера, сравнение средних значений с помощью t-критерия Стьюдента).

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

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

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

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

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

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

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

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

ГЛАВА 1. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПОСТРОЕНИЯ МЕТОДИЧЕСКОЙ

СИСТЕМЫ ОБУЧЕНИЯ МОЛЕКУЛЯРНЫМ ВЫЧИСЛЕНИЯМ

§1.1. Парадигмы мсждисциплинарностн

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

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

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

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

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

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

Термин «трансдисциплинарность» первоначально начал использоваться, центром современной антропологии Э. Морена в Париже. При этом Э. Морен, предлагает говорить о полидисциплинарных исследовательских полях, междисциплинарных исследованиях и трансдисциплинарных стратегиях исследования.

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

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

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

Трансдисциплинарность (по Б. Николеску) базируется на следующих методологических постулатах, принципиально отличающих её от междисциилинарность и полидисциплинарности:

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

2) логика, использующая принцип дополнительности (логика включённого третьего): трансдисциплинарность не противопоставляет, а объединяет, соединяет то, что рассматривалось как противоположное;

3) сложность: Трансдисциплинарность пытается понять сложность реальности и научиться справляться с ней.

Таким образом, трансдисциплинарность — это теоретическая попытка «трансцендировать» дисциплины и тем самым отреагировать на специализацию -процесса, ведущего к росту фрагментации и раздробления знания.

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

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

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

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

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

§1.2. NBIC-конвергенции как новая технологическая парадигма

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

Особенно интересным и значимым представляется выяснение взаимовлияния информационных технологий, биотехнологий, нанотехнологий и когнитивной науки. Данное явление получило название NBIC-конвергениия (по первым буквам предметных областей: N - «нано», В - «био», I - «инфо», С — «когно»). Термин NBIC-конвергенция впервые упоминается в 2002 г. в отчете «Converging Technologies for Improving Human Performance» для Национального Научного Фонда [99].

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

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

В дальнейшем будем опираться на следующее понимание понятия «нанотехнологий».

Нанотехнология (от гр. nannos - карлик) [22, с. 238] - это отрасль микроэлектроники, занимающаяся созданием микроскопических объектов (не более одной миллиардной доли исходных единиц). На базе нанотехнологий появляется техника, основанная на микроскопических роботокомплексах.

Переход от «микро-» к «нано-» - это качественный переход от манипуляции веществом к манипуляции отдельными атомами.

Когда речь идёт о развитии нанотехнологии, имеются в виду три направления:

1) изготовление электронных схем (в том числе и объёмных) с активными элементами, размерами сравнимыми с размерами молекул и атомов;

2) разработка и изготовление наномашин;

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

Изобразим схему конвергенции ЫВ1С-технологий, описывающую объекты, с помощью которых одна технология воздействует на другую (см. Рис 1).

Рис 1. Конвергенция ЫВЮ-технологий

Из четырёх описываемых областей наиболее развитой является «I» (информационно-коммуникационные технологии), и она на данный момент чаще всего поставляет инструменты для развития других; в частности, это возможность компьютерного моделирования различных процессов.

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

§1.3. Молекулярные вычисления в NBIC-тexнoлoгияx

Определим место молекулярных вычислений в ЫВ1С-конвергенции; для этого определим смысл термина «биотехнология».

По мнению Т.Г. Воловой [9], «в расширительном толковании биотехнология- это все технологические процессы, в которых используются живые организмы». Т.Г. Волова рассматривает две крайности: одна заключается в том, что при таком понимании термина все сельское хозяйство, начиная с первобытных форм, можно включить в это понятие; противоположная крайность — ограничить понятие «биотехнология» генно-инженерными манипуляциями. По утверждению Т.Г. Воловой, если отказаться от крайних позиций, то биотехнологию можно определить по её основному признаку - управлению биотехнологическими процессами.

Биотехнологии в составе КВ1С-конвергенции предоставляют теоретическую основу для развития информационных технологий, нанотехнологий и когнитивной науки.

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

Р. Твайман [105] опубликовал различные модели механизмов использования ДНК для нанотехнологий. В свою очередь были рассмотрены и обратные механизмы - модификация ДНК при помощи механического воздействия на наноуровне. Ещё 50 лет назад биоорганические объекты конструировались опытным путем, их исследование шло эмпирическим путем. В настоящее время

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

Более слабый характер взаимодействия наблюдается между биологией и

информационными_технологиями. Однако возникло несколько

Список литературы диссертационного исследования кандидат наук Ракитин, Александр Георгиевич, 2015 год

Библиография

1. 1С: Предприятие 8 (модель работы с БД) [Электронный ресурс] // Модель работы с БД. 2015. URL: http://v8.lc.ru/overview (дата обращения: 4.04.2015).

2. Абрамян М.Э. Электронный задачник по программированию: [сайт]. 2014. URL: http://ptaskbook.com/ru/ptforbio/index.php (дата обращения:

4.09.2014)

3. 1С: Предприятие 8 (обработка): [сайт]. 2015. URL: http://v8.lc.ru/overview/Term_000000118.htm (дата обращения:

4.04.2015).

4. Баранов В.И., Стечкин Б.С. Экстремальные комбинаторные задачи и их приложения. М.: Наука, 1989. 160 с.

5. Бокуть С.Б., Герасимович Н.В., Милютин A.A. Молекулярная биология: молекулярные механизмы хранения, воспроизведения и реализации генетической информации. Минск: Выш. шк., 2005. 463 с.

6. Бордовский М., Екишева С. Задачи и решения по анализу биологических последовательностей. Ижевск: НИЦ Регулярная и хаотическая динамика: Институт компьютерных исследований, 2008. 440 с.

7. Бурков В.Н., Горгидзе И.А., Ловецкий С.И. Прикладные задачи теории графов. Тбилиси: Вычислительный центр АН ГССР, 1974. 236 с.

8. Вербицкий A.A. Активное обучение в высшей школе: контекстный подход. М.: Высшая школа, 1991. 353 с.

9. Волова Т.Г. Биотехнология. Новосибирск: Изд-во Сибирского отделения РАН, 1999.252 с.

10. Воронов В.К., Подоплелов A.B. Современная физика. М.: КомКнига, 2005. 512 с.

11. Габец А.П., Гончаров Д.И. Профессиональная разработка в системе 1 С: Предприятие 8. СПб.: 1С-Паблишинг, 2007. 808 с.

12. Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология. СПб.: Невский Диалект: БХВ-Петербург, 2003. 654 с.

13. Государственный образовательный стандарт высшего профессионального образования. Требования к обязательному минимуму содержания основной образовательной программы подготовки бакалавра по направлению 540200 - физико-математическое образование. М.: Госкомитет РФ по высшему образованию, 2000.

14. Дружинин В.В., Конторов Д.С. Проблемы системологии. М.: Сов. радио, 1976. 296 с.

15. Дурбин Р., Эдди Ш., Крог Л., Митчисон Г. Анализ биологических последовательностей. Ижевск: НИЦ Регулярная и хаотическая динамика: Институт компьютерных исследований, 2006. 480 с.

16. Загвязинский В.И. Дидактика высшей школы: Текст лекций. Челябинск: ЧПИ, 1990. 98 с.

17. Зыкова Н.Ю., Лапкова О.С., Хлоповских Ю.Г. Методы математической обработки данных психолого-педагогического исследования. Воронеж: ВГУ, 2008. 48 с.

18. Канторович Л.В., Плиско В.Е. Системные идеи в математике // Философско-методологические основания системных исследований. М.: Наука, 1983. С. 56-82.

19. Касьянов М. Постановление Правительства РФ о присуждении премии Правительства РФ 2001 г. в области науки и техники // Российская газета: электрон, вере. газ. 2002. № 54. URL: http://www.rg.ru/oficial/doc/postan_rf/175.shtm.

20. Киркпатрик Д.Л., Киркпатрик Д.Д. Четыре ступеньки к успешному тренингу. М.: Эйч Ар Медиа, 2008. 128 с.

21. Князева E.B. Настоящее и будущее трансдисциплинарных исследований // Будущее фундаментальной науки: Концептуальные, философские и социальные аспекты проблемы. М.: КРАСАНД, 2011. С. 248-258.

22. Комлев Н.Г. Словарь иностранных слов. М.: Эксмо, 2006. 672 с.

23. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 1999. 960 с.

24. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: Вильяме, 2010. 1296 с.

25. Крик Ф. Безумный поиск: личный взгляд на научное открытие. Ижевск: Институт компьютерных исследований, 2004. 192 с.

26. Ланина И.Я. Методика формирования познавательного интереса школьников в процессе обучения физике: автореф. дис. Л., 1986.

27. Лаптев В.В. Теоретические основы методики использования современной электронной техники в обучении физике в школе: автореф. дис. Л., 1989. 35 с.

28. Левенштейн В.И. Двоичные коды с исправлением выпадений, вставок и замещений символов // ДАН СССР. Т. 163. 1965.

29. Левитин A.B. Алгоритмы: введение в разработку и анализ. М.: Вильяме, 2006. 576 с.

30. Ллойд Э., Ледерман У., Тюрин Ю.Н. Справочник по прикладной статистике. М.: Финансы и статистика, 1989. Т. 1.510 с.

31. Ллойд Э., Ледерман У., Тюрин Ю.Н. Справочник по прикладной статистике. М.: Финансы и статистика, 1989. Т. 2. 526 с.

32. Мак-Коннел Д. Анализ алгоритмов. Активный обучающий подход. М.: Техносфера, 2009. 416 с.

33. Малинецкий Г.Г., Науменко С.А. Вычисление на ДНК. Эксперименты. Модели. Алгоритмы. Инструментальные средства [Электронный ресурс] // ИПМ им. М.В.Келдыша. М., 2005. URL:

http:/Av\v\v.keldysh.ru/papers/2005/prep57/prep2005_57.html (дата обращения: 01.06.2014).

34. Муеинова E.B. Методика обучения будущих учителей информатики дискретной математике: автореф. кандид. пед. наук. СПб., 2001. 19 с.

35. Наследов А.Д. Математические методы психологического исследования. Анализ и интерпретация данных. СПб.: Речь, 2012. 392 с.

36. Окулов С.М., Пестов O.A. Динамическое программирование. М.: БИНОМ. Лаборатория знаний, 2012. 296 с.

37. Окулов С.М. Алгоритмы обработки строк. М.: БИНОМ. Лаборатория знаний, 2009. 255 с.

38. Паун Г., Розенберг Г., Саломаа А. ДНК-компьютер. Новая парадигма вычислений. М.: Мир, 2004. 528 с.

39. Петровский А.Б. Основные понятия теории мультимножеств. М.: Едиториал УРСС, 2002. 80 с.

40. Порублев И.Н., Ставровский А.Б. Алгоритмы и программы. Решение олимпиадных задач. М.: Вильяме, 2007. 480 с.

41. Прайд В., Медведев Д.А. Феномен NBIC-конвергенции: Реальность и ожидания [Электронный ресурс] // Российское трансгуманистическое движение. 2008. URL: http://transhumanism-russia.rU/content/view/498/l 16 (дата обращения: 1.06.2014).

42. Радченко М.Г. 1С предприятие 8.1. Практическое пособие разработчика. Примеры и типовые приемы. М: 1С-Паблишинг, 2007. 512 с.

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

44. Ракитин А.Г., Стефанова Т.С., Швецкий М.В. Интерпретатор языка пробирок для ДНК-вычислений // Научное мнение, 2013. № 10. С. 214219.

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

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

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

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

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

50. Рекомендации по преподаванию информатики в университетах: Computer Science / пер. с англ. М.Е. Зверинцева [и др.]. СПб., 2002. 372 с.

51. Роберт И.В., Панюкова C.B., Кузнецов А.А., Кравцова А.Ю. Информационные и коммуникационные технологии в образовании. М.: Дрофа, 2008.312 с.

52. Роберт И.В. Современные информационные технологии в образовании: дидактические проблемы; перспективы использования. М.: Школа-пресс, 1994. 205 с.

53. Романовский И.В. Дискретный анализ. СПб.: Невский диалект: БХВ-Петербург, 2004. 320с.

54. Руннон Р. Справочник по непараметрической статистике. Современный подход. M.: Финансы и статистика, 1982. 198 с.

55. Сачков В.Н. Введение в комбинаторные методы дискретной математики. M.: Наука, 1982.384 с.

56. Сетубал Ж., Мейданис Ж. Введение в вычислительную молекулярную биологию. М. Ижевск: НИЦ Регулярная и хаотическая динамика: Институт компьютерных исследований, 2007. 420 с.

57. Сидоренко Е.В. Методы математической обработки в психологии. СПб.: Речь, 2002. 350 с.

58. Смит Б. Методы и алгоритмы вычислений на строках. М.: Вильяме, 2006. 496 с.

59. Ставровский А.Б. Турбо Паскаль 7.0. Киев: Издательская группа BHV, 2000. 400 с.

60. Стефанова Т.С., Швецкий М.В. Теория алгоритмов: упражнения по неклассическим вычислительным моделям (ДНК-вычисления, квантовые вычисления). СПб.: Интерлайн, 2008. 476 с.

61. Стефанова Т.С. Методика обучения неклассическим вычислительным моделям бакалавров физико-математического образования: автореф. кандид. пед. наук. СПб., 2008. 22 с.

62. Суходольский Г.В. Математические методы в психологии. Харьков: Гуманитарный Центр, 2006. 284 с.

63. Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. М.: Наука, 1987. 288 с.

64. Хаубольд Б., Вие Т. Введение в вычислительную биологию. Эволюционный подход. М. Ижевск: НИЦ Регулярная и хаотическая динамика: Институт компьютерных исследований, 2006.456 с.

65. Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си. М.: Финансы и статистика, 2004. 464 с.

66. Adleman L.M. Computing with DNA // Scientific American. 1998. C. 34-41.

67. AignerM. Combinatorial theory. N.Y.: Springer-Verlag, 1979.

68. Aiken R., Balasubrahmanian A., Brauer W., Buckingham D., Hebenstreit J., Khvilon E., Levrat B., Lovis F., Murray-Lasso M., Turner J., Weert van T. A Modular Curriculum in Computer Science, UNESCO-IFIP, 1994. ED/94AVS/13.

69. Apostolico A., Guerra C. The longest common subsequence problem revisited //Algorithmica. 1987. Vol. 2. C. 315-336.

70. Baeza-Yates R., Gonnet G. A new approach to text searching // ACM. 1992. Vol. 35. C. 74-82.

71. Benenson Y., Paz-Elizur T., Adar R., and Keinan E. Programmable and autonomous computing machine made of biomolecules // Nature. 2001. No 414. C. 430-434.

72. Bergey J et al. Enterprise Framework for the Disciplined Evolution of Legacy Systems, Carnegie Millon University, Pittsburgh, Technical Report ESC-TR-97-007. 1997.

73. Boyer R.S., Moore J.S. A Fast String Searching Algorithm // Communication of ACM. 1977. Vol. 20. No 10. C. 762-772.

74. Carlson B. MAYA-II and Molecular computing // Biotechnology Healthcare. 2007. Vol. 4. C. 10-11.

75. Dershowitz N., Manna Z. Proving termination with multiset ordering // Communication of ACM. 1979. Vol. 22. No 8. C. 465-476.

76. Fischer M., Paterson M. String-matching and other products // Complexity of Computation / SIAM-AMS Proc. 1974. C. 113-125.

77. Gotoh O. An improved algorithm for matching biological sequences // J. Mol. Biol. 1982. No 162. C. 705-708.

78. Hirschberg D.S.A. A linear space algorithm for computing maximal common subsequences//CASM. 1975. No 18-6. C. 341-343.

79. Hirshberg D.S.A. Algorithms for the longest common subsequence problem // JASM. 1977. No 24-4. C. 664-675.

80. Horspool R.N. Practical fast searching in strings // Software-Practice & Experience. 1980. Vol. 10. No. 6. C. 501-506.

81. Huet G., Oppen D.C. Equations and rewrite rules: a survey // R.Book (Ed.). Formal languages perspectives and open problems. N.Y.: Academic Press, 1980.

82. Hunt J.W., Szymansski T.G. A fast algorithm for computing longest common subsequences // CASM. 1977. No 20-5. C. 350-353.

83. Jacobson G., Vo K.P. Heaviest increasing/common subsequence problems // Proc. 3-rd Symp. on Combinatorial Matching Conference. Lecture Notes in Computer Science. 1992. No 644. C. 52-65.

84. Jouannaud J.P., Lescanne P. On multiset ordering // Information Processing Letters. Vol. 1982. 15. No 2, C. 57-63.

85. Karp R.M., Rabin M.O. Efficient randomized pattern-matching algorithms // IBM J. Res. Develop. 1987. Vol. 31. No 2. C. 249-260.

86. Knuth D.E., Morris J., and Pratt V.R. Fast Pattern Matching in Strings // SIAM J. of Computing. 1977. Vol. 6. No 2. C. 323-350.

87. Knuth D.E. The art of computer programming. V.2. Seminumerical algorithms. Reading: Addison-Wesley, 1969.

88. Kurtz S. Kurtz S. Fundamental algorithms for a declarative pattern matching system. Universität Bielefeld, 1995. 237 c.

89. Landau G.M., Vishkin U. Efficient string matching with k mismatches // TCS 43. 1986. C. 239-249.

90. Landau G.M., Vishkin U. Introducing efficient parallelism into approximate string matching and a new serial algorithm // Proceedings of the 18th ACM Symposium on the Theory of Computing. 1986. C. 220-230.

91. Levenshtein V.l. Binary codes capable of correcting deletions, insertions and reversals // Cybernetics & Control Theoiy. 1966. No 10-8. C. 707-710.

Lian Y., Zhang M. Knapsack Problem based on DNA Encoding and Computing Method Solution to the 0-1 //journal of computers. 2013. Vol. 8. No 3. C. 669-675.

Lipton R. Using DNA to Solve NP-Complete Problems // Science. 1995. C. 542- 545.

Myers G. W. A fast bit-vector algorithm for approximate string matching based on dynamic programming // J ACM,, 1999. No 46-3. C. 395-415. Myers G.W. An O (nd) difference algorithm and its variations // Algorithmica. 1986. Vol. 1. C. 251-266.

Nayebi A. Fast matrix multiplication techniques based on the Adleman-Lipton model // International Journal of Computer Engineering Research. 2012. Vol.3. No l.C. 10-19.

Needleman S.B., Wunsch C.D. A General Method Applicable to the Search for Similarities in the Amino Acid Sequence of Two Proteins // J. Mol. Biol. 1970. No 48. C. 443-453.

Pevzner P., Waterman M. Matrix longest common subsequence problem, duality and Hilbert bases // Proc. 3-rd Symp. on Combinatorial Matching Conference. Lecture Notes in Computer Science. 1992. Vol. 644. C. 79-89. Roco M., Bainbridge W. Converging Technologies for Improving Human Performance: Nanotechnology, Biotechnology, Information Technology and Cognitive Science. Arlington: Springer, 2002. 488 c.

Rothemund P.W.K., Papadakis D., and Winfree E. Algorithmic self-assembly

of DNA Sierpinski triangles // PLoS Biol. 2004. No. 2

Sertel M., Slinko A. Ranking committees, words or multisets (unpublished)3

2003.

Smyth B. Computing patterns in strings. UK: Addison Wesley, 2003.423 c. Smyth T.F., Waterman M.S. Identification of common molecular subsequences//J. Mol. Biol. 1981. Vol. 147. C. 195-197.

104. Sunday D.M. A Very Fast Substring Search Algorithm // Communication of ACM. 1990. Vol. 33. No. 8. C. 132-142.

105. Twyman R. Principles of Proteomics. N.Y.: BIOS Scientific Publishers, 2004. 266 c.

106. Ukkonen E. Algorithms for approximate string matching // Information & Control. 1985. Vol. 64. C. 110-118.

107. Wagner R.A., Fischer M.J. The string-to-string correction problem // Journal of the ACM. 1974. Vol. 21. No. 1. C. 168-173.

108. Weiderman N et al. Approaches to Legacy System Evolution, Software Engineenig Institute, Technical report CMU/SEI-97-TR-014. 1997.

109. Wu S., Manber U. Fast text seaching allowing errors // CACM. 1992. Vol. 35-10. C. 83-91.

110. Yager R.R. On the theory of bags // International Journal of General Systems. 1986. Vol. 13. C. 23-37.

ПРИЛОЖЕНИЕ 1. ГРАФЫ СОДЕРЖАНИЯ ОБУЧЕНИЯ

Приведём структуру содержания обучения разделу «Цепочки ДНК и их моделирование»:

X

Стикеры I

Операции со стикераии

1. Слить;

2. Разделить;

3. Включить;

4. Очистить.

Моделирвамие классических алгоритмов

7

Опыт Л. Эдлиана (хадача о гамилмтжовои пути)

1=

ПуриныN

Аэотистие основания

• [Гк(р»»тд*в1

Одюцслочечнме Д* и РНК

->1

Кодон}—• №м«кислота I I

-I

Пртцт комплементарное ти Уотсона-Крика

й-Т. Г Ц

Генеяичсски/) код

Генетическая информация о белках

X

№

(двухцепочечная молекула)!-^

■Ц

г

Операции м?д ЦИХ:

1. Разделение и соеди-маме цепочек;

2. Удтнемие ДК;

3. Укорочение ДНК;

4. Разрезание ДНК; Сишка ДК;

Б. Модификация нуклео-

тидов ДНК; 7. Размюаегме ДНК; В. Секвеннровате.

Опыт Липтона (задача о выполнимости)

И«

(двухцепочечная молекула)

нодооикацмя

Комплементарный палиндром

Моделирование "миль-пи" в РНК

Моделирование структура "крепла" в Д НК

Задача о рюкзаке

т

Нутация в ДК

И)-с

Центральная догиа молекулярной биологии

Самопроизвольные нутации Индицированные мутации

------ — ---------

Мутация со сдвигом рамки

■Горячие точки]

ЕГЧ-

г-(Томечие ицтачжК /—1-ч /—1—\

I '-' ПЬсерция! 1Делеция1

|транэ>«у<я|

Приведём структуру содержания обучения разделу «Операции над цепочками ДНК»:

* Операции над &КК

— Разделение и соединение ЦИК

t- Денатурация I— Точка плавления

* Ренатурация

— Удлинение ЦИК

— Одноцепочечная матрица

— Праймер

— Полимераза

I— Терминальная трансфераза

— Укорочение ЦИК

t* ДНК-нуклеазы (ферменты)

• Экзонуклеазы

t* Экзонуклеаза III

• Экзонуклеаза BalSl

— Разрезание ЦИК

— Эндонуклеаза S1

t* Разрезание одинарных цепочек

* Разрезание двухцепочечных молекул Рестрикционная эндонуклеаза (рестриктаза)

(—♦ Рестриктаза EcoRI

t» Сайт узнавания

* TVin разреза (зигзагообразный) |— Рестриктаза Xnal

* Сайт узнавания

* Тип разреза (зигзагообразный)

* Множественность разрезов

— Рестриктаза Smal

t- Сайт узнавания

* TVin разреза (прямой)

— Рестриктаза Pstl

t* Сайт узнавания

* Тип разреза (зигзагообразный)

— Рестриктаза Hgal

t* Сайт узнавания

* TVin разреза (зигзагообразный)

— Снивка ЦИК '— Сыивание

— "Липкие" концы

— Насечка

— Рестриктаза Хта1

— Рестриктаза Нра11 ДНК-лигаза (фермент)

"Прямые" концы

* Рестриктаза 8та1

* Терминальная трансфераза

* ДНК-лигаза (фермент)

— Модификация нуклеошдов ЦИК

Метилаза (фермент)

— Размножение ЦИК

Е. Денатурация

* Праймирование

* Удлинение

Полимераза

— Секвенирование

Метод Сэнгера

Приведем структуру содержания обучения по разделу «Мультимножества»:

* Мультимножество —* Характеристики мультимножеств кратность

характеристическая функция моцность мультимножеств —* п-множество

1— т-мультимножество, порождённое множеством —* Операции над мультимножествами

— пересечение

— объединение

— арифметическая сумма

— арифметическая разность

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

— дополнение

— арифметическое произведение

— умножение на число I- прямое произведение

— Предикаты

I—* включение мультимножеств

Приведем структуру содержания обучения по теме «Опыт Л. Эдлмана»

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

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

Множество состояний -1—

Входной алфавит 1==

Отношение комплементарности Уотсона-Крика

Функции переходов

Начальное состояние 1

Конечный автомата Уопсона-Крика

Множество заключительных состояний

I............................J

Для каждой обозреваемой пари не более одного состояния

Недетерминированный конечный автомат Уотсона-Крика

Детерминированный конечный автомат Уотсона-Крика

Основные понятия теории графов

Способы задания конечных автоматов!

Регулярные языки и выражения

и

Автоматная диаграмма

Основы дискретной математики

Матрица переходов

Таблица переходов

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

Магазинный автомат Уотсона-Крнка

ПРИЛОЖЕНИЕ 2. ТРЕБОВАНИЯ, ПРЕДЪЯВЛЯЕМЫЕ К ЗНАНИЯМ И

УМЕНИЯМ СТУДЕНТОВ

1. ДНК-вычисления: программное моделирование ДНК и РНК. Знать понятия: ДНК, РНК, нуклеотид, азотистые основания (пурины, пиримидины); принцип комплементарности Уотсона-Крика; палиндром, комплементарный палиндром, структура шпильки в РНК, структура креста в ДНК; мутация, самопроизвольная (спонтанная) мутация, индуцированная мутация, точечная мутация (транзиция, трансверсия), мутация со сдвигом рамки считывания (инсерция, делеция); сайт, горячая точка; генетический код, кодон, свойства генетического кода.

Знать: основы одного из императивных или функциональных языков программирования (простейшие и фундаментальные типы данных).

Уметь: составлять простейшие программы на любых языках программирования (например, LISP и С), моделирующие ДНК и РНК.

2. ДНК-вычисления: операции над ДНК, моделирование операций над ДНК. Знать понятия: основные операции над ДНК: разделение и соединение

цепочек, удлинение, укорочение, разрезание, сшивка, модификация нуклеотидов, размножение, секвенирование.

Знать: основы одного из языков программирования высокого уровня (простейшие и фундаментальные типы данных).

Уметь: конструировать программы, моделирующие операции над ДНК и

РНК.

3. Компьютерное моделирование ДНК-компьютера: опыт Л. Эдлмана. Знать понятия: ДНК-компьютер; параллелизм; пробирка, операции над

пробирками: слить, размножить, обнаружить, разделить, разделить по длине,

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

Знать: основные понятия теории графов (ориентированный граф, вершина, ребро, дуга, гамильтонов путь), задача коммивояжера (о поиске гамильтонова пути в графе); основные понятия темы «Слова в алфавите» (подслово, префикс, суффикс); принцип комплементарности Уотсона-Крика.

Уметь: конструировать программы на метаязыке ДНК-вычислений; решать задачи, связанные с использованием интерпретатора, моделирующего опыт JT. Эдлмана; применять математические пакеты (MathLAB, Maple) для решения задачи о поиске гамильтонова пути (задачу коммивояжера).

4. Стнкерная модель молекулярных вычислений. Знать понятия: стикерная модель, запоминающая цепочка, стикер (цепочка-наклейка), запоминающий комплекс, включение подцепочки, выключение подцепочки; интерпретация стикерной системы; операции над стикерными системами: слить, разделить, очистить, включить; вычисление в стикерной системе; стикерная машина.

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

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

Знать понятия: детерминированный и недетерминированный конечный автомат Уотсона-Крика, сильно связный автомат; язык в алфавите, определяемый (распознаваемый, допускаемый) автоматом.

Знать: способы задания конечных автоматов (автоматная диаграмма переходов (граф), таблица переходов, матрица переходов); методы построения детерминированного и недетерминированного автомата Уотсона-Крика по

регулярному выражению; методы по преобразованию детерминированного и недетерминированного автомата Уотсона-Крика в регулярное выражение; принцип комплементарности Уотсона-Крика.

Уметь: решать задачи с использованием программы, моделирующей детерминированный и недетерминированный конечные автоматы Уотсона-Крика; моделировать конечные автоматы Уотсона-Крика на различных языках программирования; конструировать конечные автоматы Уотсона-Крика в системе .ШЬАР.

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

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

Знать: способы задания магазинных автоматов (автоматная диаграмма переходов (граф), таблица переходов, матрица переходов); способы определения (допущения) языка МП-автоматом: допустимость по заключительному состоянию, допустимость по пустому магазину.

Уметь: решать задачи с использованием программы, моделирующей детерминированный магазинный автомат Уотсона-Крика; моделировать магазинные автоматы Уотсона-Крика на различных языках программирования; строить магазинные автоматы Уотсона-Крика в системе 1РЬАР.

ПРИЛОЖЕНИЕ 3. СПРАВОЧНАЯ ИНФОРМАЦИЯ К РАЗРАБОТАННОМУ ИНТЕРПРЕТАТОРУ ДНК-ВЫЧИСЛЕНИЙ НА БАЗЕ ЯЗЫКА 1С

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

П х

Действия 4 I Настройки

0 Генерация 3 Обнаружить 1 . .1 В Выделить по префиксу' 9 Модифицировать Рс Разделить 1

1 Слить 4. Разделить 7 Выделить по суффикс/ Р Ренатурашя Бс Вюжчить

2 Размножить 5 Выделить по длине 8. Помыть пробирку Д. Денатурация Ос Очистить

.Двойные

* £тжерй

Активная пробирка 2

Разделите!*. 3 С

^ Открыть Файл Г литааГХпасси

N Цепочка ЛИК Цепочка ДНК2

Количество

N Цепочка ДНК Цепочка ДНК2

Кошчествв N Цяточка ДНК

Цепочка ДНК2

Количество

N Цепочка ДНК Цепочка ДНК2

№з!*нество

Цепочка ДНК Цепочка ДНК2

Количество

Цепочка ДНК Цепочка ДНК2

Количество

(й'чЗ* Ой & К |3 & Содержание Индекс Поиск

_^ПХ

ДНК

Обработка "ДНК-вычисления" позволяет моделировать операции с пробирками.

Таблицы моделируют содержимое пробирки. Активная пробирка подсвечена серым иветом. При операциях, в которых участвуют две пробирки, вторая пробирка подсвечивается синим цветом. Для управления активными пробирками используйте кнопки "1","2","3","4","5","6", для переключения между собой активных пробирок, используйте также кнопку с пиктограммой "обратные стрелки". Строки в таблицах моделируют нити ДНК.

1. Моделирование операций для одмослиральной ДНК:

• (0. Генерация) Получить случайную пробирку (вспомогательная функция):

• (1. Слить) "Слить";

• (2. Размножить) "Размножить";

• (3. Обнаружить) "Обнаружить";

• (4. Разделить) "Разделить";

• (5. Выделить по длине) "Выделить по длине";

• (6. Выделить по префиксу) "Выделить по префиксу";

• (7. Выделить по суффиксу) "Выделить по суффиксу";

• (8. Помыть пробирку) "Помыть пробирку" (вспомогательная функция);

• (9. Модифицировать) "Модифицировать".

В скобках указаны наименования кнопок, которые выполняют указанную операцию.

2. Моделирование операций с двуспиральной ДНК (необходимо установить флаг: "двойные цепочки"):

• (1. Ренатурация) "Размножить";

• (2. Денатурация) "Денатурация".

В скобках указаны наименования кнопок, которые выполняют указанную операцию.

3. Моделирование операций со стакерами (необходимо установить флаги: "двойные цепочки" и "стакеры"):

• (1. Слить) "Слить";

• (Рс Разделить) "Разделить";

• (Вс Включить) "Включить";

• (Ос Очистить) "Очистить";

В скобках указаны наименования кнопок, которые выполняют указанную операцию.

] Справка ДНК _ □ X

т О £) ¡3^ Содержание Индекс Пои«

4. Моделирование классических алгоритмов и использование интерпретатора для выполнение команд из файла.

Для моделирования классических алгоритмов следует использовать кнопку "Открыть файл". Файл должен быть в кодировке "1)пюос1ен и иметь расширение "1x1". Для выполнения команд из файла следует нажать гиперссылку "Команда". Описания команд приведены в файлах с классическими алгоритмами.

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

• чтобы слить пробирку под номером 4 с пробиркой под номером 3 следует указать в файле:

"1.4 3", где "1." - наименование операции "Слить", "4" - номер пробирки куда следует "перелить" ДНК из второй пробирки, "3" номер пробирки которую нужно перелить в первую пробирку;

• чтобы осуществить ренату рацию в пробирке 2 следует указать в файле:

"Р.2", где "Р." - наименование операции "Ренатурация", "2" - номер пробирки для которой будет проведена ренатурация;

• чтобы ввести заданные цепочки ДНК:

0.1 *АСТТССАС*ТСССАСТС*СССТАТСТ*СССАССАА*, где "0." - наименование операции "Генерация", - символы разделители, "АСТТССАС","ТСССАСТС","ОССТАТСТ","СССАССАА" последовательности нитей ДНК. Для возможности выполнения алгоритма по шагам или для отладки, следует установить флаг "Выполнять пошагово". При установке флага "Выводить сообщения при пошаговом выполнении" а окно сообщений выводятся текущие прочитанные команды из файла

Особенности работы с обработкой.

По кнопке "Настройка" можно задавать следующие параметры интерпретатора:

• размер шрифта строк, моделирующие нитм ДНК;

• параметры генератора случайных чисел для возможности генерации одинаковых/разных случайных цепочек ДНК;

• признак "маркер на концы" для визуального оформления строк. При установке флага добавляются маркеры "3'" и "5" в начале и конце строк;

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

в

Щ Справка ДНК _ ______________ ___ _ □ X

* 3' Содержание Индекс Поиск

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

"Р. Ренату рация", "д. Денатурация", флаг "Стакеры" и появляется дополнительная колонка, моделирующая вторую спираль ДНК.

Моделирование операции "Ренатурация" предполагает два действия:

1. разделение каждой цепочки ДНК на две.

Первая цепочка будет направлена от 3' к 5', вторая от 5' к 3'. Например:

Колонка "Цепочка ДНК" : 3' - АГПЗС - 5' Колонка "Цепочка ДНК2": 5' - ААС - 3' Колонка "Количество" : 10 ООО будет разбита на две строчки: первая строчка:

Колонка "Цепочка ДНК" : 3' - АТТСС - Б' Колонка "Цепочка ДНК2": 5' - ААС - 3' Колонка "Количество" : 5 ООО вторая строчка:

Колонка "Цепочка ДНК" : 3' - САД - 5' Колонка "Цепочка ДНК2": 5' - ССТТА - 3' Колонка "Количество" : 5 ООО

2. склеивание цепочек ДНК. Склеивается верхняя нить ДНК к другим нитям ДНК. Включение флага "Стакеры* позволяет задавать длину участка в запоминающей цепочке.

— Автор:

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

— Аспирант факультета информационных технологий,

-- кафедра информатизации образования РГПУ им. Герцена.

Г