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

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

Доведено, що автомат, ізоморфний за станами та входами лінійному примітивному автомату, буде ізоморфним йому тільки за станами. Знайдено критерій ізоморфності за станами ненадлишкового сигнатурного аналізатора (СА) деякому лінійному СА з нульовим початковим станом.

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

Введено поняття структурованої машини Тьюрінга. Показано, що довільна машина Тьюрінга еквівалентна деякій структурованій машині Тьюрінга. Розглянуто різні уточнення задачі про структурування, зокрема такі, що не дозволяють розширення робочого алфавіту.

Предложен метод проектирования автоматизированных систем контроля (АСК), основанный на алгоритмической алгебре. Эффективность разработанного метода связана с использованием при создании АСК для критических приложений теории рекурсивных автоматов.

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

Вказано на відомі методи інтуїтивного опису алгоритмів, якими є віртуальні машини Т'юрінга, Поста, Колмогорова, Шонгаге, Ахо - Ульмана - Хопкрофта, а також алгоритми Маркова і Крініцкого та рекурсивні функції, засобами яких алгоритми описуються не формалізовано. Дефініцію розширеної алгебри алгоритмів надано за допомогою аксіоматичного методу. Алгебра базується на операціях секвентування, багатозначного елімінування, паралелення та реверсування, а також циклічного секвентування, циклічного елімінування та циклічного паралелення, які виконуються над унітермами. Розширення стосується введення операції багатозначного елімінування. Проілюстровано ефективність розширеної алгебри алгоритмів.

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

Висвітлено історію Інституту проблем математичних машин і систем НАН України, яка багата цілою низкою видатних науково-технічних досягнень всесоюзного та світового рівня в таких галузях як створення ЕОМ і засобів обчислювальної техніки, створення автоматизованих систем керування, створення систем підтримки прийняття рішень, створення спеціалізованих засобів і систем випробування складних об'єктів техніки. Відзначено, що ІПММС має великий досвід співпраці з міжнародними науковими організаціями (провідні установи та навчальні заклади Росії, Швейцарії, Данії, Італії, Франції, Швеції, Литви, Польщі та ін.). Вчені Інституту приділяють значну увагу вихованню молодого покоління, викладаючи у вищих навчальних закладах. Враховуючи одержані за 20 років результати і наявність науково-технічного потенціалу інституту, зроблено висновок про актуальність, перспективність подальших досліджень та розробок в основних напрямах наукової діяльності інституту.

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

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

Рубрики:

Математичні машини

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

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