Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 5 ] 
Автор Сообщение
 Заголовок сообщения: Решить задачу на схемную сложность булевой функции
СообщениеДобавлено: 29 май 2018, 13:38 
Не в сети
Начинающий
Зарегистрирован:
29 май 2018, 13:31
Сообщений: 3
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Помогите решить задачу
Задача по дискретной математике
Дана матрица 0ей и 1иц. Найти минимальную сложность матрицы в базисе сложение по модулю 2. Нужна схемная сложность. и глубина
[math]L( x \oplus y ) =[/math] ?
[math]\begin{pmatrix} 1 & 0 & 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 1 & 0 \end{pmatrix}[/math]

Как я пытаюсь решить:

[math]f(x) = x_1 \oplus x_3 \oplus x_5 \oplus x_6 \oplus x_7[/math]

[math]f(y) = y_1 \oplus y_2 \oplus y_3 \oplus y_4 \oplus y_6[/math]

Для первой булевой функции получается схема

Изображение

Сложность схемы - число операций, то есть 4 но я думаю можно за меньшее число операций возможно с помощью какой-то формулы, паралелльных вычислений. Как посчитать минимальную сложность?
И как посчитать для 2-х функций минимальную сложность?


Последний раз редактировалось denisovviktor 29 май 2018, 13:52, всего редактировалось 7 раз(а).
Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Решить задачу на схемную сложность булевой функции
СообщениеДобавлено: 29 май 2018, 13:40 
Не в сети
Оракул
Зарегистрирован:
14 дек 2017, 17:48
Сообщений: 870
Cпасибо сказано: 33
Спасибо получено:
206 раз в 187 сообщениях
Очков репутации: 31

Добавить очки репутацииУменьшить очки репутации
Что такое сложность матрицы? И что такое глубина?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Решить задачу на схемную сложность булевой функции
СообщениеДобавлено: 29 май 2018, 13:57 
Не в сети
Начинающий
Зарегистрирован:
29 май 2018, 13:31
Сообщений: 3
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Сложность схемы - количество операций
Схемная сложность функции - это минимальная сложность схемы, которая вычисляет эту функцию.
Глубина вершины v в схеме S=(V,E) - это максимальная длина пути из входов S в v .
Глубиной D(S) схемы S назовем максимальную из глубин ее вершин

Эти определение нашел при поиске решения
Для булевой матрицы тоже встречается в книгах понятие сложности и глубины но определение не нашел

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Решить задачу на схемную сложность булевой функции
СообщениеДобавлено: 29 май 2018, 14:03 
Не в сети
Оракул
Зарегистрирован:
14 дек 2017, 17:48
Сообщений: 870
Cпасибо сказано: 33
Спасибо получено:
206 раз в 187 сообщениях
Очков репутации: 31

Добавить очки репутацииУменьшить очки репутации
Теперь немного яснее, сразу Вам не смогу помочь, не очень хорошо в этом разбираюсь.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Решить задачу на схемную сложность булевой функции
СообщениеДобавлено: 29 май 2018, 15:48 
Не в сети
Начинающий
Зарегистрирован:
29 май 2018, 13:31
Сообщений: 3
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Получается здесь нужна схемная сложность системы из двух линейных булевых функций

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

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Сложность с внесением функции под знак дифференциала

в форуме Интегральное исчисление

OlNeva

0

206

04 дек 2018, 19:18

Построить СДНФ булевой функции

в форуме Дискретная математика, Теория множеств и Логика

MathSamurai

4

143

09 ноя 2021, 16:26

Постоянная подфункция булевой функции

в форуме Дискретная математика, Теория множеств и Логика

bantester

0

94

16 дек 2022, 17:22

Найти вектор значений булевой функции

в форуме Дискретная математика, Теория множеств и Логика

alekscooper

0

599

31 мар 2018, 19:05

Сконструировать переключательную схему булевой функции

в форуме Дискретная математика, Теория множеств и Логика

Gregory723

1

182

03 апр 2022, 13:30

Решить краевую задачу с помощью функции Грина

в форуме Дифференциальные и Интегральные уравнения

dddsss

0

199

04 май 2019, 20:49

Для булевой функции, заданной вектором значений (01000011)

в форуме Дискретная математика, Теория множеств и Логика

Crow

2

655

20 сен 2017, 20:12

Определить наличие фиктивных переменных для булевой функции

в форуме Дискретная математика, Теория множеств и Логика

Gregory237

2

230

10 мар 2022, 13:50

Задача на СМО (сложность)

в форуме Математическая статистика и Эконометрика

asya_X

0

226

05 июн 2017, 20:51

Асимптотическая сложность алгоритмов

в форуме Информатика и Компьютерные науки

Bush

2

573

09 мар 2018, 16:19


Часовой пояс: UTC + 3 часа [ Летнее время ]



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

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


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

Найти:
Перейти:  
cron

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved