Методические указания к курсу «Элементы дискретной математики и биоинформатики»

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение

высшего профессионального образования

«Уральский государственный университет им. А. М. Горького»

Математико-механический факультет

Кафедра алгебры и дискретной математики

Методические указания к курсу

«Элементы дискретной математики и биоинформатики»

Автор-составитель

Прибавкина Е.В.

Руководитель ИОНЦ «Физика

в биологии и медицине»

____________ Бабушкин А.Н.

(подпись)

__________

(дата)

Екатеринбург

2007

Курс «Элементы дискретной математики и биоинформатки» читается на биологическом факультете в 3-м и 4-м семестрах и является факультативным курсом. Для восприятия излагаемого в нем материала требуется определенная математическая культура. В этом смысле курс опирается на читаемый в первых двух семестрах курс высшей математики, хотя напрямую материал этого курса используется незначительно.

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

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

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

СОДЕРЖАНИЕ

Элементы дискретной математики. 4

1. Элементы теории множеств. 4

2. Бинарные отношения. 5

3. Логика высказываний. 6

4. Теория графов. 7

5. Введение в алгоритмы. 11

6. Основные алгебраические структуры. 13

7. Элементы теории формальных языков и автоматов. 14

Основы молекулярных вычислений и биоинформатики. 16

8. Основы молекулярных вычислений. 16

9. Применение молекулярных компьютеров в медицине. 17

10. Вычисления в живых клетках. 17

11. Системы Линденмайера. 18

Задания для самоконтроля. 19

Вопросы к зачету по курсу «Элементы дискретной математики и биоинформатики»: 24

Рекомендуемая литература. 27

Элементы дискретной математики.

1. Элементы теории множеств.

Лекция 1.

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

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

Краткое содержание раздела:

Понятие множества. Способы задания множеств. Диаграммы Эйлера-Венна. Подмножества. Равенство множеств. Множество всех подмножеств конечного множества. Пустое и универсальное множество. Примеры. Операции над множествами: пересечение, объединение, разность. Основные свойства операций объединения и пересечения: коммутативность, ассоциативность, дистрибутивность. Операция дополнения. Законы де Моргана. Мощность множества. Конечные и счетные множества.

Литература: [5] стр. 12-15, [16] гл.1, стр. 19-31.

Задачи: [6], №№ 101 (1, 3), 106 (1,3,5,7), 118, 128 (1,3,5,7), 139 (1,3,5).

Пример решения задач:

Найти множество всех подмножеств множества .

Решение. Множество A
состоит из двух элементов, один из которых число 1, а второй – множество {2, 3}. Тогда множество всех подмножеств P(
A)
имеет 22
=4 элемента: .

2. Бинарные отношения.

Лекции 2-3.

Между элементами различных множеств могут быть установлены многочисленные связи и зависимости. Эти связи описываются в математике с помощью отношений и функций. Поскольку с понятием функции студенты знакомятся в курсе высшей математики в 1-м и 2-м семестрах, данный раздел посвящен понятию бинарного отношения и различным его свойствам. Отметим, что в биологии бинарные отношения могут использоваться для описания наследственных связей: например, отношение «быть предком» на множестве всех людей. Также важную роль при классификации играют отношения эквивалентности, например, эквивалентность «иметь одинаковое строение цветка, плода и одинаковый тип соцветия» на множестве всех цветковых растений делит их на классы эквивалентности – семейства – крестоцветных, розоцветных, бобовых и т.д.

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

Краткое содержание раздела:

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

Литература: [5] стр. 16-21, стр. 44-46, [16] гл. 2, стр. 32-39.

Задачи: [6] №№ 204 (1,5,9,14), 205 (1,3,5), 207 (1,3), 219, 303, 304.

Пример решения задач:

Пусть М – множество всех слов русского языка. Какими свойствами обладают отношения слова х
и у
не содержат ни одной общей буквы} и слова х и у содержат хотя бы одну общую букву}. Будут ли эти отношения отношениями эквивалентности?

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

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

3. Логика высказываний.

Лекция 4.

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

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

Краткое содержание раздела:

Высказывания. Примеры. Логические связки. Формулы логики высказываний. Примеры. Логическая эквивалентность. Свойства логических операций. Тавтологии или законы логики высказываний. Логический вывод. Доказательство теорем.

