Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 5 ] |
|
Автор | Сообщение | |
---|---|---|
denisovviktor |
|
|
Задача по дискретной математике Дана матрица 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 раз(а). |
||
Вернуться к началу | ||
Slon |
|
|
Что такое сложность матрицы? И что такое глубина?
|
||
Вернуться к началу | ||
denisovviktor |
|
|
Сложность схемы - количество операций
Схемная сложность функции - это минимальная сложность схемы, которая вычисляет эту функцию. Глубина вершины v в схеме S=(V,E) - это максимальная длина пути из входов S в v . Глубиной D(S) схемы S назовем максимальную из глубин ее вершин Эти определение нашел при поиске решения Для булевой матрицы тоже встречается в книгах понятие сложности и глубины но определение не нашел |
||
Вернуться к началу | ||
Slon |
|
|
Теперь немного яснее, сразу Вам не смогу помочь, не очень хорошо в этом разбираюсь.
|
||
Вернуться к началу | ||
denisovviktor |
|
|
Получается здесь нужна схемная сложность системы из двух линейных булевых функций
|
||
Вернуться к началу | ||
[ Сообщений: 5 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Сложность с внесением функции под знак дифференциала
в форуме Интегральное исчисление |
0 |
206 |
04 дек 2018, 19:18 |
|
Построить СДНФ булевой функции | 4 |
143 |
09 ноя 2021, 16:26 |
|
Постоянная подфункция булевой функции | 0 |
94 |
16 дек 2022, 17:22 |
|
Найти вектор значений булевой функции | 0 |
599 |
31 мар 2018, 19:05 |
|
Сконструировать переключательную схему булевой функции | 1 |
182 |
03 апр 2022, 13:30 |
|
Решить краевую задачу с помощью функции Грина | 0 |
199 |
04 май 2019, 20:49 |
|
Для булевой функции, заданной вектором значений (01000011) | 2 |
655 |
20 сен 2017, 20:12 |
|
Определить наличие фиктивных переменных для булевой функции | 2 |
230 |
10 мар 2022, 13:50 |
|
Задача на СМО (сложность) | 0 |
226 |
05 июн 2017, 20:51 |
|
Асимптотическая сложность алгоритмов
в форуме Информатика и Компьютерные науки |
2 |
573 |
09 мар 2018, 16:19 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 12 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |