Рд бгу упрД 0001 – 2001


НазваниеРд бгу упрД 0001 – 2001
Дата публикации10.05.2013
Размер89.5 Kb.
ТипПрограмма
referatdb.ru > Математика > Программа

РД БГУ УПрД - 0001 – 2001






РУКОВОДЯЩИЙ ДОКУМЕНТ

Белорусского государственного университета

___________________________________________




Одобрена

Научно-методическим советом

Белорусского государственного университета

Протокол № от «___» _________ 2001 г.

УТВЕРЖДАЮ

Ректор Белгосуниверситета

профессор
«______» ____________________ 2001 г.


УЧЕБНАЯ ПРОГРАММА ДИСЦИПЛИНЫ
^

Теория алгоритмов



© БГУ (Электронный документ)

Минск




Предисловие

1 РАЗРАБОТАНА Белорусским государственным университетом.

ИСПОЛНИТЕЛЬ: Кафедра уравнений математической физики.

Доцент кафедры уравнений математической физики Мельников О.И.

.ВНЕСЕНА кафедрой уравнений математической физики и Главным управлением учебной и научно-методической работы Белорусского государственного университета.

ОДОБРЕНА Научно-методическим советом Белорусского государственного университета (Протокол от 11.06.01 № 1).
2 УТВЕРЖДЕНА И ВВЕДЕНА В ДЕЙСТВИЕ приказом Ректора Белорусского государственного университета от 12.06.01 № с 01.09.2001 г.
^ 3 ВВЕДЕНА ВПЕРВЫЕ

© БГУ (Электронный документ)
Настоящий руководящий документ (учебная программа дисциплины) не может быть тиражирован и распространен без разрешения Белорусского государственного университета.

Издан на русском языке


^ ПОЯСНИТЕЛЬНАЯ ЗАПИСКА


Теория алгоритмов связана с разработкой и анализом эффективных алгоритмов решения экстремальных комбинаторных задач. Наиболее интенсивно прикладные аспекты теории стали развиваться в середине XX века в связи с необходимостью исследования больших кибернетических систем с помощью ЭВМ. Поскольку эти системы отличаются огромным числом составляющих их элементов и связей между ними, то становится актуальным вопрос о построении эффективных алгоритмов их изучения. Главная задача курса – это подготовка студентов к решению реальных производственных задач.

Программа предназначена для студентов-математиков, специальности математическая электроника механико-математического факультета.

.

^ «ТЕОРИЯ АЛГОРИТМОВ»
Цель курса – научить студентов оценивать трудоемкость алгоритмов, ознакомить их с основными приемами сведения сложных задач к простым, эффективными универсальными алгоритмами решения комбинаторных задач и конкретными эффективными алгоритмами решения наиболее распространенных комбинаторных задач.

^ Тематический план курса «Теория алгоритмов»



темы

Количество часов

Содержание курса

Лекции

^ Семинарские и практические

1

2

3

Введение.

1




1.Принципы оценки комбинаторных алгоритмов. Основные структуры данных

2




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

2




3. Цифровая сортировка. Сортировка цепочек. Изоморфизм корневых деревьев

2

2

4. Сортирующее дерево

2

2

5. 2-3-деревья. Реализация с их помощью словарей и очередей с приоритетами. Построение минимального остовного дерева

4

2

6. Схема исчерпывающего поиска

1




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

2




8. Выделение двусвязных компонент

2

2

9. Построение циклов и клик в графе

2

2

10. Определение изоморфизма графов

1




12.Алгоритм построения плоской укладки графа.

3

4

13. Метод разделяй и властвуй

1




14. Алгоритм Штрассена умножения матриц

2

1

15. Алгоритмы построения комбинаторных объектов

3

2

16. Понятие о параллельных алгоритмах

2




17.Понятие о классах Р и NР

2




ИТОГО

28

14



Содержание.

Предмет теория алгоритмов. Прикладное значение эффективности алгоритмов. Связь с дискретной математикой, математической кибернетикой, программированием. .