Литература: [16] гл. 3, стр. 61-81, [5] стр. 65-85.

Задачи: [6] №№ 601 (1,4,7,10,13,16), 602 (1,3), 604 (1,3,5), 612 (1,3,4).

Пример решения задач:

В одной местности расположены два города И и Л. Жители И всегда говорят правду, а жители Л всегда лгут. Как, попав в один из этих городов, узнать у первого встречного название города?

Решение. Поскольку ответ встречного зависит от его правдивости, обозначим х
=«Ты правдив». Нас интересует название города, поэтому обозначим у
=«Это город И». Теперь из высказываний х и у сконструируем высказывание р
так, что услышав от встречного ответ «Да» на вопрос «Верно ли, что р
=И?» мы поймем, что находимся в И. Составим для р
следующую таблицу истинности:

		Слышимый ответ	Понимаемый ответ	Р
Л	Л	нет	да	И
Л	И	да	нет	Л
И	Л	нет	нет	Л
И	И	да	Да	И

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

4. Теория графов.

Лекции 5-15.

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

Цель данного раздела – представить основное, устоявшееся ядро современной теории графов, акцентируя внимание на биологических приложениях. Для более полного охвата разделов современной теории графов, некоторые факты приводятся без доказательств (например, критерий планарности графа – теорема Понтрягина-Куратовского или теорема Хивуда о 5-раскрашиваемости планарного графа).

Краткое содержание раздела:

Способы формального задания графов. Степень вершины. Лемма о рукопожатиях. Подграфы, остовные подграфы. Полные графы. Число ребер полного графа. Подграфы, остовные подграфы. Пересечение и объединение подграфов.

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

Ориентированные графы. Турниры. Ормаршруты, орцепи, орциклы (контуры). Орлемма о рукопожатиях.

Матрицы, ассоциированные с графами: матрица смежности, матрица инцидентности. Их свойства.

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

Эйлеровы графы, их свойства.

Гамильтоновы графы. Достаточное условие гамильтоновости графа (теорема Дирака).

Укладки графов. Планарные графы. Укладка графа в трехмерном пространстве. Эквивалентность планарности и укладываемости графа на сфере. Формула Эйлера для плоских графов. Связь числа вершин, ребер и граней выпуклых многогранников в трехмерном евклидовом пространстве. Непланарность графов К3,3
и К5
. Теорема Понтрягина-Куратовского.

Раскраски графов. Хроматические числа. Теорема Кенига о 2-хроматичности обыкновенного графа. Теорема Хивуда о 5-раскрашиваемости любого планарного графа.

Литература: [1] гл. 1-3, 5-6,
[7
].

Задачи: [12] №№ 1, 4, 17, 18, 19, 37, 38, 39, 46, 54, 55, 56, 58, 59, 60, 63, 64, 74, 77, 94, 95.

Пример решения задач:

5.1. В соревновании по круговой системе с двенадцатью участниками провели все встречи. Сколько встреч было сыграно?

Решение. Построим граф встреч игроков: каждому из 12-ти игроков поставим в соответствие вершину графа. Если два игрока встретились между собой, то соединим соответствующие вершины ребром. Поскольку соревнование проводится по круговой системе, т.е. каждый играет с каждым, и были сыграны все встречи, то граф встреч является полным графом на 12-ти вершинах. Число ребер в нем . Таким образом, было сыграно 66 встреч.

5.2. Рассмотрим граф , изображенный на рисунке. На примере этого графа рассмотрим некоторые понятия теории графов.

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

	3	3	3	4	2	3	2

Матрицей смежности
неориентированного графа называется матрица размерности , элементы которой определяются следующим образом:

Матрица смежности для данного графа имеет вид:

.

Матрицей инцидентности
неориентированного графа с вершинами и ребрами называется матрица размерности , элементы которой определяются следующим образом:

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

		1	1	1	0	0	0	0	0	0	0
		1	0	0	1	1	0	0	0	0	0
		0	0	0	1	0	1	1	0	0	0
		0	1	0	0	1	1	0	1	0	0
		0	0	1	0	0	0	0	0	1	0
		0	0	0	0	0	0	0	1	1	1
		0	0	0	0	0	0	1	0	0	1

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

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

. Здесь – это множество вершин графа .

Радиус
графа G
определяется как наименьший из условных радиусов графа, а центр графа составляют вершины, условные радиусы графа относительно которых совпадают с радиусом графа.

Для данного графа таблица расстояний и условных радиусов вершин имеет вид:

	0	1	2	1	1	2	3	3
	1	0	1	1	2	2	2	2
	2	1	0	1	3	2	1	3
	1	1	1	0	2	1	2	2
	1	2	3	2	0	1	2	3
	2	2	2	1	1	0	1	2
	3	2	1	2	2	1	0	3

Радиус графа , следовательно, центр графа – это множество вершин .

5.3. Из одной бактерии в результате деления получилось 1000 бактерий: вначале бактерия разделилась на две, затем одна из них вновь разделилась на две, затем одна из трех бактерий разделилась на две и т.д. Докажите, что в некоторый момент существовала бактерия, число потомков которой в самом конце, т.е. среди 1000 бактерий не меньше 100 и не больше 199.

Решение. Процесс деления бактерий опишем корневым деревом. Условимся называть дочками бактерии те две бактерии, на которые она разделилась. Обозначим через Б1
, Б2
, Б3
, … такую последовательность бактерий:

Б1
– исходная бактерия, число ее потомков П1
=1000;

Б2
– та из дочек Б1
, у которой число потомков не меньше, чем у другой дочки бактерии Б1
;

Б3
– та из дочек Б2
, у которой число потомков не меньше, чем у другой дочки бактерии Б2
и т.д.

В силу выбора нами дочерних бактерий следует, что .

Последовательность натуральных чисел П1
, П2
, П3
, … монотонно убывает. Первый член этой последовательности равен 1000, последний – 2. Значит, найдется такой номер k, когда число Пk
в первый раз станет меньше 200, т.е. когда и . Учитывая, что , получим , т.е. число потомков бактерии Бk
не меньше 100 и не больше 199.

5. Введение в алгоритмы.

Лекции 16-17.

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

В качестве примера, приведем две типичные задачи биоинформатики. Первая задача – задача сравнения последовательностей. Дана аминокислотная последовательность, похожая на некоторую другую последовательность, хранящуюся в банке данных, т.е. по которой имеются экспериментальные данные, и известны ее функции. Тогда можно предположить, что эти последовательности выполняют сходные функции. Таким образом, после секвенирования новой последовательности ее сравнивают с уже существующими в базах данных последовательностями, чтобы судить о том, какие функции несет эта последовательность. Следовательно, возникает задача поиска сходства последовательностей, а именно: одна последовательность записывается под другой, и требуется найти наилучший вариант так выровнять эту пару последовательностей, чтобы количество совпадений было максимальным. Качество выравнивания оценивают, назначая штрафы за несовпадение букв и за наличие пробелов (когда приходится раздвигать одну последовательность для того, чтобы получить наибольшее число совпадающих позиций). Ясно, что можно найти оптимальное выравнивание перебором всех возможных вариантов, но на практике этот способ неприменим – число возможных выравниваний экспоненциально зависит от длины последовательности. Тем не менее, для решения этой задачи существует эффективный алгоритм: она сводится к задаче поиска кратчайшего пути во взвешенном графе.

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

Краткое содержание раздела:

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

Литература: [1], гл. 7 стр. 207-213, гл. 8 стр. 226-232, 247-262.

Задачи:
[12
] №№ 59, 61.

ign:center;">6. Основные алгебраические структуры.

Лекции 18-20.

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

a
– «черный одноцветный», b
– «черный пятнистый»,

c
– «бурый одноцветный», d
– «бурый пятнистый».

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

	a b c d
a b c d	a a a a a b a b a a c c a b c d

Это – таблица Кэли для группоида . По данной таблице можно проверить, что операция является ассоциативной, т.е. S является полугруппой. Кроме того, таблица является симметричной относительно главной диагонали, следовательно, операция коммутативна, элемент d
является нейтральным элементом полугруппы, а
– нулем.

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

Краткое содержание раздела:

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

Кольца. Поля. Основные свойства, примеры. Область целостности, тело. Примеры. Кольцо многочленов.

Литература: [2], [10], [11].

Задачи: [3] №№ 1.1.1 (а, в, д, ж, и), 1.1.3 (а), 1.1.9, 1.2.10 (а), 1.2.12 (б), 2.2.33 (б), 2.3.6 (а, в), 3.1.1 (а, б, в), 4.1.15 (а), 4.2.4.

7. Элементы теории формальных языков и автоматов.

Лекции 21-24.

Теория формальных языков и автоматов представляет удобный и естественный аппарат для формального математического описания операций над молекулами ДНК, самих молекул и вычислительных процессов с использованием ДНК. Живые организмы выполняют сложные операции, руководствуясь, по сути, цифровой информацией. Биомолекулярные реакции, да и деятельность организма в целом, управляются инструкциями, записанными в геноме последовательностью нуклеиновых кислот. Если внутриклеточную биомолекулярную машину, обрабатывающую нуклеотидные последовательности ДНК и РНК, сравнить с машиной Тьюринга, то можно заметить поразительное сходство. Обе системы оперируют информацией, которая хранится в цепочке символов, построенной на основании алфавита, и шаг за шагом выполняют инструкции, переходя от одного элемента к другому и по определенным правилам изменяя их или добавляя новые. Поэтому естественно предположить, что из биологических молекул можно создать ЭВМ. При этом, естественным аппаратом для математического моделирования и исследования молекулярных вычислений является теория формальных языков и автоматов. Например, молекула ДНК состоит из двух нитей, которые, соединяясь друг с другом, образуют двойную спираль. Каждая нить, будучи полимером, построена из нуклеотидов, различающихся своими основаниями. Таких оснований четыре: А (аденин), Г (гуанин), Ц (цитозин) и Т (тимин). Поэтому отдельную нить ДНК естественно представлять в виде слова над четырехбуквенным алфавитом. При помощи специальных веществ – ферментов
– с ДНК можно производить различные операции: удлинять ДНК, обрезать или разрезать ДНК, соединять последовательно две молекулы ДНК. Эти и другие ферментные операции с молекулами ДНК естественно представляются как операции над строками (например, сшивка двух молекул ДНК соответствует операции конкатенации
двух строк, т.е. приписывания второй строки в конец первой).

Краткое содержание раздела:

Понятие формального языка. Цепочки ДНК как языки над 4-буквенным алфавитом. Операции над языками. Понятие конечного автомата. Детерминированные и недетерминированные автоматы. Распознавание языков автоматами. Регулярные языки. Представление регулярных языков КДА (теорема Клини).

Машина Тьюринга как модель алгоритма. Вычисление на машине Тьюринга. Вычислимые функции. Тезис Черча. Рекурсивно-перечислимые и рекурсивные языки.

Понятие формальной грамматики. Задание языков с помощью грамматик. Виды грамматик. Контекстно-свободные языки. Контекстно-зависимые языки. Иерархия Хомского. Примеры.

Литература: [14] гл. 1-3, 5, [9].

Задачи: [3] №№ 10.1.1 (б, д), 10.1.2, 10.1.9 (а, в), 10.1.10 (а), 10.2.3 (а), 10.2.4 (в).

Основы молекулярных вычислений и биоинформатики.

8. Основы молекулярных вычислений.

Лекции 25-30.

Данный раздел посвящен введению в молекулярные вычисления. Мысль о том, что живая клетка, выполняя свои функции, перерабатывает не только химические вещества, но и информацию, возникла в третьей четверти XX-го века, когда была раскрыта роль ДНК как носителя генетического кода. Человек уже давно использует живые клетки в качестве миниатюрных, но весьма эффективных химических фабрик (вспомним хотя бы о дрожжах). Можно ли создать из клеток столь же эффективные «фабрики вычислений»? Знаменитый опыт Эдлмана, осуществленный в 1994 году, показал, что молекулы ДНК могут решать вычислительные задачи, причем именно те, которые представляют наибольшие трудности для традиционных электронных компьютеров.

Краткое содержание раздела:

