Записи с темой: дискретная математика (список заголовков)
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. Возможно ли такое? Как поступать дальше?

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

10:28 

Исчисление предикатов

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

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

08:19 

Дискретная математика (Вычислить КНФ)

Всем привет.
Возник вопрос по поводу КНФ
Условие задания:
Вычислить КНФ БФ от трёх переменных `((X ^^ Y) vv (Z + X)) -> Z`

Более наглядное(и удобное) изображение задания:
изображение задания

Вот таблица для этой функции:
читать дальше

1 способ
Табличный
СКНФ:
читать дальше
Получается, здесь всё? При дальнейшем упрощении будет уже ДНФ а не кнф. (не икс v Z).

2 способ
Эквивалентности
Последняя строка будет такой:
читать дальше
При дальнейшем умножении скобок, будет ДНФ.

Ну и собственно вопрос: почему ответы не сходятся? И какой из них правильный?

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

05:53 

Дискретная математика. Полугруппы

всем здравствуйте

1-й курс Каунасского технологического университета (Литва), бакалавриат прикладной математики

ломаю зубы об дискретную математику.
делаю домашнее задание - программу генерирования полгрупп - т.е. ввожу элементы множества "a,b,c," и программа генерирует все возможные варианты квадратной матрицы-таблицы Келли, и проверяет ассоциативность и коммутативность (выбирает из них Абелевые группы)

скажите пожалуйста сколько всего полугрупп получается (чтобы я знал правильно программа работает или нет) из множетва из 2-х, 3-х, 4-х, 5-ти элементов
как посчитать количество всех возможнх вариантов таблиц Келли полугрупп?
в какой книге это можно посмотреть?

если кому нужно - могу исходный код программы сбросить как сделаю. мне не жалко. уже некоторая часть работает.

так например для множества [a,b,c] количество вариантов строк матриц - 3*3*3 = 27, количество всех возможгных матриц - 19683, из них полугрупп - 273. правильно ли это?

по идее я должен уловить закономерность и сделать генерацию таблиц Кэли полугрупп для большого числа элементов (типа [a,b,c,d,f,...])оптимизированно, поскольку если перебирать все варианты, то очень резко растёт время расчёта

помогите пожалуйста !!!
в какой литературе это можно посмотреть? а то так таблицы Кэли для полугрупп никто не рассматривает, по крайней мере я пока не нашёл
по идее я должен заметить закономерность в полученных полугруппах для малого числа элементов и спроецировать её для экономной генерации полугрупп для большого числа элементов (так как время счёта очень резко увеличивается уже для 5 элементов, если рассматривать все варианты)
и где это можно посмотреть или подскажите как это сделать (я постараюсь сам, но если это можно посмотреть в литературе, было бы здорово)


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



помогите пожалуйста, сессия горит. крайний срок сдачи - среда

P.S. (вопрос модераторам - я правильно спрятал под кат? - если не так, то исправлю)

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

09:32 

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

IWannaBeTheVeryBest
Всем привет. Не нашел нигде, кто бы мог решить вот эти 2 задачки или хотя-бы поставить на правильный путь.
1. "Доказать, что если P - силовская подгруппа в G, то нормализаор нормализатора P равен нормализатору P"
Ну начну с того, что знаю.
Порядок конечной группы - это мощность или количество элементов этой группы. Пусть `G` — конечная группа, а `p` — простое число, которое делит порядок `G`. Подгруппы порядка `p^t` называются p-подгруппами. Выделим из порядка группы `G` примарный делитель по `p`, то есть `|G| = p^ns`, где `s` не делится на `p`. Тогда силовской p-подгруппой называется подгруппа `G`, имеющая порядок `p^n`.
Определение нормализатора группы
`N_G(P) = {g in G | gP = Pg}`
Ну я это понимаю как множество всех элементов в G которые коммутируют со всеми элементами в P.
С чего бы начать? Я просто очень слабо в этом соображаю.
Ну вот предположим, что G - группа, с какими-то рандомными элементами.
Скажем, что мощность или порядок G = 90. Простое число p = 3 делит порядок G = 3^2 * 10, где 10 не делится на 3. Таким образом у нас есть 3-подгруппа силовская, имеющая порядок 3^2. Так вот, нам надо опеделится с тем, что такое этот номализатор скажем 3-группы. Так что это? Ну это какое-то множество элементов, которые коммутируют со всеми элементами нашей 3-группы. Нормализатор нормализатора в моем представлении - это и есть наша 3-группа. Вот тут то и начинаются странности


2. "Пусть S - полугруппа эндоморфизмов End V линейного пространства V (умножение - композиция эндоморфизмов). Доказать, что любой идеал в S - главный. (т.е. порождаетсяодним элементом)"
Плииииз хоть кто-нибудь, хоть немного.

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

20:22 

Еще немного дискретной математики

blackhawkjkee
Возникли проблемы с парой вещей:

1) Как показать транзитивное замыкание на этом графе?


2) Даются числа в следующем порядке: 7 5 6 4 3 8 1
Необходимо построить двоичное дерево поиска исходя из заданных цифр.

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

19:13 

Свойства бинарных отношений на множестве и замыкания

blackhawkjkee
У меня возник еще один вопрос по поводу свойств.
Собственно, предположим что на множестве `A = {1,2,3,4}` задано отношение `R = {(1,2),(3,4),(4,2)}`

С замыканием `R` относительно симметричности и рефлексивности я вроде разобрался, но с остальными свойствами, такими как: антисимметричность, антирефлексивность и транзитивность, я разобраться до конца не смог.
Есть предположения насчет антисимметричности:
`R^1 = {(1,2),(3,4),(4,2);(2,4),(4,3),(2,1)}` - верно ли это?

И насчет замыкания относ-но транзитивности, вот правильное замыкание:
`R^1 = {(1,2),(3,4),(4,2);(2,3)}`

Почему `(2,3)`? Можете по-подробнее объяснить или предоставить какой-нибудь пример(желательно в той же тематике что и выше)?

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

16:56 

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

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

Предположим, есть `A={1,2}, B={3,4}, C={5,6)`
`A` x `B = {(1,3),(1,4),(2,3),(2,4)}`
Чтобы найти `A` x `B` x `C` необходимо ли использовать уже составленное декартово произведение выше или это необязательно?

Также нашел вот такое свойство:
Количество элементов в декартовом произведении равно произведению чисел элементов множеств-сомножителей (в случае их конечности, разумеется):
`|A`×`B|=|A|*|B|.`

Как будет формулироваться подобное свойство для, например, трех множеств? `|A|*|B|*|C|?`

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

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

главная