 Форум мехмата МГУ по высшей математике
| Пользователям: | Аксиома — это истина, на которую не хватило доказательств. |
Все посты пользователя
Новости проекта «Математический форум», анонсы и обсуждение новых возможностей, общение с разработчиками, предложения по развитию сайта.
хеш-таблицы и деревья - 17 лет назад
1. Можно использовать готовые хеш-функции, специально разработанные для строк (MD5, Tiger и т. п.). 2. Другой способ организации очень быстрого словаря - TST-дерево. Сравнение различных деревьев можно найти в статье Бентли и Сэджвика. Скорость построения словаря также обсуждалась на другом форуме (правда, там больше сравнивались не алгоритмы, а языки программирования). 3. При любой "умавтор egor - Высшая математика
Подсказка: дополнить до ортонорм. базисов - 17 лет назад
Подсказка: считать |a|=|b|=1, дополнить одновекторные системы {a} и {b} до ортонормальных базисов, обозначить через A и B матрицы, составленные из векторов-столбцов этих базисов. Матрицы A и B унитарные (в Вашей терминологии - ортогональные). Теперь легко сообразить, какая матрица сойдёт в качестве U.автор egor - Высшая математика
Красиво! Кстати, нашёл старое обсуждение - 17 лет назад
По-моему, великолепное доказательство. Фактически, итеративный процесс очень похож на построение цепной дроби (на каждом шаге используется целая часть от 1/x), но сразу заточен на решение данной задачи. Кстати, обнаружил старое обсуждение задачи о sin(n): http://www.mathforum.ru/forum/read/1/5770/5770/#5770автор egor - Высшая математика
Теорема известная. Интересно Ваше доказательство. - 17 лет назад
Цитата Maxim писал: Я догадался что справедливо следующее. (Теорема) Для любого E>0, для любого X вещественного, для любого alpha иррационального, существуют такие (вообще ненулевые) целые n и m что: |(n+m*alpha)-X|<E. Иными словами: целочисленная линейная комбинация единицы и иррационального числа может сколь угодно близко приблизить любое вещественное число. Потом доказал этоавтор egor - Высшая математика
странно, что ссылки не работают - 17 лет назад
Цитата Maxim писал(а) : У меня ни одна ссылка не работает. Непонятно. Только что проверил: страницы библиотеки lib.mexmat.ru и страница с заметкой Максима Алексеева о последовательности 1/(n^3 sin(n)) нормально открываются. Другое дело, что прямо с lib.mexmat.ru книги скачать нельзя. Можно найти на http://www.poiskknig.ru и http://www.eboogle.ru.автор egor - Высшая математика
цепные дроби и другие подходы - 17 лет назад
Задача сводится к приближению числа pi рациональными числами. Есть хорошо разработанные теории приближения иррациональных чисел рациональными. Касселс "Введение в теорию диофантовых приближений". Один из стандартных аппаратов - теория цепных дробей (другое название - непрерывные дроби). Хинчин "Цепные дроби". Некоторые элементарные результаты (которых достаточно дляавтор egor - Высшая математика
решение для пяти чисел - 17 лет назад
Здесь удобен такой критерий: два числа взаимно просты <=> у них нет общих простых делителей. Если p простое и p>=5, то p может быть делителем лишь у одного из наших 5 чисел. Следовательно, нужно заботиться только о делимости на 2 и на 3. Среди данных пяти чисел подойдёт такое, которое не делится ни на 2, ни на 3, т. е. имеет вид 6n+1 или 6n+5. Такие "хорошие" числа идут другавтор egor - Высшая математика
План решения - 17 лет назад
Цитата Eugene писал(а) : Как доказать, что слабое замыкание единичной сферы в l_2 есть единичный шар? Очень подробный план решения. 1. Вспомнить, что каждый непрерывный линейный функционал f на l_2 имеет вид f(x)=\sum_{n=1}^\infty x_n y_n*, где y - некоторая последовательность из l_2, звёздочка обозначает операцию сопряжения комплексного числа (если рассматривается действительное l_2, то савтор egor - Высшая математика
Случай перпендикулярных векторов - 17 лет назад
Итак, последний шаг вызвал проблемы. Да, в рассматриваемой плоскости приходится переходить к новой системе координат, но это несложно. Упражнение 4. Даны взаимно перпендикулярные векторы a и c одинаковой длины. Построить вектор r, который получается поворотом вектора a на угол alpha в направлении вектора c. В плоскости, порождённой векторами a и c, рассмотрим базис a, c. Любой вектор, лежащиавтор egor - Высшая математика
подсказки - 17 лет назад
Прежде всего, с помощью сдвига нужно сделать точку (x0,y0,z0) началом координат. Более подробно: из всех векторов вычесть (x0,y0,z0), решить полученную задачу, затем к ответу нужно будет прибавить (x0,y0,z0). Теперь будем считать, что все векторы - это радиус-векторы, т. е. начало расположено в начале координат. Несколько вспомогательных упражнений. 1. Даны векторы a и b. Найти вектор n, перпенавтор egor - Высшая математика
Найти бы инварианты бит-матриц относит. перестановок... - 17 лет назад
Переформулирую Вашу задачу ещё одним способом. Бит-матрицей будем называть матрицу с элементами из {0,1}. Дана бит-матрица размера K на N. Сколькими способами можно расставить на клетках с единицами K ладей, чтобы ни одна из них не находилась под ударом другой? Очевидно, искомое число способов можно найти с помощью рекуррентного алгоритма экспоненциальной сложности. Видимо, цель в том, чтобавтор egor - Высшая математика
подсказка - 17 лет назад
Вопрос-подсказка: где должен лежать центр окружности?автор egor - Высшая математика
Наибольшего элемента не будет - 17 лет назад
Цитата AlexDemche писал(а) : Во первых, на носителе задан полный порядок, то есть (i) очевидно выполнено. Во вторых, групповая операция согласована с порядком, т. е. a <= a' и b <= b' => a + b <= a' + b'. Да, это более естественная формулировка. Но похоже, что она равносильна "моим" условиям (i), (ii), (iii). Ведь для линейного (=полного) порядка условие согласованностиавтор egor - Высшая математика
как связаны операция и порядок? - 17 лет назад
Цитата AlexDemche писал(а) : существуют ли примеры групп с бесконечным числом элементов, тем не менее имеющих наименьший и наибольший? Тут нужно определиться, насколько сильно порядок связан с групповой операцией. Рассмотрим случай, когда порядок связан очень тесно: (i) для любого a выполняется ровно одно из трёх условий: либо a>e, либо a=e, либо a<e; (ii) для любых a и b из a&gавтор egor - Высшая математика
Нельзя (следует теоремы Лагранжа) - 17 лет назад
Цитата AlexDemche писал(а) : Можно ли группы по обычному умножению или сложению расширить на случай расширенной прямой (R U {+\infty} U {-\infty})? Нельзя. Группу G можно расширить двумя новыми элементами лишь тогда, когда сама G состоит из одного либо двух элементов. Доказательство сразу следует из теоремы Лагранжа: исходная группа является подгруппой для расширенной группы, поэтому расширеннаавтор egor - Высшая математика
ещё раз - 17 лет назад
Не знаю, как тут ещё проще объяснить. :-( Поэтому просто повторю заново всё, что уже раньше писал. :-) Рассматриваем задачу, когда неподходящий ключ возвращается в мешок. Через x обозначим среднее число попыток, которое требуется для взлома замка, т. е. мат. ожидание случайной величины кси - числа попыток. Чтобы составить уравнение для x, разобьём пространство событий на случаи H1 и H2 и воспольавтор egor - Высшая математика
да, нет (выразить через x) - 17 лет назад
Цитата tania писал(а) : P(H2)=(n-1)/n ? Да. Цитата E(xi|H2)= 1+n ? Нет. Непонятно, откуда взялось слагаемое n. Нужно выразить E(xi|H2) через x. Кстати, у esperanto очень красивое решение. Только нужно немножко разбираться в мартингалах.автор egor - Высшая математика
по поводу P(H2) и E(xi|H2) - 17 лет назад
Цитата tania писал(а) : что такое H1 и H2 это ясно! P(H1) = 1/n и P(H2)=1/n так? Нет, не так. Сколько неподходящих ключей в мешке? Чему равно P(H2)? Можно ещё так рассуждать: H1 и H2 - противоположные события. Их вероятности в сумме должны давать 1. Цитата E(xi|H2)= ????? Вспомним, что через x обозначено среднее число попыток, нужное для открывания двери, когда в мешке находятся n ключавтор egor - Высшая математика
виноват, перепутал ответы - 17 лет назад
Цитата tania писал(а) : теперь вроде поняла :) ТО есть ответ на 2 условие будет: n ??? 1 * P(A_1) + 2 * P(A_2) + ... + n * P(A_n)=n ??? Виноват, перепутал ответы в своём первом сообщении. Теперь исправил. Когда неподходящий ключ не возвращается в мешок: нужно честно посчитать P(A_k) для всех k (k=1,2,3,...,n) и показать, что 1 * P(A_1) + 2 * P(A_2) + ... + n * P(A_n) = (n+1)/2. Когда кавтор egor - Высшая математика
P(A_1) и P(A_2), когда ключ не возвращается - 17 лет назад
Рассмотрим условие 2 (когда ключ не кладётся обратно в мешок). Вероятность вытащить правильный ключ с первой попытки равна 1/n: P(A_1) = 1/n. Вычислим P(A_2), т. е. вероятность того, что дверь будет открыта со второй попытки. Сначала вытаскивается неподходящий ключ. Вероятность этого равна (n-1)/n. Затем неподходящий ключ выбрасывается, и число оставшихся ключей будет равно n-1. Значит, вероятноавтор egor - Высшая математика
Любопытно узнать Ваш ход решения - 17 лет назад
Цитата tania писал(а) : эмммм, а не могли бы вы поконкретнее с решением???:) что то у меня никак не получабтся такие ответы.... Любопытно, какие величины получились у Вас: P(A_k) для случая 1), P(A_k) для случая 2), P(H1), P(H2), E(xi при условии H2). Буквой xi (кси) обозвал случайную величину, равную среднему числу попыток.автор egor - Высшая математика
забыл сказать, что такое H1 и H2 - 17 лет назад
Забыл сказать, какие события обозначены через H1 и H2 во втором способе решения. H1 - первая попытка взлома оказалась удачной; H2 - первая попытка взлома была неудачной. Цитата tania писала : уфффф....как тут всё сложно :)) спасибо огромное... За задачку спасибо. Давно такие не решал, так что извиняйте за корявые объяснения.автор egor - Высшая математика
подробный план решения и ответы - 17 лет назад
Цитата tania писала: Задачка такова: Парень стоит у дверей в дом и пытается открыть дверь случайно выбранным из мешка ключом. в мешке всего n ключей. Сколько раз в среднем ему придется пробовать открыть эту комнату, если: 1) проверенный ключ кладется обратно в мешок 2) проверенный ключ НЕ кладется обратно в мешок. Первый способ решения (хорош для ситуации 2). Обозначим через A_k следующеавтор egor - Высшая математика
это начала комплексного анализа - 18 лет назад
Это относится к элементам комплексного анализа (теории функций комплексного переменного). См. учебники: Привалов, Лаврентьев и Шабат, и др. (искать через http://www.poiskknig.ru). По данному конкретному вопросу немножко написано в конспектах занятий 11 и 12 со странички http://maxmath.narod.ru/ma4.htm.автор egor - Высшая математика
доки к MATLAB? преобразования Холецкого? - 18 лет назад
Цитата cyberblonde писал(а) : Размер моей матрицы - больше 1000*1000. Структура - скорее, специальная (разреженные, либо блочного вида матрицы). Конкретно для разреженных матриц , я слышала, существуют алгоритмы, позволяющие обращать марицу за О(n^2.3). При том, что Гауссом за O(n^3). Вот, описание соответствующего алгоритма я и ищу. Слышал, будто разреженные матрицы неплохо реализованы в MATавтор egor - Высшая математика
названия книг - 18 лет назад
Цитата cyberblonde писал(а) : А в каком именно учебнике Кнута Вам это встретилось? Ни в "Конкретной математике. Основании информатики.", ни в "Математических методах анализа алгоритмов" я не смогла найти ничего похожего... Кнут, "Искусство программирования. Том 2. Получисленные алгоритмы." В разделе 4.6.4 упоминается алгоритм Штрассена. Не знаю, обсуждается ли вавтор egor - Высшая математика
В каком виде дана сеть? - 18 лет назад
Тут важно, в каком виде дана сетка. 1. Можно ведь задать сетку в таком виде, что сразу видно, где у неё границы и углы. Например, если сетка задана в виде текстового файла: A-B---C | | | D-E-F-G | | | H---I-J 2. Сетка может быть задана как произвольный неориентированный граф. Например, через матрицу смежности или списки соседей: A: B, D B: A, C, E C: B, G D: A, E, G E: B, D, F F: E, G, I G:автор egor - Высшая математика
переделать алгоритм Штрассена - 18 лет назад
Слышал, будто алгоритмы быстрого умножения матриц (например, алгоритм Штрассена и ещё более хитроумные) можно переделать для обращения матриц. Кажется, об этом написано в учебниках Ахо-Хопкрофта-Ульмана и Кнута. Но выигрыш во времени получается лишь для матриц очень больших размеров. Кроме того, погрешности накапливаются быстрее, чем в обычном алгоритме Гаусса.автор egor - Высшая математика
ещё нужно учитывать, в каком ряду пустышка - 18 лет назад
Цитата jura05 писал(а) : совершенно верно, инвариант = четность перестановки! см., например, статью "Пятнашки" в Википедии Это если пустышка находится в последнем ряду. В общем случае, нужно учитывать чётность перестановки и чётность номера ряда (горизонтального), в котором находится пустышка.автор egor - Высшая математика
нет, это функция Хэвисайда - 18 лет назад
Цитата Giggs писал(а) : Предлагаю назвать альфой функцию, равную нулю при отрицательных значениях аргумента и единице при положительных. Будет как бы интеграл от дельта-функции Дирака. Нет, для такой функции уже есть название и обозначение: http://ru.wikipedia.org/wiki/Функция_Хевисайдаавтор egor - Высшая математика