2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4  След.
 
 Re: Черный ящик
Сообщение11.04.2018, 20:03 


20/09/09
1879
Уфа
Эта тема вроде бы относится к Computer Science, а не к Искусственному интеллекту?

 Профиль  
                  
 
 Re: Черный ящик
Сообщение11.04.2018, 20:53 
Аватара пользователя


13/08/13

4323
arseniiv в сообщении #1303280 писал(а):
А вот сможете ли вы найти для произвольных $n,i,o$ количество классов эквивалентности автоматов с $n$ состояниями (одно из которых маркировано — стартовое), $i$ входными символами и $o$ выходными?

Я тоже над этим думал, какую-нибудь зацепку?

-- 11.04.2018, 20:53 --

Rasool в сообщении #1303292 писал(а):
Эта тема вроде бы относится к Computer Science, а не к Искусственному интеллекту?

Тут все есть :-)

 Профиль  
                  
 
 Re: Черный ящик
Сообщение11.04.2018, 22:22 
Заслуженный участник


27/04/09
28128
Sicker в сообщении #1303310 писал(а):
Я тоже над этим думал, какую-нибудь зацепку?
Какую зацепку, это исследовательская задача. На самом деле я сам о ней пока всерьёз не думал.

 Профиль  
                  
 
 Re: Черный ящик
Сообщение11.04.2018, 22:33 
Заслуженный участник
Аватара пользователя


16/07/14
8348
Цюрих
Для $i = 1$ получается задача об ожерельях. Для большего - непонятно (там даже просто посчитать число сильно связных графов не так просто).

 Профиль  
                  
 
 Posted automatically
Сообщение12.04.2018, 00:20 
Заслуженный участник


09/05/12
25179
 i  Тема перемещена из форума «Искусственный интеллект и Машинное обучение» в форум «Computer Science»
Причина переноса: AI и ML, если тут и подразумевались, как-то испарились в процессе.

 Профиль  
                  
 
 Re: Черный ящик
Сообщение12.04.2018, 17:06 


27/02/09
253
Sicker в сообщении #1303061 писал(а):
Как по отклику на входной сигнал определить устройство черного ящика?
Вообще говоря - никак.
То есть, существуют чёрные ящики, удовлетворяющие условию задачи, устройство которых по отклику определить нельзя.

 Профиль  
                  
 
 Re: Черный ящик
Сообщение12.04.2018, 17:58 
Аватара пользователя


13/08/13

4323
guryev в сообщении #1303518 писал(а):
То есть, существуют чёрные ящики, удовлетворяющие условию задачи, устройство которых по отклику определить нельзя.

Докажите, т.к. я в начале темы привел тот способ.

 Профиль  
                  
 
 Re: Черный ящик
Сообщение12.04.2018, 18:50 


27/02/09
253
Sicker в сообщении #1303528 писал(а):
я в начале темы привел тот способ
Не привели:
Sicker в сообщении #1303061 писал(а):
те из них, которые дают такой же выход, что и наш исходный ящик, и будут его функциональными двойниками
- термина "функциональные двойники", в условии задачи нет.
Вместо этого стоит задача:
Sicker в сообщении #1303061 писал(а):
по отклику на входной сигнал определить устройство черного ящика
По условию "чёрный ящик" из задачи соответствует определению конечного автомата. Так вот, "определить устройство", то есть, построить автомат, изоморфный описанному в задаче, по отклику, вообще говоря, нельзя.

 Профиль  
                  
 
 Re: Черный ящик
Сообщение12.04.2018, 18:58 
Заслуженный участник
Аватара пользователя


16/07/14
8348
Цюрих
Если не требовать восстановить начальное состояние, то можно: пар (автомат, начальное состояние) конечно; если автоматы в двух таких парах неизоморфны, то, зная какое слово мы уже подали, можно подобрать слово, отличающее эти пары. В итоге у нас останутся только пары с изоморфными состояниями.
Начальное состояние восстановить нельзя: например если автомат по нулю всегда переходит в $0$ и выдает $0$, и мы первым делом подали на вход $0$, то мы уже не узнаем, в каком состоянии он был.

 Профиль  
                  
 
 Re: Черный ящик
Сообщение12.04.2018, 19:04 


27/02/09
253
Существуют неизоморфные автоматы, отклики которых всегда совпадают.

 Профиль  
                  
 
 Re: Черный ящик
Сообщение12.04.2018, 19:17 
Аватара пользователя


13/08/13

4323
guryev в сообщении #1303540 писал(а):
термина "функциональные двойники", в условии задачи нет.

Ну не так выразился.
guryev в сообщении #1303549 писал(а):
Существуют неизоморфные автоматы, отклики которых всегда совпадают.

Если отклики совпадают, то они изоморфны по определению.

 Профиль  
                  
 
 Re: Черный ящик
Сообщение12.04.2018, 19:36 


27/02/09
253
Sicker в сообщении #1303550 писал(а):
Если отклики совпадают, то они изоморфны по определению.
Нет, определение изоморфизма немного другое. :-)

 Профиль  
                  
 
 Re: Черный ящик
Сообщение12.04.2018, 20:20 
Заслуженный участник


27/04/09
28128
Sicker в сообщении #1303550 писал(а):
Если отклики совпадают, то они изоморфны по определению.
Конечно, нет. Классы эквивалентности по выдаче одинаковых строк при подаче одинаковых строк включают часто более одного автомата. В частности, если автомат выдаёт всегда один и тот же символ, его граф переходов может быть вообще каким угодно.

 Профиль  
                  
 
 Re: Черный ящик
Сообщение12.04.2018, 20:29 
Аватара пользователя


13/08/13

4323
arseniiv в сообщении #1303556 писал(а):
В частности, если автомат выдаёт всегда один и тот же символ, его граф переходов может быть вообще каким угодно.

Да ну,а какое тогда определение изоморфизма?

 Профиль  
                  
 
 Re: Черный ящик
Сообщение12.04.2018, 22:24 
Заслуженный участник


27/04/09
28128
Конечный автомат (в данном случае) задаётся тремя множествами $S,I,O$, начальным состоянием $s_0\in S$ и функцией переходов $m\colon S\times I\to S\times O$. Отсюда должно быть практически очевидно (потому что $(S,I,O,s,m)$ — это алгебраическая система, даром что немножечко обобщённая), что гомоморфизм — это тройка функций $f_X\colon X\to X'$ таких, что $f_S(s_0) = s'_0$ и $m(s_1,i) = (s_2,o)\Rightarrow m'(f_S(s_1),f_I(i)) = (f_S(s_2),f_O(o))$ (в интересном случае $I=I', O=O'$ всё становится проще, конечно). А изоморфизм — это всегда гомоморфизм, имеющий обратный гомоморфизм.

Вот я щас удивлюсь, если моё автоматически выведенное определение не совпадёт с используемым в литературе по КА.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 47 ]  На страницу Пред.  1, 2, 3, 4  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group