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

построить машину Тьюринга

Построить для функции f(x,y)=x, если x>y; y, если x<y; 0, если x=y
какая идея построения?

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

13:30 

Доказательство нескольких утверждений по графам

Никак не получается, понять как грамотно доказать некоторые утверждения, например:

1) Доказать, что если в графе (без петель и кратных ребер) более 4 вершин, то либо в самом графе, либо в его дополнении содержится цикл.
попытки доказать

2) Если v - разделяющая вершина графа, то она не является разделяющей в его дополнении.

домыслы

3) Показать, что самодополнительный граф связен

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

14:11 

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

Вот не приходят идеи мне к этим 2 задачкам по теории графов:
1) Доказать, что в мультиграфе всякий замкнутый маршрут нечетной длины l>=3 содержит простой цикл. Доказать, что это несправедливо для маршрутов четной длины.
мои мысли
2) Пусть p(G) - наименьшая из степеней вершин графа G, не имеющего петель и кратных ребер и содержащего n вершин (n >= 2)
Доказать, что если p(G) >= (n-1)/2, то граф связен.
очевидное рассуждение

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

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`.

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

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

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


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

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

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

главная