2014 dxdy logo

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

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




 
 Распознавание некоторых отображений
Сообщение15.03.2015, 17:55 
Рассмотрим следующую простую задачу:
Пусть $w_k$ - произвольные непустые строки.
Пусть дана строка $w=\prod\limits_{k=1}^n aw_kb$, где $ab\neq\epsilon$. Надо найти нетривиальные $a,b$ (попроще и пооптимальнее) и определить, в каком случае задача разрешима. У меня получилось, что задача разрешима, если $n\geqslant 2$ и неверно, что все $w_k$ начинаются на один символ и неверно, что все $w_k$ заканчиваются на один символ. Алгоритм решения состоит в том, чтобы брать начало и с конец строки и искать их вхождения в $w$ так, чтобы все вхождения были сочленены, а начало и конец максимальны по длине.
При анализе быдлокода у меня часто возникают такая и более сложные задачи. $w$ имеет более сложный вид: $w=c\left(\prod\limits_{k=1}^n aw_kb\right)d$, $w=c\left(\prod\limits_{k=1}^n aw_kb\right)d\left(\prod\limits_{k=1}^n eu_kf\right)g$, $w=c\left(\prod\limits_{k=1}^m aw_kb\right)d\left(\prod\limits_{k=1}^n eu_kf\right)g$ и т.п., надо найти все константы $a,b,c,d,e,...$ и минимальные ограничения на $m,n$.
Желательно найти как можно более простые критерии их разрешимости и как можно более простые и одновременно быстрые алгоритмы их решений.
В качестве необходимого условия разрешимости можем принять, что $n\geqslant 2$ и неверно, что все $w_k$ начинаются на один символ и неверно, что все $w_k$ заканчиваются на один символ, но достаточно ли оно для разрешимости? В качестве более общего алгоритма решения я даже не знаю, что брать. М.б. поиск одинаковых подстрок в строке, но хотелось бы, чтобы кто-то подтвердил, что это будет работать, поскольку я не вижу, сработает ли это точно или нет :roll:

 
 
 [ 1 сообщение ] 


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