Программа по дисциплине «Вычислительные задачи геометрии» для специальности: 511200 Математика. Прикладная математика (магистратура) очная форма обучения icon

Программа по дисциплине «Вычислительные задачи геометрии» для специальности: 511200 Математика. Прикладная математика (магистратура) очная форма обучения


Смотрите также:
Программа по дисциплине современная алгебра для специальности 511200 Математика...
Программа по дисциплине Избранные главы алгебры и теории чисел для специальности 511200...
Программа дисциплины дс...
Рабочая программа по дисциплине «теория сложности алгоритмов и вычислений» для специальности...
Программа по дисциплине Линейные топологические пространства для специальности 511200 Математика...
Программа дисциплины дс. 11...
Государственный образовательный стандарт высшего профессионального образования направление...
Программа обучения студентов ( Syllabus ) по дисциплине «Вариационное исчисление и методы...
Программа дисциплины ф...
Программа государственного экзамена «Вычислительная математика» для студентов проходящих...
Учебная программа по специальности 01. 02. 00 Прикладная математика и информатика...
Попов А. М. Лекции по линейной алгебре...



Загрузка...
скачать


ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ




ГОУ ВПО «УДМУРТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ»




Математический факультет



Кафедра алгебры и топологии


РАБОЧАЯ

ПРОГРАММА



по дисциплине

«Вычислительные задачи геометрии»


для специальности: 511200 Математика. Прикладная математика (магистратура)

очная форма обучения


Курс ……………………………..………….. 2

Семестр……………………………………... 4

Всего аудиторных часов…………………… 65

Лекции, час………………………………….. 34

Практические (семинарские) занятия, час… 17

Самостоятельная работа, час……………… 49

Зачет (семестр)……………………………… 4


Ижевск 2007


Рабочая программа составлена на основании __^ Государственного образовательного

(название документа, дата утверждения)

стандарта по специальности____________________________________________________


Составители рабочей программы

профессор, д.ф.-м.н. ______________ А.А.Грызлов

(должность, ученое звание, степень) (подпись) (Ф.И.О.)


Рабочая программа утверждена на заседании кафедры алгебры и топологии


«_____»______________ 2007 г.


Заведующий кафедрой ______________ А.А. Грызлов

(подпись) (Ф.И.О.)


Декан факультета ______________ __^ А.С. Мерзляков

(подпись) (Ф.И.О.)


Решение методической комиссии математического факультета


«____»_______________ 2007 г.


Председатель

методической комиссии ______________ Н.А. Баранова_____

(подпись) (Ф.И.О.)


Согласовано с библиотекой УдГУ _______________ 2007 г.


Директор библиотеки УдГУ _______________ ________________

(подпись) (Ф.И.О.)


^ 1. Организационно-методический раздел


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

Данная дисциплина тесно связана с дисциплиной «Геометрическое моделирование».

Вычислительная геометрия имеет широкий круг применений, включающий распознавание образов, робототехника, машинная графика, раскрой материалов и т. д.

Вычислительная геометрия опирается на много разделов как классической, так и современной математики.

Результатом освоения курса является приобретение основ знаний в области вычислительной геометрии, овладение основными методами решения задач и их приложений.

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

^ 2. Объем и распределение часов по темам и видам занятий.




Наименование разделов и тем

Всего

Лекций

Лаборатор.

Самостоят.

работа




Основные понятия, группы, структуры.

8

4




4




Геометрический поиск

19

6

4

9




Выпуклые оболочки. Основные алгоритмы, приложения.

19

6

4

9




Близость. Основные алгоритмы, варианты и обобщения.

18

6

3

9




Пересечения.

19

6

4

9




Геометрия прямоугольников.

17

6

2

9







100

34

17

49


^ 3. Формы контроля знаний.


В конце семестра предусмотрен зачет.


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


