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

Паросочетания

Найти максимальное паросочетание в двудольном графе, состоящем из дуг: A ->a, A->d,A->i,A->j,B->c,B->e,C->e,D->b,D->c,D->g,D->h,D->j,E->e,E->j.F->c,F->d,G->d,G->f,G->g,H->a,I->c,I->a,J->b,J->h,J->i.

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

16:34 

нахождение СДНФ

Мне нужно путем эквивалентных преобразований формулы получить СДНФ. У меня получилась такая формула: (~y&z)V(~y&~x)V(~z=y), где ~ - отрицание, = - равносильность. Особенно смущает равносильность: никаких преобразований с ней сделать не могу. Дальше нужно строить таблицу истинности, по ней смотреть, где формула принимает 1 и далее строить СДНФ? Или я ошибаюсь?

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

20:06 

Игра

wpoms.
Step by step ...


Рассмотрим следующую игру для одного игрока, играемую на оси `x`. Для каждого целого `k` обозначим `X_k` точку с координатами `(k, 0)`. Во время игры диски сложены в некоторых точках `X_k`. Выполняя ход игрок выбирает точку `X_j`, в которой находятся по крайней мере два диска, после этого он берет два диска из `X_j` и переносит один из них в точку `X_{j-1}` и другой в `X_{j+1}`.

В начале игры `2n +1` дисков находятся в точке `X_0`. Игра продолжается до тех пор, пока остается возможность сделать очередной ход. Докажите, что после `n(n + 1)(2n + 1)//6` ходов продолжение игры невозможно и что по завершении игры один диск находится в каждой из позиций:
`X_{-n}, X_{-n+1}, ..., X_{-1}, X_{0}, X_{1}, ..., X_{n-1}, X_{n} `.




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

14:04 

Планарные графы

Работаю над алгоритмом генерации/перебора всевозможных планарных графов на n вершинах. В общем, идея пока такова: генерирую всевозможные n-вершинные графы -> оставляю только планарные.
Как просто (с точки зрения алгоритма) проверить граф на планарность?

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

23:37 

Теория множеств

Необходимо определить мощность множества всех вещественных точек первой координатной четверти (`x >= 0`, `y >= 0`). В методичке нашел, что это множество является несчетным и мощность равна мощности континуума. Однако как это доказать. Необходимо установить взаимно однозначное соответствие между двумя этими множествами, т.е. задать функцию, которая каждой точке из первой четверти ставила бы точку из интервала (0,1). Помогите пожалуйста, в каком направлении двигаться?

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

02:25 

Апроксимация матрицы.

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

Есть матрица смежности:
`A=((0,1,0,0,0),(0,0,1,0,0),(-1,0,0,-1,0),(0,1,0,0,0),(-1,0,0,1,0))`

Как можно из этой матрицы получить матрицу B, такую что:
`A~~B={b_(ij)=(p_i)*(q_j)}`
?

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

17:33 

Контактно-релейные схемы

Задача на составление схемы. Из условия: Голосуют четыре человека A, B, C, D. D обладает правом вето. Помогите понять, что значит D обладает правом вето?

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

14:10 

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

A2kat
Поставил цель, добейся, и точка
Помогите разобраться. Какими свойствами обладает данное отношение? Какое минимальное число пар следует добавить к заданному отношению, чтобы оно стало отношением частичного порядка? Сколькими способами заданное отношение может быть дополнено до отношения линейного порядка, до отношения эквивалентности? Такое отношение DB,AE,AC,FB,FF,AA,EC. Вот мои соображения я построил табличку и получил, что данное отношение является не рефлексивным, не симметричным, транзитивным. До отношения эквивалентности можно дополнить одним способом. Правильно ли? И как быть дальше?

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

15:39 

Конюктивная нормальная форма

Может ли конъюктивная нормальная форма состоять только из элементарных дизъюнкций? Т.е. путем тождественных преобразований получился результат:
1&(P1VP2VP3)=P1VP2VP3

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

02:23 

Нормальные формы

A2kat
Поставил цель, добейся, и точка
Привести к СДНФ и СКНФ( совершенно дезъюнктивная (конъюктивная) нормальная форма) `(xo+y) subset (y equiv barz)`. Я не понимаю, как это делать с включением.

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

10:53 

ищу где скачать бесплатно книгу О.Курно

ищу где скачать бесплатно книгу О.Курно

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

12:57 

