Очень нужно помочь с этими заданиями, сейчас!

[flame19]

задали данные задания, но ни как нее могу разобраться.
помогите хоть с один решением,заранее спасибо
1) Рассмотрим задачу о рюкзаке : по набору предметов `A = {a1....an}` их объемов `s(a1)...s(an)` и числу `B` найти такое подмножество `A' subseteq A` для которого `sum_{a in A'} s(a) = B`.
Используем для ее решения алгоритм "динамич. программирования" . Пусть `m(i,j) = 1` если среди первых `i` предметов `a1...ai` можно выбрать подмножество общего объема `j`, иначе `m(i,j) = 0`. Напишите реккурентное соотношение для `m(i,j)` Определите сложность решения задачи о рюкзаке, т.е . вычисления `m(n,B)` через параметры задачи. Является ли предложенный алгоритм полиномиальным?

2) Пусть задано циклическое слово S[1..n] в котором за каждым символом S(i) следует символ S(i + 1 mod n) Задача состоит в том, чтобы выбрать место разрезания этого слова i так чтобы получившееся линейное слово S<верхний index i> = S(i)...S(n)S(1)....S(i - 1) было лексикографически минимальным среди всех таких линейных слов. Предложите алгоритм линейной сложности для линеаризации циклических слов.

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

---

очень нужно

[flame19]

Пусть дано множество W, состоящее из К различных строк (слов) суммарной длины n. Для каждого i от 2 до K определить l(i) как длину самой длинной подстроки, входящей в не менее чем в i строк W. Задача состоит в том, чтобы построить таблицу из (K-1) -й строки, в которой для каждого i указано число l(i) и какая-нибудь строка длины l(i), входящая в >= i строк из W.
указание. построим объединенное суффикcное дерево T для множества W, в котором каждый лист имеет метку слова, суффикс которого в этом листе заканчивается. Для каждой внутренней вершины v обозначим через C(v) число различных слов из W, суффиксы которых заканчиваются в поддереве с корнем v.

a) Нужно предложить алгоритм вычисления значения C(v) для всех внутренних вершин T за время O(Kn)
б)показать,как, зная значения C(v) для всех внутренних вершин, построить требуемую таблицу за время O(n).

у меня тоже попалось такое задание? кто-нибудь знает что с этим можно сделать?

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

---

[[~Shadow~]]

Закрытая запись, не предназначенная для публичного просмотра

---

Теория чисел. Группы

[Old Nick]

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

Посоветуйте, пожалуйста, литературу по темам:
Кольцо классов вычетов по модулю: таблица сложения и умножения, противоположный и обратный элементы, делители нуля, порядок элемента. Свойства порядка элемента. Разложение мультипликативной группы кольца в прямое произведение циклических групп. Строение мультипликативной группы кольца классов вычетов по четному примарному модулю. Поле классов вычетов по простому модулю. Мультипликативная группа поля.

Желательно, чтобы объяснялось кратко и доступно. Углубленная теория пока не нужна, только основы. Скачал несколько учебников, но ничего не нашёл (Виноградов, Бухштаб и т.д.). Скачал Куроша, Теория групп, там слишком много и сложно, мне за такое пока рано браться.

@темы: Теория групп, Посоветуйте литературу!, Теория чисел

---

1.140

[dana-beisalieva]

Упростить выражения. Найти области допустимых значений параметров, если они не указаны.
`(a/(3(a^2+1)^(0,5))-(2a^2+1+a sqrt(4a^2+3))^(0,5)/(2a^2+3+a sqrt(4a^2+3))^(0,5))^2`
Ответ: `(4a^2+3)/(9(a^2+1))`, a принадлежит R
Как доказать что a принадлежит R?

@темы: Школьный курс алгебры и матанализа

---

Линейные пространства...

[косявр]

Образуют ли линейное пространство все векторы, концы которых лежат:
а) на данной прямой;
б) в первой или третьей четверти;
в) в первой или второй четверти?

Помогите пожалуйста разобраться, пункт а), как я понимаю, имеются в виду коллинеарные векторы, тогда они образуют линейное пространство.

пункт б) имеется в виду, что координаты векторов (x, y) (если рассматривать двумерное пр-во) или положительные или отрицательные, в таком случае, произведение на отрицательное число даст противоположный знак и получившийся вектор так же будет принадлежать этому множеству как и сумма этих векторов. Очевидно выполнение аксиом, существование 0 и единичного векторов, которые также принадлежат множеству. Т.о. это лин. пр-во.

пункт в) имеется в виду, что координаты векторов (x, y) (если рассматривать двумерное пр-во) имеют положительную у координату и или положительную, или отрицательную х, но в таком случае, произведение на отрицательное число даст противоположный знак и получившийся вектор не будет принадлежать этому множеству.

Подскажите, я права? Если нет, то в чем ошибаюсь и как это грамотно записать?
Заранее, спасибо!

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

---

Задача на доказательство

