Анотація до роботи:

Резнік Ю.А. Дослідження властивостей цифрових дерев з адаптивним гілкуванням.– Рукопис. Дисертації на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.03 – математичне та програмне забезпечення обчислювальних машин і систем. – Київський національний університет імені Тараса Шевченка. Київ, 2005.

Дисертацію присвячено дослідженню властивостей цифрових дерев з адаптивним гілкуванням та розробці ефективних алгортмів пошуку інформації що грунтуються на застосуванні таких дерев. У роботі створено узагальнену аналітичну модель для класу цифрових дерев з адаптивним гілкуванням і проведено аналіз локалізації їх досяжних просторово-часових характеристик. На основі цього аналізу виявлено режими маючі найбільш практичний інтерес і розроблено алгортми побудови такіх дерев. Зокрема, у роботі створено нові алгоритми побудови дерев з лог-логаріфмічним та з константним середнім часом доступу.

Основним результатом дисертаційної роботи є теоретичне вивчення класу цифрових дерев з адаптивним гілкуванням, розробка та експериментальне дослідження алгоритмів динамічної побудови таких дерев та створення прикладних систем на їх основі.

В дисертаційній роботі поставлено та вирішено такі задачі:

1. порівняльний аналіз та класифікація існуючих методів інформаційного пошуку, що грунтуються на застосуванні цифрових дерев;

2. створення узагальненої аналітичної моделі для класу цифрових дерев з адаптивним гілкуванням;

3. дослідження локалізації просторово-часових характеристик, які можуть бути досягнуті цифровими деревами з адаптивним гілкуванням;

4. розробка та експериментальне порівняльне дослідження ефективності прикладних алгоритмів інформаційного пошуку на основі цифрових дерев з адаптивним гілкуванням;

5. розробка методики збільшення продуктивності дерев шляхом симетруючого перетворення рядків вхідних даних.

Найбільш перспективними для застосування результатів даної роботи є:

інформаційно-пошукові системи;

програми та системи критично залежні від ефективності пошукових операцій: web-сервери, IP-роутери, сервери систем мобільного зв’язку;

програми та системи, що використовують цифрові дерева для внутрішнього представлен-ня даних: CAD-системи, системи обробки зображень, геоінформаційні системи, системи мовного перекладу, алгоритми стиснення даних.

Публікації автора:

1. Резник Ю.А. О пространственно-временной эффективности цифровых деревьев с адаптивным многоразрядным ветвлением // Кибернетика и системный анализ. –2003.- № 1.- С.152-162.

2. Резник Ю. А. О средней плотности и избирательности узлов в многоразрядных цифровых деревьях // Математические машины и системы. –2002.- № 1.- С.70-83.

3. Резник Ю.А. Некоторые результаты касающиеся деревьев с адаптивным ветвлением // Математические машины и системы. –2001.- № 1-2.- С.55-65.

4. Резник Ю.А. On compact level partitioning of digital trees // Математические машины и системы. –1998.- № 1.- С. 38-45.

5. Reznik Yu. A. Some Results on Tries with Adaptive Branching // Theoretical Computer Science. - 2002. – Vol. 289, № 2. - P.1009-1026.

6. Reznik Yu. A., Szpankowski W. On the Average Redundancy Rate of the Lempel-Ziv Code with the K-Error Protocol // Information Sciences.-2001.- Vol. 135.- P. 57--70.

7. Reznik Yu. A., On the Average Density and Selectivity of Nodes in Multi-Digit Tries // Proc. 2^nd ACM-SIAM Workshop on Analytic Algorithmics and Combinatorics (ANALCO’05).- Vancouver, BC, Canada, January 22, 2005. – P.58-69.

8. Reznik Yu. A., Anisimov A. V., Using Tries for Universal Data Compression // Proc. 3^rd Intl. Colloquium on Mathematics and Computer Science (MathInfo’04).- Vienna, Austria, September 13-17, 2004.- P. 348-350.

9. Reznik Yu. A. On Tries, Suffix Trees, and Universal Variable-Length-to-Block Codes // Proc. IEEE International Symposium on Information Theory (ISIT’02).- Lausanne, Switzerland, June 30 - July 5, 2002.- P. 287.

10. Reznik Yu. A., Szpankowski W. Improved behaviour of tries by the symmetrization of the source // Proc. IEEE Data Compression Conference (DCC’02), Snowbird, Utah, USA, April 2-4, 2002.- P. 253-262.

11. Reznik Yu. A. Some Results on Tries with Adaptive Branching // Proc. 6th Annual International Computing and Combinatorics Conference (COCOON'00), Bondi Beach, Sydney, Australia, July 26-28, 2000 / Lecture Notes in Computer Science, Vol. 1858.- Springer-Verlag, New York, 2000.- P. 148-158.

12. Reznik Yu. A. LZRW1 Without Hashing // Proc. Data Compression Conference (DCC'98), Snowbird, Utah, USA, March 30-April 1, 1998.- P. 569.