Побудова алгоритмів виконання швидких узагальнених кон"юнктивних перетворень дискретних сигналів. Розробка алгоритмів розпізнавання та мінімізації однорідних бульових функцій та побудови узагальнених канонічних поліномів функцій двозначної логіки.
Аннотация к работе
Національна академія наук України АВТОРЕФЕРАТ дисертації на здобуття наукового ступеня кандидата фізико-математичних наукНауковий керівник: кандидат фізико-математичних наук, доцент ТРОФИМЛЮК Олег Тимофійович, Ужгородський національний університет. Офіційні опоненти: доктор фізико-математичних наук, професор ГУПАЛ Анатолій Михайлович, Науково-учбовий центр прикладної інформатики НАН України, директор, кандидат фізико-математичних наук, АКСЬОНОВА Людмила Олександрівна Київський національний технічний український університет "КПІ", старший науковий співробітник. Захист відбудеться 23.11.2001 р. о 14 год. на засіданні спеціалізованої вченої ради при Інституті кібернетики імені В.М.Глушкова НАН України за адресою: 03680, МСП, Київ 187, проспект Академіка Глушкова, 40Дисертаційна робота присвячена розгляду та дослідженню властивостей одного з неортогональних перетворень сигналів з скінченою областю визначення, яке називається узагальненим конюнктивним перетворенням, та розробці на основі цих властивостей методів та алгоритмів цифрової обробки функцій двозначної логіки, які в цьому випадку розглядаються як елементи-вимірного простору сигналів. З математичної точки зору сигнал - це функція, яка приймає значення в деякому полі. Тому сигнали і результати їх перетворень зручно розглядати як елементи деякого функціонального простору - простору сигналів. Знаходження спектрів сигналів скінченовимірного простору сигналів зводиться до знаходження добутку деякої матриці, побудованої на основі бази простору, на сигнал. Одним із прикладів неортогональних перетворень в-вимірному просторі сигналів є представлені в роботах Айзенберга Н.Н., Айзенберга І.Н, Трофимлюка О.Т., конюнктивні перетворення дискретних сигналів, які знайшли своє застосування в розроблених на їх основі алгоритмах розпізнавання монотонності бульових функцій, побудови канонічних поліномів (поліномів Жегалкіна) цих функцій, побудови системи тестів для тестових алгоритмів розпізнавання образів, тощо.Дещо по новому визначено поняття імпліканти та простої імпліканти бульової функції. Матриця може бути представлена у вигляді кронекерівського добутку матриць 2-о порядку. Матричний добуток названо узагальненим конюнктивним перетворенням функції з міткою . Це, в свою чергу, дозволяє розробити алгоритм швидких узагальнених конюнктивних перетворень для знаходження матричного добутку , де --вимірний вектор-стовпець, який задає деяку, необовязково бульову, функцію (дискретний сигнал), визначену на множині . В цьому ж розділі розвязана задача знаходження матриці оператора переходу від базиса простору сигналів (функцій) , який задається множиною стовпців матриці до базиса цього простору, який задається множиною стовпців матриці .Введено в розгляд узагальнені конюнтивні перетворення в-мірному просторі дискретних сигналів над полем дійсних чисел. Однією з основних властивостей цих матриць є можливість їх факторизації, що дозволяє ввести в розгляд швидкі узагальнені конюнктивні перетворення при реалізації яких на ЕОМ можна обійтись як без побудови самої матриці так і набагато зменшити кількість необхідних арифметичних операцій. Дані алгоритми базуються на властивостях узагальнених канонічних перетворень, використання ж при цьому швидких перетворень робить їх зручними при практичній реалізації. На основі розглянутого в роботі відношення часткового порядку , яке породжується заданим бульовим вектором , введено поняття-монотонної бульової функції. Дисертаційна робота присвячена розгляду та дослідженню властивостей одного з неортогональних перетворень сигналів (функцій) з скінченою областю визначення, яке називається узагальненим конюнктивним перетворенням, та розробці на основі цих властивостей методів та ефективних алгоритмів розвязування ряду задач теорії функцій двозначної логіки.