Geum.ru

Курс IV семестры 8 (весенний) лекции 16 часов Экзамен 8 семестр (весенний)

Вид материалаЛекции

Содержание


Всего часов
4. Операции над множествами.
5. Алгоритмы на графах.
6. Алгоритмы в биоинформатике.
Подобный материал:

министерство образования и науки российской федерации

Федеральное агентство по образованию


Государственное образовательное учреждение

высшего профессионального образования

Московский физико-технический институт

(государственный университет)


УТВЕРЖДАЮ

проректор по учебной работе

д.т.н. Е.В. Глухова


«___» _____________ 200__ г.




П Р О Г Р А М М А




Курса Основы эффективных вычислений

по направлению 010600 «Прикладные математика и физика»

по магистерским программам 010656, 010674

факультет РТК

кафедра проблем передачи и обработки информации

курс IV

семестры 8 (весенний)


лекции 16 часов Экзамен 8 семестр (весенний)

семинары нет Зачёт нет

лабораторные занятия 16 часов


самостоятельная работа 2 часа в неделю

ВСЕГО ЧАСОВ 32




Программу составил: профессор, д.ф.-м.н. Вьюгин В.В.

Программа обсуждена на заседании кафедры

проблем передачи и обработки информации

02 июня 2008 года


Заведующий кафедрой

чл.-корр. РАН А.П. Кулешов

1. Модели вычислений.

1.1. Машины с произвольным доступом к памяти (РАМ). Вычислительная сложность РАМ-программ. Модель с хранимой программой.

1.2. Машина Тьюринга. Связь машин Тьюринга и РАМ (по времени вычисления и объему памяти).


2. Некоторые эффективные алгоритмы.

2.1. Структуры данных: списки, очереди, стеки. Представления множеств.

2.2. Графы, их представления. Деревья, алгоритмы прохождения дерева.

2.3. Рекурсия: примеры алгоритмов: нахождение минимального (максимального) элемента множества, сортировка слиянием.

2.4. Умножение чисел, динамическое программирование. Алгоритм Штрассена быстрого умножения матриц.


3. Алгоритмы сортировки.

3.1. Сортировка вычерпыванием: цифровая и лексикографическая сортировки.

3.2. Сортировка деревом. Быстрая в среднем сортировка.


4. Операции над множествами.

4.1. Основные операции над множествами.

4.2. Двоичный поиск. Деревья двоичного поиска: алгоритмы просмотра, вставки, удаления элементов.

4.3. Оптимальные деревья двоичного поиска.

4.4. Схемы сбалансированных деревьев.


5. Алгоритмы на графах.

5.1. Алгоритмы построения остовного дерева наименьшей стоимости, поиска в глубину в ориентированном графе.

5.2. Динамическое программирование: общая постановка. Полукольца: их свойства. Алгоритмы поиска путей на графе с ребрами, размеченными элементами полукольца.


6. Алгоритмы в биоинформатике.

6.1. Алгоритмы поиска оптимального выравнивания двух последовательностей ДНК.

6.2. Статистическая физика полипептидов. Алгоритм поиска оптимального склеивания последовательностей ДНК.

6.3. Алгоритмы поиска подстрок: алгоритм Рабина - Карпа. Алгоритм Кнута – Морриса – Пратта.


СПИСОК ЛИТЕРАТУРЫ
  1. Шень А. Программирование: теоремы и задачи. М.: МЦНМО, 1995.
  2. Ахо А., Хопкофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.


СПИСОК ДОПОЛНИТЕЛЬНОЙ ЛИТЕРАТУРЫ
  1. Гасфилд Д. Строки, деревья и последовательности в алгоритмах (информатика и вычислительная биология). СПб.: BHV-CG, 2003.
  2. Кормен Т., Лейзерзон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 1999.
  3. Finkelstein A.V., Roytberg M.A. Computation of biopolymers: A general approach to different problems // Biosystems. 30 (1993), 1-19.