Алгебра, логика, теория чисел и теория алгоритмов

Список форумов  |  Новая тема  |  В корень форума  |  В корень темы  |  Режим дерева  |  Поиск

Следующая тема  |  Предыдущая тема

Конечные автоматы

Автор: Сергей Подзоров (---.math.nsc.ru) Дата:   24 Nov. 2005 13:36 Пусть n --- натуральное число > 0. Чему равно максимально возможное число состояний минимального детерменированного конечного автомата, эквивалентного недетерминированному конечному автомату с n состояниями, если в алфавите всего один символ? См. также здесь

Ответить на сообщение

Re: Конечные автоматы

Автор: esperanto (---.94.124.67.cable.012.net.il) Дата:   26 Nov. 2005 16:07 п

Ответить на сообщение

Re: Конечные автоматы

Автор: maxal (---.dsl.sndg02.pacbell.net) Дата:   27 Nov. 2005 09:14 Для n > 1 ответом будет n - 1 + p1^k1*...*pm^km где p1 < ... < pm - все простые меньшие n, а ki = [ln(n)/ln(pi)] (т.е. ki = максимальному показателю такому, что pi^ki <= n). Это значение достигается на автомате с состояниями 1,2,...,n и переходами вида: i -> i+1 n -> n n -> n + 1 - pi^ki Идея доказательства состоит в том, что за n-1 первых переходов автомат достигнет всех своих циклов, а дальнейшее количество различных недетерминированных состояний равно НОК длин его циклов. Максимальное значение достигается когда циклы имеют длины p1^k1, ..., pm^km. Вот искомое количество состояний для n=1..10: 1 3 7 10 16 17 25 30 37 38

Ответить на сообщение

Re: Конечные автоматы

Автор: Рустем (---.megalan.ru) Дата:   27 Nov. 2005 19:50 Приведённые числа не соответствуют ответу начиная уже со второго члена. Для n=2 нет простых меньше 2, стало быть согласно верхнему ответу получаем 1 (а не 3). Если заменим "все простые меньше n" на "все простые не превосходящие n" ответ для n=2 и 3 совпадёт с нижеприведённым, однако другие ответы не будут соответствовать этому даже с учётом этой поправки.

Ответить на сообщение

Re: Конечные автоматы

Автор: maxal (---.dsl.sndg02.pacbell.net) Дата:   28 Nov. 2005 01:04 > Если заменим "все простые меньше n" на "все простые не превосходящие n" Естественно, это описка. > однако другие ответы не будут соответствовать этому даже с учётом этой поправки. Почему?

Ответить на сообщение

Re: Конечные автоматы

Автор: maxal (---.dsl.sndg02.pacbell.net) Дата:   28 Nov. 2005 01:44 > ответ для n=2 и 3 совпадёт с нижеприведённым, однако другие ответы не будут соответствовать этому даже с учётом этой поправки А! Ты про числовые значения? Там баг в проге был ;) Правильные значения для n=1..10 такие: 1 3 8 15 64 65 426 847 2528 2529 Кстати, для n=3 результат тоже неверным был.

Ответить на сообщение

Re: Конечные автоматы

Автор: Рустем (---.megalan.ru) Дата:   28 Nov. 2005 01:45 Получается начало последовательности: 1 3 8 16 64 65 426 847 2528 2529 (считал вручную, надеюсь не ошибся).

Ответить на сообщение

Re: Конечные автоматы

Автор: maxal (---.dsl.sndg02.pacbell.net) Дата:   28 Nov. 2005 01:46 По исправленным результатам сразу нашлась последовательность A065500.

Ответить на сообщение

Re: Конечные автоматы

Автор: maxal (---.dsl.sndg02.pacbell.net) Дата:   28 Nov. 2005 01:51 > 1 3 8 16 64 65 426 847 2528 2529 (считал вручную, надеюсь не ошибся). Для n=4 должно быть 15, в остальном наши результаты сходятся.

Ответить на сообщение

Re: Конечные автоматы

