Размещено на http://www.allbest.ru/

Міністерство освіти і науки України

Національний аерокосмічний університет ім. М.Є. Жуковського

“Харківський авіаційний інститут”

УДК 658.012.011.56:681.3.062:519.71

Методи алгоритмізації білінгових задач

у корпоративних комп'ютерних системах

05.13.06 - автоматизовані системи управління

та прогресивні інформаційні технології

Автореферат

дисертації на здобуття наукового ступеня

кандидата технічних наук

Бугас Дмитро Миколайович

Харків - 2005

анотація

Бугас Д.М. Методи алгоритмізації білінгових задач у корпоративних комп'ютерних системах. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.06 - автоматизовані системи управління і прогресивні інформаційні технології. - Національний аерокосмічний університет ім. М.Є. Жуковського “Харківський авіаційний інститут”, Харків, 2005.

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

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

Опрацьовано метод конструктивного перерахування типових алгоритмічних структур. Отримані оцінки кількості варіантів. Складено каталоги типових алгоритмічних структур.

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

Ключові слова: білінгова система, модель, алгоритм, граф, перетворення, перерахування, синтез.

Аннотация

Бугас Д.Н. Методы алгоритмизации биллинговых задач в корпоративных компьютерных системах. - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.06 - автоматизированные системы управления и прогрессивные информационные технологии. - Национальный аэрокосмический университет им. Н.Е. Жуковского “Харьковский авиационный институт”, Харьков, 2005.

Диссертация посвящена решению научно-прикладной задачи разработки алгоритмических моделей для построения биллинговых систем телекоммуникационных сетей.

При анализе тенденций развития телекоммуникационных систем выявлено, что интенсивное развитие информационных технологий, необходимость обмена огромными массивами информации внутри предприятий и между ними, критичность к скорости передачи данных и к их надежности делают проблему проектирования корпоративных сетей одной из первоочередных. Актуальными становятся проблемы оптимального использования каналов связи и тарификации всех предоставляемых провайдерами услуг. В структуре телекоммуникационных компаний биллинговые системы занимают одно из важнейших мест. Общей тенденцией является уменьшение расчетного периода, которое в пределе дает системы реального времени.

Проведенный анализ методов обработки информации в биллинговых системах показал, что бизнес-процессы в телекоммуникационной отрасли характеризируются высокой сложностью и обработкой большого объема транзакций, разветвленной логикой, высокими требованиями к скоростным характеристикам работы, особенно при “горячем” биллинге.

Для описания алгоритмических структур, процессов обработки информации в биллинговых системах предлагается использовать графы специального вида. В отличие от других известных представлений алгоритмов проверки, выполняемых вершинами - это логические функции от некоторых коммутативных условных переменных; в графе нет петель и замкнутых цепей. Рассмотрены свойства графов, выделен подкласс аранжируемых графов, в которых ярус вершин увеличивается. На множестве графов введены операции произведения, композиции и суммирования. Рассмотрены свойства - и разложимых графов и оценка их маршрутных характеристик. Определено количество цепей при наличии в графе кратных дуг. Для описания состава цепей графа введены диаграммы цепей. Рассмотрены способы формирования диаграмм для графов, полученных с помощью введенных операций.

Разработан метод построения минимальных по глубине алгоритмических структур, основанный на приведении алгоритмической структуры к бесповторному или слабоповторному виду. Рассмотрено решение поэтапных задач метода: последовательная декомпозиция диаграмм цепей по выбранным переменным, оценка количества и площади выделенных на диаграммах конфигураций. Метод позволяет минимизировать в том числе и рекурсивные схемы алгоритмов. Для его применения необходимо в исходном алгоритме выделить структурированные фрагменты. Применение этих преобразований позволяет сократить глубину алгоритма. Уменьшение глубины зависит от вида исходного алгоритма.

Предложен метод конструктивного перечисления аранжируемых и структурно-эквивалентных графов. Сформулированы задача оценки числа П- и -разложимых графов с n вершинами. Получены оценки для указанных видов графов. Разработан способ генерации аранжируемых и структурно- эквивалентных графов, который включает решение следующих поэтапных задач: формирование множества допустимых разбиений числа вершин на заданные подмножества, формирование вариантов построения графов для каждого варианта разбиения, анализ построенных вариантов и формирование каталога. Предложенный метод конструктивного перечисления позволяет составлять каталоги типовых представителей алгоритмических структур, необходимые при разработке алгоритмического обеспечения биллинговых процессов.

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

