5. Введение в алгоритмы - Методические указания к курсу «Элементы дискретной математики и биоинформатики»

^ 5. Введение в методы.

Лекции 16-17.

Цель данного раздела – дать общее представление о теории алгоритмов, обсудить вопросы трудности и эффективности, разглядеть традиционные примеры алгоритмов на графах, также примеры био задач, использующих алгоритмические способы решения. Тем, этот 5. Введение в алгоритмы - Методические указания к курсу «Элементы дискретной математики и биоинформатики» раздел с одной стороны позволяет студентам более удачно осваивать дисциплины, связанные с информатикой, с другой стороны дает подготовительные сведения из теории алгоритмов, нужные при исследовании 2-ой части курса, посвященной основам биоинформатики.

В качестве 5. Введение в алгоритмы - Методические указания к курсу «Элементы дискретной математики и биоинформатики» примера, приведем две обычные задачки биоинформатики. 1-ая задачка – задачка сопоставления последовательностей. Дана аминокислотная последовательность, схожая на некую другую последовательность, лежащую в банке данных, т.е. по которой имеются экспериментальные 5. Введение в алгоритмы - Методические указания к курсу «Элементы дискретной математики и биоинформатики» данные, и известны ее функции. Тогда можно представить, что эти последовательности делают схожие функции. Таким макаром, после секвенирования новейшей последовательности ее ассоциируют с уже существующими в базах данных последовательностями, чтоб судить о том 5. Введение в алгоритмы - Методические указания к курсу «Элементы дискретной математики и биоинформатики», какие функции несет эта последовательность. Как следует, появляется задачка поиска сходства последовательностей, а конкретно: одна последовательность записывается под другой, и требуется отыскать лучший вариант так выровнять эту пару последовательностей, чтоб количество совпадений было наибольшим 5. Введение в алгоритмы - Методические указания к курсу «Элементы дискретной математики и биоинформатики». Качество выравнивания оценивают, назначая штрафы за несовпадение букв и за наличие пробелов (когда приходится раздвигать одну последовательность для того, чтоб получить наибольшее число совпадающих позиций). Ясно, что можно отыскать наилучшее выравнивание 5. Введение в алгоритмы - Методические указания к курсу «Элементы дискретной математики и биоинформатики» перебором всех вероятных вариантов, но на практике этот метод неприменим – число вероятных выравниваний экспоненциально находится в зависимости от длины последовательности. Все же, для решения этой задачки существует действенный метод: она 5. Введение в алгоритмы - Методические указания к курсу «Элементы дискретной математики и биоинформатики» сводится к задачке поиска кратчайшего пути во взвешенном графе.

Другая задачка – пророчество вторичной структуры РНК. Вторичная структура РНК – структура, образуемая спаренными основаниями на однонитевой молекуле РНК. Вся РНК состоит из петель и спиралей. Петли бывают 5. Введение в алгоритмы - Методические указания к курсу «Элементы дискретной математики и биоинформатики» последующих типов: шпилька, внутренняя, выпуклость, множественная, псевдоузел. Таким макаром, задачка определения вторичной структуры состоит в правильном определении спаренных нуклеотидов. Эту задачку можно интерпретировать в определениях теории графов: «правильной» вторичной структуре будет соответствовать 5. Введение в алгоритмы - Методические указания к курсу «Элементы дискретной математики и биоинформатики» наибольший подграф (клика) в графе возможных спиралей. Но понятно, что задачка поиска клики в графе является труднорешаемой – для нее, вероятнее всего, не существует более действенного метода решения, чем полный перебор 5. Введение в алгоритмы - Методические указания к курсу «Элементы дискретной математики и биоинформатики» всех вариантов. Все же, на практике эта задачка решается приближенно, используя метод динамического программирования.

^ Короткое содержание раздела:

Понятие метода. Методы и их сложность. Полиномиальные и экспоненциальные методы. Действенные и неэффективные методы. Примеры задач: задачка 5. Введение в алгоритмы - Методические указания к курсу «Элементы дискретной математики и биоинформатики» о кратчайшем пути во взвешенном графе, задачка о наименьшем остове. Метод Краскала. Труднорешаемые задачки: задачка коммивояжера, задачка о наивысшем полном подграфе. Поиск в графе: поиск в глубину, поиск в 5. Введение в алгоритмы - Методические указания к курсу «Элементы дискретной математики и биоинформатики» ширину. Поиск кратчайшего по числу ребер пути. Метод отыскания эйлеровой цепи в эйлеровом графе. Некие обычные задачки биоинформатики, сводящиеся к задачкам на графах: задачка сопоставления последовательностей, задачка пророчества вторичной структуры РНК, задачка поиска 5. Введение в алгоритмы - Методические указания к курсу «Элементы дискретной математики и биоинформатики» кратчайшей надстроки, расшифровка гибридизацией.

Литература: [1], гл. 7 стр. 207-213, гл. 8 стр. 226-232, 247-262.

Задачки: [12] №№ 59, 61.

^ 6. Главные алгебраические структуры.

Лекции 18-20.

