Введение в топологические пространства. Программирование конечных топологий на Java

[tagir_valeev]

Чем не понравился стандартный HashSet? Ваша реализация FSet даёт линейную сложность на contains и квадратичную на subset и equals.

[ProPupil]

Тем, что его методы addAll и retainAll, представляющие собой объединение и пересечение соответственно, меняют объект, к которому они применены, а здесь мне необходима неизменяемость объекта после того, как я его проинициализировал.

[tagir_valeev]

Ну да, а ваш метод add, конечно, не меняет объект после инициализации. Ограничить функционал всегда можно через делегирование. Вот как-то так:

public class FSet<T> {
  private final Set<T> set;

  public FSet(Collection<? extends T> src) {
    set = new HashSet<>(src);
  }

  public FSet<T> union(FSet<T> other) {
    FSet<T> result = new FSet<>(set);
    result.set.addAll(other.set);
    return result;
  }

  public FSet<T> intersect(FSet<T> other) {
    FSet<T> result = new FSet<>(set);
    result.set.retainAll(other.set);
    return result;
  }
  ...
}

Будет и существенно быстрее, и не будете отвлекаться на ненужные детали реализации.

[potan]

Тогда почему бы не писать на Scala или Clojure, которые поощеряют иммутабельные коллекции сохраняя хорошую асимптоматику?

[MaximChistov]

А можно для не изучавших тему топика хотя бы парочку примеров практического применения? Или его нет?

[ProPupil]

Конечные топологии широко используются в алгоритмах кластеризации и распознавания образов.

[MaximChistov]

_практического_
ну то есть как это можно использовать в реальной программе(код)

[esayanoleg]

Не код же вам распознавания образа приводить.

[aapetrov3]

Я как-то читал про число попарно негомеоморфных конечных топологических пространств — там оно растет очень быстро при росте размера множества.

А можно что-нибудь сказать про гомотопический тип? Какими могут быть гомотопичекие группы, гомологии конечного пространства? Вопросы их вычисления, кстати наверное тоже можно алгоритмизировать.

[Mrrl]

А можно что-нибудь сказать про гомотопический тип? Какими могут быть гомотопичекие группы, гомологии конечного пространства?

Нашлось такое обсуждение:
maxmornev.livejournal.com/6687.html
Правда, выводов я не понял. Кажется, «скорее, нет».

[Mrrl]

Число неэквивалентных T0-топологий (в которых для любых двух точек есть открытое множество, содержащее ровно одну из них) равно числу частичных порядков на этом множестве, и образует последовательность OEIS А000112
1, 1, 2, 5, 16, 63, 318, 2045, 16999, 183231, 2567284, 46749427, 1104891746, 33823827452, 1338193159771, 68275077901156, 4483130665195087

[potan]

Гомотопические группы предпологают наличия нетривиальных морфизмов из I = [0; 1]. В конечные пространства отобразить отрезок не получится.

[aapetrov3]

Ну почему не получится, можно например рассмотреть постоянное отображение. Вот пример четырехэлементного неодносвязного пространства Pseudocircle

[DmitriyN]

Посчитать формально можно, но там безумная комбинаторика и сложность алгоритмов будет просто дикая. Это относится и к сингулярным гомологиям и к гомотопическим группам.

[mikhanoid]

Вообще, было бы круто, если бы Вы ещё рассказали о счётных топологиях, в частности, о топологии Скотта. Она достаточно близкая к этому всему и полезная для программистов, придаёт значение тому, зачем нужны базы или монотонные отображения.

[Sayonji]

Как же без функции, которая дополняет систему подмножеств до топологии? Она же самая важная.

[Mrrl]

Вообще, утверждается, что любой конечной топологии соответствует частичный порядок: x<=y тогда и только тогда, когда x принадлежит замыканию одноэлементного множества {y}. А частичные порядки реализовывать гораздо проще, чем множества подмножеств: они требуют только N^2 бит. Нужно только переформулировать топологические понятия в терминах порядка. Особенно интересно, во что превратятся непрерывные отображения.

[hacklex]

Точка x из множества X называется точкой прикосновения множества M, лежащего в X, если каждая окрестность точки x содержит хотя бы одну точку из M
Точка x из множества X называется предельной точкой множества M, лежащего в X, если каждая окрестность точки x содержит хотя бы одну точку из M, отличную от X

(2)… точнее, если каждая отличная от {x} окрестность х? Или в случае, когда у х есть окрестность {x}, х не может быть предельной точкой?

[hacklex]

ага, всё ясно, второй вариант. Это всё моя привычка задавать вопросы сразу -__-'

[fuxx]

Спасибо! Будет интересно прочитат про темы предложенные в «Заключении».