Записи с темой: дискретная математика (список заголовков)
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|?`

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

20:30 

Раскраска домов

wpoms.
Step by step ...


На улице Антонио сто домов, пронумерованных числами от единицы до ста. Любой дом, чей номер равен разности номеров домов, покрашенных в один цвет, покрашен в цвет отличный от цвета этих двух домов. Докажите, что на улице Антонио есть дома по крайне мере пяти разных цветов.



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

19:25 

Доказательство лемм

Добрый день,

В работе над курсовой работой у меня возникла потребность в доказательстве вспомогательных лемм. К сожалению, доказательство собственных теорем/лемм - самый слабый мой математический навык и я был бы благодарен за помощь в данной проблеме. Прочитал книжку Успенского про примеры математических доказательств, но ни на какие мысли это меня не натолкнуло.
Суть лемм состоит в следующем. У нас имеется модель процесса в виде сети Петри, а точнее ее развертки, которое можно рассматривать как параллельное исполнение, а также все возможные последовательные исполнения процесса. Я исследую отношения между событиями процесса: `>`: `e > e'` - если случилось событие `e'`, то `e` случилось до этого; `#`: `e # e'` - события `e` и `e'` никогда не встречаются в одном последовательном исполнении; `e || e'` - `neg (e > e') wedge neg (e' > e) wedge neg (e # e')`. Так, например, для процесса на картинке, имеем следующие последовательные исполнения: `adc`, `acd`. `cad`, `b`. Т.е. события находятся в следующих отношениях: `a || c`, `d || c`, `a > d`, `a # b`, `c # b`, `d # b`.


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

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

10:03 

помогите если можно то с описанием решения

Отношение Т: «иметь один и тот же остаток при делении на 4» задано на множестве Х={6, 7, 8, 9, 10, 11, 12, 13}. Является ли оно отношением эквивалентности.

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

10:59 

помогите решить

задайте всеми известными способами соответствия между множествами Х={3,4,5,9} и Y={135,0,264,122} "число х является делителем числа y"

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

14:41 

Шарики

wpoms.
Step by step ...


В одной сумке лежит `m` шариков, в другой их `n` (`m, n > 0`). Можно выполнять две разные операции:
a) Удалить равное количество шариков из обеих сумок;
b) Удвоить количество шариков в одной из сумок.
Всегда ли возможно опустошить обе сумки с помощью конечной последовательности операций a) и b)?
Операцию b) заменяют на
b') Утроить количество шаров в одной из сумок.
Всегда ли возможно опустошить обе сумки с помощью конечной последовательности операций a) и b')?



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

12:19 

помогите решить

соответствия между множествами C = {1,2,3,4,5} и D={5,6,7} таково что его график состоит из пар в которых первая компонента взята из множества С а вторая из D и больше первой компаненты. Постройте граф этого соответствия , график этого соответствия в прямоугольной системе координат. Постройте граф противоположного соответствия , график противоположного соответствия в прямоугольной системе координат.

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

21:41 

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

Курс интересен практической направленностью, постоянно возникают задачи со сложными структурами, свойства которых приходится анализировать самостоятельно. Рекомендую его всем, кто хочет о комбинаторике узнать чуть больше, чем это даётся в стандартном курсе теории вероятностей. Я два модуля прошёл.

Пример среднего по сложности задания:

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

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

00:47 

Раскраска

wpoms.
Step by step ...


Стороны выпуклого `(L + M + N)`-угольника раскрашены в три цвета: `L` сторон красным, `M` сторон желтым и `N` сторон синим. Выразите в виде неравенств необходимые и достаточные условия такой раскраски, при которой две смежные стороны не окрашены одним и тем же цветом.



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

22:22 

Помогите док-ть ассоциативность умножения по модулю 5!Срочно!Пожалуйста!

Помогите док-ть ассоциативность умножения по модулю 5!

Введем на полученном множестве N5(0,1,2,3,4,5) операцию умножения по модулю 5. Так как 5 – простое число, то выполняются все аксиомы группы, что легко проверяется. Так, замкнутость следует из того, что произведение чисел, меньших простого модуля, не кратна ему.

Ассоциативность легко доказывается при переходе от сравнения к равенствам. ??? как это расписать,помогите,пожалуйста! с чего начать, как обозначить,записать на математическом языке не понимаю.

+ к какой математической модели (моноид, полугруппа, группа, кольцо, область целостности, поле, тело) относятся следующие множества (U) с заданными операциями.

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

19:23 

Композиция бинарных отношений - помогите понять

Задали найти композицию бинарных отношений,а я никак не пойму что откуда брать.
R1(x, y) = {(x, y) | x^2 = y}
R2(x, y) = {(x, y) | x = y^2}

Нужно найти R1 * R2 и R2 * R1?
Думал будет так : R1*R2 = sqrt(x)=y^2
R2*R1 = x=y
но оказалось не верно

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

21:06 

Найти коэффициент при x^6 в разложении многочлена

Найти коэффициент при x^6 в разложении многочлена
(1+2x^2-3x^4)^8

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

01:46 

Представить отношение R другими возможными способами

На множестве М бинарное отношение R c МхМ задано характеристическим свойством. Представить отношение R другими возможными способами. Выяснить какими свойствами оно обладает.
M = {-1,0,1,2,3,4}, R = { (х;у)|х+у<4; х,у є М }

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

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

главная