Отправляет email-рассылки с помощью сервиса Sendsay

RFpro.ru: Консультации по дискретной математике

Подписаться Бесплатная «Серебряная» новостная рассылка . Подписчиков 106 RSS
←   Июнь 2014   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


За последние 60 дней ни разу не выходила


Сайт рассылки: http://rusfaq.ru/issues/8/19/525
Открыта: 17-04-2009

Автор
Калашников О.А.

Статистика

106 подписчиков
0 за неделю
←   Все выпуски   →

RFpro.ru: Консультации по дискретной математике


Хостинг портала RFpro.ru:
Московский хостер
Профессиональный ХОСТИНГ на базе Linux x64 и Windows x64

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Лучшие эксперты по данной тематике

Асмик Гаряка
Статус: Советник
Рейтинг: 10866
∙ повысить рейтинг » 		Коцюрбенко Алексей aka Жерар
Статус: Советник
Рейтинг: 4005
∙ повысить рейтинг » 		CradleA
Статус: Бакалавр
Рейтинг: 2050
∙ повысить рейтинг »

/ НАУКА И ОБРАЗОВАНИЕ / Точные и естественные науки / Математика дискретная

Номер выпуска:325
Дата выхода:11.06.2014, 15:09
Администратор рассылки:Асмик Гаряка (Советник)
Подписчиков / экспертов:17 / 35
Вопросов / ответов:3 / 5

Консультация # 177970: Здравствуйте, уважаемые эксперты! Помогите, пожалуйста, с теорией вероятности ещё раз. Задача такая: И, если можно, опять-таки с небольшими комментариями. Спасибо большое!...

Консультация # 110501: Здравствуйте, уважаемые эксперты! Помогите пожалуйста решить следующие задачи: тема БУЛЕВАЯ АЛГЕБРА 1) проверить 0 принадлежит ли [{x+xy+yz, x}] 2) найти число функций, существенно зависящих от 2х переменных 3)решить систему x+y+z=1; (x->y)vz=0 то есть состоит система из двух уравнений ОЧЕНЬ БОЛЬШОЕ СПАСИБО !! С уважение...
Консультация # 183013: Здравствуйте! Прошу помощи в следующем вопросе: 1. Все перестановки 7 чисел (1;2;3;4;5;6;7) упорядочены в лексикографическом порядке. Какой по счету идет перестановка 6153742 ? 4. Постройте наибольшее паросочетание для двудольного графа G. Первая доля состоит из вершин {a,b,c,d,e,f,g}, вторая доля - из вершин {α,β,γ, ...

Консультация # 177970:

Здравствуйте, уважаемые эксперты! Помогите, пожалуйста, с теорией вероятности ещё раз. Задача такая:



И, если можно, опять-таки с небольшими комментариями. Спасибо большое!

Дата отправки: 22.04.2010, 01:34
Вопрос задал: MrSpencer
Всего ответов: 2
Страница онлайн-консультации »

Консультирует Лиджи-Гаряев Владимир:

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

Уточним f(x). Площадь треугольника должна быть равна 1, следовательно f(1)=1.
Уравнение прямой, проходящей через точки (-1;0) и (1;1) -> f(x)=(x+1)/2
Получим
f(x)={0,x<-1
(x+1)/2, -1≤x<1
0,x≥1}

my=M(y(x))=∫-∞∞y(x)*f(x)dx=∫-11(1-x2)*((x+1)/2)dx=(1/2)*∫-11(x-x3+1-x2)dx=2/3

dy=∫-∞∞(y(x)-my)2*f(x)dx=∫-11(1-x2-2/3)2*((x+1)/2)dx=4/45

Т.е. для my и dy используются формулы mx и dx для случайной величины x, в которых вместо x ставится y(x).

Консультировал: Лиджи-Гаряев Владимир
Дата отправки: 22.04.2010, 23:51

5
Спасибо!
-----
Дата оценки: 24.04.2010, 22:59
Рейтинг ответа:

НЕ одобряю +1 одобряю!

Консультирует Andy (Модератор):

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

Задана плотность f(x) распределения случайной величины X. Случайная величина Y связана со случайной величиной X зависимостью Y = 1 – X2. Требуется найти математическое ожидание M(Y) случайной величины Y (двумя способами) и ее дисперсию D(Y).

Рассмотрим сначала плотность f(x) распределения случайной величины x. Площадь S треугольника, изображенного на рисунке, ограниченного сверху кривой распределения (графиком функции f(x)), а снизу осью абсцисс, равна 1. Поэтому S = 1/2 ∙ (1 – (-1)) ∙ f(1) = 1/2 ∙ 2 ∙ f(1) = f(1) = 1, откуда f(1) = 1.

Уравнение прямой f(x) найдем как уравнение прямой, проходящей через точки (-1; 0) и (0; 1):
(x + 1)/(1 + 1) = (f – 0)/(1 – 0),
f = x/2 + 1/2.
Вне отрезка [-1; 1] плотность распределения случайной величины X равна нулю. Поэтому аналитическое выражение кривой распределения случайной величины X, показанное на рисунке, имеет вид
f(x) = x/2 + 1/2, есл и -1 ≤ x ≤ 1,
f(x) = 0, если -∞ < x < -1 или 1 < x < ∞.

Имеем Y = 1 – X2 и M(Y) = M(1 – X2) = M(1) – M(X2). Находим
M(X2) = -1∫1 x2 ∙ f(x)dx = -1∫1 x2 ∙ (x/2 + 1/2)dx = -1∫1 (x3/2 + x2/2)dx = (x4/8 + x3/6)|-11 =
= (1/8 + 1/6) – (1/8 – 1/6) = 1/3,
M(Y) = 1 – 1/3 = 2/3.

Находим дисперсию случайной величины Y:
D(Y) = D(1 – X2) = D(-X2) = (-1)2 ∙ D(X2) = D(X2) = M(X4) – (M(X2))2,
M(X4) = -1∫1 x4 ∙ f(x)dx = -1∫1 x4 ∙ (x/2 + 1/2)dx = -1∫1 (x5/2 + x4/ 2)dx = (x6/12 + x5/10)|-11 =
= (1/12 + 1/10) – (1/12 – 1/10) = 1/5,
D(Y) = 1/5 – (1/3)2 = 1/5 – 1/9 = (9 – 5)/45 = 4/45.

Ответ: M(Y) = 2/3, D(Y) = 4/45.

Вроде бы так...

С уважением.

Консультировал: Andy (Модератор)
Дата отправки: 22.04.2010, 23:55

5
Спасибо!
-----
Дата оценки: 24.04.2010, 22:59
Рейтинг ответа:

НЕ одобряю +1 одобряю!

Консультация # 110501:

Здравствуйте, уважаемые эксперты!
Помогите пожалуйста решить следующие задачи: тема БУЛЕВАЯ АЛГЕБРА
1) проверить 0 принадлежит ли [{x+xy+yz, x}]
2) найти число функций, существенно зависящих от 2х переменных
3)решить систему x+y+z=1; (x->y)vz=0 то есть состоит система из двух уравнений
ОЧЕНЬ БОЛЬШОЕ СПАСИБО !!
С уважением, Гуля.

Дата отправки: 22.11.2007, 10:27
Вопрос задал: Gul4atai
Всего ответов: 1
Страница онлайн-консультации »

Консультирует Воробьёв Алексей Викторович:

Здравствуйте, Gul4atai!

1) проверить 0 принадлежит ли [{x+xy+yz, x}]

Не могу ответить на эту задачу, так как не знаком с такой нотацией.

2) найти число функций, существенно зависящих от 2х переменных

Всего есть 16 функций от 2х переменных.
Нам не подходят 6 функций: всегда 0, всегда 1, всегда равна первой переменной, всегда противоположна первой переменной, всегда равна второй переменной, всегда противоположна второй переменной.
Остаётся 10 функций, которые существенно зависят от обеих переменных.

3)решить систему x+y+z=1; (x->y)vz=0 то есть состоит система из двух уравнений