Достоверность результатов подтверждается внедрением их на ряде промышленных предприятий и в учебном процессе университета. Полученные результаты могут найти широкое применение при разработке алгоритмического обеспечения для автоматизированных систем с повышенными требованиями к быстродействию, работающих в реальном времени.

Ключевые слова: биллинговая система, модель, алгоритм, граф, преобразования, перечисление, синтез.

Abstract

Bugas D.N. Methods of billing tasks algorithmization in corporate computer systems. - Manuscript.

Thesis for a engineering science candidate's scientific degree competition by speciality 05.13.06 - automated control systems and progressive information technologies. - National Aerospace University Kharkiv aviation institute, Kharkiv, 2005.

The dissertation is devoted to a scientific-application task solution of algorithmic models development for telecommunication networks billing systems construction.

The graph algorithmic models for description of information processing in billing systems are offered. The method of algorithmic structures with commutative conditions transformation is developed. The application of transformations allows reducing depth of algorithm. The method of standard algorithmic structures design enumeration is developed. The estimations of variants quantity are obtained. The standard algorithmic structures catalogues are constructed.

For algorithmic structures development automation the software and hardware are offered. The results of work have allowed to improve processes of algorithmic creations.

Keywords: billing system, model, algorithm, graph, transformation, enumeration, synthesis.

Дисертацією є рукопис.

Робота виконана в Національному аерокосмічному університеті ім. М.Є. Жуковського “Харківський авіаційний інститут”, Міністерство освіти і науки України.

Науковий керівник: доктор технічних наук, професор Чумаченко Ігор Володимирович, Національний аерокосмічний університет ім. М.Є. Жуковського “ХАІ”, завідувач кафедри менеджменту.

Офіційні опоненти: доктор технічних наук, професор Краснобаєв Віктор Анатолійович, Харківський державний технічний університет сільського господарства, професор кафедри автоматизації та комп'ютерних технологій;

- кандидат технічних наук, старший науковий співробітник Кучук Георгій Анатолійович, Харківський університет повітряних сил, начальник науково-дослідного відділу інформаційно-обчислювального центру.

Провідна установа: Харківський національний університет радіоелектроніки, кафедра інформаційних управляючих систем, Міністерство освіти і науки України, м. Харків.

Захист відбудеться “24” червня 2005р. о 14 годині на засіданні спеціалізованої вченої ради Д 64.062.01 у Національному аерокосмічному університеті ім. М.Є. Жуковського “Харківський авіаційний інститут” за адресою: 61070, м. Харків, вул. Чкалова, 17, радіотехнічний корпус, ауд. 232.

З дисертацією можна ознайомитися у бібліотеці Національного аерокосмічного університету ім. М.Є. Жуковського за адресою: 61070, м. Харків, вул. Чкалова, 17.

Автореферат розісланий “13”травня 2005 р.

Вчений секретар спеціалізованої вченої ради Латкін М.О.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

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

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконувалася в рамках науково-дослідних робіт, що проводилися на кафедрах авіаційних приладів і вимірювань, менеджменту Національного аерокосмічного університету ім. М.Є. Жуковського “Харківський авіаційний інститут” відповідно до планів Міністерства освіти і науки України, Міністерства оборони України, постанов директивних органів з держбюджетних і госпдоговірних тем: “Розробка системного забезпечення автоматизованої комп'ютерної інформаційно-керуючої системи військової частини України” (№ ДР 0100U005402); “Дослідження й розробка методів проектування і модернізації засобів мікроелектронної техніки” (№ ДР 012U001772); “Автоматизована система вибору мікроконтролера для систем керування, збору й переробки інформації” (№ ДР 0102U002307); “Інформаційна технологія розробки моделей і методів діагностичної алгоритмізації функціональних задач керування і переробки інформації в бортових приладових комплексах” (№ ДР 0102U005986). Автор є виконавцем зазначених робіт.

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

Задачі, що вирішуються в дисертаційній роботі:

1) проведення аналізу сучасного стану телекомунікаційного сервісу й особливостей переробки інформації в білінгових системах і можливостей її удосконалення на основі сучасних технологій;

2) розробка моделей процесів переробки інформації в білінгових системах;