Обсуждение возможности: применение двух основных феноменов – массового параллелизма цепочек ДНК и комплементарности Уотсона-Крика. Строение ДНК. Дезоксирибонуклеотиды. Азотистые основания. Строение РНК. Способы соединения нуклеотидов. Комплементарность Уотсона-Крика. Измеряемые характеристики. Измерение длины молекулы ДНК. «Выуживание» из раствора с молекулами ДНК известных молекул. Операции над ДНК: Разделение и соединение цепочек ДНК. Использование ферментов для проведения операций с молекулами ДНК. Удлинение ДНК. Укорочение ДНК. Разрезание ДНК. Сшивка ДНК. Операции над ДНК: Модификация нуклеотидов ДНК; размножение ДНК, полимеразная цепная реакция. Секвенирование. Эксперименты по решению сложных вычислительных задач: опыт Эдлмана решения задачи о поиске гамильтонова пути в графе; алгоритм Липтона решения задачи выполнимости пропозициональных формул. Стикерная модель молекулярных вычислений. Основанный на этой модели алгоритм взлома криптосистемы DES. Определение стикера. Операции с ДНК, используемые в данной модели.

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

Литература: [12], гл. 1-2, [17] гл. 1, 5.

9. Применение молекулярных компьютеров в медицине.

Лекция 31.

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

Краткое содержание раздела:

Компьютеры из ДНК. От моделей к молекулам. Создание молекулярного конечного автомата. Применение молекулярных компьютеров в медицине.

Литература:
[4].

10. Вычисления в живых клетках.

Лекция 32.

С вычислительной точки зрения чрезвычайный интерес представляет процедура сборки генов при половом размножении одноклеточных класса ресничных (к нему принадлежит знакомая по школьным урокам зоологии инфузория-туфелька). У ресничных функционируют два ядра: макроядро и микроядро, наследственная информация в которых организована по-разному. Микроядро является покоящимся ядром, оно служит для передачи наследственной информации от поколения к поколению. Хромосомы микроядра находятся в компактном состоянии. В макроядре же хромосомы находятся в активном состоянии – они поставляют информацию для процессов жизнедеятельности организма. На начальных этапах развития инфузории хромосомный материал испытывает серию сложных превращений. Происходит своеобразная «разархивация» генов, так называемая сборка генов. В данном разделе изучаются две различные предложенные разными авторами математические модели процесса сборки генов у ресничных.

Краткое содержание раздела:

Вычисления в живых клетках. Биологическая сторона процесса сборки генов. Структура генов. Математические модели сборки генов у ресничных: внутримолекулярная и межмолекулярная модели.

Литература:
[8],
[18
].

11. Системы Линденмайера.

Лекция 33-34.

В процессах развития многих организмов, особенно растений, наблюдается регулярное повторение определенных многоклеточных структур, например, отдельные листья, являющиеся частью сложного листа на поздней стадии развития, имеют ту же структуру, что имел весь лист на ранних стадиях развития. Этот феномен самоподобия в процессе развития растений формально описывается при помощи систем Линденмайера (L-систем). Это понятие было введено Аристидом Линденмайером в 1968 году при математическом моделировании процессов развития простых многоклеточных организмов, а затем применено для изучения высших растений. Позднее, благодаря использованию компьютерной графики, стала возможной визуализация структуры растений и процессов их развития. Цель данного раздела – познакомить студентов с возможностями применения теории формальных языков к процессам клеточного роста, рассмотреть примеры растениеподобных структур, порожденных системами Линденмайера.

Краткое содержание раздела:

Системы Линденмайера. L-системы и формальные грамматики Хомского. Графическая интрепретация – черепашья графика. Примеры. Снежинка Коха.

Ветвящиеся структуры. Осевые деревья. Древесные ОL-системы. Скобочные ОL-системы. Примеры структур, порожденных ОL-системами.

Литература: [15], гл. 1 стр. 1-11, стр. 21-28.

Задания для самоконтроля.

1.
Множества.

1.1. Пусть — множество чисел, кратных 5, — множество чисел, кратных 7, а универсальное множество — множество всех целых чисел. Найти , .

1.2. Пусть А
и В
– множества всех прямоугольных и равносторонних треугольников на плоскости соответственно; универсальное множество – множество всех треугольников на плоскости. какие треугольники содержатся в множествах , , , , , ?

1.3. Найти множество всех подмножеств множества .

1.4. Доказать, что .

1.5. Доказать, что если и , то .

2.
Бинарные отношения.

2.1. Пусть . Пусть также () тогда и только тогда, когда . Какими свойствами обладает отношение ?

2.2. Пусть . Пусть также () тогда и только тогда, когда и . Доказать, что — отношение эквивалентности и построить разбиение на классы эквивалентности.

2.3. Для разбиения множества построить эквивалентность .

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

2.5. Пусть . Рассмотрим на этом множестве отношение делить нацело. Доказать, что это отношение частичного порядка. Построить диаграмму этого отношения.

3.
Логика высказываний.

3.1. Является ли высказыванием предложение «треугольник называется равносторонним, если все его стороны равны»?

3.2. Сформулируйте отрицания следующих высказываний и укажите значения истинности высказываний и их отрицаний: «Картофель относится к семейству розоцветных»; «картофель не относится к семейству пасленовых».

3.3. Являются ли следующие высказывания отрицаниями друг друга (объяснить почему): «человеку известны все виды животных, обитающих на Земле», «на Земле существует вид животных, не известный человеку».

3.4. Следующее сложное предложение требуется расчленить на простые и записать с использованием логических связок: «Обидно, если в пору цветения садов не сочиняют стихи и не наполняют чарки вином» (Цзацзауань. Ли Шан-Инь).

3.5. Записать таблицу истинности для формулы: .

4.
Теория графов.

4.1. В шахматном турнире по круговой системе участвуют семь студентов. Известно, что Ваня сыграл шесть партий, Толя – пять, Леша и Дима – по три, Семен и Илья – по две, Женя – одну. С кем сыграл Леша?

4.2. Насыщенным углеводородом называется соединение углерода C
, имеющего валентность 4 и водорода H
, имеющего валентность 1, в котором при заданном числе атомов углерода содержится наибольшее число атомов водорода. Найдите формулу насыщенного углеводорода, содержащего n
атомов углерода.

4.3. Мэрия решила построить торговый центр в каждом квартале города, имеющего 155 перекрестков и 260 отрезков улиц между перекрестками. Сколько будет построено торговых центров?

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

4.5. Образовавшийся коммерческий университет арендует здание для проведения занятий. В четверг проводится 7 лекций: право, английский язык, французский язык, экономика, менеджмент, маркетинг, этикет. Чтение каждой лекции в отдельности занимает один час, но некоторые лекции не могут читаться одновременно, например, их читает один и тот же лектор, или есть студенты, которые должны посещать разные лекции, или для их проведения нужна одна и та же аудитория и т.д. (В таблице крестиком отмечены лекции, которые не могут читаться одновременно). Определите минимальное время, за которое могут быть прочитаны лекции в четверг.

	право	англ.яз.	фран.яз.	экономика	Менеджмент	маркетинг	Этикет
Право
Англ. яз.
Фран. яз.
Экономика
Менеджмент
Маркетинг
Этикет

5.
Введение в алгоритмы.

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

	1	2	3	4	5	6	7
1	0	200	0	100	0	0	0
2	200	0	150	0	170	180	0
3	0	150	0	0	0	100	0
4	100	0	0	0	240	0	380
5	0	170	0	240	0	0	210
6	0	180	100	0	0	0	260
7	0	0	0	380	210	260	0

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

6.
Основные алгебраические структуры.

6.1. Обозначим через В2
множество, состоящее из нулевой матрицы и четырех «матричных единиц» , , , .

а) Проверить, что В2
является полугруппой относительно умножения.

б) Составить таблицу Кэли для полугруппы В2
.

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

б) Выяснить, существует ли для полугруппы двухэлементное порождающее множество?

6.3. Определить, какие из следующих отображений группы (Z,+) в себя являются гомоморфизмами: а) ; б) ; в) г) .

6.4. Найти порядок элемента группы S5
.

6.5. Найти свободные коммутативные полугруппы над {b
} и над {a
, b
}.

6.6. Выяснить, образуют ли идеал необратимые элементы следующих колец: а) Z9
; б) Z12
; в) Z16
.

6.7. Найти все делители нуля в кольцах: а) Z9
; б) Z12
; в) Z8
; г) Z.

6.8. Решить в поле Z5
следующую систему уравнений:

7.
Формальные языки и автоматы.

7.1. Для данного множества слов над алфавитом {a, b} определить, будет ли оно кодом, и в случае положительного ответа указать, будет ли данный код суффиксным, префиксным или бипрефиксным: а) {ab
, ba
, a
}; б) {a
, aba
}.

7.2. Выписать все слова длины не больше 5, принадлежащие языку над алфавитом {a
,b
}, заданному регулярным выражением (a
*
+b
*
)(ab
2
+a
2
b
).

7.3. Охарактеризовать язык, порождаемый грамматикой с множеством нетерминальных символов {A
, S
}, где S
– аксиома, множеством терминальных символов {0, 1} и множеством правил вывода {S
0A
1, 0A
00A
1, A
}.

7.4. Построить конечный автомат, распознающий язык над алфавитом {a
, b
}, состоящий из всех таких слов, в которых каждый третий символ – буква a
.

7.5. По данной таблице построить граф автомата и охарактеризовать язык, распознаваемый этим автоматом:

А	a b
1 2 3	2 1 2 3 3 3

Вопросы к зачету по курсу «Элементы дискретной математики и биоинформатики»:

3 семестр:

Множества, способы их заданий, равенство множеств, подмножества. Примеры.
Конечные и бесконечные множества, счетные множества. Примеры.
Операции на множествах: объединение, пересечение, дополнение. Примеры.
Свойства операций объединения, пересечения, дополнения, законы де Моргана.
Декартово произведение множеств, бинарные отношения, примеры, основные типы бинарных отношений.
Свойства бинарных отношений: рефлексивность, транзитивность, примеры.
Свойства бинарных отношений: симметричность, антисимметричность, примеры.
Отношения эквивалентности. Классы эквивалентности. Разбиения. Фактор-множество. Отношения эквивалентности в биологии – примеры.
Отношения частичного и линейного порядка. Примеры.
Логические связки. Формулы логики высказываний. Тавтология, выполнимая формула, противоречие.
Логическая эквивалентность. Законы логики высказываний,
Основные понятия теории графов. Лемма о рукопожатиях. Способы формального задания графов.
Маршруты, связность, циклы. Мосты, разрезы.
Верхняя и нижняя границы для числа ребер в обыкновенном графе.
Расстояния в графах, радиус и диаметр связного графа.
Ориентированные графы. Турниры. Ормаршруты, орцепи, орциклы (контуры). Орлемма о рукопожатиях.
Матрицы, ассоциированные с графами.
Деревья, леса, свойства. Применение деревьев в биологии.
Остовы. Цикломатическиое число. Число остовов в обыкновенном связном графе.
Эйлеровы графы.
Гамильтоновы графы.
Укладки графов, планарные графы, формула Эйлера для плоских графов.
Эквивалентность планарности и укладываемости графа на сфере.
Непланарность графов К3,3
и К5
. Теорема Понтрягина-Куратовского.
Раскраски графов, хроматические числа. Теорема Кенига о 2-хроматичности обыкновенного графа.
Теорема Хивуда о 5-раскрашиваемости любого планарного графа.
Алгоритмы и их сложность, запись алгоритмов.
Поиск в глубину.
Поиск в ширину.
Задача о кратчайшем пути.
Задача о минимальном остове. Алгоритм Краскала.
Примеры труднорешаемых задач: задача коммивояжера, задача поиска максимального полного подграфа.
Поиск эйлеровой цепи в эйлеровом графе.
Задача о поиске кратчайшей надстроки. Задача расшифровки ДНК гибридизацией. Сведение к задаче поиска эйлерова пути в мультиграфе.

4 семестр:

Операции на множестве. Задание с помощью таблицы Кэли. Свойства операций.
Определение полугруппы, группы. Полугруппы в биологии – примеры.
Свойства нейтрального и обратного элементов.
Подполугруппы, порождающие множества.
Подгруппы, порождающие множества.
Циклические полугруппы, группы, свойства. Примеры.
Свободные полугруппы. Свойства. Свободные полугруппы и цепочки ДНК.
Свободные группы.
Гомоморфизмы и изоморфизмы полугрупп и групп.
Определение кольца. Примеры. Типы колец. Идеалы.
Понятие области целостности, тела, области главных идеалов. Примеры.
Поля. Основные свойства. Примеры.
Понятие формального языка. Операции над языками.
Цепочки ДНК как языки над 4-буквенным алфавитом.
Конечные автоматы. Детерминированные и недетерминированные автоматы.
Распознавание языков автоматами.
Регулярные языки. Теорема Клини.
Машина Тьюринга как модель алгоритма. Тезис Черча.
Формальные грамматики как способ задания языков.
Виды грамматик. Иерархия Хомского.
Основы молекулярных вычислений. Строение ДНК. Измеряемые характеристики.
Операции над ДНК: удлинение, укорочение.
Операции над ДНК: разрезание, сшивка.
Операции над ДНК: модификация нуклеотидов, размножение ДНК. Полимеразная цепная реакция. Секвенирование.
Поиск гамильтонова пути в графе. Опыт Эдлмана.
Алгоритм Липтона решения задачи выполнимости пропозициональных формул.
Стикерная модель молекулярных вычислений. Основанный на этой модели алгоритм взлома криптосистемы DES. Определение стикера.
Вычисления в живых клетках. Биологическая сторона процесса сборки генов. Структура генов.
Математические модели сборки генов у ресничных: внутримолекулярная модель.
Математические модели сборки генов у ресничных: межмолекулярная модель.
Применение теории формальных языков при изучении процессов метаболизма и процессов клеточного роста. Системы Линденмайера.
Графическая интрепретация – черепашья графика. Примеры: снежинка Коха, ковер Серпинского.
Ветвящиеся структуры. Осевые деревья. Древесные ОL-системы.
Скобочные ОL-системы. Примеры растениеподобных структур, порожденных ОL-системами.

Рекомендуемая литература.

1. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы: Учеб. пособие. Екатеринбург: Изд-во Урал. ун-та, 2001.

2. Баранский В.А. Введение в общую алгебру и ее приложения: Учеб. пособие. Екатеринбург: Изд-во Урал. ун-та, 1998.

3. Баранский В.А., Важенин Ю.М., Волков М.В. и др. Сборник задач по общей алгебре и дискретной математике: Учеб. пособие. Екатеринбург: Изд-во Урал. ун-та, 2003.

4. Бененсон Я. Шапиро Э. Компьютеры из ДНК. «В мире науки» стр. 35-41, №9, 2006.

5. Важенин Ю.М. Множества, логика, алгоритмы: Учеб. пособие. Екатеринбург: Изд-во Урал. ун-та, 1995.

6. Важенин Ю.М., Попов В.Ю. Множества, логика, алгоритмы в задачах: Учеб. пособие. Екатеринбург: Изд-во Урал. ун-та, 1997.

7. Емеличев В. А., Мельников О. И., Сарваров В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990.

8. Залетова С.А. Математические модели сборки генов у ресничных. Изв. Урал. гос. ун-та. 2006. №43 (Компьютерные науки и информационные технологии. Вып. 1) С.22-37.

9. Карпов Ю.Г. Теория автоматов. Издат. дом «Питер», 2003.

10. Кострикин А.И. Введение в алгебру. Часть I:Основы алгебры. Москва,Физматлит,2004.

11. Лидл Р., Пильц Г. Прикладная абстрактная алгебра. Изд-во Урал. ун-та, 1996.

12. Мельников О.И. Занимательные задачи по теории графов: Учеб.-метод. пособие. Минск: «ТетраСистемс», 2001.

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

14. Пентус А.Е., Пентус М.Р. Теория формальных языков: Учеб. пособие. Москва, 2004.

15. Прузинкевич П., Линденмайер А. Алгоритмическая красота растений. Шпрингер-Ферлаг, 1996. (англ. P. Prusinkiewicz, A. Lindenmeyer. The Algorithmic Beauty of Plants. Springer-Verlag, 1996).

16. Турецкий В.Я. Математика и информатика: Учеб. пособие. Екатеринбург: Изд-во Урал. ун-та, 1998.

17. Эймос М. Теоретические и экспериментальные ДНК-вычисления. Шпрингер-Ферлаг, 2005.(англ. M.Amos. Theoretical and Experimental DNA Computation. Springer-Verlag, 2005).

18. Эренфойхт А., Харью Т., Петре И. и др. Вычисления в живой клетке. Сборка генов у ресничных. Шпрингер-Ферлаг, 2004. (англ. A. Ehrenfeucht, T. Harju, I. Petre et al. Computation in Living Cells. Gene Assembly in Ciliates. Springer-Verlag, 2004).