Рекурентни уравнения

[Гост]

Задачи за рекурентни уравнения

[ptj]

Задача 2 :

Имаме [tex]n[/tex]-значна двоична дума, но не можем да различаваме символите [tex]0,1[/tex]. Тогава за да сме сигурни, че сме възпроизвели [tex]n[/tex] на брой 1-ци, ще трябва да възпроизведем всички възможни двоични думи, т.e. [tex]2^{n}-1[/tex] (началото не го броим).

За целта номерираме ключовете в началното положение с "0"-ли. След това ги превключваме в съответствие с двоичния запис на числата между [tex]1[/tex] и [tex]2^n-1[/tex].

...

[ptj]

2 задача:
Дължината на най-късата редица от щраквания очевидно е не по малка от броя ня двоичните думи, защото трябва да минем през всяка дума, т.е. поне [tex]2^n-1[/tex].

Обосновката за минималната редица от щраквания е доста сложна задача, излизаща извън пределите на дискретната математика, която реално е търсене на най-къса хамилтонова верига в граф.

4-та : При симетрични правила е невъзможно да се получи несиметрична матрица.

[Гост]

За задача 4: трябва да се докаже, че е симетрична

[ptj]

2 задача:
Дължината на най-късата редица от щраквания очевидно е не по малка от броя ня двоичните думи, защото трябва да минем през всяка дума, т.е. поне [tex]2^n-1[/tex].

Обосновката за минималната редица от щраквания е доста сложна задача, излизаща извън пределите на дискретната математика, която реално е търсене на най-къса хамилтонова верига в граф.

Нещо повече- решението на горния проблем би било частен случай на задачата за търговския пътник, за която все още не се знае дали е решима за полиномиално време.

[drago]

2 задача:
Дължината на най-късата редица от щраквания очевидно е не по малка от броя ня двоичните думи, защото трябва да минем през всяка дума, т.е. поне [tex]2^n-1[/tex].

Обосновката за минималната редица от щраквания е доста сложна задача, излизаща извън пределите на дискретната математика, която реално е търсене на най-къса хамилтонова верига в граф.

Нещо повече- решението на горния проблем би било частен случай на задачата за търговския пътник, за която все още не се знае дали е решима за полиномиално време.

Няма как да излиза извън пределите на дискретната математика, щото това е задачата и за това дават 10т. според условието. Така, че трябва да светне една червена лампичка преди да пишеш тези неща. Това, че има път от $2^n-1$ ребра(щраквания) в този граф, в който две двоични думи са свързани, ако имат само една различна цифра, се доказва много лесно с индукция (по $n$).
Второ, това няма нищо общо с търговския пътник, която е наистина $NP$ пълна задача, щото там се иска алгоритъм, който като вход получава произволен (всеки) граф и траябва да намери път. Тук просто имаш един специфичен граф, в който пътя се построява лесно. Има разлика, нали?

[ptj]

О.К. Аз не успях да намеря път с дължина 7 при 3 двоични ключа и затова не търсих доказателства.
Мога ли да видя вашия пример за него?
Възможно ли е да публикувате също и доказателството (индукцията) за дължината на пътя в общия случай с [tex]k-[/tex]възможни състояния на ключовете?

[ptj]

Намерих решение, което на практика е хамилтонов цикъл.
[tex](000)->(001)->(011)->(111)->(101)->(100)->(110)->(010)[/tex]

Наистина доказателството за общия случай е елементарно.
1.)Записваме същата последователност като прибавяме по една нула отпред на всяка дума.
2.)При изчерпване на редицата я записваме в обратен ред като пред всяка дума записваме 1.

Пример:
[tex](0)->(1)[/tex]
[tex](00)->(01)->(11)->(10)[/tex]
[tex](000)->(001)->(011)->(010)->(110)->(111)->(101)->(100)[/tex]

Хубава задача! Извинавам се глупостите по-горе.

П.П. Може да бъде дадена като тест за интелигентност (работа) на доста високо ниво.

[drago]

...П.П. Може да бъде дадена като тест за интелигентност (работа) на доста високо ниво.

Демек, ставаме за министри или визираш още по-високо ниво!?

[ptj]

За министри подобни способности определено са вредни,
но за програмисти или трейдъри в престижна фирма са огромен плюс .