АНАЛИЗ МНОГОУРОВНЕВЫХ ПИРАМИД
Объект исследования: многоуровневая пирамида и основные операции над ней.
Результаты, полученные лично автором: собраны материалы в английском сегменте интернета, разработана программа, проанализированы результаты тестирования.
Многоуровневая пирамида – структура данных, представляющая собой биномиальную пирамиду с большим количеством уровней.
Многоуровневые пирамиды используются для сортировки элементов, а так же поиска необходимого элемента. Таким образом, 1 миллион элементов с помощью такой пирамиды можно обойти всего за 20 шагов.
Чаще всего применяются следующие операции над пирамидами: объединение, вставка, удаление, удаление минимального и максимального элемента.
Операция объединение. В корне результирующего дерева находится максимальный из корней исходных деревьев. Левое поддерево максимального корня становится правым поддеревом меньшего корня.
Операция вставка. Новый элемент добавляется в лесу как дерево ранга 0, и последовательные слияния выполняются до тех пор, пока еще нет двух деревьев одного и того же ранга. (Это эквивалентно добавлению 1 к числу в двоичном представлении.)
Удаление максимального и минимального элемента. Корень с наименьшим или наибольшим элементом удаляется, оставляя при этом все поддеревья этого элемента в качестве независимых деревьев. Деревья равных рангов будут объединены до тех пор пока нет двух деревьев одного и того же ранга.
|
|
|
Удаление. Ключ узла для удаления многократно меняется местами со своими предками до корня этого дерева. Затем он удаляется по правилу удаления максимального (или минимального) элемента.
Ниже приведены необходимые исследования для операций удаления и удаления максимума. Наша структура Пирамиды достигает, в амортизационном смысле, постоянных затрат на вставку и find-min, и логарифмическая стоимость в основном log n + O(log log n) сравнения за удаление и удаление максимума (минимума).
Наша модифицированная структура Пирамиды достигает постоянной сложности для вставки и find-min и уменьшения ключа сложности, и логарифмические стоимость в основном log n + O(log log n) сравнений за удаление и удаление максимума (минимума).
Амортизационное количество сравнений, выполняемых за операцию удаления и удаления максимума (минимума) в нижнем слое, ограничена log n + O(1).
Материал поступил в редколлегию 03.04.2017
УДК 004.4
А.В. Кузин
Научный руководитель: ассистент кафедры «Информатика и программное обеспечение», Е.В. Коптенок
on-clear@inbox.ru
РАЗРАБОТКА СПОСОБА ПРЕДСТАВЛЕНИЯ ДЛИННЫХ ЧИСЕЛ
В ПАМЯТИ КОМПЬЮТЕРА И АЛГОРИТМОВ ВЫПОЛНЕНИЯ
АРИФМЕТИЧЕСКИХ ОПЕРАЦИЙ НАД НИМИ
|
|
|
Объект исследования: способы представления длинных чисел в памяти компьютера.
Результаты, полученные лично автором: разработан алгоритм представления в памяти компьютера чисел неограниченной длины и точности, а также алгоритмы выполнения арифметических действий над ними.
Длинная арифметика применяется во многих сферах, например, в криптографии, разработке математического ПО, а также в сферах, требующих вычислений больших величин или высоких точностей расчетов: астрономия, океанология, разработка ПО для военных нужд. Например, при реализации метода шифрования RSA, криптосистемы Рабина или схемы Эль-Гамаля требуется обеспечить точность результатов умножения и возведения в степень порядка 10309. Причем, требуется не столько вычисление очень больших величин, но и высокая точность (например, 50-70 знаков после запятой в десятичном представлении).
На данный момент распространенными способами являются хранение длинных чисел в массиве поразрядно. Недостатком такого метода является недостаточно гибкая работа с памятью, а также то, что большинство алгоритмов работают только с целыми числами. Также можно представить числа в памяти путем факторизации или разложения на простые множители, но в таком случае невозможно выполнение некоторых арифметических операций.
|
|
|
Разработан алгоритм поразрядного представления числа в памяти на основе динамических структур. Число хранится в виде стека из ячеек-разрядов, связанных между собой в двусвязный список. Одна ячейка числа имеет основание 103. Доступ напрямую осуществляется к трем ячейкам: старшему разряду, младшему разряду целой части и младшему разряду дробной части. Хранение длинного числа в памяти представлено на Рис. 4:
Рис. 4 Организация хранения числа в памяти компьютера
Операции сложения, вычитания и умножения выполняются поразрядно, с проверкой всех ячеек на переполнение. Деление реализовано с использованием алгоритма вычитания на основе последовательности действий при делении чисел в столбик. Прекращается деление при нулевом остатке или достижении заданной точности.
Возведение в степень осуществляется путем представления показателя степени в виде произведений и степеней двойки (например, a10=((a2)2)*a)2. Данный алгоритм делает возведение в степень тем быстрее, чем больше показатель степени (а он также может быть длинным числом).Факториал вычисляется путем рекурсивного умножения, так как для длинных чисел нет одновременно эффективного и экономного по памяти метода.
|
|
|
На основе полученных результатов разработана программа «Калькулятор длинных чисел. Перспективами продолжения исследований по данной тематике является написание библиотеки для вычисления значения математических функций (тригонометрические, экспоненциальные, логарифмические, степенные и т.д.) для длинных чисел.
Материал поступил в редколлегию 24.04.2017
УДК 004.05
О.К. Левкина
Научный руководитель: доцент кафедры «Информатика и программное обеспечение», к.т.н., А.О. Трубаков
mollielufkin@gmail.com
Дата добавления: 2018-10-27; просмотров: 194; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!