Автор: Гост (---.ict.nsk.su) Дата:   29 Nov. 2005 13:19 "Лабиринт состоит из комнат и соединяющих комнаты коридоров. Всего n комнат, одна из них является стартовой. Коридоры содержат клапаны, благодаря которым проход по каждому коридору возможен только в одном направлении. (Хотя, конечно, пару комнат A и B могут соединять два коридора: по одному можно пройти из A в B, по другому из B в A. Коридоры, которые приводят из комнаты в неё саму, тоже допускаются.) Пусть для натурального k множество R(k) --- это множество всех комнат, в которые можно пройти из стартовой комнаты, миновав ровно k коридоров. Каково максимально возможное число различных R(k)? " Разве из такой формулировки задачи не следует, что максимально возможное число различных R(k) не превосходит числа различных подмножеств из n элементов? Почему тогда такие большие числа получаются здесь: 1 3 8 15 64 65 426 847 2528 2529 ? Или в такой формулировке получается другая задача?

Ответить на сообщение

Re: Конечные автоматы

Автор: Рустем (---.megalan.ru) Дата:   29 Nov. 2005 13:57 Я не понимаю, что значит недерминированный автомат эквивалентен детерминированному (в каком смысле). А здесь максимальное число различных R(k)=2^n-1. Так как при фиксированном варианте коридоров всегда число различных R(k)=1 (некоторое множество коридоров являющемся каким то подмножеством). Когда спрашивают максимально возможное, я понимаю как изменение схем коридоров. Так как для любого непустого подмножества комнат существует некоторая схема коридоров при котором это подмножество является множеством всех комнат куда можно прийти миновав ровно к комнат, то получаем результат 2^n-1.

Ответить на сообщение

Re: Конечные автоматы

Автор: Гост (---.ict.nsk.su) Дата:   29 Nov. 2005 14:10 Мне кажется, что здесь нельзя менять схему коридоров. Надо выбрать такую схему из всех схем, для которой R(k) максимально. Ясно, что R(k) не превосходит 2^n-1, а больше ничего не ясно. Далее к условию с лабиринтами приводится пояснение: "Пример 1: n=2, первая комната стартовая, коридоры ведет из первой комнаты во вторую, а из второй --- во вторую и в первую. Тогда R(0) = { 1 }, R(1) = { 2 } и R(k) = { 1,2 } для k больше либо равно 2. Всего 3 различных R(k). Пример 2: n=2, первая комната стартовая, коридоров нет вообще. Тогда R(0) = { 1 } и R(k) = пустому множеству для k больше либо равного 1. Всего 2 различных R(k)." Так что при фиксированном варианте коридоров количество различных R(k) может быть различным, а не всегда R(k)=1.

Ответить на сообщение

Re: Конечные автоматы

Автор: Гост (---.ict.nsk.su) Дата:   29 Nov. 2005 14:13 Из второго примера, кстати, следует, что число различных R(k) не превосходит 2^n, т.к. R(k) может быть пустым множеством.

Ответить на сообщение

Re: Конечные автоматы

Автор: Рустем (---.megalan.ru) Дата:   29 Nov. 2005 14:32 Я имел в виду и фиксированность к. Тогда я понимаю, что система коридоров фиксированная, а к меняется. Соответственно образуются подмножества С(n)={R(0), R(1),... (до бесконечности)}. Делается подсчёт различных значений подмножеств среди этой последовательности при заданной схеме коридоров, соответствующее количеству элементов C(n). А далее, по видимому считают количество различных С(n) при изменении схемы коридоров. Тогда ограничение сверху будет 2^(2^n)-1.

Ответить на сообщение

Re: Конечные автоматы

Автор: Гост (---.ict.nsk.su) Дата:   29 Nov. 2005 14:41 Надо подождать комментариев автора. А пока я понимаю так, что надо придумать схему коридоров, при которой как можно больше различных R(k) при k=0,1,2,.....

Ответить на сообщение

Re: Конечные автоматы

Автор: Рустем (---.megalan.ru) Дата:   29 Nov. 2005 18:18 В любом случае, пока можно констатировать, что ответы maxala не совпадают с ответами для этой задачи как в вашем варианте (при n=7 у maxala больше 2^7), так и при моем понимании. В последнем случае при n=2 имеется 5 вариантов {{1},{0}},{1},{{1},{2},{0}},{{1},{1,2}},{{1},{2}} (0 - пустое множество).

