Задачи с экзамена по дискретной математики МГУ
и что теперь все задачи с семинаров вываливать? это несерьезно и нереально
зато прикольно 
семинары у меня есть
написал бы что-н. с экзамена...
не будем флудить!
написал бы что-н. с экзамена...
не будем флудить!
Только имхо чтобы такой проект был действительно полезен, нужно где-нибудь складывать и решения к ним. И еще желательно все в виде, пригодном для правки и печати, типа теха какого-нибудь
И конечно, чтобы это сохранилось для будущих поколений...
Это будет лучше обычных задачников (в принципе они же существуют? ибо задачи скорее всего более актуальные (может кстати стоит указывать конкретный источник). Впрочем, сначала можно и не пытаться их превзойти.
И конечно, чтобы это сохранилось для будущих поколений...
Это будет лучше обычных задачников (в принципе они же существуют? ибо задачи скорее всего более актуальные (может кстати стоит указывать конкретный источник). Впрочем, сначала можно и не пытаться их превзойти.
вторая задача решается с помощью бинома и комплексных чисел?
Предложение хорошее, только кто этим будет заниматься? В этом треде я рассчитывал на людей, у которых скоро экзамен, с рассчетом, что им будет интересно узнать задачи с реального экзамена, а тем, кто может достать задачи, будет не влом помочь своим товарищам и запостить задачки сюда. Лично мне не сложно постить их в техе (вернее, в близком к теху варианте тем более как их записать текстом иначе - не ясно. Тому кто захочет заняться сбором задач, нужно будет просто покопировать их, чуть подправив.
Вот, кстати, еще (источник один - с экзамена ):
f(x_1, ..., x_n) = x_1 x_2 + x_2 x_3 + ... + x_{n-1} x_n - булева ф-ия
На скольких наборах f = 1?
Вот, кстати, еще (источник один - с экзамена
):f(x_1, ..., x_n) = x_1 x_2 + x_2 x_3 + ... + x_{n-1} x_n - булева ф-ия
На скольких наборах f = 1?
>тем более как их записать текстом иначе - не ясно
вставлять картинку.
вставлять картинку.
да, нужно пробовать (1 + x)^n, где x пробегает корни третьей степени из 1
владимир, сможешь заняться этим?
как человек, наиболее шарящий в этом...
в принципе шару с тех-файлами с условиями и решениями держать могу у себя, комп могу держать почти всегда включенным
только вот с написанием решений помочь, к сожалению, не смогу, т.к. у самого еще ни одного зачета
как человек, наиболее шарящий в этом...
в принципе шару с тех-файлами с условиями и решениями держать могу у себя, комп могу держать почти всегда включенным
только вот с написанием решений помочь, к сожалению, не смогу, т.к. у самого еще ни одного зачета
Под источником я понимал группу(поток) и/или преподавателя.
А эту задачу можно решать так:
введем U_n и V_n - количество единиц соответственно при x_n=0
и при x_n=1.
тогда U_{n+1}=U_n+V_n
V_{n+1}=2^{n-1}-V_n+U_n
Почему такие рекуррентные соотношения: у нас есть функция
f_{n+1}(...)=f_n+x_n x_{n+1}.
Для U_{n+1}: x_{n+1}=0 и получаем f_{n+1}=f_n
Для V_{n+1}: f_{n+1}=f_n+x_n
x_n равному 0 соответствуют U_n наборов.
x_n равному 1 соответствуют 2^{n-1}-V_n наборов. ($f_{n+1}=1 \Leftrightarrow f_n=0$)
Теперь как решать: можно заметить, что собственные значения матрицы \pm\sqrt{2}
тогда $U_n=a2^n+2^{n/2}\left( b+(-1)^n c \right)$
аналогично $V_n=p2^n+2^{n/2}\left( q+(-1)^n r \right)$.
записывая рекуррентные соотношения, находим
(из u_{n+1} )
q=b(\sqrt{2}-1)
r=c(\sqrt{2}+1)
a=p
(из v_{n+1} )
2p=1/2-p+a \Rightarrow a=p=1/4
Теперь $b$ и $c$ находятся например из начальных условий U_2=0, V_2=1. Хотя наверно проще считать из U_2=0, U_3=1, но тогда не так очевидно совпадение с нужной последовательностью.
А эту задачу можно решать так:
введем U_n и V_n - количество единиц соответственно при x_n=0
и при x_n=1.
тогда U_{n+1}=U_n+V_n
V_{n+1}=2^{n-1}-V_n+U_n
Почему такие рекуррентные соотношения: у нас есть функция
f_{n+1}(...)=f_n+x_n x_{n+1}.
Для U_{n+1}: x_{n+1}=0 и получаем f_{n+1}=f_n
Для V_{n+1}: f_{n+1}=f_n+x_n
x_n равному 0 соответствуют U_n наборов.
x_n равному 1 соответствуют 2^{n-1}-V_n наборов. ($f_{n+1}=1 \Leftrightarrow f_n=0$)
Теперь как решать: можно заметить, что собственные значения матрицы \pm\sqrt{2}
тогда $U_n=a2^n+2^{n/2}\left( b+(-1)^n c \right)$
аналогично $V_n=p2^n+2^{n/2}\left( q+(-1)^n r \right)$.
записывая рекуррентные соотношения, находим
(из u_{n+1} )
q=b(\sqrt{2}-1)
r=c(\sqrt{2}+1)
a=p
(из v_{n+1} )
2p=1/2-p+a \Rightarrow a=p=1/4
Теперь $b$ и $c$ находятся например из начальных условий U_2=0, V_2=1. Хотя наверно проще считать из U_2=0, U_3=1, но тогда не так очевидно совпадение с нужной последовательностью.
С какого потока эти задачи?
Почему получаются такие рекуррентные соотношения?
спасибо, исправил
я тоже так решал (только рекурентность более кустарно разрешал)к сожалению, нет времени написать все решение задачи но идея такая:
1) ясно что прямоугольник состоит из блоков 1х1 и 1х3
2) каждый блок можно сформировать двумя способами из наших фигур
3) составляем линейную рекурентность на кол-во расстановок (g_n): 1-ый случай - самый левый блок 1х1, 2-ой случай - самый левый блок 1х3
g_n = 2 g_{n - 1} + 2 g_{n - 3}
думаю источник задач установить довольно трудно
2: какой поток - неважно, кафедра дискры сейчас у всех читает... а задачи из той большой пачки, из которой на экзамене выбирают
могу дать условия задач , которые были в прошлом году на экзаменах у первого потока (лектор Лупанов) , вообще типов задач было 7-8 . У второго потока были те же задачи + задачка на автоматы. Так что если кто будет постить! их приходите
Куда приходить-то?
Задача с экзамена, 2-й поток: Найти количество к-мерных граней n-мерного куба, проходящих через заданную вершину n-мерного куба и не проходящую через другую вершину.
2-ой поток, могут задать вопрос: привести пример нерегулярного события и доказать соответствующее утверждение.
Задача с экзамена, 2-й поток: Найти количество к-мерных граней n-мерного куба, проходящих через заданную вершину n-мерного куба и не проходящую через другую вершину.
2-ой поток, могут задать вопрос: привести пример нерегулярного события и доказать соответствующее утверждение.
Я выбрал из задач -а более или менее уникальные (кстати, действительно, очень много похожих, так что решайте, народ!). Вот они.
1) Исправить ошибку в слове 001110100101011 при условии, что для передачи информации использовался код Хэмминга
2) 1, ..., 2000. Сколько чисел делится на 2, 3, 5, 7?
3) регулярны ли события
а) (1(11)^*00(0)^*)*
б) {1^n2^m3^k0^n}
4) A = { f | f(x_1, ..., x_{2n-1} = 0, x_1 + .. + x_{2n-1} >= n }
найти max_{f \in A} L(f).
5) Найти кол-во ф-ий от $n$ переменных, существенно зависящих от всех $n$ переменных.
6) Положим |a| = \sum_{i=1}^n a_i 2^{i-1}.
A := { f | f(x) = f(y) при |x| = |y| (mod n^3) }
Оценить max_{f \in A} L(f).
7,8,9) см. задачи которые я постил
----
и еще задачу нашел:
f(x_1, ..., x_n) \in [ x -> y ], существенно зависит хотя бы от двух переменных.
Д-ть, что она принимает значение единица более чем на половине наборов.
1) Исправить ошибку в слове 001110100101011 при условии, что для передачи информации использовался код Хэмминга
2) 1, ..., 2000. Сколько чисел делится на 2, 3, 5, 7?
3) регулярны ли события
а) (1(11)^*00(0)^*)*
б) {1^n2^m3^k0^n}
4) A = { f | f(x_1, ..., x_{2n-1} = 0, x_1 + .. + x_{2n-1} >= n }
найти max_{f \in A} L(f).
5) Найти кол-во ф-ий от $n$ переменных, существенно зависящих от всех $n$ переменных.
6) Положим |a| = \sum_{i=1}^n a_i 2^{i-1}.
A := { f | f(x) = f(y) при |x| = |y| (mod n^3) }
Оценить max_{f \in A} L(f).
7,8,9) см. задачи которые я постил
----
и еще задачу нашел:
f(x_1, ..., x_n) \in [ x -> y ], существенно зависит хотя бы от двух переменных.
Д-ть, что она принимает значение единица более чем на половине наборов.
f(x_1, ..., x_n) \in [ x -> y ], существенно зависит хотя бы от двух переменных.
Д-ть, что она принимает значение единица более чем на половине наборов.
докажем индукцией по построению. Для функций вида x_i утверждение тривиально
Для функций вида F->G, ($F\rightarrow G$ где утверждение для G считается выполненным, то есть
либо G существенно зависит хотя бы от 2 переменных, и тогда конечно F->G выполняется более чем на половине наборов, потому что даже G там выполняется.
либо G существенно зависит от не более одной переменной, то есть G либо x, либо "не x", либо 0, либо 1.
Но 0 она не может быть, так как все функции данного класса сохраняют единицу.
Значит G дает 1 на хотя бы половине наборов. Но по условию F->G ей не равна, и кроме того F->G \ge G. Значит F->G >G, и принимает значение 1 на большем числе наборов, чем половина.
Д-ть, что она принимает значение единица более чем на половине наборов.
докажем индукцией по построению. Для функций вида x_i утверждение тривиально
Для функций вида F->G, ($F\rightarrow G$ где утверждение для G считается выполненным, то есть
либо G существенно зависит хотя бы от 2 переменных, и тогда конечно F->G выполняется более чем на половине наборов, потому что даже G там выполняется.
либо G существенно зависит от не более одной переменной, то есть G либо x, либо "не x", либо 0, либо 1.
Но 0 она не может быть, так как все функции данного класса сохраняют единицу.
Значит G дает 1 на хотя бы половине наборов. Но по условию F->G ей не равна, и кроме того F->G \ge G. Значит F->G >G, и принимает значение 1 на большем числе наборов, чем половина.
все так, кроме
(она не зависит от 2х переменных, проверять не надо, база другая)
я также решал, только учел, что "не $x$" быть не может (не лежит в классе и вспомнил про набор из одних нулей
Для функций вида x_i утверждение тривиально
(она не зависит от 2х переменных, проверять не надо, база другая)
я также решал, только учел, что "не $x$" быть не может (не лежит в классе и вспомнил про набор из одних нулей
задачи на элемент задержки запостите лучше - у нас их не было, но на экзамене их любят давать!
у нас тоже не было
что это такое? приведи пример
что это такое? приведи пример
($F\rightarrow G$)
Символы подобного рода не понятны
это тех
right arrow - стрелка вправо
к тому же это написано в скобках... поэтому можешь не обращать внимания
right arrow - стрелка вправо
к тому же это написано в скобках... поэтому можешь не обращать внимания
Тогда не понятны следующие вещи :
И какая же тогда база?
f(x_1, ..., x_n) \in [ x -> y ]
Но 0 она не может быть, так как все функции данного класса сохраняют единицу
F->G \ge G
F->G >G
И какая же тогда база?
Задача:
Оценить асимптотику кол-ва решений в целых числах уравнения x + 2y + 3z = n.
Оценить асимптотику кол-ва решений в целых числах уравнения x + 2y + 3z = n.
зайди, объясню
Куда зайти ? )
f(x_1, ..., x_n) \in [ x -> y ]
f лежит в классе, являющемся "замыканием функции следования". Я правда не помню на нашем потоке такого определения.
Но 0 она не может быть, так как все функции данного класса сохраняют единицу
То есть так как все функции на наборе (1,1 ...1) дают результат 1, то и любая построенная из них тоже даст 1 на таком наборе. А 0 равен 0 на наборе из одних единиц. Значит он в нашем классе не лежит.
(F->G) \ge G
(F->G) > G
сравнение функций - поэлементно. Если \ge, что означает >=, то просто на каждом наборе не меньше. Если > то кроме того еще на некотором наборе неравенство строгое. А вообще-то насчет базы - надо вспоминать определение операции [ ].
В общем, похоже мне не стоит особо писать решения, тем более, что задачи-то похоже многие уже решены. Может быть когда смогу записывать аккуратно...
to : можно более аккуратно сформулировать условие 4-й? (немного подправить, и немного поподробней)
f лежит в классе, являющемся "замыканием функции следования". Я правда не помню на нашем потоке такого определения.
Но 0 она не может быть, так как все функции данного класса сохраняют единицу
То есть так как все функции на наборе (1,1 ...1) дают результат 1, то и любая построенная из них тоже даст 1 на таком наборе. А 0 равен 0 на наборе из одних единиц. Значит он в нашем классе не лежит.
(F->G) \ge G
(F->G) > G
сравнение функций - поэлементно. Если \ge, что означает >=, то просто на каждом наборе не меньше. Если > то кроме того еще на некотором наборе неравенство строгое. А вообще-то насчет базы - надо вспоминать определение операции [ ].
В общем, похоже мне не стоит особо писать решения, тем более, что задачи-то похоже многие уже решены. Может быть когда смогу записывать аккуратно...
to : можно более аккуратно сформулировать условие 4-й? (немного подправить, и немного поподробней)
A - мн-во ф-ий f: f(x_1, ..., x_{2n-1}) = 0 на наборах, которые x_1 + .. + x_{2n-1} >= n
найти max_{f \in A} L(f где L(f) - минимальное кол-во элементов схемы, которыми можно реализовать f
(про L(f) - это мое мнение, у нас так обозначали; что до -а, то я не знаю, это ли имелось ввиду, подписано не было)
сорри, скобку пропустил
найти max_{f \in A} L(f где L(f) - минимальное кол-во элементов схемы, которыми можно реализовать f
(про L(f) - это мое мнение, у нас так обозначали; что до -а, то я не знаю, это ли имелось ввиду, подписано не было)
сорри, скобку пропустил
Теперь понятно )
Тогда я правильно понимаю, что точного ответа здесь нет, и это просто сводится к асимптотике для функций 2n-2 переменных,
с помощью сопоставления набору x_1,x_2 ...x_{2n-1}
набора x_1+x_{2n-1},x_2+x_{2n-1}, ... x_{2n-2}+x_{2n-1},
которое организуется за довольно малое число элементов?
с помощью сопоставления набору x_1,x_2 ...x_{2n-1}
набора x_1+x_{2n-1},x_2+x_{2n-1}, ... x_{2n-2}+x_{2n-1},
которое организуется за довольно малое число элементов?
я не понял твоих мыслей, а с задачей еще не разбирался. объясни, если не затруднит, подробней
про 5-ую: знаешь как решать НЕ методом вкл-выкл. а то не все любят суммы
про 5-ую: знаешь как решать НЕ методом вкл-выкл. а то не все любят суммы
ребята, я с вас просто тащусь!
а в более удобоваримом виде это появится?
а в более удобоваримом виде это появится?
я не понял твоих мыслей, а с задачей еще не разбирался. объясни, если не затруднит, подробнейИтак, можно реализовать функцию нашего класса $A$ если мы сделаем схему, которая на наборе с суммой $\ge n$ выдает $0$, а на наборе с суммой $\le n-1$ выдает сначала $2n-2$ промежуточных выхода, а затем результат вычисления функции $2n-2$ переменных, которая строится по такому правилу.
$f(x_1\dots x_{2n-1})\mapsto g(x_1 \dots x_{2n-2}$\\
где $g$ равна $ f(x_1, \dots, x_{2n-2},0)$ для суммы не большей n-1\\
и равна $f(\bar x_1, \dots, \bar x_{2n-2},1)$ для суммы не меньшей $n$.
В другую сторону это преобразование чуть проще:\\
$f(x_1 \dots x_{2n-1})=0$ для набора веса более $n-1$,\\
$f(x_1 \dots x_{2n-1})=g(x_1+x_{2n-1}, x_2+x_{2n-1}, \dots x_{2n-2}+x_{2n-1} )$ для набора веса не более $n-1$,\\
Таким образом на входы $g$ надо подать $n$ сумм по модулю $2$, которые вычисляются за $O(n)$ элементов.
максимальная сложность функции $g$ асимптотически известна.
Сложность сведения не более $O(n^2)$.
Оценка максимума снизу либо делается с помощью стандартной леммы через кол-во функций в нашем классе, либо обратным сведением функции $2n-2$ переменных к функции нашего класса (опять единственная реальная сложность в $L(\makebox{сведение}) $ - посчитать настоящую сумму $2n-2$ переменных и сравнить с числом $n-1$).
Нельзя сказать, чтобы попытка добавить картинку была очень удачной, но зато написанное выше уже компилируется в TeX'е, хотя понятно пожалуй далеко не каждому
-----------
про 5-ую: знаешь как решать НЕ методом вкл-выкл. а то не все любят суммы
но ответ то все равно наверно
$ 2^{2^n} -C_n^1 2^{2^{n-1}}+C_n^2 2^{2^{n-2}}- \dots + (-1)^n 2^{2^0} C_n^n$?
И казалось бы его не упростить, а тогда так или иначе что-то вроде сумм и метода вкл-искл нужно?
------------
Насчет второй: там имеется в виду кол-во делящихся на 2,3,5 или 7?
спасибо, хотя я не понял
(не понятно зачем $g$ нужна и, соответственно, как ее использовать потом)
а насчет картинки, то, мне кажется, нужно было сразу вставлять в пост (в ubb это тег image)
меня лично ломает компилировать под виндами, потом еще картинку делать, да и вставлять в форум не очень приятно
насчет второй - ошибочка - там одновренно НЕ делятся на 2, 3, 5, 7...
короче, на метод вкл-выкл
(не понятно зачем $g$ нужна и, соответственно, как ее использовать потом)
а насчет картинки, то, мне кажется, нужно было сразу вставлять в пост (в ubb это тег image)
меня лично ломает компилировать под виндами, потом еще картинку делать, да и вставлять в форум не очень приятно
насчет второй - ошибочка
- там одновренно НЕ делятся на 2, 3, 5, 7...короче, на метод вкл-выкл
итак, определяем по f функцию g как написано. Тогда получаем взаимно-однозначное соответствие между функциями класса A и всеми функциями от 2n-2 переменных.
Теперь покажем, что L(f)=L(g)+O(n^2).
Для этого
1) пусть есть схема для g.\\
тогда нужно:
а)подать ей на вход $x_i+x_{2n-1}$
б)взять в зависимости от $|x|$- которое считается за O(n^2) операций - либо значение на выходе схемы для $g$, либо 0 в качестве результата.
2)пусть есть схема для $f$. Тогда нужно аргументы для $g$ преобразовать в правильные аргументы для $f$ и это тоже делается за $O(n^2)$ операций.
Таким образом, с учетом того, что асимптотика для максимума $L$ в классе всех функций $2n-2$ переменных была получена на лекции (интересно, она равна в данном случае $2^{2n} /8n$? то получаем ответ, так как искомое число отличается от нее всего лишь на $O(n^2)$
В общем спрашивайте. Чем больше спрашивать, тем более подробным, простым, понятным и правильным будет решение (до разумного предела).
Теперь покажем, что L(f)=L(g)+O(n^2).
Для этого
1) пусть есть схема для g.\\
тогда нужно:
а)подать ей на вход $x_i+x_{2n-1}$
б)взять в зависимости от $|x|$- которое считается за O(n^2) операций - либо значение на выходе схемы для $g$, либо 0 в качестве результата.
2)пусть есть схема для $f$. Тогда нужно аргументы для $g$ преобразовать в правильные аргументы для $f$ и это тоже делается за $O(n^2)$ операций.
Таким образом, с учетом того, что асимптотика для максимума $L$ в классе всех функций $2n-2$ переменных была получена на лекции (интересно, она равна в данном случае $2^{2n} /8n$? то получаем ответ, так как искомое число отличается от нее всего лишь на $O(n^2)$
В общем спрашивайте. Чем больше спрашивать, тем более подробным, простым, понятным и правильным будет решение (до разумного предела).
хм
так значительно понятнее, но единственное я не понял:
связано это видимо с тем, что не ясно, как ты строишь обратную функцию (определение $g$ понятно)
и еще: у нас на лекциях $L$ не вводилось, было только на семинарах, поэтому я не знал той оценки
значит все-таки есть небольшое отличие между курсами 1-го и 2-го потока
так значительно понятнее, но единственное я не понял:
взаимно-однозначное соответствие между функциями класса A и всеми функциями от 2n-2 переменных
связано это видимо с тем, что не ясно, как ты строишь обратную функцию (определение $g$ понятно)
и еще: у нас на лекциях $L$ не вводилось, было только на семинарах, поэтому я не знал той оценки
значит все-таки есть небольшое отличие между курсами 1-го и 2-го потока
так значительно понятнее, но единственное я не понял:Это следует из того, что {всем наборам, на которых функция класса A может быть ненулевой} взаимно однозначно сопоставлены {все наборы из 2n-2 переменных}. Отображения наборов расписаны в обе стороны. (Отображения функций сейчас вроде бы тоже, правда "на языке схем")
взаимно-однозначное соответствие между функциями класса A и всеми функциями от 2n-2 переменных
на которых функция класса A может быть ненулевой
может я чего-то не понял, но ф-ия всегда 0 если лежит в А (по опр. А)
у меня конкретный вопрос как ты писал обр. преобразования, я вообще не понял:
В другую сторону это преобразование чуть проще:\\
$f(x_1 \dots x_{2n-1})=0$ для набора веса более $n-1$,\\
$f(x_1 \dots x_{2n-1})=g(x_1+x_{2n-1}, x_2+x_{2n-1}, \dots x_{2n-2}+x_{2n-1} )$ для набора веса не более $n-1$
Чувствуется скоро эта ветка погибнет. Если еще не .
Тогда по определению класса A
f(1,1,1)=f(1,1,0)=f(1,0,1)=f(0,1,1)=0,
что и написано в первой строчке. (да, на всякий случай, вес - это у меня |x|, сумма x_i как целых чисел)
На остальных наборах (вторая строчка)
f(x_1,x_2,x_3):=g(x_1+x_3,x_2+x_3)
f(0,0,0)=g(0+0,0+0)=g(0,0)
f(1,0,0)=g(1+0,0+0)=g(1,0)
f(0,1,0)=g(0,1)
f(0,0,1)=g(1,1)
.В другую сторону это преобразование чуть проще:\\Привожу конкретный пример: n=2.
$f(x_1 \dots x_{2n-1})=0$ для набора веса более $n-1$,\\
$f(x_1 \dots x_{2n-1})=g(x_1+x_{2n-1}, x_2+x_{2n-1}, \dots x_{2n-2}+x_{2n-1} )$ для набора веса не более $n-1$
Тогда по определению класса A
f(1,1,1)=f(1,1,0)=f(1,0,1)=f(0,1,1)=0,
что и написано в первой строчке. (да, на всякий случай, вес - это у меня |x|, сумма x_i как целых чисел)
На остальных наборах (вторая строчка)
f(x_1,x_2,x_3):=g(x_1+x_3,x_2+x_3)
f(0,0,0)=g(0+0,0+0)=g(0,0)
f(1,0,0)=g(1+0,0+0)=g(1,0)
f(0,1,0)=g(0,1)
f(0,0,1)=g(1,1)
все, до меня дошло!
grand thnx
Ну, завтра 8-ая группа сдает, будут еще задачи, и я их сюда буду постить.
Может показаться, что только мне все это и надо, но я знаю точно, что еще четверым моим знакомым эта ветка нужна.
Не все ведь, кто читает задачи, спешит здесь отметиться (и правильно, чтоб flood не разводить!).
Надеюсь, что это нужно большему количеству людей, чем многие думают.
grand thnx
Чувствуется скоро эта ветка погибнет
Ну, завтра 8-ая группа сдает, будут еще задачи, и я их сюда буду постить.
Может показаться, что только мне все это и надо, но я знаю точно, что еще четверым моим знакомым эта ветка нужна.
Не все ведь, кто читает задачи, спешит здесь отметиться (и правильно, чтоб flood не разводить!).
Надеюсь, что это нужно большему количеству людей, чем многие думают.
Оценить асимптотику кол-ва решений в целых числах уравнения x + 2y + 3z = n.
кто-нибудь объяснит в чем дело?
разве их не бесконечно много для любого n? :
(x, y, z) = (n - 2t, t, 0) - решения
м.б. в натуральных?
стопудово
это ты на что ответил? на "натуральных" или на "в чем дело"
да, требуется найти решение на множестве натуральных чисел!
кто-нибудь решал?
у меня получилось n^2 / 8
интересно сравнить ответ
у меня получилось n^2 / 8
интересно сравнить ответ
м-да, оказалось не правильно...
вот правильное решение -а (выражаю ему благодарность):
Найдем число решений уравнения $x+2y+3z=n$ в натуральных числах.
Для этого достаточно найти число пар $(y,z)$ таких, что $2y+3z<n$.
Это соответствует нахождению следующей суммы по $y$:
$$\sum_{y=1}^{[n/2]} [(n-2y)/3]$$
Если $n=2k$ или $n=2k+1$, то получаем соответственно
$$\sum_{y=1}^k [(n-2y)/3].$$
Сумма дробных частей $k/2+O(1)$, \\
сумма без целых частей $(nk-k(k+1/3$.
Асимптотика при $n\rightarrow \infty$ получается $n^2/12$.
(для получения точного выражения можно перебрать все остатки при делении на 6, и получить для каждого точное значение суммы).
\medskip
\begin{center} {Альтернативный метод решения (через производящие функции). \end{center}
Количество решений равенства -- это коэффициэнты в произведении
$$(t+t^2+t^3+\dotst^2+t^4+t^6+\dotst^3+t^6+t^9+\dots)$$
(первый множитель соответствует $x$, второй - $2y$, третий - $3z$).
Тогда Функция можем быть свернута к виду
$$\frac{t^6}{(1-t1-t^21-t^3)}$$
она раскладывается в сумму $\sum a_i/(t-\alpha_i) +b/(1-t)^2+k/(1-t)^3 - 1$.
первым 2 слагаемым отвечают выражения вида $O(n)$. Третьему -- $k C_{n+2}^2=kn^2/2+O(n)$.
Найдем $k$, умножив функцию на $(1-t)^3$ и подставив $t=1$. получим $1/(2\cdot 3)=0+0+k$, $k=1/6$.
вот правильное решение -а (выражаю ему благодарность):
Найдем число решений уравнения $x+2y+3z=n$ в натуральных числах.
Для этого достаточно найти число пар $(y,z)$ таких, что $2y+3z<n$.
Это соответствует нахождению следующей суммы по $y$:
$$\sum_{y=1}^{[n/2]} [(n-2y)/3]$$
Если $n=2k$ или $n=2k+1$, то получаем соответственно
$$\sum_{y=1}^k [(n-2y)/3].$$
Сумма дробных частей $k/2+O(1)$, \\
сумма без целых частей $(nk-k(k+1/3$.
Асимптотика при $n\rightarrow \infty$ получается $n^2/12$.
(для получения точного выражения можно перебрать все остатки при делении на 6, и получить для каждого точное значение суммы).
\medskip
\begin{center} {Альтернативный метод решения (через производящие функции). \end{center}
Количество решений равенства -- это коэффициэнты в произведении
$$(t+t^2+t^3+\dotst^2+t^4+t^6+\dotst^3+t^6+t^9+\dots)$$
(первый множитель соответствует $x$, второй - $2y$, третий - $3z$).
Тогда Функция можем быть свернута к виду
$$\frac{t^6}{(1-t1-t^21-t^3)}$$
она раскладывается в сумму $\sum a_i/(t-\alpha_i) +b/(1-t)^2+k/(1-t)^3 - 1$.
первым 2 слагаемым отвечают выражения вида $O(n)$. Третьему -- $k C_{n+2}^2=kn^2/2+O(n)$.
Найдем $k$, умножив функцию на $(1-t)^3$ и подставив $t=1$. получим $1/(2\cdot 3)=0+0+k$, $k=1/6$.
вот такая задачка:
доказать, что любой граф допускает такую геометрическую реализацию в |R3 (евклидово 3-х мерное что рёбрам отвечают прямолинейные отрезки. (граф без петель и кратных рёбер !)
подсказка: Вершины расположить на поверхности цилинра, и по индукции.
доказать, что любой граф допускает такую геометрическую реализацию в |R3 (евклидово 3-х мерное что рёбрам отвечают прямолинейные отрезки. (граф без петель и кратных рёбер !)
подсказка: Вершины расположить на поверхности цилинра, и по индукции.
А вот еще задачки:
1. Пусть |a| = sum( a*2^(n-1) ) (сумма по i от 0 до n). f(x)=f(y если |x|=|y| (mod n^3). Множество A состоит из таких фукций. Оценить max L(f) по f из А.
2. f(x_1,...,x_3n). Функции симметричны относительно x_i, x_(i+n) и x_(i+2n). Оценить max L(f).
Вроде такие условия
1. Пусть |a| = sum( a*2^(n-1) ) (сумма по i от 0 до n). f(x)=f(y если |x|=|y| (mod n^3). Множество A состоит из таких фукций. Оценить max L(f) по f из А.
2. f(x_1,...,x_3n). Функции симметричны относительно x_i, x_(i+n) и x_(i+2n). Оценить max L(f).
Вроде такие условия
а ты сдал ему?
Вот моя задачка:
Даны алфавиты вх. A={a_1, ..., a_r}, вых. B={b_1, ..., b_q}. Требуется найти в каких пределах может меняться длина кодовых слов при оптимальном кодировании.
Ответ: от 1 до [ r / (q - 1) ]. (рассм. вероятности p_1 >> p_2 >> ...)
Вот задачка жены:
Найти сложность схемы, позволяющей совместную реализацию системы {x~y, x->y}, в базисе {конъюнкция, дизъюнкция, отрицание}
Ответ: 6.
Даны алфавиты вх. A={a_1, ..., a_r}, вых. B={b_1, ..., b_q}. Требуется найти в каких пределах может меняться длина кодовых слов при оптимальном кодировании.
Ответ: от 1 до [ r / (q - 1) ]. (рассм. вероятности p_1 >> p_2 >> ...)
Вот задачка жены:
Найти сложность схемы, позволяющей совместную реализацию системы {x~y, x->y}, в базисе {конъюнкция, дизъюнкция, отрицание}
Ответ: 6.
нет
еще задачки:
1.пусть А - множество всех булевых функций f(x_1, ..., x_n, y_1, ..., y_n симметричных относительно пар переменных x_i и y_i, i= 1, ..., n. оценить maxL(f максимум по f из А
2. найти количество n-разрядных десятичных чисел, в которых нет двух рядом стоящих четных цифр
3. найти среднее расстояние между ребрами в n-мерном булевом кубе
еще задачки:
1.пусть А - множество всех булевых функций f(x_1, ..., x_n, y_1, ..., y_n симметричных относительно пар переменных x_i и y_i, i= 1, ..., n. оценить maxL(f максимум по f из А
2. найти количество n-разрядных десятичных чисел, в которых нет двух рядом стоящих четных цифр
3. найти среднее расстояние между ребрами в n-мерном булевом кубе
и еще:(первый поток)
1)Fi:[0,1]^n->[0,1]^n
сумма по i от 1 до n Fi(x) равна 2 для любого х
найти максимальную сложность L(F)
2)f(х1,х2,х3n) ; f симметрична относительно xi,x(i+nx(i+2n)
оценить maxL(f) по f принадлежащим А(множество булевых функций с данными условиями)
3)!
a,b принадлежат {0,1}^n
Найти число к-мерных граней ,проходящих через а и не проходящих через b
4)!
код длины n=2k с мин. расст. k
Д-ть,что в нем не более 2n слов
Пожалуйста!
1)Fi:[0,1]^n->[0,1]^n
сумма по i от 1 до n Fi(x) равна 2 для любого х
найти максимальную сложность L(F)
2)f(х1,х2,х3n) ; f симметрична относительно xi,x(i+nx(i+2n)
оценить maxL(f) по f принадлежащим А(множество булевых функций с данными условиями)
3)!
a,b принадлежат {0,1}^n
Найти число к-мерных граней ,проходящих через а и не проходящих через b
4)!
код длины n=2k с мин. расст. k
Д-ть,что в нем не более 2n слов
Пожалуйста!
нужно посчитать кол-во граней через a минус кол-во граней через a&b
первое считатется просто C_n^k, а второе:
c := a + b = a - b
m = || c ||
т.е. нужно выбрать n - k нулей из n - m нулей = C_{n-m}^{n-k}
первое считатется просто C_n^k, а второе:
c := a + b = a - b
m = || c ||
т.е. нужно выбрать n - k нулей из n - m нулей = C_{n-m}^{n-k}
Спасибо! на самом деле очень интересуют первые две!
в каком базиcе первые две задачи?
(кстати, если для тебя больше важны первые две, почему же у 3-ей больше всего '!'?")
(кстати, если для тебя больше важны первые две, почему же у 3-ей больше всего '!'?")
и еще: во второй имеется ввиду фикс. i или i = 1 .. n ?
Спасибо за задачи. Все в тех перевел и компильнул. Правда, замучился $-ы расставлять. Решальщики, расставляйте больше $-ов.
может качнешь в форум (как .jpg) архивчик с правленными задачками? всем (кто в курсе, что такое тех) сделал бы доброе дело!
вообще тут народ вроде собирался что-то подобное организовать, но что-то все затихло...
вообще тут народ вроде собирался что-то подобное организовать, но что-то все затихло...
а как у тебя комп называется?
Я не знаю как. Над текстом надо, конечно, еще работать, но найти его можно на \\wc\Задачи по дискре. Я просто перевел все, что зедсь было написано в tex, dvi и pdf. Может еще попробую на досуге превратить это в связный текст. Пока влом.
Архивируешь. Переименовываешь в *.jpg. Далее, при составлении сообщения есть ссылка upload - позволяет загрузить на сервер файл с расширением jpg. После загрузки тебе дают ссылку, и ты постишь ее с помощью "URL" в таблице UBBCode (ну, или просто вставляешь в пост).
Тогда какой-нить бот может скачать этот файл и разархивировать его (только ты должен указать архиватор).
А на \\wc нужно включить гостя с пустым паролем или сказать пароль. Я не смог зайти.
Тогда какой-нить бот может скачать этот файл и разархивировать его (только ты должен указать архиватор).
А на \\wc нужно включить гостя с пустым паролем или сказать пароль. Я не смог зайти.
На wc можно зайти под User. Пароль 1.
i Фиксированное..
Базис: конъюнкция,дизъюнкция и отрицание...
L(f)-это минимальное число оперций в схеме реализующей f
Остались неясны только задачи такого типа(со сложностью)! Помогите разобраться!
Базис: конъюнкция,дизъюнкция и отрицание...
L(f)-это минимальное число оперций в схеме реализующей f
Остались неясны только задачи такого типа(со сложностью)! Помогите разобраться!
Это было to
я что-то подумал над второй - сходу не получается...
странно, что i фикс., так как можно было сказать, что она симметрична по первым трем переменным и не заморачиваться с 3n..
я со второго потока, у нас на лекции не было L(f на семинарах мы мало затронули эту тему
вот мой совет: напиши -у в приват, он разбирается в этом типе задач (да и вообще во многих, международник все-таки)
попроси его заглянуть в тему, он тебе поможет
и запости сюда решение - мне тоже интересно!
странно, что i фикс., так как можно было сказать, что она симметрична по первым трем переменным и не заморачиваться с 3n..
я со второго потока, у нас на лекции не было L(f на семинарах мы мало затронули эту тему
вот мой совет: напиши -у в приват, он разбирается в этом типе задач (да и вообще во многих, международник все-таки)
попроси его заглянуть в тему, он тебе поможет
и запости сюда решение - мне тоже интересно!
up
Тут три файла (Задачи с экзаменов по дискре): тех, dvi и pdf -
Заархвировано Winrar'ом.
Заархвировано Winrar'ом.
клево, теперь из инета люди смогут глядеть
правда, там еще для хорошей читаемости нужно править, но кому надо, тот разберется
ты молодец, потому что не все знают, что такое тех
2all: ну что, кто-нибудь написал в приват Дремову?
правда, там еще для хорошей читаемости нужно править, но кому надо, тот разберется
ты молодец, потому что не все знают, что такое тех
2all: ну что, кто-нибудь написал в приват Дремову?
ий поток. Тема Графы.
Дерево имеет К концевых вершин. Степень каждой вершина не более 3 (понимать следует как, инцидентность не более 3 ребрам). Доказать, что существует цепь длины не менее logk (по основанию 2-йки).
Надеюсь кому-нибудь пригодится.
Дерево имеет К концевых вершин. Степень каждой вершина не более 3 (понимать следует как, инцидентность не более 3 ребрам). Доказать, что существует цепь длины не менее logk (по основанию 2-йки).
Надеюсь кому-нибудь пригодится.
А у тебя решение есть?
пароль 1 не работает
он выложил rar архив с расширением jpg (см. выше ссылку - его пост)
пусть $A$ - множество всех булевых функций $f(x_1, ..., x_n, y_1, ..., y_n)$, симметричных относительно пар переменных $x_i$ и $y_i$, $i= 1, ..., n$. оценить $maxL(f)$, максимум по $f$ из $А$
Попробую написать решение с получением ответа в виде эквивалентности. Замечу, что для ответа в виде
$c_13^n/n \le maxL \le c_2 3^n/n$ таких сложностей не надо.
Хотя фактически это будет лишь реализация схемы, данной на лекции в случае максимальной сложности функций инвариантых классов, но зато теперь я лучше понимаю то доказательство.
Во-первых, количество функций в нашем множестве есть $2^{3^n}$.
Это связано с тем, что каждой паре переменных соответсвуют 3 различных набора аргументов (симметричные не различаем)
Отсюда логично предположить, что $max L\sim 3^n/log_2{3^n}$
Оценка сверху делается с помощью следующей схемы:
Сначала сводим функции к функциям $n \log_2(3)$ аргументов
для этого переводим набор из $00$, $01=10$ и $11$
в целое число в троичной записи, которое далее записываем как двоичное. Эта часть имеет небольшую сложность (заведомо не более $n^C$). Впрочем - зато это единственное место, где в этой задаче надо думать, а не вспоминать, что было на лекции.
Теперь берём в полученном двоичном числе последние m разрядов и фиксируем. Тогда мы обязательно получаем функцию семейства $B$, см. ниже. И значит можем получить одну из $|Bl$ различных функций от не более, чем $1+k\log_2{3}-m$ переменных.
Они нумеруются наборами длины $l=[3^k/2^m]+1$
Так как у нас уже есть функция $f$, то такой номер мы получаем для каждого из возможных фиксирований последних аргументов. Но тогда это отображение можно представить в виде $l$ булевых функций, от $m$ аргументов каждая.
И сложность реализации этого набора функций даёт главный вклад -- $l\frac{2^m}{m}$.
Кроме того, каждую из функций $r=1+[k\log_2{3}]-m$ переменных
надо реализовать, на это уходит $|B| \frac{2^r}{r}$ элементов.
И кроме того по выходам всех этих функций надо получить ответ
В итоге схема выглядит так:
сначала наши x_i,y_i преобразовываются к двоичному слову длины $r+m$. Потом от его первых $r$ разядов вычисляются все функции из семейства $B$, равного 0 на словах больших $[3^k/2^m]$.
Далее от его последних разрядов вычисляются (зависящие от нужной нам f) $l$ функций $m$ переменных, вместе дающие номер.
И теперь по полученным не более, чем $l+|B|$ числам однозначно определена наша искомая функция $f$, потому что $l$ чисел задают, какое из $|B|$ надо брать.
----------------------------(вариант1)
Для реализации этого на лекции вводились еще промежуточные функции ($2^r$ функций от $l$ переменных, каждая из которых давала на заданном номере значение функции множества $B$ с этим номером).
Их сложность не более $2^{r+l}/l$. У них уже всего $2^r$ выходов, и какой из них брать определяется значением первых $r$ разрядов.
Значит теперь сложность получения ответа -- сложность одной функции и не более, чем
$\frac{2^{2^r+r}}{2^r+r}$
И суммарная сложность есть
$n^C+|B|2^r/r+l2^m/m+2^{r+l}/l+\frac{2^{r+2^r} }{r+2^r}$.
Теперь выбираем $m$ близко к $k\log_2{3}$, но не слишком;
например $[k\log_2{3}-ln{k}/2]$.
Тогда $l\sim 3^k/2^m$, $m\sim k\log_2{3}$, $|B|\le 2^l$, $l\le 2^{1+ln{k}/2}\le 2\sqrt{k}$, $r\le \ln{k}+2$
Первое слагаемое сразу мало. Остальные оцениваются из того, что в них есть только $2^{с\sqrt{k}}$, что существенно меньше $2^k$.
----------------(вариант 2)
Но вроде на самом деле можно выбор из $|B|$ вариантов осуществить и напрямую. Например, рассмотреть дизъюнкцию $|B|$ конъюнкций, каждого выхода $b(c_1 \dots c_r)$ с соответствующим ему индикатором $I_b$.
здесь если $t_1,t_2 \dots t_l$ выданный номер, а $e_1,e_2 \dots e_l$ номер функции $b$ то $I_b:=t_1^{e_1}\dots t_l^{e_l}$,
$t_i^0:=\overline{t_i}$, $t_i^1:=t_i$
Получаем сложность порядка $(2l+1)|B|$, что тоже существенно меньше основного слагаемого $l2^m/m$.
уфф.....
Теперь оценка в другую сторону.
Число функций $N$ от $n$ переменных, которые можно реализовать схемами сложности не более $h$ ограничено как $[B(n+h)]^(n+h+2)$
(впрочем $n+h+2$ можно заменить на $n+h$, но у нас на лекции было так)
Тогда если взять $h_0=(1-\varepsilon)3^n/log_2{3^n}$, то
получим для достаточно больших $n$ оценку
$$N<2^{3^n}$$
из которой следует, что не может сложность всех функций во множестве $A$ из $2^{3^n}$ элементов быть меньше $h_0$.
Таким образом, получаем искомое асимптотическое неравенство.
Замечу напоследок, что равенство с точностью до мультипликативной константы величине $3^n/n$ доказывается очень просто, сведением к функциям от $[n\log_2{3}]$ переменных -- или то же $+1$ для верхней оценки сложности. Но как это делается, я уже писал в другой задаче. Правда там сведение удавалось провести к одной и той же функции для верхней и нижней оценок, поэтому сразу получался ответ в виде "$\sim$".
Попробую написать решение с получением ответа в виде эквивалентности. Замечу, что для ответа в виде
$c_13^n/n \le maxL \le c_2 3^n/n$ таких сложностей не надо.
Хотя фактически это будет лишь реализация схемы, данной на лекции в случае максимальной сложности функций инвариантых классов, но зато теперь я лучше понимаю то доказательство.
Во-первых, количество функций в нашем множестве есть $2^{3^n}$.
Это связано с тем, что каждой паре переменных соответсвуют 3 различных набора аргументов (симметричные не различаем)
Отсюда логично предположить, что $max L\sim 3^n/log_2{3^n}$
Оценка сверху делается с помощью следующей схемы:
Сначала сводим функции к функциям $n \log_2(3)$ аргументов
для этого переводим набор из $00$, $01=10$ и $11$
в целое число в троичной записи, которое далее записываем как двоичное. Эта часть имеет небольшую сложность (заведомо не более $n^C$). Впрочем - зато это единственное место, где в этой задаче надо думать, а не вспоминать, что было на лекции.
Теперь берём в полученном двоичном числе последние m разрядов и фиксируем. Тогда мы обязательно получаем функцию семейства $B$, см. ниже. И значит можем получить одну из $|Bl$ различных функций от не более, чем $1+k\log_2{3}-m$ переменных.
Они нумеруются наборами длины $l=[3^k/2^m]+1$
Так как у нас уже есть функция $f$, то такой номер мы получаем для каждого из возможных фиксирований последних аргументов. Но тогда это отображение можно представить в виде $l$ булевых функций, от $m$ аргументов каждая.
И сложность реализации этого набора функций даёт главный вклад -- $l\frac{2^m}{m}$.
Кроме того, каждую из функций $r=1+[k\log_2{3}]-m$ переменных
надо реализовать, на это уходит $|B| \frac{2^r}{r}$ элементов.
И кроме того по выходам всех этих функций надо получить ответ
В итоге схема выглядит так:
сначала наши x_i,y_i преобразовываются к двоичному слову длины $r+m$. Потом от его первых $r$ разядов вычисляются все функции из семейства $B$, равного 0 на словах больших $[3^k/2^m]$.
Далее от его последних разрядов вычисляются (зависящие от нужной нам f) $l$ функций $m$ переменных, вместе дающие номер.
И теперь по полученным не более, чем $l+|B|$ числам однозначно определена наша искомая функция $f$, потому что $l$ чисел задают, какое из $|B|$ надо брать.
----------------------------(вариант1)
Для реализации этого на лекции вводились еще промежуточные функции ($2^r$ функций от $l$ переменных, каждая из которых давала на заданном номере значение функции множества $B$ с этим номером).
Их сложность не более $2^{r+l}/l$. У них уже всего $2^r$ выходов, и какой из них брать определяется значением первых $r$ разрядов.
Значит теперь сложность получения ответа -- сложность одной функции и не более, чем
$\frac{2^{2^r+r}}{2^r+r}$
И суммарная сложность есть
$n^C+|B|2^r/r+l2^m/m+2^{r+l}/l+\frac{2^{r+2^r} }{r+2^r}$.
Теперь выбираем $m$ близко к $k\log_2{3}$, но не слишком;
например $[k\log_2{3}-ln{k}/2]$.
Тогда $l\sim 3^k/2^m$, $m\sim k\log_2{3}$, $|B|\le 2^l$, $l\le 2^{1+ln{k}/2}\le 2\sqrt{k}$, $r\le \ln{k}+2$
Первое слагаемое сразу мало. Остальные оцениваются из того, что в них есть только $2^{с\sqrt{k}}$, что существенно меньше $2^k$.
----------------(вариант 2)
Но вроде на самом деле можно выбор из $|B|$ вариантов осуществить и напрямую. Например, рассмотреть дизъюнкцию $|B|$ конъюнкций, каждого выхода $b(c_1 \dots c_r)$ с соответствующим ему индикатором $I_b$.
здесь если $t_1,t_2 \dots t_l$ выданный номер, а $e_1,e_2 \dots e_l$ номер функции $b$ то $I_b:=t_1^{e_1}\dots t_l^{e_l}$,
$t_i^0:=\overline{t_i}$, $t_i^1:=t_i$
Получаем сложность порядка $(2l+1)|B|$, что тоже существенно меньше основного слагаемого $l2^m/m$.
уфф.....
Теперь оценка в другую сторону.
Число функций $N$ от $n$ переменных, которые можно реализовать схемами сложности не более $h$ ограничено как $[B(n+h)]^(n+h+2)$
(впрочем $n+h+2$ можно заменить на $n+h$, но у нас на лекции было так)
Тогда если взять $h_0=(1-\varepsilon)3^n/log_2{3^n}$, то
получим для достаточно больших $n$ оценку
$$N<2^{3^n}$$
из которой следует, что не может сложность всех функций во множестве $A$ из $2^{3^n}$ элементов быть меньше $h_0$.
Таким образом, получаем искомое асимптотическое неравенство.
Замечу напоследок, что равенство с точностью до мультипликативной константы величине $3^n/n$ доказывается очень просто, сведением к функциям от $[n\log_2{3}]$ переменных -- или то же $+1$ для верхней оценки сложности. Но как это делается, я уже писал в другой задаче. Правда там сведение удавалось провести к одной и той же функции для верхней и нижней оценок, поэтому сразу получался ответ в виде "$\sim$".
у меня появились решения еще части задач (которые здесь не разобраны но их легче объяснить, чем выкладывать, так Что в приват
Оригинально :
:так Что в приват
тогда $U_n=a2^n+2^{n/2}\left( b+(-1)^n c \right)$Почему? Откуда взялись a2^n и p2^n? Остальное ясно. Правильно я понимаю, что если свободные члены реккурентностей геометрические прогрессии, то одно из частных решений состоит из линейной комбинации этих же прогрессий?
аналогично $V_n=p2^n+2^{n/2}\left( q+(-1)^n r \right)$
Замечу напоследок, что равенство с точностью до мультипликативной константы величине $3^n/n$ доказывается очень просто, сведением к функциям от $[n\log_2{3}]$ переменных -- или то же $+1$ для верхней оценки сложности. Но как это делается, я уже писал в другой задаче. Правда там сведение удавалось провести к одной и той же функции для верхней и нижней оценок, поэтому сразу получался ответ в виде "$\sim$".
Извините, как вы думаете, человеку со второго потока, реально , не решить (какой уж там! а хотя бы понять решение подобных задач? В одном из решений упоминался вес схемы реализующий все функции от n переменных. Чему он равен и как это доказать? А кстати на каком потоке было так подробно рассказано про сложность булевых функций?
Что такое * в
3) регулярны ли события
а) (1(11)^*00(0)^*)*
б) {1^n2^m3^k0^n}
На первом потоке нам рассказывали про сложность. А "очень просто" -- это лишь по сравнению с тем, что написано в том сообщении выше.
У нас было 3 теоремы:
про сложность реализации функции n переменных формулой,
сложность реализации произвольной функции n переменных схемой из функциональных элементов;
И сложность реализации функции n переменных из инвариантного класса схемой
И вот первая теорема -- это совсем уже гроб. Но к счастью, в задачах это понятие редко используется в таком виде.
А то, что процитировано -- не решение. То же, что не процитировано -- это всего лишь довольно удачная попытка разобраться почему то, что нам рассказывали на лекции, является довольно естественным и общим методом оценки сложности.
Если есть вопросы -- по другому решению, там где происходит сведение к функции на 1 меньшего числа переменных -- то я готов пояснить. А если это просто жалобы на преподавателей - то что же, мне кажется они оправданы не более чем подобное поведение преподавателей.
Конкретный вопрос: вес схемы, реализующей все функции $n$ переменных. Он считается точно, и это тоже довольно распространённое рассуждение.
Во-первых, $n$ функций реализовывать не надо (это $x_1, x_2 \dots x_n$).
Покажем, что на каждую из остальных уходит ровно по одному функциональному элементу. Обозначим кол-во функций $N=2^{2^n}-n$.
Оценка $L\ge N$ -- следствие определения, так как на каждом элементе схемы мы получаем ровно одну функцию. Значит количество элементов не может быть меньше количества реализуемых функций. Исключение -- переменные, которые в сложность не включаются.
Оценка $L\le N$ получается из такой схемы:
сначала мы реализуем все функции сложности 1. На каждую тратим ровно по одному функциональному элементу.
Следующий шаг: реализуем функцию $f$ сложности 2. При этом так как в её схеме A сложности 2 на вход каждого элемента подаются функции сложности не более, чем 1 -- то все функции, нужные для нашей уже реализованы. И значит остаётся только добавить тот элемент схемы A, на выходе которого мы получаем $f$, дав ему нужные входы.
Таким образом, на каждую функцию сложности 2 мы потратили еще по 1 элементу.
Теперь для функций сложности 3 мы действуем совершенно аналогично: соединяем элемент с нужными функциями сложности не более 2.
Таким образом, каждую функцию мы получим, потратив не более одного элемента. Здесь даже не надо специально оговаривать случай, когда функций какой-то сложности нет -- это никак не повлияет на решение, просто очередной шаг тривиален. Единственное, что нужно -- это реализуемость каждой функции некоторой схемой минимальной сложности.
У нас было 3 теоремы:
про сложность реализации функции n переменных формулой,
сложность реализации произвольной функции n переменных схемой из функциональных элементов;
И сложность реализации функции n переменных из инвариантного класса схемой
И вот первая теорема -- это совсем уже гроб. Но к счастью, в задачах это понятие редко используется в таком виде.
А то, что процитировано -- не решение. То же, что не процитировано -- это всего лишь довольно удачная попытка разобраться почему то, что нам рассказывали на лекции, является довольно естественным и общим методом оценки сложности.
Если есть вопросы -- по другому решению, там где происходит сведение к функции на 1 меньшего числа переменных -- то я готов пояснить. А если это просто жалобы на преподавателей - то что же, мне кажется они оправданы не более чем подобное поведение преподавателей.
Конкретный вопрос: вес схемы, реализующей все функции $n$ переменных. Он считается точно, и это тоже довольно распространённое рассуждение.
Во-первых, $n$ функций реализовывать не надо (это $x_1, x_2 \dots x_n$).
Покажем, что на каждую из остальных уходит ровно по одному функциональному элементу. Обозначим кол-во функций $N=2^{2^n}-n$.
Оценка $L\ge N$ -- следствие определения, так как на каждом элементе схемы мы получаем ровно одну функцию. Значит количество элементов не может быть меньше количества реализуемых функций. Исключение -- переменные, которые в сложность не включаются.
Оценка $L\le N$ получается из такой схемы:
сначала мы реализуем все функции сложности 1. На каждую тратим ровно по одному функциональному элементу.
Следующий шаг: реализуем функцию $f$ сложности 2. При этом так как в её схеме A сложности 2 на вход каждого элемента подаются функции сложности не более, чем 1 -- то все функции, нужные для нашей уже реализованы. И значит остаётся только добавить тот элемент схемы A, на выходе которого мы получаем $f$, дав ему нужные входы.
Таким образом, на каждую функцию сложности 2 мы потратили еще по 1 элементу.
Теперь для функций сложности 3 мы действуем совершенно аналогично: соединяем элемент с нужными функциями сложности не более 2.
Таким образом, каждую функцию мы получим, потратив не более одного элемента. Здесь даже не надо специально оговаривать случай, когда функций какой-то сложности нет -- это никак не повлияет на решение, просто очередной шаг тривиален. Единственное, что нужно -- это реализуемость каждой функции некоторой схемой минимальной сложности.
Таким образом, с учетом того, что асимптотика для максимума $L$ в классе всех функций $2n-2$ переменных была получена на лекции (интересно, она равна в данном случае $2^{2n} /8n$? то получаем ответ, так как искомое число отличается от нее всего лишь на $O(n^2)$
В общем спрашивайте. Чем больше спрашивать, тем более подробным, простым, понятным и правильным будет решение (до разумного предела).
Я не правильно задал вопрос. Хотя спасибо за ответ. Интересно откуда взялось вот, что
$2^{2n} /8n$
Как это доказать, хотя бы примерно. И какие еще асимптотики были у вас на лекции/семинаре ?
Как я понимаю ответ задачи таков: $2^{2n} /8n+O(n^2)$?
про сложность реализации функции n переменных формулой,
сложность реализации произвольной функции n переменных схемой из функциональных элементов;
И сложность реализации функции n переменных из инвариантного класса схемой
Как я понимаю, можно пользоваться этими теоремами на экзамене... Эх, если бы знать, как они формулируются
сложность формулы $L(\Phi)$ -- это количество входящих в неё символов переменных
Сложность схемы -- это количество входящих в неё функциональных элементов
Сложность функции $L(f)$ -- минимальная сложность ее реализации
Сложность $L_n$ -- это максимальная сложность функции $n$ переменных, $max_{f} L(f)$
Тогда
для формул $L_n\sim \frac{2^n}{\log_2 n}$ ($\approx$т. Лупанова)
для схем $L_n\sim \frac{2^n}{n}$
А для инвариантных классов нужны ещё определения. А вообще - в учебниках это должно быть. В том же Яблонском сейчас посмотрел - теорема про схемы есть на 361й странице.
Сложность схемы -- это количество входящих в неё функциональных элементов
Сложность функции $L(f)$ -- минимальная сложность ее реализации
Сложность $L_n$ -- это максимальная сложность функции $n$ переменных, $max_{f} L(f)$
Тогда
для формул $L_n\sim \frac{2^n}{\log_2 n}$ ($\approx$т. Лупанова)
для схем $L_n\sim \frac{2^n}{n}$
А для инвариантных классов нужны ещё определения. А вообще - в учебниках это должно быть. В том же Яблонском сейчас посмотрел - теорема про схемы есть на 361й странице.
правильно не
а $2^{2n} /8n+ o(2^{2n}/n)$
Как я понимаю ответ задачи таков: $2^{2n} /8n+O(n^2)$?
а $2^{2n} /8n+ o(2^{2n}/n)$
сам я точно не знаю, но видимо это значит, что группа может повторяться от нуля до сколь угодно большого кол-ва раз
т.е. в (1(11)^*00(0)^*)^* лежат пустое слово, 100, 111110000100111000 и пр.
т.е. в (1(11)^*00(0)^*)^* лежат пустое слово, 100, 111110000100111000 и пр.
те надо понимать событие - нерегулярное?
Нет, как раз события записанные на языке пункта a)
чуть ли не все регулярны.
чуть ли не все регулярны.
те (1^n 2^m 3^k 0^n) тоже регулярное, если да, то почему вкратце
хотя это уже пункт б)
хотя это уже пункт б)
нет, оно не регулярное. Дело в том, что там дважды встречается $n$ в показателе, и потому оно не есть просто 1(1)^*2(2)^*3(3)^*0(0)^*
Но конечно чтобы строго доказывать, надо сначала уточнить две вещи:
1)действительно ли показатели $k,m,n$ целые положительные
2)какое из определений регулярности мы хотим использовать
Но конечно чтобы строго доказывать, надо сначала уточнить две вещи:
1)действительно ли показатели $k,m,n$ целые положительные
2)какое из определений регулярности мы хотим использовать
Определение регулярности...
1. Настоящее определение: регулярное если его можно получить из элементарных с помощью теор.-множ. операций
2 Которое представляется в виде автомата (поправте, если я не так употребляю слова)
3 Еще можно приплести, которые получаются с пом. обобщенного источника
Используя последнее, по-моему, можно доказать
1. Настоящее определение: регулярное если его можно получить из элементарных с помощью теор.-множ. операций
2 Которое представляется в виде автомата (поправте, если я не так употребляю слова)
3 Еще можно приплести, которые получаются с пом. обобщенного источника
Используя последнее, по-моему, можно доказать
* обозначает то, что выражение в скобке можно повторять
то есть
(ABCA)* разрешает такие возможности: "", "ABCA", "ABCAABCA"...
то есть
(ABCA)* разрешает такие возможности: "", "ABCA", "ABCAABCA"...
все так, как написал
а) регулярное (по экв. опр. регулярности - строим обобщенный источник)
б) нерег. (так же, как в примере нерег. события из лекций второго потока)
а) регулярное (по экв. опр. регулярности - строим обобщенный источник)
б) нерег. (так же, как в примере нерег. события из лекций второго потока)
2 Которое представляется в виде автомата (поправте, если я не так употребляю слова)(может быть, правильнее "представляется автоматом"? И уж точно "поправьте"
3 Еще можно приплести, которые получаются с пом. обобщенного источника
Используя последнее, по-моему, можно доказать
)С помощью таких определений очень тяжело доказывать.
Там ещё была какая-то эквивалентность, что регулярно, если соответствуюшая детерминированная функция является ограниченно-детерминированной.
Вот такого рода определения пригодны, а "не существует автомат", или "не существует обобщённый источник" - едва ли нормально докажешь для конкретного случая, всё равно придётся использовать какой-то общий критерий
Что было на 2 потоке, я
не знаю. Меня только с некоторыми непонятными местами знакомилиСпасибо за то, что научил решать задачи на сложность. Мне попалась задача
И я получил пять на экзамене! Правда преподаватель (Кочергин) учел, что этой темы не было на лекциях и не заставил меня объяснять все строго. Например, как поделить одно число на другое с остатком спомощью схемы из функциональных элементов я не знаю.
Ура! Очередная ссесия сдана на отлично!
Пусть |a| = sum( a*2^(n-1) ) (сумма по i от 0 до n). f(x)=f(y если |x|=|y| (mod n^3). Множество A состоит из таких фукций. Оценить max L(f) по f из А.
И я получил пять на экзамене! Правда преподаватель (Кочергин) учел, что этой темы не было на лекциях и не заставил меня объяснять все строго. Например, как поделить одно число на другое с остатком спомощью схемы из функциональных элементов я не знаю.
Ура! Очередная ссесия сдана на отлично!
молодец!
и еще мне было приятно узнать, что я не зря начал эту тему
кстати, может в следующем году кому пригодится!
и еще мне было приятно узнать, что я не зря начал эту тему
кстати, может в следующем году кому пригодится!
Lika25
Народ!Есть предложение сваливать сюды задачки по дискре с экзамена 4 курса. Их у кафедры очень много, однако это поможет подготовиться...
Если КТО ЗНАЕТ какие-нибудь задачи с экзамена, НАПИШИТЕ ИХ, ПОЖАЛУЙСТА, СЮДА.
Вношу свой вклад:
1)
даны эти фигуры
сколькими способами из них можно составить это:
2) Д-ть: C_n^0 + C_n^3 + C_n^6 + ... = (2^n + 2cos(\pi n / 3 / 3
(кто не знает: _ - нижний индекс, ^ - верхний, \pi - пи)