Вопросы с меткой [дискретная-математика]
Дискре́тная матема́тика — часть математики, изучающая дискретные математические структуры, такие, как графы и утверждения в логике.
75
вопросов
1
голос
1
ответ
302
показа
Как сделать циклом Функциональный граф?
Добрый день!
Помогите пожалуйста или дайте подсказку. Решаю задачу. Условие следующее:
В школе перед Новым Годом устраивают игру в Тайного Санту. Каждому ученику i выдается ученик
ai, которому он ...
0
голосов
0
ответов
28
показов
Суперпозиция, не получается решить задачу
Дана функция, нужно из заданного набора других трёх функций с помощью отождествлений и подстановок следующую суперпозицию https://ibb.co/cXY6n9d .
На лекциях разбор был с простыми функциями, применяя ...
0
голосов
0
ответов
36
показов
Задача о назначениях с недопустимыми назначениями
Итак, имеется задача о назначениях.
Дана матрица m x n , в ней есть положительные числа и "NaN".
Альтернативная форма - дан взвешенный двудольный (но не обязательно полный двудольный) граф.
...
0
голосов
2
ответа
52
показа
Рекуррентное решение, комбинаторика
Кодовое слово может содержать цифры 0, 1..7 , при этом количество числа 0 - нечетное. Сколько вариантов такого слова может быть при длине N? Нужно решить рекуррентно.
Мое решение этой задачи:
Символы ...
2
голоса
0
ответов
309
показов
Как найти минимальное количество ребер, которое нужно добавить, чтобы граф стал эйлеровым путем или циклом?
Есть некоторые графы, например как на скриншоте. Как узнать, сколько раз (если их рисовать карандашом) надо оторвать карандаш от бумаги, чтобы нарисовать граф.
Граф задается по одной компоненте ...
0
голосов
1
ответ
77
показов
Обход вершин минимального остовного дерева
Нахождение минимального остовного дерева графа по алгоритму Крускала
#include <iostream>
#include <vector>
using namespace std;
// Структура для представления графа
struct Graph {
...
1
голос
0
ответов
53
показа
Образуют ли функции Базис
Условие задачи:
Во входном файле заданы несколько функций. Образуют ли они базис? Сначала во входном файле записано число - количество функций, далее все функции, каждая в отдельной строке.
Идея:
...
0
голосов
0
ответов
34
показа
Функция распределения и отрицательное биномиальное распределение
https://youtu.be/bvCh0udl3cs?t=3263
Изучал тему - отрицательное биномиальное распределение. Предлагается задачка (по ссылке). Но её решение завело меня в ступор. По определению, распределение ...
0
голосов
0
ответов
39
показов
Не могу понять как выведена формула для решения задачи по нахождению числа графов где нет вершины максимальной степени
Задача: Задан граф без петель и кратных ребер. Найти количество графов из n вершин, таких, что в графе существует единственная вершина, соединенная со всеми другими (то есть ровно у одной вершины ...
-1
голос
1
ответ
489
показов
В кондитерской продают 7 видов пирожных. Сколькими способами можно купить 15 пирожных?
Снова всем привет!
Задача:
В кондитерской продают 7 видов пирожных. Сколькими способами можно купить 15 пирожных? Сколькими способами можно это сделать так, чтобы среди них оказались пирожные каждого ...
-7
голосов
1
ответ
129
показов
Упростить вид множества, которое задано с помощью операций
Упростить вид множества, которое задано с помощью операций, применяя законы алгебры множеств (в ответ множества могут входить не более одного раза):
0
голосов
0
ответов
52
показа
Как построить матрицы по данным отношениям?
Есть 2 вида отношений a = {(x, y) ∈ R^2 | x + y = 0} и b = {(x, y) ∈ N^2 | y = x^2}. Как по ним построить матрицы?
Я правильно понимаю, что в случае a - это будет матрица из нулей, в которой на местах ...
0
голосов
0
ответов
83
показа
Сдвиг центра графика
При разработке программы отображения графика функции возникла задача скроллинга графика по оси Y вверх или вниз без изменения масштаба.
Т.е. необходимо сдвинуть границы отображаемой части графика так, ...
1
голос
1
ответ
143
показа
Как доказать полноту системы булевых функций без использования Теоремы Поста?
Стоит задача доказать полноту системы булевых функций без использования Теоремы Поста, но в интернете я пока к большому сожалению ничего найти не смог. Есть ли альтернативный способ доказательства?
-3
голоса
1
ответ
79
показов
Число Фибоначчи с полным квадрат
задание
Показать, что 2n+1 – 7f2n-1, есть полный квадрат.
А как это реализовать я не понимаю, подскажите что нужно подставить, вот код
public class Two {
public static void main(String[] args) {
...
4
голоса
1
ответ
312
показов
Что такое симметричное замыкание?
Всем привет, ни как не могу понять что такое симметричное замыкание?
Знаю что симметричное замыкание R является объединением R с его обратное отношением R , на некотором множестве R, но как и что с ...
1
голос
1
ответ
576
показов
Посчитать количество графов в котором хотя бы одна вершина имеет степень N - 1
Как посчитать количество неориентированных графов из N вершин , где ни у одной вершины нет степени N-1. Графы без петель и кратных ребер.
До чего пришел :
Всего графов на N вершинах можно построить 2^...
0
голосов
1
ответ
443
показа
Задача по олимпиадному программированию
Наткнулся на одну задачу, я ее точно решить не смогу, но если кто-то ее решит, то был бы рад прийти в восторг от решения :)
Задача, как по мне, довольно сложная
Прочитал на одном форуме, что это нужно ...
0
голосов
1
ответ
36
показов
Как читается запись ∃x~(Ɐy)R(x,y)?
вот есть запись:
∃x~(Ɐy)R(x,y),
где R(x,y) - предикат
как эта запись читаеться?
есть некоторое x, и не каждое y что высказывание: R(x,y) истинно?
0
голосов
1
ответ
89
показов
Что значит запись ~Ɐx(D(x))?
Вот есть запись: ~Ɐx(D(x))
~ - отрицание
D(x) - предикат,
Ɐ - для всех x.
а как читаеться эта запись? для всех x ложен предикат? или как, и как она будет работать на каком небудь примере?
1
голос
1
ответ
68
показов
Массив не заполняется до конца через цикл
Есть массив func, в него передаем 1 либо 0, там где равно 1 в новом массиве miniterms4 мы записываем соответственное значение:
n = int(input("Колво переменных: "))
miniterms4 = set([])
func =...
2
голоса
0
ответов
160
показов
Создание булевой формулы на Python
Есть задача поиска максимальных внутренне устойчивых множеств графа методом Магу(дискретная математика в вузе).
Задаю граф матрицей смежности(уже реализовал), далее требуется составить булевы формулы ...
0
голосов
1
ответ
55
показов
Комбинаторика(Деревья на участках)
Сколькими способами можно рассадить деревья трех видов: 5 вишен, 6 яблонь и 10 абрикос на трех разных участках, если на каждом участке должны быть деревья всех видов.
Как я понял у нас по-любому 9 ...
1
голос
0
ответов
32
показа
Матрица отношений
Нужно найти матрицу отношения
Может кто-то объяснить как делать такие задания?
1
голос
1
ответ
52
показа
Фикс программы сравнения множеств чисел (Си)
Реализую программу сравнения множеств,в целом программа работает нормально до момента ввода во множество одинаковых чисел,я пытался это как то исправить но мой способ работает тольо если повторения ...
1
голос
0
ответов
46
показов
Улучшение сложности Венгерского алгоритма
В данный момент пишу реализацию Венгерского алгоритма для решения задачи о назначениях. На каждой итерации алгоритма максимальное паросочетание ищется заново (а не путем преобразования предыдущего). ...
0
голосов
0
ответов
185
показов
Входные данные к реализации алгоритма Куна
Хочу изучить и реализовать Венгерский алгоритм (задача о назначениях). Как я понимаю, алгоритм Куна является его составной частью (решает промежуточную задачу поиска максимального паросочетания). Код, ...
0
голосов
1
ответ
284
показа
вычисление интеграла, дискретная математика
Мне необходимо вычислить интеграл. Область G, ограниченная окружностью x[SUP]2[/SUP]+y[SUP]2[/SUP]<=25, вписанная в квадрат D. Вычислить необходимо по формуле приведенной ниже. В условии дали ответ ...
2
голоса
1
ответ
107
показов
геометрическая вероятность, интеграл
Мне необходимо вычислить интеграл. Область G, ограниченная прямыми x=2, y=x и гиперболой xy=1, вписанная в прямоугольник D. Вычислить необходимо по формуле приведенной ниже. В условии дали ответ ...
1
голос
2
ответа
858
показов
Как реализовать генерацию размещений без повторений?
Как лучше реализовать функцию permutate с сигнатурой (JavaScript)
const array = ['a', 'b', 'c']; // множество элементов
const k = 2; // размер размещений
const permutations = permutate(array, k);
...
6
голосов
4
ответа
3k
показов
Как реализовать генерацию сочетаний без повторений?
Как лучше реализовать функцию combine с сигнатурой (JavaScript)
const array = ['a', 'b', 'c', 'd']; // множество элементов
const k = 3; // размер сочетаний
const combinations = combine(array, k);
...
1
голос
1
ответ
171
показ
Определить множество, на котором данное отношение является функциональным, биективным
Определить множество (если это возможно), на которой данное
отношение являются: а) функциональным; б) биективним:
Как это решить
Может кто-то скинет пример решения подобной задачи
1
голос
2
ответа
2k
показов
Нерефлексивне, симметричное, транзитивное бинарное отношение
Привести пример бинарного отношения R ⊂ A × A, где
A = {a, b, c,d,e}, которое является нерефлексивное, симметричное, транзитивное, и
построить его матрицу.
0
голосов
1
ответ
86
показов
Дискретная математика
По таблице истинности найти формулы, определяющие функции
f1(x1,x2,x3), f2(x1,x2,x3), и придать им более простой вид:
1
голос
1
ответ
418
показов
Упростить вид множества
Упростить вид множества, заданной с помощью
операций, применяя законы алгебры множеств (в ответ множества
могут входить не более одного раза):
(A ∩ ¯B)∆(¯A ∩ B)
А как дальше?
Могу ли я взять ¯B и ...
1
голос
0
ответов
147
показов
Записать условие задачи с помощью алгебры логики
Помогите, пожалуйста, записать условие задачи с помощью алгебры логики.
Три дочери писательницы Дорис Кей — Джуди, Айрис и Линда — тоже очень талантливы. Они приобрели известность в разных видах ...
1
голос
2
ответа
70
показов
Сопоставление текста и html. Поиск позиции
Есть текст и его html версия:
Once upon a time there was a very rich man who lived with his three daughters. The two older daughters laughed at anyone who did not dress as wel as they did. If the ...
3
голоса
2
ответа
10k
показов
Числа Рамануджана
Есть известное число Рамануджана - 1729. Это наименьшее число, выражаемое как сумма двух кубов двумя разными способами. Другими словами:
1729 = 1^3 + 12^3 = 9^3 + 10^3.
Какие есть еще числа ...
7
голосов
0
ответов
139
показов
Улучшение алгоритма подсчета количества пар, чье побитовое И является степенью 2
Как можно улучшить алгоритм считающий количество неупорядоченных пар в массиве, чье побитовое И является степенью 2? Например, если массив равен [10,7,2,8,3]. Ответ 6. Объяснение:
10 & 7 = 2
10 &...
0
голосов
0
ответов
26
показов
Почему автор статьи использует дробь если должны быть целые числа?
Автор в этой статье описывает метод инициализации сложности темы. Вот здесь (ниже на скрине)
он говорит что определят уровень преимущества одной темы над другой с помощью шкалы Саати (цифры от 1 до 9)...
1
голос
1
ответ
43
показа
Проблема с пониманием алгоритма Монтгомери
Возникла необходимость разобраться в алгоритме Монтгомери. При изучении статьи на википедии (https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9C%D0%BE%D0%BD%D1%82%D0%...
0
голосов
1
ответ
155
показов
Задача с палочками
У Андрея есть палочки с целочисленными длинами и общей длиной 200. Ни из каких трёх нельзя составить треугольник. Какое наибольшее число палочек может быть?
Я знаю что любая палочка должна быть ...
0
голосов
0
ответов
28
показов
Полнота условий
Всем доброго времени суток. Есть задача, которую не понимаю как можно красиво алгоритмически решить.
Условие: Пользователь может задавать набор правил(условия для предикатов), для примера, рассмотрим ...
3
голоса
1
ответ
279
показов
Замкнутость множества из книги Кострикин А.И. 1977 г
помогите понять элементарную алгебру.
В книге Введение в Алгебру Кострикина А.И. есть утверждение.
Множество S = {4k+1 | k = 0, 1, 2 ...}. Оно замкнуто относительно умножения
(4k1 + 1)(4k2+1) = ...
2
голоса
1
ответ
120
показов
как реализовать остаток от деления в обратную сторону?
Предположим У меня сейчас такой код в цикле
C++
a = (a+3) % (13)
Я получаю такие результаты
3
6
9
12
2
5
Теперь я бы хотел сделать другой цикл в обратной последовательности. Где ...
0
голосов
0
ответов
143
показа
Реализация функции с помощью алгоритма Стаи серых Волков
Задавал вопрос по этому же примеру, но с реализацией по генетическому алгоритму. Сейчас мне нужно реализовать этот же пример, только с помощью алгоритма Стаи серых Волков. Есть у кого-то примеры с ...
1
голос
1
ответ
1k
показов
Композиция бинарных отношений (на матрице) равна произведению матриц бинарных отношений?
Композиция бинарных отношений (на матрице) равна произведению матриц бинарных отношений?
0
голосов
0
ответов
42
показа
Построить КДА, который по двоичному разложению числа a строит двоичное разложение числа 3а
Построить кда который по двоичному разложению числа "a" строить двоичное разложение числа "3а"
Можете пожалуйста обьяснить что вообще это за автомат такой? на вход подаётся только буква "a"? или ...
-1
голос
1
ответ
68
показов
Вопрос к знающим дискретную математику [закрыт]
Можно ли браться за "Алгоритмы. Построение и анализ." Кормена со школьными знаниями математики? Если же нет, посоветуйте вводную литературу, за счет которой можно подготовиться к Кормену.
0
голосов
0
ответов
140
показов
Построить контекстно-свободную грамматику, порождающую указанный язык
Построить кс грамматику порождающую язык: a^n b^3m a^5 b^3 c^2n c^m n>0 m>0:n>0 m>0 более точно написано на скриншоте
Я построил вот так не знаю правильно ли это?
S->ABCDKM
A->a
B-&...