[Nevemore]

Доказать что в пространстве всех матриц размером `N_2 x N_1` можно ввести скалярное произведение по формуле `(X,Y) = tr(X_T Y)`, `X_T -` транспонированная, tr -след матрицы. С чего начать, в чем идея?

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

---

[flame19]

Добрый день всем кто это читает!

Помогите пожалуйста с двумя заданиями:
Сразу скажу, что с алгоритмом Штрассена я знакома лучше.

1) Предположим, что существует алгоритм, вычисляющий произведение двух 8 х 8 матриц, используя 150 операций умножения и 220 операций сложения. Алгоритм какой сложности для умножения n x n матриц можно было бы тогда получить? Будет ли он лучше алгоритма Штрассена?

2) Поиск всех вхождений слов-образцов.
Пусть задано множество слов-образцов P = {U1,...Uk}, суммарная длина которых равна n. Требуется найти все вхождения этих образцов в текст S длины m. Докажите, что это можно сделать с использованием суффиксного дерева за время O(n+m+r), где r - общее число искомых вхождений.
Примечание для 2: используется алгоритм Уконнена

СПАСИБО!

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

---

Проблемма с диф уравнением

[illuminates]

y''+9y=sin(3x)

вопрос : у нас кратность два или один, т е домнажаем частное на x или x^2?

@темы: Дифференциальные уравнения

---

c4 не могу понять как нашли DE!

[an96]

alexlarin.net/ege/mioo2011/ege11m101020krit.pdf

Дан треугольник `ABC`: `AB = 10`, `BC= 5`, `AC = 6`. Точка `D` лежит на прямой `BC` так, что `(BD)/(DC) = 1/2`. Окружности, вписанная в из треуг-к `ADC` касается стороны `AD` в точке `E`, а окружность, вписанная в треуг. `ADB` касается (той же) стороны `AD` в точке `F`. Найти длину отрезка `FE`.

@темы: Планиметрия, ЕГЭ

---

Поток векторного поля

[FFold]

1) найти поток векторного поля а через замкнутую поверхность ơ = ơ1+ơ2(выбирается внешняя нормаль к ơ);

2) вычислить циркуляцию векторного поля a по контуру Г, образованному пересечением поверхностей ơ1, и ơ2 (направление обхода должно быть выбрано так, чтобы область, ограниченная контуром Г, находилась слева);

3) проверить правильность вычисленных значений потока и циркуляции с помощью формул Остроградского и Стокса;

4) дать заключение о наличии источников или стоков внутри области, ограниченной поверхностью ơ;

5) сделать схематический чертеж поверхности ơ.

Выполнить задания, взяв в качестве вектора а вектор rotG



` G = 2 xi - (xz -2 y)j + (4 + z^2)k `

` ơ1: x^2 + у^2 -2 z -3 = 0 `

` ơ2 : z = - 1 `



Нормали правильны?

` n1=(xi+yj-k)/sqrt(x^2+y^2+1) `

` n2=k `





Уже пол книжек перелопатил, что-то ни как

Ничего толкового не получается, может поможет кто, советом, формулой или решением аналогичных задач.

@темы: Теория поля, Приложения определенного интеграла, Кратные и криволинейные интегралы

---

Могли бы вы помочь

[seremuxa]

Пусть дано множество W, состоящее из К различных строк (слов) суммарной длины n. Для каждого i от 2 до K определить l(i) как длину самой длинной подстроки, входящей в не менее чем в i строк W. Задача состоит в том, чтобы построить таблицу из (K-1) -й строки, в которой для каждого i указано число l(i) и какая-нибудь строка длины l(i), входящая в >= i строк из W.
указание. построим объединенное суффикcное дерево T для множества W, в котором каждый лист имеет метку слова, суффикс которого в этом листе заканчивается. Для каждой внутренней вершины v обозначим через C(v) число различных слов из W, суффиксы которых заканчиваются в поддереве с корнем v.

a) Нужно предложить алгоритм вычисления значения C(v) для всех внутренних вершин T за время O(Kn)
б)показать,как, зная значения C(v) для всех внутренних вершин, построить требуемую таблицу за время O(n).

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

---

Как научиться думать?

[Old Nick]

Заметил, что мозг совершенно не умеет работать. Например, надо знать доказательство теоремы. Если я его разберу и выучу практически наизусть, то я его смогу ответить. Если же просто буду знать все определения и свойства, которые используются в доказательстве, даже общий принцип, но не выучу его, то всё, буду просто смотреть на формулировку и ничего не смогу сделать. Так, на прошедшем экзамене по алгебре ответил на сложный вопрос - воспроизвёл доказательство на 1,5 страницы (с полным пониманием того, что происходит) и не смог ответить на два простых вопроса, в одном из которых доказательство было в две строчки, абсолютно тривиальное, а принцип другого я даже знал, но не смог применить. Что-то придумать самостоятельно вообще не получается. Поэтому теоретические задачи абсолютно не даются.
Получается, в случае с доказательствами только зубрёжка (ну, разумеется, с пониманием)? Однако она отнимает много времени, а сейчас, в условиях нехватки времени для подготовки к экзаменам, это плохо.
Что делать?