Составьте таблицу истинности. Я обозначу функции буквами f и g:

x y z f g
0 0 0 0 1
0 0 1 1 1
0 1 0 1 1
0 1 1 1 1
1 0 0 1 0 ***
1 0 1 1 1
1 1 0 1 1
1 1 1 1 1

Я обозначил звёздчками наше решение: x = 1, y = 0, z = 0.
Глядя на таблицу истинности можно найти и более "логическое" решение.
(x->y)vz=0 толькко когда x->y = 0 и z = 0, но x->y = 0 только когда x = 1 и y = 0.
x+y+z=1 будет выполняться всегда, кроме x = y = z = 0.
Таким образом, найденное решение удовлетворяет обоим уравнениям.

Консультировал: Воробьёв Алексей Викторович
Дата отправки: 22.11.2007, 11:47
Рейтинг ответа:

НЕ одобряю 0 одобряю!

Консультация # 183013:

Здравствуйте! Прошу помощи в следующем вопросе:

1. Все перестановки 7 чисел (1;2;3;4;5;6;7) упорядочены в лексикографическом порядке. Какой по счету идет перестановка 6153742 ?

4. Постройте наибольшее паросочетание для двудольного графа G. Первая доля состоит из вершин {a,b,c,d,e,f,g}, вторая доля - из вершин {α,β,γ,δ,ε,σ,η}. Ребра заданы следующим списком: {(a,ε)(a,η)(b,σ)(c,η)(d,α)(d,β)(d,γ)(d,δ)(d,η)(e,ε)(e,η)(f,γ)(f,σ)(g,γ)(g,ε)(g,η)}.

Дата отправки: 02.05.2011, 14:41
Вопрос задал: Посетитель - 351942
Всего ответов: 2
Страница онлайн-консультации »

Консультирует Andy (Модератор):

Здравствуйте, Посетитель - 351942!

Рассмотрим первую задачу. При упорядочении перестановок в лексикографическом порядке первой является перестановка 1234567, последней - перестановка 7654321.

1) Перед перестановкой 6153742 находятся перестановки, начинающиеся с цифр 1, 2, 3, 4, 5. Их количество равно 5 · 6! = 3600. Номер рассматриваемой нами перестановки не меньше числа 3600 + 1 = 3601.

2) Рассмотрим перестановку 153742. Цифра 1 является первой из возможных, поэтому номер перестановки не меняется.

3) Рассмотрим перестановку 53742. Перед ней находятся перестановки, начинающиеся с цифр 2, 3, 4 (цифра 1 уже использована). Их количество равно 3 · 4! = 72. С учётом рассмотренных выше перестановок, номер заданной перестановки не меньше числа 3601 + 72 = 3673.

4) Рассмотрим перестановку 3742. Перед ней находятся перестановки, начинающиеся с цифры 2 (цифра 1 уже использована). Их количество равно 1 · 3! = 6. С учётом рассмотренных выше перест ановок, номер заданной перестановки не меньше числа 3673 + 6 = 3679.

5) Рассмотрим перестановку 742. Перед ней находятся перестановки, начинающиеся с цифр 2, 4 (цифры 1, 3, 5, 6 уже использованы). Их количество равно 2 · 2! = 8. С учётом рассмотренных выше перестановок, номер заданной перестановки не меньше числа 3679 + 8 = 3687.

6) Рассмотрим перестановку 42. Перед ней находятся перестановки, начинающиеся с цифры 2. Их количество равно 1 · 1! = 1. С учётом рассмотренных выше перестановок, номер заданной перестановки не меньше числа 3687 + 1 = 3688.

Последний элемент перестановки роли не играет. Следовательно, искомый номер перестановки равен 3688.

Ответ: 3688.

С уважением.

Консультировал: Andy (Модератор)
Дата отправки: 02.05.2011, 16:24
Рейтинг ответа:

НЕ одобряю 0 одобряю!

Консультирует Асмик Гаряка (Советник):

Здравствуйте, Посетитель - 351942!


