PARALLEL.RU

Дискуссионный клуб по параллельным вычислениям
Текущее время: 18 ноя 19 1:39

Часовой пояс: UTC + 4 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 18 ]  На страницу 1, 2  След.
Автор Сообщение
СообщениеДобавлено: 20 май 06 20:27 
Не в сети

Зарегистрирован: 20 май 06 20:24
Сообщения: 10
Помогите пожалуйста с алгоритмом (словесно или пример) эквивалентности СТРУКТУРНЫХ автоматов Мура. Заданы два структурных автомата Мура, нужно определить эквивалентны они или нет...


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: 22 май 06 21:05 
Не в сети

Зарегистрирован: 19 окт 04 11:21
Сообщения: 197
komapp@mail.ru писал(а):
Помогите пожалуйста с алгоритмом (словесно или пример) эквивалентности СТРУКТУРНЫХ автоматов Мура. Заданы два структурных автомата Мура, нужно определить эквивалентны они или нет...

Посмотрите книгу:
Айзерман М.А., Гусев Л.А., Розоноэр Л.И., Смирнова И.М., Таль А.А. Логика. Автоматы. Алгоритмы М.: Физматгиз, 1963. – 556 с.
В ней целая глава - "Эквивалентность и минимизация последовательностных машин". Может, и найдете то, что Вам нужно. Только, думаю, нужно будет Ваши структурные автоматы привести к абстрактным.

_________________
Лучшее - враг хорошего?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: 23 май 06 9:00 
Не в сети

Зарегистрирован: 20 май 06 20:24
Сообщения: 10
Цитата:
"Только, думаю, нужно будет Ваши структурные автоматы привести к абстрактным."
Такое возможно привести структурные к абстрактным?
Вообще тема называется Определение эквивалентности структурных автоматов Мура. Считать их эквивалентными если они могут быть получены из одной ГСА.
Я получил два разных структурных автомата, теперь надо определеить эквивалентны они или нет...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: 23 май 06 20:44 
Не в сети

Зарегистрирован: 19 окт 04 11:21
Сообщения: 197
komapp@mail.ru писал(а):
Цитата:
"Только, думаю, нужно будет Ваши структурные автоматы привести к абстрактным."
Такое возможно привести структурные к абстрактным?

Переименуйте структурные алфавиты (входной/выходной) обычными буквами и получите абстрактный.
komapp@mail.ru писал(а):
Вообще тема называется Определение эквивалентности структурных автоматов Мура. Считать их эквивалентными если они могут быть получены из одной ГСА.
Я получил два разных структурных автомата, теперь надо определеить эквивалентны они или нет...

Это Вы из одной ГСА получили два разных автомата? Если так, то они в этом случае эквивалентны (поскольку обратным преобразованием они приводятся к одной модели - ГСА, что и есть доказательство их эквивалентности).
Но здесь Вам, наверное, лучше почитать С.Баранова. Синтез микропрограммных автоматов. Там он как раз и выполняет взаимные преобразования ГСА в КА и обратно. Смотрели?

_________________
Лучшее - враг хорошего?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: 24 май 06 9:59 
Не в сети

Зарегистрирован: 20 май 06 20:24
Сообщения: 10
Цитата:
Но здесь Вам, наверное, лучше почитать С.Баранова. Синтез микропрограммных автоматов.

Сам преподаватель советовал эту книгу...Но ее нигде в городе нет. В инете электронных вариантов тоже нет. А курсовой уже в пятницу сдавать.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: 24 май 06 13:18 
Не в сети

Зарегистрирован: 19 окт 04 11:21
Сообщения: 197
komapp@mail.ru писал(а):
Цитата:
Но здесь Вам, наверное, лучше почитать С.Баранова. Синтез микропрограммных автоматов.

Сам преподаватель советовал эту книгу...Но ее нигде в городе нет. В инете электронных вариантов тоже нет. А курсовой уже в пятницу сдавать.

