Записи с темой: дискретная математика (список заголовков)
10:40 

Задача из теории множеств

Доказать, что если отношения R1 и R2 рефлексивны, то рефлексивны отношения R1 объединение R2, R1 пересечение R2, R1 * R2, (R1)^-1

@темы: Дискретная математика, Бинарные отношения

23:56 

Перестановки

Помогите пожалуйста решить задачу
сколькими способами можно переставить буквы слова "баллада", чтобы две буквы "а" не шли рядом?
у меня в решении поучается всего перестановок 7!/3!/2!
берем две буквы а как одну 6!/2!/2!
берем три буквы а как одну 5!/2!
Итого 7!/3!/2!-6!/2!/2!+5!/2!=300

@темы: Комбинаторика, Дискретная математика

14:36 

Бинарные отношения?

Добрый вечер!
Подскажите, пожалуйста, как проверить свойства?

Каким свойством обладает отношение R, заданное на парах положительных чисел.
`(a;b)R(c;d) <=> a^2-d^2=b^2-c^2`

@темы: Бинарные отношения, Дискретная математика

11:43 

Доказать или опровергнуть формулу (A\B)\C=(A\C)\(B\C).

Подскажите, пожалуйста, как доказать или опровергнуть формулу (A\B)\C=(A\C)\(B\C).
Кроме диаграмм эйлера-Венна ничего в голову не приходит(( будут ли диаграммы доказательством?

@темы: Дискретная математика

15:09 

Теоремы Силова

Здравствуйте, проблем с теорема Силова, а точнее с их доказательствами
не могла бы вы подсказать доказательства теорем простым язык чтоле или привести свое:)
смотрел в книге Каргаполова, Мерзлякова
ну очень там сложно, в особенности теорема о существовании и сопряженности
спасибо всем)

@темы: Высшая алгебра, Дискретная математика, Литература, Теория групп

14:37 

Максимальный поток, минимальный разрез в сетевом графе.

adolescence
Есть задача: Найти максимальный поток, минимальный разрез. Должна быть таблица с "достижимыми" вершинами на каждом шаге. В ответе должна быть величина потока и ребра, входящие в разрез.

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

Заранее спасибо за помощь)

@темы: Дискретная математика

22:41 

Сложность факторизации

Здравствуйте! Меня интересует вопрос: а почему разложение на простые множители такое сложное? Если будем перебирать числа от `1` до `sqrt(n)`, то сложность алгоритма будет всего-то `sqrt(n)`. Общая сложность: `O(sqrt(n) log_2^2 n)` - это я нашел в интернете. Так вот, это же полиномиальная сложность, так как `sqrt(n) log^2 n < n^(2.5)`. Даже некоторые алгоритмы сортировок массивов имеют сложность `O(n^2)` - тот же пузырёк. Так что же сложного в этом?

@темы: Теория чисел, Дискретная математика

20:07 

Сад камней

wpoms.
Step by step ...


Пусть `n` - натуральное число, большее `2`. У Ванессы есть `n` кучек нефритовых камней с различным количеством камней в кучках. Она может распределить камни из любой кучки среди остальных и получить `n - 1` кучку с равным количеством камней. Она может распределить камни из любых двух кучек среди остальных и получить `n - 2` кучки с равным количеством камней. Определите наименьшее возможное количество камней, которое может находиться в кучке с наибольшим количеством камней?



@темы: Дискретная математика

21:02 

Задача по теории графов

Республиканская олимпиада 10 класса 2007 года в РБ.
читать дальше

@темы: Теория графов, Дискретная математика

21:01 

Задача по теории графов

Городская олимпиада 11 класса 1999 года в РБ.
читать дальше

@темы: Теория графов, Дискретная математика

17:08 

Игра

wpoms.
Step by step ...


Нельсон предложил Тельме поиграть в такую игру:
Тельма стирает `2^9` чисел из множества `{0,1, 2, 3, ..., 1024}`, затем Нельсон стирает `2^8` чисел, после этого Тельма стирает `2^7` чисел и так далее пока не останутся только два числа. По завершении игры Нельсон выплачивает Тельме разницу между этими двумя числами в евро. Какую наибольшую сумму может выиграть Тельма вне зависимости от стратегии Нельсона?



@темы: Дискретная математика

15:25 

Построить отношение на множестве

Кошка
В Содоме и Гоморре солнечно.
Всем добрый день!

Есть множества:

`S = {a, v, d, k, o, p, r, s, u, y}`
`T = {a, g, l, o, y}`

и третье, являющееся их объединением:

`A_1 = S uu T = {a, v, g, d, k, l, o, p, r, s, u, y}`

Надо построить такое отношение R на множестве `A_1`:

`(а_11 in А_1; а_12 in А_1) Rightarrow (а_11 R а_12 Leftrightarrow ((а_11 in S; а_12 in T) uu (а_11 in S; а_12 in T)))`

