О сложности восстановления частичного порядка

А. А. Абдель Маджид

Московский государственный университет имени М. В. Ломоносова, механико-математический факультет

Аннотация: Работа посвящена вопросу сложности восстановления частичного порядка на конечном множестве, если известно, что частичный порядок обладает какими-то наперед заданными свойствами. Рассматривается модель вычислений, в которой под сложностью понимается количество сравнений, необходимое для восстановления частичного порядка. Исследуются классы частично упорядоченных множеств, для которых задача восстановления порядка решается меньше чем за квадратичное число сравнений относительно количества элементов в множестве.

Ключевые слова: частичный порядок, конечное множество, восстановление порядка, сортировка, сравнение.