• ↓
  • ↑
  • ⇑
 
Записи пользователя: MestnyBomzh (список заголовков)
22:57 

Жорданов базис

Хелп! Завтра контрольная, нужно понять алгоритм поиска Жорданового базиса, помогите! Дана матрица `A=((3,2,-3),(4,10,-12),(3,6,-7))`. Нужно найти ее Жарданов базис, собственные вектора уже успешно найдены`(-2,1,0);(3,0,1)`, cобственное число `lambda=2` осталось выяснить как найти злосчастный присоединенный. Ищем его при поомщи линейной комбинации собственных векторов `(A-2E)h=alpha ((-2),(1),(0))+ beta ((3),(0),(1))`. Подбираем альфа и бета так, чтобы система была совместимой, то есть `alpha=4`, `beta=3`. Получаем уравнение `x_1=-2x_2+3x_3+1`; Получается опять два вектора в ФСР, какой из них брать?

@темы: Линейная алгебра

14:14 

Область значения функции, неразрешимое множество

Возник спор: можно ли подобрать такую функцию, множество значений которой будет неразрешимым? Не могли бы вы мне помочь подобрать такой пример?

@темы: Математический анализ, Исследование функций

23:32 

Что бы это могло быть?


Собственно, вопрос про некоторую неизвестную букву `I`. Тема - комплексные числа, пространства, линейные операторы, так что есть подозрение на мнимою единицу, но чтобы так её обозначать...

@темы: Линейная алгебра

02:53 

Количество экстремумов функции

Довольно интересная задачка, на мой взгляд:
Существует ли такая функция, которая имеет более чем счетное число точек строгого локального экстремума?
Как я понял, все крутится вокруг уравнения `y=sin(1/x)`(естественно доопределяем в нуле нулем) Но тут проблема: найдем экстремумы: `y '=-cos(1/x)/x^2`Приравняем к нулю и полчим `x=2/(pi+2pi n)` Но отсюда следует, что экстремумов счетное количество, увы.. Значит нужно придумать однородное уравнение, которое будет иметь более чем счетное количество корней (например, континуум) и найти его первообразную... На просторах интернета нашел такую функцию (говорят, что вроде как, она имеет несчетное количество экстремумов): `y=x^2(2+sin(1/x))` и `y=0` если `x=0`; Однако я не знаю, почему это так, потому что найдя производную, я получаю уравнение, решить которое я не в состоянии.. Подскажите как доказать, что эта функция действительно имеет более чем счетное количество экстремумов? Или это не так? Спасибо!

@темы: Математический анализ

20:23 

Графы

Помогите с задачей! Спасибо)
Граф с 100 вершинами имеет 98 вершин степени 30, и по одной вершины степеней 25 и 15. Обязательно ли он будет связен?

@темы: Теория графов

21:38 

Графы

Добрый вечер! Прошу помощи в проверке решения задачи (опять по дискретке).
Вершины неориентированного графа (`n` штук) расположены на окружности и соединены через одну и через `3` (соседние вершины не соединены). При каких `n` в этом графе существует эйлеров цикл?
Сразу оговорим признак наличия эйлерова цикла: 1)граф связен 2) отсутствуют вершины нечетной степени. Про степени: во всех случаях (кроме `n=2` и `n=4`) для всех вершин степени будут четными, так для для каждой вершины однозначно поставлены в соответствие 4 вершины: две вершины "через три" (назад и вперед) и еще две "через одну" (вперед и назад). Теперь про связность: здесь будут проблемы, так как иногда у нас будет происходить зацикливание. Итак, выпишем в ряд подряд натуральные числа: `1 2 3 4 5 6 7 8 9 10 11 12.....n 1 2 3 4...n 1 2 3......n..... `(где 1-первая вершина, 2-вторая и тд) будем формировать эту цепь для конкретных `n`, например для `n=6`: `1 2 3 4 5 6 1 2 3 4 5 6 1 ....`. Итак, эта цепь нужна для того, чтобы показать алгоритм соединения вершин через 1 и через 3. Вершины соединенные через одну образуют арифм. прогрессию: `a_1=1, d=2` (например 1 соединена с 3, 3 с 5 и тд). Вершины соединенные через 3 образуют арифметическую прогрессию `a_1=1, d=4` (например, 1 переходит в 5, 5 в 9 и тд). Идя с начала нашего ряда нам нужно чтобы наши прогрессии на двоих прошли через каждое числа (от 1 до `n`, можно чтобы они были разными, главное чтобы наш алгоритм прошел через каждую-это и будет связностью графа) и при этом, чтобы они пересеклись (или одна из них пройдет все числа, при этом она, бузесловно, пересечется со второй). Так вот, если `n` четное, то у нас проблема возникает-в первой прогрессии только нечетные числа, а во второй только четные=> они никогда не пересекутся и ни одна из них не пройдет всех значений (одна не пройдет нечетные числа, другая-четные). Значит для четных `n` не будет граф связен. Теперь для нечетных `n`: тут достаточно доказать, что только при проходе "через один" будут охвачены все вершины: в первом проходе будут охвачены все нечетные числа: `1-3-5-7...-n` дальше произойдет смена четности (так как подряд в нашем ряду будет идти `n 1` и оба этих числа нечетны) и цикл пройдет через все четные числа: `2-4-6....n-1` и из `n-1` мы опять попадем в `1`. Итак, граф будет связен. Итого: только для нечетных.
Скорее всего, я не очень понятно выразил свою идею, но все же, кто попробует взяться за задачу-спасибо!)

