Методические указания к курсу «Элементы дискретной математики и биоинформатики» (стр. 1 из 8)
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
Государственное образовательное учреждение
высшего профессионального образования
«Уральский государственный университет им. А. М. Горького»
Математико-механический факультет
Кафедра алгебры и дискретной математики
Методические указания к курсу
«Элементы дискретной математики и биоинформатики»
Автор-составитель
Прибавкина Е.В.
Руководитель ИОНЦ «Физика
в биологии и медицине»
____________ Бабушкин А.Н.
(подпись)
__________
(дата)
Екатеринбург
2007
Курс «Элементы дискретной математики и биоинформатки» читается на биологическом факультете в 3-м и 4-м семестрах и является факультативным курсом. Для восприятия излагаемого в нем материала требуется определенная математическая культура. В этом смысле курс опирается на читаемый в первых двух семестрах курс высшей математики, хотя напрямую материал этого курса используется незначительно.
Первая часть курса (элементы дискретной математики) призвана повысить общематематическую культуру студентов и дает необходимую математическую основу для изучения второй части курса – основ биоинформатики. Первая часть включает в себя разделы, посвященные теории множеств, бинарным отношениям, математической логике, теории графов, основам теории алгоритмов, основным алгебраическим структурам, теории формальных языков и автоматов. Особое внимание уделяется примерам, иллюстрирующим биологические приложения изучаемых понятий.
Вторая часть курса под общим названием «элементы биоинформатики» включает в себя обзор новейших достижений в области применения математических и компьютерных методов в биологии. Обсуждаются возможность создания биологического вычислительного устройства на основе ДНК и некоторые эксперименты в этом направлении, а также возможность создания лекарств на основе таких молекулярных компьютеров. Рассматривается вопрос о том, как в реальности происходит вычисление и расшифровка генетической информации в живой клетке – в этой связи изучаются математические модели сборки генов у ресничных. Последний раздел второй части посвящен применению теории формальных языков для описания процесса развития растений.
В процессе изучения курса студент должен ознакомиться с понятиями теории множеств, бинарных отношений, логики высказываний, алгебраических систем. Требуется освоить ключевые понятия теории графов, алгоритмов, формальных языков и автоматов. Кроме того, студент должен составить представление об основных задачах, возникающих в современной биоинформатике, и о подходах к их решению, использующих методы дискретной математики.
СОДЕРЖАНИЕ
Элементы дискретной математики. 4
1. Элементы теории множеств. 4
6. Основные алгебраические структуры. 13
7. Элементы теории формальных языков и автоматов. 14
Основы молекулярных вычислений и биоинформатики. 16
8. Основы молекулярных вычислений. 16
9. Применение молекулярных компьютеров в медицине. 17
10. Вычисления в живых клетках. 17
Вопросы к зачету по курсу «Элементы дискретной математики и биоинформатики»: 24
Элементы дискретной математики.
Лекция 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-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.
Пример решения задач:
Пусть М – множество всех слов русского языка. Какими свойствами обладают отношения
слова х и у не содержат ни одной общей буквы} и 
слова х и у содержат хотя бы одну общую букву}. Будут ли эти отношения отношениями эквивалентности?Решение. Рассмотрим сначала отношение
. Ясно, что оно не является рефлексивным (поскольку у слов х и х все буквы общие, следовательно пара (х,х) не принадлежит 
). Это отношение является симметричным, но не является транзитивным, поскольку, например, слова кот, пёс и слова пёс, мышка находятся в отношении , но слова кот, мышка не принадлежат этому отношению, поскольку имеют общую букву к. Следовательно, отношение не является отношением эквивалентности.Рассмотрим теперь отношение
. Очевидно, что оно является рефлексивным и симметричным. Оно не транзитивно, поскольку, например, слова кот, компот и слова компот, мама принадлежат отношению , но слова кот, мама ему не принадлежат, т.к. не имеют общих букв. Лекция 4.
Математика развивается по своим внутренним законам, а именно, по законам логики. Математическая логика – это теория верных рассуждений. Слово «верных» не следует понимать в абсолютном смысле. Большинство естественнонаучных дисциплин строится на основе некоторых исходных договоренностей, или аксиом, принципов, которые формулируются исходя из разумных соображений здравого смысла или опыта. Далее из аксиом выводятся следствия, причем доказательство строится по законам логического вывода, которыми обеспечивает как раз математическая логика. Данный раздел посвящен основам математической логики, которую еще называют формальной логикой. Формальной, потому что она позволяет проверить правильность рассуждений, независимо от их содержания. Цепочки рассуждений в совершенно разных областях математики и других наук можно одинаково описать на языке логики и убедиться в их справедливости или ошибочности.