| Title: | Исследование практической эффективности битовой оптимизации динамического программирования в информационно-компьютерных системах на примере задачи о рюкзаке 0-1 |
| Other Titles: | Optimization of computational modules in information and computer systems: a case study of the knapsack problem |
| Authors: | Марковец, Р. С. |
| Keywords: | материалы конференций;битовое множество;задача о рюкзаке;оптимизация алгоритмов;спортивное программирование;информационно-компьютерные системы;вычислительные модули |
| Issue Date: | 2026 |
| Publisher: | БГУИР |
| Citation: | Марковец, Р. С. Исследование практической эффективности битовой оптимизации динамического программирования в информационно-компьютерных системах на примере задачи о рюкзаке 0-1 = Optimization of computational modules in information and computer systems: a case study of the knapsack problem / Р. С. Марковец // Электронные системы и технологии : сборник материалов 62-й научной конференции аспирантов, магистрантов и студентов БГУИР, Минск, 13–17 апреля 2026 г. / Белорусский государственный университет информатики и радиоэлектроники ; редкол.: П. В. Камлач [и др.]. – Минск, 2026. – С. 67–69. |
| Abstract: | Экспериментально исследована практическая эффективность битовой
оптимизации динамического программирования для задачи о рюкзаке 0-1 в контексте
вычислительных модулей информационно-компьютерных систем. Установлено, что
реальное ускорение составляет от 15,6 до 21,0 раза в зависимости от распределения весов
предметов, что в 3-4 раза ниже теоретического предела ускорения в 64 раза. Выявлены
основные факторы расхождения: кэш-промахи при обработке битового множества,
накладные расходы библиотечной реализации и межсловные сдвиги. |
| Alternative abstract: | The practical efficiency of bit optimization of dynamic programming for the 0-1
knapsack problem in the context of computational modules of information and computer systems
has been experimentally studied. The actual speedup is found to range from 15.6 to 21.0 times
depending on the item weight distribution, which is 3-4 times lower than the theoretical speedup
limit of 64 times. The main factors contributing to this discrepancy are identified: cache misses
during bitset processing, overhead of the library implementation, and cross-word shifts. |
| URI: | https://libeldoc.bsuir.by/handle/123456789/64551 |
| Appears in Collections: | Электронные системы и технологии : материалы 62-й конференции аспирантов, магистрантов и студентов (2026)
|