3) розробка методу перетворення алгоритмічних структур і вибору мінімальних за глибиною та створення на його основі програмно-апаратних засобів автоматизованого аналізу й розробки алгоритмічних структур;

4) розробка методу конструктивного перерахування типових алгоритмічних структур;

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

Об'єкт дослідження - процес переробки інформації в білінгових системах.

Предмет дослідження - моделі та методи формального перетворення алгоритмічних структур.

Методи дослідження. Досягнення мети дисертаційної роботи ґрунтується на комплексному використанні методів і положень теорії графів, булевої алгебри, теорії множин, комбінаторного аналізу, алгоритмічних алгебр, оптимізації. При дослідженні графових алгоритмічних моделей та вирішенні задачі конструктивного перерахування типових варіантів структур використовуються теорія графів, теорія перерахування комбінаторних об'єктів; для перетворення алгоритмічних структур з комутативними умовами використовуються алгоритмічні алгебри, булева алгебра, методи оптимізації.

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

У ході рішення поставлених задач було отримано такі результати:

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

- удосконалено графові алгоритмічні моделі, що дозволяє розширити область їх застосування;

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

Наукові результати отримано автором особисто.

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

У практику підприємств і організацій впроваджено такі результати виконаних досліджень: метод перетворення алгоритмічних структур та програмне забезпечення використані у в/ч А-2374, м. Богодухів, що дозволило автоматизувати процес розробки й верифікації алгоритмічних і програмних засобів, скоротити час їхньої розробки і підвищити вірогідність одержуваних результатів за рахунок виключення суб'єктивних факторів; узагальнені графові алгоритмічні моделі, комбінаторний підхід і метод перетворення алгоритмічних структур, комп'ютерна програма “Програма перетворення алгоритмів” використовувалися при розробці алгоритмів обробки інформації, керування і контролю у відкритому акціонерному товаристві “АТ Науково-дослідний інститут радіотехнічних вимірів”, м. Харків, що дозволило автоматизувати процес розробки алгоритмічного забезпечення, підвищити ефективність програмного забезпечення, вдосконалити процес супроводження програмної документації; метод перетворення алгоритмічних структур і метод перерахування алгоритмічних структур впроваджено в навчальний процес Національного аерокосмічного університету ім. М.Є. Жуковського “Харківський авіаційний інститут”, м. Харків, що дозволило підвищити ефективність навчального процесу за фахом “Інформаційно-вимірювальні системи”; визнані винаходами з видачею патентів України у Державному департаменті інтелектуальної власності, Українському інституті промислової власності аналізатор алгоритмічних перетворювачів і алгоритмічний перетворювач, м. Київ. На програму перетворення алгоритмів і програму генерації варіантів алгоритмічних структур отримані свідоцтва про Державну реєстрацію прав автора у Державному департаменті інтелектуальної власності, м. Київ.

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

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

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

Особистий внесок здобувача. Всі основні наукові положення, висновки і рекомендації дисертаційної роботи отримані особисто автором. У публікаціях, написаних у співавторстві, здобувачеві належать наступні результати: графові алгоритмічні моделі та їх властивості [1], класифікація безповторних алгоритмічних структур [2], види еквівалентності алгоритмічних структур [3], метод конструктивного перерахування типових алгоритмічних структур [4], структура аналізатора алгоритмічних перетворювачів [5], схема алгоритмічного перетворювача [6], процедури перетворення алгоритмів [7], програмно-апаратні засоби для автоматизованих систем обробки інформації [9], алгоритми перетворення алгоритмічних структур [12, 13, 14], алгоритми перетворення діагностичних процедур [15].

Апробація результатів дисертації. Основні результати дисертації доповідалися й обговорювалися на науково-технічних конференціях: Міжнародній науково-технічній конференції “Інтегровані комп'ютерні технології в машинобудуванні ІКТМ-2004” (м. Харків, 2004 р.); 3-й Міжнародній науково-практичній конференції “Динаміка наукових досліджень 2004” (м. Дніпропетровськ, 2004 р.); 1-й Міжнародній науково-практичній конференції “Науковий потенціал світу 2004” (м. Дніпропетровськ, 2004 р.), а також на наукових семінарах кафедри менеджменту Національного аерокосмічного університету ім. М.Є. Жуковського “Харківський авіаційний інститут”.

Публікації. Основні результати дисертації опубліковано в 15 працях, із них 4 статті у збірках наукових праць, 2 патенти України, 2 свідоцтва Державної реєстрації прав автора на твір, 3 у матеріалах конференцій, 4 звіти з науково-дослідної роботи.

Структура й обсяг роботи. Дисертація містить вступ, 4 розділи, висновки і додатки, викладена на 154 сторінках, що містять 45 рисунків на 2 сторінках, 36 таблиць на 4 сторінках, список з 126 використаних літературних джерел на 12 сторінках і 3 додатки на 12 сторінках.

ОСНОВНИЙ ЗМІСТ роботи

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

У першому розділі проведено аналіз сучасного стану телекомунікаційного сервісу та можливостей його вдосконалення на основі сучасних технологій.

Аналіз вітчизняного та закордонного досвіду свідчить про те, що створення корпоративних (відомчих) цифрових мереж інтегрального обслуговування є найбільш ефективним способом комплексного вирішення проблем удосконалення зв'язку в інтересах підвищення ефективності діяльності корпорації. Створення корпоративних мереж обумовлене тим, що існуючі мережі зв'язку загального користування не забезпечують необхідного переліку й якості послуг. Функціонування та розвиток корпорацій залежать від того, як вирішено в корпорації проблему інформаційного забезпечення, необхідного для вирішення задач керування й технологічної підтримки. Актуальними стають проблеми оптимального використання каналів зв'язку й тарифікації всіх наданих провайдерами послуг. У структурі телекомунікаційних компаній білінгові системи займають одне з найважливіших місць.

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

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

Другий розділ присвячено розробці моделей і методу перетворення алгоритмічних структур.

Специфіка задач, які постають перед оператором стільникового зв'язку, визначає функціональні вимоги до систем обслуговування викликів. Виділено особливості обробки інформації в білінгових системах: бізнес у телекомунікаційній галузі формується з складних процесів з розгалуженою логікою; висока складність обробки і великий обсяг транзакцій; пакети послуг можуть містити алгоритми складної логічної тарифікації; високі вимоги до швидкісних характеристик роботи, особливо при “гарячому” білінзі.

Для опису алгоритмічних структур, процесів обробки інформації в білінгових системах пропонується використовувати графи спеціального виду (далі - В-графи).

Визначення 2.1. В-графом називається орієнтований мультиграф без петель з множиною вершин V = {v₁, …, v_n} і множиною ребер Q = {q₁, … , q_2(n1)}, у якому виділено два полюси (початкова вершина v₁ і кінцева вершина v_n), напівстепінь виходу всіх вершин, крім кінцевої, дорівнює двом і для будь-якої вершини v_i (i = 2, …, n-1) існує хоча б один простий ланцюг v₁…v_i…v_n.

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

Дуга, що виходить з вершини v_i і входить у вершину v_j позначається (i, j). Якщо у В-графі є двократні дуги та їх необхідно розрізняти, то вказується верхній індекс, наприклад, (1, 2)¹ чи (1, 2)².

Відстань між вершинами v_i і v_j - величина найкоротшого (i, j) - ланцюга. Якщо ці вершини не з'єднані, то відстань між ними дорівнює .

Ярусом i-ї вершини (позначається d_i) називається відстань між вершинами v₁ і v_i. Зміною ярусу при переході по дузі (i, j) називається величина (i, j), що дорівнює різниці ярусів вершин v_j і v_i, тобто

(i, j) = d_j - d_i.

Позначимо множину всіх простих ланцюгів через С, тоді залежно від зміни ярусу вершин у ланцюзі множину В-графів можна розбити на три групи:

1) з довільною зміною ярусу;

2) з неспадною зміною ярусу, якщо для всіх ланцюгів з множини С ярус не зменшується;

3) зі зростаючою зміною ярусу, якщо для всіх ланцюгів з множини С ярус збільшується.

В-графи зі зростаючою зміною ярусу називаються аранжировними. Аранжировність еквівалентна звідності графа і є однією з найважливіших характеристик В-графів.

Кількість дуг у маршруті називається його довжиною. Оскільки дуги у В-графі можуть бути кратними, то можливі варіанти проходження маршруту. Простий ланцюг, що містить h двократних дуг, має 2^h варіантів проходження. Для опису множини довжин простих ланцюгів у В-графі використовується поліноміальна форма.

На множині В-графів визначено операції добутку, композиції і суми.

