2014 dxdy logo

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

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




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


11/12/05
7669
Diкий Запад
Sicker в сообщении #1303080 писал(а):
тут не исключающее либо.
Разумеется, и уже это учтено выше.

Sicker в сообщении #1303080 писал(а):
А этот автомат можно разделить на два подтипа, который переключается при подаче на вход единицы или нет, итого у нас три типа)
ну и дальше 3*3, а не 2*2)
Присоединяюсь к призыву: учите матчасть.

-- Вт апр 10, 2018 21:09:19 --

Sicker в сообщении #1303082 писал(а):
Че за бред вы несете?. Вот все возможности (0 1) - (0 1), (0 1) - (1 0), (0 1) - (1 1) для одного состояния, вы согласны?
Бред сейчас несёте именно вы.

-- Вт апр 10, 2018 21:13:00 --

Sicker в сообщении #1303080 писал(а):
Хорошо, если я исключу требование переключаемости, тогда вы согласны что было бы 4*4 вариантов?
Даже с этим требованием число различных вариантов, как я написал сразу, равно 16, то есть 4*4. А без него вариантов будет поболее.

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


13/08/13
24/02/19
3448
Dan B-Yallay в сообщении #1303083 писал(а):
Присоединяюсь к призыву: учите матчасть.

ссылку в студию.
Dan B-Yallay в сообщении #1303083 писал(а):
Бред сейчас несёте именно вы.

(0 1) - (0 1) для состояния P означает, что при подаче 0 оно остается P, а при подаче 1 меняет его на Q, и так далее, что не понятного?

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


11/12/05
7669
Diкий Запад
Sicker в сообщении #1303084 писал(а):
ссылку в студию.
Читайте сообщение от Pavia на предидущей стр.

Sicker в сообщении #1303084 писал(а):
(0 1) - (0 1) для состояния P означает, что при подаче 0 оно остается P, а при подаче 1 меняет его на Q, и так далее, что не понятного?
Либо вы пользyетесь моими обозначениями и тогда понимаете что они означают, либо вводите собственные, но тогда обьясняете что они означают. Иначе разговора не получается и BCE непонятно.

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


13/08/13
24/02/19
3448
Dan B-Yallay в сообщении #1303085 писал(а):
Либо вы пользyетесь моими обозначениями и тогда понимаете что они означают, либо вводите собственные, но тогда обьясняете что они означают. Иначе разговора не получается и BCE непонятно.

Так объясните их.
Вот мои ((0 1) 0) - (0 1), ((0 1) 1) - (1 1)
Это один из автоматов, они означают, что если автомат находится в состоянии 0, то при подаче 0 он остается в 0, а при подаче 1 переходит в 1, а если находится в состоянии 1, то при подаче 0 или 1 переходит в 0 - состояние.
И таких 9 штук.

-- 11.04.2018, 06:30 --

третья цифра - номер состояния, первые две - возможные входы, последние две, первая из них реализуется при входе 0, вторая при входе 1.

-- 11.04.2018, 06:30 --

Да, первые две можно не писать :mrgreen:
(0) - (0 1), (1) - (1 1)

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


11/12/05
7669
Diкий Запад
Sicker в сообщении #1303086 писал(а):
Это один из автоматов, они означают, что если автомат находится в состоянии 0
Нет у вас такого состояния как 0. Нету:
Sicker в сообщении #1303061 писал(а):
Пусть черный ящик представляет собой машину Тьюринга, он имеет два внутренних состояния, 1 и 2,

Я еще несколько постов назад предложил избавиться от неудобного и путающего обозначения. Даже предложил свои.
Тут, похоже дело безнадёжное. Спасибо за беседу.

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


13/08/13
24/02/19
3448
Dan B-Yallay в сообщении #1303087 писал(а):
Я еще несколько постов назад предложил избавиться от неудобного и путающего обозначения. Даже предложил свои.

Sicker в сообщении #1303086 писал(а):
Так объясните их.

Dan B-Yallay в сообщении #1303087 писал(а):
Пусть черный ящик представляет собой машину Тьюринга, он имеет два внутренних состояния, 1 и 2,

Замените их на 0 и 1 тогда :mrgreen:

-- 11.04.2018, 06:55 --

Dan B-Yallay в сообщении #1303087 писал(а):
Тут, похоже дело безнадёжное.

Мне сейчас дико смешно от того, что кто-то из нас не может разобраться с такой фигней :-)
Вы кстати, так и не ответили на мой вопрос в начале темы)

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


11/12/05
7669
Diкий Запад
Sicker в сообщении #1303090 писал(а):
Замените их на 0 и 1 тогда
Хорошо, имеем автомат с двумя возможными состояниями 0,1 а также двумя различными входными данными также обозначенными 0 и 1. Tогда конструируем следующую таблицу:

$$
\begin{bmatrix}
\text{Нач. сост } & \text{Вход } & \text{Выход } & \text{Посл Сост}\\
0 & 0 & x_{00} & y_{00}\\
0 & 1 & x_{01} & y_{01}\\
1 & 0 & x_{10} & y_{10}\\
1 & 1 & x_{11} & y_{11}\\
\end{bmatrix}
$$

