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