Алгебраические способы описания моделей находят самое обширное применение при формализации разных предметных областей. Можно сказать, что при построении 5. Введение в алгоритмы - Методические указания к курсу «Элементы дискретной математики и биоинформатики» модели предметной области, все начинается с введения подходящих множеств, операций и отношений над их элементами с следующим исследованием их параметров. Таким макаром, владение алгебраической терминологией заходит в арсенал средств, нужных для 5. Введение в алгоритмы - Методические указания к курсу «Элементы дискретной математики и биоинформатики» абстрактного моделирования. Приведем пример внедрения полугрупп в биологии для описания неких качеств скрещивания организмов. При выведении породы большого рогатого скота рассматривают цвет, темный либо бурый, и признаки одноцветности либо пятнистости. Понятно, что темный 5. Введение в алгоритмы - Методические указания к курсу «Элементы дискретной математики и биоинформатики» цвет доминантен, а бурый рецессивен и что одноцветность доминирует над пятнистостью. Таким макаром, в данном стаде различают четыре типа скота:

a – «черный одноцветный», b – «черный пятнистый»,

c – «бурый одноцветный», d – «бурый пятнистый».

Беря во 5. Введение в алгоритмы - Методические указания к курсу «Элементы дискретной математики и биоинформатики» внимание дела преобладания, при скрещивании темной пятнистой особи с бурой одноцветной особью следует ждать темное одноцветное потомство. Это можно записать в виде . «Операция скрещивания» , рассмотренная для всех различных пар, описывается последующей таблицей 5. Введение в алгоритмы - Методические указания к курсу «Элементы дискретной математики и биоинформатики»:



a b c d

a

b

c

d

a a a a

a b a b

a a c c

a b c d

Это – таблица Кэли для группоида . По данной таблице можно проверить, что операция является ассоциативной 5. Введение в алгоритмы - Методические указания к курсу «Элементы дискретной математики и биоинформатики», т.е. S является полугруппой. Не считая того, таблица является симметричной относительно главной диагонали, как следует, операция коммутативна, элемент d является нейтральным элементом полугруппы, а – нулем.

В процессе исследования данного раздела студенты 5. Введение в алгоритмы - Методические указания к курсу «Элементы дискретной математики и биоинформатики» должны составить представление о традиционных алгебраических структурах: полугруппах, группах, кольцах, полях и их главных свойствах. Повышенное внимание при исследовании данного раздела уделяется свободным полугруппам, так как они играют важную роль, как в общей 5. Введение в алгоритмы - Методические указания к курсу «Элементы дискретной математики и биоинформатики» теории полугрупп, так и в приложениях. Их прикладная роль разъясняется, а именно, тем, что в почти всех процессах передачи инфы, передаваемые сообщения представляют собой цепочки знаков ("реальных" букв либо слов, других кодовых символов 5. Введение в алгоритмы - Методические указания к курсу «Элементы дискретной математики и биоинформатики», электронных сигналов, последовательностей нуклеотидов в цепочке ДНК и т.д.), и соединение 2-ух таких цепочек есть не что другое, как конкатенация слов в подходящей свободной полугруппе. Свободные полугруппы (приемущественно над конечными алфавитами) являются 5. Введение в алгоритмы - Методические указания к курсу «Элементы дискретной математики и биоинформатики» начальным объектом в теории формальных языков и теории кодов, существенна их роль в теории автоматов.

^ Короткое содержание раздела:

Операции на огромных количествах. Характеристики операций: ассоциативность, коммутативность. Понятие полугруппы. Примеры. Полугруппы 5. Введение в алгоритмы - Методические указания к курсу «Элементы дискретной математики и биоинформатики» в биологии. Нейтральный элемент и его характеристики. Оборотный элемент и его единственность в полугруппе. Понятие группы. Примеры. Абелевы группы. Подполугруппы, подгруппы. Порождающие огромного количества. Циклические полугруппы и группы, их характеристики. Гомоморфизмы и изоморфизмы полугрупп 5. Введение в алгоритмы - Методические указания к курсу «Элементы дискретной математики и биоинформатики» и групп. Свободные полугруппы и группы, их характеристики. Свободные полугруппы и цепочки ДНК.

Кольца. Поля. Главные характеристики, примеры. Область целостности, тело. Примеры. Кольцо многочленов.

Литература: [2], [10], [11].

Задачки: [3] №№ 1.1.1 (а, в, д, ж, и), 1.1.3 (а 5. Введение в алгоритмы - Методические указания к курсу «Элементы дискретной математики и биоинформатики»), 1.1.9, 1.2.10 (а), 1.2.12 (б), 2.2.33 (б), 2.3.6 (а, в), 3.1.1 (а, б, в), 4.1.15 (а), 4.2.4.



5-vnutribolnichnie-infekcii-gornomarijskij-municipalnij-rajon.html
5-voprosi-dlya-samokontrolya-mnozhestvennij-vibor-predislovie.html
5-vospitatelnaya-rabota-v-shkole-doklad-za-20112012-uchebnij-god-mou-sosh-83.html