Поведение коллектива автоматов со связью на целочисленном луче - дипломная работа | ИСТИНА – Интеллектуальная Система Тематического Исследования НАукометрических данных

Научный руководитель: Волков Н.Ю.
Автор: Пулатов Элдор Шовкат угли
Тип: Бакалавр
Организация, в которой проходила защита: МГУ имени М.В. Ломоносова, Филиал МГУ в г. Ташкенте
Год защиты: 2021
Аннотация: В работе вводится понятие «коллектива автоматов со связью». Это система автоматов в лабиринте, которые способны в любой момент времени знать состояния и входные символы друг друга. Коллектив автоматов со связью является более сложным вычислителем, чем коллектив автоматов и более простым вычислителем, чем лабиринтный монстр, введённых Г. Килибардой. Фактически, коллектив автоматов со связью – это простой лабиринтный монстр без красок, без рёберных и вершинных камней. Исследуется движение такой системы на целочисленном луче и на целочисленной прямой. Вводится понятие вычислимости функций f: N0n -> N0 по аналогии с вычислимостью функций коллективами автоматов. Ставится задача исследовать классы функций, вычислимых коллективами автоматов со связью в зависимости от числа автоматов в них. Также вводится понятия быстрой вычислимости функций (это вычислимость за время t=const*f(x1,…,xn)+o(f(x1,…,xn)) сверхбыстрой вычислимости функций (это вычислимость за время t= f(x1,…,xn)+o(f(x1,…,xn)). Автору удалось найти способы вычисления некоторых элементарных функций коллективами автоматов со связью, более быстрые и более экономные по числу автоматов, чем способы вычисления этих же функций, доступные для обычных коллективов автоматов. В частности, показано, что f(x1,…,xn) =x1+…+xn ∈ G"n – это класс функций сверхбыстро вычислимых на луче коллективами из n автоматов со связью. Также показано, что f(x1,x2) =x1*x2 ∈ G"4, а f(x1,…,xn)=x1*…*xn ∈ G’n – это класс функций быстро вычислимых на луче коллективами из n автоматов со связью. Доказано, что класс функций, вычислимых на прямой коллективом из n автоматов со связью, совпадает с классом функций, вычислимых на луче коллективом из (n-1) автомата со связью. Указано, как в одной из этих вычислительных моделей моделировать вычисления, производимые в другой.
Добавил в систему: Волков Николай Юрьевич

	ИСТИНА	Войти в систему Регистрация
	ИСТИНА ЦЭМИ РАН
	Главная Поиск Статистика О проекте Помощь

ИСТИНА

ИСТИНА ЦЭМИ РАН

Поведение коллектива автоматов со связью на целочисленном лучедипломная работа (Бакалавр)

Прикрепленные файлы