Визначення 2.2. Добутком, або послідовним з'єднанням двох В-графів G₁(V¹) та G₂(V²), називається В-граф G₃(V³) = G₁(V¹)*G₂(V²), одержаний шляхом злиття вершин v_1.n1 і v_2.1, тобто V³ = (V¹V²) - v_1.n1.

Властивість 2.1. В-граф, усі прості ланцюги якого містять i-ту вершину може бути представлений як добуток підграфів і називається П-розкладним.

Визначення 2.3. Композицією В-графа G([(I₁, J₁), G₁], …, [(It, Jt), Gt]) називається В-граф, одержаний із графа G заміною відповідних ребер (I_k, J_k) добутком (I_k, J_k)*G_k, k = 1,…,t.

Визначення 2.4. Сумою, або паралельним з'єднанням В-графів G₁ та G₂, називається В-граф G₃, отриманий у результаті композиції:

G₃ = G₀([(1, 2)¹,G₁], [(1, 2)²,G₂]).

Властивість 2.2. В-граф, який можна подати тільки у вигляді суми підграфів називається -розкладним.

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

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

В основі перетворення ланцюгів лежить таке правило:

CdFi v CdF_i = CF_i,

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

Розглянуто способи формування діаграм ланцюгів при виконанні введених операцій над графами.

Метод побудови оптимальних за глибиною алгоритмічних систем, заснований на приведенні алгоритмічної структури до безповторного або слабкоповторного вигляду та складається з таких етапів:

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

Етап 2. Вибирається умовна вершина, що містить найбільшу кількість правильних конфігурацій найбільшої площини (для визначеності позначимо її р).

Етап 3. Проводиться декомпозиція діаграми щодо обраної на другому етапі умовної вершини, тобто розбиття її на дві діаграми: одна відповідає р, а друга р.

Етап 4. Етапи 1-3 виконуються для всіх виділених у процесі декомпозиції діаграм. Зазначений процес закінчується коли отримана на деякому етапі діаграма площею С для умовної вершини Т містить одну правильну конфігурацію площею С/2 і одну правильну конфігурацію площею С/2 для Т .

Метод дозволяє мінімізувати у тому числі й рекурсивні схеми алгоритмів. Для його застосування потрібно у вихідному алгоритмі виділити структуровані фрагменти. Застосування цих перетворень дозволяє скоротити глибину алгоритму в середньому на 7...28 % залежно від виду алгоритму.

Основні результати розділу опубліковано в працях [1, 2, 3].

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

Аналіз методів перерахування показав, що для розглянутого класу об'єктів найефективнішим методом є метод рекурентних співвідношень, який полягає в тому, що розв'язок комбінаторної задачі з n предметами виражається через розв'язок аналогічної задачі з меншою кількістю предметів за допомогою деякого співвідношення, що називається рекурентним. Користуючись цим співвідношенням, шукану величину можна обчислити, виходячи з того, що для невеликої кількості предметів розв'язок задачі знаходиться легко.

Конструктивне перерахування комбінаторних об'єктів полягає у розробці методу оцінки кількості типових структур і (або) їх генерації. Розглянемо розв'язок першої задачі - оцінки кількості типових структур В-графів.

При описі використано такі позначення:

n - кількість активних вершин В-графа, тобто вершина-стік не враховується;

n_i - кількість активних вершин i-го підграфа;

Sn_i,j - j-й тип П-нерозкладного графа з n_i вершинами;

Сn_i,j - j-й тип -розкладного графа з n_i вершинами;

Pn_i,j - j-й тип П-розкладного графа з n_i вершинами;

Z(n) - множина типових варіантів -розкладних графів з n вершинами;

Z(n) - множина типових варіантів П-розкладних графів з n вершинами;

L(n) - потужність множини типових варіантів -розкладних графів з n вершинами;

L(n) - потужність множини типових варіантів П-розкладних графів з n вершинами;

L(n) - кількість типових варіантів структур графів з n вершинами.

Задача оцінки кількості типових варіантів структур зводиться до визначення значень L(n) = L(n) + L(n), а задача генерації типових варіантів полягає в розробці методу побудови множин Z(n) і Z(n). Оскільки існує тільки два види структур В-графів: - і П-розкладні, то необхідно розробити метод оцінки для кожного типу. У загальному випадку, множини типових структур для n вершин формуються на базі типових структур для n - 1, n - 2, ..., 1-ї вершин. Для початкових значень (n = 2, 3) зазначені множини можна отримати в результаті аналізу структур графів і варіантів розкладань аналітично.

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