Сложно Вам чем-то помочь :( Но преподаватель должен был бы дать по идее нужный материал. Можно, конечно, отсканировать (у меня она есть). Но... нужно знать, что конкретно. Насколько я помню все это привязано к минимизации автоматов и достаточно разбросано по книге. А если еще нужно и описание преобразований ГСА в КА и обратно, то объем еще увеличится :(
В Инете на ALib.ru ее продают за 400 руб., но ... до пятницы Вам не успеть :(

_________________
Лучшее - враг хорошего?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: 24 май 06 16:45 
Не в сети

Зарегистрирован: 20 май 06 20:24
Сообщения: 10
Цитата:
А если еще нужно и описание преобразований ГСА в КА и обратно, то объем еще увеличится


Мне очень помогло преобразование КА в ГСА. Можно даже словестно.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: 24 май 06 22:36 
Не в сети

Зарегистрирован: 19 окт 04 11:21
Сообщения: 197
komapp@mail.ru писал(а):
Цитата:
А если еще нужно и описание преобразований ГСА в КА и обратно, то объем еще увеличится


Мне очень помогло преобразование КА в ГСА. Можно даже словестно.

Посмотрите статью:
Любченко В.С. Искусство программирования … RS-триггера?! Часть 1. Электронная схема и формальные модели. http://www.softcraft.ru/auto/ka/rsm/rsm01.shtml. Особенно на в ней на рис.4 - автоматные графы и на рис. - ГСА автоматов на рис.4. Думаю, догадаться можно. Подробно же расписывать - долго :(
Хорошо бы Вам поискать еще одну книгу - Э.Хамби. Программирование таблиц решений. Нужно только учитывать, что одна ТР - это одно состояние автомата. Как преобразовать одну ТР и блок-схему в ней есть.

_________________
Лучшее - враг хорошего?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: 25 май 06 21:15 
Не в сети

Зарегистрирован: 20 май 06 20:24
Сообщения: 10
Наверное я уже надоел:) Завтра все закончится. Появился еще один вопрос. Есть ГСА, преобразую ее в автомат. Из автомата получаю другую ГСА. Ее снова преобразую в автомат. Минимизурую таблицы переходов этих автоматов.
1. Они должны получиться одинаковыми?
2. Если они получатся одинаковыми, можно ли проверять эквивалентность таким способом (минимизацией таблиц переходов)?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: 26 май 06 0:08 
Не в сети

Зарегистрирован: 19 окт 04 11:21
Сообщения: 197
komapp@mail.ru писал(а):
Наверное я уже надоел:) Завтра все закончится.

Я бы предпочел, чтобы продолжилось ;) В смысле, чтобы у Вас остался интерес к автоматам. Поверьте, у автоматов было, есть и будет большое будущее. Тогда это будет только начало. А я в этом случае буду считать, что время потрачено не даром ;)
komapp@mail.ru писал(а):
Появился еще один вопрос. Есть ГСА, преобразую ее в автомат. Из автомата получаю другую ГСА. Ее снова преобразую в автомат. Минимизурую таблицы переходов этих автоматов.
1. Они должны получиться одинаковыми?

Не обязательно. Минимальный автомат у некоторого автомата может быть не один.
komapp@mail.ru писал(а):
2. Если они получатся одинаковыми, можно ли проверять эквивалентность таким способом (минимизацией таблиц переходов)?

В результате таких преобразований автоматы могут получиться и разными, но поскольку последний автомат получен путем эквивалентных преобразований, то эти автоматы эквивалентны по определению ;) Хотя, как я уже сказал, если мы из двух внешне разных автоматов получим одну ГСА, то смею утверждать, что такие автоматы эквивалентны. Хотя, если честно, о таком доказательстве я не слышал ;) Просто рассуждаю логически. Если какие-то две модели сводятся к одной путем эквивалентных преобразований, то эти исходные модели эквивалентны.
Да. Минимизация не есть проверка на эквивалентность. Хотя, конечно, все минимальные автоматы некоторого автомата эквивалентны. Речь, наверное, должна идти о минимальных автоматах разных автоматов, проверяемых на эквивалентность. Хотя эвивалентность минимальных автоматов, думаю, легче доказывать. Просто меньше объем работы ;).

_________________
Лучшее - враг хорошего?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: 31 май 06 20:09 
Не в сети

Зарегистрирован: 20 май 06 20:24
Сообщения: 10
Огромное спасибо...За курсовой я получил отлично...
Цитата:
Поверьте, у автоматов было, есть и будет большое будущее. Тогда это будет только начало. А я в этом случае буду считать, что время потрачено не даром

Пока я не увидел практического применения автоматов, поэтому они особый интерес не вызывают...У меня в следующем семестре будет предмет ТЯП, вроде он тесно связан с автоматами...может там он (интерес) и проснется...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: 31 май 06 20:11 
Не в сети

Зарегистрирован: 20 май 06 20:24
Сообщения: 10
а где практически автоматы применяются???


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: 1 июн 06 15:26 
Не в сети

Зарегистрирован: 19 окт 04 11:21
Сообщения: 197
komapp@mail.ru писал(а):
а где практически автоматы применяются???

Да везде - от проектирования "железа", до программирования; от последовательного программирования, до параллельного... ;)
Вам, наверное, их плохо дают, так сказать, на уровне ТЯП-ЛЯП :D , если у Вас такое представление о них :(
См. для примера сайты:
1) SWITCH-технология - http://is.ifmo.ru/
2) КА-технология - http://www.softcraft.ru/forum/viewforum ... efd927be3d

_________________
Лучшее - враг хорошего?


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: 1 июн 06 15:32 
Не в сети

Зарегистрирован: 20 май 06 20:24
Сообщения: 10
Цитата:
Да везде - от проектирования "железа", до программирования; от последовательного программирования, до параллельного...

Учусь на третем курсе по специальности "Программное обеспечение вычислительной техники и автоматизированных систем". Преподавание считаю хорошим, писал довольно сложные проекты, но сказать, что прямо сталкивался с автоматами не могу. Или я глупец или...


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: 1 июн 06 16:17 
Не в сети

Зарегистрирован: 19 окт 04 11:21
Сообщения: 197
komapp@mail.ru писал(а):
... но сказать, что прямо сталкивался с автоматами не могу. Или я глупец или...

Не думаю, что этот вариант ... ;) Так обычно дают, т.к. в програмировании автоматы достаточно специализированны. Стандартно - теория и проектирование компиляторов. Но ситуация меняется (правда, как я считаю, медлено). Тот же - UML. Там все фактически на автоматах. Это-то есть последний "писк". Какие автоматы и какой "писк" - другой вопрос. Но уж c UML-то по идее Вас должны бы знакомить, если Ваши преподаватели отслеживают современные тенденции в программировании?

_________________
Лучшее - враг хорошего?


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

Часовой пояс: UTC + 4 часа [ Летнее время ]


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

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


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

Найти:
Перейти:  
cron
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB