2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



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


06/03/09
240
Владивосток
В какой книжке можно про них прочитать?

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


20/04/10
1776

(Оффтоп)

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

 Профиль  
                  
 
 Re: Ряды фурье для булевых функций
Сообщение02.06.2010, 23:14 
Заслуженный участник
Аватара пользователя


06/10/08
6422
В книге "Булевы функции в теории кодирования и криптологии" активно используется преобразование Фурье булевых функций, но на основах авторы подробно не останавливаются.

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

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

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


06/03/09
240
Владивосток
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 
Заслуженный участник
Аватара пользователя


11/01/06
3822
Ещё по анализу Фурье на конечных группах рекомендуют книжку A. Terras, Fourier analysis on finite groups and applications, но сам я не читал (и в свободном доступе книжка не очень хочет находиться).

 Профиль  
                  
 
 Re: Ряды фурье для булевых функций
Сообщение03.06.2010, 11:21 


20/12/09
1527
Ряды Фурье появились для решения линейных дифференциальных уравнений.
Решение ищется в виде суммы собственных функций оператора дифференцирования.
Экспонента, синусы и косинусы.

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

 Профиль  
                  
 
 Re: Ряды фурье для булевых функций
Сообщение03.06.2010, 12:06 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Ряды фурье для булевых функций
Сообщение03.06.2010, 14:02 


20/12/09
1527
Xaositect в сообщении #327140 писал(а):
Они используются для изучения алгебраических свойств

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

 Профиль  
                  
 
 Re: Ряды фурье для булевых функций
Сообщение02.07.2010, 07:42 


22/08/09
48
Как раз в тему:
Помогите разложить в ряд Фурье следующую булеву функцию:
$f(a,b,c)=(a \cap c) \cup ({\overline{a}}  \cap {\overline{c}})$

 Профиль  
                  
 
 Re: Ряды фурье для булевых функций
Сообщение02.07.2010, 10:09 
Аватара пользователя


06/03/09
240
Владивосток
warezhunter_ в сообщении #336754 писал(а):
Как раз в тему:
Помогите разложить в ряд Фурье следующую булеву функцию:
$f(a,b,c)=(a \cap c) \cup ({\overline{a}}  \cap {\overline{c}})$

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

 Профиль  
                  
 
 Re: Ряды фурье для булевых функций
Сообщение02.07.2010, 10:23 


22/08/09
48
BapuK в сообщении #336774 писал(а):
warezhunter_ в сообщении #336754 писал(а):
Как раз в тему:
Помогите разложить в ряд Фурье следующую булеву функцию:
$f(a,b,c)=(a \cap c) \cup ({\overline{a}}  \cap {\overline{c}})$

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

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

 Профиль  
                  
 
 Re: Ряды фурье для булевых функций
Сообщение02.07.2010, 12:43 


22/08/09
48
А, все похоже разобрался, сначала строим матрицу Уолша, затем Радехаммера, перемножаем по таблице истинности функцию и матрицу Радехаммера, получаем коэффициенты Уолша и затем формируем ряд Фурье.

 Профиль  
                  
 
 Re: Ряды фурье для булевых функций
Сообщение02.07.2010, 18:09 
Аватара пользователя


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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group