П-розкладний граф, усі прості ланцюги якого містять i-ту вершину, може бути поданий як добуток відповідних підграфів G₁*G₂*…*G_s з кількістю вершин відповідно n₁, n₂, … , n_s. Граф G та підграфи G₁, G₂, … , G_s є безповторними, тому

n₁ + n₂ + … + n_s = n.

У загальному випадку можливі різні варіанти побудови графа G. Мінімальним будемо називати добуток, при якому підграфи G₁, G₂, … , G_s не є П-розкладними. Очевидно, що в цьому випадку всі підграфи є -розкладними.

Задача оцінки кількості П-розкладних графів з n вершинами полягає у визначенні кількості різних добутків, складених з -розкладних графів із сумарною кількістю вершин n та формулюється таким способом.

Визначити потужність множини Z(n) = {G^t₁,…,G^t_L(n)}, де

Розглянуто основні етапи вирішення даної задачі, отримано оцінку кількості типових варіантів П-розкладних графів:

L(n) = .

При розгляді -розкладних графів слід враховувати такі особливості:

- необхідно розглянути варіанти розбиття n - 1 вершини, тому що одна з вершин графа є джерелом;

- при розбитті кількість доданків k = 2, що обумовлено структурою розкладного графа;

- можливе розбиття виду 0 + (n-1), тобто одного з графів немає;

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

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

Визначити потужність множини

Z(n) = {G^t₁,…, G^t_L(n)},

де

G^t_i = G₀([(1, 2)¹, G₁], [(1, 2)²,G₂]);

n₁ + n₂ = n - 1;

G₁ { Z (n₁), Z(n₁)}, G₂ { Z (n₂), Z(n₂)}.

Розглянуто основні етапи розвязання даної задачі, отримано оцінку кількості типових варіантів -розкладних графів:



де (n) - кількість N-еквівалентних графів.

Розглянуто перерахування структурно-еквівалентних графів, які мають однакові маршрутні характеристики, тому їх перерахування відрізняється від розглянутого вище методу. Це обумовлено тим, що до одного класу еквівалентності відносяться графи, що описуються однаковими характеристичними поліномами. Для П-розкладних графів структурно-еквівалентних графів істотною є множина підграфів, що входять у добуток. Порядок входження в добуток є несуттєвим. Множина -розкладних графів у цьому випадку для n = 1, 2, 3 збігається з аналогічним для розглянутих вище графів.

Поставимо у відповідність i-у мінімальному П-розкладенню графа кортеж Сⁱ = <Gⁱ₁, Gⁱ₂, … , Gⁱ_s >, де Gⁱ_j Z(n-1). Задача перерахування Прозкладних графів з n вершинами полягає у визначенні множини різних кортежів, складених з -розкладних графів із сумарною кількістю вершин, рівною n.

В основі розв'язання цієї задачі лежить також розбиття множини змінних n на k підмножин.

Задача розбиття множини чисел на підмножини формулюється таким чином: скількома способами можна записати задане натуральне число n у виді суми n = b₁ + … +b_k, де k > 1, b₁, … , b_k > 0. При цьому суми вважають еквівалентними, якщо вони відрізняються тільки порядком доданків.

Загальну кількість П-розкладних структурно-еквівалентних графів V_n можна обчислити шляхом послідовного розгляду варіантів розбиття та обчислення кількості різних кортежів для кожного розбиття, що визначається функцією



Размещено на http://www.allbest.ru/

Кількість типових -розкладних структурно-еквівалентних графів Wn визначається аналогічно:

Размещено на http://www.allbest.ru/

де

Размещено на http://www.allbest.ru/

Одержано оцінки кількості типових структур та побудовано каталоги типових представників.

Другий етап розв'язання задачі - конструктивне перерахування типових структур графів - містить розв'язок таких наступних поетапних задач:

1. Формування множини припустимого розбиття кількості вершин на задані підмножини.

2. Формування варіантів побудови графів для кожного варіанту розбиття.

3. Аналіз побудованих варіантів та формування каталога.

Оскільки типові структури для П-розкладних графів будуються на основі тільки -розкладних графів, а -розкладні графи будуються на основі як розкладних так і П-розкладних для меншого числа змінних, то послідовний процес побудови каталогів можна подати у вигляді такої послідовності формованих множин (каталоги для n = 1, 2, 3 сформовано раніше):

