Регистрирайте сеРегистрирайте се

Двоични вектори


 
   Форум за математика Форуми -> Дискретната математика
Предишната тема :: Следващата тема  
Автор Съобщение
Nona
Напреднал


Регистриран на: 12 Sep 2006
Мнения: 477

Репутация: 234.7
гласове: 163

МнениеПуснато на: Sat Jan 10, 2009 8:19 pm    Заглавие: Двоични вектори

Rolling Eyes


zad.PNG
 Description:
 Големина на файла:  20.61 KB
 Видяна:  3204 пъти(s)

zad.PNG


Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Реклама







Пуснато на:     Заглавие: Реклама

Върнете се в началото
r2d2
VIP


Регистриран на: 28 Feb 2007
Мнения: 1936
Местожителство: in the galaxy (Far Far Away)
Репутация: 311.2Репутация: 311.2
гласове: 179

МнениеПуснато на: Sun Jan 11, 2009 1:40 pm    Заглавие:

Как да отгатнем какво е [tex]\nu (\alpha)[/tex] i B(n,k)?
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Nona
Напреднал


Регистриран на: 12 Sep 2006
Мнения: 477

Репутация: 234.7
гласове: 163

МнениеПуснато на: Sun Jan 11, 2009 2:38 pm    Заглавие:

[tex]\nu (\alpha)=\sum_{i=1}^n\alpha_i.2^{n-i}[/tex] - номер на вектора α.

Пример: [tex]\alpha=(0,1,1)\in J_2^3 \Rightarrow \nu (\alpha)=2^2.0+2^1.1+2^0.1=3.[/tex]

[tex]\omega(\alpha)=\sum_{i=1}^n\alpha_i[/tex] - тегло на вектор.

Пример: [tex]\alpha=(0,1,1)\in J_2^3 \Rightarrow \omega (\alpha)=2.[/tex]

[tex]B_k^n=\left{\alpha|\omega(\alpha)=k\right}[/tex] - k-ти слой на n-мерния булев куб.

[tex]n-k[/tex]-мерна стена (повърхнина) - множеството от всички вектори, в което k компонента са избрани и фиксирани.

n-мерен булев куб - граф с върхове n-мерните двоични вектори и ребра едномерните повърхнини.
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Nona
Напреднал


Регистриран на: 12 Sep 2006
Мнения: 477

Репутация: 234.7
гласове: 163

МнениеПуснато на: Mon Jan 12, 2009 11:04 pm    Заглавие:

[tex] \left( \begin{array} j \\ k \end{array} \right) - \left( \begin{array} i \\ k \end{array} \right) [/tex] Question
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
nikko1
Напреднал


Регистриран на: 23 Nov 2008
Мнения: 422

Репутация: 61.8
гласове: 36

МнениеПуснато на: Tue Jan 13, 2009 1:40 am    Заглавие:

Хмм.
Трудничка задача.
Добре значи трябва да разгледаме двоичните числа между [tex]2^i[/tex] и [tex]2^j.[/tex] Ще разгледам два случая.
I. [tex]k=1[/tex], тогава имаме [tex]j-i+1[/tex] двоични числа с тегло 1 (трябва да имаме само по една единица, но тогава те са степени на двойката и са [tex]2^i,\ 2^{i+1}, \dots, 2^{j}[/tex]
II. [tex]k\geq 2.[/tex] Ще използвам таблица и ще разделя числата в интервала [tex]2^i[/tex] и [tex]2^j[/tex] на групи след което ще преброя по колко двоични числа с тегло [tex]k[/tex] има във всяка от тях.
Първата група числа е между [tex]2^i[/tex] и [tex]2^{i+1}-1[/tex]. Всички те изглеждат така [tex]\begin{array}{lllllll}position&&i+1&i&i-1&\dots&0\\0&\dots&0&1&0&\dots&0\\0&\dots&0&1&0&\dots&1\\\dots&\dots&\dots&\dots&\dots&\dots&\dots\\0&\dots&0&1&1&\dots&1\end{array}[/tex]. Тук понеже в позиция i винаги имаме 1, то остава от станалите i позиции (да не забравим, че има и нулева) да изберем k-1 единици, което можем да направим по [tex]i\choose {k-1}[/tex] начина.
Аналогично за следващата група числа получаваме [tex]i+1\choose {k-1}[/tex] вектора с тегло k.
...
Накрая за последната група числа, които са между [tex]2^{j-1}[/tex] и [tex]2^{j}[/tex] (числото [tex]2^j[/tex] изключваме защото има само 1 единица, а тук [tex]k\geq 2[/tex]) получаваме [tex]j-1\choose {k-1}[/tex] вектора.
Сега остава да сумираме и окончателно получаваме [tex]\sum\limits_{s=i}^{j-1}{s\choose k-1}.[/tex]

P. S. Като смятаме по формулата не трябва да забравяме, че [tex]{n \choose k} = 0[/tex], ако [tex]k < 0[/tex] или [tex]k>n.[/tex]
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
2sxy4u
Начинаещ


Регистриран на: 17 May 2008
Мнения: 57

Репутация: 10.8
гласове: 3

МнениеПуснато на: Tue Jan 13, 2009 1:52 am    Заглавие:

Алелуя ! Very Happy
Стигнах до същия отговор , но ми се струваше толкова изродски и брутален , че проверявам от 1/2 час дали нямам грешка и като видях пост-а ти се израдвах като малко дете Very Happy Very Happy Very Happy
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
nikko1
Напреднал


Регистриран на: 23 Nov 2008
Мнения: 422

Репутация: 61.8
гласове: 36

МнениеПуснато на: Tue Jan 13, 2009 2:46 am    Заглавие:

2sxy4u написа:
Стигнах до същия отговор , но ми се струваше толкова изродски и брутален...

Еее, това е дискретна математика, тук винаги е доста брутално.
Нона, може ли един въпрос: От къде да тези задачи?
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Nona
Напреднал


Регистриран на: 12 Sep 2006
Мнения: 477

Репутация: 234.7
гласове: 163

МнениеПуснато на: Tue Jan 13, 2009 6:52 am    Заглавие:

Благодаря за решението Very Happy

nikko1 написа:
От къде да тези задачи?


От упражненията ни по Дискретни структури. (СУ, спец. КН)
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Nona
Напреднал


Регистриран на: 12 Sep 2006
Мнения: 477

Репутация: 234.7
гласове: 163

МнениеПуснато на: Tue Jan 13, 2009 7:42 pm    Заглавие:

От n- та до j-та позиция не трябва да има нули, за да е изпълнено условието, значи трябва да разположим k единици на j позиции: [tex]{j \choose k} .[/tex] От i-та до j-та позиция трябва да има поне една единица, т.е. неблагоприятен е само случаят, в който всички елементи от този интервал са нули, затова го изваждаме: [tex]{j\choose k} - {i\choose k}.[/tex]



С индукция може да се докаже, че [tex] \sum\limits_{s=i}^{j-1}{s\choose k-1} = {j\choose k} - {i\choose k}.[/tex] Laughing
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
2sxy4u
Начинаещ


Регистриран на: 17 May 2008
Мнения: 57

Репутация: 10.8
гласове: 3

МнениеПуснато на: Tue Jan 13, 2009 10:14 pm    Заглавие:

E tova trqbva da e "Evala" ... Smile
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
nikko1
Напреднал


Регистриран на: 23 Nov 2008
Мнения: 422

Репутация: 61.8
гласове: 36

МнениеПуснато на: Tue Jan 13, 2009 10:27 pm    Заглавие:

Права си, но все пак твоята формула не е вярна при [tex]k=1[/tex].
Ето как може да се докаже, че двете формули са равносилни при [tex]k\geq2.[/tex]
Първо ще докажа, че [tex]{{n+1}\choose k}-{n\choose k}={n\choose{k-1}}.[/tex]
[tex]{{n+1}\choose k}-{n\choose k}=\frac{(n+1)!}{k!(n-k+1)!}-\frac{n!}{k!(n-k)!}=\frac{n!}{k!(n-k)!}\left(\frac{n+1}{n-k+1}-1\right)=\frac{n!}{\not{k}!(n-k)!}\frac{\not{n}+\not{1}-\not{n}+\not{k}-\not{1}}{n-k+1}=\frac{n!}{(k-1)!(n-k+1)!}={n\choose{k-1}}[/tex]
Сега разглеждам e равенствата
[tex]{j\choose k}-{j-1\choose k}={j-1\choose k-1},[/tex]
[tex]{{j-1}\choose k}-{{j-2}\choose k}={j-2\choose k-1},[/tex]
...
[tex]{{i+1}\choose k}-{{i}\choose k}={i\choose k-1}.[/tex] Събираме ги и получаваме
[tex]{j\choose k}-{i\choose k}=\sum\limits_{s=i}^{j-1}{s\choose {k-1}}.[/tex]
Върнете се в началото
Вижте профила на потребителя Изпратете лично съобщение
Покажи мнения от преди:   
   Форум за математика Форуми -> Дискретната математика Часовете са според зоната GMT + 2 Часа
Страница 1 от 1

 
Идете на:  
Не Можете да пускате нови теми
Не Можете да отговаряте на темите
Не Можете да променяте съобщенията си
Не Можете да изтривате съобщенията си
Не Можете да гласувате в анкети
You cannot attach files in this forum
Може да сваляте файлове от този форум
Copyright © 2005-2021 math10.com.