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

Вопрос, возможно, немного глупый, но я так и не разобрался по литературе.


Что будет если подать строчку 001 на вход детерминированного конечного автомата, изображенного на картинке?

Почему то в темах нет "теории автоматов"...

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

01:54 

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

Med-ved
Пушист. Чешите.
Доброго времени суток! нужна ваша помощь :)
Прошу привести и объяснить способ проверки автомата на синхронизируемость, помочь разобраться с рациональными отношениями в контексте автоматов и регулярных языков.
Заранее спасибо.

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

21:04 

Лампочки

wpoms.
Step by step ...


На распределительном щите имеется `a` строк с выключателями по `b` выключателей в каждой (`a` строк и `b` столбцов), каждый выключатель соединен с лампочкой в одном из домов. При нажатии выключателя, соответствующего некоторому дому, вместе с лампочкой данного дома изменяют состояния лампочки домов, стоящих в одной строке и одном столбце с данной (включенные, гаснут, выключенные загораются).
Для каких величин `a` и `b` возможна ситуация, в которой после серии переключений окажется включена только одна лампочка?



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

00:24 

Дети

wpoms.
Step by step ...


В математическом лагере `2010^2010` детей. Каждый имеет в лагере не более трех друзей и, если `A` дружит с `B`, то `B` дружит с `A`. Начальник лагеря хочет построить детей в ряд, так чтобы между любой парой друзей стояло не более `2010` детей. Всегда ли это можно сделать?



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

22:03 

Игра

wpoms.
Step by step ...


На прямоугольной доске размером `5 xx 9` играют в игру. Сначала некоторое количество дисков помещают случайным образом в квадраты доски, при этом в каждый квадрат помещают не более одного диска. Ход заключается в перемещении всех дисков из квадратов, в которых они находились, в другие квадраты, с соблюдением следующих правил:
(a) каждый диск можно переместить на один квадрат вверх, вниз, влево или вправо относительно того квадрата, в котором он находится;
(b) если диск переместили вверх или вниз в рамках одного хода, то следующим ходом его нужно будет перемещать влево или вправо;
(c) если диск переместили влево или вправо в рамках одного хода, то следующим ходом его нужно будет перемещать вверх или вниз;
(d) по завершении перемещения всех дисков в рамках одного хода ни один квадрат не должен содержать более одного диска.
Игра завершается, если нет возможности переместить все диски в рамках одного хода по указанным выше правилам. Докажите, что если в начале игры на доске разместили `33` диска, то игра в конце концов завершится. Докажите, что можно разместить на доске в начале игры `32` диска таким образом, чтобы игра могла продолжалась бесконечно.



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

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. Вот мои соображения я построил табличку и получил, что данное отношение является не рефлексивным, не симметричным, транзитивным. До отношения эквивалентности можно дополнить одним способом. Правильно ли? И как быть дальше?

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

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

главная