@темы: Образование

---

Решить систему.

[MANISHAPOWER]

`{(2x^2 + xy - 4 = 0), (2y^2 + xy - 10 = 0):}`

Подскажите как решить)

@темы: Системы НЕлинейных уравнений, ЕГЭ

---

Скажите пожалуйста где это можно найти

[tanya_VVV]

Изобразите графики функций, имеющих точки разрыва конечного и бесконечного скачка. Существует ли предел функции в точке разрыва? Односторонние пределы?

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

---

Исследование на непрерывность ф-и двух переменных с переходом к полярным координатам

[rissy44k]

Пожалуйста, помогите немного по математическому анализу.
Если при исследовании непрерывности необходимо перейти к полярным координатам, а там в знаменателе получается свободный от r синус или косинус (к примеру: `lim_(r->0)((r*sina*cosa)/(r*cosa+5sina))` ), то он всё-таки существует или нет, этот предел?
Долго искал ответ, выяснил, что предел не существует если зависит от угла, но зависимость может получиться, если sinφ=0, но при этом cosφ не равен нулю, а r только стремится, поэтому так доказывать нельзя. Можно ли объяснить не существование предела по такой причине, что sinφ может принимать значение r или 1/r, или как-то ещё по другому?

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

---

Проблемма с диф уравнением

[illuminates]

Найти полосу в которой решение задачи y'=x+y^3,y(0)=0 существует и единственно.


в обще не понимаю что хотят, выручайте братцы. может это обратная краевая задача?

@темы: Дифференциальные уравнения

---

Задача № 1.141 Из Сканави

[dana-beisalieva]

Упростить выражения. Найти области допустимых значений параметров, если они не указаны.
`sqrt((a-8root(6)(a^3b^2)+4root(3)(b^2))/(sqrt(a)-2root(3)(b)+2root(12)(a^3 b^2))+3root(3)(b))`
После приведения к общему знаменателю получилось вот что:
`sqrt((a-2root(3)(b^2)-3sqrt(a)root(3)(b)+6a^(1/4)b^(1/2))/(sqrt(a)-2root(3)(b)+2root(12)(a^3 b^2))`
Ответ: `|root(4)(a)-root(6)(b)|` `a>=0`, `b>=0`, `a+b!=0`

@темы: Школьный курс алгебры и матанализа, Тождественные преобразования

---

NP-полнота задачи РАЗБИЕНИЕ НА ТРЕУГОЛЬНИКИ

[flame19]

Всем привет! прошу помочь решить такую задачу:
Докажите NP-полноту задачи РАЗБИЕНИЕ НА ТРЕУГОЛЬНИКИ:
вход: неор. граф G=(V,E), такой, что для некоторого целого q: |V|=3q (т.е. число вершин равно 3q)
вопрос: можно ли разбить вершины графа G на q непересекающихся множеств V1,...,Vq, каждоое из которых содержит ровно 3 вершины, попарно соединённых ребрами, т.е. для каждого i=1,...,q V(i)={u(i), v(i), w(i)} и (u(i), v(i)), (v(i), w(i)), (w(i), u(i)) принадлежат множеству рёбер Е.

вот моё решение:
К задаче РАЗБИЕНИЕ НА ТРЕУГОЛЬНИКИ можно свести задачу 3-МЕРНОЕ СОЧЕТАНИЕ. Т.к. задача 3-С. - NP-полная, то и РАЗБИЕНИЕ НА ТРЕУГОЛЬНИКИ -тоже NP-полная.
нужно доказать что 3-С. можно свести к этой задаче.
задачу 3-С. можно формально записать так:
M=W*X*Y (M,X,Y,W - множества)
M' содержится в M, если (w,x,y) принадлежат M' и (w', x', y') принадлежат M' и w!=w', x!=x', y!=y'

теперь опишем представление графа G:
его вершины разобьём на три группы размером q вершин:
|X|=|Y|=|W|=q

теперь нужно описать что из себя представляют эти вершины и ребра. вот с этим и возникают трудности. понятно, что наши вершины в графе будут соответствовать элементам 3-мерного сочетания. а про рёбра вообще нет идей... Подскажите пожалуйста, как закончить доказательство??
Заранее спасибо!

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

---

Дифференцируемость..

[gl2u]

Исследовать функции на дифференцируемость:

1) `f(x,y)={((x^2 + y^2)*sin(1/(x^2+y^2)) , if x^2 + y^2 > 0),(0 , if x=y=0.):}
в точке (0,0)


2) `f(x,y)={((xy)/(sqrt(x^2+y^2)) , if x^2 + y^2 > 0),(0 , if x=y=0.):}
в точке (0,0)

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