Scoun
Мне обещали, что я буду летать, но я все время ездил в трамвае.
"В стране `n` городов и некоторые из них соединены дорогами. Известно, что в стране нет ни одного замкнутого несамопересекающегося маршрута длины `4`. Докажите, что количество дорог не превосходит
`(n-1)^2/4`."
Натолкните, пожалуйста.

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

17:47 

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

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

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

15:37 

Рекурсивность

Функция `[sqrt(x)]` примитивно-рекурсивна, так как: `f(0)=0` и `f(x+1)=f(x)+bar(sgn)(|[(x+1)/(f(x)+1)]-f(x)-1|)`. Теперь вопрос, а будет ли функция `sqrt(x)` примитивно-рекурсивной или вообще рекурсивной? Просто попалась такая задача: будет ли функция `y=sqrt(x^2-5)` а) примитивно-рекурсивной? б) рекурсивной? Как я понял, нужно сделать так: `x^2-5=z^2, z in NN; (x-z)(x+z)=5 <=> x-z=1` и `x+z=5` или `x-z=5` и `x+z=1` . Теперь, так как `x in NN`и `z in NN`, то остается только первый вариант. Вот, а что уже делать с этим?

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

14:01 

Найти мощность множества многочленов с действительными коэффициентами.

Буду благодарна наводке и помощи!

1) Найти мощность множества комплексных чисел.
2) Найти мощность множества многочленов с действительными коэффициентами.

Мои "идеи" решения:
1)Все числа комплексного множества можно изобразить на плоскости с действительной и мнимой координатными осями и определить как упорядоченную пару вещественных чисел (x, y). Упорядоченные пары вещественных чисел -это элементы декартово произведения множества RxR, а декартово произведение множеств мощности континуум имеет мощность континуум.
Верно ли это?

2) а здесь пусто т.к. не нашла ничего похожего, на что ориентироваться и как математическим языком записать не знаю.

@темы: Дискретная математика, Множества, Функциональный анализ

21:13 

Дополнение до монотонной функии

Про функцию алгебры логики f(x, y, z) известно, что f(0, 1, 0)=0, f(1, 0, 1)=1. Дополните f до монотонной функции. Сколькими способами это можно сделать?
Нашла в учебнике Кузнецова определение монотонной функции:
Функция f(x1, ..., xn) называется монотонной, если для любых двоичных наборов а и b длины n из того, что a<=b, следует, что f(a)<=f(b).
Понимаю, что f(0, 1, 0)=0, и если f(0, 1, 1)=1, то эта функция будет монотонной
Не понимаю, как можно решить? :confused: Помогите, разобраться, пожалуйста:thnk:

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

22:26 

Пример задачи по кольцу вычетов по модулю n

Объясните, пожалуйста, что такое группа вычетов по модулю n на каком-то примере. Существуют ли решенные задачи по группе вычетов в виде разобранных примеров? Меня интересуют задачи вида: "...в группе вычетов по модулю 5 выписать циклическую подруппу порожденную элементом 3..."

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

21:16 

Соответствия

Существует ли функциональное, сюръективное, но не всюду определенное соответствие `f`: `[0;1] rightarrow (- oo;0)`
Могу ли я привести следующее соответствие: `f=-1/x+1`; Причем сделаем так: чтобы достичь не всюду определённости определим функцию на `(0;1]`; Так вот, вроде получившееся соотношение а)функционально (для каждого из `(0;1]` определён единственный элемент) б)сюръективно (для каждого из `(- oo;0)` соответствует не менее одного элемента) в) не всюду определено (не определено в `0`); Верен ли мой пример?

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

20:29 

Дискретная математика(бинарные отношения)

Для заданного бинарного отношения `P` найти область определения бинарного отношения `delta_p`, область значения бинарного отношения `rho_rho`, обратное отношение `P^(-1)`, композиции `P circ P` , `P^(-1) circ P`, `P circ P^(-1)`. `P={(x,y):x,y in RR` и `3x < 5y}`
С областью определения и областью значения всё ясно. Вопрос такой: я правильно понимаю, что `P^(-1)={(y,x):y,x in RR` и `3y < 5x}`, причем область определения и область значения также `RR` ? И, соответственно, как найти их композиции?

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

16:11 

Сокращенная ДНФ/КНФ и карта Карно

Прошу мне помочь определить с помощью карт Карно сокращенные ДНФ и КНФ.
Собственно что у меня есть на данный момент:

Далее с помощью карты Карно я определил минимальные ДНФ и КНФ:




Прошу объяснить, как это сделать.

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

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

главная