+
XVII МЕЖДУНАРОДНАЯ КОНФЕРЕНЦИЯ "ПРОБЛЕМЫ ТЕОРЕТИЧЕСКОЙ КИБЕРНЕТИКИ"
стр.5-6
Загружаем данные из библиотечной системы...
+
УНИВЕРСАЛЬНОЕ КВАНТОВОЕ ХЕШИРОВАНИЕ
стр.7-18
Аблаев Фарид Мансурович, Аблаев Марат Фаридович, Васильев Александр Валерьевич
Предложен метод квантового хеширования, комбинирующий известные конструкции универсальных хеш-семейств с квантовыми односторонними функциями. Определено понятие квантового хеш-генератора и предложен подход для построения большого числа различных квантовых хеш-функций. Конструкция основана на объединении классических ε-универсальных хеш-семейств и заданного семейства функций - квантового хеш-генератора. Предложенная конструкция обладает свойствами устойчивого представления информации классическими кодами с исправлением ошибок, а также возможностью высоконадежного представления информации квантовыми системами. В частности, предложена квантовая хеш-функция, основанная на коде Рида - Соломона, и доказано, что данная конструкция является оптимальной в смысле необходимого числа кубитов.
Загружаем данные из библиотечной системы...
Ключевые слова
+
УМНОЖЕНИЯ МАТРИЦ РАЗМЕРОВ 5×2 И 2×2
стр.19-29
Алексеев Валерий Борисович
Статья посвящена изучению билинейной сложности (то есть наименьшего число умножений без учета коммутативности элементов) для задачи умножения матриц малых размеров. Показано, что билинейная сложность для задачи умножения матриц размеров 5×2 и 2×2 не может быть меньше 17 ни над каким полем.
Загружаем данные из библиотечной системы...
Ключевые слова
+
СЛОЖНОСТЬ ВЕТВЯЩИХСЯ ПРОГРАММ ДЛЯ ЧАСТИЧНО ОПРЕДЕЛЕННЫХ ФУНКЦИЙ
стр.30-48
Гайнутдинова Аида Фаритовна
Упорядоченные ветвящиеся диаграммы решений (OBDD - Ordered Binary Decision Diagrams) - известная модель для вычисления булевых функций. В работе рассмотрены частично определенные булевы функции и сложность их вычисления в различных вариантах OBDD (детерминированных, недетерминированных, вероятностных и квантовых). В качестве исследуемой меры сложности взята ширина OBDD. Известно, что при рассмотрении всюду определенных булевых функций вероятностные OBDD могут быть эффективнее детерминированных и данный разрыв в сложности может быть не более чем экспоненциальным. Аналогичный результат верен и при сравнении квантовых OBDD с классическими. Показано, что для частично определенных функций преимущество в сложности квантовых моделей перед классическими может быть усилено. Предложена частично определенная булева функция, которая вычислима с нулевой ошибкой квантовой OBDD ширины 2. При этом ширина классических детерминированной, вероятностной OBDD экспоненциально зависит от параметра функции. Предложено также бесконечное семейство частично определенных булевых функций таких, что любая функция из данного семейства вычислима с ограниченной ошибкой вероятностной OBDD ширины 2. При этом существует бесконечное подмножество функций из данного семейства таких, что ширина классической детерминированной OBDD для вычисления каждой функции из данного подмножества возрастает неограниченно.
Загружаем данные из библиотечной системы...
Ключевые слова
+
О ПОРОЖДАЮЩИХ СИСТЕМАХ В КЛАССАХ МОНОТОННЫХ ФУНКЦИЙ МНОГОЗНАЧНОЙ ЛОГИКИ
стр.49-54
Рассмотрена задача о конечной порожденности предполных классов монотонных функций k-значной логики. Для семейства всех частично упорядоченных множеств с наименьшим и наибольшим элементами таких, что для любых двух элементов x и y существует sup( x, y) или inf( x, y), установлено, что соответствующие классы монотонных функций являются конечно-порожденными.
Загружаем данные из библиотечной системы...
Ключевые слова
+
ЦЕПНЫЕ КОДЫ И SNAKE-IN-THE-BOX PROBLEM
стр.55-65
Евдокимов Александр Андреевич
Статья написана по материалам пленарного доклада “Цепные коды и Snake-in-the-Box Problem: современное состояние, обобщения, приложения”, сделанного на XVII Международной конференции “Проблемы теоретической кибернетики”, Казанский федеральный университет, июнь, 2014 г. В статье мы обсуждаем современное состояние исследований по этой хорошо известной комбинаторной проблеме и её обобщениям. Даётся обзор результатов по нижним и верхним оценкам наибольшей длины цепи (snake) и цикла в n-мерном булевом кубе. Сравниваются известные методы конструирования змей и верхние оценки их максимальной длины. Приводится таблица точных значений наибольших длин для n < 9 и оценки для n = 10, 11 и 12. Описана простая конструкция змеи длины const·2 n со значением const > 0.26. Анализируются свойства конструкций, влияющие на величину константы. Даётся обзор результатов по обобщающим змеи цепным кодам. Приводятся некоторые нерешённые задачи.
Загружаем данные из библиотечной системы...
Ключевые слова
+
КИБЕРНЕТИЧЕСКАЯ МОДЕЛЬ ЦИКЛИЧЕСКОГО УПРАВЛЕНИЯ КОНФЛИКТНЫМИ ПОТОКАМИ С ПОСЛЕДЕЙСТВИЕМ
стр.66-75
Зорин Андрей Владимирович
Для построения математической модели процесса обслуживания конфликтных потоков в классе циклических алгоритмов с переналадками применен подход Ляпунова - Яблонского. Для задания входных потоков с зависимыми интервалами между поступлением требований использовано нелокальное описание. Выделены и нелокально описаны блоки-схемы, информация, координаты и функция системы. Конструктивно задана многомерная цепь Маркова с несчетным измеримым пространством состояний, описывающая изменение состояния обслуживающего устройства, флуктуации длин очередей и состояние входных потоков. Установлены некоторые свойства полученного стохастического переходного ядра.
Загружаем данные из библиотечной системы...
Ключевые слова
+
НЕКОТОРЫЕ ОСОБЕННОСТИ ЗАДАЧИ СИНТЕЗА БУЛЕВЫХ ФОРМУЛ В ПОЛНЫХ БАЗИСАХ С ПРЯМЫМИ И ИТЕРАТИВНЫМИ ПЕРЕМЕННЫМИ
стр.76-83
Коноводов Владимир Александрович
В работе рассмотрены вопросы сложности формул в различных базисах, состоящих из функций алгебры логики с прямыми и итеративными переменными. Показано, что “стандартное” поведение функции Шеннона для сложности формул (2 n /log n) не всегда имеет место, приведены примеры нетривиальных семейств базисов с порядком роста этой функции, равным 2 n . Такие примеры существуют среди каждого из семейств в классификации полных базисов по их итеративным замыканиям, кроме двух, в которых функция Шеннона ведет себя стандартно. Для оператора итеративного замыкания δ, введенного в работе [Ложкин С.А. О полноте и замкнутых классах функций алгебры логики с прямыми и итеративными переменными // Вестн. Моск. ун-та. Сер. 15. Вычисл. матем. и кибернетика. - 1999. - № 3. - С. 35-41], получено новое представление. Отдельно рассмотрен вопрос о сложности линейной функции в некоторых классах базисов и приведены примеры кардинального изменения этой сложности в различных базисах одного семейства.
Загружаем данные из библиотечной системы...
Ключевые слова
+
О ДИНАМИЧЕСКОЙ АКТИВНОСТИ СХЕМ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ И ПОСТРОЕНИИ АСИМПТОТИЧЕСКИ ОПТИМАЛЬНЫХ ПО СЛОЖНОСТИ СХЕМ С ЛИНЕЙНОЙ ДИНАМИЧЕСКОЙ АКТИВНОСТЬЮ
стр.84-97
Ложкин Сергей Андреевич, Шуплецов Михаил Сергеевич
Для схем из функциональных элементов введено понятие их динамической активности, которая дополняет исследованную ранее статическую активность, или мощность, и моделирует энергопотребление интегральных схем, связанное с возникающими в них переходными процессами. Для динамической активности функций алгебры логики от n переменных при их реализации схемами из функциональных элементов получена линейная по n верхняя оценка функции Шеннона в произвольном конечном полном базисе. Кроме того, предложены методы синтеза, позволяющие строить для указанных функций такие схемы из функциональных элементов в стандартном базисе {&,˅,¬}, сложность которых асимптотически не больше чем 2 n / n, а динамическая и статическая активности имеют линейный относительно n порядок роста, причём их статическая активность удовлетворяет новым более точным оценкам.
Загружаем данные из библиотечной системы...
Ключевые слова
+
О КЛАССАХ ФУНКЦИЙ k-ЗНАЧНОЙ ЛОГИКИ, ПРИНИМАЮЩИХ НЕ БОЛЕЕ ТРЕХ ЗНАЧЕНИЙ
стр.98-109
Подолько Дмитрий Константинович
В работе для функций k-значной логики при k = 2 m , m ≥ 2, рассмотрен оператор β-замыкания, который определен на основе кодирования данных функций в двоичной системе счисления. Построено отображение семейства всех β-замкнутых классов в семейство замкнутых классов булевых функций и для каждого класса ß булевых функций исследована мощность множества β-замкнутых классов, которые отображаются в класс ß и содержат только функции, принимающие не более трех значений.
Загружаем данные из библиотечной системы...
Ключевые слова
+
О СИНТЕЗЕ КОНТАКТНЫХ СХЕМ, ДОПУСКАЮЩИХ КОРОТКИЕ ПРОВЕРЯЮЩИЕ ТЕСТЫ
стр.110-115
Романов Дмитрий Сергеевич
В статье установлено, что для произвольной отличной от константы булевой функции f( x 1,…, x n ) существуют допускающие единичный проверяющий тест линейной по n длины тестопригодные а) трехполюсная контактная схема (с одним входным и двумя выходными полюсами), реализующая систему функций ( f, f̅), б) двухполюсная контактная схема, реализующая функцию f( x 1,…, f n ) + x n +1. Доказано также, что почти все булевы функции f( x 1,…, x n ) реализуемы двухполюсными контактными схемами, обладающими коротким проверяющим тестом (тестом длины O( n)) относительно однотипных неисправностей контактов.
Загружаем данные из библиотечной системы...
Ключевые слова
+
О РЕАЛИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ ОБОБЩЕННЫМИ α-ФОРМУЛАМИ
стр.116-122
Сысоева Любовь Николаевна
Рассмотрена задача о реализации булевых функций обобщенными α-формулами. Введено понятие обобщенной α-формулы. Определено понятие универсального множества обобщенных α-формул для заданного множества булевых функций. Введено понятие двойственных обобщенных α-формул, сформулирован принцип двойственности. Показано, что для каждого n ≥ 2 для множеств T 0( n) и T 1( n) всех булевых функций от переменных x 1, x 2,…, x n , сохраняющих константы 0 и 1 соответственно, существуют универсальные множества.
Загружаем данные из библиотечной системы...
Ключевые слова
+
НЕКОТОРЫЕ УСЛОВИЯ РАВНОМЕРНОСТИ МОНОТОННЫХ ФУНКЦИЙ k-ЗНАЧНОЙ ЛОГИКИ, ПРИНИМАЮЩИХ ЗНАЧЕНИЯ 0 И 1
стр.123-131
Рассмотрено соотношение между глубиной и сложностью реализации функций многозначной логики формулами над конечными базисами. Система функций A называется квазиравномерной, если существуют такие константы c и d, что для любой функции f из замкнутого класса, порожденного данной системой, выполнено неравенство D A ( f) ≤ c log 2 2 L A ( f) + d, где D A ( f) и L A ( f) - соответственно глубина и сложность реализации функции f формулами над A. Представлены нетривиальные условия квазиравномерности конечных систем функций k-значной логики, принимающих значения 0 и 1 и монотонных относительно частичного порядка на множестве {0,…, k-1}, в котором 1 > 0, а остальные элементы несравнимы.
Загружаем данные из библиотечной системы...
Ключевые слова
+
О ЛИНЕЙНЫХ ОПЕРАТОРАХ, ИНЪЕКТИВНЫХ НА ПРОИЗВОЛЬНЫХ ПОДМНОЖЕСТВАХ
стр.132-141
Чашкин Александр Викторович
Рассмотрены линейные операторы, инъективные на подмножествах линейного пространства над GF( p). Показано, что при любой положительной постоянной ε, начиная с некоторого n, для каждой области D из GF n (p) существует инъективный на этой области линейный оператор, ранг которого не превосходит (2 + ε) log p | D| и сложность которого есть O( n).
Загружаем данные из библиотечной системы...
Ключевые слова
+
СПОСОБЫ ВЫБОРА ПРАВИЛ ПРИ ОБРАТНОМ ВЫВОДЕ В СТАТИЧЕСКИХ ЭКСПЕРТНЫХ СИСТЕМАХ
стр.142-151
Юрин Арнольд Менделевич, Денисов Максим Павлович
В статье рассмотрена задача оптимизации процесса поиска решений статической экспертной системы. Для ее решения было проведено исследование этапа обратного вывода по выбору правила для исполнения. Приведен метод сбора статистики для анализа данного этапа. Представлены результаты сбора статистики в виде сравнительного анализа 4 способов выбора правил для баз знаний в 3 категориях решаемых задач. Выявлены наиболее эффективные способы в этих категориях. На их основе предложены вариант комбинированного способа и алгоритм обратного вывода, минимизирующий число правил, которые используются при решении рассмотренных категорий задач.
Загружаем данные из библиотечной системы...
Ключевые слова
