Четвер, 18 вересня 2014 Автор Опубліковано в Cтатті & Публікації

Обчислювальна геометрія і топологія

(10 голосів)
Перегляди: 49395 разів
Обчислювальна геометрія і топологія Обчислювальна геометрія і топологія

Теперішній проект сертифікованого курсу "Advanced computational mathematics", що здійснюється спільно з Вюрцбурзьким Університетом, розпочався з розмов про обчислювальні аспекти геометрії, що їх провадив Александер Вольф з професором Тарасом Банахом та іншими львівськими математиками під час візиту до Львова представницької делегації з Вюрцбурга. Автор цих рядків був присутній на одній з таких розмов, що відбулася у знаменитій "Шотландській кав'ярні".

Обчислювальна геометрія - це розділ інформатики (computer science), що займається алгоритмічними аспектами геометрії. Однією з найпростіших (стосовно формулювання) проблем обчислювальної геометрії є проблема знаходження пари точок, що реалізують найменшу відстань, серед n заданих точок на площині. Атака повного перебору (brute force) дає змогу знайти шукану пару за n(n-1)/2 кроки. Іншими словами, такий алгоритм вимагає O(n2) часу. Класичний результат обчислювальної геометрії полягає у знаходженні алгоритму, що вимагає O(n logn) часу.

Згадаймо інші задачі обчислювальної геометрії:

1) Знаходження опуклої оболонки системи точок у евклідовому просторі.

2) Знаходження діаграми Вороного (Voronoi diagram) системи точок у евклідовому просторі.

Діаграма Вороного системи точок - розбиття простору на області, кожна з яких складається з точок, ближчих до якоїсь точки з системи, ніж до інших точок системи. Георгій Вороний (1868-1968) - видатний український математик.

Діаграма Вороного

3) Знаходження тріангуляції Делоне (Delaunay triangulation) системи точок на площині.

Тріангуляція Делоне системи точок - розбиття площини на трикутники, таке що жодна точка системи не лежить всередині жодного кола, описаного навколо трикутника тріангуляції. Борис Делоне (1890-1980) - російський математик, учень Г. Вороного.

Тріангуляція Делоне

Мені якось зустрілася стаття з задачею:

4) Знаходження відстані Канторовича між ймовірнісними мірами зі скінченними носіями на відрізку (або на колі).

У статті [М. М. Заричный, О. Р. Никифорчин, “Функтор емкостей в категории компактов”, Матем. сб., 199:2 (2008), 3–26; англ. версія: M. M. Zarichnyi, O. R. Nykyforchyn, Capacity functor in the category of compacta, Sbornik: Mathematics (2008),199(2):159–184] запроваджено аналог метрики Канторовича для неадитивних мір (ємностей). Одразу приходимо до відкритої проблеми:

4') Знаходження відстані між ємностями зі скінченними носіями на відрізку (або на колі).

Природна гіпотеза: алгоритм вимагає істотно більше часу, аніж для мір. Але наскільки більше?

Тісно пов'язаною з обчислювальною геометрією є обчислювальна топологія. Це відносно нова галузь топології, що присвячена знаходженню ефективних алгоритмів для розв'язування топологічних задач. Прикладом може служити задача розпізнавання тривимірної сфери серед тріангульовних тривимірних многовидів.

Стійкі гомології (persistent homology)

Близьким до обчислювальної топології є топологічний аналіз даних (topological data analysis, TDA), він полягає у зображенні точкових наборів даних симпліціальними комплексами і обчисленні груп гомологій цих комплексів (спеціально для TDA створено теорію так званих стійких гомологій). Авторові цих рядків пощастило бути серед численних слухачів пленарної доповіді одного з класиків обчислювальної топології Г. Карлссона на 6-му Європейському математичному конгресі.

Застосування обчислювальної геометрії та обчислювальної топології охоплюють комп'ютерну графіку, комп'ютерний зір, аналіз даних (to be continued). 

На завершення наведу міркування математика Володимира Воєводського, лауреата медалі Філдса:

- Що стосується питання про зближення прикладної і чистої математики, то у мене є ось яка картинка. Чиста математика працює з моделями високого рівня абстрактності і малої складності (математики цю малу складність люблять називати елегантністю). Прикладна математика працює з моделями більш конкретними, але високого рівня складності (багато змінних, рівнянь і т.д.). Цікаві застосування ідей сучасної чистої математики швидше за все лежать в області високої абстрактності і високої складності. Ця область зараз практично недоступна, багато в чому через обмежену здатність людського мозку працювати з такими моделями. Коли ми навчимося використовувати комп'ютери для роботи з абстрактними математичними об'єктами, ця проблема поступово відійде на другий план і з'являться цікаві застосування ідей сьогоднішньої абстрактної математики.

Можна припустити, що курс "Advanced computational mathematics" є кроком саме у цьому напрямку.

М.М. Зарічний

доктор фізико-математичних наук, професор кафедри алгебри, топології та основ математики, заслужений професор Львівського національного університету імені Івана Франка

Додати коментар

Захисний код
Оновити

Наші контакти

Ідея, дизайн, верстка і т.д.:
Олег Романів