Темы лекционных занятий и их краткое содержание.


  1. Основные понятия, термины, структура. Методические истоки дисциплины. Алгоритмические основы. Геометрические предпосылки. Модели вычислений.

  2. Геометрический поиск. Основные понятия. Задачи локализации точки. Простые случаи. Локализация точки на планарном разбиении. Методы полос, цепей, метод планарного сепаратора, метод трапеций.

Задачи регионального поиска. Метод многомерного двоичного дерева, метод прямого доступа, метод дерева регионов.

  1. Выпуклые оболочки. Основные алгоритмы. Алгоритм построения выпуклой оболочки на плоскости. Выпуклые оболочки в пространствах размерности больше двух. Выпуклая оболочка простого многоугольника. Приложения к статистике.

  2. Близость. Задачи, связанные с близостью. Задача о единственности элементов. Решение задачи о ближайшей паре методом «разделяй и властвуй». Решения задач о близости методом локусов; диаграмма Вороного.

Евклидовы минимальные остовые деревья. Евклидова задача о коммивояжере. Триангуляция с ограничениями.

  1. Пересечения. Некоторые приложения: задачи удаления невидимых линий и поверхностей, распознавание образов, трассировка и размещение. Плоские приложения. Пересечение выпуклых многоугольников. Пересечение звездных многоугольников. Пересечение отрезков. Пересечение полуплоскостей и задачи линейного программирования. Трехмерные приложения.

  2. Геометрия прямоугольников. Некоторые приложения геометрии прямоугольников; проектирование интегральных схем. Мера и периметр объединения прямоугольников. Замыкание объединения прямоугольников. Пересечение прямоугольников и связанные с этим задачи.


Вопросы к зачету.


  1. Метод полос локализации точки.

  2. Метод цепей локализации точки.

  3. Метод планарного сепаратора.

  4. Метод детализации триангуляции.

  5. Метод трапеций.

  6. Метод прямого доступа.

  7. Метод дерева регионов.

  8. Основные задачи построения выпуклой оболочки.

  9. Алгоритм построения выпуклой оболочки на плоскости.

  10. Обход методом Джарвиса.

  11. Алгоритм типа «разделяй и властвуй».

  12. Выпуклая оболочка простого многоугольника.

  13. Приложение выпуклых оболочек к статистике.

  14. Основные задачи, связанные с близостью.

  15. Решение задачи о ближайшей паре методом локусов.

  16. Диаграмма Вороного.

  17. Евклидовы минимальные остовые деревья.

  18. Евклидова задача о коммивояжере.

  19. Пересечение выпуклых многоугольников.

  20. Пересечение образов.

  21. Пересечение полуплоскостей.


^ 5. Учебно-методическое обеспечение курса.


Основная литература

  1. Ф. Препарата, М. Шеймос. Вычислительная геометрия. Введение. М.: Мир, 1989, 478 с.

  2. Роджерс Д., Адамс Дж. Математические основы машинной графики. М: Мир, 2001.

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

  4. Горелик А.Л., Скрипкин В.А. Методы распознавания. М.: Высшая школа, 1989.


Дополнительная литература

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

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

  3. Саати Т. Цельночисленные методы оптимизации и связанные сними экстремальные проблемы. М.: Мир, 1973.

  4. Рокефеллер А. Выпуклый анализ. М.: Мир, 1971.





Скачать 66.01 Kb.
оставить комментарий
Дата02.10.2011
Размер66.01 Kb.
ТипПрограмма, Образовательные материалы
Добавить документ в свой блог или на сайт

Ваша оценка этого документа будет первой.
Ваша оценка:
Разместите кнопку на своём сайте или блоге:
rudocs.exdat.com

Загрузка...
База данных защищена авторским правом ©exdat 2000-2017
При копировании материала укажите ссылку
обратиться к администрации
Анализ
Справочники
Сценарии
Рефераты
Курсовые работы
Авторефераты
Программы
Методички
Документы
Понятия

опубликовать
Загрузка...
Документы

Рейтинг@Mail.ru
наверх