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

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

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

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

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

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

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

 

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

3 семестр:

1. Множества, способы их заданий, равенство множеств, подмножества. Примеры.

2. Конечные и бесконечные множества, счетные множества. Примеры.

3. Операции на множествах: объединение, пересечение, дополнение. Примеры.

4. Свойства операций объединения, пересечения, дополнения, законы де Моргана.

5. Декартово произведение множеств, бинарные отношения, примеры, основные типы бинарных отношений.

6. Свойства бинарных отношений: рефлексивность, транзитивность, примеры.

7. Свойства бинарных отношений: симметричность, антисимметричность, примеры.

8. Отношения эквивалентности. Классы эквивалентности. Разбиения. Фактор-множество. Отношения эквивалентности в биологии – примеры.

9. Отношения частичного и линейного порядка. Примеры.

10. Логические связки. Формулы логики высказываний. Тавтология, выполнимая формула, противоречие.

11. Логическая эквивалентность. Законы логики высказываний,

12. Основные понятия теории графов. Лемма о рукопожатиях. Способы формального задания графов.

13. Маршруты, связность, циклы. Мосты, разрезы.

14. Верхняя и нижняя границы для числа ребер в обыкновенном графе.

15. Расстояния в графах, радиус и диаметр связного графа.

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

17. Матрицы, ассоциированные с графами.

18. Деревья, леса, свойства. Применение деревьев в биологии.

19. Остовы. Цикломатическиое число. Число остовов в обыкновенном связном графе.

20. Эйлеровы графы.

21. Гамильтоновы графы.

22. Укладки графов, планарные графы, формула Эйлера для плоских графов.

23. Эквивалентность планарности и укладываемости графа на сфере.

24. Непланарность графов К_3,3 и К₅. Теорема Понтрягина-Куратовского.

25. Раскраски графов, хроматические числа. Теорема Кенига о 2-хроматичности обыкновенного графа.

26. Теорема Хивуда о 5-раскрашиваемости любого планарного графа.

27. Алгоритмы и их сложность, запись алгоритмов.

28. Поиск в глубину.

29. Поиск в ширину.

30. Задача о кратчайшем пути.

31. Задача о минимальном остове. Алгоритм Краскала.

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

33. Поиск эйлеровой цепи в эйлеровом графе.

34. Задача о поиске кратчайшей надстроки. Задача расшифровки ДНК гибридизацией. Сведение к задаче поиска эйлерова пути в мультиграфе.

4 семестр:

1. Операции на множестве. Задание с помощью таблицы Кэли. Свойства операций.

2. Определение полугруппы, группы. Полугруппы в биологии – примеры.

3. Свойства нейтрального и обратного элементов.

4. Подполугруппы, порождающие множества.

5. Подгруппы, порождающие множества.

6. Циклические полугруппы, группы, свойства. Примеры.

7. Свободные полугруппы. Свойства. Свободные полугруппы и цепочки ДНК.

8. Свободные группы.

9. Гомоморфизмы и изоморфизмы полугрупп и групп.

10. Определение кольца. Примеры. Типы колец. Идеалы.

11. Понятие области целостности, тела, области главных идеалов. Примеры.

12. Поля. Основные свойства. Примеры.

13. Понятие формального языка. Операции над языками.

14. Цепочки ДНК как языки над 4-буквенным алфавитом.

15. Конечные автоматы. Детерминированные и недетерминированные автоматы.

16. Распознавание языков автоматами.

17. Регулярные языки. Теорема Клини.

18. Машина Тьюринга как модель алгоритма. Тезис Черча.

19. Формальные грамматики как способ задания языков.

20. Виды грамматик. Иерархия Хомского.

21. Основы молекулярных вычислений. Строение ДНК. Измеряемые характеристики.

22. Операции над ДНК: удлинение, укорочение.

23. Операции над ДНК: разрезание, сшивка.

24. Операции над ДНК: модификация нуклеотидов, размножение ДНК. Полимеразная цепная реакция. Секвенирование.

25. Поиск гамильтонова пути в графе. Опыт Эдлмана.

26. Алгоритм Липтона решения задачи выполнимости пропозициональных формул.

27. Стикерная модель молекулярных вычислений. Основанный на этой модели алгоритм взлома криптосистемы DES. Определение стикера.

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

29. Математические модели сборки генов у ресничных: внутримолекулярная модель.

30. Математические модели сборки генов у ресничных: межмолекулярная модель.

31. Применение теории формальных языков при изучении процессов метаболизма и процессов клеточного роста. Системы Линденмайера.

32. Графическая интрепретация – черепашья графика. Примеры: снежинка Коха, ковер Серпинского.

33. Ветвящиеся структуры. Осевые деревья. Древесные ОL-системы.

34. Скобочные О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).