Вопросы с меткой [дискретная-математика]

Дискре́тная матема́тика — часть математики, изучающая дискретные математические структуры, такие, как графы и утверждения в логике.

Фильтрация
Сортировка
Метки
1 голос
1 ответ
302 показа

Как сделать циклом Функциональный граф?

Добрый день! Помогите пожалуйста или дайте подсказку. Решаю задачу. Условие следующее: В школе перед Новым Годом устраивают игру в Тайного Санту. Каждому ученику i выдается ученик ai, которому он ...
Илья Ким's user avatar
0 голосов
0 ответов
28 показов

Суперпозиция, не получается решить задачу

Дана функция, нужно из заданного набора других трёх функций с помощью отождествлений и подстановок следующую суперпозицию https://ibb.co/cXY6n9d . На лекциях разбор был с простыми функциями, применяя ...
Nikita Razuvaev's user avatar
0 голосов
0 ответов
36 показов

Задача о назначениях с недопустимыми назначениями

Итак, имеется задача о назначениях. Дана матрица m x n , в ней есть положительные числа и "NaN". Альтернативная форма - дан взвешенный двудольный (но не обязательно полный двудольный) граф. ...
pes oves's user avatar
0 голосов
2 ответа
52 показа

Рекуррентное решение, комбинаторика

Кодовое слово может содержать цифры 0, 1..7 , при этом количество числа 0 - нечетное. Сколько вариантов такого слова может быть при длине N? Нужно решить рекуррентно. Мое решение этой задачи: Символы ...
NoOneCare's user avatar
2 голоса
0 ответов
309 показов

Как найти минимальное количество ребер, которое нужно добавить, чтобы граф стал эйлеровым путем или циклом?

Есть некоторые графы, например как на скриншоте. Как узнать, сколько раз (если их рисовать карандашом) надо оторвать карандаш от бумаги, чтобы нарисовать граф. Граф задается по одной компоненте ...
fgrd4035's user avatar
0 голосов
1 ответ
77 показов

Обход вершин минимального остовного дерева

Нахождение минимального остовного дерева графа по алгоритму Крускала #include <iostream> #include <vector> using namespace std; // Структура для представления графа struct Graph { ...
vadyanysh's user avatar
1 голос
0 ответов
53 показа

Образуют ли функции Базис

Условие задачи: Во входном файле заданы несколько функций. Образуют ли они базис? Сначала во входном файле записано число - количество функций, далее все функции, каждая в отдельной строке. Идея: ...
Stan's user avatar
  • 305
0 голосов
0 ответов
34 показа

Функция распределения и отрицательное биномиальное распределение

https://youtu.be/bvCh0udl3cs?t=3263 Изучал тему - отрицательное биномиальное распределение. Предлагается задачка (по ссылке). Но её решение завело меня в ступор. По определению, распределение ...
Тима 's user avatar
0 голосов
0 ответов
39 показов

Не могу понять как выведена формула для решения задачи по нахождению числа графов где нет вершины максимальной степени