Ответить на сообщение

Re: Конечные автоматы

Автор: maxal (---.dsl.sndg02.pacbell.net) Дата:   29 Nov. 2005 19:07 То, что получились значения большие 2^n объясняется просто. Дело в том, что циклы в построенном конечном автомате имеют общие элементы-состояния, и поэтому количество недетерминированных состояних будет меньше НОК длин циклов. Таким образом, приведенное мной выражение дает решение к другой задаче. ;)

Ответить на сообщение

Re: Конечные автоматы

Автор: maxal (---.dsl.sndg02.pacbell.net) Дата:   29 Nov. 2005 20:31 Полный перебор для n=1..5 дал такие значения: n=1: максимальное число достижимых недетерминированных состояний = 2 достигается на конечном автомате с матрицей смежности: [0] n=2: максимальное число достижимых недетерминированных состояний = 3 достигается на конечном автомате с матрицей смежности: [ 0, 0 ] [ 1, 0 ] n=3: максимальное число достижимых недетерминированных состояний = 6 достигается на конечном автомате с матрицей смежности: [ 0, 0, 1 ] [ 1, 0, 1 ] [ 0, 1, 0 ] n=4: максимальное число достижимых недетерминированных состояний = 11 достигается на конечном автомате с матрицей смежности: [ 0, 0, 1, 0 ] [ 1, 0, 1, 0 ] [ 0, 0, 0, 1 ] [ 0, 1, 0, 0 ] n=5: максимальное число достижимых недетерминированных состояний = 18 достигается на конечном автомате с матрицей смежности: [ 0, 0, 0, 1, 0 ] [ 1, 0, 0, 1, 0 ] [ 0, 0, 0, 0, 1 ] [ 0, 0, 1, 0, 0 ] [ 0, 1, 0, 0, 0 ] Кстати, матрицы получились интересного вида, легко улавливаются некоторые закономерности...

Ответить на сообщение

Re: Конечные автоматы

Автор: Рустем (---.megalan.ru) Дата:   29 Nov. 2005 21:28 Я понял, что сейчас решается задача Гост. Здесь ясно, что диагональные элементы не увеличат количество достижимых состояний. Матрицы которые получаются некоторой перестановкой строк и столбцов эквивалентны, соответствуют только перенумерации комнат. За счёт чего можно привести к более менее схожему виду. Понятно так же что количество нулей меньше количества 1. Из приведённых видов схем коридоров пока ничего другого не проглядывается. Разве что, в каждой строке (за исключением одного) и в каждом столбце (за исключением одного) ровно одна 1.

Ответить на сообщение

Re: Конечные автоматы

Автор: Рустем (---.megalan.ru) Дата:   29 Nov. 2005 21:49 Кстати, если первая строка и столбец соответствуют стартовой комнате, то R(k) есть множество ненулевых элементов в первой строке для к-ой степени матрицы инцидентности. Может это поможет вычислению максимального числа достижимых состояний в дальнейшем.

Ответить на сообщение

Re: Конечные автоматы

Автор: maxal (---.dsl.sndg02.pacbell.net) Дата:   30 Nov. 2005 02:51 > Кстати, если первая строка и столбец соответствуют стартовой комнате, то R(k) есть множество ненулевых элементов в первой строке для к-ой степени матрицы инцидентности. Именно так я и вычислял. Для n=6 текущее максимальное число достижимых недетерминированных состояний равно 27, дается матрицей [ 0, 0, 0, 1, 0, 0 ] [ 1, 0, 0, 1, 0, 0 ] [ 0, 0, 0, 0, 0, 1 ] [ 0, 0, 0, 0, 1, 0 ] [ 0, 0, 1, 0, 0, 0 ] [ 0, 1, 0, 0, 0, 0 ] но перебор еще не закончен. Можно предположить, что в общем виде матрица имеет вид: 0 0 ... 0 0 1 0 0 ... 0 0 1 0 ... 0 0 1 0 0 ... 0 0 0 0 ... 0 0 0 0 0 ... 0 1 0 0 ... 0 0 0 0 0 ... 1 0 ... 0 0 ... 0 0 0 0 1 ... 0 0 0 0 ... 0 0 0 1 0 ... 0 0 0 0 ... 0 1 0 0 0 ... 0 0 0 0 ... 1 0 0 0 0 ... 0 0 ... 0 1 ... 0 0 0 0 0 ... 0 0 где столбец содержащий две единицы имеет номер (n+1)/2 или (n+2)/2 в зависимости от четности n.

