Черный ящик

[Rasool]

Эта тема вроде бы относится к Computer Science, а не к Искусственному интеллекту?

[Sicker]

arseniiv в сообщении #1303280 писал(а):

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

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

-- 11.04.2018, 20:53 --

Rasool в сообщении #1303292 писал(а):

Эта тема вроде бы относится к Computer Science, а не к Искусственному интеллекту?

Тут все есть

[arseniiv]

Sicker в сообщении #1303310 писал(а):

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

Какую зацепку, это исследовательская задача. На самом деле я сам о ней пока всерьёз не думал.

[mihaild]

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

[Pphantom]

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

[guryev]

Sicker в сообщении #1303061 писал(а):

Как по отклику на входной сигнал определить устройство черного ящика?

Вообще говоря - никак.
То есть, существуют чёрные ящики, удовлетворяющие условию задачи, устройство которых по отклику определить нельзя.

[Sicker]

guryev в сообщении #1303518 писал(а):

То есть, существуют чёрные ящики, удовлетворяющие условию задачи, устройство которых по отклику определить нельзя.

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

[guryev]

Sicker в сообщении #1303528 писал(а):

я в начале темы привел тот способ

Не привели:

Sicker в сообщении #1303061 писал(а):

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

- термина "функциональные двойники", в условии задачи нет.
Вместо этого стоит задача:

Sicker в сообщении #1303061 писал(а):

по отклику на входной сигнал определить устройство черного ящика

По условию "чёрный ящик" из задачи соответствует определению конечного автомата. Так вот, "определить устройство", то есть, построить автомат, изоморфный описанному в задаче, по отклику, вообще говоря, нельзя.

[mihaild]

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

[guryev]

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

[Sicker]

guryev в сообщении #1303540 писал(а):

термина "функциональные двойники", в условии задачи нет.

Ну не так выразился.

guryev в сообщении #1303549 писал(а):

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

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

[guryev]

Sicker в сообщении #1303550 писал(а):

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

Нет, определение изоморфизма немного другое.

[arseniiv]

Sicker в сообщении #1303550 писал(а):

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

Конечно, нет. Классы эквивалентности по выдаче одинаковых строк при подаче одинаковых строк включают часто более одного автомата. В частности, если автомат выдаёт всегда один и тот же символ, его граф переходов может быть вообще каким угодно.

[Sicker]

arseniiv в сообщении #1303556 писал(а):

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

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

[arseniiv]

Конечный автомат (в данном случае) задаётся тремя множествами $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'$ всё становится проще, конечно). А изоморфизм — это всегда гомоморфизм, имеющий обратный гомоморфизм.

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