Задача: Задан граф без петель и кратных ребер. Найти количество графов из n вершин, таких, что в графе существует единственная вершина, соединенная со всеми другими (то есть ровно у одной вершины ...
Павел Татаров's user avatar
-1 голос
1 ответ
489 показов

В кондитерской продают 7 видов пирожных. Сколькими способами можно купить 15 пирожных?

Снова всем привет! Задача: В кондитерской продают 7 видов пирожных. Сколькими способами можно купить 15 пирожных? Сколькими способами можно это сделать так, чтобы среди них оказались пирожные каждого ...
user avatar
-7 голосов
1 ответ
129 показов

Упростить вид множества, которое задано с помощью операций

Упростить вид множества, которое задано с помощью операций, применяя законы алгебры множеств (в ответ множества могут входить не более одного раза):
wwwww2's user avatar
  • 1
0 голосов
0 ответов
52 показа

Как построить матрицы по данным отношениям?

Есть 2 вида отношений a = {(x, y) ∈ R^2 | x + y = 0} и b = {(x, y) ∈ N^2 | y = x^2}. Как по ним построить матрицы? Я правильно понимаю, что в случае a - это будет матрица из нулей, в которой на местах ...
gnd20032's user avatar
0 голосов
0 ответов
83 показа

Сдвиг центра графика

При разработке программы отображения графика функции возникла задача скроллинга графика по оси Y вверх или вниз без изменения масштаба. Т.е. необходимо сдвинуть границы отображаемой части графика так, ...
Volear's user avatar
  • 1
1 голос
1 ответ
143 показа

Как доказать полноту системы булевых функций без использования Теоремы Поста?

Стоит задача доказать полноту системы булевых функций без использования Теоремы Поста, но в интернете я пока к большому сожалению ничего найти не смог. Есть ли альтернативный способ доказательства?
sweetferrero's user avatar
-3 голоса
1 ответ
79 показов

Число Фибоначчи с полным квадрат

задание Показать, что 2n+1 – 7f2n-1, есть полный квадрат. А как это реализовать я не понимаю, подскажите что нужно подставить, вот код public class Two { public static void main(String[] args) { ...
Jizik51's user avatar
  • 39
4 голоса
1 ответ
312 показов

Что такое симметричное замыкание?

Всем привет, ни как не могу понять что такое симметричное замыкание? Знаю что симметричное замыкание R является объединением R с его обратное отношением R , на некотором множестве R, но как и что с ...
RockInMyHead's user avatar
1 голос
1 ответ
576 показов

Посчитать количество графов в котором хотя бы одна вершина имеет степень N - 1

Как посчитать количество неориентированных графов из N вершин , где ни у одной вершины нет степени N-1. Графы без петель и кратных ребер. До чего пришел : Всего графов на N вершинах можно построить 2^...
Inp Pq's user avatar
  • 21
0 голосов
1 ответ
443 показа

Задача по олимпиадному программированию

Наткнулся на одну задачу, я ее точно решить не смогу, но если кто-то ее решит, то был бы рад прийти в восторг от решения :) Задача, как по мне, довольно сложная Прочитал на одном форуме, что это нужно ...
KAVA's user avatar
  • 45
0 голосов
1 ответ
36 показов

Как читается запись ∃x~(Ɐy)R(x,y)?

вот есть запись: ∃x~(Ɐy)R(x,y), где R(x,y) - предикат как эта запись читаеться? есть некоторое x, и не каждое y что высказывание: R(x,y) истинно?
user avatar
0 голосов
1 ответ
89 показов

Что значит запись ~Ɐx(D(x))?

Вот есть запись: ~Ɐx(D(x)) ~ - отрицание D(x) - предикат, Ɐ - для всех x. а как читаеться эта запись? для всех x ложен предикат? или как, и как она будет работать на каком небудь примере?
user avatar
1 голос
1 ответ
68 показов

Массив не заполняется до конца через цикл

Есть массив func, в него передаем 1 либо 0, там где равно 1 в новом массиве miniterms4 мы записываем соответственное значение: n = int(input("Колво переменных: ")) miniterms4 = set([]) func =...
sdgdrhzdrhzr's user avatar
2 голоса
0 ответов
160 показов

Создание булевой формулы на Python

Есть задача поиска максимальных внутренне устойчивых множеств графа методом Магу(дискретная математика в вузе). Задаю граф матрицей смежности(уже реализовал), далее требуется составить булевы формулы ...
Yan's user avatar
  • 89
0 голосов
1 ответ
55 показов

Комбинаторика(Деревья на участках)

Сколькими способами можно рассадить деревья трех видов: 5 вишен, 6 яблонь и 10 абрикос на трех разных участках, если на каждом участке должны быть деревья всех видов. Как я понял у нас по-любому 9 ...
whoIam's user avatar
  • 47
1 голос
0 ответов
32 показа

Матрица отношений

Нужно найти матрицу отношения Может кто-то объяснить как делать такие задания?
whoIam's user avatar
  • 47
1 голос
1 ответ
52 показа

Фикс программы сравнения множеств чисел (Си)

Реализую программу сравнения множеств,в целом программа работает нормально до момента ввода во множество одинаковых чисел,я пытался это как то исправить но мой способ работает тольо если повторения ...
MarshalStroheim's user avatar
1 голос
0 ответов
46 показов

Улучшение сложности Венгерского алгоритма

В данный момент пишу реализацию Венгерского алгоритма для решения задачи о назначениях. На каждой итерации алгоритма максимальное паросочетание ищется заново (а не путем преобразования предыдущего). ...
Maxim Voloshin's user avatar
0 голосов
0 ответов
185 показов

Входные данные к реализации алгоритма Куна

Хочу изучить и реализовать Венгерский алгоритм (задача о назначениях). Как я понимаю, алгоритм Куна является его составной частью (решает промежуточную задачу поиска максимального паросочетания). Код, ...
Maxim Voloshin's user avatar
0 голосов
1 ответ
284 показа

вычисление интеграла, дискретная математика

Мне необходимо вычислить интеграл. Область G, ограниченная окружностью x[SUP]2[/SUP]+y[SUP]2[/SUP]<=25, вписанная в квадрат D. Вычислить необходимо по формуле приведенной ниже. В условии дали ответ ...
Igor's user avatar
  • 101
2 голоса
1 ответ
107 показов

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

Мне необходимо вычислить интеграл. Область G, ограниченная прямыми x=2, y=x и гиперболой xy=1, вписанная в прямоугольник D. Вычислить необходимо по формуле приведенной ниже. В условии дали ответ ...
Igor's user avatar
  • 101
1 голос
2 ответа
858 показов

Как реализовать генерацию размещений без повторений?

Как лучше реализовать функцию permutate с сигнатурой (JavaScript) const array = ['a', 'b', 'c']; // множество элементов const k = 2; // размер размещений const permutations = permutate(array, k); ...
Артём Ионаш's user avatar
6 голосов
4 ответа
3k показов

Как реализовать генерацию сочетаний без повторений?

Как лучше реализовать функцию combine с сигнатурой (JavaScript) const array = ['a', 'b', 'c', 'd']; // множество элементов const k = 3; // размер сочетаний const combinations = combine(array, k); ...
Артём Ионаш's user avatar
1 голос
1 ответ
171 показ

Определить множество, на котором данное отношение является функциональным, биективным

Определить множество (если это возможно), на которой данное отношение являются: а) функциональным; б) биективним: Как это решить Может кто-то скинет пример решения подобной задачи
Bohdan's user avatar
  • 231
