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




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


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




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




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



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


РАБОЧАЯ

ПРОГРАММА



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

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


для специальности: 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.


Дадаць дакумент у свой блог ці на сайт

Падобныя:

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

Программа по дисциплине «Вычислительные задачи геометрии» для специальности: 511200 Математика. Прикладная математика (магистратура) очная форма обучения iconПрограмма курса для студентов специальности 1-31 01 01-02 математика 1-31 03 03-02 прикладная математика
Автор: Касперко М. В., старший преподаватель кафедры алгебры, геометрии и методики преподавания математики ГрГУ

Программа по дисциплине «Вычислительные задачи геометрии» для специальности: 511200 Математика. Прикладная математика (магистратура) очная форма обучения iconРабочая учебная программа по дисциплине «Литература Швейцарии» для специальности «050303- иностранный язык» по циклу опд. В2 дисциплины по выбору Очная форма обучения
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования

Программа по дисциплине «Вычислительные задачи геометрии» для специальности: 511200 Математика. Прикладная математика (магистратура) очная форма обучения iconПрограмма дисциплины Русский язык и культура речи для направления 010400. 62 «Прикладная математика и информатика»
Государственное образовательное бюджетное учреждение высшего профессионального образования

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

Программа по дисциплине «Вычислительные задачи геометрии» для специальности: 511200 Математика. Прикладная математика (магистратура) очная форма обучения iconПрограмма дисциплины [Введите название дисциплины] для направления/ специальности [код направления подготовки и «Название направления подготовки» ] подготовки бакалавра/ магистра/ специалиста Правительство Российской Федерации
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки 231300....

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

Программа по дисциплине «Вычислительные задачи геометрии» для специальности: 511200 Математика. Прикладная математика (магистратура) очная форма обучения iconГрафик проведения встреч со студентами университета первого года обучения
Студенты направлений подготовки 140800 «Ядерные физика и технологии», 011200 «Физика», 223200 «Техническая физика», 010400 «Прикладная...

Программа по дисциплине «Вычислительные задачи геометрии» для специальности: 511200 Математика. Прикладная математика (магистратура) очная форма обучения iconРабочая программа составлена на основе типовой учебной программы для высших учебных заведений по специальности 1-31 03 01 "Математика (по направлениям)", утверждённой 29. 12. 2008 г. Рег.№ Тд g. 161 / тип
Рабочая программа составлена на основе типовой учебной программы для высших учебных заведений по специальности 1-31 03 01 “Математика...

Программа по дисциплине «Вычислительные задачи геометрии» для специальности: 511200 Математика. Прикладная математика (магистратура) очная форма обучения iconРабочая программа составлена на основе типовой учебной программы для высших учебных заведений по специальности 1-31 03 01 "Математика (по направлениям)", утверждённой 29. 12. 2008 г. Рег.№ Тд g. 161 / тип
Рабочая программа составлена на основе типовой учебной программы для высших учебных заведений по специальности 1-31 03 01 “Математика...

Размесціце кнопку на сваім сайце:
be.convdocs.org


База данных защищена авторским правом ©be.convdocs.org 2012
звярнуцца да адміністрацыі
be.convdocs.org
Галоўная старонка