Препринт
Interpretations of Linear Orderings in Presburger Arithmetic
Heaps are well-studied fundamental data structures, having myriads of applications, both theoretical and practical. We consider the problem of designing a heap with an “optimal” extract-min operation. Assuming an arbitrary linear ordering of keys, a heap with n elements typically takes O(log n) time to extract the min-imum. Extracting all elements faster is impossible as this would violate the Ω(n log n) bound for comparison-based sorting. It is known, however, that is takes only O(n + k log k) time to sort just k smallest elements out of n given, which prompts that there might be a faster heap, whose extract-min performance depends on the number of elements extracted so far. In this paper we show that is indeed the case. We present a version of heap that performs insert in O(1) time and takes only O(log ∗ n + log k) time to carry out the k-th extraction (where log ∗ denotes the iterated logarithm). All the above bounds are worst-case.
Эта публикация представляет собой сборник отдельных статей "Третьей Международной конференции по динамике информационных систем», которая состоялась в университете Флориды, 16-18 февраля 2011 года. Цель данной конференции заключалась в том, чтобы собрать вместе ученых и инженеров из промышленности, правительства и научных кругов, чтобы они смогли обменяться новыми открытиями и результатами в вопросах, имеющих отношение к теории и практике динамики информационных систем. Динамика информационных систем: математическое открытие представляет собой современное исследование и предназначается студентам – аспирантам и исследователям, которые интересуются самыми последними открытиями в информационной теории и динамичных системах. Ученые других дисциплин могут также получить пользу от применения новых разработок в своих областях исследований.
Heaps are well-studied fundamental data structures, having myriads of applications, both theoretical and practical. We consider the problem of designing a heap with an “optimal” extract-min operation. Assuming an arbitrary linear ordering of keys, a heap with n elements typically takes O(log n) time to extract the minimum. Extracting all elements faster is impossible as this would violate the Ω (nlog n) bound for comparison-based sorting. It is known, however, that is takes only O(n+ klog k) time to sort just k smallest elements out of n given, which prompts that there might be a faster heap, whose extract-min performance depends on the number of elements extracted so far. In this paper we show that this is indeed the case. We present a version of heap that performs insert in O(1) time and takes only O(log ∗ n+ log k) time to carry out the k-th extraction (where log ∗ denotes the iterated logarithm). All the above bounds are worst-case. © 2018, Springer Science+Business Media, LLC, part of Springer Nature.
Сборник составлен по результатам исследований молодых ученых, аспирантов и студентов МЭСИ, а также ряда вузов Москвы, Йошкар-Олы, Магнитогорска, Махачкалы, Пензы, Саранска, Саратова, Улан-Удэ. Рассмотренные на конференции (июнь 2011 г.) результаты исследований посвящены вопросам статистической методологии, применению математико-статистических и эконометрических методов в различных отраслях экономики и социальной сфере. Обобщается зарубежный опыт статистического анализа ряда проблем экономической и социальной жизни. Сравнивается эффективность различных методов, формулируются рекомендации по их выбору в зависимости от специфики решаемой задачи.
В основе настоящего учебного пособия лежит специальный курс по выбору студента, прочитанный автором на механико - математическом факультете МГУ им. М.В. Ломоносова в 2010-2012 учебных годах. Пособие знакомит читателя с методом параметрикса и его дискретным аналогом, развитым в самое последнее время автором пособия и его коллегами-соавторами. Оно объединяет воедино материал, который ранее содержался только в ряде журнальных статей. Не стремясь к максимальной общности изложения, автор ставил целью продемонстрировать возможности метода при доказательстве локальных предельных теорем о сходимости марковских цепей к диффузионному процессу и при получении двусторонних оценок типа Аронсона для некоторых вырожденных диффузий.
Статьи данного сборника написаны на основе докладов, сделанных в 2011 г. на социологическом факультете МГУ им. М.В. Ломоносова на заседании XIV Междисциплинарного ежегодного научного семинара "Математическое моделирование социальных процессов" им. Героя Социалистического труда академика А.А. Самарского.
Издание предназначено для научных сотрудников, преподавателей, учащихся вузов и научных учреждений РАН, интересующихся проблемами, разработкой и внедрением методологии математического моделирования социальных процессов.