1 голос
2 ответа
2k показов

Нерефлексивне, симметричное, транзитивное бинарное отношение

Привести пример бинарного отношения R ⊂ A × A, где A = {a, b, c,d,e}, которое является нерефлексивное, симметричное, транзитивное, и построить его матрицу.
Bohdan's user avatar
  • 231
0 голосов
1 ответ
86 показов

Дискретная математика

По таблице истинности найти формулы, определяющие функции f1(x1,x2,x3), f2(x1,x2,x3), и придать им более простой вид:
laapa's user avatar
  • 19
1 голос
1 ответ
418 показов

Упростить вид множества

Упростить вид множества, заданной с помощью операций, применяя законы алгебры множеств (в ответ множества могут входить не более одного раза): (A ∩ ¯B)∆(¯A ∩ B) А как дальше? Могу ли я взять ¯B и ...
Bohdan's user avatar
  • 231
1 голос
0 ответов
147 показов

Записать условие задачи с помощью алгебры логики

Помогите, пожалуйста, записать условие задачи с помощью алгебры логики. Три дочери писательницы Дорис Кей — Джуди, Айрис и Линда — тоже очень талантливы. Они приобрели известность в разных видах ...
TheKnight's user avatar
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 ...
grvctr's user avatar
  • 11
3 голоса
2 ответа
10k показов