@темы: Теория графов

19:06 

Графы

В простом неориентированном графе `5` простых циклов. Чему может быть равно его цикломатическое число?
Я придумал примеры, когда цикломатическое число равно `5`,`4`,`3`. Подскажите, как доказать, что цикломатическое число не может быть равно `2` или `1`?

@темы: Теория графов

21:27 

Помогите с теоремой из логики

Теорема:Всякая булева формула, не содержащая отрицаний, представляет монотонную функцию, отличную от `0` и `1`;
Док-во: Пусть дана булева формула, без отрицаний. Применим к ней процедуру приведения к ДНФ. Получим невырожденную ДНФ также не содержащую отрицаний. Пусть на наборе `a=(a_1......a_n) F(a)=1`. Тогда `F` содержит конъюнкцию (без отрицаний!) `x_{i1}....x_{ik}=1`, равную `1` на этом наборе. Следовательно, `a_{i1}=....=a_{ik}=1`. Рассмотрим любой набор `b`, больший чем `a`. В нем обязательно `b_{i1}=....=b_{ik}=1`, поэтому `x_{i1},.....x_{ik}` обратится в `1` и `F(b)=1`; Таким образом, условие монотонности для `F` выполнено и функция `f`, представляемая ДНФ `F` (а значит, и исходной формулой), монотонна.
Кто-нибудь, пожалуйста, объясните этот момент: ....Тогда `F` содержит конъюнкцию (без отрицаний!) `x_{i1}....x_{ik}=1`, равную `1` на этом наборе. Следовательно, `a_{i1}=....=a_{ik}=1`....здесь `x_{i1}....x_{ik}=1` это элементы конъюнкции? То есть есть `x_{i1}\wedge ....\wedge x_{ik}=1`, а что тогда означает: Следовательно, `a_{i1}=....=a_{ik}=1`. Что это за набор, что он означает?

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

22:54 

2 задачи по комбинаторике

Приключения с дискреткой продолжаются, теперь две задачи по комбинаторике. Просьба уже стандартная-проверить :-) Спасибо!
1. У велосипедиста `8` пар разных покрышек и `2` велосипеда (тоже разных). Сколькими способами можно одеть покрышки на велосипеды ( на переднем и заднем колесе могут стоять покрышки из разных пар, покрышки в паре не отличимы)? Моё решение: (заранее оговоримся, что колёса у велосипеда различимы:есть заднее и переднее) я рассматривал `3` случая: 1) мы выбрали все четыре разные покрышки 2) две из четырёх составляют пару 3) 2 пары покрышек. 1) можем выбрать четыре разные покрышки из восьми: `C^4_8`, и можем их произвольно переставить, домножим на `4!`, получим: `C^4_8*4!`. 2) можем выбрать одну пару `C^1_8` способами, ещё два непарных колеса можем выбрать `C^2_7` способами (разных(!) покрышек) и можем переставить их `8` способами (посчитал вручную, т.к `3!` там не подойдет) итого: `C^1_8*C^2_7*8` 3) Выбираем две пары из восьми: `C^2_8`, можем переставить их `4` способами. Для третьего случая получили: `C^2_8*4` способов. Итого, суммируя, получим ответ: `C^4_8*4!+C^1_8*C^2_7*8+C^2_8*4`
2. В кульке `20` конфет одного сорта. Вася взял больше половины конфет, остальные достались Лизе и Тане. Сколькими способами дети могут разделить конфеты между собой?
Моё решение: Пусть Вася вытащил `11` конфет. В таком случае осталось `9` конфет. Их мы можем распределить между девочками `C^1_10` способами. Если Вася вытащил `12` конфет, то можем распределить конфеты между девочками `C^1_9` способами и т.д. Тут, как я предполагаю, нужно сложить полученные результаты, так как таким образом мы рассмотрели все случаи, то есть получим: `sum_(k=1)^(9) C^1_{10-k}`.

@темы: Комбинаторика

19:36 

Продолжение бинарных отношений

