Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > Prolog
Перезагрузить страницу Общая тема участников ветки Пролог
Ответ
 
Опции темы Опции просмотра
  (#781 (permalink)) Старый
gromozeka gromozeka вне форума
Флудер
 
Аватар для gromozeka
 
Сообщений: 3,170
Сказал(а) спасибо: 6
Поблагодарили 16 раз(а) в 15 сообщениях
Регистрация: 28.02.2005
Адрес: Израиль
По умолчанию 12.10.2016, 19:14

насколько я помню, обычная машина Тьюринга описывается таблицей. на пересечении символа и состояния находится тройка - новый символ, новое состояние и движение (вперед/назад). в тьюрмитах всё то же самое, но вместо движения 4 вида поворота, а само движение всегда вперёд. тьюрмита можно легко свести к обычной машине Тьюринга, если убрать повороты вправо/влево и оставить только отсутствие поворота и разворот.
Ответить с цитированием
  (#782 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,953
Сказал(а) спасибо: 2
Поблагодарили 302 раз(а) в 302 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 12.10.2016, 22:01

Цитата:
Сообщение от gromozeka Посмотреть сообщение
(вперед/назад)
Есть ещё третья команда - стоять на месте.
А программу для машины Тьюринга можно писать в виде графа, таблицы, но проще в виде исходного текста. Именно так у меня и сделано.
Ответить с цитированием
  (#783 (permalink)) Старый
defond defond вне форума
Member
 
Сообщений: 248
Сказал(а) спасибо: 35
Поблагодарили 2 раз(а) в 2 сообщениях
Регистрация: 15.11.2012
По умолчанию 31.12.2016, 17:59

Всем привет!

Сегодня последний день в году! Традиционно, поздравляю всех с наступающим Новым годом! Счастья всем участникам ветки, здоровья, кода без ошибок, успехов в рабочих проектах! Обязательно интересных и познавательных дискуссий!
Чтобы в семьях был мир и радость!
Чтобы работа приносила еще больше удовольствия и за нее достойно платили!

Вы хорошие люди! И пусть у Вас всех и у каждого в отдельности все было очень хорошо! И спасибо тем, кто помогал мне в этом году - Ваша помощь была неоценима!

Элис, отдельно пожелаю быть самой красивой и очаровательной! Умные и приятные девушки сейчас редкость! Пусть Вас ценят!

Всем счастья! И с Новым годом!
Ответить с цитированием
  (#784 (permalink)) Старый
defond defond вне форума
Member
 
Сообщений: 248
Сказал(а) спасибо: 35
Поблагодарили 2 раз(а) в 2 сообщениях
Регистрация: 15.11.2012
По умолчанию 31.12.2017, 18:20

Всем привет!
И опять, традиционно, с Наступающим Новым годом!

Счастья, здоровья, всего самого доброго!
Ответить с цитированием
  (#785 (permalink)) Старый
gromozeka gromozeka вне форума
Флудер
 
Аватар для gromozeka
 
Сообщений: 3,170
Сказал(а) спасибо: 6
Поблагодарили 16 раз(а) в 15 сообщениях
Регистрация: 28.02.2005
Адрес: Израиль
По умолчанию 31.12.2017, 18:59

С новым годом!
Ответить с цитированием
Ads.
  (#786 (permalink)) Старый
VictorY VictorY вне форума
Member
 
Аватар для VictorY
 
Сообщений: 984
Сказал(а) спасибо: 0
Поблагодарили 43 раз(а) в 43 сообщениях
Регистрация: 10.02.2005
По умолчанию 31.12.2017, 20:25

Приятно быть на островке, населенном единоинтересующимися!

С Новым Годом!
Ответить с цитированием
  (#787 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,781
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 27.02.2018, 16:11

Я написала статью про 2 задачи, про которые мы здесь почти все писали программы. Это задача о рыцарях и оруженосцах (в статье - о ревнивых мужьях) и задача о миссионерах и каннибалах. В статье рассматривается математическая сторона вопроса.

Вот статья https://arxiv.org/pdf/1802.09369.pdf

Ответить с цитированием
  (#788 (permalink)) Старый
SergeMukhin78 SergeMukhin78 вне форума
Member
 
Сообщений: 556
Сказал(а) спасибо: 17
Поблагодарили 35 раз(а) в 35 сообщениях
Регистрация: 28.03.2012
По умолчанию 27.02.2018, 16:25

Цитата:
Сообщение от Alison Посмотреть сообщение
математическая сторона вопроса
супер! ничего не понял
Ответить с цитированием
  (#789 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,781
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 27.02.2018, 16:51

Цитата:
Сообщение от SergeMukhin78 Посмотреть сообщение
супер! ничего не понял
Ну, за минуту, да еще не на самом хорошем английском, трудно понять.
Надо смотреть еще раз.
Там про связь между этими задачами, точная такая простая связь, выраженная алгебраическим языком. Если читать чуть-чуть медленнее, то все будет понятно.
Ответить с цитированием
  (#790 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,781
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 27.02.2018, 17:02

На самом деле, надо начинать читать с картинок - они на 8 и 9 страницах!

После этого вся суть уже будет понятна и без слов почти.
Ответить с цитированием
  (#791 (permalink)) Старый
VictorY VictorY вне форума
Member
 
Аватар для VictorY
 
Сообщений: 984
Сказал(а) спасибо: 0
Поблагодарили 43 раз(а) в 43 сообщениях
Регистрация: 10.02.2005
По умолчанию 28.02.2018, 00:07

Цитата:
Сообщение от Alison Посмотреть сообщение
На самом деле, надо начинать читать с картинок - они на 8 и 9 страницах!

После этого вся суть уже будет понятна и без слов почти.
Будучи червем клавишным, я в восхищении!
Не сомневаясь в математической корректности, задам вопросы, которые обычно задают на защитах диссертаций люди, слабо знакомые с деталями математической истории решения проблемы (если она существует) и с авторефератом.

Понятно, что эти две задачи (и, возможно, их больше) представляют проблему перевода системы из начального состояния в некоторе заданное, имея в наличии ограниченный набор политик, в условиях заданных ограничений. Здесь Alison показала, что две задачи могут быть представлены единой математической моделью.

В заключении статьи я ожидал увидеть выводы, которые отвечают на вопросы:
1. Можно ли на основании формулирования задачи определить имеет ли задача решение?
2. Есть ли конструктивный алгоритм получения решения задачи (не переборный).
3. Есть ли конструктивный эвристический алгоритм нахождения оптимального (или близкого к оптимальному) решения на заданной метрике?

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

Кстати здесь на форуме неоднократно решались задачи типа задачи Эйнштейна. Александр здесь даже выработал универсальный переборный подход.

Когда-то мы с Alison эту задачу обсуждали по переписке и ясно, что эта задача сводится к задаче группировки факторов (непротиворечивых в пределах группы).

Применительно к тематике этого форума как раз было бы интересно построение движка, который на основании формулировки фактов и отношений позволил бы:

либо сгенерировать текст пролог-программы, решающей конкретно сформулированную задачу близким к оптимальному способом;

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

Будучи клавишным червем, приношу извинения, если на поставленные вопросы уже имеются готовые ответы.
Ответить с цитированием
  (#792 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,781
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 28.02.2018, 00:23

Ну, пока только могу сделать замечание, что из статьи следует, что сначала надо решать задачу о миссионерах и каннибалах (даже если нужны решения другой задачи), так как их относительно мало и все решения легко найти, перебирая все перечисленные варианты. А потом по ним уже строить решения задачи о рыцарях и оруженосцах, которых очень много, если нужны они все; эта часть уже конструктивна.

Вообще, статья в некотором смысле и о том, что полезно выявлять симметрии, иногда они очень сильно могут сократить перебор (например, там есть 486 решений против 4).
Ответить с цитированием
Ads
  (#793 (permalink)) Старый
Винитарх Винитарх вне форума
Специалист
 
Аватар для Винитарх
 
Сообщений: 7,953
Сказал(а) спасибо: 2
Поблагодарили 302 раз(а) в 302 сообщениях
Регистрация: 01.03.2003
Адрес: Краснодар
По умолчанию 28.02.2018, 12:37

Цитата:
Сообщение от Alison Посмотреть сообщение
Я написала статью про 2 задачи, про которые мы здесь почти все писали программы. Это задача о рыцарях и оруженосцах (в статье - о ревнивых мужьях) и задача о миссионерах и каннибалах. В статье рассматривается математическая сторона вопроса.

Вот статья https://arxiv.org/pdf/1802.09369.pdf
Поздравляю! Великолепно!
Ответить с цитированием
  (#794 (permalink)) Старый
Alison Alison вне форума
Member
 
Сообщений: 4,781
Сказал(а) спасибо: 0
Поблагодарили 119 раз(а) в 116 сообщениях
Регистрация: 17.11.2004
По умолчанию 28.02.2018, 20:48

Цитата:
Сообщение от VictorY Посмотреть сообщение
В заключении статьи я ожидал увидеть выводы, которые отвечают на вопросы:
1. Можно ли на основании формулирования задачи определить имеет ли задача решение?
2. Есть ли конструктивный алгоритм получения решения задачи (не переборный).
3. Есть ли конструктивный эвристический алгоритм нахождения оптимального (или близкого к оптимальному) решения на заданной метрике?
Раз речь идет о поиске на графе состояний, то можно использовать все, что есть про это в теории графов. И самое приятное, что это все надо использовать только для задачи о миссионерах и каннибалах, где вершин - состояний - многократно меньше, при этом все они описаны в статье, т.е. их легко найти, ребра - переходы между состояниями - тоже описаны. Т.е. можно сходу строить матрицу смежности, например, и применять все что есть - алгоритм Уоршолла (строит матрицу достижимости, сложность O(n^3),) это уже делали в работе [9], но можно проще, матрица специфическая, поэтому там красивые формулы; алгоритм Флойда-Уоршолла, для поиска самих путей (сложность тоже О(n^3)); алгоритм Дейкстры - это все точные методы. Ну и те приближенные, которые есть для поиска путей на графах - тоже. Наверное, с учетом специфики, можно получить что-то более простое и симпатичное, чем обычно, в каждом случае.
Ответить с цитированием
  (#795 (permalink)) Старый
VictorY VictorY вне форума
Member
 
Аватар для VictorY
 
Сообщений: 984
Сказал(а) спасибо: 0
Поблагодарили 43 раз(а) в 43 сообщениях
Регистрация: 10.02.2005
По умолчанию 28.02.2018, 23:30

Цитата:
Сообщение от Alison Посмотреть сообщение
Раз речь идет о поиске на графе состояний, то можно использовать все, что есть про это в теории графов. И самое приятное, что это все надо использовать только для задачи о миссионерах и каннибалах, где вершин - состояний - многократно меньше, при этом все они описаны в статье, т.е. их легко найти, ребра - переходы между состояниями - тоже описаны. Т.е. можно сходу строить матрицу смежности, например, и применять все что есть - алгоритм Уоршолла (строит матрицу достижимости, сложность O(n^3),) это уже делали в работе [9], но можно проще, матрица специфическая, поэтому там красивые формулы; алгоритм Флойда-Уоршолла, для поиска самих путей (сложность тоже О(n^3)); алгоритм Дейкстры - это все точные методы. Ну и те приближенные, которые есть для поиска путей на графах - тоже. Наверное, с учетом специфики, можно получить что-то более простое и симпатичное, чем обычно, в каждом случае.
Спасибо! Это достойно быть помещенным в выводы!
Ответить с цитированием
Ответ

Опции темы
Опции просмотра

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

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Тема для курсовой? С++ & dll era88 Вопросы начинающих программистов 0 19.04.2011 01:08
Где моя тема???????? MYRKA2124 Любые вопросы от новичков 6 11.01.2011 11:32
2 видео карты в гросс по 512памяти каждая-сколько общая видео память? aleksej Память 7 10.02.2009 22:07
Чтение параметра из ветки HKEY_LOCAL_MACHINE Hoot C++ Builder 6 30.08.2006 11:37
Вот так тема... dead Pascal 5 11.06.2006 20:22
Требуется общая информация о передаче потокового видео/аудио Palmman Сетевое программирование 2 08.06.2006 10:36
Как написать реакцию на выбор определенного елемента ветки компонента TreeView Gremlin Inc. C++ Builder 5 22.04.2006 17:11
Реестр сохранение и восстановление ветки реестра JJ WinAPI 7 22.11.2005 00:05
Старая тема про NU Алексеев Николай Юмор 1 24.10.2004 15:50
Общая ошибка ODBC UnLtd Visual Basic 0 09.04.2004 07:42
Общая ошибка защиты как исправить Anonymous Kylix 1 04.07.2003 01:47



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов