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

Здравствуйте! Помогите, пожалуйста, решить задачу по дискретной математике.
Задача.
Определить планарен граф или нет. Если планарен, то построить ему плоский изоморфный, если не планарен, то доказать его непланарность по теореме Портнягина-Куратовского.

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

23:22 

Теория графов и конечные автоматы

Двадцать_Семь
// иногда мне кажется, что компилятор игнорирует все мои комментарии (c)
Добрый день.
Оставили тему на самостоятельное изучение, а я ее не понимаю. Объясните, пожалуйста, как найти язык допускаемый конечным автоматом?

Автомат задан набором `({a,b},{q_1,q_2,q_3,q_4,q_5}, Q_s, Q_f)`, где {a,b} - алфавит,`Q_s` -множество начальных состояния, `Q_f` - множество конечных состояний. Запись `(i,j,a,b)` означает, что дуга (i,j), идущая из `q_i` в `q_j` имеет метки a,b:
Входы: `Q_s={1}`
Выход: `Q_s={3,4}`
Дуги: (1,5,b),(1,4,a),(2,1,b),(2,2,a),(5,4,b)
`L_0=a^m ba^n | n,m >= 0}`
1. Построить граф автомата и найти язык L, допускаемый автоматом.
Вот какой у меня получился граф:
читать дальше
У меня даже нет конкретных вопросов, потому что я не понимаю, что мне надо делать дальше(((

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

18:07 

Saiyuri-chan
Every moments and times are special.© L is so cute, you could die. Really! ©
Надо определить является ли число числом (L-R) типа.
Число

Вообще, мне хотелось бы понять, как в целом это все определяется. Я конечно прочитала, что должно быть выполнено три условия, но вот первое же действие в пособии поставило меня в тупик...
Первое действие

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

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

21:16 

СКНФ

Строю СКНФ ((y+¬x)->(y|x)((y¬x)~z) по таблице истинности и получаю: (¬x+¬y+¬z)(¬x+¬y+z)(¬x+y+¬z)(x+¬y+z)(x+y+¬z)(x+y+z). Теперь строю СКНФ с помощью эквивалентных преобразований и получаю результат, в котором пять членов совпадает, а один отличается: вместо (x+y+z) получаю (¬x+y+z). Я так понимаю, что СКНФ должна получится одинаковая. Много раз проверяю, ошибку найти не могу. Помогите пожалуйста.

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

11:44 

Графы

yoggik_wow
And I'm feeling good.
Добрый день.
Есть вот такая задачка:
Верно ли, что в вершинно k-связном графе любые k+1 вершин лежат на общей цепи?

Я нашла такую теорему, которая утверждает, что если граф k-связен, то любые k вершин принадлежат простому циклу.
Далее я отталкивалась уже от определений. Раз у нас есть k вершин в простом цикле, то это значит, что они различны. А т.к граф k-связен, то у него k+1 вершина, и эта еще одна вершина тоже будет различной (правда не до конца понятно почему). Отсюда следует, что все вершины и ребра различны, а значит это определение общей цепи.

Хотелось бы узнать, правильны ли мои рассуждения?

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

13:44 

Сколько функций содержит множество?

Дано вот такое множество :
( L - T0 ) U T1

Вот мои попытки решения :
Для начала разберемся с операциями, операция '-' - означает, что нужно найти такие элементы, которые есть только в L и только в T0...
Запишем линейное представление функции :
a0 + a1x1 + a2x2 + ... + anxn
Теперь разберемся с T0 в этой функции, для этого просто подставим заместо x - нули, и приравняем наше L к 0.
Т.е имеем :
a0 + a1 * 0 + a2 * 0 + ... + an * 0 = 0 => a0 = 0, а все остальное комбинируем как хотим -> получаем что мощность вот таких функций = 2 ^ n( ну т.е линейных, где фиксировано a0 )...
Теперь у меня возникает вопрос, а мощность множества ( L - T0 ) чему будет равна ?
Вот такие варианты есть, либо 2 ^ n, либо |L| - 2 ^ n + |T0| - 2 ^ n ???

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

15:26 

Конечные автоматы

Med-ved
Пушист. Чешите.
Доброго времени суток. Прошу помощи.
Построить автомат с выходом, который возвращает количество букв а после самой левой буквы b в слове {a,b}* по модулю 4.
И, пожалуйста, посоветуйте какие-нибудь материалы по конечным автоматам: алгоритм детерминации (детерминизации?), построение регулярного выражения по автомату.
Буду благодарен =)

к сожалению, не нашел темы "Конечные автоматы" =(

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

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

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

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

главная