Паросочетание -- произвольное подмножество попарно несмежных ребер графа.
Максимальное паросочетание (maximal matching) -- паросочетание, которое не содержится в паросочетании с большим числом ребер.
Наибольшее паросочетание (maximum matching) -- паросочетание, в котором число рёбер наибольшее среди всех паросочетаний графа.

Двудольный (bipartite) граф -- такой граф, вершины которого (V) можно разделить на два множества (V+ и V-), так чтобы вершины каждого из множеств были попарно несмежны.

Определение
Пусть есть паросочетание в графе (V, E), обозначим его M (множество рёбер). M-чередующийся путь -- это путь в графе, содержащий поочерёдно рёбра из M и из (E\M).
Теорема
Паросочетание M является наибольшим тогда и только тогда, когда нет невырожденного M-чередующегося пути, начинающегося и заканчивающегося в вершинах, не инцидентных ни одному ребру из М.
Лемма
Если такой путь есть (обозначим его рёбра как P), то можно получить разбиение большее, чем M, следующим образом: M' = M⊕ P (симметрическая разность, или XOR).
Для решения задачи о паросочетании остается научиться находить увеличивающие пути или убеждаться, что таких путей нет.
Алгоритм прост -- начать с пустого паросочетания M={} и постепенно увеличивать его, находя M-чередующийся путь из теоремы и выполняя операции, указанные в лемме. Когда путь найти будет нельзя, это будет означать, что M -- наибольшее паросочетание.
Вначале все вершины ненасыщенные. Для построения начального паросочетания применим «жадный» алгоритм; будем просматривать по очереди вершины из первой доли, если из нее ведут ребра в ненасыщенные вершины из K будем жадно хватать и вводить в паросочетание первое попавшееся ребро, не думая о последствиях.

добавляем ребро M={(a,ε),(b,σ)(c,ο)(d,α)(f,γ)}

Далее, преобразуем двудольный граф G в ориентированный граф G’, введя ориентацию сл едующим образом:
все ребра, вошедшие в M, ориентируем снизу вверх, т.е. из второй доли в первую, а остальные ребра сверху вниз.
Очевидно, что увеличивающая относительно паросочетания M цепь существует в графе G тогда и только тогда, когда в графе B’ существует путь из s в t, где s -ненасыщенная вершина из 1 доли, t из второй.
Вершины g и e - ненасыщенные в верхней доле, β и δ во второй. Если среди достижимых вершин из g и e окажется вершина β или δ, есть увеличивающая относительно M цепь в графе G. В эти вершины путь ведет лишь из d, а туда лишь из α. В α не ведет ни одного пути. Значит, постороенное паросочетание наибольшее.

Консультировал: Асмик Гаряка (Советник)
Дата отправки: 05.05.2011, 22:45
Рейтинг ответа:

НЕ одобряю 0 одобряю!

Оценить выпуск | Задать вопрос экспертам

главная страница  |  стать участником  |  получить консультацию
техническая поддержка  |  восстановить логин/пароль

Дорогой читатель!
Команда портала RFPRO.RU благодарит Вас за то, что Вы пользуетесь нашими услугами. Вы только что прочли очередной выпуск рассылки. Мы старались. Пожалуйста, оцените его. Если совет помог Вам, если Вам понравился ответ, Вы можете поблагодарить автора - для этого в каждом ответе есть специальные ссылки. Вы можете оставить отзыв о работе портале. Нам очень важно знать Ваше мнение. Вы можете поближе познакомиться с жизнью портала, посетив наш форум, почитав журнал, который издают наши эксперты. Если у Вас есть желание помочь людям, поделиться своими знаниями, Вы можете зарегистрироваться экспертом. Заходите - у нас интересно!
МЫ РАБОТАЕМ ДЛЯ ВАС!

© 2001-2012, Портал RFPRO.RU, Россия
Авторское право: ООО "Мастер-Эксперт Про"
Калашников О.А. | Гладенюк А.Г.
Версия системы: 2011.6.36 от 26.01.2012
В избранное