Произвольно задав значения 0 или 1 для всех выходных значений $x_{ij}$ и состояний $y_{ij}$ получим некоторую "машину Тьюринга". Очевидно, что таких вариантов $2^8=256$.
Это при условии, что снято требование об обязательном переходе между состояниями.

-- Вт апр 10, 2018 22:24:27 --

Sicker в сообщении #1303090 писал(а):
Вы кстати, так и не ответили на мой вопрос в начале темы)
Я не занимаюсь теоретическим программированием или реверс-инжинирингом поэтому не знаю ответа на вопрос о том, какие есть алгоритмы анализа подобных чёрных ящиков. Ждите других, более знающих участников.

-- Вт апр 10, 2018 23:09:39 --

Насчёт изначального требования перехода из одного состояния в другое:
Dan B-Yallay в сообщении #1303064 писал(а):
Их 16.
Sicker в сообщении #1303080 писал(а):
А этот автомат можно разделить на два подтипа, который переключается при подаче на вход единицы или нет, итого у нас три типа)
В этом вы правы, получается больше чем 16. А именно $9*16=144$, если опять не вру. Похоже, мне тоже пора идти читать матчасть.

Всё, ухожу из темы.

 Профиль  
                  
 
 Re: Черный ящик
Сообщение11.04.2018, 09:14 


12/08/14

401
Sicker в сообщении #1303061 писал(а):
Пусть черный ящик представляет собой машину Тьюринга, он имеет два внутренних состояния, 1 и 2, которые определяют по входящему сигналу (0 или 1) что будет на выходе (0 или 1), и в какое состояние перейдет черный ящик. Пусть из любого состояния есть переход в другое.


****которые определяют по входящему сигналу (0 или 1)

входящий датчик один, по которому может быть получен сигнал 0 или 1
вход$=(0,1)$

***он имеет два внутренних состояния, $1$ и $2$,

состояние начальное$=(0,1)$

****будет на выходе (0 или 1)

выходящий датчик один, например экран, на котором может быть $0 $ или $1$
выход$=(0,1)$

****в какое состояние перейдет черный ящик

состояние конечное$=(0,1)$

<вход> <состояние_1> <выход> <состояние_2>
(0,1) x (0,1) x (0,1) x (0,1)

<вход> <состояние_1> <выход> <состояние_2>
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1

0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1

1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1

1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1

16 вариантов

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


31/10/08
982
Sicker
Извиняюсь не успел с утра написать ответ. И он получился довольно грубым. Но теория автоматов хорошо описана и формулы приведены. Если не в первом, то во-втором учебнике.

Для примера возьмем Трахтенброт Б. А., Барздинь Я. М.-Конечные автоматы (поведение и синтез)-Наука (1970)
на стр 17 в самом конце.

Цитата:
тогда матрица переходов может быть заполнена $k^{mk}$ способами, а матрица выходов $n^{mh}$ способами. Следовательно, общее число автоматов с заданными алфавитами, насчитывающими соответственно $k, m, n$ символов, в точности равно
$(kn)^{mk}$.


Определение автомата :

Конечным автоматом называется система $S = \{ Q,X, Y,\Psi,\Phi\}$, где
$X=\{x_1 ,...x_m \}$ - входной алфавит, $Q=\{q_1 ,...q_k \}$ -состояния автомата,
$Y=\{y_1 ,...y_n \}$- выходной алфавит, $\Psi$ - функция переходов, $\Phi$ -функция выходов.
Поскольку функции $\Psi$ и $\Phi$ определены на конечных множествах,
то их можно задавать таблицами, обычно две таблицы обьединяют в
одну $\Psi \times  \Phi :Q\times X \rightarrow Q \times Y$, называемой таблицей переходов автомата. (рис 1.1).


\begin{tabular}{|l|r|r|}
\hline
 &  x1 & x2  \\
\hline
q1 & q_*, y_* & q_*, y_* \\
\hline
q2 & q_*, y_* & q_*, y_* \\
\hline
\end{tabular}


Цитата:
тогда матрица переходов может быть заполнена $k^{mk}$ способами, а матрица выходов $n^{mh}$ способами. Следовательно, общее число автоматов с заданными алфавитами, насчитывающими соответственно $k, m, n$ символов, в точности равно
$(kn)^{mk}$.


Признаю что в предыдущем посте ошибся. Подставляем условия в формулу получаем (2*2)^(2*2)=256

Никаких троек.* - тут можно подискутировать но это лучше вынести в отдельная тему.

Что касается основного вопроса следует изучить цепи Маркова. Только на практике их почти не применяют. Предпочитают использовать нейронные сети которые с некоторой погрешностью аппроксимируют неизвестную функцию.

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


12/08/14

401
Pavia сорри, кажется вы неправильно поняли начальные путанные условия задачи, посмотрите плиз мой пост, где я ошибся, если не трудно

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


31/10/08
982
Sicker
Sicker в сообщении #1303080 писал(а):
А этот автомат можно разделить на два подтипа, который переключается при подаче на вход единицы или нет, итого у нас три типа) ну и дальше 3*3, а не 2*2)

