Проекты

Методы повышения эффективности и надежности реализации динамических структур данных

2009-2011 г.г.
рук. Соколов А.В.
РФФИ, № 09-01-00330-a

Анализируются некоторые методы реализации приоритетной очереди. Допускаются операции «вставить», «удалить наибольший», «найти наибольший». Предполагаются известными вероятности выполнения операции “вставить” для каждого приоритета. Операции «удалить наибольший» и «найти наибольший» выполняются с равной вероятностью для всех приоритетов. Рассмотрены способы представления очереди в виде массива и в виде нескольких FIFO-очередей. Предложены математические модели этих методов, и на их базе методы сравниваются с точки зрения минимизации средней доли потерянных элементов на бесконечном времени и максимизации среднего времени до переполнения памяти.
Последние изменения: 16 февраля 2012