Необходимость оценки алгоритмов. Принципы оценки трудоемкости комбинаторных алгоритмов с помощью времени работы универсальной вычислительной машины. Трудоемкость «в худшем», трудоемкость «в среднем», трудоемкость «почти всегда». Структуры данных: массив, список, очередь, стек. Последовательное и связное хранение линейных списков. Операции над элементами структур.

Сортировка с помощью сравнений. Теорема о невозможности существования алгоритма сортировки в «худшем» и «в среднем»трудоемкостью лучшем, чем О(n log2n)

Сортировка вычерпыванием. Лексикографическая сортировка цепочек. Использо-вание ее для определения изоморфизма корневых деревьев.

Сортирующее дерево. Построение дерева с помощью операций пересыпки. Исполь-зование дерева для сортировки.

Определение 2-3-дерева. Структуры, реализуемые с помощью 2-3-деревьев: словарь, очередь с приоритетом. Операции над деревьями. Построение деревьев. Реализация алгоритма Краскала построения минимального остовного дерева с помощью деревьев. Реализация алгоритма Прима построения минимального остовного дерева

Схема исчерпывающего поиска с возвращением. Некоторые эвристические правила поиска. Алгоритм поиска в глубину. Определение с его помощью двусвязных компонент и точек сочленения. Использования поиска в глубину для построения фундаментального множества циклов и множества всех циклов.

Использования поиска с возвращением для построения клик графа и для определения изоморфизма графов.

Алгоритм построения плоской укладки графа и использование при его реализации специального поиска в глубину.

Метод разделяй и властвуй и теоремы о его трудоемкости. Алгоритм Штрассена эффективного умножения матриц.

Поиск в глубину для ориентированных графов.

Алгоритмы построения комбинаторных объектов: перестановок, сочетаний, разбиений.

Понятие о параллельных алгоритмах. Алгоритм Соллинга построения минимального остовного дерева.

Понятие о классах Р и NР. Списки наиболее известных NР-полных задач.

^ Раздел 2. Булевы функции
ЛИТЕРАТУРА

по курсу "Теория алгоритмов"
Основная:

Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979.

Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы.Теория и практика. М.: Мир, 1980.
Дополнительная:

Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. М.: Вильямс, 2000

Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. М.: Мир, 1981.

Кнут Д. Искусство программирования для ЭВМ. Т.1-3. М.: Мир, 1976-1977

Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.:МЦНМО. 1999

Разработчики:

Кафедра уравнений математической физики

Белорусского государственного университета

Доцент кафедры УМФ О.И.Мельников

Зав.кафедрой,

профессор Н.И. Юрчук
Согласована:

Управление учебной и научно-методической работы

Белорусского государственного университета
Начальник В.В.Самохвал




Похожие рефераты:

Рд бгу упрД 0001 – 2001
Внесена кафедрой уравнений математической физики механико-математического факультета бгу
Рд бгу упрД 0001 – 2001
Савчук В. П. кандидат физико-математических, доцент кафедры теоретической и прикладной механики механико-математического факультета...
Рд бгу упрД 0001 – 2001
Вярьвильская О. Н. кандидат физико-математических, доцент кафедры теоретической и прикладной механики механико-математического факультета...
Рд бгу упрД 0001 – 2001
Алехно Е. А. кандидат физико-математических, ассистент кафедры математические методы теории управления механико-математического факультета...
Рд бгу упрД 0001 – 2001
Мартыненко М. Д. доктор физико-математических наук, профессор кафедры теоретической и прикладной механики механико-математического...
Рд бгу упрД 0001 – 2001
Программа предназначена для студентов механико-математического факультета
Рд бгу упрД 0001 – 2001
Емеличев В. А. – профессор кафедры уравнений математической физики Белорусского государственного университета
Рд бгу упрД 0001 – 2001
Программа предназначена для студентов высших учебных заведений, основная специальность которых связана с математикой и механикой
Рд бгу упрД 0001 – 2001
Внесена кафедрой уравнений математической физики и Главным управлением учебной и научно-методической работы Белорусского государственного...
Рд бгу упрД 0001 – 2001
Внесена кафедрой уравнений математической физики и Главным управлением учебной и научно-методической работы Белорусского государственного...

Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
referatdb.ru
referatdb.ru
Рефераты ДатаБаза