Продолжаю терроризировать форум с дискреткой. Проверьте, кому не трудно)
Пусть `X={x_1....x_n}` и `varphi`- отношение нестрогого линейного порядка на `X`, а `psi`-отношение эквивалентности на `X`. В каом случае `varphi cap psi` будет отношением нестрого линейного порядка?
Моё решение: (сразу скажу, что я рассматриваю матрицу )рассмотрим отношение эквивалентности `psi`: для любых `x_i,x_j` будет выполнено: `(x_i,x_j)=0` и`(x_j,x_i)=0`, либо `(x_i,x_j)=1` и `(x_j,x_i)=1`(следует из симметричности). При пересечении в первом случае (когда клетки равны нулю) получим те же нули, то есть `(x_i,x_j)=0` и`(x_j,x_i)=0`, но в таком случае будет нарушена линейность (нам нужно получить линейный порядок), значит все элементы `psi` равны `1`; Причем на диагонали тоже должны стоять единицы, из-за рефлексивности. Значит, фактически, это отношение представляет собой полный граф, то есть в матрице стоят все единицы. Пересечение любого отношения с таким отношением даст исходное отношение=>полученное отношение тоже будет нестрого линейного порядка
.

@темы: Бинарные отношения

23:53 

Логика

Кому не трудно-проверьте. Спасибо!
Функция алгебры логики называется симметричной, если при любой перестановке переменных значение функции не меняется, например, `f(x,y,z)=f(y,x,z)`. Может симметричная функция от трёх переменных быть самодвойственной? Если да, то сколько таких функций?
Рисунок:
http://static.diary.ru/userdir/3/1/8/9/3189394/80371577.jpg
Моё решение: функция самодвойственна, если она принимает противоположные значения на противоположных наборах. На рисунке оранжевым обозначены наборы, симметричные `(0,0,1)`, в овал обведены наборы, симметричные `(0,1,1)`. Пусть оранжевый набор принимает значение `0`, тогда набор в овале принимает значение `1`(чтобы сохранялась самодвойственность). Тогда либо `f(0,0,0)=0` и `f(1,1,1)=1`, либо `f(0,0,0)=1` и `f(1,1,1)=0`. Аналогично для случая, если оранжевый набор равен `1` тоже будет `2` случая. Итого `4` случая.

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

21:16 

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

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

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

21:51 

Бинарные отношения

Кому не трудно, можете проверить моё решение. Спасибо!
Отношение эквивалентности `P` определено на множестве `{a,b,c,d,e,f}`. Известно, что `aPb,b bar(P)c, c bar(P)d, d bar(P)e, ePf`.
а)Приведите пример отношения, удовлетворяющего этим свойствам
б)Сколько существует таких отношений?
а) рисунок: http://static.diary.ru/userdir/3/1/8/9/3189394/80354682.jpg
б) Рассмотрим матрицу, приведённую на рисунке выше: будем заполнять её так, чтобы она оставалась матрицей отношения эквивалентности. То, что написано ручкой изменить не можем (из-за рефлексивности, симметричности, а также из условий `aPb,b bar(P)c, c bar(P)d, d bar(P)e, ePf`), будем менять только то, что написано карандашом, причём будем рассматривать только верхний правый угол (левый нижний будет меняться абсолютно так же из-за симметричности). Например, в клетке `(a,c)` можем поставить как `0`, так и `1`, так как в строке `c` единиц будет две-одна: `(c,a)`, вторая: `(c,c)`=> транзитивность не нарушена. Аналогично в клетке `(a,d)` можем поставить `1` или `0`. Теперь для клетки: `(a,e)`: если там будет `1`, то транзитивность нарушена, так как `(e,f)=1`=> если мы ставим `1` в `(a,e)`, то мы должны поставить `1` в клетку `(a,f)`. По аналогии для строчки `b`: в клетке `(b,d)`-либо `0`, либо `1`, в клетках `(b,e)` и `(b,f)` либо нули, либо единицы. Для строки `c`: в клетках `(c,e)` и `(c,f)` либо нули, либо единицы. Итого получили `6` независимых (из шести-три по одной клетке, три-пара клеток) клеток, в которые можно поставить `1` или `0`. Таким образом всего таких отношений: `2^6`;

@темы: Бинарные отношения

01:35 

Снова логика

