2014 dxdy logo

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

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




На страницу Пред.  1, 2, 3  След.
 
 Re: Алгоритм деления пополам для произвольной булевой функции
Сообщение10.01.2013, 16:42 
Цель в том и состоит чтобы выяснить, как это записать.

 
 
 
 Re: Алгоритм деления пополам для произвольной булевой функции
Сообщение10.01.2013, 16:47 
Аватара пользователя
Сформулируйте словами правило выбора следующего куска из нескольких имеющихся.
Стандартный язык - псевдопаскаль. Но можно и на русском :D

 
 
 
 Re: Алгоритм деления пополам для произвольной булевой функции
Сообщение10.01.2013, 16:51 
involume, машина Тьюринга вам ничем не поможет при выяснении, как выглядит алгоритм и вычисляет ли он монотонность функции.

 
 
 
 Re: Алгоритм деления пополам для произвольной булевой функции
Сообщение17.01.2013, 13:55 
А как мне тогда быть, если вот тот самый алгоритм проверки монотонности с помощью машины Тьюринга меня попросили записать в виде состояний МТ?

 
 
 
 Re: Алгоритм деления пополам для произвольной булевой функции
Сообщение17.01.2013, 14:00 
Аватара пользователя
Что значит попросили? Курсовая? Где?
Испросите разрешения воспользоваться теоремами композиции и т.п. :shock:

 
 
 
 Re: Алгоритм деления пополам для произвольной булевой функции
Сообщение17.01.2013, 14:24 
Да, курсовая. Теоремами этими можно пользоваться.

 
 
 
 Re: Алгоритм деления пополам для произвольной булевой функции
Сообщение21.03.2013, 22:02 
Вопрос такой. У меня есть лента МТ, я переписываю её на вторую ленту, то есть получается две одинаковые ленты. Как с помощью состояний МТ сделать так, чтобы мы нашли середину у этих лент. То есть допустим если мы идём слева одной ленты, а у другой справа. Если есть 1 или 0, то вместо них записываем пустой символ. Так вот, собственно такой алгоритм полностью сотрёт две ленты и оставит лямбда, как этого избежать?

 
 
 
 Re: Алгоритм деления пополам для произвольной булевой функции
Сообщение22.03.2013, 13:02 
А не проще будет записывать на вторую просто единицы, а потом разделить число пополам? После этого нужное отшагать по первой.

 
 
 
 Re: Алгоритм деления пополам для произвольной булевой функции
Сообщение22.03.2013, 13:53 
Аватара пользователя
involume в сообщении #699494 писал(а):
Вопрос такой. У меня есть лента МТ, я переписываю её на вторую ленту,

Не очень понятны ограничения задачи. Две ленты, 3 буквы внешнего алфавита?
"Пустышку" можно использовать как дополнительные буквы, организуя слова из пустышек между двумя единичками (или ноль - один, как скобки).

 
 
 
 Posted automatically
Сообщение22.03.2013, 14:22 
Аватара пользователя
 i  Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы не оформлены $\TeX$ом

involume в сообщении #669773 писал(а):
1. Сравниваем соседние биты пары, затираем пару. Формируем справа
строки из первых (q1) и вторых (q2) эл-в пар (Q1 и Q2 соответственно).
Повторяем до тех пор пока не сотрем исходную строку значений с ленты или пока не встретится пара с отношением q1>q2, во втором случае функция не монотонна.
2. Склеиваем получившиеся строки Q1 и Q2. Переходим к 1 шагу
алгоритма. Цикл повторяется N раз, где N число аргументов функции.
3. Если цикл выполняется N раз ф-ция монотонна.

Теперь это надо как-то в виде состояний записать вида q a -> q b D
involume, наберите формулы $\TeX$ом. Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

 
 
 
 Posted automatically
Сообщение22.03.2013, 17:29 
Аватара пользователя
 i  Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
вернул

 
 
 
 Re: Алгоритм деления пополам для произвольной булевой функции
Сообщение23.03.2013, 12:35 
У нас алфавит из ${0,1}$, сама проблема в том, как с помощью состояний описать процесс деления 1 ленты пополам. Было предположение на счёт этого, но видимо оно не правильное:
$q_f (0,0) \to q_f (lamdba,lambda) (R,L) \kill$
$q_f (0,1) \to q_f (lamdba,lambda) (R,L) \kill$
$q_f (1,0) \to q_f (lamdba,lambda) (R,L) \kill$
$q_f (1,1) \to q_f (lamdba,lambda) (R,L) \kill$
$q_f (lambda,0) \to q_p (lamdba,0) (L,S) \kill$
$q_f (lambda,1) \to q_p (lamdba,1) (L,S) \kill$
$q_f (0,lambda) \to q_p (0,lamdba) (S,R) \kill$
$q_f (1,lambda) \to q_p (1,lamdba) (S,R) \kill$
Это как раз описанный мой алгоритм с двумя лентами, когда мы начинаем двигаться с двух разных сторон и записывать вместо 1 или 0 лямбда.

 
 
 
 Re: Алгоритм деления пополам для произвольной булевой функции
Сообщение23.03.2013, 22:08 
Может, лучше \lambda $\lambda$?

 
 
 
 Re: Алгоритм деления пополам для произвольной булевой функции
Сообщение24.03.2013, 15:22 
Цитата:
Может, лучше \lambda $\lambda$?

Какая разница, как я это написал, лучше бы предложили мысль хоть какую-то по этому поводу.

 
 
 
 Re: Алгоритм деления пополам для произвольной булевой функции
Сообщение24.03.2013, 15:44 
Аватара пользователя
Уже предложена - для начала расширьте внешний алфавит, а потом "конвертируйте" в старый.

 
 
 [ Сообщений: 34 ]  На страницу Пред.  1, 2, 3  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group