2014 dxdy logo

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

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




 
 Ряды фурье для булевых функций
Сообщение02.06.2010, 14:25 
Аватара пользователя
В какой книжке можно про них прочитать?

 
 
 
 Re: Ряды фурье для булевых функций
Сообщение02.06.2010, 22:48 

(Оффтоп)

Сначала хотел написать, что это что-то из области фантастики, потому как трудно представить, как может булева функция удовлетворять условиям Дирихле. Но погуглив, на нескольких серьёзных сайтах нашел упоминания об этом, правда там всё больше темы конференций, а не литература.

 
 
 
 Re: Ряды фурье для булевых функций
Сообщение02.06.2010, 23:14 
Аватара пользователя
В книге "Булевы функции в теории кодирования и криптологии" активно используется преобразование Фурье булевых функций, но на основах авторы подробно не останавливаются.

Есть обзор http://www.cs.cmu.edu/~odonnell/papers/ ... survey.pdf

Есть еще хорошее введение в http://cosec.bit.uni-bonn.de/fileadmin/ ... /tof05.pdf , там рассматривается общий случай функций над конечным полем, главы по булевым функциям есть.

 
 
 
 Re: Ряды фурье для булевых функций
Сообщение03.06.2010, 07:21 
Аватара пользователя
lel0lel в сообщении #327001 писал(а):

(Оффтоп)

Сначала хотел написать, что это что-то из области фантастики, потому как трудно представить, как может булева функция удовлетворять условиям Дирихле. Но погуглив, на нескольких серьёзных сайтах нашел упоминания об этом, правда там всё больше темы конференций, а не литература.

(Оффтоп)

могу даже подсказать как выглядят эти ряды: $$f(x_1,\dots,x_n)=2^{-n}\sum\limits_{\alpha\in V_n} C_\alpha^f (-1)^{(\alpha , x)},$$ где $\alpha = (\alpha_1, \dots, \alpha_n), x = (x_1, \dots, x_n), V_n$ - всевозможные вектора длины $n$ над множеством $\{0,1\}. C_\alpha^f = \sum_{x\in V_n} f(x)(-1)^{(\alpha , x)}$ и $(a,b) = a_1b_1 + \dots a_nb_n$, где сложение ведется по модулю 2.

Просто у нас преподаватель, который ведет дискретную математику, весь материал берет из каких-либо книжек, про которые нам ничего не рассказывает, думал может здесь знают откуда же он его берет)

 
 
 
 Re: Ряды фурье для булевых функций
Сообщение03.06.2010, 09:45 
Аватара пользователя
Ещё по анализу Фурье на конечных группах рекомендуют книжку A. Terras, Fourier analysis on finite groups and applications, но сам я не читал (и в свободном доступе книжка не очень хочет находиться).

 
 
 
 Re: Ряды фурье для булевых функций
Сообщение03.06.2010, 11:21 
Ряды Фурье появились для решения линейных дифференциальных уравнений.
Решение ищется в виде суммы собственных функций оператора дифференцирования.
Экспонента, синусы и косинусы.

Для чего нужны ряды Фурье булевых функций? Какие задачи они помогают решить?

 
 
 
 Re: Ряды фурье для булевых функций
Сообщение03.06.2010, 12:06 
Аватара пользователя
Ales в сообщении #327128 писал(а):
Для чего нужны ряды Фурье булевых функций? Какие задачи они помогают решить?
Они используются для изучения алгебраических свойств, например таких, как нелинейность(широко используется в криптологии). Также есть оценки, связывающие спектральные характеристики и сложность реализации булевых функций: http://ilex.iit.cnr.it/codenotti/ps_files/fourier.ps . Наверняка еще есть применения.

 
 
 
 Re: Ряды фурье для булевых функций
Сообщение03.06.2010, 14:02 
Xaositect в сообщении #327140 писал(а):
Они используются для изучения алгебраических свойств

А они там естественно возникли или принесены искусственно?
Не факт ведь, что ряды полезные в гладком анализе, будут также полезны в дискретной математике.
Хорошо ли вводить ряды Фурье для булевых функций?

 
 
 
 Re: Ряды фурье для булевых функций
Сообщение02.07.2010, 07:42 
Как раз в тему:
Помогите разложить в ряд Фурье следующую булеву функцию:
$f(a,b,c)=(a \cap c) \cup ({\overline{a}}  \cap {\overline{c}})$

 
 
 
 Re: Ряды фурье для булевых функций
Сообщение02.07.2010, 10:09 
Аватара пользователя
warezhunter_ в сообщении #336754 писал(а):
Как раз в тему:
Помогите разложить в ряд Фурье следующую булеву функцию:
$f(a,b,c)=(a \cap c) \cup ({\overline{a}}  \cap {\overline{c}})$

каким методом разложить надо и в чем затруднения?

 
 
 
 Re: Ряды фурье для булевых функций
Сообщение02.07.2010, 10:23 
BapuK в сообщении #336774 писал(а):
warezhunter_ в сообщении #336754 писал(а):
Как раз в тему:
Помогите разложить в ряд Фурье следующую булеву функцию:
$f(a,b,c)=(a \cap c) \cup ({\overline{a}}  \cap {\overline{c}})$

каким методом разложить надо и в чем затруднения?

Затруднение в том, что я просто не могу найти практический материал или похожий пример как это сделать, в учебниках не понятно ничего.

 
 
 
 Re: Ряды фурье для булевых функций
Сообщение02.07.2010, 12:43 
А, все похоже разобрался, сначала строим матрицу Уолша, затем Радехаммера, перемножаем по таблице истинности функцию и матрицу Радехаммера, получаем коэффициенты Уолша и затем формируем ряд Фурье.

 
 
 
 Re: Ряды фурье для булевых функций
Сообщение02.07.2010, 18:09 
Аватара пользователя
warezhunter_ в сообщении #336807 писал(а):
А, все похоже разобрался, сначала строим матрицу Уолша, затем Радехаммера, перемножаем по таблице истинности функцию и матрицу Радехаммера, получаем коэффициенты Уолша и затем формируем ряд Фурье.

Все верно, только таким образом получаем коэффициенты Фурье, если бы переменожали столбец истинности действительной функции, которая соответсвует данной булевой, то получили бы коэффициенты Уолша.

 
 
 [ Сообщений: 13 ] 


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