6. Основные алгебраические структуры.
6.1. Обозначим через В2 множество, состоящее из нулевой

матрицы

и четырех «матричных единиц»

,

,

,

.
а) Проверить, что В2 является полугруппой относительно умножения.
б) Составить таблицу Кэли для полугруппы В2.
6.2. а) Доказать, что преобразования

,

и

составляют порождающее множество полугруппы

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

двухэлементное порождающее множество?
6.3. Определить, какие из следующих отображений

группы (Z,+) в себя являются гомоморфизмами: а)

; б)

; в)

г)

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

группы S
5.
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*)(ab2+a2b).
7.3. Охарактеризовать язык, порождаемый грамматикой с множеством нетерминальных символов {A, S}, где S – аксиома, множеством терминальных символов {0, 1} и множеством правил вывода {S

0
A1, 0
A 
00
A1,
A

}.
7.4. Построить конечный автомат, распознающий язык над алфавитом {a, b}, состоящий из всех таких слов, в которых каждый третий символ – буква a.
7.5. По данной таблице построить граф автомата и охарактеризовать язык, распознаваемый этим автоматом:
Вопросы к зачету по курсу «Элементы дискретной математики и биоинформатики»:
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.