Computer Topology

2020/2021

Academic Year

RUS

Instruction in Russian

10

ECTS credits

Delivered at:

Department of Fundamental Mathematics (Faculty of Informatics, Mathematics, and Computer Science (HSE Nizhny Novgorod))

Course type:

Elective course

When:

4 year, 1, 2 module

Instructor

Yakovlev, Evgeniy

Программа дисциплины

Аннотация

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

Цель освоения дисциплины

• Целями освоения дисциплины «Компьютерная топология» являются знакомство с базовыми понятиями и конструкциями комбинаторной топологии; изучение методов и алгоритмов вычисления топологических характеристик и элементов полиэдров, используемых на практике в качестве компьютерных моделей реальных объектов.

Планируемые результаты обучения

• Знание основных понятий комбинаторной топологии, умение выполнять симплициальное и клеточное разбиение стандартных полиэдров
• Знание основных понятий теории гомологий. Умение вычислять группы гомологий двумерных и трехмерных полиэдров с помощью клеточных разбиений, а также с помощью точных гомологических последовательностей.
• Знание критериев многообразий и псевдомногообразий, критериев ориентируемости многообразий. Умение находить особенности полиэдров размерностей 2 и 3, применять алгоритм построения ориентации 2-многообразия
• Знание алгоритмов эффективного вычисления групп гомологий, умение применять их на моделях с небольшим числом симплексов
• Знание теории индексов пересечения и методов их вычисления. Умение вычислять индексы пересечения циклов на многообразиях размерностей 2 и 3
• Знание алгоритмов условной минимизации путей и циклов. Умение строить симплициальную схему накрывающего полиэдра по заданной индексной вектор-функции.
• Знакомство с применениями топологии в компьютерном моделировании и механике сплошной среды

Содержание учебной дисциплины

• Базовые конструкции комбинаторной топологии
  Симплициальные комплексы и схемы. Полиэдры. Клеточные разбиения. Связность и сильная связность, алгоритмы вычисления компонент связности и сильной связности. Однородность. Барицентрические подразделения.
• Группы симплициальных и клеточных гомологий по модулю 2
  Определение и простейшие свойства групп гомологий. Топологический смысл нульмерных гомологий. Группы относительных гомологий, гомологическая последовательность пары. Последовательности Майера-Виеториса. Клеточные гомологии.
• Триангулированные многообразия
  Комбинаторные критерии многообразий. Алгоритмы поиска особых вершин и ребер двумерных и трехмерных полиэдров. Псевдомногообразия. Ориентируемость и ориентации многообразий. Алгоритм для проверки на ориентируемость и задания ориентации двумерного триангулированного многообразия.
• Вычисление базисов групп гомологий
  Матричные алгоритмы. Поиск фундаментальных циклов графа. Вычисление базисов групп гомологий двумерных псевдомногообразий без применения матриц. Теорема Александера-Понтрягина и алгоритм построения двумерных базисных циклов разветвленной поверхности. Алгоритмы вычисления базиса группы одномерных гомологий разветвленной поверхности. Группы гомологий трехмерного тела.
• Индексы пересечения
  Барицентрические звезды и группы гомологий. Индексы пересечения и их свойства. Группы когомологий и изоморфизмы Пуанкаре и Лефшеца. Алгоритмы для вычисления индексов пересечения на двумерных и трехмерных компактных многообразиях. Некоторые методы вычисления базисов групп когомологий.
• Минимальные пути и циклы
  Индексная вектор-функция и ее свойства. Алгоритм построения индексной вектор-функции. Накрывающие полиэдры. Алгоритм построения пути с минимальным весом, соединяющего заданные вершины и гомологичного заданному пути. Поиск минимальных циклов в заданных классах одномерных гомологий.
• Применения топологических алгоритмов
  Выделение ручек двумерных многообразий. Обнаружение и устранение топологических дефектов компьютерных моделей. Применение топологии в некоторой численной схеме решения трехмерных задач механики сплошной среды.

Элементы контроля

• Контрольная работа
  Задание содержит 2 задачи.
• Итоговая контрольная работа
  Задание содержит 1 задачу и 1 теоретический вопрос.

Промежуточная аттестация

• Промежуточная аттестация (2 модуль)
  0.6 * Итоговая контрольная работа + 0.4 * Контрольная работа

Список литературы

Рекомендуемая основная литература

• Вычислительная топология, учебник, 213 с., Яковлев, Е. И., 2005
• Задачи по топологии, Независимый Московский ун-т, 38 с., Прасолов, В. В., 2008
• Элементы комбинаторной и дифференциальной топологии, 2-е изд., испр. и доп., 358 с., Прасолов, В. В., 2014

Рекомендуемая дополнительная литература

• Виро О.Я., Иванов О.А., Нецветаев Н.Ю. - Элементарная топология - Московский центр непрерывного математического образования - 2010 - 352с. - ISBN: 978-5-94057-587-0 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/9313
• Матвеев С.В. - Алгоритмическая топология и классификация трехмерных многообразий - Московский центр непрерывного математического образования - 2007 - 456с. - ISBN: 978-5-94057-209-1 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/9370
• Скопенков А.Б. - Алгебраическая топология с геометрической точки зрения - Московский центр непрерывного математического образования - 2016 - 270с. - ISBN: 978-5-4439-2477-9 - Текст электронный // ЭБС ЛАНЬ - URL: https://e.lanbook.com/book/71854