Числа Рамануджана

Есть известное число Рамануджана - 1729. Это наименьшее число, выражаемое как сумма двух кубов двумя разными способами. Другими словами: 1729 = 1^3 + 12^3 = 9^3 + 10^3. Какие есть еще числа ...
fox_price's user avatar
  • 177
7 голосов
0 ответов
139 показов

Улучшение алгоритма подсчета количества пар, чье побитовое И является степенью 2

Как можно улучшить алгоритм считающий количество неупорядоченных пар в массиве, чье побитовое И является степенью 2? Например, если массив равен [10,7,2,8,3]. Ответ 6. Объяснение: 10 & 7 = 2 10 &...
NTP's user avatar
  • 3,161
0 голосов
0 ответов
26 показов

Почему автор статьи использует дробь если должны быть целые числа?

Автор в этой статье описывает метод инициализации сложности темы. Вот здесь (ниже на скрине) он говорит что определят уровень преимущества одной темы над другой с помощью шкалы Саати (цифры от 1 до 9)...
ADam Carraway's user avatar
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%...
Lesha Cherkasov's user avatar
0 голосов
1 ответ
155 показов

Задача с палочками

У Андрея есть палочки с целочисленными длинами и общей длиной 200. Ни из каких трёх нельзя составить треугольник. Какое наибольшее число палочек может быть? Я знаю что любая палочка должна быть ...
artem_tmm's user avatar
0 голосов
0 ответов
28 показов

Полнота условий

Всем доброго времени суток. Есть задача, которую не понимаю как можно красиво алгоритмически решить. Условие: Пользователь может задавать набор правил(условия для предикатов), для примера, рассмотрим ...
Denis Markov's user avatar
3 голоса
1 ответ
279 показов

Замкнутость множества из книги Кострикин А.И. 1977 г

помогите понять элементарную алгебру. В книге Введение в Алгебру Кострикина А.И. есть утверждение. Множество S = {4k+1 | k = 0, 1, 2 ...}. Оно замкнуто относительно умножения (4k1 + 1)(4k2+1) = ...
Павел's user avatar
2 голоса
1 ответ
120 показов

как реализовать остаток от деления в обратную сторону?

Предположим У меня сейчас такой код в цикле C++ a = (a+3) % (13) Я получаю такие результаты 3 6 9 12 2 5 Теперь я бы хотел сделать другой цикл в обратной последовательности. Где ...
user362551's user avatar
0 голосов
0 ответов
143 показа

Реализация функции с помощью алгоритма Стаи серых Волков

Задавал вопрос по этому же примеру, но с реализацией по генетическому алгоритму. Сейчас мне нужно реализовать этот же пример, только с помощью алгоритма Стаи серых Волков. Есть у кого-то примеры с ...
Богдан Донченко's user avatar
1 голос
1 ответ
1k показов

Композиция бинарных отношений (на матрице) равна произведению матриц бинарных отношений?

Композиция бинарных отношений (на матрице) равна произведению матриц бинарных отношений?
Orizz's user avatar
  • 133
0 голосов
0 ответов
42 показа

Построить КДА, который по двоичному разложению числа a строит двоичное разложение числа 3а

Построить кда который по двоичному разложению числа "a" строить двоичное разложение числа "3а" Можете пожалуйста обьяснить что вообще это за автомат такой? на вход подаётся только буква "a"? или ...
Сергей Александров's user avatar
-1 голос
1 ответ
68 показов

Вопрос к знающим дискретную математику [закрыт]

Можно ли браться за "Алгоритмы. Построение и анализ." Кормена со школьными знаниями математики? Если же нет, посоветуйте вводную литературу, за счет которой можно подготовиться к Кормену.
Max's user avatar
  • 331
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-&...
Сергей Александров's user avatar