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

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

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

Розвинуто підхід Штрассена до швидкого множення великих чисел для використання під час його реалізації алгоритму ІІПТУ для обчислення дискретної циклічної згортки. Наведено апріорні оцінки складності побудованого алгоритму, результати порівняльного аналізу з алгоритмами Карацуби - Оффмана, Шенхаге - Штрассена та стандартним алгоритмом, а також галузі його ефективного використання.

Індекс рубрикатора НБУВ: В127.4

Рубрики:

Теорія обчислюваності. Складність обчислень

Шифр НБУВ: Ж29114 Пошук видання у каталогах НБУВ 

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

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

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

Досліджено задачі комбінаторної теорії ігор і екстремальної комбінаторики. Значну увагу приділено питанням конструктивності та застосування у теорії складності обчислень і теорії дескриптивної складності. Розв'язано екстремальні задачі Рамсеївського типу для симетричних підмножин Евклідового простору, у цьому випадку значення екстремальних функцій досягаються ефективними детермінованими або ймовірнісними конструкціями. Для класу сильних ігор щодо уникнення забороненого підграфа введено та вивчено поняття симетричної стратегії. Введено поняття логічної глибини графа й одержано оцінки цього інваріанту на підставі всебічного вивчення гри Еренфойхта на графах. Ці оцінки застосовано для аналізу алгоритму Вайсфайлера - Лемана розпізнання ізоморфних графів. Шляхом ігрової інтерпретації та зведенням до екстремальних задач одержано результати про паралельне повторення інтерактивних доведень. Розроблено доведення без розголошення для теоретико-групових задач про перестановки. З'ясовано обчислювальну важкість форсингового хроматичного числа графа. Проведено оракульне конструювання, що дає змогу розв'язати питання Крайчика та Пудлака про існування оптимальних алгоритмів для coNP-задач.

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

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

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

Індекс рубрикатора НБУВ: В127.4

Рубрики:

Теорія обчислюваності. Складність обчислень

Шифр НБУВ: Ж29144 Пошук видання у каталогах НБУВ 

Розглянуто проблему відшукання гамільтонових циклів на числових графах. Розглянуто алгоритм з поверненням, алгоритм Approx-TSP(G) та алгоритм із поліноміальним часом. Проаналізовано часову складність даних алгоритмів.

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

Індекс рубрикатора НБУВ: В127.4 + В152.12

Рубрики:

Теорія обчислюваності. Складність обчислень

Незвідність багаточленів. Розкладання на множини

Шифр НБУВ: Ж14163 Пошук видання у каталогах НБУВ 

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

Розглянуто гіпотезу Блера (Blair) про обчислювальну складність задачі, пов'язаної з оптимальними розв'язками так званих близьких задач про рюкзак. Гіпотезу доведено для узагальнено близьких задач про рюкзак.

Запропоновано об'єднаний клітинний метод множення матриць, який являє собою гібрид трьох методів: рекурсивних методів Штрассена, Лейдермана та швидкого клітинного методу множення матриць. Взаємодія трьох методів забезпечує найвищий порівняно з відомими методами відсоток мінімізації (37 %) мультиплікативної, адитивної та загальної складності клітинних аналогів відомих алгоритмів множення матриць. Оцінку обчислювальної складності об'єднаного методу наведено на прикладі одержання клітинного аналога традиційного алгоритму множення матриць.

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

Получены критерии сильной допустимости и сильной разрешимости нечеткой линейной системы неравенств в пяти смыслах: четком, квазичетком, полунечетком, квазинечетком, нечетком.