Это в точности то, что у меня сейчас есть, и условие пока уточнить не могу. Я не понимаю, зачем там значок следования после указания, что оба элемента принадлежат множеству `A_1`. Но допустим, что первая часть записана верно.

Вопрос: для построения отношения тут, скорее всего, имеется в виду, что:

1) условие, при котором между элементами `а_11` и `a_12` имеется отношение R, надо упростить и получить:

`(а_11 in А_1; а_12 in А_1) Rightarrow (а_11 R а_12 Leftrightarrow (а_11 in S; а_12 in T))`

или

2) тут, видимо, перепутаны индексы и должно быть что-то вроде:

`(а_11 in А_1; а_12 in А_1) Rightarrow (а_11 R а_12 Leftrightarrow ((а_11 in S; а_12 in T) uu (а_12 in S; а_11 in T)))`

с 12 перед 11 во второй части условия (иначе зачем она вообще нужна)?

@темы: Бинарные отношения, Дискретная математика

18:38 

Дискретка

pol_lemura
забудем того тебя, который живет в зеркале
Объясните пожалуйста, как это сделать?

Нарисовать граф, вершины которого - указанные множества и две вершины считаются смежными, если пересечение множеств не пусто.
Есть множество X и три его подмножества: A, B, C.

@темы: Дискретная математика

11:43 

Количество отношений строгого порядка

Здравствуйте!

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

Сколько существует различных неэквивалентных отношений строгого порядка на конечном множестве альтернатив, состоящем из n элементов?

Спасибо.

@темы: Дискретная математика, Комбинаторика

21:32 

Бинарные отношения на бесконечном множестве

Горе-гуру
Это неважно, если ты счастлив
Задание: построить на бесконечном множестве отношение, обладающее следующим набором свойств: рефлексивное (не антирефлексивное), антисимметричное (не симметричное), не транзитивное и связное. Отношение требуется задать словесно. Оба элемента отношения принадлежат одному множеству.

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

@темы: Бинарные отношения, Дискретная математика

23:00 

Задача по изоморфизму регулярных графов

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

Условие: "Докажите, что любые два регулярных графа типа (10,8) (10 вершин, из каждой выходит по 8 ребер) изоморфны".

Подскажите, пожалуйста, как подходить к задачам такого рода и доступную литературу по этой теме.

@темы: Посоветуйте литературу!, Дискретная математика

17:10 

если `A \subseteq \delta_{f} \edge B \subseteq \rho_{f} => f (f ^{-1} (B))= B `

Здравствуйте уважаемое сообщество.

1 курс каунасского технологического университета. домашнее задание по дискретной математике

нужно доказать, что
если `A \subseteq \delta_{f} \edge B \subseteq \rho_{f} => f (f ^{-1} (B))= B `

Как следует из задания , нам даны функциональное и обратное ему соответсвие, в соответствии с определениями (6.7),
они являются однозначными, `f` и обратны`f^{-1}` и множество `A` \ в \ `delta {F} `является прототипом и
`A \subseteq ` pr`_1 G`, а множество ` B \subseteq \rho_{f}` есть образ множества `A` и `B \subseteq ` pr`_2 G`, где `G` функциональное соответствие `f`.

читать дальше
В первом случае (а) проблемы не возникет, и решение таково

поставим очерёдность рассмотрения операций
читать дальше
что должно бтть первым, а что - вторым?

Использованные определения:
читать дальше
----------------------------------------------------------
надеюсь это не будет большой наглостью с моей стороны.
сейчас работа приобрела такой видчитать дальше


заранее спасибо

@темы: Дискретная математика, Множества

04:45 

дискретная мтематика. Множества . A∩B⊆C <=> A⊆bar{B}∪C

Здравствуйте уважаемое сообщество

не получается решить задание. домашняя работа, 1 курс прикладной математики Каунасского Технологического университета

нужно доказать что

`A nn B subseteq C iff A subseteq bar{B} uu C`



попытка решения под катом

читать дальше

выражение эквивалентности значит "тогда и только тогда, когда..."

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

что нужно сделать дальше? помогите пожалуйста.
я сам всё сделаю, подскажите направление, пожалуйста

@темы: Множества, Дискретная математика

17:50 

Дискретная математика. Множества (A\B)\C = (A\C)\(B\C)

Здравствуйте .

Дискретная математика, домашнее задание, 1-й курс Каунасского технологического университета.

доказать что (A\B)\C = (A\C)\(B\C)

вторую часть доказал (под катом)

читать дальше

@темы: Дискретная математика, Множества

06:25 

Алгоритм Дейкстры

Здравствуйте! С помощью алгоритма Дейкстры ищу кратчайшие пути. В третьей итерации получается, что три временные вершины имеют значение 5. Возможно ли такое? Как поступать дальше?

@темы: Дискретная математика, Математическая логика, Теория графов

Не решается алгебра/высшая математика?.. ПОМОЖЕМ!

главная