Z(4), Z(4), Z(5), Z(5), …, Z(n), Z(n).

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

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

Розроблений метод і побудовані каталоги можна використовувати при розробці типових алгоритмічних структур.

Основні наукові результати розділу опубліковано в працях [4, 8].

У четвертому розділі розглянуто розроблені програмно-апаратні засоби для автоматизації аналізу та розробки алгоритмічних структур.

Розробка алгоритмічних систем дуже трудомістка, особливо при пошуку оптимальних рішень, і потребує великих витрат часу навіть при використанні ЕОМ. Для автоматизації розв'язання логіко-комбінаторних задач, що виникають при розробці й аналізі алгоритмів, було розроблено оригінальні спеціалізовані пристрої: аналізатор алгоритмічних перетворювачів і алгоритмічний перетворювач. Пристрої можуть бути використані як спеціальні математичні співпроцесори для реалізації відповідних макрокоманд. Розроблені пристрої визнано винаходами, видано патенти України.

Розроблений програмний комплекс вирішує такі задачі:

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

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

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

Програми, що входять у програмний комплекс, зареєстровано в Державному департаменті інтелектуальної власності України.

ВИСНОВКИ

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

1. При аналізі тенденцій розвитку телекомунікаційних систем виявлено, що актуальність проблеми проектування корпоративних мереж обумовлена інтенсивним розвитком інформаційних технологій, необхідністю обміну значними масивами інформації, критичністю до швидкості передачі даних та до її надійності. Перспективним напрямком у розвитку телекомунікаційних систем є перехід від стільникових мереж другого покоління до мереж третього покоління (3G-мереж). На сьогоднішній день білінгові системи посідають одне з найважливіших місць у структурі телекомунікаційних компаній, при цьому загальною тенденцією є зменшення розрахункового періоду, що у межі дає системи реального часу. Використання такого білінгу дозволяє не тільки уникнути втрат, але й розширити перелік послуг, що надають компанії.

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

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

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

5. Розроблено метод побудови мінімальних за глибиною алгоритмічних систем, заснований на зведенні алгоритмічної структури до безповторного або слабкоповторного вигляду. Метод дозволяє мінімізувати у тому числі й рекурсивні схеми алгоритмів. Застосування цих перетворень дозволяє скоротити глибину алгоритму в середньому на 7...28 % залежно від вигляду алгоритму.

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

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

8. У практику підприємств і організацій впроваджено такі результати виконаних досліджень:

- метод перетворення алгоритмічних структур і програмне забезпечення впроваджені в в/ч А-2374, м. Богодухів; застосування комплексу програм дозволило автоматизувати процес розробки й верифікації алгоритмічних і програмних засобів, скоротити час їх розробки і підвищити вірогідність одержуваних результатів за рахунок вилучення суб'єктивних факторів;

- узагальнені графові алгоритмічні моделі, комбінаторний підхід і метод перетворення алгоритмічних структур, комп'ютерна програма “Програма перетворення алгоритмів” використовувалися при розробці алгоритмів обробки інформації, керування і контролю у відкритому акціонерному товаристві “АТ Науково-дослідний інститут радіотехнічних вимірів”, що дозволило автоматизувати процес розробки алгоритмічного забезпечення, підвищити ефективність програмного забезпечення, вдосконалити процес супроводження програмної документації;

- метод перетворення алгоритмічних структур і метод перерахування алгоритмічних структур впроваджені в навчальний процес Національного аерокосмічного університету ім. М.Є. Жуковського “Харківський авіаційний інститут”, що дозволило підвищити ефективність навчального процесу за фахом 8.091301 “Інформаційно-вимірювальні системи”;

- програмний комплекс пройшов Державну реєстрацію у Державному департаменті інтелектуальної власності; на програму перетворення алгоритмів і програму генерації варіантів алгоритмічних структур отримано свідоцтва про Державну реєстрацію прав автора на твори;

- аналізатор алгоритмічних перетворювачів та алгоритмічний перетворювач впроваджено в Державному департаменті інтелектуальної власності, Українському інституті промислової власності та визнані винаходами.

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Бугас Д.Н., Чумаченко И.В. Графовые алгоритмические модели // Моделювання та інформаційні технології: Зб. наук. пр. - Київ: НАНУ, 2004. - Вип. 25. - С. 13-16.

2. Бугас Д.Н., Чумаченко И.В. Бесповторные структуры // Моделювання та інформаційні технології: Зб. наук. пр. - Київ: НАНУ, 2004. - Вип. 26. - С. 18-22.

3. Чумаченко И.В., Бугас Д.Н. Эквивалентность алгоритмических структур // Системи обробки інформаціп: Зб. наук. пр. - Харків: НАНУ, ПАНМ, ХВУ, 2004. - Вип. 8 (36). - С. 181-185.

4. Чумаченко И.В., Бугас Д.Н. Перечисление типовых алгоритмических структур // Системи обробки інформаціп: Зб. наук. пр. - Харків: НАНУ, ПАНМ, ХВУ, 2004. - Вип. 9 (37). - С. 201-204.

5. Патент України № 44172, G06F17/00. Аналізатор алгоритмічних перетворювачів / І.В. Чумаченко, Н.В. Доценко, Д.М. Бугас, О.В. Кас'ян, С.Ю. Мелешенко, А.Є. Горобець. - № 2001064097; Заявл. 14.06.2001; Опубл. 15.10.2003, Бюл. № 10. - 4 с.

6. Патент України на корисну модель по заявці № 20040706136, G 06 F 17/00. Алгоритмічний перетворювач / Чумаченко І.В., Бугас Д.М. - № 20040706136; Заявл. 23.07.2004; Висновок про видачу патенту від 16.12.2004р. - 4 с.

7. Комп'ютерна програма “Програма перетворення алгоритмів” / Чумаченко І.В., Бугас Д.М.: Свід. про реєстр. автор. права на твір № 11019.- Зареєстр. в Держ. департ. інтелектуальної власності Мін. освіти і науки України 14.09.2004 р.

8. Комп'ютерна програма “Програма генерації варіантів алгоритмічних структур” / Бугас Д.М.: Свід. про реєстр. автор. права на твір № 11358.- Зареєстр. в Держ. департ. інтелектуальної власності Мін. освіти і науки України 20.10.2004 р.

9. Чумаченко И.В., Кучмиев В.Г., Бугас Д.Н. Алгоритмические и инструментальные средства автоматизированных систем обработки информации // Матеріали ІІІ Міжнар. наук.-практ. конф. “Динаміка наукових досліджень 2004”. - Дніпропетровськ: Наука і освіта, 2004. - Т. 64. - С. 52-53.

10. Бугас Д.Н. Преобразование алгоритмических структур // Міжнар. наук.-техн. конф. “Інтегровані комп'ютерні технології в машинобудуванні ІКТМ - 2004”: Тези доповідей. - Харків: Нац. аерокосм. ун-т “ХАІ”, 2004. - С. 156.

11. Бугас Д.Н. Типовые алгоритмические структуры // Матеріали 1-й Міжнар. наук.-практ. конф. “Науковий потенціал світу 2004”. - Дніпропетровськ: Наука і освіта, 2004. - Т.58. - С.45-46.

12. Автоматизированная система выбора микроконтроллера для систем управления, сбора и переработки информации: Отчлт о НИР (заключит.) / Нац. аерокосміч. ун-т “Харк. авіац. ін-т”. - 303-11/2001; № ДР 0102U002307; Інв. № 0202U000938. - Харків, 2002. - 48 с.

13. Разработка системного обеспечения автоматизированной компьютерной информационно-управляющей системы воинской части Украины: Отчлт о НИР (заключит.) / Нац. аерокосміч. ун-т “Харк. авіац. ін-т”. - 303-11/2001; № ДР 0100U005402; Інв. № 0202U006605. - Харків, 2002. - 79 с.

14. Исследование и разработка методов проектирования и модернизации средств микроэлектронной техники: Отчлт о НИР (заключит.) / Нац. аерокосміч. ун-т “Харк. авіац. ін-т”. - 303-11/2001; № ДР 012U001772; Інв. № 0202U004383. - Харків, 2002. - 65 с.

15. Информационная технология разработки моделей и методов диагностической алгоритмизации функциональных задач управления и переработки информации в бортовых приборных комплексах: Отчлт о НИР (заключит.) / Нац. аерокосміч. ун-т “Харк. авіац. ін-т”.- 602-8/2002;№ ДР 0102U005986; Інв. № 0203U002602. - Харків, 2003. - 93 с.

Размещено на Allbest.ru