Методические указания к курсу «Элементы дискретной математики и биоинформатики» (стр. 5 из 8)
Краткое содержание раздела:
Понятие формального языка. Цепочки ДНК как языки над 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].
Лекция 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. Пусть
. Пусть также 
( 
) тогда и только тогда, когда 
. Какими свойствами обладает отношение 
?