Без переключение это переход состояния в себя такие автоматы эквиваленты поэтому 3 не возникает.
$q1\rightarrow q1$
$q2\rightarrow q2$
А вот если автомат не выдаёт данные в некотором состояние. То тогда в выходной алфавит можно добавить $\varepsilon$

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


27/04/09
24101
Уфа
Sicker в сообщении #1303061 писал(а):
Пусть черный ящик представляет собой машину Тьюринга, он имеет два внутренних состояния, 1 и 2, которые определяют по входящему сигналу (0 или 1) что будет на выходе (0 или 1), и в какое состояние перейдет черный ящик.
Это не машина Тьюринга, это конечный автомат (ой, уже написали). Боже, когда вы уже познаете пользу аккуратности и предварительных приготовлений…

Sicker в сообщении #1303061 писал(а):
Пусть из любого состояния есть переход в другое. Как по отклику на входной сигнал определить устройство черного ящика? Или точнее, его функцию отклика (ведь есть состояния, которые функционально изоморфны).
Например, для байесовских сетей и подобных моделей есть алгоритмы вывода состояния неизвестных переменных. В самом плохом случае здесь могло бы подойти аналогичное.

Кроме того, можно моделировать сразу все возможные автоматы, отсекая несоответствующие парам (вход, выход) данного, генерируя входные символы в случае неоднозначности случайно. Когда в пуле останется мало автоматов, всё чаще будут встречаться ситуации, когда поведение всех автоматов по одному из входных символов уже известно, и потому можно будет выбрать детерминированно другой. Это не обязательно оптимальный алгоритм, но лёгкий в реализации и для вашего количества (255) должен быстро давать ответ, особенно если подбирать вероятность выбора очередного входного символа при неоднозначности аккуратно (а не просто 0,5).

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


13/08/13
24/02/19
3448
Dan B-Yallay в сообщении #1303091 писал(а):
Произвольно задав значения 0 или 1 для всех выходных значений $x_{ij}$ и состояний $y_{ij}$ получим некоторую "машину Тьюринга". Очевидно, что таких вариантов $2^8=256$.
Это при условии, что снято требование об обязательном переходе между состояниями.

Полностью согласен :D
Dan B-Yallay в сообщении #1303091 писал(а):
В этом вы правы, получается больше чем 16. А именно $9*16=144$, если опять не вру. Похоже, мне тоже пора идти читать матчасть.

:appl: :appl: :appl:
У меня тоже самое)
Sicker в сообщении #1303071 писал(а):
И не забываем про второе состояние, тогда суммарное число комбинаций 12*12

Pavia в сообщении #1303108 писал(а):
Признаю что в предыдущем посте ошибся. Подставляем условия в формулу получаем (2*2)^(2*2)=256

:appl:
Pavia в сообщении #1303108 писал(а):
Никаких троек.* - тут можно подискутировать но это лучше вынести в отдельная тему.

Мы выше уже разобрались :-)
Pavia в сообщении #1303108 писал(а):
Что касается основного вопроса следует изучить цепи Маркова. Только на практике их почти не применяют. Предпочитают использовать нейронные сети которые с некоторой погрешностью аппроксимируют неизвестную функцию.

Мне тоже первое что пришло в голову это использовать нейронные сети.
arseniiv в сообщении #1303204 писал(а):
Например, для байесовских сетей
и подобных моделей есть алгоритмы вывода состояния неизвестных переменных. В самом плохом случае здесь могло бы подойти аналогичное.

Спасибо, почитаю)
arseniiv в сообщении #1303204 писал(а):
Кроме того, можно моделировать сразу все возможные автоматы, отсекая несоответствующие парам (вход, выход) данного, генерируя входные символы в случае неоднозначности случайно. Когда в пуле останется мало автоматов, всё чаще будут встречаться ситуации, когда поведение всех автоматов по одному из входных символов уже известно, и потому можно будет выбрать детерминированно другой. Это не обязательно оптимальный алгоритм, но лёгкий в реализации и для вашего количества (255) должен быстро давать ответ, особенно если подбирать вероятность выбора очередного входного символа при неоднозначности аккуратно (а не просто 0,5).

Это по сути, то что я в начале предложил.

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


11/12/05
7669
Diкий Запад
Sicker в сообщении #1303268 писал(а):
У меня тоже самое)
Не уверен, что то же самое:

Sicker в сообщении #1303061 писал(а):
Я думаю так, можно рассмотреть все возможные конфигурации черных ящиков (их здесь вроде 72)
Sicker в сообщении #1303066 писал(а):
3*3*4*4*2
$$ 144 \ne 72 \ne 3*3*4*4*2 $$
Sicker в сообщении #1303071 писал(а):
И не забываем про второе состояние, тогда суммарное число комбинаций 12*12
$144 = 12*12$
:appl:

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


27/04/09
24101
Уфа
Sicker в сообщении #1303268 писал(а):
Это по сути, то что я в начале предложил.
Но вы не указали, когда этому алгоритму рано, а когда пора заканчивать. Впрочем, я тоже. И ещё у меня там опечатка — разумеется, 256, а не 255.

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

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

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



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

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


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

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