Существует ли
а)линейная и монотонная
б)нелинейная и монотонная
функция, существенно зависящая от 4-ёх переменных?
Решение:
а) Нет, не существует. Нам дано, что функция линейна => представима в виде полинома Жегалкина первой степени. А значит она представима в виде: `x_1 oplus x_2 oplus x_3 oplus x_4 oplus a` (здесь нет других переменных, так как функция существенно зависит только от четырёх переменных. Коэффициенты при `x_1,x_2,x_3,x_4` не равны нулю, потому что в таком случае функция существенно зависела бы от `n < = 3` переменных ), где `a in {0,1}`. Можно рассмотреть оба случая: `a=0` и `a=1`; При `a=0` функция немонотонна: `f(0,0,1,0)=1;f(0,0,1,1)=0`. При `a=1`: `f(0,0,0,0)=1;f(0,0,0,1)=0`=>немонотонна.
б) Да, существует, например: `x_1x_2x_3x_4`
Проверьте, пожалуйста. Что-то мне подсказывает, что в пункте а) не может быть только два случая к рассмотрению, хотя по логике вещей именно так и есть.

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

20:54 

Определение существенно зависящей функции (дискретка)

Добрый вечер! Не подскажите определение существенно зависящей функции от трёх переменных? Я нашёл определение существенно зависящей функции от одной переменной, вот оно: Булева функция `y=f(x_1,x_2 ... x_n)` существенно зависит от переменной `x_k`, если существует такой набор значений `a_1,a_2 ... a_{k-1}, a_{k+1}, a_{k+2} ... a_n`, что `f(a_1,a_2 ... a_{k-1}, 0, a_{k+1}, a_{k+2} ... a_n) != f(a_1, a_2 ... a_{k-1}, 1, a_{k+1}, a_{k+2} ... a_n)`. То есть при изменении переменной меняется и значение функции. Логично было бы предположить это же и для трёх переменных : меняется одна из них, меняется и значение функции, меняются только две => значение не меняется, меняются три => меняется. Однако это не так (на контрольной за это минус поставили). Подскажите, что же это.

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

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` ? И, соответственно, как найти их композиции?

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

21:17 

Необычная просьба

Добрый вечер!У меня необычный вопрос:недавно нашел в интернете пособие, в котором подробнейшим образом разбиралась задача. Отложив в отдельную папку на "разбор на потом", успешно потерял её....Может кто может помочь и знает, как называется это пособие(или книга в электронном виде) или автора...а задача такая:Дана последовательность `a_n` ,причем `a_1=a > 0`;`a_2=a^a`;`a_3=a^a^a`.....`a_(n+1)=a^(a_n)` и рассматривались случаи при каких `a` сходится, а при каких расходится. Заранее спасибо!

@темы: Математический анализ

01:31 

Рекурентные соотношения и уравнение общего члена

Всем доброй ночи! Сразу скажу, что я читал и знаю как находить общую формулу элемента последовательности при помощи характерестического уравнения. Собственно, прошу консультации в таких вопросах:1) если есть последовательность, заданная рекуррентным соотношением,но при этом присутствует свободной коэффициент,например `x_n=1+2x_(n-1)` Как в таких случаях поступать? 2)Аналогичный вопрос,но у нас нет линейности,то есть, например:`(x_n)^2=x_(n+1)+1`
Заранее спасибо!

@темы: Математический анализ

18:04 

Последовательность..

Помогите,пожалуйста,с задачей:Последовательность `{x_n}` такова, что для всех `n`,начиная с некоторого,выполняется неравенство `0 < x_(n+1) < x_n` , и последовательность `sum_(k=1)^(n) x_n` сходится. Докажите,что `lim_(n -> infty) n*x_n=0`.
Собственно,обычно,люди пишут свои догадки в задаче....Но,к сожалению,я не продвинулся даже с условия...

@темы: Математический анализ

17:35 

Задача про возрастающие/убывающие подпоследовательности последовательности:)

Добрый день,форумчане! Помогите разобраться с решением такой задачи:

"Докажем, что любая последовательность из `mn + 1` попарно различных чисел содержит либо возрастающую последовательность из `m + 1` чисел, либо убывающую последовательность из `n + 1` чисел.

Сопоставим члену `a_k` данной последовательности два числа `x_k` и `y_k`, где `x_k` – наибольшая длина возрастающей последовательности, начинающейся с `a_k`, `y_k` – наибольшая длина убывающей последовательности, начинающейся с `a_k`.
Предположим, что `x_k <= m` и `y_k <= n` для всех `k`. Тогда количество всех различных пар `(x_k, y_k)` не превосходит `mn`. Поэтому `x_k = x_l` и `y_k = y_l` для некоторых номеров `k, l`.
Пусть для определённости `k < l`. Тогда если `a_k < a_l`, то `x_k > x_l`, а если `a_k > a_l`, то `y_k > y_l`. Противоречие. Следовательно, `x_k > m` или `y_k > n` для для некоторого `k`".


Я не понимаю с момента:"Поэтому `x_k = x_l` и `y_k = y_l`..."
Не могли бы вы объяснить,зачем вообще делается такая замена??

@темы: Математическая логика, Математический анализ, Олимпиадные задачи

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

главная