Ответить на сообщение

Re: Конечные автоматы

Автор: maxal (---.dsl.sndg02.pacbell.net) Дата:   30 Nov. 2005 03:03 А число максимальное число недетерминированных состояний, похоже, равно (n-1)^2+2.

Ответить на сообщение

Re: Конечные автоматы

Автор: Рустем (---.megalan.ru) Дата:   30 Nov. 2005 11:52 Думаю, что это случайное совпадение при малых n. При больших n по видимому порядок роста имеет вид n^sqrt(n). Формула (n-1)^2+2 связано с видом матрицы,имеющий во всех строках и столбцах за исключением одного одна 1, а в исключительной две (в начальный момент 0). Возможно уже c n=7 или в исключительном количество единиц увеличится до 3, или таких (исключительных станет 2.

Ответить на сообщение

Re: Конечные автоматы

Автор: Рустем (---.megalan.ru) Дата:   30 Nov. 2005 12:37 Контрпример к этой формуле легко построить. Возьмём одну комнату разъездов с к выходами и одну комнату встреч с к входами (в качестве комнаты встреч можно взять стартовую комнату), для остальных комнат один выход и один вход. Тогда образуется к циклов. Если количество элементов в этих циклах взаимно простое, то имеются все варианты выборок к элементов (по одному с каждого цикла). За счёт чего появляется более быстрый рост. Оценка порядка exp(sqrt(n)) оправдывается этими соображениями.

Ответить на сообщение

Re: Конечные автоматы

Автор: Рустем (---.megalan.ru) Дата:   30 Nov. 2005 12:46 Для вычисления проще взять комнату разъездов и комнату встреч в стартовой комнате.

Ответить на сообщение

Re: Конечные автоматы

Автор: Рустем (---.megalan.ru) Дата:   30 Nov. 2005 13:02 Оценка несколько улучшается если брать в качестве циклов 2,3,5,...Всего к простых чисел с условием (p(1)-1)+(p(2)-1)+...+(p(k)-1)

Ответить на сообщение

Re: Конечные автоматы

Автор: Рустем (---.megalan.ru) Дата:   30 Nov. 2005 13:04 Оборвалось. Если брать все простые подряд, то оценка получается n^sqrt(n*ln(n)).

Ответить на сообщение

Re: Конечные автоматы

Автор: maxal (---.dsl.sndg02.pacbell.net) Дата:   30 Nov. 2005 13:11 > Если количество элементов в этих циклах взаимно простое, то имеются все варианты выборок к элементов (по одному с каждого цикла). Все они будут является подмножествами недетерминированных состояний, но этих состояний может быть существенно меньше чем количество выборок. Я вполне допускаю, что может существовать контр-пример к формуле (n-1)^2+2, но оценка роста exp(sqrt(n)) мне также кажется необоснованной.

Ответить на сообщение

Re: Конечные автоматы

Автор: Рустем (---.megalan.ru) Дата:   30 Nov. 2005 13:14 В частности при n=14 имеем (2-1)+(3-1)+(5-1)+(7-1) меньше 14. Что позволяет строит количество достижимых состояний 2*3*5*7=210(больше 13^2+2).

Ответить на сообщение

Re: Конечные автоматы

Автор: maxal (---.dsl.sndg02.pacbell.net) Дата:   30 Nov. 2005 13:26 > В частности при n=14 имеем (2-1)+(3-1)+(5-1)+(7-1) меньше 14. Что позволяет строит количество достижимых состояний 2*3*5*7=210(больше 13^2+2). Я построил такой автомат с циклами: 0, 1 0, 2, 3 0, 4, 5, 6, 7 0, 8, 9, 10, 11, 12, 13 где 0 - стартовое состояние. Вот его недетерминированные состояния: [0] [1, 2, 4, 8] [0, 3, 5, 9] [0, 1, 10, 2, 4, 6, 8] [0, 1, 11, 2, 3, 4, 5, 7, 8, 9] [0, 1, 10, 12, 2, 3, 4, 5, 6, 8, 9] [0, 1, 10, 11, 13, 2, 3, 4, 5, 6, 7, 8, 9] [0, 1, 10, 11, 12, 2, 3, 4, 5, 6, 7, 8, 9] [0, 1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9] [0, 1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9] Всего их 9 штук, а не 210.

Ответить на сообщение

Re: Конечные автоматы

Автор: Рустем (---.megalan.ru) Дата:   30 Nov. 2005 14:33 Я ошибся считая количество состояний как произведение по циклам. Дело в том, что R(m)=Oбъединение R(m-n(i)) по всем циклам n(i) и множества состоящего из тех комнат если бы двигались только по одному циклу (не более к элементов). Поэтому наличие малых циклов (как здесь 2) быстро приводит к полному множеству. Для того, чтобы увеличить количество состояний надо иметь все длины примерно одного порядка n(i)~n/k. Тогда в каждом цикле будут браться подмножества из небольшого количества элементов и они будут различаться. По всей видимости k не удастся выбрать растущей как sqrt(n). Даже, если k~ln(n), оценка снизу будет порядка n^ln(n) а не полиномиальная.

Ответить на сообщение

Re: Конечные автоматы

Автор: Рустем (---.megalan.ru) Дата:   30 Nov. 2005 14:49 Всё таки брать к больше 2 невыгодно, так как уже примерно через (n/k)^2 шагов R(m) будет множеством всех комнат. Стало быть оценка снизу квадратичная. Один из вариантов разбить n+1=n1+n2 (n1 и n2 взаимно простые). Тогда количество состояний похоже n1*n2.

Ответить на сообщение

Re: Конечные автоматы

Автор: Рустем (---.megalan.ru) Дата:   30 Nov. 2005 15:45 Я начал сомневаться в вычислениях maxalа. По моим оценкам число состояний не больше (n+1)(n+2)/4+const(небольшая, учитывающая чётности и т.п.). Для n=6 это дает порядка 14. Если нет циклов то не больше n+1. Один цикл не больше n. Оптимальным является два цикла (топологический граф - восьмёрка). За счёт некоторого удаления вершины восьмёрки удается несколько увеличить линейный член в полиноме от n, начинающийся с n^2/4. Вот эти соображения дают вышеприведённую оценку. Поэтому, хотелось бы посмотреть на R(k) при n=5,6.

Ответить на сообщение

Re: Конечные автоматы

Автор: maxal (---.dsl.sndg02.pacbell.net) Дата:   30 Nov. 2005 15:59 > Поэтому, хотелось бы посмотреть на R(k) при n=5,6. Легко! Случай n=5. Автомат задается матрицей смежности: [ 0, 0, 0, 1, 0 ] [ 1, 0, 0, 1, 0 ] [ 0, 0, 0, 0, 1 ] [ 0, 0, 1, 0, 0 ] [ 0, 1, 0, 0, 0 ] Стартовое состояние 1. Вот его недетерминированные состояния: 1 2 5 3 4 1, 2 2, 5 3, 5 3, 4 1, 2, 4 1, 2, 5 2, 3, 5 3, 4, 5 1, 2, 3, 4 1, 2, 4, 5 1, 2, 3, 5 2, 3, 4, 5 1, 2, 3, 4, 5 1, 2, 3, 4, 5 Общее число недетерминированных состояний = 18.

Ответить на сообщение

Re: Конечные автоматы

Автор: maxal (---.dsl.sndg02.pacbell.net) Дата:   30 Nov. 2005 16:02 Случай n=6. Автомат задается матрицей смежности: [ 0, 0, 0, 1, 0, 0 ] [ 1, 0, 0, 1, 0, 0 ] [ 0, 0, 0, 0, 0, 1 ] [ 0, 0, 0, 0, 1, 0 ] [ 0, 0, 1, 0, 0, 0 ] [ 0, 1, 0, 0, 0, 0 ] Стартовое состояние 1. Вот его недетерминированные состояния: 1 2 6 3 5 4 1, 2 2, 6 3, 6 3, 5 4, 5 1, 2, 4 1, 2, 6 2, 3, 6 3, 5, 6 3, 4, 5 1, 2, 4, 5 1, 2, 4, 6 1, 2, 3, 6 2, 3, 5, 6 3, 4, 5, 6 1, 2, 3, 4, 5 1, 2, 4, 5, 6 1, 2, 3, 4, 6 1, 2, 3, 5, 6 2, 3, 4, 5, 6 1, 2, 3, 4, 5, 6 1, 2, 3, 4, 5, 6 Число различных недетерминированных состояний = 27.

Ответить на сообщение

Re: Конечные автоматы

Автор: Рустем (---.megalan.ru) Дата:   30 Nov. 2005 16:24 Спасибо. Я понял, что у вас переход по столбцу и комната встреч (2)отличается от комнаты разъездов (4) за счёт чего можно увеличить коэффициент перед n^2 до 1. Соответствено для оптимального (максимального) числа состояний граф переходов должен иметь вид 1-2-....-n-(1) | (2) циклы получаются длины n и (n-1). Поэтому количество состояний действительно получается (n-1)^2+2.

Ответить на сообщение

Re: Конечные автоматы

Автор: Рустем (---.megalan.ru) Дата:   30 Nov. 2005 16:33 При отправке палочка (коридор) от n (по вертикали) сдвинулся. n - комната разъездов, 2 комната встреч (это дает всю информацию) и циклы длины n и n-1.

Ответить на сообщение

Re: Конечные автоматы

Автор: Рустем (---.megalan.ru) Дата:   30 Nov. 2005 16:42 У меня нумерация комнат отличается от нумерации maxala. Но всё таки напишу в этом виде (n-1)^2+2 состояний: {1},{2},...{n},{1,2},{2,3},...{n-1,n},{n,1,2}, {1,2,3},..... Вначале n одноэлементных множеств, потом по (n-1) двух элементных, трёхэлементных и т.д. (n-1) - (n-1)элементных и одно n элементное множество. Всего (n-1)^2+2.

Ответить на сообщение

Re: Конечные автоматы

Автор: Рустем (---.megalan.ru) Дата:   30 Nov. 2005 23:35 Всё таки я был прав с k циклами. Я это понял по дороге на работу, куда уехал после последней записи. Надо было разделить циклы (делать их независимыми). Соответственно пусть стартовая комната является комнатой разъездов (сразу к выходов). Далее каждый цикл (всего к) не возвращается в стартовую а в свою бинарную точку встреч. Пусть длины n(1),n(2),...,n(k). Тогда n(1)+n(2)+...+n(k)+s=n (s не меньше 1, таким образом циклы делаются независимыми). Если все n(i) взаимно просты то M(n) - искомое число состояний равно (1) M(n)=s+n(1)*n(2)*...*n(k). Из - за независимости циклов R(m) начиная с s состоит ровно из к комнат (по одному из каждого цикла). Соответственно начиная с n=26 оптимальное количество состояний находится по следующему алгоритму. Выбираем к так, чтобы сумма первых к простых чисел было меньше n. Пусть s=n-(p(1)+...p(k)). Если s больше чем p(k+1)-p(k), то p(k) заменяем на p(k+1), а s на s-p(k+1)+p(k). Если s больше чем p(k)-p(к-1), то заменим p(k-1) на p(k) и т.д. В конце концов получим n(1), n(2),...n(k) как последовательность первых простых чисел за исключением может одного. Тогда по формуле (1) находим M(n). Несложные вычисления показывают, что M(n)=exp(sqrt(2n)(1+o(1))).

Ответить на сообщение

Re: Конечные автоматы

Автор: Рустем (---.megalan.ru) Дата:   01 Dec. 2005 00:09 Отмечу, что при n=78 (вряд ли maxal сможет вычислить истинное значение) по этому алгоритму получаем M(78)=1+2*3*5*7*11*13*17*19=9699691, в то время как оценка exp(sqrt(2n))~256666, т.е. o(1) принимает не только отрицательные, но и положительные значения.

Ответить на сообщение

Re: Конечные автоматы

Автор: Рустем (---.megalan.ru) Дата:   01 Dec. 2005 09:04 Ошибся в оценке M(n). Точнее ln(M(n))~sqrt(2n*ln(n))*(1+o(1)). Соответственно в этом примере o(1) отрицательная. То, что M(n) начиная с некоторого n дает максимальное число состоянмй строго доказывается. При этом надо ещё рассмотреть циклы с хвостами типа 6 и доказать, что хвосты можно убрать до начала цикла.

Ответить на сообщение

Re: Конечные автоматы

Автор: maxal (---.dsl.sndg02.pacbell.net) Дата:   01 Dec. 2005 10:17 > То, что M(n) начиная с некоторого n дает максимальное число состоянмй строго доказывается. Можно увидеть доказательство? С какого n это так?

Ответить на сообщение

Re: Конечные автоматы

Автор: Рустем (---.megalan.ru) Дата:   01 Dec. 2005 11:44 Даю идею доказательства, если не хватит как нибудь распишу и вышлю. Повесим в каждой комнате лампочку и зажгём его в момент m, если R(m) содержит эту комнату иначе выключим. Классифицируем комнаты по типам. Тёмные, когда начиная с некоторого момента лампочки больше не загоряться, светлые - когда начиная с некоторого момента они зажигаются навсегда и другие. Для последних доказываем периодичность - они зажигаются только в моменты, когда m=m0(mod ni), поэтому их лучше назвать периодическими. Для первых двух типов доказываем, что до момента окончательного включения или выключения проходит не более квадратичное от n время. Для каждого периода с периодом n0 имеется не менее n0 лампочек с таким периодом. Соответственно они дают состояния в количестве НОК периодов. Светлые и тёмные комнаты к общему числу состояний могут дать вклад только в виде суммы, а периодические в лучшем случае произведение. Имея сумму лампочек n оценивается возможное количество суммы по светлым и тёмным и произведение по периодическим. Формула с M(n) дает максимальное количество кажется с n=26. В оценке M(n) возможно я ошибся в коэффициенте при вычислениях в уме, поэтому приведу их здесь. Из p(1)+...+p(k)~n следует k^2lnk~2n отсюда k~sqrt(n),lnk~0.5lnn, следовательно k~2sqrt(n/lnn). Произведение p(1)*...*p(k)~exp(klnk)~exp(2sqrt(n/lnn)*0.5lnn)~exp(sqrt(nlnn)).

Ответить на сообщение

Re: Конечные автоматы

Автор: Рустем (---.megalan.ru) Дата:   01 Dec. 2005 12:19 Забыл сказать, что периодические тоже требуют времени стабилазации, т.е не с самого начало в моменты m0(mod ni) они зажигаются. Все времена стабилизации (включая и тёмные и светлые) дают вклад в виде добавки max времени стабилизации по всем комнатам.

Ответить на сообщение

Re: Конечные автоматы

Автор: Сергей Подзоров (---.math.nsc.ru) Дата:   12 Dec. 2005 15:06 >Надо подождать комментариев автора. А пока я понимаю так, что >надо придумать схему коридоров, при которой как можно больше >различных R(k) при k=0,1,2,..... Да, Гост все правильно понял.

Ответить на сообщение

Re: Конечные автоматы

Автор: Рустем (---.megalan.ru) Дата:   13 Dec. 2005 11:39 Упустил, то что длины независимых циклов для оптимального автомата являются степенями простых чисел (когда простые меньше некоторого числа, примерно равного sqrt(sqrt(n))). Соответственно алгоритм их выбора несколько усложняется. Асимптотическое поведение остается такой же. Формула относительно максимального количества состояний (n-1)^2+2 работает только при n меньше 24 за исключением n=20 и 21. Сама теория и выводы у меня заняло более 6 страниц. Желающим ознакомится я отправлю.

Ответить на сообщение

Список форумов  |  Новая тема  |  В корень форума  |  В корень темы  |  Режим дерева  |  Поиск
Ответить на сообщение
Ваше имя:
e-mail:
Тема: